последовательность Стэнли

Математическая последовательность, включающая арифметические прогрессии

В математике последовательность Стэнли — это целочисленная последовательность , сгенерированная жадным алгоритмом , который выбирает элементы последовательности так, чтобы избежать арифметических прогрессий . Если — конечный набор неотрицательных целых чисел, на котором никакие три элемента не образуют арифметическую прогрессию (то есть набор Сейлема–Спенсера ), то последовательность Стэнли, сгенерированная из , начинается с элементов , в отсортированном порядке, а затем многократно выбирает каждый последующий элемент последовательности как число, которое больше уже выбранных чисел и не образует с ними никакой трехчленной арифметической прогрессии. Эти последовательности названы в честь Ричарда П. Стэнли . ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

Двоично-троичная последовательность

Последовательность Стэнли, начинающаяся с пустого множества, состоит из тех чисел, троичные представления которых содержат только цифры 0 и 1. ^[1] То есть, будучи записанными в троичной системе, они выглядят как двоичные числа . Эти числа

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (последовательность A005836 в OEIS )

По своей конструкции как последовательность Стэнли, эта последовательность является лексикографически первой последовательностью без арифметической прогрессии . Ее элементами являются суммы различных степеней трех , числа, такие что th центральный биномиальный коэффициент равен 1 mod 3, и числа, сбалансированное троичное представление которых совпадает с их троичным представлением. ^[2] ${\displaystyle n}$ ${\displaystyle n}$

Построение этой последовательности из троичных чисел аналогично построению последовательности Мозера–де Брейна , последовательности чисел, чьи представления по основанию 4 имеют только цифры 0 и 1, и построению множества Кантора как подмножества действительных чисел в интервале, чьи троичные представления используют только цифры 0 и 2. В более общем смысле, они являются 2-регулярной последовательностью , одной из класса целочисленных последовательностей, определяемых линейным рекуррентным соотношением с множителем 2. ^[3] ${\displaystyle [0,1]}$

Эта последовательность включает в себя три степени двойки : 1, 4 и 256 = 3 ⁵ + 3 ² + 3 + 1. Пол Эрдёш предположил, что это единственные степени двойки, которые она содержит. ^[4]

Темпы роста

Эндрю Одлыжко и Ричард П. Стэнли заметили, что число элементов до некоторого порогового значения в двоично-троичной последовательности и в других последовательностях Стэнли, начинающихся с или , растет пропорционально . Для других начальных наборов последовательности Стэнли, которые они рассматривали, по-видимому, растут более хаотично, но еще более разреженно. ^[1] Например, первый нерегулярный случай — это , который генерирует последовательность ${\displaystyle n}$ ${\displaystyle \{0,3^{k}\}}$ ${\displaystyle \{0,2\cdot 3^{k}\}}$ ${\displaystyle n^{\log _{2}3}\approx n^{0.631}}$ ${\displaystyle \{0,s\}}$ ${\displaystyle s=4}$

0, 4, 5, 7, 11, 12, 16, 23, 26, 31, 33, 37, 38, 44, 49, 56, 73, 78, 80, 85, 95, 99, ... (последовательность A005487 в OEIS )

Одлыжко и Стэнли предположили, что в таких случаях число элементов до любого порога равно . То есть, существует дихотомия в скорости роста последовательностей Стэнли между теми, у которых рост аналогичен двоично-троичной последовательности, и другими, у которых скорость роста гораздо меньше; согласно этой гипотезе, не должно быть последовательностей Стэнли с промежуточным ростом. ^{[1] [5]} ${\displaystyle n}$ ${\displaystyle O{\bigl (}{\sqrt {n\log n}}{\bigr )}}$

Мой доказал, что последовательности Стэнли не могут расти значительно медленнее, чем предполагаемая граница для последовательностей медленного роста. Каждая последовательность Стэнли имеет элементы до . Точнее, Мой показал, что для каждой такой последовательности, для каждого и всех достаточно больших , число элементов не менее . ^[6] Более поздние авторы улучшили постоянный множитель в этой границе, ^[7] и доказали, что для последовательностей Стэнли, которые растут как постоянный множитель в их темпах роста, может быть любым рациональным числом, знаменатель которого является степенью трех. ^[8] ${\displaystyle \Omega {\bigl (}{\sqrt {n}}{\bigr )}}$ ${\displaystyle n}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle n}$ ${\displaystyle ({\sqrt {2}}-\varepsilon ){\sqrt {n}}}$ ${\displaystyle n^{\log _{2}3}}$

