Теорема Блихфельдта

Теорема Блихфельдта — математическая теорема в геометрии чисел , утверждающая, что всякий раз, когда ограниченное множество на евклидовой плоскости имеет площадь $A$ , его можно перевести так, чтобы оно включало как минимум $\lceil A\rceil$ точки целочисленной решетки . ^{[ 1 ]} Эквивалентно, каждое ограниченное множество площадей $A$ содержит набор $\lceil A\rceil$ точки, координаты которых отличаются целыми числами. ^{[ 2 ]}

Эту теорему можно обобщить на другие решетки и на более высокие измерения, и ее можно интерпретировать как непрерывную версию принципа «ячейки» . ^{[ 2 ]} Она названа в честь датско-американского математика Ганса Фредерика Блихфельдта , опубликовавшего ее в 1914 году. ^{[ 3 ]} Некоторые источники называют это принципом Блихфельдта. ^{[ 4 ]} или лемма Блихфельдта . ^{[ 5 ]}

Заявление и доказательство

Наиболее просто теорему можно сформулировать для точек евклидовой плоскости и для целочисленной решетки на плоскости. Для этой версии теоремы пусть $S$ любое измеримое множество , пусть $A$ обозначим его площадь и округлим это число до следующего целого значения, $n=\lceil A\rceil$ . Тогда теорема Блихфельдта утверждает, что $S$ можно перевести так, чтобы его переведенная копия содержала как минимум $n$ точки с целочисленными координатами. ^{[ 1 ]}

Основная идея доказательства — разрезать $S$ на части в соответствии с квадратами целочисленной решетки и перевести каждую из этих частей на целое число так, чтобы она лежала внутри единичного квадрата, которого находится начало координат в правом нижнем углу. Этот перевод может привести к тому, что некоторые части единичного квадрата будут покрыты более одного раза, но если объединенная площадь переведенных частей посчитана с кратностью, она останется неизменной, равной $A$ . С другой стороны, если бы весь единичный квадрат был покрыт кратностью $n-1$ его площадь будет $n-1$ , меньше, чем $A$ . Поэтому какой-то момент $p$ единичного квадрата должна быть покрыта кратностью не менее $n$ . Перевод, который занимает $p$ в начало координат также перенесет все $n$ точки $S$ это покрыло $p$ до целых точек, что и требовалось. ^{[ 1 ]}

В более общем смысле теорема применима к $d$ -мерные множества $S$ , с $d$ -мерный объем $A$ , и произвольному $d$ -мерная решетка $\Lambda$ (набор точек в $d$ -мерное пространство, которые не все лежат в каком-либо подпространстве более низкой размерности, отделены друг от друга некоторым минимальным расстоянием и могут быть объединены путем добавления или вычитания их координат для создания других точек в том же наборе). Подобно тому, как целочисленная решетка делит плоскость на квадраты, произвольная решетка делит свое пространство на фундаментальные области (называемые параллелоэдрами ) со свойством, что любая из этих областей может быть переведена на любую другую путем добавления координат уникальной точки решетки. . Если $L$ это $d$ -мерный объем одного из параллелоэдров, то теорема Блихфельдта утверждает, что $S$ можно перевести, включив как минимум $\lceil A/L\rceil$ точки $\Lambda$ . Доказательство то же самое: разрезать $S$ по параллелотопам, перевести куски по векторам перевода в $\lambda$ на один параллелоэдр, не меняя общего объема (считаемого с кратностью), заметим, что должна существовать точка $p$ кратности, по крайней мере $\lceil A/L\rceil$ и используйте перевод, который принимает $p$ к источнику. ^{[ 1 ]}

Вместо того, чтобы просить перевод, для которого есть $n$ точек решетки, эквивалентная форма теоремы утверждает, что $S$ сам содержит набор $n$ точки, все попарные разности которых принадлежат решетке. ^{[ 2 ]} Усиленная версия теоремы применима к компактным множествам и утверждает, что их можно перевести так, чтобы они содержали по крайней мере $\lfloor A+1\rfloor$ точки решетки. Это количество баллов отличается от $\lceil A\rceil$ только когда $A$ является целым числом, для которого оно больше на единицу. ^{[ 1 ]}

Приложения

Теорема Минковского

Теорема Минковского раньше, чем работа Блихфельдта , доказанная Германом Минковским , утверждает, что любое выпуклое множество на плоскости, центрально симметричное относительно начала координат, с площадью больше четырех (или компактное симметричное множество с площадью, равной четырем), содержит ненулевую целочисленную точку. . В более общем смысле для $d$ -мерная решетка $\Lambda$ чьи фундаментальные параллелоэдры имеют объем $L$ , любое множество, центрально симметричное относительно начала координат, с объемом, превышающим $2^{d}L$ содержит ненулевую точку решетки. ^{[ 1 ]}

