Теорема Эрдеша–Эннинга

О множествах точек с целочисленными расстояниями

Прямая целых чисел , множество из бесконечного числа точек с целочисленными расстояниями. Согласно теореме Эрдёша–Эннинга, любое такое множество лежит на прямой.

Теорема Эрдёша–Эннинга утверждает, что всякий раз, когда бесконечное число точек на плоскости имеет целочисленные расстояния, эти точки лежат на одной прямой . Тот же результат справедлив и в евклидовых пространствах более высокой размерности . Теорему нельзя усилить, чтобы дать конечную границу для числа точек: существуют произвольно большие конечные множества точек, которые не лежат на одной прямой и имеют целочисленные расстояния.

Теорема названа в честь Пола Эрдёша и Нормана Х. Эннинга , которые опубликовали её доказательство в 1945 году. ^[1] Эрдёш позже предоставил более простое доказательство, которое также можно использовать для проверки того, образует ли множество точек граф Эрдёша–Диофантов , нерасширяемую систему целых точек с целыми расстояниями. Теорема Эрдёша–Эннинга вдохновила на проблему Эрдёша–Улама о существовании плотных множеств точек с рациональными расстояниями.

Рациональность против целостности

Целые кратные угла прямоугольного треугольника 3–4–5 . Все попарные расстояния между четными кратными (каждая вторая точка из этого множества) являются рациональными числами. Масштабирование любого конечного подмножества этих точек по наименьшему общему знаменателю их расстояний дает произвольно большой конечный набор точек на целых расстояниях друг от друга.

Хотя не может быть бесконечного неколлинеарного множества точек с целочисленными расстояниями, существуют бесконечные неколлинеарные множества точек, расстояния которых являются рациональными числами . ^[2] Например, подмножество точек на единичной окружности, полученное как четные кратные одного из острых углов прямоугольного треугольника с целыми сторонами ( такого как треугольник с длинами сторон 3, 4 и 5 ), обладает этим свойством. Эта конструкция образует плотное множество в окружности. ^[3] (Все еще нерешенная) проблема Эрдёша–Улама спрашивает, может ли существовать множество точек на рациональных расстояниях друг от друга, которое образует плотное множество для всей евклидовой плоскости. ^[4] По словам Эрдёша, Станислав Улам был вдохновлен задать этот вопрос, услышав от Эрдёша о теореме Эрдёша–Аннинга. ^[5]

Для любого конечного множества S точек, находящихся на рациональных расстояниях друг от друга, можно найти аналогичное множество точек, находящихся на целых расстояниях друг от друга, расширив S на коэффициент наименьшего общего знаменателя расстояний в S. Расширяя таким образом конечное подмножество конструкции единичной окружности, можно построить произвольно большие конечные множества неколлинеарных точек с целыми расстояниями друг от друга. ^[3] Однако включение большего количества точек в S может привести к увеличению коэффициента расширения, поэтому эта конструкция не позволяет преобразовать бесконечные множества точек на рациональных расстояниях в бесконечные множества точек на целочисленных расстояниях. ^[1]

Доказательство

Иллюстрация к доказательству теоремы Эрдёша–Эннинга. Даны три неколлинеарные точки A , B , C с целочисленными расстояниями друг от друга (в данном случае вершины прямоугольного треугольника 3–4–5), точки, расстояния которых до A и B отличаются на целое число, лежат на системе гипербол и вырожденных гипербол (синие), и симметрично точки, расстояния которых до B и C отличаются на целое число, лежат на другой системе гипербол (красные). Любая точка с целочисленным расстоянием до всех трех точек A , B , C лежит на пересечении синей и красной кривых. Существует конечное число пересечений, поэтому конечное число дополнительных точек в наборе. Каждая ветвь гиперболы помечена целочисленной разностью расстояний, которая инвариантна для точек на этой ветви.

Вскоре после первоначальной публикации теоремы Эрдёша–Эннинга Эрдёш предоставил следующее более простое доказательство. ^{[6] [7]}

Доказательство предполагает заданный набор точек с целочисленными расстояниями, не все на одной линии. Затем оно доказывает, что этот набор должен быть конечным, используя систему кривых, для которой каждая точка заданного набора лежит на пересечении двух кривых. Более подробно, оно состоит из следующих шагов:

• Произвольно выберем треугольник, образованный тремя из данных точек. На рисунке показан пример, для которого эти три выбранные точки образуют прямоугольный треугольник (желтый) с длинами сторон 3, 4 и 5. ${\displaystyle ABC}$
• Пусть обозначает функцию евклидова расстояния . Для любой заданной точки целое число не превышает , по неравенству треугольника . Таким образом, лежит на одной из гипербол , определяемых уравнениями вида с . Они показаны синим цветом на рисунке. Для это уравнение вместо этого определяет два луча, идущих в противоположных направлениях на прямой, проходящей через и (также показаны синим цветом); эту пару лучей можно рассматривать как вырожденную гиперболу для целей доказательства. ${\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}$
• По симметричному аргументу, также должна лежать на одной из гипербол или вырожденных гипербол, определяемых уравнениями вида с . Они показаны красным на рисунке. ${\displaystyle X}$ ${\displaystyle d(B,C)+1}$ $${\displaystyle |d(B,X)-d(C,X)|=j}$$ ${\displaystyle 0\leq j\leq d(B,C)}$
• Синяя и красная гиперболы, содержащие , не могут совпадать, поскольку у них разные пары фокусов . Таким образом, должна быть точка, в которой они пересекаются. Каждая пара синей и красной гиперболы имеет не более четырех точек пересечения, по теореме Безу . ${\displaystyle X}$ ${\displaystyle X}$
• Поскольку каждая заданная точка должна быть одной из этих точек пересечения, число заданных точек не более произведения числа пар гипербол и числа пересечений на пару. Это не более чем число точек, конечное число. ^[6] $${\displaystyle 4{\bigl (}d(A,B)+1{\bigr )}{\bigl (}d(B,C)+1{\bigr )}}$$

