Teorema de Erdös-Anning

Sobre conjuntos de puntos con distancias enteras

La recta numérica entera es un conjunto de infinitos puntos con distancias enteras. Según el teorema de Erdős-Anning, cualquier conjunto de este tipo se encuentra sobre una recta.

El teorema de Erdős-Anning establece que, siempre que un número infinito de puntos en el plano tengan distancias enteras , los puntos se encuentran en una línea recta . El mismo resultado se cumple en espacios euclidianos de dimensiones superiores . El teorema no se puede reforzar para dar un límite finito al número de puntos: existen conjuntos finitos arbitrariamente grandes de puntos que no están en una línea y tienen distancias enteras.

El teorema recibe su nombre de Paul Erdős y Norman H. Anning , quienes publicaron una prueba del mismo en 1945. ^[1] Erdős proporcionó posteriormente una prueba más sencilla, que también puede utilizarse para comprobar si un conjunto de puntos forma un grafo de Erdős-Diofantino , un sistema inextensible de puntos enteros con distancias enteras. El teorema de Erdős-Anning inspiró el problema de Erdős-Ulam sobre la existencia de conjuntos de puntos densos con distancias racionales.

Racionalidad versus integralidad

Los múltiplos enteros del ángulo de un triángulo rectángulo de 3–4–5 . Todas las distancias por pares entre los múltiplos pares (todos los demás puntos de este conjunto) son números racionales. Al escalar cualquier subconjunto finito de estos puntos por el mínimo común denominador de sus distancias, se obtiene un conjunto finito arbitrariamente grande de puntos a distancias enteras entre sí.

Aunque no puede haber un conjunto infinito no colineal de puntos con distancias enteras, hay conjuntos infinitos no colineales de puntos cuyas distancias son números racionales . ^[2] Por ejemplo, el subconjunto de puntos en un círculo unitario obtenido como los múltiplos pares de uno de los ángulos agudos de un triángulo rectángulo de lados enteros (como el triángulo con longitudes de lado 3, 4 y 5 ) tiene esta propiedad. Esta construcción forma un conjunto denso en el círculo. ^{[3] El} problema de Erdős-Ulam (aún sin resolver) pregunta si puede existir un conjunto de puntos a distancias racionales entre sí que forme un conjunto denso para todo el plano euclidiano. ^[4] Según Erdős, Stanisław Ulam se inspiró para hacer esta pregunta después de escuchar de Erdős sobre el teorema de Erdős-Anning. ^[5]

Para cualquier conjunto finito S de puntos a distancias racionales entre sí, es posible encontrar un conjunto similar de puntos a distancias enteras entre sí, expandiendo S por un factor del mínimo común denominador de las distancias en S . Al expandir de esta manera un subconjunto finito de la construcción del círculo unitario, se pueden construir conjuntos finitos arbitrariamente grandes de puntos no colineales con distancias enteras entre sí. ^[3] Sin embargo, incluir más puntos en S puede hacer que el factor de expansión aumente, por lo que esta construcción no permite que conjuntos infinitos de puntos a distancias racionales se transformen en conjuntos infinitos de puntos a distancias enteras. ^[1]

Prueba

Ilustración para una demostración del teorema de Erdős-Anning. Dados tres puntos no colineales A , B , C con distancias enteras entre sí (aquí, los vértices de un triángulo rectángulo 3-4-5), los puntos cuyas distancias a A y B difieren en un entero se encuentran en un sistema de hipérbolas e hipérbolas degeneradas (azul), y simétricamente los puntos cuyas distancias a B y C difieren en un entero se encuentran en otro sistema de hipérbolas (rojo). Cualquier punto con una distancia entera a los tres, A , B , C se encuentra en un cruce de una curva azul y una roja. Hay un número finito de cruces, por lo que hay un número finito de puntos adicionales en el conjunto. Cada rama de una hipérbola está etiquetada por la diferencia entera de distancias que es invariante para los puntos de esa rama.

Poco después de la publicación original del teorema de Erdős-Anning, Erdős proporcionó la siguiente prueba más simple. ^{[6] [7]}

La prueba supone un conjunto dado de puntos con distancias enteras, no todos en una línea. Luego demuestra que este conjunto debe ser finito, utilizando un sistema de curvas para el cual cada punto del conjunto dado se encuentra en un cruce de dos de las curvas. En más detalle, consta de los siguientes pasos:

• Elija arbitrariamente un triángulo formado por tres de los puntos dados. La figura muestra un ejemplo en el que estos tres puntos elegidos forman un triángulo rectángulo (amarillo) con longitudes de aristas de 3, 4 y 5. ${\displaystyle ABC}$
• Sea la función de distancia euclidiana . Para cualquier punto dado , el entero es como máximo , por la desigualdad triangular . Por lo tanto, se encuentra en una de las hipérbolas , definidas por ecuaciones de la forma con . Estas se muestran en azul en la figura. Para esta ecuación, en cambio, se definen dos rayos que se extienden en direcciones opuestas en la línea que pasa por y (también se muestra en azul); este par de rayos puede tratarse como una hipérbola degenerada para los fines de la prueba. ${\displaystyle d}$ ${\displaystyle X}$ ${\displaystyle |d(A,X)-d(B,X)|}$ ${\displaystyle d(A,B)}$ ${\displaystyle X}$ ${\displaystyle d(A,B)}$ $${\displaystyle |d(A,X)-d(B,X)|=i}$$ ${\displaystyle 0\leq i<d(A,B)}$ ${\displaystyle i=d(A,B)}$ ${\displaystyle A}$ ${\displaystyle B}$
• Por un argumento simétrico, también debe estar en una de las hipérbolas o hipérbolas degeneradas definidas por ecuaciones de la forma con . Estas se muestran en rojo en la figura. ${\displaystyle X}$ ${\displaystyle d(B,C)+1}$ $${\displaystyle |d(B,X)-d(C,X)|=j}$$ ${\displaystyle 0\leq j\leq d(B,C)}$
• Las hipérbolas azul y roja que contienen no pueden coincidir, porque tienen diferentes pares de focos . Por lo tanto, debe haber un punto en el que se intersecan. Cada par de hipérbolas azul y roja tiene como máximo cuatro puntos de intersección, según el teorema de Bézout . ${\displaystyle X}$ ${\displaystyle X}$
• Como cada punto dado debe ser uno de estos puntos de intersección, el número de puntos dados es, como máximo, el producto del número de pares de hipérbolas y el número de intersecciones por par. Este es, como máximo , un número finito. ^[6] $${\displaystyle 4{\bigl (}d(A,B)+1{\bigr )}{\bigl (}d(B,C)+1{\bigr )}}$$

