{{Short description|Mathematical sequence involving arithmetic progressions}} In mathematics, a '''Stanley sequence''' is an integer sequence generated by a greedy algorithm that chooses the sequence members to avoid arithmetic progressions. If <math>S</math> 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 <math>S</math> starts from the elements of <math>S</math>, 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.{{r|os}} 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, ... {{OEIS|A005836}}
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 <math>n</math> such that the <math>n</math>th central binomial coefficient is 1 mod 3, and the numbers whose balanced ternary representation is the same as their ternary representation.<ref>{{cite OEIS|A005836}}</ref>
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 <math>[0,1]</math> 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.{{r|as}}
This sequence includes three powers of two: 1, 4, and 256 = 3<sup>5</sup> + 3<sup>2</sup> + 3 + 1. Paul Erdős conjectured that these are the only powers of two that it contains.{{r|g}}
==Growth rate== Andrew Odlyzko and Richard P. Stanley observed that the number of elements up to some threshold <math>n</math> in the binary–ternary sequence, and in other Stanley sequences starting from <math>\{0,3^k\}</math> or <math>\{0,2\cdot 3^k\}</math>, grows proportionally to <math>n^{\log_2 3}\approx n^{0.631}</math>. For other starting sets <math>\{0,s\}</math> the Stanley sequences that they considered appeared to grow more erratically but even more sparsely.{{r|os}} For instance, the first irregular case is <math>s=4</math>, 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, ... {{OEIS|A005487}} Odlyzko and Stanley conjectured that in such cases the number of elements up to any threshold <math>n</math> is <math>O\bigl(\sqrt{n\log n}\bigr)</math>. 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.{{r|os|elrss}}
Moy proved that Stanley sequences cannot grow significantly more slowly than the conjectured bound for the sequences of slow growth. Every Stanley sequence has <math>\Omega\bigl(\sqrt{n}\bigr)</math> elements up to <math>n</math>. More precisely Moy showed that, for every such sequence, every <math>\varepsilon>0</math>, and all sufficiently large <math>n</math>, the number of elements is at least <math>(\sqrt 2 - \varepsilon)\sqrt n</math>.{{r|m}} Relatedly, Dai and Chen proved that the number of elements is at least <math>1.77 \sqrt n</math> for infinitely many <math>n</math>.{{r|dc}} Rolnick and Venkataramana also proved that for Stanley sequences that grow as <math>n^{\log_2 3}</math> the constant factor in their growth rates can be any rational number whose denominator is a power of three.{{r|rv}}
==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.{{r|et}}
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 <math>\{0,s\}</math>.{{r|os}}
Stanley sequences were named, and generalized to other starting sets than <math>\{0,s\}</math>, in a paper published in 1999 by Erdős (posthumously) with four other authors.{{r|elrss}}
==References== <references>
<ref name=as>{{citation | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | citeseerx = 10.1.1.8.6912 | doi = 10.1016/0304-3975(92)90001-V | issue = 2 | journal = Theoretical Computer Science | mr = 1166363 | pages = 163–197 | title = The ring of <math>k</math>-regular sequences | volume = 98 | year = 1992}}. See Example 26, p. 192.</ref>
<ref name=dc>{{citation | last1 = Dai | first1 = Li-Xia | last2 = Chen | first2 = Yong-Gao | doi = 10.5486/PMD.2013.5286 | issue = 1 | journal = Publicationes Mathematicae Debrecen | mr = 3034370 | pages = 91–95 | title = On the counting function of Stanley sequences | volume = 82 | year = 2013| doi-access = free }}</ref>
<ref name=elrss>{{citation | last1 = Erdős | first1 = P. | author1-link = Paul Erdős | last2 = Lev | first2 = V. | last3 = Rauzy | first3 = G. | last4 = Sándor | first4 = C. | last5 = Sárközy | first5 = A. | doi = 10.1016/S0012-365X(98)00385-9 | issue = 1–3 | journal = Discrete Mathematics | mr = 1692285 | pages = 119–135 | title = Greedy algorithm, arithmetic progressions, subset sums and divisibility | volume = 200 | year = 1999| doi-access = free }}</ref>
<ref name=et>{{citation | last1 = Erdős | first1 = Paul | author1-link = Paul Erdős | last2 = Turán | first2 = Paul | author2-link = Pál Turán | doi = 10.1112/jlms/s1-11.4.261 | issue = 4 | journal = Journal of the London Mathematical Society | mr = 1574918 | pages = 261–264 | title = On some sequences of integers | url = https://users.renyi.hu/~p_erdos/1936-05.pdf | volume = 11 | year = 1936}}</ref>
<ref name=g>{{citation | last = Gupta | first = Hansraj | issue = 602–633 | journal = Univerzitet u Beogradu Publikacije Elektrotehničkog Fakulteta, Serija Matematika i Fizika | mr = 580438 | pages = 151–158 (1979) | title = Powers of 2 and sums of distinct powers of 3 | year = 1978}}</ref>
<ref name=m>{{citation | last = Moy | first = Richard A. | doi = 10.1016/j.disc.2010.12.019 | issue = 7 | journal = Discrete Mathematics | mr = 2765623 | pages = 560–562 | title = On the growth of the counting function of Stanley sequences | volume = 311 | year = 2011| arxiv = 1101.0022 | s2cid = 11040813 }}</ref>
<ref name=os>{{citation | last1 = Odlyzko | first1 = A. M. | author1-link = Andrew Odlyzko | last2 = Stanley | first2 = R. P. | author2-link = Richard P. Stanley | date = January 1978 | title = OdlSta-78 | url = https://www.dtc.umn.edu/~odlyzko/unpublished/greedy.sequence.pdf}}</ref>
<ref name=rv>{{citation | last1 = Rolnick | first1 = David | last2 = Venkataramana | first2 = Praveen S. | doi = 10.1016/j.disc.2015.04.006 | issue = 11 | journal = Discrete Mathematics | mr = 3357778 | pages = 1928–1937 | title = On the growth of Stanley sequences | volume = 338 | year = 2015| arxiv = 1408.4710 | s2cid = 2568329 }}</ref>
</references>
==Further reading== *{{citation | last = Moy | first = Richard A. | arxiv = 1707.02037 | title = Stanley sequences with odd character | year = 2017}} *{{citation | last1 = Moy | first1 = Richard A. | last2 = Rolnick | first2 = David | doi = 10.1016/j.disc.2015.10.017 | issue = 2 | journal = Discrete Mathematics | mr = 3431382 | pages = 689–698 | title = Novel structures in Stanley sequences | volume = 339 | year = 2016| arxiv = 1502.06013 | s2cid = 6660477 }} *{{citation | last = Rolnick | first = David | doi = 10.1016/j.ejc.2016.06.004 | journal = European Journal of Combinatorics | mr = 3546902 | pages = 51–70 | title = On the classification of Stanley sequences | volume = 59 | year = 2017| doi-access = free | arxiv = 1408.1940 }} *{{citation | last = Sawhney | first = Mehtaab | arxiv = 1706.05444 | title = Character Values of Stanley Sequences | year = 2017}}
Category:Integer sequences