Movimiento sobre puntos racionales

Hoy martes os traigo el problema de esta semana. Ahí va el enunciado:

Sea $P$ el conjunto de puntos de $\mathbb{R}^n$ que cumplen que todas sus coordenadas son números racionales. La cuestión es que queremos movernos entre esos puntos, pero vamos a poner una restricción a este movimiento: sólo podemos movernos de un punto a otro si están a distancia 1. Es decir:

Dados $A,B \in P$ , podemos movernos desde $A$ hasta $B$ siempre que el segmento $AB$ tenga longitud 1.

En estas condiciones, demostrar que desde un punto cualquiera de $P$ , digamos $M$ , se puede llegar a cualquier otro punto de $P$ , digamos $N$ , en un número finito de movimientos si y sólo si $n \ge 5$ , es decir, si estamos trabajando en $\mathbb{R}^5$ o superior.

En particular, este resultado nos dice que ni en el plano ni en el espacio tridimensional (ni siquiera en cuatro dimensiones) podemos viajar de esta forma de todo punto racional a cualquier otro.

A por él.

25 comentarios

jbgg | 12 de July de 2011 | 13:31

Dios! que interesante cuestión, no la conocía!

Si es cierta es interesante… a ver como se demuestra, bueno en $\mathbb{R}^1$ es fácil ver que no se cumple xD
Muchas gracias por darla a conocer.
Sebastián | 12 de July de 2011 | 19:41

Tengo una duda. Cuando el enunciado refiere a moverse de M a N en un número finito de movimientos, ¿se refiere a que entre M y N hay movimientos de distancia uno, pero no sólo uno posible? ¿O se refiere a que se puede construir un ‘camino’ de M a N pasando por puntos intermedios con movimientos de distancia uno entre éstos? Gracias.

*(lo estoy intentando mediante espacios afines y variedades lineales)
gaussianos | 12 de July de 2011 | 20:01

Sebastián, significa que se puede construir un camino de M a N pasando por puntos intermedios donde todos los movimientos se han entre puntos a distancia 1 (no podemos ir directamente de un punto a otro si no están a distancia 1).

¿Alguna duda más?
vengoroso | 12 de July de 2011 | 20:46

(4) Este problema se ve muy interesante! Ademas creo que se adaptaria muy bien a intentar una “solucion colaborativa” al estilo que propusieron Tim Gowers y Terry Tao con los problemas “polymath”. Os parece interesante la idea?

De momento, voy a hacer mi colaboracion parcial de esa manera (numero mi comentario como 4 por si alguien lo cita despues).

Primera observacion obvia, es que basta con probar (sin perdida de generalidad) que se puede alcanzar cualquier punto $P$ comenzando desde el origen de coordenadas.

Como dice jbgg en (1) es obvio que para $n=1$ comenzando desde el origen solo se pueden alcanzar los enteros, o dicho de otra manera, desde un numero real se puede llegar a otro si y solo si la diferencia entre ambos es un entero.

El problema es mas interesante para el caso $n = 2$ , desde el punto $(0,0)$ podemos saltar al punto $(a,b)$ si y solo si $a^2 + b^2 = 1$ . Reescribiendo $a, b$ como fracciones y eliminando denominadores obtenemos que cada salto valido se corresponde con una terna pitagorica, y los puntos alcanzables desde el origen son los que se pueden obtener como suma de fracciones obtenidas a partir de ternas pitagoricas. El siguente paso es usar la parametrizacion conocida de estas ternas para obtener una caracterizacion mas explicita.
Sebastián | 12 de July de 2011 | 22:47

@Gaussianos: perfectamente explicado. Gracias
gaussianos | 13 de July de 2011 | 01:13

De nada
Félix | 13 de July de 2011 | 10:15

Al leer a (4) he tenido una idea, que solo hace falta demostrarlo para puntos contenidos en la hiperesfera de radio 1 y centro en el origen de coordenadas.
vengoroso | 13 de July de 2011 | 10:58

