Последовательность Стэнли - Википедия - 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 п ^ { журнал _ {2} 3} приблизительно п ^ {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 О { bigl (} { sqrt {п журнал п}} { 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 п ^ { журнал _ {2} 3}}$ постоянным фактором их темпов роста может быть любое рациональное число, знаменатель которого является степенью трех.^[8]

История

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

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

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

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

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

• Мой, Ричард А. (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