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

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

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

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

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

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

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

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

Темпы роста

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

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

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

История

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

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

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

Ссылки

^ Jump up to: Перейти обратно: ^а ^б ^с ^д Одлизко, А.М. ; Стэнли, РП (январь 1978 г.), OdlSta-78 (PDF)
^ Слоан, Нью-Джерси (ред.). «Последовательность A005836» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
^ Аллуш, Жан-Поль; Шалит, Джеффри (1992), «Кольцо $k$ -регулярные последовательности», Theoretical Computer Science , 98 (2): 163–197, CiteSeerX 10.1.1.8.6912 , doi : 10.1016/0304-3975(92)90001-V , MR 1166363. См. пример 26, стр. 192.
^ Гупта, Хансрадж (1978), «Степени 2 и суммы различных степеней 3», Публикации Белградского университета, серия факультета электротехники, математики и физики (602–633): 151–158 (1979), MR 0580438
^ Jump up to: Перейти обратно: ^а ^б Эрдеш, П .; Лев, В.; Рози, Г.; Шандор, К.; Саркози, А. (1999), «Жадный алгоритм, арифметические прогрессии, суммы подмножеств и делимость», Discrete Mathematics , 200 (1–3): 119–135, doi : 10.1016/S0012-365X(98)00385-9 , MR 1692285
^ Мой, Ричард А. (2011), «О росте счетной функции последовательностей Стэнли», Discrete Mathematics , 311 (7): 560–562, arXiv : 1101.0022 , doi : 10.1016/j.disc.2010.12.019 , МР 2765623 , S2CID 11040813
^ Дай, Ли-Ся; Чен, Юн-Гао (2013), «О счетной функции последовательностей Стэнли», Publicationes Mathematicae Debrecen , 82 (1): 91–95, doi : 10.5486/PMD.2013.5286 , MR 3034370
^ Рольник, Дэвид; Венкатарамана, Правин С. (2015), «О росте последовательностей Стэнли», Discrete Mathematics , 338 (11): 1928–1937, arXiv : 1408.4710 , doi : 10.1016/j.disc.2015.04.006 , MR 3357778 , S2CID 2568329
^ Эрдеш, Пол ; Туран, Пол (1936), «О некоторых последовательностях целых чисел» (PDF) , Журнал Лондонского математического общества , 11 (4): 261–264, doi : 10.1112/jlms/s1-11.4.261 , MR 1574918

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

Мой, Ричард А. (2017), Последовательности Стэнли с нечетным символом , arXiv : 1707.02037
Мой, Ричард А.; Рольник, Дэвид (2016), «Новые структуры в последовательностях Стэнли», Discrete Mathematics , 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
Сони, Мехтааб (2017), Значения символов последовательностей Стэнли , arXiv : 1706.05444

[os-1] Jump up to: Перейти обратно: ^а ^б ^с ^д Одлизко, А.М. ; Стэнли, РП (январь 1978 г.), OdlSta-78 (PDF)

[2] Слоан, Нью-Джерси (ред.). «Последовательность A005836» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.

[as-3] Аллуш, Жан-Поль; Шалит, Джеффри (1992), «Кольцо $k$ -регулярные последовательности», Theoretical Computer Science , 98 (2): 163–197, CiteSeerX 10.1.1.8.6912 , doi : 10.1016/0304-3975(92)90001-V , MR 1166363. См. пример 26, стр. 192.

[g-4] Гупта, Хансрадж (1978), «Степени 2 и суммы различных степеней 3», Публикации Белградского университета, серия факультета электротехники, математики и физики (602–633): 151–158 (1979), MR 0580438

[elrss-5] Jump up to: Перейти обратно: ^а ^б Эрдеш, П .; Лев, В.; Рози, Г.; Шандор, К.; Саркози, А. (1999), «Жадный алгоритм, арифметические прогрессии, суммы подмножеств и делимость», Discrete Mathematics , 200 (1–3): 119–135, doi : 10.1016/S0012-365X(98)00385-9 , MR 1692285

[m-6] Мой, Ричард А. (2011), «О росте счетной функции последовательностей Стэнли», Discrete Mathematics , 311 (7): 560–562, arXiv : 1101.0022 , doi : 10.1016/j.disc.2010.12.019 , МР 2765623 , S2CID 11040813

[dc-7] Дай, Ли-Ся; Чен, Юн-Гао (2013), «О счетной функции последовательностей Стэнли», Publicationes Mathematicae Debrecen , 82 (1): 91–95, doi : 10.5486/PMD.2013.5286 , MR 3034370

[rv-8] Рольник, Дэвид; Венкатарамана, Правин С. (2015), «О росте последовательностей Стэнли», Discrete Mathematics , 338 (11): 1928–1937, arXiv : 1408.4710 , doi : 10.1016/j.disc.2015.04.006 , MR 3357778 , S2CID 2568329

[et-9] Эрдеш, Пол ; Туран, Пол (1936), «О некоторых последовательностях целых чисел» (PDF) , Журнал Лондонского математического общества , 11 (4): 261–264, doi : 10.1112/jlms/s1-11.4.261 , MR 1574918

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]