Salem–Spencer set

Jump to navigation Jump to search
For the set {1, 2, 4, 5, 10, 11, 13, 14}, all midpoints of two elements (the 28 yellow points) land outside the set, so no three elements can form an arithmetic progression

In mathematics, and in particular in arithmetic combinatorics, a Salem-Spencer set is a set of numbers no three of which form an arithmetic progression. Salem–Spencer sets are also called 3-AP-free sequences or progression-free sets. They are named after Raphaël Salem and Donald C. Spencer, who showed in 1942 that dense Salem–Spencer sets exist.

Examples

For ${\displaystyle k=1,2,\dots }$ the smallest values of ${\displaystyle n}$ such that the numbers from ${\displaystyle 1}$ to ${\displaystyle n}$ have a ${\displaystyle k}$-element Salem-Spencer set are

1, 2, 4, 5, 9, 11, 13, 14, 20, 24, 26, 30, 32, 36, ... (sequence A065825 in the OEIS)

For instance, among the numbers from 1 to 14, the eight numbers

{1, 2, 4, 5, 10, 11, 13, 14}

form the unique largest Salem-Spencer set.[1]

This example is shifted by adding one to the elements of an infinite Salem–Spencer set, the Stanley sequence

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

of numbers that, when written as a ternary number, use only the digits 0 and 1. This sequence is the lexicographically first infinite Salem–Spencer set.[2] Another infinite Salem–Spencer set is given by the cubes

0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, ... (sequence A000578 in the OEIS)

It is a theorem of Leonhard Euler that no three cubes are in arithmetic progression.[3]

Density

In 1942, Salem and Spencer published a proof that the integers in the range from ${\displaystyle 1}$ to ${\displaystyle n}$ have large Salem–Spencer sets, of size ${\displaystyle n/e^{O(\log n/\log \log n)}}$.[4] This bound disproved a conjecture of Paul Erdős and Pál Turán that the size of such a set could be at most ${\displaystyle n^{1-\delta }}$ for some ${\displaystyle \delta >0}$.[1][5] The bound was improved by Felix Behrend in 1946 to ${\displaystyle n/e^{O({\sqrt {\log n}})}}$.[6]

In 1952, Klaus Roth proved that the size of a Salem-Spencer set must be ${\displaystyle O(n/\log \log n)}$.[7] This is a special case of Szemerédi's theorem on the density of sets of integers that avoid longer arithmetic progressions.[1] After several additional improvements to Roth's theorem,[8][9][10][11] the size of a Salem–Spencer set has been proven to be ${\displaystyle O{\bigl (}n(\log \log n)^{4}/\log n{\bigr )}}$.[12]

Construction

