Введение

Существование прямой, проходящей через две точки

Теорема Сильвестра — Галлая в геометрии утверждает, что для любого конечного множества точек на евклидовой плоскости существует прямая, проходящая ровно через две из этих точек, или прямая, проходящая через все точки множества. Она названа в честь Джеймса Джозефа Сильвестра, сформулировавшего её как задачу в 1893 году, и Тибора Галлая, опубликовавшего одно из первых доказательств этой теоремы в 1944 году. Прямая, содержащая ровно две точки из заданного множества, называется обычной прямой. Другая формулировка теоремы гласит, что любое конечное множество точек, не лежащих на одной прямой, имеет обычную прямую. Согласно усилению теоремы, любое конечное множество точек (не все лежащие на одной прямой) содержит хотя бы линейное число обычных прямых. Алгоритм может найти обычную прямую в множестве из точек за время .

История

Теорема Сильвестра — Галлая была сформулирована как проблема, и предполагается, что Сильвестр мог быть мотивирован связанным явлением в алгебраической геометрии, где точки перегиба кубической кривой в комплексной проективной плоскости образуют конфигурацию из девяти точек и двенадцати прямых (конфигурация Гессе), в которой каждая прямая, определяемая двумя точками, содержит третью точку. Теорема Сильвестра — Галлая подразумевает, что невозможно, чтобы все девять этих точек имели вещественные координаты. утверждал, что обладает коротким доказательством теоремы Сильвестра — Галлая, но уже при публикации было отмечено, что оно неполно. доказала теорему (и даже немного более сильный результат) в эквивалентной формулировке, а именно её проективной двойственной. Не зная о доказательстве Мелхиора, он вновь сформулировал гипотезу, которая впоследствии была доказана Тибором Галлаем, а вскоре после этого и другими авторами. В обзоре 1951 года Эрдеш назвал результат «теоремой Галлая», но уже в обзоре 1954 года Леонард Блюменталь назвал её теоремой Сильвестра — Галлая. Это одна из многих математических тем, названных в честь Сильвестра.

Эквивалентные версии

Вопрос о существовании обычной прямой также может быть поставлен для точек в реальной проективной плоскости RP2 вместо евклидовой плоскости. Проективная плоскость может быть получена из евклидовой плоскости путем добавления дополнительных точек «на бесконечности», в которых параллельные линии евклидовой плоскости пересекаются, и добавления единственной прямой «на бесконечности», содержащей все добавленные точки. Однако дополнительные точки проективной плоскости не позволяют создать неевклидовы конечные множества точек, не содержащие обычной прямой, поскольку любое конечное множество точек в проективной плоскости может быть преобразовано в евклидово множество точек с той же комбинаторной схемой инцидентности точек и прямых. Следовательно, любая схема из конечного числа пересекающихся точек и прямых, существующая в одном из этих двух типов плоскостей, существует и в другом. Тем не менее, проективный подход позволяет более легко описывать определенные конфигурации. В частности, он позволяет использовать проективную двойственность, при которой роли точек и прямых в утверждениях проективной геометрии можно менять местами. При проективной двойственности существование обычной прямой для множества неколлинеарных точек в RP2 эквивалентно существованию обычной точки в нетривиальной конфигурации конечного числа прямых. Конфигурация считается тривиальной, если все ее прямые проходят через одну общую точку, и нетривиальной в противном случае; обычная точка — это точка, принадлежащая ровно двум прямым. Конфигурации прямых обладают комбинаторной структурой, тесно связанной с зоноэдрами — многогранниками, образованными как сумма Минковского конечного набора отрезков прямых, называемых образующими. В этой связи каждая пара противоположных граней зоноэдра соответствует точке пересечения прямых в проективной плоскости, при этом на каждую образующую приходится одна прямая. Количество сторон каждой грани вдвое больше числа пересекающихся прямых в конфигурации. Например, показанный вытянутый додекаэдр является зоноэдром с пятью образующими, двумя парами противоположных шестиугольных граней и четырьмя парами противоположных параллелограммных граней. В соответствующей конфигурации из пяти прямых две тройки прямых пересекаются (что соответствует двум парам противоположных шестиугольников), а остальные четыре пары прямых пересекаются в обычных точках (что соответствует четырем парам противоположных параллелограммов). Эквивалентная формулировка теоремы Сильвестра — Галлая, выраженная в терминах зоноэдров, заключается в том, что каждый зоноэдр имеет по крайней мере одну параллелограммную грань (при этом прямоугольники, ромбы и квадраты рассматриваются как частные случаи параллелограммов). Более того, если можно гарантировать, что множества точек на плоскости имеют по крайней мере обычных прямых, то можно гарантировать, что зоноэдры с заданным числом образующих имеют по крайней мере заданное число параллелограммных граней.

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