Respecto a (7) Felix, muy cierto! Partiendo de tu simplificacion podemos hacer otra similar: quedarnos con el hiper-cubo de arista con longitud 1 y vertices opuestos en $(0,0,\dotsc, 0)$ y $(1,1,\dotsc, 1)$ , que hablando en plata significa que podemos ignorar la parte entera de las coordenadas y quedarnos solo con la parte decimal (vista como un numero positivo).
vengoroso | 13 de July de 2011 | 11:04

(9) Otra idea que he tenido, que no tiene en cuenta la simplificacion anterior: si podemos llegar desde el origen hasta $P$ y podemos llegar desde el origen hasta $Q$ , entonces tambien podemos llegar desde el origen hasta el punto $P+Q$ . Ademas es evidente que si podemos ir a $P$ , haciendo los mismos saltos con signo opuesto podemos llegar a $-P$ , por lo que el conjunto de puntos alcanzables desde 0 es un subgrupo aditivo de $\mathbb{Q}^n$ .

Como todos los “vectores basicos” son alcanzables en un unico paso, esto nos da una condicion suficiente para resolver el problema: Basta demostrar que si podemos llegar al punto $P$ , entonces tambien podemos llegar al punto $\lambda P$ donde $\latex \lambda$ es un racional positivo.
vengoroso | 13 de July de 2011 | 11:06

(10) Juntando (9) con (7), para resolver el problema basta con demostrar que desde el punto $(0,0,\dotsc, 0)$ podemos llegar al punto $(\frac{a}{b},0,\dotsc, 0)$ donde $\frac{a}{b}$ es un racional menor que 1.
Félix | 13 de July de 2011 | 13:42

(11): Respecto a (10) , si (a,c,b) forman una terna pitagórica, entonces se puede llegar con un solo paso dese el origen hasta (a/b,0,0,0,0) porque pasa por (a/2b,a/2b,a/2b,a/2b,c/b).Sobre las dimensiones, por inducción, solo hace falta probar que la propiedad buscada se cumple para n=5 y no para n=4.
vengoroso | 13 de July de 2011 | 18:00

(12) Una simplificacion mas: supongamos que $b = mn$ donde $m$ y $n$ son primos entre si, entonces por la identidad de Bezout existen $u,v$ tales que $1 = um + vn$ , por lo que $a = uma + vna$ y podemos escribir $\frac{a}{b} = \frac{uma + vna}{mn} = \frac{ua}{n} + \frac{va}{m}$ , como consecuencia, basta demostrar el resultado para puntos de la forma $(\frac{a}{q},0,\dotsc, 0)$ donde $q = p^e$ es una potencia de un primo.
Pirer | 13 de July de 2011 | 18:03

(12)

Sobre lo que se ha dicho en (10), basta ver que desde el origen (0,0,…,0) podemos llegar al punto (1/n, 0, …, 0) para todo n natural, y así, por simetrías y repeticiones siempre podremos alcanzar cualquier punto racional.
Pirer | 13 de July de 2011 | 18:04

(14)

El anterior mio, que pone (12), es el (13). Que rapidos soys!
vengoroso | 13 de July de 2011 | 18:22

(15) Partiendo de (13), creo que la clave (y de aqui debe venir la necesidad de tener dimension mayor o igual a 5) debe estar en el teorema de los cuatro cuadrados: todo natural $n$ puede escribirse como suma de 4 cuadrados $n = a^2 + b^2 + c^2 + d^2$
vengoroso | 13 de July de 2011 | 19:11

(16) Creo que tengo el paso final para dimension 5 o superior. Usando (13) y anteriores, basta obtener el punto $(\frac{1}{n}, 0, 0, 0, 0)$ (si la dimension es superior a 5 ponemos mas ceros al final en todos los pasos). Aplicando el teorema de los cuatro cuadrados al numero $(2n)^2 - 1$ obtenemos $(2n)^2 - 1 = a^2 + b^2 + c^2 + d^2$ , que re-escrito queda $1 = \frac{1}{(2n)^2} + \frac{a^2}{(2n)^2} + \frac{b^2}{(2n)^2} + \frac{c^2}{(2n)^2} + \frac{d^2}{(2n)^2}$ , por lo que la transformacion $(0,0,0,0,0) \longmapsto (\frac{1}{2n}, \frac{a}{2n}, \frac{b}{2n}, \frac{c}{2n}, \frac{d}{2n})$ es valida. Desde este punto aplicamos la misma transformacion cambiando los signos en todas las coordenadas menos en la primera, y tenemos $(\frac{1}{2n}, \frac{a}{2n}, \frac{b}{2n}, \frac{c}{2n}, \frac{d}{2n}) \longmapsto (\frac{1}{n}, 0, 0, 0, 0)$ , como queriamos demostrar.

