Теорема Фюрстенберга – Шаркози - 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 O(n/(\log n)^{{\frac {1}{4}}\log \log \log \log n})}$

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

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

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

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

${\displaystyle O(n^{1/2}\log ^{k}n)}$

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

${\displaystyle O(n^{1/2+\varepsilon })}$

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

${\displaystyle \Omega \left(n^{(1+\log _{65}7)/2}\right)\approx 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)\approx n^{0.733412}.}$^[14][15]

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

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

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

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

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

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

1. Эйснер, Таня; Фаркаш, Балинт; Хаасе, Маркус; Нагель, Райнер (2015), «20.5 Теорема Фюрстенберга – Шаркози», Теоретико-операторные аспекты эргодической теории, Тексты для выпускников по математике, 272, Cham, Switzerland: Springer, pp. 455–457, Дои:10.1007/978-3-319-16898-2, ISBN  978-3-319-16897-5, Г-Н  3410920.
2. Голомб, Соломон В. (1966), "Математическое исследование игр" на вынос"", Журнал комбинаторной теории, 1 (4): 443–458, Дои:10.1016 / S0021-9800 (66) 80016-9, Г-Н  0209015.
3. Слоан, Н. Дж. А. (ред.). «Последовательность A030193». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
4. Применимость этой теоремы к последовательности, полученной жадным алгоритмом, неявно подразумевается в Ружа (1984), который начинает свою статью с утверждения, что, «очевидно», жадная последовательность должна иметь размер, по крайней мере, пропорциональный квадратному корню. Лайалл и Райс (2015) заявляют, что конструкция Ружа (1984) генерирует наборы «намного больше, чем набор, полученный жадным алгоритмом», но не предоставляет границ или цитат, детализирующих размер жадного набора.
5. Эппштейн, Дэвид (2018), «Более быстрая оценка игр на вычитание», Ито, Хиро; Леонарди, Стефано; Пагли, Линда; Пренсипи, Джузеппе (ред.), Proc. 9-й Int. Конф. Развлечение с алгоритмами (FUN 2018), Международный журнал Лейбница по информатике (LIPIcs), 100, Schloss Dagstuhl, стр. 20: 1–20: 12, arXiv:1804.06515, Дои:10.4230 / LIPIcs.FUN.2018.20
6. Фюрстенберг, Гарри (1977), "Эргодическое поведение диагональных мер и теорема Семереди об арифметических прогрессиях", Журнал д'анализа математика, 31: 204–256, Дои:10.1007 / BF02813304, Г-Н  0498471.
7. Саркози, А. (1978), «О разностных наборах последовательностей целых чисел. I» (PDF), Acta Mathematica Academiae Scientiarum Hungaricae, 31 (1–2): 125–149, Дои:10.1007 / BF01896079, Г-Н  0466059.
8. Грин, Бен (2002), «Об арифметических структурах в плотных наборах целых чисел», Математический журнал герцога, 114 (2): 215–238, Дои:10.1215 / S0012-7094-02-11422-7, Г-Н  1920188.
9. Лайалл, Нил (2013), "Новое доказательство теоремы Саркози", Труды Американского математического общества, 141 (7): 2253–2264, arXiv:1107.0243, Дои:10.1090 / S0002-9939-2013-11628-X, Г-Н  3043007.
10. Тао, Терри (28 февраля 2013 г.), «Бесфурье-доказательство теоремы Фюрстенберга-Саркози», Какие новости
11. Пинц, Янош; Steiger, W. L .; Семереди, Эндре (1988), «О множествах натуральных чисел, разностное множество которых не содержит квадратов», Журнал Лондонского математического общества, Вторая серия, 37 (2): 219–231, Дои:10.1112 / jlms / s2-37.2.219, Г-Н  0928519.
12. Шаркози, А. (1978), «О разностных множествах последовательностей целых чисел. II», Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, 21: 45–53 (1979), Г-Н  0536201.
13. Ружа, И.З. (1984), «Разностные множества без квадратов», Periodica Mathematica Hungarica, 15 (3): 205–209, Дои:10.1007 / BF02454169, Г-Н  0756185.
14. Бейгель, Ричард; Гасарх, Уильям (2008), Наборы размеров без квадратов ${\displaystyle \Omega (n^{0.7334\dots })}$, arXiv:0804.4892, Bibcode:2008arXiv0804.4892B.
15. Левко, Марк (2015), «Улучшенная нижняя оценка, связанная с теоремой Фюрстенберга-Шаркози», Электронный журнал комбинаторики, 22 (1), Бумага P1.32, 6pp, Г-Н  3315474.
16. Слоан, Н. Дж. А. (ред.). «Последовательность A000695 (последовательность Мозера-де Брейна)». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
17. Лайалл, Нил; Райс, Алекс (2015), Разностные множества и многочлены, arXiv:1504.04904, Bibcode:2015arXiv150404904L.
18. Райс, Алекс (2019), "Максимальное расширение наиболее известных оценок теоремы Фюрстенберга – Шаркози", Acta Arithmetica, 187 (1): 1–41, arXiv:1612.01760, Дои:10.4064 / aa170828-26-8, Г-Н  3884220