Последовательность Стэнли - Stanley sequence

В математике Последовательность Стэнли является целочисленная последовательность созданный жадный алгоритм который выбирает члены последовательности, чтобы избежать арифметические прогрессии. Если ${\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 )

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

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

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

Скорость роста

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

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

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

История

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

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

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

Рекомендации

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

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

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