Множество, свободное от квадратной разности

Числа, разности которых не являются квадратами

В математике множество , свободное от квадратной разности, — это множество натуральных чисел , никакие два из которых не отличаются на квадратное число . В конце 1970-х годов Хиллель Фюрстенберг и Андраш Саркози доказали теорему Фюрстенберга–Саркози из аддитивной теории чисел, показывающую, что в определенном смысле эти множества не могут быть очень большими. В игре « Вычитание квадрата» позиции, в которых проигрывает следующий игрок, образуют множество, свободное от квадратной разности. Другое множество, свободное от квадратной разности, получается путем удвоения последовательности Мозера–де Брейна .

Лучшая известная верхняя граница размера множества чисел, свободного от квадратной разности, вплоть до является лишь слегка сублинейной, но самые большие известные множества этой формы значительно меньше, размером . Сокращение разрыва между этими верхними и нижними границами остается открытой проблемой . Границы сублинейных размеров множеств, свободных от квадратной разности, можно обобщить на множества, где некоторые другие многочлены запрещены как разности между парами элементов. ${\displaystyle n}$ ${\displaystyle \approx n^{0.733412}}$

Пример

Примером множества без квадратной разницы является игра « Вычти квадрат », придуманная Ричардом А. Эпштейном и впервые описанная в 1966 году Соломоном В. Голомбом . В этой игре два игрока по очереди вынимают монеты из кучи монет; игрок, вытащивший последнюю монету, выигрывает. За каждый ход игрок может вынуть из кучи только ненулевое квадратное число монет. ^[1] Любая позиция в этой игре может быть описана целым числом — ее количеством монет. Неотрицательные целые числа можно разбить на «холодные» позиции, в которых игрок, который собирается сделать ход, проигрывает, и «горячие» позиции, в которых игрок, который собирается сделать ход, может выиграть, перейдя в холодную позицию. Никакие две холодные позиции не могут отличаться на квадрат, потому что если бы они отличались, то игрок, столкнувшийся с большей из двух позиций, мог бы переместиться в меньшую позицию и выиграть. Таким образом, холодные позиции образуют множество без квадратной разницы:

0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44, … (последовательность A030193 в OEIS )

Эти позиции могут быть сгенерированы жадным алгоритмом , в котором холодные позиции генерируются в числовом порядке, на каждом шаге выбирая наименьшее число, которое не имеет квадратичной разницы с любым ранее выбранным числом. ^{[1] [2]} Как заметил Голомб, холодные позиции бесконечны, и, что более строго, число холодных позиций до по крайней мере пропорционально . Ведь если бы было меньше холодных позиций, их было бы недостаточно, чтобы обеспечить выигрышный ход в каждую горячую позицию. ^[1] Теорема Фюрстенберга–Саркози показывает, однако, что холодные позиции встречаются реже, чем горячие позиции: для любого и для всех достаточно больших , доля холодных позиций до не превышает . То есть, столкнувшись с начальной позицией в диапазоне от 1 до , первый игрок может выиграть из большинства этих позиций. ^[3] Численные данные свидетельствуют о том, что фактическое число холодных позиций до приблизительно равно . [ ^4] ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \varepsilon }$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n^{0.7}}$

Верхние границы

Согласно теореме Фюрстенберга–Саркези, если — множество, свободное от квадратной разности, то естественная плотность равна нулю. То есть для любого и для всех достаточно больших доля чисел до , содержащихся в , меньше . Эквивалентно, каждое множество натуральных чисел с положительной верхней плотностью содержит два числа, разность которых является квадратом, и, что более строго, содержит бесконечно много таких пар. ^[5] Теорема Фюрстенберга–Саркези была выдвинута Ласло Ловасом и независимо доказана в конце 1970-х годов Хиллелем Фюрстенбергом и Андрашем Саркези , в честь которых она и названа. ^{[6] [7]} После их работы было опубликовано несколько других доказательств того же результата, в основном либо упрощающих предыдущие доказательства, либо усиливающих границы того, насколько разреженным должно быть множество, свободное от квадратной разности. ^{[8] [9] [10]} Лучшая из известных в настоящее время верхних границ принадлежит Томасу Блуму и Джеймсу Мейнарду , ^[11] которые показали, что множество, свободное от разностей квадратов, может включать в себя большинство целых чисел от до , как выражено в нотации O большое , где — некоторая абсолютная константа. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle \varepsilon }$ $${\displaystyle O\!\left({\frac {n}{(\log n)^{c\log \log \log n}}}\right)}$$ ${\displaystyle 0}$ ${\displaystyle n}$ ${\displaystyle c>0}$

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

