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

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

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

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

Эти позиции могут быть сгенерированы жадным алгоритмом , в котором холодные позиции генерируются в числовом порядке, на каждом шаге выбирая наименьшее число, которое не имеет квадратичной разницы с любым ранее выбранным числом. ^{[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 с>0}$

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

Пауль Эрдёш предположил, что каждое множество, свободное от квадратной разности, имеет элементы вплоть до , для некоторой константы , но это было опровергнуто Саркози, который доказал, что существуют более плотные последовательности. Саркози ослабил гипотезу Эрдёша, предположив, что для каждого каждое множество, свободное от квадратной разности, имеет элементы вплоть до . ^[12] Это, в свою очередь, было опровергнуто Имре З. Ружей , который нашел множества, свободное от квадратной разности, с элементами вплоть до . ^[13]$${\displaystyle O(n^{1/2}\log ^{k}n)}$$${\displaystyle n}$${\displaystyle к}$${\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 б}$${\displaystyle б}$${\displaystyle R}$${\displaystyle 0}$${\displaystyle б-1}$ ${\displaystyle б}$${\displaystyle б}$${\displaystyle R}$${\displaystyle R=\{0,15,21,27,42,48,59\}}$${\displaystyle b=65}$${\displaystyle б=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} )}$