El problema de las distintas distancias de Erdő

Problema en geometría discreta

En geometría discreta , el problema de las distancias distintas de Erdős plantea que cada conjunto de puntos en el plano tiene un número casi lineal de distancias distintas. Fue planteado por Paul Erdős en 1946 ^{[1] [2]} y casi demostrado por Larry Guth y Nets Katz en 2015. ^{[3] [4] [5]}

La conjetura

En lo que sigue, sea g ( n ) el número mínimo de distancias distintas entre n puntos en el plano, o equivalentemente la cardinalidad más pequeña posible de su conjunto de distancias . En su artículo de 1946, Erdős demostró las estimaciones

${\displaystyle {\sqrt {n-3/4}}-1/2\leq g(n)\leq cn/{\sqrt {\log n}}}$

para alguna constante . El límite inferior se dio mediante un argumento fácil. El límite superior se da mediante una cuadrícula cuadrada. Para dicha cuadrícula, hay números por debajo de n que son sumas de dos cuadrados, expresados ​​en notación O mayúscula ; véase Constante de Landau-Ramanujan . Erdős conjeturó que el límite superior estaba más cerca del valor verdadero de g ( n ), y específicamente que (usando la notación Omega mayúscula ) se cumple para cada c < 1 . ${\displaystyle c}$ ${\displaystyle {\sqrt {n}}\times {\sqrt {n}}}$ ${\displaystyle O(n/{\sqrt {\log n}})}$ ${\displaystyle g(n)=\Omega (n^{c})}$

Resultados parciales

El límite inferior de g ( n ) = Ω( n ^1/2 ) de Paul Erdős de 1946 se mejoró sucesivamente a:

• g ( n ) = Ω( n ^2/3 ) por Leo Moser en 1952, ^[6]
• g ( n ) = Ω( n ^5/7 ) por Fan Chung en 1984, ^[7]

• g ( n ) = Ω ( n ^4/5 /log n ) por Fan Chung, Endre Szemerédi y William T. Trotter en 1992, ^[8]
• gramo ( norte ) = Ω ( norte ^4/5 ) por László A. Székely en 1993, ^[9]
• g ( n ) = Ω( n ^6/7 ) por József Solymosi y Csaba D. Tóth en 2001, ^[10]
• g ( n ) = Ω( n ^{(4 e /(5 e − 1)) − ɛ} ) por Gábor Tardos en 2003, ^[11]
• g ( n ) = Ω( n ^{((48 − 14 e )/(55 − 16 e )) − ɛ} ) por Nets Katz y Gábor Tardos en 2004, ^[12]
• g ( n ) = Ω( n /log n ) por Larry Guth y Nets Katz en 2015. ^[3]

Dimensiones superiores

Erdős también consideró la variante de dimensión superior del problema: para sea el número mínimo posible de distancias distintas entre puntos en el espacio euclidiano de dimensión -. Demostró que y y conjeturó que el límite superior es de hecho preciso, es decir, . József Solymosi y Van H. Vu obtuvieron el límite inferior en 2008. ^[13] ${\displaystyle d\geq 3}$ ${\displaystyle g_{d}(n)}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle g_{d}(n)=\Omega (n^{1/d})}$ ${\displaystyle g_{d}(n)=O(n^{2/d})}$ ${\displaystyle g_{d}(n)=\Theta (n^{2/d})}$ ${\displaystyle g_{d}(n)=\Omega (n^{2/d-2/d(d+2)})}$

Véase también

• Conjetura del cetrero
• Problema de distancia unitaria de Erdős
• El problema de la distancia de Erdös

Referencias

1. Erdős, Paul (1946). "Sobre conjuntos de distancias de n puntos" (PDF) . American Mathematical Monthly . 53 (5): 248–250. doi :10.2307/2305092. JSTOR  2305092.
2. Garibaldi, Julia; Iosevich, Alex; Senger, Steven (2011), El problema de la distancia de Erdős , Student Mathematical Library, vol. 56, Providence, RI: American Mathematical Society, ISBN 978-0-8218-5281-1, Sr.  2721878
3. Guth, Larry ; Katz, Nets Hawk (2015). "Sobre el problema de distancias distintas de Erdős en el plano". Anales de Matemáticas . 181 (1): 155–190. arXiv : 1011.4105 . doi :10.4007/annals.2015.181.1.2. MR  3272924. Zbl  1310.52019.
4. El límite de Guth-Katz en el problema de la distancia de Erdős, una exposición detallada de la prueba, por Terence Tao
5. La solución de Guth y Katz al problema de las distancias distintas de Erdős, publicación invitada de János Pach en el blog de Gil Kalai
6. Moser, Leo (1952). "Sobre las diferentes distancias determinadas por puntos". American Mathematical Monthly . 59 (2): 85–91. doi :10.2307/2307105. JSTOR  2307105. MR  0046663. ${\displaystyle n}$
7. Chung, Fan (1984). "El número de distancias diferentes determinadas por n {\displaystyle n} puntos en el plano" (PDF) . Journal of Combinatorial Theory . Serie A. 36 (3): 342–354. doi : 10.1016/0097-3165(84)90041-4 . MR  0744082.
8. Chung, Fan ; Szemerédi, Endre ; Trotter, William T. (1992). "El número de distancias diferentes determinadas por un conjunto de puntos en el plano euclidiano" (PDF) . Geometría discreta y computacional . 7 : 342–354. doi : 10.1007/BF02187820 . MR  1134448. S2CID  10637819.
9. Székely, László A. (1993). "Números cruzados y problemas de Erdös difíciles en geometría discreta". Combinatoria, probabilidad y computación . 11 (3): 1–10. doi :10.1017/S0963548397002976. MR  1464571. S2CID  36602807.
10. Solymosi, József ; Tóth, Csaba D. (2001). "Distintas distancias en el plano". Geometría discreta y computacional . 25 (4): 629–634. doi : 10.1007/s00454-001-0009-z . SEÑOR  1838423.
11. Tardos, Gábor (2003). "Sobre sumas distintas y distancias distintas". Avances en Matemáticas . 180 (1): 275–289. doi : 10.1016/s0001-8708(03)00004-5 . MR  2019225.
12. Katz, Nets Hawk ; Tardos, Gábor (2004). "Una nueva desigualdad de entropía para el problema de la distancia de Erdős". En Pach, János (ed.). Hacia una teoría de grafos geométricos . Matemáticas contemporáneas. Vol. 342. Providence, RI: American Mathematical Society. págs. 119–126. doi :10.1090/conm/342/06136. ISBN 978-0-8218-3484-8.Señor 2065258  .
13. Solymosi, József ; Vu, Van H. (2008). "Límites casi óptimos para el problema de las distintas distancias de Erdő en grandes dimensiones". Combinatoria . 28 : 113-125. doi :10.1007/s00493-008-2099-1. SEÑOR  2399013. S2CID  2225458.

Enlaces externos

• La página de William Gasarch sobre el problema