Нижние границы

Пауль Эрдёш предположил, что каждое множество, свободное от квадратной разности, имеет элементы вплоть до , для некоторой константы , но это было опровергнуто Саркози, который доказал, что существуют более плотные последовательности. Саркози ослабил гипотезу Эрдёша, предположив, что для каждого каждое множество, свободное от квадратной разности, имеет элементы вплоть до . ^[12] Это, в свою очередь, было опровергнуто Имре З. Ружей , который нашел множества, свободное от квадратной разности, с элементами вплоть до . ^[13] $${\displaystyle O(n^{1/2}\log ^{k}n)}$$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \varepsilon >0}$ $${\displaystyle O(n^{1/2+\varepsilon })}$$ ${\displaystyle n}$ $${\displaystyle \Omega {\big (}n^{(1\,+\,\log _{65}7)/2}{\big )}\approx n^{0.733077}}$$

Конструкция Ружи выбирает целое число , свободное от квадратов , в качестве основания системы счисления с основанием для целых чисел, так что существует большой набор чисел от до ни одно из которых не является квадратом по модулю . Затем он выбирает свой набор, свободный от квадратов, в качестве чисел, которые в системе с основанием имеют элементы в четных позициях цифр. Цифры в нечетных позициях этих чисел могут быть произвольными. Ружа нашел набор из семи элементов по модулю , что дает указанную границу. Впоследствии конструкция Ружи была улучшена путем использования другого основания, , чтобы дать множества, свободные от квадратов, размером ^{[14] [15]} При применении к основанию та же конструкция генерирует последовательность Мозера–де Брейна , умноженную на два, набор элементов, свободный от квадратов . Это слишком разреженно, чтобы обеспечить нетривиальные нижние границы теоремы Фюрстенберга–Саркези, но та же последовательность обладает другими примечательными математическими свойствами. ^[16] ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle R}$ ${\displaystyle 0}$ ${\displaystyle b-1}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle R}$ ${\displaystyle R=\{0,15,21,27,42,48,59\}}$ ${\displaystyle b=65}$ ${\displaystyle b=205}$ $${\displaystyle \Omega {\big (}n^{(1\,+\,\log _{205}12)/2}{\big )}\approx n^{0.733412}.}$$ ${\displaystyle b=2}$ ${\displaystyle O(n^{1/2})}$

Нерешенная задача по математике :

Существует ли показатель степени, такой что каждое подмножество, свободное от квадратной разности, имеет элементы? ${\displaystyle c<1}$ ${\displaystyle [0,n]}$ ${\displaystyle O(n^{c})}$

(еще нерешенные проблемы по математике)

На основании этих результатов было высказано предположение, что для любого достаточно большого числа существуют подмножества чисел от до с элементами, свободные от квадратной разности. То есть, если эта гипотеза верна, показатель степени единицы в верхних границах теоремы Фюрстенберга–Саркози не может быть понижен. ^[9] В качестве альтернативной возможности показатель степени 3/4 был определен как «естественное ограничение конструкции Ружи» и еще один кандидат на истинную максимальную скорость роста этих множеств. ^[17] ${\displaystyle \varepsilon >0}$ ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle n}$ ${\displaystyle \Omega (n^{1-\varepsilon })}$

Обобщение на другие многочлены

Верхнюю границу теоремы Фюрстенберга–Саркози можно обобщить с множеств, которые избегают разностей квадратов, на множества, которые избегают разностей в , значениях в целых числах многочлена с целыми коэффициентами , при условии, что значения включают целое число, кратное каждому целому числу. Условие на кратные целых чисел необходимо для этого результата, поскольку если есть целое число , кратные которого не появляются в , то кратные будут образовывать множество ненулевой плотности без разностей в . ^[18] ${\displaystyle p(\mathbb {N} )}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle p(\mathbb {N} )}$ ${\displaystyle k}$ ${\displaystyle p(\mathbb {N} )}$

Ссылки