Теорема Сильвестра — Галлая была доказана многими различными способами. Доказательство Галлая 1944 года переключается между евклидовой и проективной геометрией, чтобы преобразовать точки в эквивалентную конфигурацию, в которой обычная прямая может быть найдена как прямая с наклоном, наиболее близким к нулю; подробности см. Доказательство 1941 года Мелхиора использует проективную двойственность для преобразования задачи в эквивалентный вопрос о расположении прямых, на который можно ответить, используя полиэдрическую формулу Эйлера. Другое доказательство Леруа Милтона Келли показывает от противного, что соединяющая прямая с наименьшим ненулевым расстоянием до другой точки должна быть обычной. И, опираясь на более раннее доказательство Штейнберга, Х. С. М. Коксетер показал, что метрические понятия наклона и расстояния, используемые в доказательствах Галлая и Келли, излишне сильны, и вместо этого доказал теорему, используя только аксиомы упорядоченной геометрии.

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

Это доказательство принадлежит Лерою Милтону Келли. Назовем его «просто лучшим» из множества доказательств этой теоремы. Предположим, что конечное множество точек не все лежат на одной прямой. Определим соединяющую прямую как прямую, содержащую по крайней мере две точки из этого множества. В силу конечности множества, должна существовать точка и соединяющая прямая, находящиеся на положительном расстоянии друг от друга, но ближе, чем любая другая пара точка-прямая. Келли доказал, что эта пара является обычной, от противного. Предположим, что эта пара не является обычной. Тогда она проходит через по крайней мере три точки множества. По крайней мере две из этих точек лежат на одной стороне перпендикулярной проекции этой точки на прямую. Назовем их и , причем ближе к (и, возможно, совпадает с ней). Проведем соединяющую прямую, проходящую через и , и перпендикуляр из на эту прямую. Тогда этот перпендикуляр короче, чем расстояние между точкой и прямой. Это следует из того факта, что треугольники и подобны, причем один содержится внутри другого. Однако это противоречит исходному определению пары точка-прямая как пары с наименьшим положительным расстоянием. Следовательно, предположение о том, что пара не является обычной, неверно. Что и требовалось доказать.

Доказательство Мелхиора

В 1941 году (следовательно, до публикации вопроса Эрдошем и последующего доказательства Галлаем) Мельхиор показал, что любое нетривиальное конечное расположение линий в проективной плоскости имеет не менее трех обычных точек. По принципу двойственности, из этого результата также следует, что любое нетривиальное конечное множество точек на плоскости имеет не менее трех обычных прямых. Мельхиор заметил, что для любого графа, вложенного в реальную проективную плоскость, формула должна быть равна , характеристике Эйлера проективной плоскости. Здесь , , и – это количество вершин, ребер и граней графа соответственно. Любое нетривиальное расположение линий на проективной плоскости определяет граф, в котором каждая грань ограничена как минимум тремя ребрами, а каждое ребро ограничивает две грани; таким образом, двойной подсчет дает дополнительное неравенство. Использование этого неравенства для исключения из характеристики Эйлера приводит к неравенству. Но если бы каждая вершина в расположении была точкой пересечения трех или более линий, то общее количество ребер было бы не менее , что противоречит этому неравенству. Следовательно, некоторые вершины должны быть точкой пересечения только двух линий, и, как показывает более детальный анализ Мельхиора, для удовлетворения неравенства требуется не менее трех обычных вершин. Как отмечают, тот же аргумент в пользу существования обычной вершины был также приведен в 1944 году Норманом Стинродом, который явно применил его к двойственной задаче об обычных прямых.

Аксиоматика