Хотя первоначальное доказательство Минковского было другим, теорему Бличфельдта можно использовать для простого доказательства теоремы Минковского. Позволять $X$ — любое центрально-симметричное множество с объемом, большим, чем $2^{d}L$ (отвечающего условиям теоремы Минковского) и уменьшите его в два раза, чтобы получить набор ${\tfrac {1}{2}}X$ объема больше, чем $L$ . По теореме Блихфельдта ${\tfrac {1}{2}}X$ имеет две точки $p$ и $q$ покоординатная разность которого принадлежит $L$ . Отмена операции сжатия, $2p$ и $2q$ принадлежать $X$ . По симметрии $-2q$ также принадлежит $X$ , а по выпуклости середина $2p$ и $-2q$ принадлежит $X$ . Но эта середина $p-q$ , ненулевая точка $L$ . ^{[ 2 ]}

Другие приложения

Многие приложения теоремы Блихфельдта, как и приложение к теореме Минковского, предполагают поиск ненулевой точки решетки в достаточно большом множестве, но не выпуклом. Для доказательства теоремы Минковского ключевым соотношением между множествами $X$ и ${\tfrac {1}{2}}X$ доказательство работает, состоит в том, что все различия пар точек в ${\tfrac {1}{2}}X$ принадлежать $X$ . Однако для набора $X$ это не выпукло, ${\tfrac {1}{2}}X$ могут иметь пары точек, разность которых не принадлежит $X$ , что делает его непригодным для использования в этой технике. Вместо этого можно было бы найти наибольшее центрально-симметричное выпуклое подмножество. $K\subset X$ , а затем применить теорему Минковского к $K$ или, что то же самое, применить теорему Блихфельдта к ${\tfrac {1}{2}}K$ . Однако во многих случаях данное невыпуклое множество $X$ имеет подмножество $Y\subset X$ это больше, чем ${\tfrac {1}{2}}K$ , попарные разности которого принадлежат $X$ . В этом случае больший размер $Y$ относительно ${\tfrac {1}{2}}K$ приводит к ужесточению границ размера $X$ необходимо быть уверенным в наличии точки решетки. ^{[ 6 ]}

Для центрально-симметричной звездной области можно использовать вариационное исчисление , чтобы найти наибольшее множество $X'$ чьи попарные разности принадлежат $X$ . Приложения этого метода включают одновременную диофантову аппроксимацию , проблему приближения данного набора иррациональных чисел рациональными числами, имеющими одинаковые знаменатели. ^{[ 6 ]}

Обобщения

Аналоги теоремы Блихфельдта были доказаны для других наборов точек, кроме решеток, показывая, что достаточно большие области содержат много точек из этих наборов. К ним относятся теорема для фуксовых групп , решетчатых подмножеств $2\times 2$ матрицы, ^{[ 7 ]} и для множеств вершин архимедовых разбиений . ^{[ 8 ]}^{[ 9 ]}

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

Вычислительная сложность

Было показано, что вычислительная задача, связанная с теоремой Блихфельдта, является полной для класса сложности PPP и, следовательно, вряд ли может быть решена за полиномиальное время. Задача принимает на вход набор целочисленных векторов, образующих основу $d$ -мерная решетка $\Lambda$ , и набор $S$ целочисленных векторов, неявно представленных логической схемой для проверки того, принадлежит ли данный вектор $S$ . Требуется, чтобы мощность $S$ , разделенный на объем основного параллелоэдра $\Lambda$ , есть хотя бы один, из чего из дискретной версии теоремы Блихфельдта следует, что $S$ включает в себя пару точек, разность которых принадлежит $\Lambda$ . Задача состоит в том, чтобы найти либо такую пару, либо точку $S$ который сам принадлежит $\Lambda$ . Вычислительная сложность этой задачи мотивирует создание кандидата на устойчивую к коллизиям криптографическую хеш-функцию . ^{[ 11 ]}

