Stanleyova sekvence - Stanley sequence - Wikipedia

V matematice, a Stanleyova sekvence je celočíselná sekvence generované a chamtivý algoritmus který vybírá členy sekvence, kterým se má vyhnout aritmetické průběhy. Li ${ displaystyle S}$ je konečná množina nezáporných celých čísel, na nichž žádné tři prvky netvoří aritmetický postup (tj. Sada Salem – Spencer ), poté Stanleyova sekvence vygenerovaná z ${ displaystyle S}$ začíná od prvků ${ displaystyle S}$, v seřazeném pořadí, a poté opakovaně zvolí, aby každý následující prvek sekvence byl číslem, které je větší než již zvolená čísla a netvoří s nimi žádný třídobý aritmetický postup. Tyto sekvence jsou pojmenovány po Richard P. Stanley.

Binární – ternární sekvence

Sekvence Stanley začínající od prázdné sady se skládá z těch čísel, jejichž ternární reprezentace mít pouze číslice 0 a 1.^[1] To znamená, že když jsou psány ternárně, vypadají binární čísla. Tato čísla jsou

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (sekvence A005836 v OEIS )

Konstrukcí jako Stanleyho sekvence je tato sekvence lexikograficky za prvé sekvence bez aritmetického postupu. Jeho prvky jsou součty odlišných pravomoci tří, čísla ${ displaystyle n}$ takové, že ${ displaystyle n}$th centrální binomický koeficient je 1 mod 3 a čísla, jejichž vyvážená ternární reprezentace je stejná jako jejich ternární reprezentace.^[2]

Konstrukce této posloupnosti z ternárních čísel je analogická s konstrukcí Moser – de Bruijnova sekvence posloupnost čísel, jejichž reprezentace základny-4 mají pouze číslice 0 a 1, a konstrukce Cantor set jako podmnožina reálných čísel v intervalu ${ displaystyle [0,1]}$ jehož ternární reprezentace používají pouze číslice 0 a 2. Obecněji jsou to a 2-pravidelná sekvence, jedna ze třídy celočíselných sekvencí definovaných lineárně relace opakování s multiplikátorem 2.^[3]

Tato sekvence zahrnuje tři pravomoci dvou: 1, 4 a 256 = 3⁵ + 3² + 3 + 1. Paul Erdős domníval se, že to jsou jediné síly dvou, které obsahuje.^[4]

Tempo růstu

Andrew Odlyzko a Richard P. Stanley zjistil, že počet prvků do určité prahové hodnoty ${ displaystyle n}$ v binární – ternární sekvenci a v dalších Stanleyových sekvencích počínaje od ${ displaystyle {0,3 ^ {k} }}$ nebo ${ displaystyle {0,2 cdot 3 ^ {k} }}$, roste úměrně k ${ displaystyle n ^ { log _ {2} 3} přibližně n ^ {0,631}}$. Pro ostatní startovní sady ${ displaystyle {0, s }}$ Stanleyho sekvence, které považovali za, se zdálo, že rostou nepravidelněji, ale ještě řídčeji.^[1] Například první nepravidelný případ je ${ displaystyle s = 4}$, který generuje sekvenci

0, 4, 5, 7, 11, 12, 16, 23, 26, 31, 33, 37, 38, 44, 49, 56, 73, 78, 80, 85, 95, 99, ... (sekvence A005487 v OEIS )

Odlyzko a Stanley se domnívali, že v takových případech je počet prvků až po jakoukoli prahovou hodnotu ${ displaystyle n}$ je ${ displaystyle O { bigl (} { sqrt {n log n}} { bigr)}}$. To znamená, že v rychlosti růstu stanleyských sekvencí existuje dichotomie mezi sekvencemi s podobným růstem jako binární-ternární sekvence a ostatními s mnohem menší rychlostí růstu; podle této domněnky by neměly existovat žádné Stanleyho sekvence se středním růstem.^[1][5]

Moy dokázal, že Stanleyho sekvence nemohou růst podstatně pomaleji než domnělá hranice pro sekvence pomalého růstu. Každá Stanleyova sekvence má ${ displaystyle Omega { bigl (} { sqrt {n}} { bigr)}}$ prvky až ${ displaystyle n}$. Přesněji Moy ukázal, že pro každou takovou sekvenci každý ${ displaystyle varepsilon> 0}$a všechny dostatečně velké ${ displaystyle n}$, počet prvků je alespoň ${ displaystyle ({ sqrt {2}} - varepsilon) { sqrt {n}}}$.^[6] Pozdější autoři vylepšili konstantní faktor v této vazbě,^[7]a dokázal, že pro Stanley sekvence, které rostou jako ${ displaystyle n ^ { log _ {2} 3}}$ konstantním faktorem v jejich rychlostech růstu může být jakékoli racionální číslo, jehož jmenovatelem je síla tří.^[8]

Dějiny

O variaci binární-ternární sekvence (s jednou přidanou ke každému prvku) uvažoval v roce 1936 Paul Erdős a Pál Turán, který poznamenal, že nemá třídobý aritmetický postup, a domníval se (nesprávně), že se jedná o nejhustší možnou sekvenci bez aritmetického postupu.^[9]

V nepublikované práci s Andrew Odlyzko v roce 1978, Richard P. Stanley experimentovali s chamtivým algoritmem, aby generovali sekvence bez progrese. Sekvence, které studovali, byly přesně Stanleyovy sekvence pro počáteční sady ${ displaystyle {0, s }}$.^[1]

Stanleyovy sekvence byly pojmenovány a zobecněny na jiné výchozí sady než ${ displaystyle {0, s }}$, v dokumentu publikovaném v roce 1999 Erdősem (posmrtně) se čtyřmi dalšími autory.^[5]

Reference

Další čtení

• Moy, Richard A. (2017), Stanleyho sekvence s lichým charakterem, arXiv:1707.02037
• Moy, Richard A .; Rolnick, David (2016), „Nové struktury ve Stanleyho sekvencích“, Diskrétní matematika, 339 (2): 689–698, arXiv:1502.06013, doi:10.1016 / j.disc.2015.10.017, PAN  3431382
• Rolnick, David (2017), „O klasifikaci Stanleyových sekvencí“, European Journal of Combinatorics, 59: 51–70, doi:10.1016 / j.ejc.2016.06.004, PAN  3546902
• Sawhney, Mehtaab (2017), Hodnoty znaků Stanleyho sekvencí, arXiv:1706.05444