Teorema de Erdős-Anning

Archiu:Number-line-4.svg

La recta numèrica sancera és un conjunt d'infinits punts en distàncies sanceres. Segons la teorema de Erdős-Anning, qualsevol conjunt d'este tipo es troba en una recta.

La teorema de Erdős-Anning afirma que, sempre que un número infinit de punts del pla tinguen tots distàncies sanceres, els punts es troben en una llínea recta. El mateix resultat és vàlit en espais euclidianos de dimensions superiors. La teorema no pot reforçar-se per a obtindre un llímit finito del número de punts: existixen conjunts finitos arbitrariamente grans de punts que no estan en una recta i tenen distàncies sanceres.

La teorema deu el seu nom a Paul Erdős i Norman H. Anning, que varen publicar una demostració del mateix en 1945. Erdős va proporcionar posteriorment una demostració més senzilla, que també pot utilisar-se per a comprovar si un conjunt de punts forma un grafo de Erdős-Diophantine, un sistema inextensible de punts sancers en distàncies sanceres. La teorema de Erdős-Anning va inspirar el problema de Erdős-Ulam sobre l'existència de conjunts de punts densos en distàncies racionals.

Racionalitat versus integralidad

Archiu:Pythagorean dense rational distance set.svg

Els múltiples sancers de l'àngul d'un triàngul rectàngul 3-4-5. Totes les distàncies entre parells dels múltiples pares (qualsevol atre punt d'este conjunt) són número racional. Escalant qualsevol subconjunt finito d'estos punts pel mínim comú denominador de les seues distàncies s'obté un conjunt finito arbitrariamente gran de punts a distàncies sanceres entre sí.

Encara que no pot existir un conjunt infinit no colineal de punts en distàncies sanceres, existixen infinits conjunts no colineales de punts les distàncies dels quals són número racional. Per eixemple, el subconjunt de punts d'un círcul unitari obtingut com els múltiples pares d'un dels ànguls aguts d'un triàngul rectàngul de costats sancers (com el triàngul de costats 3, 4 i 5) té esta propietat. Esta construcció forma un conjunt dens en el círcul. El problema (encara no resolt) de Erdős-Ulam planteja si pot existir un conjunt de punts a distàncies racionals entre sí que forme un conjunt dens per a tot el pla euclídeo. Segons Erdős, Stanisław Ulam es va inspirar per a plantejar esta qüestió despuix de sentir parlar a Erdős de la teorema de Erdős-Anning.

Per a qualsevol conjunt finito S de punts a distàncies racionals entre sí, és possible trobar un conjunt similar de punts a distàncies sanceres entre sí, expandint S per un factor del mínim comú denominador de les distàncies en S. Expandint d'esta manera un subconjunt finito de la construcció del círcul unitari, es poden construir conjunts finitos arbitrariamente grans de punts no colineales en distàncies sanceres entre sí. No obstant, incloure més punts en S pot fer que el factor d'expansió aumente, per lo que esta construcció no permet transformar conjunts infinits de punts a distàncies racionals en conjunts infinits de punts a distàncies sanceres.

Evidència

Poc despuix de la publicació original de la teorema de Erdős-Anning, Erdős va proporcionar la següent demostració més senzilla.

La prova partix d'un conjunt donat de punts en distàncies sanceres, no tots sobre una recta. A continuació, es demostra que este conjunt deu ser finito, utilisant un sistema de curves per al que cada punt del conjunt dau es troba en un creuament de dos de les curves. Més detalladament, consta dels següents passos:

• Archiu:Erdős–Anning proof.svg

  Ilustració d'una demostració de la teorema de Erdős-Anning. Daus tres punts no colineales A, B, C en distàncies sanceres entre sí (ací, els vèrtiços d'un triàngul rectàngul 3-4-5), els punts les distàncies dels quals a A i B diferixen en un número entero es troben en un sistema d'hipérboles i hipérboles degeneradas (blava), i simétricamente els punts les distàncies dels quals a B i C diferixen en un número entero es troben en un atre sistema d'hipérboles (roig). Qualsevol punt en una distància sancera a les tres curves A, B, C es troba en el creuament d'una curva blava i una roja. Hi ha un número finito de creus, per lo que hi ha un número finito de punts adicionals en el conjunt. Cada branca d'una hipérbola està etiquetada per la diferència sancera de distàncies que és invariante per als punts d'eixa branca.

  Elegir arbitrariamente un triàngul $ABC$ format per tres dels punts donats. La figura mostra un eixemple en el que estos tres punts elegits formen un triàngul rectàngul (groc) en arestes de llongitut 3, 4 i 5.
• Deixem que $d$ denota la funció de distància euclidiana. Per a qualsevol punt $X$, l'número entero $|d(A,X)-d(B,X)|$és com a màxim $d(A,B)$ per la desigualtat del triàngul. Per lo tant, $X$ es troba en un de $d(A,B)$ hipérboles, definides per equacions de la forma:

$|d(A,X)-d(B,X)|=i$

En $0\le i<d(A,B)$. En la figura es mostren en blava. En $i=d(A,B)$ esta equació definix dos rajos que s'estenen en direccions opostes sobre la llínea que passa per $A$ i $B$ (també en blava); este parell de rajos pot tractar-se com una hipérbola degenerada a efectes de la demostració.

• Per un argument simètric, $X$ també deu estar en un dels $d(B,C)+1$ hipérboles o hipérboles degeneradas definides per equacions de la forma:

$|d(B,X)-d(C,X)|=j$

En $0\le j\le d(B,C)$. En la figura es mostren en roig.

• Les hipérboles blava i roja que contenen $X$ no poden coincidir, perque tenen parells de focs diferents. Per lo tant, $X$ deu haver un punt en el que es intersecan. Cada parell d'hipérbola blava i roja té com a màxim quatre punts d'intersecció, pel teorema de Bézout.
• Ya que cada punt donat deu ser un d'estos punts d'intersecció, el número de punts donats és com a màxim el producte del número de parells d'hipérboles i el número d'interseccions per parell. Açò és, com a màxim:

$4(d(A,B)+1)(d(B,C)+1)$punts, un número finito.

La mateixa demostració mostra que, quan el diàmetro d'un conjunt de punts en distàncies sanceres és $\delta$ hi ha com a màxim $4(\delta +1{)}^2$ punts. La dependència quadràtica d'este llímit en $\delta$ pot millorar-se significativament: si un conjunt en distàncies sanceres i diàmetro $\delta$ és colineal, òbviament té com a màxim $\delta +1$ punts, i si no és colineal, té tamany ${\delta }^{O(1/\log \log \delta )}$, a on el $O()$ utilisa la notació big O. No obstant, no és possible substituir $\delta$ per la distància mínima entre els punts: existixen conjunts de punts no colineales arbitrariamente grans en distàncies sanceres i en distància mínima dos.