Это же доказательство показывает, что когда диаметр набора точек с целочисленными расстояниями равен , то существует не более точек. ^[6] Квадратичную зависимость этой границы от можно улучшить, используя похожее доказательство, но с более тщательным выбором пар точек, используемых для определения семейств гипербол: каждый набор точек с целочисленными расстояниями и диаметром имеет размер , где используется большая нотация O . Однако невозможно заменить на минимальное расстояние между точками: существуют произвольно большие неколлинеарные наборы точек с целочисленными расстояниями и с минимальным расстоянием два. ^[7] ${\displaystyle \delta }$ ${\displaystyle 4(\delta +1)^{2}}$ ${\displaystyle \delta }$ ${\displaystyle \delta }$ ${\displaystyle O(\delta )}$ ${\displaystyle O(\,)}$ ${\displaystyle \delta }$

Максимальные множества точек с целыми расстояниями

Пятивершинный граф Эрдеша – Диофанта ^[8]

Альтернативный способ сформулировать теорему заключается в том, что неколлинеарный набор точек на плоскости с целочисленными расстояниями может быть расширен только путем добавления конечного числа дополнительных точек, прежде чем больше точек нельзя будет добавить. Набор точек с целочисленными координатами и целочисленными расстояниями, к которому больше ничего нельзя добавить, сохраняя оба свойства, образует граф Эрдёша–Диофантова . ^[8]

Доказательство теоремы Эрдёша–Эннинга можно использовать в алгоритме для проверки того, образует ли заданный набор целых точек с целыми расстояниями граф Эрдёша–Диофантов: просто найдите все точки пересечения гипербол, используемых в доказательстве, и проверьте, имеет ли какая-либо из полученных точек также целые координаты и целые расстояния от заданного набора. ^[8]

Более высокие измерения

Как писали Эннинг и Эрдёш в своей оригинальной статье по этой теореме, «похожим рассуждением мы можем показать, что не может быть бесконечного числа точек в -мерном пространстве, не все из которых лежат на одной прямой, при этом все расстояния должны быть целыми числами» ^{[1] .} ${\displaystyle n}$

Ссылки

1. Эннинг, Норман Х.; Эрдёш , Пол (1945), «Интегральные расстояния», Бюллетень Американского математического общества , 51 (8): 598–600, doi : 10.1090/S0002-9904-1945-08407-9
2. Эйлер, Леонхард (1862), «Fragmenta arithmetica ex Adversariis mathematicis deprompta, C: Analysis Diophantea», Opera postuma (на латыни), том. Я, Петрополис: Эггерс, стр. 204–263.; см. Теорему 65, стр. 229
3. Harborth, Heiko (1998), «Интегральные расстояния в точечных множествах», Карл Великий и его наследие: 1200 лет цивилизации и науки в Европе, т. 2 (Аахен, 1995) , Тюрнхаут, Бельгия: Brepols, стр. 213–224Обратите внимание, что Харборт неверно указывает результат для кратных угла целочисленного прямоугольного треугольника: это должны быть четные кратные этого угла, но Харборт указывает, что это все целые кратные.
4. Клее, Виктор ; Вагон, Стэн (1991), «Проблема 10. Содержит ли плоскость плотное рациональное множество?», Старые и новые нерешенные проблемы в плоской геометрии и теории чисел, математические изложения Dolciani, т. 11, Cambridge University Press, стр. 132–135, ISBN 978-0-88385-315-3
5. Эрдёш, Пол (1985), «Улам, человек и математик» (PDF) , Журнал теории графов , 9 (4): 445–449, doi :10.1002/jgt.3190090402, MR  0890232
6. Эрдёш, Пол (1945), "Интегральные расстояния", Бюллетень Американского математического общества , 51 (12): 996, doi : 10.1090/S0002-9904-1945-08490-0 , MR  0013512
7. Solymosi, Йожеф (2003), «Примечание об целочисленных расстояниях», Discrete & Computational Geometry , 30 (2): 337–342, doi : 10.1007/s00454-003-0014-7 , MR  2007970
8. Конерт, Аксель; Курц, Саша (2007), «Заметки о графах Эрдеша – Диофанта и диофантовых коврах», Mathematica Balkanica , New Series, 21 (1–2): 1–5, arXiv : math/0511705 , MR  2350714