La misma prueba muestra que, cuando el diámetro de un conjunto de puntos con distancias enteras es , hay como máximo puntos. ^[6] La dependencia cuadrática de esta cota de se puede mejorar, utilizando una prueba similar pero con una elección más cuidadosa de los pares de puntos utilizados para definir familias de hipérbolas: cada conjunto de puntos con distancias enteras y diámetro tiene tamaño , donde utiliza la notación O mayúscula . Sin embargo, no es posible reemplazar por la distancia mínima entre los puntos: existen conjuntos de puntos no colineales arbitrariamente grandes con distancias enteras y con distancia mínima dos. ^[7] ${\displaystyle \delta }$ ${\displaystyle 4(\delta +1)^{2}}$ ${\displaystyle \delta }$ ${\displaystyle \delta }$ ${\displaystyle O(\delta )}$ ${\displaystyle O(\,)}$ ${\displaystyle \delta }$

Conjuntos de puntos máximos con distancias integrales

Gráfico Erdős-Diophantine de cinco vértices ^[8]

Una forma alternativa de enunciar el teorema es que un conjunto no colineal de puntos en el plano con distancias enteras solo puede extenderse agregando un número finito de puntos adicionales, antes de que no se puedan agregar más puntos. Un conjunto de puntos con coordenadas y distancias enteras, a los que no se pueden agregar más mientras se preservan ambas propiedades, forma un grafo de Erdős–Diofantino . ^[8]

La prueba del teorema de Erdős-Anning se puede utilizar en un algoritmo para comprobar si un conjunto dado de puntos enteros con distancias enteras forma un gráfico de Erdős-Diofantino: simplemente hay que encontrar todos los puntos de cruce de las hipérbolas utilizadas en la prueba y comprobar si alguno de los puntos resultantes también tiene coordenadas enteras y distancias enteras respecto del conjunto dado. ^[8]

Dimensiones superiores

Como escribieron Anning y Erdős en su artículo original sobre este teorema, "mediante un argumento similar podemos demostrar que no podemos tener infinitos puntos en el espacio dimensional que no estén todos en una línea, siendo todas las distancias integrales". ^[1] ${\displaystyle n}$

Referencias

1. Anning, Norman H. ; Erdős, Paul (1945), "Distancias integrales", Boletín de la Sociedad Matemática Americana , 51 (8): 598–600, doi : 10.1090/S0002-9904-1945-08407-9
2. Euler, Leonhard (1862), "Fragmenta arithmetica ex Adversariis mathematicis deprompta, C: Analysis Diophantea", Opera postuma (en latín), vol. Yo, Petrópolis: Eggers, págs. 204-263; véase el teorema 65, pág. 229
3. Harborth, Heiko (1998), "Distancias integrales en conjuntos de puntos", Carlomagno y su herencia: 1200 años de civilización y ciencia en Europa, vol. 2 (Aquisgrán, 1995) , Turnhout, Bélgica: Brepols, págs. 213-224. Nótese que Harborth expresa incorrectamente el resultado en múltiplos del ángulo de un triángulo rectángulo entero: deberían ser los múltiplos pares de este ángulo, pero Harborth lo expresa como todos los múltiplos enteros.
4. Klee, Victor ; Wagon, Stan (1991), "Problema 10 ¿Contiene el plano un conjunto racional denso?", Problemas antiguos y nuevos sin resolver en geometría plana y teoría de números, Exposiciones matemáticas de Dolciani, vol. 11, Cambridge University Press, págs. 132-135, ISBN 978-0-88385-315-3
5. Erdős, Paul (1985), "Ulam, el hombre y el matemático" (PDF) , Journal of Graph Theory , 9 (4): 445–449, doi :10.1002/jgt.3190090402, MR  0890232
6. Erdős, Paul (1945), "Distancias integrales", Boletín de la Sociedad Matemática Americana , 51 (12): 996, doi : 10.1090/S0002-9904-1945-08490-0 , MR  0013512
7. Solymosi, József (2003), "Nota sobre distancias integrales", Geometría computacional y discreta , 30 (2): 337–342, doi : 10.1007/s00454-003-0014-7 , SEÑOR  2007970
8. Kohnert, Axel; Kurz, Sascha (2007), "Una nota sobre los gráficos Erdős-Diophantine y las alfombras diophantine", Mathematica Balkanica , New Series, 21 (1–2): 1–5, arXiv : math/0511705 , MR  2350714