On the classification of Stanley sequences

DOI10.1016/J.EJC.2016.06.004zbMATH Open1390.11054arXiv1408.1940OpenAlexW2299314452MaRDI QIDQ326649FDOQ326649

Authors: David Rolnick 

Publication date: 12 October 2016

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: An integer sequence is said to be 3-free if no three elements form an arithmetic progression. Following the greedy algorithm, the Stanley sequence $S(a_0,a_1,ldots,a_k)$ is defined to be the 3-free sequence $a_n$ having initial terms $a_0,a_1,ldots,a_k$ and with each subsequent term $a_n>a_{n-1}$ chosen minimally such that the 3-free condition is not violated. Odlyzko and Stanley conjectured that Stanley sequences divide into two classes based on asymptotic growth patterns, with one class of highly structured sequences satisfying $a_{n}approxTheta(n^{lo{g}_{2}3})$ and another class of seemingly chaotic sequences obeying $a_n=Theta(n^2/logn)$. We propose a rigorous definition of regularity in Stanley sequences based on local structure rather than asymptotic behavior and show that our definition implies the corresponding asymptotic property proposed by Odlyzko and Stanley. We then construct many classes of regular Stanley sequences, which include as special cases all such sequences previously identified. We show how two regular sequences may be combined into another regular sequence, and how parts of a Stanley sequence may be translated while preserving regularity. Finally, we demonstrate that certain Stanley sequences possess proper subsets that are also Stanley sequences, a situation that appears previously to have been assumed impossible.

Full work available at URL: https://arxiv.org/abs/1408.1940

Recommendations

• On the growth of Stanley sequences
• Novel structures in Stanley sequences
• Stanley sequences with odd character
• On the growth of the counting function of Stanley sequences
• On generalized Stanley sequences

Mathematics Subject Classification ID

Other combinatorial number theory (11B75)

Cites Work

• On Certain Sets of Integers
• Greedy algorithm, arithmetic progressions, subset sums and divisibility
• A note on maximal progression-free sets
• Irregular Sets of Integers Generated by the Greedy Algorithm
• On the growth of the counting function of Stanley sequences
• On Roth's theorem on progressions

Cited In (7)

• Two classes of modular \(p\)-Stanley sequences
• Stanley sequences with odd character
• On the counting function of Stanley sequences
• Novel structures in Stanley sequences
• On the growth of the counting function of Stanley sequences
• Characters of independent Stanley sequences
• On the growth of Stanley sequences

This page was built for publication: On the classification of Stanley sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q326649)