Stanley sequence

In mathematics, a Stanley sequence is an integer sequence generated by a greedy algorithm that chooses the sequence members to avoid arithmetic progressions. If $S$ is a finite set of non-negative integers on which no three elements form an arithmetic progression (that is, a Salem–Spencer set), then the Stanley sequence generated from $S$ starts from the elements of $S$ , in sorted order, and then repeatedly chooses each successive element of the sequence to be a number that is larger than the already-chosen numbers and does not form any three-term arithmetic progression with them. These sequences are named after Richard P. Stanley.

Binary–ternary sequence

The Stanley sequence starting from the empty set consists of those numbers whose ternary representations have only the digits 0 and 1.^[1] That is, when written in ternary, they look like binary numbers. These numbers are

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

By their construction as a Stanley sequence, this sequence is the lexicographically first arithmetic-progression-free sequence. Its elements are the sums of distinct powers of three, the numbers $n$ such that the $n$ th central binomial coefficient is 1 mod 3, and the numbers whose balanced ternary representation is the same as their ternary representation.^[2]

The construction of this sequence from the ternary numbers is analogous to the construction of the Moser–de Bruijn sequence, the sequence of numbers whose base-4 representations have only the digits 0 and 1, and the construction of the Cantor set as the subset of real numbers in the interval $[0,1]$ whose ternary representations use only the digits 0 and 2. More generally, they are a 2-regular sequence, one of a class of integer sequences defined by a linear recurrence relation with multiplier 2.^[3]

This sequence includes three powers of two: 1, 4, and 256 = 3⁵ + 3² + 3 + 1. Paul Erdős conjectured that these are the only powers of two that it contains.^[4]

Growth rate

Andrew Odlyzko and Richard P. Stanley observed that the number of elements up to some threshold $n$ in the binary–ternary sequence, and in other Stanley sequences starting from $\{0,3^{k}\}$ or $\{0,2\cdot 3^{k}\}$ , grows proportionally to $n^{\log _{2}3}\approx n^{0.631}$ . For other starting sets $\{0,s\}$ the Stanley sequences that they considered appeared to grow more erratically but even more sparsely.^[1] For instance, the first irregular case is $s=4$ , which generates the sequence

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

Odlyzko and Stanley conjectured that in such cases the number of elements up to any threshold $n$ is $O{\bigl (}{\sqrt {n\log n}}{\bigr )}$ . That is, there is a dichotomy in the growth rate of Stanley sequences between the ones with similar growth to the binary–ternary sequence and others with a much smaller growth rate; according to this conjecture, there should be no Stanley sequences with intermediate growth.^[1]^[5]

Moy proved that Stanley sequences cannot grow significantly more slowly than the conjectured bound for the sequences of slow growth. Every Stanley sequence has $\Omega {\bigl (}{\sqrt {n}}{\bigr )}$ elements up to $n$ . More precisely Moy showed that, for every such sequence, every $\varepsilon >0$ , and all sufficiently large $n$ , the number of elements is at least $({\sqrt {2}}-\varepsilon ){\sqrt {n}}$ .^[6] Later authors improved the constant factor in this bound,^[7] and proved that for Stanley sequences that grow as $n^{\log _{2}3}$ the constant factor in their growth rates can be any rational number whose denominator is a power of three.^[8]

History

A variation of the binary–ternary sequence (with one added to each element) was considered in 1936 by Paul Erdős and Pál Turán, who observed that it has no three-term arithmetic progression and conjectured (incorrectly) that it was the densest possible sequence with no arithmetic progression.^[9]

In unpublished work with Andrew Odlyzko in 1978, Richard P. Stanley experimented with the greedy algorithm to generate progression-free sequences. The sequences they studied were exactly the Stanley sequences for the initial sets $\{0,s\}$ .^[1]

Stanley sequences were named, and generalized to other starting sets than $\{0,s\}$ , in a paper published in 1999 by Erdős (posthumously) with four other authors.^[5]

References

^ ^a ^b ^c ^d Odlyzko, A. M.; Stanley, R. P. (January 1978), OdlSta-78 (PDF)
^ Sloane, N. J. A. (ed.). "Sequence A005836". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ Allouche, Jean-Paul; Shallit, Jeffrey (1992), "The ring of $k$ -regular sequences", Theoretical Computer Science, 98 (2): 163–197, CiteSeerX 10.1.1.8.6912, doi:10.1016/0304-3975(92)90001-V, MR 1166363. See Example 26, p. 192.
^ Gupta, Hansraj (1978), "Powers of 2 and sums of distinct powers of 3", Univerzitet u Beogradu Publikacije Elektrotehničkog Fakulteta, Serija Matematika i Fizika (602–633): 151–158 (1979), MR 0580438
^ ^a ^b Erdős, P.; Lev, V.; Rauzy, G.; Sándor, C.; Sárközy, A. (1999), "Greedy algorithm, arithmetic progressions, subset sums and divisibility", Discrete Mathematics, 200 (1–3): 119–135, doi:10.1016/S0012-365X(98)00385-9, MR 1692285
^ Moy, Richard A. (2011), "On the growth of the counting function of Stanley sequences", Discrete Mathematics, 311 (7): 560–562, arXiv:1101.0022, doi:10.1016/j.disc.2010.12.019, MR 2765623, S2CID 11040813
^ Dai, Li-Xia; Chen, Yong-Gao (2013), "On the counting function of Stanley sequences", Publicationes Mathematicae Debrecen, 82 (1): 91–95, doi:10.5486/PMD.2013.5286, MR 3034370
^ Rolnick, David; Venkataramana, Praveen S. (2015), "On the growth of Stanley sequences", Discrete Mathematics, 338 (11): 1928–1937, arXiv:1408.4710, doi:10.1016/j.disc.2015.04.006, MR 3357778, S2CID 2568329
^ Erdős, Paul; Turán, Paul (1936), "On some sequences of integers" (PDF), Journal of the London Mathematical Society, 11 (4): 261–264, doi:10.1112/jlms/s1-11.4.261, MR 1574918

Binary–ternary sequence

Growth rate

History

References

Further reading