1. Голомб, Соломон В. (1966), "Математическое исследование игр "на вынос"", Журнал комбинаторной теории , 1 (4): 443–458, doi : 10.1016/S0021-9800(66)80016-9 , MR  0209015.
2. Слоан, Н. Дж. А. (ред.), «Последовательность A030193», Онлайновая энциклопедия целочисленных последовательностей , Фонд OEIS
3. Применимость этой теоремы к последовательности, полученной с помощью жадного алгоритма, подразумевается в работе Ruzsa (1984), которая начинает свою работу с утверждения, что «очевидно», что жадная последовательность должна иметь размер, по крайней мере пропорциональный квадратному корню. Lyall & Rice (2015) утверждают, что конструкция Ruzsa (1984) генерирует множества, «гораздо большие, чем множество, полученное с помощью жадного алгоритма», но не приводят границ или ссылок, которые бы подробно описывали размер жадного множества.
4. Эппштейн, Дэвид (2018), «Быстрая оценка игр на вычитание», в Ито, Хиро; Леонарди, Стефано; Пагли, Линда ; Пренсипе, Джузеппе (ред.), Proc. 9th Int. Conf. Fun with Algorithms (FUN 2018) , Leibniz International Proceedings in Informatics (LIPIcs), т. 100, Schloss Dagstuhl, стр. 20:1–20:12, arXiv : 1804.06515 , doi : 10.4230/LIPIcs.FUN.2018.20 , ISBN 9783959770675, S2CID  4952124
5. Эйснер, Таня ; Фаркаш, Балинт; Хаазе, Маркус; Нагель, Райнер (2015), "20.5 Теорема Фюрстенберга–Саркози", Теоретические аспекты операторов эргодической теории , Graduate Texts in Mathematics , т. 272, Хам, Швейцария: Springer, стр. 455–457, doi :10.1007/978-3-319-16898-2, ISBN 978-3-319-16897-5, МР  3410920.
6. Фюрстенберг, Гарри (1977), «Эргодическое поведение диагональных мер и теорема Семереди об арифметических прогрессиях», Journal d'Analyse Mathématique , 31 : 204–256, doi :10.1007/BF02813304, MR  0498471, S2CID  120917478.
7. Саркози, А. (1978), «О разностных множествах последовательностей целых чисел. I» (PDF) , Acta Mathematica Academiae Scientiarum Hungaricae , 31 (1–2): 125–149, doi : 10.1007/BF01896079 , MR  0466059, S2CID  122018775.
8. Грин, Бен (2002), «Об арифметических структурах в плотных множествах целых чисел», Duke Mathematical Journal , 114 (2): 215–238, doi :10.1215/S0012-7094-02-11422-7, MR  1920188.
9. Lyall, Neil (2013), «Новое доказательство теоремы Саркози», Труды Американского математического общества , 141 (7): 2253–2264, arXiv : 1107.0243 , doi : 10.1090/S0002-9939-2013-11628-X , MR  3043007, S2CID  16842750.
10. Tao, Terry (28 февраля 2013 г.), "Доказательство теоремы Фюрстенберга-Саркози без использования Фурье", Что нового
11. Блум, Томас Ф.; Мейнард, Джеймс (24 февраля 2021 г.). «Новая верхняя граница для множеств без разностей квадратов». arXiv : 2011.13266 [math.NT].
12. Саркози, А. (1978), «О разностных множествах последовательностей целых чисел. II», Annales Universitatis Scientiarum Buddhainensis de Rolando Eötvös Nominatae , 21 : 45–53 (1979), MR  0536201.
13. Ruzsa, IZ (1984), «Разностные множества без квадратов», Periodica Mathematica Hungarica , 15 (3): 205–209, doi :10.1007/BF02454169, MR  0756185, S2CID  122624503.
14. Бейгель, Ричард; Газарч, Уильям (2008), Множества размера , свободные от квадратной разности , arXiv : 0804.4892 , Bibcode : 2008arXiv0804.4892B ${\displaystyle \Omega (n^{0.7334\dots })}$.
15. Левко, Марк (2015), «Улучшенная нижняя граница, связанная с теоремой Фюрстенберга-Саркози», Электронный журнал комбинаторики , 22 (1), Статья P1.32, 6 стр., doi : 10.37236/4656 , MR  3315474.
16. Слоан, Н. Дж. А. (ред.), «Последовательность A000695 (последовательность Мозера-де Брейна)», Онлайновая энциклопедия целочисленных последовательностей , Фонд OEIS
17. Лайалл, Нил; Райс, Алекс (2015), Разностные множества и многочлены , arXiv : 1504.04904 , Bibcode : 2015arXiv150404904L.
18. Райс, Алекс (2019), «Максимальное расширение наиболее известных границ теоремы Фюрстенберга–Саркози», Acta Arithmetica , 187 (1): 1–41, arXiv : 1612.01760 , doi : 10.4064/aa170828-26-8, MR  3884220, S2CID  119139825