См. также

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

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Олдс, CD ; Лакс, Аннели ; Давидофф, Джулиана П. (2000), «Глава 9: Новый принцип геометрии чисел», Геометрия чисел , Новая математическая библиотека Аннели Лакс, том. 41, Математическая ассоциация Америки, Вашингтон, округ Колумбия, стр. 119–127, ISBN. 0-88385-643-3 , МР : 1817689
^ Jump up to: ^а ^б ^с ^д Касселс, JWS (1978), «Теорема 2.1 (Блихфельдт)» , Рациональные квадратичные формы , Монографии Лондонского математического общества, том. 13, Академик Пресс, с. 68, ISBN 0-12-163260-1 , МР 0522835
^ Бличфельдт, HF (1914), «Новый принцип геометрии чисел с некоторыми приложениями», Transactions of the American Mathematical Society , 15 (3): 227–235, doi : 10.1090/S0002-9947-1914-1500976- 6 , JSTOR 1988585 , MR 1500976
^ Марвин, Стивен (ноябрь 2012 г.), «B», Словарь научных принципов , John Wiley & Sons, стр. 19–36, doi : 10.1002/9781118582121.ch2
^ Хонсбергер, Росс (1973), «Проблема фруктового сада», Mathematical Gems I , Dolciani Mathematical Expositions, vol. 1, Математическая ассоциация Америки, стр. 43–53 ; см., в частности, лемму Блихфельдта, с. 44
^ Jump up to: ^а ^б Спон, WG (1968), «Теорема Блихфельдта и одновременное диофантово приближение», American Journal of Mathematics , 90 : 885–894, doi : 10.2307/2373489 , JSTOR 2373489 , MR 0231794
^ Цудзи, Масацугу (1956), «Аналог теоремы Блихфельдта для фуксовых групп», Commentarii Mathematici Universitatis Sancti Pauli , 5 : 17–24, MR 0081323
^ Цао, Пэнхао; Юань, Липинг (2011), «Теорема типа Блихфельдта для $H$ -points», American Mathematical Monthly , 118 (8): 743–746, doi : 10.4169/amer.math.monthly.118.08.743 , MR 2843996
^ Шимура, Матиас; Юань, Липинг (2019), «Заметка о дискретных решеточно-периодических множествах с применением к архимедовым мозаикам», Contributions to Algebra and Geometry , 60 (4): 749–759, arXiv : 1710.02552 , doi : 10.1007/s13366-019 -00446-x , МР 4025474
^ Леккеркеркер, CG (1969), «Раздел 2.6: Обобщения теоремы Блихфельдта», Геометрия чисел , Bibliotheca Mathematica, vol. 8, Северная Голландия, стр. 40–43, MR 0271032.
^ Сотираки, Катерина; Зампетакис, Манолис; Зирделис, Гиоргос (2018), «PPP-полнота со связью с криптографией», Торуп, Миккель (редактор), 59-й ежегодный симпозиум IEEE по основам компьютерных наук, FOCS 2018, Париж, Франция, 7-9 октября 2018 г. , Компьютерное общество IEEE, стр. 148–158, arXiv : 1808.06407. , doi : 10.1109/FOCS.2018.00023 , МР 3899585

Внешние ссылки

Вайсштейн, Эрик В. , «Теорема Блихфельдта» , MathWorld

[olds-1] Jump up to: ^а ^б ^с ^д ^и ^ж Олдс, CD ; Лакс, Аннели ; Давидофф, Джулиана П. (2000), «Глава 9: Новый принцип геометрии чисел», Геометрия чисел , Новая математическая библиотека Аннели Лакс, том. 41, Математическая ассоциация Америки, Вашингтон, округ Колумбия, стр. 119–127, ISBN. 0-88385-643-3 , МР : 1817689

[cassels-2] Jump up to: ^а ^б ^с ^д Касселс, JWS (1978), «Теорема 2.1 (Блихфельдт)» , Рациональные квадратичные формы , Монографии Лондонского математического общества, том. 13, Академик Пресс, с. 68, ISBN 0-12-163260-1 , МР 0522835

[blichfeldt-3] Бличфельдт, HF (1914), «Новый принцип геометрии чисел с некоторыми приложениями», Transactions of the American Mathematical Society , 15 (3): 227–235, doi : 10.1090/S0002-9947-1914-1500976- 6 , JSTOR 1988585 , MR 1500976

[marvin-4] Марвин, Стивен (ноябрь 2012 г.), «B», Словарь научных принципов , John Wiley & Sons, стр. 19–36, doi : 10.1002/9781118582121.ch2

[honsberger-5] Хонсбергер, Росс (1973), «Проблема фруктового сада», Mathematical Gems I , Dolciani Mathematical Expositions, vol. 1, Математическая ассоциация Америки, стр. 43–53 ; см., в частности, лемму Блихфельдта, с. 44

[spohn-6] Jump up to: ^а ^б Спон, WG (1968), «Теорема Блихфельдта и одновременное диофантово приближение», American Journal of Mathematics , 90 : 885–894, doi : 10.2307/2373489 , JSTOR 2373489 , MR 0231794

[tsuji-7] Цудзи, Масацугу (1956), «Аналог теоремы Блихфельдта для фуксовых групп», Commentarii Mathematici Universitatis Sancti Pauli , 5 : 17–24, MR 0081323

[cao-8] Цао, Пэнхао; Юань, Липинг (2011), «Теорема типа Блихфельдта для $H$ -points», American Mathematical Monthly , 118 (8): 743–746, doi : 10.4169/amer.math.monthly.118.08.743 , MR 2843996

[schymura-9] Шимура, Матиас; Юань, Липинг (2019), «Заметка о дискретных решеточно-периодических множествах с применением к архимедовым мозаикам», Contributions to Algebra and Geometry , 60 (4): 749–759, arXiv : 1710.02552 , doi : 10.1007/s13366-019 -00446-x , МР 4025474

[lekkerkerker-10] Леккеркеркер, CG (1969), «Раздел 2.6: Обобщения теоремы Блихфельдта», Геометрия чисел , Bibliotheca Mathematica, vol. 8, Северная Голландия, стр. 40–43, MR 0271032.

[sotiraki-11] Сотираки, Катерина; Зампетакис, Манолис; Зирделис, Гиоргос (2018), «PPP-полнота со связью с криптографией», Торуп, Миккель (редактор), 59-й ежегодный симпозиум IEEE по основам компьютерных наук, FOCS 2018, Париж, Франция, 7-9 октября 2018 г. , Компьютерное общество IEEE, стр. 148–158, arXiv : 1808.06407. , doi : 10.1109/FOCS.2018.00023 , МР 3899585

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]