Набор без квадратных разностей

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

(еще нерешенные задачи по математике)

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

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

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