Теорема Фюрстенберга – Шаркози - Furstenberg–Sárközy theorem

В Теорема Фюрстенберга – Шаркози это результат аддитивная теория чисел на наборах чисел, никакие два из которых не отличаются на квадрат. В нем говорится, что если ${ displaystyle S}$ это набор натуральные числа с тем свойством, что нет двух чисел в ${ displaystyle S}$ отличаться квадратный номер, то естественная плотность из ${ displaystyle S}$ равно нулю. То есть на каждый ${ displaystyle varepsilon> 0}$, и для всех достаточно больших ${ displaystyle n}$, доля чисел до ${ displaystyle n}$ которые находятся в ${ displaystyle S}$ меньше чем ${ displaystyle varepsilon}$. Эквивалентно, каждый набор натуральных чисел с положительной верхней плотностью содержит два числа, разность которых равна квадрату (и, что более важно, бесконечно много таких пар).^[1] Теорема названа в честь Гилель Фюрстенберг и Андраш Шаркози, которые доказали это в конце 1970-х гг.

пример

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

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

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

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

Теорема Фюрстенберга – Шаркози была предположена Ласло Ловас, и независимо доказали в конце 1970-х Гилель Фюрстенберг и Андраш Шаркози, в честь кого назван.^[6][7] Со времени их работы было опубликовано несколько других доказательств того же результата, в основном либо упрощающих предыдущие доказательства, либо усиливающих границы того, насколько разреженным должно быть бесквадратное множество.^[8][9][10] В частности, теперь известно, что бесквадратный набор может включать не более

${ Displaystyle О (п / ( журнал п) ^ {{ гидроразрыва {1} {4}} журнал журнал журнал журнал п})}$

целых чисел из ${ displaystyle 0}$ к ${ displaystyle n}$, как выражено в нотация большой O.^[11]

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

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

Пол Эрдёш предположил, что каждое бесквадратное множество имеет

${ Displaystyle О (п ^ {1/2} журнал ^ {к} п)}$

элементы до ${ displaystyle n}$, для некоторой постоянной ${ displaystyle k}$, но это было опровергнуто Шаркози, доказавшим существование более плотных последовательностей. Шаркози ослабил гипотезу Эрдёша, предположив, что для каждого ${ displaystyle varepsilon> 0}$, каждый бесквадратный набор имеет

${ Displaystyle О (п ^ {1/2 + varepsilon})}$

элементы до ${ displaystyle n}$.^[12] Это, в свою очередь, было опровергнуто Имре З. Ружа, который нашел бесквадратные наборы с точностью до

${ displaystyle Omega left (n ^ {(1+ log _ {65} 7) / 2} right) приблизительно n ^ {0,733077}}$

элементы.^[13]

Конструкция Ружи выбирает целое число без квадратов ${ 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 left (n ^ {(1+ log _ {205} 12) / 2} right) приблизительно n ^ {0,733412}.}$^[14][15]

При нанесении на основу ${ displaystyle b = 2}$, та же конструкция порождает Последовательность Мозера – де Брейна умноженное на два, бесквадратное разностное множество, которое слишком разрежено, чтобы обеспечить нетривиальные нижние оценки теоремы Фюрстенберга – Шаркози, но обладает другими примечательными математическими свойствами.^[16]

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

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

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

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

использованная литература