Ahora solo falta ver que para dimension 2, 3 y 4 existen puntos que no se pueden alcanzar.
edward | 13 de July de 2011 | 23:15

(17) Y si lo ponemo todo en una sola demostracion?
Es un poco dificil seguir la pista.
Pirer | 14 de July de 2011 | 04:21

(18)

(16), creo que tienes toda la razón. Con esto sólo falta demostrar que existe algún punto racional de $R^4$ que no se puede alcanzar mediante sucesivas iteraciones… quizás con clases de equivalencia?

(17), cuando esté completa, lo resumimos. De momento está demostrado el caso n=5, 6, …, básicamente tienes que mirar (16), que es donde está la “chicha”.
vengoroso | 14 de July de 2011 | 11:15

(19)
La misma demostración de (16) es valida en dimensión 4 (resp 3, 2) para obtener el punto con primera cordenada $\frac{1}{n}$ siempre que $(2n)^2 - 1$ se pueda escribir como suma de 3 (resp 2, resp 1) cuadrados, por lo que un primer acercamiento para buscar un punto no alcanzable en dimensión 4 (que ya valdría como contraejemplo para dimensiones 3 y 2) es buscar un $n$ tal que $(2n)^2 - 1$ no se pueda escribir como suma de 3 cuadrados. Tenemos suerte y el valor más pequeño $n=2$ ya nos vale porque 15 no puede escribirse como suma de 3 cuadrados, así que me atrevería a conjeturar que el punto $(\frac{1}{2},0,0,0)$ no es alcanzable desde el origen.

Respecto a (18): si logramos demostrar que existen diferentes clases de equivalencia también habremos terminado, pero como podriamos usar esto de forma efectiva? Durante un rato estuve pensando en considerar las clases como órbitas de la acción del grupo de isometrías generado por traslaciones de longitud 1, pero no se me ocurrió ninguna manera de demostrar que la acción no es transitiva usando este enfoque…
Maelstrom | 15 de July de 2011 | 00:29

Bonito problema. Desafiando la intuición.
josejuan | 15 de July de 2011 | 08:57

Precioso problema, y muy divertida la forma en la que la habéis resuelto vengoroso, Pirer y Félix.
Félix | 15 de July de 2011 | 11:24

josejuan, todavía queda hallar un contraejemplo para n=4 o probar su existencia,
y yo, creo que no sabría como hacerlo.
fede | 17 de July de 2011 | 22:29

Para el caso n=2, la teoria de las ternas pitagóricas dice que los puntos racionales a distancia 1 de (0,0) son, en fracciones irreducibles, de la forma $( \dfrac{ a^2-b^2}{a^2+b^2}, \dfrac{2ab}{a^2+b^2})$ o $( \dfrac{2ab}{a^2+b^2}, \dfrac{ a^2-b^2}{a^2+b^2})$ con a y b primos entre sí y de distinta paridad.
Por tanto los denominadores de las coordenadas de los puntos racionales alcanzables desde (0,0) son siempre impares.

La solución completa al problema del post se puede ver en los apartados 2.1 y 2.2 de este artículo:
http://www.math.uwaterloo.ca/co/graduate-students/files/mmath/Lino-D.pdf
vengoroso | 18 de July de 2011 | 17:53

Gracias fede, parece entonces que el trozo que faltaba era tambien bastante elemental, debe ser que andamos un poco flojos con los calores veraniegos

Curioso que la demostracion del articulo para la conectividad con $n\geq 5$ es virtualmente identica a la que hemos encontrado aqui…
M | 21 de July de 2011 | 19:15

Precioso problema. Me encantan estos resultados que dependen de la dimensión!