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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Высшие измерения

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

Ссылки

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

[ae-1] Jump up to: ^а ^б ^с Эннинг, Норман Х .; Эрдеш, Пол (1945), «Интегральные расстояния» , Бюллетень Американского математического общества , 51 (8): 598–600, doi : 10.1090/S0002-9904-1945-08407-9

[euler-2] Эйлер, Леонхард (1862), «Арифметические фрагменты от математических противников, C: Диофантовый анализ» , Посмертные произведения (на латыни), том. Я, Петрополис: Эггерс, стр. 204–263 ; см. теорему 65, с. 229

[h-3] Jump up to: ^а ^б Харборт, Хейко (1998), «Целочисленные расстояния в множествах точек», Карл Великий и его наследие: 1200 лет цивилизации и науки в Европе, Vol. 2 (Аахен, 1995) , Тюрнхаут, Бельгия: Бреполс, стр. 213–224 . Обратите внимание, что Харборт неправильно формулирует результат для угла, кратного целочисленному прямоугольному треугольнику: он должен быть четным, кратным этому углу, но Харборт утверждает, что это все кратные целым числам.

[kw-4] Клее, Виктор ; Вагон, Стэн (1991), «Проблема 10. Содержит ли плоскость плотное рациональное множество?», Старые и новые нерешенные проблемы плоской геометрии и теории чисел , Математические пояснения Дольчиани, том. 11, Издательство Кембриджского университета, стр. 132–135, ISBN. 978-0-88385-315-3

[eu-5] Эрдеш, Пол (1985), «Улам, человек и математик» (PDF) , Журнал теории графов , 9 (4): 445–449, doi : 10.1002/jgt.3190090402 , MR 0890232

[e-6] Jump up to: ^а ^б ^с Эрдеш, Пол (1945), «Интегральные расстояния», Бюллетень Американского математического общества , 51 (12): 996, doi : 10.1090/S0002-9904-1945-08490-0 , MR 0013512

[s-7] Jump up to: ^а ^б Солимоси, Йожеф (2003), «Примечание об целочисленных расстояниях», Дискретная и вычислительная геометрия , 30 (2): 337–342, doi : 10.1007/s00454-003-0014-7 , MR 2007970

[kk-8] Jump up to: ^а ^б ^с Конерт, Аксель; Курц, Саша (2007), «Заметки о графах Эрдеша – Диофанта и диофантовых коврах», Mathematica Balkanica , New Series, 21 (1–2): 1–5, arXiv : math/0511705 , MR 2350714

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]