On the growth of Stanley sequences

Abstract

A set is said to be \emph{3-free} if no three elements form an arithmetic progression. Given a 3-free set $A$ of integers $0=a_0<a_1<\cdots <a_t$, the \emph{Stanley sequence} $S(A)=\{a_n\}$ is defined using the greedy algorithm: For each successive $n>t$, we pick the smallest possible $a_n$ so that $\{a_0,a_1,\dots ,a_n\}$ is 3-free and increasing. Work by Odlyzko and Stanley indicates that Stanley sequences may be divided into two classes. Sequences of Type 1 are highly structured and satisfy $\alpha n^{{\log }_{2}3}/2\le a_n\le \alpha n^{{\log }_{2}3}$, for some constant $\alpha$, while those of Type 2 are chaotic and satisfy $\Theta (n^2/\log n)$. In this paper, we consider the possible values for $\alpha$ in the growth of Type 1 Stanley sequences. Whereas Odlyzko and Stanley assumed $\alpha =1$, we show that $\alpha$ can be any rational number which is at least 1 and for which the denominator, in lowest terms, is a power of 3.

10 pages

References in corpus (1)

• On the classification of Stanley sequences