A simple construction for a Salem–Spencer set (of size considerably smaller than Behrend's bound) is to choose the ternary numbers that use only the digits 0 and 1, not 2. Such a set must be progression-free, because if two of its elements ${\displaystyle x}$ and ${\displaystyle y}$ are the first and second members of an arithmetic progression, the third member must have the digit two at the position of the least significant digit where ${\displaystyle x}$ and ${\displaystyle y}$ differ.[1] The illustration shows a set of this form, for the three-digit ternary numbers (shifted by one to make the smallest element 1 instead of 0).

Behrend's construction uses a similar idea, for a larger odd radix ${\displaystyle 2d-1}$. His set consists of the numbers whose digits are restricted to the range from ${\displaystyle 0}$ to ${\displaystyle d-1}$ (so that addition of these numbers has no carries), with the extra constraint that the sum of the squares of the digits is some chosen value ${\displaystyle k}$.[6] If the digits of each number are thought of as coordinates of a vector, this constraint describes a sphere in the resulting vector space, and by convexity the average of two distinct values on this sphere will be interior to the sphere rather than on it.[13] Therefore, if two elements of Behrend's set are the endpoints of an arithmetic progression, the middle value of the progression (their average) will not be in the set. Thus, the resulting set is progression-free.[6]

With a careful choice of ${\displaystyle d}$, and a choice of ${\displaystyle k}$ as the most frequently-occurring sum of squares of digits, Behrend achieves his bound.[6] By considering the convex hull of points inside a sphere, rather than the set of points on a sphere, it is possible to improve the construction by a factor of ${\displaystyle {\sqrt {\log n}}}$.[13][14] However, this does not affect the size bound in the form stated above.

Applications

In connection with the Ruzsa–Szemerédi problem, Salem–Spencer sets have been used to construct dense graphs in which each edge belongs to a unique triangle.[15] They have also been used in the design of the Coppersmith–Winograd algorithm for fast matrix multiplication,[16] and in the construction of efficient non-interactive zero-knowledge proofs.[17]

References

1. ^ a b c d Dybizbański, Janusz (2012), "Sequences containing no 3-term arithmetic progressions", Electronic Journal of Combinatorics, 19 (2): P15:1–P15:5, MR 2928630
2. ^ Sloane, N. J. A. (ed.). "Sequence A005836". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
3. ^ 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
4. ^ Salem, R.; Spencer, D. C. (December 1942), "On Sets of Integers Which Contain No Three Terms in Arithmetical Progression", Proceedings of the National Academy of Sciences, 28 (12): 561–563, doi:10.1073/pnas.28.12.561
5. ^ 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
6. ^ a b c d Behrend, F. A. (December 1946), "On sets of integers which contain no three terms in arithmetical progression", Proceedings of the National Academy of Sciences, 32 (12): 331–332, doi:10.1073/pnas.32.12.331
7. ^ Roth, Klaus (1952), "Sur quelques ensembles d'entiers", Comptes rendus de l'Académie des Sciences, 234: 388–390, MR 0046374
8. ^ Heath-Brown, D. R. (1987), "Integer sets containing no arithmetic progressions", Journal of the London Mathematical Society, Second Series, 35 (3): 385–394, doi:10.1112/jlms/s2-35.3.385, MR 0889362
9. ^ Szemerédi, E. (1990), "Integer sets containing no arithmetic progressions", Acta Mathematica Hungarica, 56 (1–2): 155–158, doi:10.1007/BF01903717, MR 1100788
10. ^ Bourgain, J. (1999), "On triples in arithmetic progression", Geometric and Functional Analysis, 9 (5): 968–984, doi:10.1007/s000390050105, MR 1726234
11. ^ Sanders, Tom (2011), "On Roth's theorem on progressions", Annals of Mathematics, Second Series, 174 (1): 619–636, doi:10.4007/annals.2011.174.1.20, MR 2811612
12. ^ Bloom, T. F. (2016), "A quantitative improvement for Roth's theorem on arithmetic progressions", Journal of the London Mathematical Society, Second Series, 93 (3): 643–663, arXiv:1405.5800, doi:10.1112/jlms/jdw010, MR 3509957
13. ^ a b Elkin, Michael (2011), "An improved construction of progression-free sets", Israel Journal of Mathematics, 184: 93–128, arXiv:0801.4310, doi:10.1007/s11856-011-0061-1, MR 2823971
14. ^ Green, Ben; Wolf, Julia (2010), "A note on Elkin's improvement of Behrend's construction", in Chudnovsky, David; Chudnovsky, Gregory, Additive number theory: Festschrift in honor of the sixtieth birthday of Melvyn B. Nathanson, New York: Springer, pp. 141–144, arXiv:0810.0732, doi:10.1007/978-0-387-68361-4_9, MR 2744752
15. ^ Ruzsa, I. Z.; Szemerédi, E. (1978), "Triple systems with no six points carrying three triangles", Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. János Bolyai, 18, Amsterdam and New York: North-Holland, pp. 939–945, MR 0519318
16. ^ Coppersmith, Don; Winograd, Shmuel (1990), "Matrix multiplication via arithmetic progressions", Journal of Symbolic Computation, 9 (3): 251–280, doi:10.1016/S0747-7171(08)80013-2, MR 1056627
17. ^ Lipmaa, Helger (2012), "Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments", in Cramer, Ronald, Theory of Cryptography: 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19–21, 2012, Proceedings, Lecture Notes in Computer Science, 7194, Springer, pp. 169–189, doi:10.1007/978-3-642-28914-9_10