пишет о доказательстве Келли, что его использование евклидова расстояния излишне эффективно, "как если бы раскалывать орех кувалдой". Вместо этого Коксетер предложил другое доказательство теоремы Сильвестра — Галлая в рамках упорядоченной геометрии, аксиоматизации геометрии, основанной на понятии "между", которая включает в себя не только евклидову геометрию, но и несколько других связанных геометрий. Доказательство Коксетера является вариацией более раннего доказательства, предложенного Штейнбергом в 1944 году. Задача поиска минимального набора аксиом, необходимых для доказательства теоремы, относится к обратной математике; см. для исследования этого вопроса. Стандартная формулировка теоремы Сильвестра — Галлая недействительна в конструктивном анализе, поскольку она подразумевает принцип ограниченной всезнательности, ослабленную форму закона исключённого третьего, который отвергается как аксиома конструктивной математики. Тем не менее, можно сформулировать версию теоремы Сильвестра — Галлая, которая справедлива в рамках аксиом конструктивного анализа, и адаптировать доказательство Келли, чтобы оно стало корректным доказательством в соответствии с этими аксиомами.

Количество обычных строк

В то время как теорема Сильвестра — Галлая утверждает, что расположение точек, не все коллинеарные, должно определять обычную прямую, она не указывает, сколько таких прямых должно быть определено. Пусть — минимальное количество обычных прямых, определяемых любым набором из неколлинеарных точек. Доказательство Мелхиора показало, что и подняло вопрос о том, стремится ли к бесконечности с ростом . подтвердил это, доказав, что . Было предположено, что для всех значений , и это предположение остаётся в силе по состоянию на 2013 год. Это часто называют гипотезой Дирака — Моцкина; см., например, доказал, что предполагаемая нижняя граница Дирака асимптотически является наилучшей возможной, поскольку чётные числа, большие четырёх, имеют соответствующую верхнюю границу. Конструкция, предложенная Каролем Борёцким, достигающая этой границы, состоит из вершин правильного -угольника в реальной проективной плоскости и ещё точек (таким образом, ) на бесконечно прямой, соответствующих каждому из направлений, определяемых парами вершин. Хотя эти точки существуют парами, они определяют только различных направлений. Эта конфигурация содержит только обычных прямых, то есть прямых, соединяющих вершину с точкой на бесконечности, коллинеарной с двумя её соседями. Как и любая конечная конфигурация в реальной проективной плоскости, эта конструкция может быть незначительно изменена так, чтобы все точки стали конечными, не меняя при этом количества обычных прямых. состоит из двух правильных пятиугольников, соединённых стороной к стороне, вместе со средней точкой общей стороны и четырьмя точками на бесконечно прямой в проективной плоскости; эти 13 точек содержат среди них 6 обычных прямых. Модификации конструкции Борёцкого приводят к наборам точек нечётного количества с обычными прямыми. доказал, что за исключением случая, когда равно семи. Асимптотически, эта формула уже является долей доказанной верхней границы. Случай является исключением, поскольку в противном случае конструкция Келли — Мозера была бы контрпримером; их конструкция показывает, что. Однако, если бы граница Цсима — Сойера была справедлива для , она утверждала бы, что.
Тесно связанным результатом является теорема Бека, устанавливающая компромисс между количеством прямых с малым числом точек и количеством точек на одной прямой. Бен Грин и Теренс Тао показали, что для всех достаточно больших наборов точек (то есть для некоторого подходящего выбора ) число обычных прямых действительно не меньше . Кроме того, когда нечётно, число обычных прямых не меньше , для некоторой константы. Таким образом, конструкции Борёцкого для чётных и нечётных (обсуждённые выше) являются оптимальными. Минимизация числа обычных прямых тесно связана с задачей о посадке сада, заключающейся в максимизации числа прямых, содержащих три точки, которую Грин и Тао также решили для всех достаточно больших наборов точек. В двойственной постановке, где ищутся обычные точки, можно рассмотреть минимальное количество обычных точек в расположении псевдопрямых. В этом контексте нижняя граница Цсима — Сойера остаётся справедливой, хотя неизвестно, сохраняется ли асимптотическая граница, полученная Грином и Тао.

Количество соединительных линий

