Просмотр кода страницы Гипотеза Эрдёша о числе различных расстояний

'''Гипотеза Эрдёша о числе различных расстояний''' — утверждение [[Комбинаторная геометрия|комбинаторной геометрии]], согласно которому между <math>n</math> различными точками на плоскости имеется не меньше, чем <math>n^{1 - o(1)}</math> различных расстояний. Гипотеза сформулирована [[Эрдёш, Пал|Палом Эрдёшем]] в [[1946 год в науке|1946 году]], в [[2010 год в науке|2010 году]] [[Гут, Ларри|Ларри Гут]] и {{нп2|Кац, Нетс|Нетс Катц|en|Nets Katz|Nets Hawk Katz}} объявили о возможном решении этой проблемы<ref>{{cite arxiv|first1=l.|last1=Guth|first2=N. H.|last2=Katz|eprint=1011.4105 |title=On the Erdős distinct distance problem on the plane|year=2010}}. См. также [http://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/ Граница Гута-Каца для проблемы Эрдёша о расстояниях] {{Wayback|url=http://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/ |date=20130425112952 }} и [http://gilkalai.wordpress.com/2010/11/20/janos-pach-guth-and-katzs-solution-of-erdos-distinct-distances-problem/ Решение Гута-Каца проблемы Эрдёша о различных расстояниях] {{Wayback|url=http://gilkalai.wordpress.com/2010/11/20/janos-pach-guth-and-katzs-solution-of-erdos-distinct-distances-problem/ |date=20130509231657 }}.</ref>, окончательное доказательство Гута и Каца было завершено в [[2015 год в науке|2015 году]].

== Гипотеза ==
Пусть <math>g(n)</math> минимальное число различных расстояний между <math>n</math> точками на плоскости. В 1946 году Эрдёш доказал оценки
<math>\sqrt{n-3/4}-1/2\leqslant g(n)\leqslant c n/\sqrt{\log n}</math> для некоторой константы <math>c</math>. Нижняя оценка получена простым доказательством, верхняя оценка получена на базе квадратной решётки <math>\sqrt{n}\times\sqrt{n}</math> и того, что число целых меньше <math>n</math> равных сумме двух квадратов равно <math>O( n/\sqrt{\log n})</math> согласно [[Константа Ландау — Рамануджана|результату Ландау — Рамануджана]]. Эрдёш предположил, что верхняя граница ближе к истинной величине <math>g(n)</math> и <math>g(n) = \Omega(n^c)</math> верно для любого <math>c < 1</math>.

== Результаты ==
Нижняя граница Эрдёша {{math|1=''g''(''n'') = [[«O» большое и «o» малое|&Omega;]](''n''<sup>1/2</sup>)}} последовательно улучшалась:
* {{math|1=''g''(''n'') = &Omega;(''n''<sup>2/3</sup>)}} — {{нп2|Мозер, Лео|Лео Мозер|en|Leo Moser}}, 1952;
* {{math|1=''g''(''n'') = &Omega;(''n''<sup>5/7</sup>)}} — {{нп2|Чун, Фан|Фан Чун|en|Fan Chung}}, 1984;
* {{math|1=''g''(''n'') = &Omega;(''n''<sup>4/5</sup>/log ''n'')}} — Фан Чун, [[Эндре Семереди]], Уильям Троттер, 1992;
* {{math|1=''g''(''n'') = &Omega;(''n''<sup>4/5</sup>)}} — [[Секей, Ласло|Ласло Секей]], 1993;
* {{math|1=''g''(''n'') = &Omega;(''n''<sup>6/7</sup>)}} — [[Шоймоши, Йожеф|Йожеф Шоймоши]], Чаба Тот, 2001;
* {{math|1=''g''(''n'') = &Omega;(''n''<sup>(4''e''/(5''e'' &minus; 1)) &minus; ''e''</sup>)}} — {{нп2|Тардош, Габор|Габор Тардош|en|Gábor Tardos}}, 2003;
* {{math|1=''g''(''n'') = &Omega;(''n''<sup>((48 &minus; 14''e'')/(55 &minus; 16''e'')) &minus; ''e''</sup>)}} — Нетс Кац, Габор Тардош, 2004;
* {{math|1=''g''(''n'') = &Omega;(''n''/log ''n'')}} — Ларри Гут, Нетс Кац, 2015.

== Другие размерности ==
Эрдёш рассмотрел также проблему для более высоких размерностей пространства. Пусть <math>g_d(n)</math> минимальное число различных расстояний для <math>n</math> точек в евклидовом пространстве размерности <math>d</math>. Он доказал, что {{math|1=''g''<sub>''d''</sub>(''n'') = &Omega;(''n''<sup>1/''d''</sup>)}} и {{math|1=''g''<sub>''d''</sub>(''n'') = O(''n''<sup>2/''d''</sup>)}} и предположил, что верхняя граница является близкой, то есть {{math|1=''g''<sub>''d''</sub>(''n'') = &Theta;(''n''<sup>2/''d''</sup>)}}. В [[2008 год в науке|2008 году]] Шоймоши и {{нп2|Ву, Ван|Ван Ву|en|Van H. Vu|Van Vu)}} получили нижнюю оценку {{math|1=''g''<sub>''d''</sub>(''n'') = O(''n''<sup>2/''d''(1-1/(''d''+2))</sup>)}}.

