Sekwencja Stanleya

W matematyce sekwencja Stanleya jest sekwencją całkowitą generowaną przez zachłanny algorytm , który wybiera elementy sekwencji, aby uniknąć postępów arytmetycznych . Jeśli $skończonym$ zbiorem nieujemnych liczb całkowitych, na których żadne trzy elementy nie tworzą postępu arytmetycznego (to znaczy zbiór Salem-Spencer ), to sekwencja Stanleya wygenerowana z zaczyna się od $displaystyle S}$ elementy ${\ Displaystyle S}$ , w posortowanej kolejności, a następnie wielokrotnie wybiera każdy kolejny element ciągu jako liczbę większą od już wybranych liczb i nie tworzy z nimi żadnego trzyczłonowego ciągu arytmetycznego. Sekwencje te zostały nazwane na cześć Richarda P. Stanleya .

Sekwencja binarno-trójskładnikowa

Sekwencja Stanleya rozpoczynająca się od zbioru pustego składa się z tych liczb, których trójskładnikowe reprezentacje mają tylko cyfry 0 i 1. Oznacza to, że zapisane trójskładnikowo wyglądają jak liczby binarne . Te liczby są

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

Dzięki swojej konstrukcji jako sekwencji Stanleya, sekwencja ta jest leksykograficznie pierwszą sekwencją wolną od postępu arytmetycznego . Jego elementami są sumy różnych potęg trzech , liczby takie, że $dwumianu$ wynosi 1 mod 3, oraz liczby, których $zrównoważona$ trójskładnikowa jest taka sama jak ich trójskładnikowa reprezentacja.

Konstrukcja tego ciągu z liczb trójskładnikowych jest analogiczna do konstrukcji ciągu Mosera – de Bruijna , ciągu liczb, których reprezentacje o podstawie 4 mają tylko cyfry 0 i 1, oraz konstrukcji zbioru Cantora jako podzbioru liczby rzeczywiste w przedziale , których $trójskładnikowe$ reprezentacje wykorzystują tylko cyfry 0 i 2. Bardziej ogólnie, są to regularne należące do klasy sekwencji całkowitych zdefiniowanych przez a liniowa relacja powtarzalności z mnożnikiem 2.

Ta sekwencja zawiera trzy potęgi dwójki : 1, 4 i 256 = 3 ⁵ + 3 ² + 3 + 1. Paul Erdős przypuszczał, że są to jedyne potęgi dwójki, które zawiera.

Tempo wzrostu

Andrew Odlyzko i Richard P. Stanley zauważyli, że liczba elementów do pewnego progu ${$ sekwencji binarno-trójskładnikowej oraz w innych sekwencjach Stanleya, począwszy od $\ displaystyle \ {0,3} ^ {k} \}}$ lub ${\ Displaystyle \ {0,2 \ cdot 3 ^ {k} \}}$ rośnie proporcjonalnie do ${\ Displaystyle n ^ {\ log _ {2}3} \ ok n ^ {0,631}}$ . W przypadku innych zestawów początkowych sekwencje Stanleya, które uważali, wydawały się rosnąć bardziej nieregularnie $jeszcze$ Na przykład pierwszym nieregularnym przypadkiem jest , który generuje sekwencję ${\ 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, ... (sekwencja A005487 w OIS )

${\ Displaystyle O {\ bigl (} {\ sqrt {n \ log n}} \bigr )}}$ że w takich przypadkach liczba elementów do dowolnego progu wynosi $)$ . Oznacza to, że istnieje dychotomia w tempie wzrostu sekwencji Stanleya między sekwencjami o podobnym wzroście do sekwencji binarno-trójskładnikowej i innymi o znacznie mniejszym tempie wzrostu; zgodnie z tym przypuszczeniem nie powinno być sekwencji Stanleya o średnim wzroście.

Moy udowodnił, że sekwencje Stanleya nie mogą rosnąć znacznie wolniej niż przypuszczalna granica dla sekwencji powolnego wzrostu. Każda sekwencja Stanleya ma $elementy$ do $displaystyle n$ } Dokładniej Moy wykazał, że dla każdej takiej sekwencji, każdej $\ varepsilon > 0}$ dużej liczby elementów wynosi co najmniej $> {\ displaystyle$${\ Displaystyle ({\ sqrt {2}} - \ varepsilon) {\ sqrt {n}}}$ . Późniejsi autorzy poprawili stały czynnik w tej granicy i udowodnili, że dla sekwencji Stanleya, które rosną jako ${\ Displaystyle n ^ {\ log _ {2}3}}$ stały współczynnik ich tempa wzrostu może być dowolny racjonalny liczba, której mianownikiem jest potęga trójki.

Historia

Odmiana sekwencji binarno-trójskładnikowej (z dodaniem jednego do każdego elementu) została rozważona w 1936 roku przez Paula Erdősa i Pála Turána , którzy zauważyli, że nie ma ona trzyczłonowej progresji arytmetycznej i przypuszczali (niepoprawnie), że była to najgęstsza możliwa sekwencja bez postępu arytmetycznego.

W niepublikowanej pracy z Andrew Odlyzko w 1978 roku Richard P. Stanley eksperymentował z algorytmem zachłannym w celu generowania sekwencji wolnych od progresji. Sekwencje, które badali, były dokładnie $sekwencjami$ dla

Sekwencje Stanleya zostały nazwane i uogólnione na inne zestawy początkowe niż w artykule opublikowanym w 1999 roku przez Erdősa (pośmiertnie) wraz $autorami$

Dalsza lektura

• Moy, Richard A. (2017), sekwencje Stanleya z nieparzystym charakterem , arXiv : 1707.02037
•    Moy, Richard A.; Rolnick, David (2016), „Nowe struktury w sekwencjach Stanleya” , Matematyka dyskretna , 339 (2): 689–698, arXiv : 1502,06013 , doi : 10,1016/j.disc.2015.10.017 , MR 3431382 , S2CID 6660477
•   Rolnick, David (2017), „O klasyfikacji sekwencji Stanleya”, European Journal of Combinatorics , 59 : 51–70, doi : 10.1016/j.ejc.2016.06.004 , MR 3546902
• Sawhney, Mehtaab (2017), Wartości znaków sekwencji Stanleya , arXiv : 1706,05444