История

Разновидность двоично-троичной последовательности (с добавлением одного элемента к каждому элементу) была рассмотрена в 1936 году Полом Эрдёшем и Палом Тураном , которые заметили, что она не имеет трехчленной арифметической прогрессии, и предположили (ошибочно), что это самая плотная возможная последовательность без арифметической прогрессии. ^[9]

В неопубликованной работе с Эндрю Одлыжко в 1978 году Ричард П. Стэнли экспериментировал с жадным алгоритмом для генерации последовательностей без прогрессии. Последовательности, которые они изучали, были в точности последовательностями Стэнли для начальных наборов . ^[1] ${\displaystyle \{0,s\}}$

Последовательности Стэнли были названы и обобщены на другие начальные множества, отличные от , в статье, опубликованной в 1999 году Эрдёшем (посмертно) совместно с четырьмя другими авторами. ^[5] ${\displaystyle \{0,s\}}$

Ссылки

1. Одлыжко, AM ; Стэнли, RP (январь 1978), OdlSta-78 (PDF)
2. Sloane, N. J. A. (ред.). "Последовательность A005836". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
3. Аллуш, Жан-Поль; Шаллит, Джеффри (1992), «Кольцо -регулярных последовательностей», Теоретическая информатика , 98 (2): 163–197, CiteSeerX 10.1.1.8.6912 , doi :10.1016/0304-3975(92)90001-V, MR  1166363 ${\displaystyle k}$ . См. пример 26, стр. 192.
4. Гупта, Хансрай (1978), «Степени 2 и суммы различных степеней 3», Univerzitet u Beogradu Publikacije Elektrotehničkog Fakulteta, Serija Matematika i Fizika (602–633): 151–158 (1979), MR  0580438
5. Erdős, P. ; Lev, V.; Rauzy, G.; Sándor, C.; Sárközy, A. (1999), "Жадный алгоритм, арифметические прогрессии, суммы подмножеств и делимость", Discrete Mathematics , 200 (1–3): 119–135, doi : 10.1016/S0012-365X(98)00385-9 , MR  1692285
6. Мой, Ричард А. (2011), «О росте счетной функции последовательностей Стэнли», Дискретная математика , 311 (7): 560–562, arXiv : 1101.0022 , doi : 10.1016/j.disc.2010.12.019, MR  2765623, S2CID  11040813
7. Дай, Ли-Ся; Чэнь, Юн-Гао (2013), «О счетной функции последовательностей Стэнли», Publicationes Mathematicae Debrecen , 82 (1): 91–95, doi : 10.5486/PMD.2013.5286 , MR  3034370
8. Ролник, Дэвид; Венкатарамана, Правин С. (2015), «О росте последовательностей Стэнли», Дискретная математика , 338 (11): 1928–1937, arXiv : 1408.4710 , doi : 10.1016/j.disc.2015.04.006, MR  3357778, S2CID  2568329
9. Эрдёш, Пол ; Туран, Пол (1936), «О некоторых последовательностях целых чисел» (PDF) , Журнал Лондонского математического общества , 11 (4): 261–264, doi :10.1112/jlms/s1-11.4.261, MR  1574918

Дальнейшее чтение

• Мой, Ричард А. (2017), Последовательности Стэнли с нечетными символами , arXiv : 1707.02037
• Мой, Ричард А.; Ролник, Дэвид (2016), «Новые структуры в последовательностях Стэнли», Дискретная математика , 339 (2): 689–698, arXiv : 1502.06013 , doi : 10.1016/j.disc.2015.10.017, MR  3431382, S2CID  6660477
• Ролник, Дэвид (2017), «О классификации последовательностей Стэнли», Европейский журнал комбинаторики , 59 : 51–70, arXiv : 1408.1940 , doi : 10.1016/j.ejc.2016.06.004 , MR  3546902
• Sawhney, Mehtaab (2017), Значения символов последовательностей Стэнли , arXiv : 1706.05444