== См. также ==
* {{нп2|Гипотеза Фальконера||en|Falconer's conjecture}}
* [[Граф единичных расстояний]]

== Примечания ==
{{примечания}}

== Литература ==
* {{citation|first=F.|last=Chung|title=The number of different distances determined by {{math|''n''}} points in the  plane|journal=[[Journal of Combinatorial Theory]], (A)|volume=36|year=1984|pages=342–354|url=http://www.math.ucsd.edu/~fan/mypaps/fanpap/67distances.pdf|doi=10.1016/0097-3165(84)90041-4}} {{Wayback|url=http://www.math.ucsd.edu/~fan/mypaps/fanpap/67distances.pdf |date=20120303013357 }}.
* {{citation|first1=F.|last1=Chung|authorlink1=Fan Chung|first2=E.|last2=Szemerédi|authorlink2=Семереди, Эндре|first3=W. T.|last3=Trotter|title=The number of different distances determined by a set of points in  the Euclidean plane|journal=[[Discrete and Computational Geometry]]|volume=7|year=1984|pages=342–354|url=http://www.math.ucsd.edu/~fan/wp/124distances.pdf|doi=10.1007/BF02187820}} {{Wayback|url=http://www.math.ucsd.edu/~fan/wp/124distances.pdf |date=20120303013401 }}
* {{citation|first=P.|last=Erdős|url=http://www.renyi.hu/~p_erdos/1946-03.pdf|title=On sets of distances of {{math|''n''}} points|journal=[[American Mathematical Monthly]]|volume=53|year=1946|pages=248–250}} {{Wayback|url=http://www.renyi.hu/~p_erdos/1946-03.pdf |date=20120305164600 }}
* {{citation|first1=J.|last1=Garibaldi|first2=A.|last2=Iosevich|first3=S.|last3=Senger|title=The Erdős Distance Problem|year=2011|publisher=American Mathematical Society |place=Providence, RI  }}
* {{cite arxiv|first1=L.|last1=Guth|first2=N. H.|last2=Katz|eprint=1011.4105 |title=On the Erdős distinct distance problem on the plane|year=2010}}
* {{citation|first=L.|last=Moser|title=On the different distances determined by {{math|''n''}} points|journal=[[American Mathematical Monthly]]|volume=59|year=1952|pages=85–91}}.
* {{citation|first1=J.|last1=Solymosi|first2=Cs. D.|last2=Tóth|title=Distinct Distances in the Plane |journal=[[Discrete and Computational Geometry]]|volume=25|year=2001|pages=629–634}}.
* {{citation|first1=J.|last1=Solymosi|first2=Van H.|last2=Vu|title= Near optimal bounds for the Erdős distinct distances problem in high dimensions
|journal=[[Combinatorica]]|volume=28|year=2008|pages=113–125}}.
* {{citation|first=L.|last=Székely|title=Crossing numbers and hard Erdös problems in discrete geometry|journal=Combinatorics, Probability and Computing|volume=11|year=1993|pages=1–10}}.
* {{citation|first=G.|last=Tardos|authorlink=Gábor Tardos|title=On distinct sums and distinct distances |journal=Advances in Mathematics|volume=180|year=2003|pages=275–289}}.

== Ссылки ==
* William Gasarch. [https://web.archive.org/web/20110611055716/http://www.cs.umd.edu/~gasarch/erdos_dist/erdos_dist.html A Webpage on The Erdos Distance Problem]
* [http://gilkalai.wordpress.com/2010/11/20/janos-pach-guth-and-katzs-solution-of-erdos-distinct-distances-problem/ János Pach: Guth and Katz’s Solution of Erdős’s Distinct Distances Problem] {{Wayback|url=http://gilkalai.wordpress.com/2010/11/20/janos-pach-guth-and-katzs-solution-of-erdos-distinct-distances-problem/ |date=20130509231657 }} (в блоге {{iw|Калай, Гиль|Гиля Калая|en|Gil Kalai}})
* [http://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/ Подробное доказательство Гута — Каца] {{Wayback|url=http://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/ |date=20130425112952 }} в блоге [[Тао, Теренс|Теренса Тао]]

[[Категория:Комбинаторная геометрия]]
[[Категория:Доказанные математические гипотезы]]