Как заметил Пол Эрдош, теорема Сильвестра — Галлая немедленно влечет за собой, что любое множество точек, не лежащих на одной прямой, определяет по крайней мере различных прямых. Этот результат известен как теорема Де Брюйна — Эрдоша. В качестве базового случая результат очевидно верен для . Для любого большего значения , результат можно свести от точек к точкам, удалив обычную прямую и одну из двух точек на ней (следя за тем, чтобы не удалить точку, для которой оставшееся подмножество лежало бы на одной прямой). Таким образом, это следует из математической индукции. Пример почти карандаша, то есть множества коллинеарных точек вместе с одной дополнительной точкой, не лежащей на той же прямой, что и остальные, показывает, что эта оценка является точной.

Нереальные координаты

Так же, как Евклидова плоскость или проективная плоскость могут быть определены с помощью действительных чисел для координат их точек (картезианские координаты для Евклидовой плоскости и однородные координаты для проективной плоскости), аналогичные абстрактные системы точек и линий могут быть определены с помощью других систем чисел в качестве координат. Теорема Сильвестра — Галлая не выполняется для геометрий, определенных таким образом над конечными полями: для некоторых конечных геометрий, определенных таким образом, таких как плоскость Фано, множество всех точек в геометрии не содержит обычных линий. Теорема Сильвестра — Галлая также не применяется напрямую к геометриям, в которых точки имеют координаты, являющиеся парами комплексных чисел или кватернионов, но для этих геометрий существуют более сложные аналоги теоремы. Например, в комплексной проективной плоскости существует конфигурация из девяти точек, конфигурация Гессе (точки перегиба кубической кривой), в которой каждая прямая является неординарной, что противоречит теореме Сильвестра — Галлая. Такая конфигурация известна как конфигурация Сильвестра — Галлая и не может быть реализована точками и прямыми Евклидовой плоскости. Другая формулировка теоремы Сильвестра — Галлая заключается в том, что если точки конфигурации Сильвестра — Галлая вкладываются в евклидово пространство с сохранением коллинеарности, то все точки должны лежать на одной прямой, и пример конфигурации Гессе показывает, что это неверно для комплексной проективной плоскости. Однако было доказано комплексное аналогичное теореме Сильвестра — Галлая: если точки конфигурации Сильвестра — Галлая вкладываются в комплексное проективное пространство, то все точки должны лежать в двухмерном подпространстве. Эквивалентно, множество точек в трехмерном комплексном пространстве, аффинная оболочка которого является всем пространством, должно содержать обычную прямую, и более того, линейное число обычных прямых. Аналогично, было показано, что если конфигурация Сильвестра — Галлая вкладывается в пространство, определенное над кватернионами, то ее точки должны лежать в трехмерном подпространстве.

Матроиды

Каждый набор точек в евклидовой плоскости и линии, соединяющие их, могут быть абстрагированы как элементы и аффинные подпространства ориентированного матроида ранга 3. Точки и линии геометрий, определенных с использованием других систем чисел, отличных от действительных, также образуют матроиды, но не обязательно ориентированные матроиды. В этом контексте результат, устанавливающий нижнюю границу для числа обычных прямых, может быть обобщен на ориентированные матроиды: каждый ориентированный матроид ранга 3 с n элементами имеет по крайней мере две точки на прямой, или, эквивалентно, каждый матроид ранга 3 с меньшим числом точек на прямой должен быть неориентируемым. Матроид, не содержащий ни одной точки на прямой, называется матроидом Сильвестра. Кроме того, конфигурация Келли — Мозера, состоящая из семи точек и только трех обычных прямых, является одним из запрещенных миноров для матроидов, представимых в GF(4).

Геометрия расстояний

Еще одно обобщение теоремы Сильвестра — Галлая для произвольных метрических пространств было предложено и доказано. В этом обобщении тройка точек в метрическом пространстве считается коллинеарной, если неравенство треугольника для этих точек превращается в равенство, а линия определяется из любой пары точек путем последовательного добавления других точек, коллинеарных с уже добавленными, до тех пор, пока невозможно добавить новые точки. Обобщение Чватала и Чена утверждает, что каждое конечное метрическое пространство содержит линию, которая либо включает все точки, либо ровно две точки.