View source for Salem–Spencer set

{{Short description|Progression-free set of numbers}}
[[File:Salem-Spencer-8-14.svg|thumb|upright=1.35|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 have also been called non-averaging sets,{{r|m53|ggk}} but this term has also been used to denote a set of integers none of which can be obtained as the average of any subset of the other numbers.{{r|a76}} Salem-Spencer sets are named after [[Raphaël Salem]] and [[Donald C. Spencer]], who showed in 1942 that Salem–Spencer sets can have nearly-linear size. However a later theorem of [[Klaus Roth]] shows that the size is always less than linear.

==Examples==
For <math>k=1,2,\dots</math> the smallest values of <math>n</math> such that the numbers from <math>1</math> to <math>n</math> have a <math>k</math>-element Salem-Spencer set are
:1, 2, 4, 5, 9, 11, 13, 14, 20, 24, 26, 30, 32, 36, ... {{OEIS|A065825}}
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.{{r|d12}}

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, ... {{OEIS|A005836}}
of numbers that, when written as a [[ternary number]], use only the digits 0 and 1. This sequence is the [[Lexicographical order|lexicographically]] first infinite Salem–Spencer set.<ref>{{cite OEIS|A005836|mode=cs2}}</ref> Another infinite Salem–Spencer set is given by the [[Cube (algebra)|cubes]]
:0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, ... {{OEIS|A000578}}
It is a theorem of [[Leonhard Euler]] that no three cubes are in arithmetic progression.{{r|elrss}}

==Size==
{{See also|Szemerédi's theorem#Quantitative bounds|Erdős conjecture on arithmetic progressions#Progress and related results|Roth's theorem on arithmetic progressions#Improving Bounds}}
In 1942, Salem and Spencer published a proof that the integers in the range from <math>1</math> to <math>n</math> have large Salem–Spencer sets, of size <math>n/e^{O(\log n/\log\log n)}</math>.{{r|ss42}} The denominator of this expression uses [[big O notation]], and grows more slowly than any power of <math>n</math>, so the sets found by Salem and Spencer have a size that is nearly linear. 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 <math>n^{1-\delta}</math> for some <math>\delta>0</math>.{{r|d12|et36}}
The construction of Salem and Spencer was improved by [[Felix Behrend]] in 1946, who found sets of size <math>n/e^{O(\sqrt{\log n})}</math>.{{r|b46}}

In 1952, [[Klaus Roth]] proved [[Roth's theorem on arithmetic progressions|Roth's theorem]] establishing that the size of a Salem-Spencer set must be <math>O(n/\log\log n)</math>.{{r|r52}} Therefore, although the sets constructed by Salem, Spencer, and Behrend have sizes that are nearly linear, it is not possible to improve them and find sets whose size is actually linear. This result became a special case of [[Szemerédi's theorem]] on the density of sets of integers that avoid longer arithmetic progressions.{{r|d12}} To distinguish Roth's bound on Salem–Spencer sets from [[Roth's theorem]] on [[Diophantine approximation]] of [[algebraic number]]s, this result has been called ''Roth's theorem on arithmetic progressions''.{{r|bs19}} After several additional improvements to Roth's theorem,{{r|hb87|s90|b99|s11}} the size of a Salem–Spencer set has been proven to be <math>O\bigl(n(\log\log n)^4/\log n\bigr)</math>.{{r|b16}} An even better bound of <math>O\bigl(n/(\log n)^{1+\delta}\bigr)</math> (for some <math>\delta>0</math> that has not been [[Effective results in number theory|explicitly]] computed) was announced in 2020 in a preprint.{{r|bs20}} In 2023 a new bound of <math>\exp(-c(\log N)^{1/12})N</math><ref>{{Cite book |last1=Kelley |first1=Zander |last2=Meka |first2=Raghu |chapter=Strong Bounds for 3-Progressions |date=2023-11-06 |title=2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) |chapter-url=https://ieeexplore.ieee.org/document/10353076 |publisher=IEEE |pages=933–973 |doi=10.1109/FOCS57990.2023.00059 |isbn=979-8-3503-1894-4|arxiv=2302.05537 }}</ref><ref>{{Cite arXiv |last1=Kelley |first1=Zander |last2=Meka |first2=Raghu |date=2023-02-10 |title=Strong Bounds for 3-Progressions |class=math.NT |eprint=2302.05537 }}</ref><ref>{{Cite web |last=Sloman |first=Leila |date=2023-03-21 |title=Surprise Computer Science Proof Stuns Mathematicians |url=https://www.quantamagazine.org/surprise-computer-science-proof-stuns-mathematicians-20230321/ |access-date= |website=Quanta Magazine |language=en}}</ref> was found by computers scientist Kelley and Meka and shortly after an exposition in more familiar mathematical terms was given by [[Thomas Bloom|Bloom]] and Sisask<ref>{{Cite journal |last1=Bloom |first1=Thomas F. |last2=Sisask |first2=Olof |date=2023-12-31 |title=The Kelley–Meka bounds for sets free of three-term arithmetic progressions |url=https://msp.org/ent/2023/2-1/p02.xhtml |journal=Essential Number Theory |language=en |volume=2 |issue=1 |pages=15–44 |doi=10.2140/ent.2023.2.15 |issn=2834-4634|arxiv=2302.07211 }}</ref><ref>{{Cite journal |last1=Bloom |first1=Thomas F. |last2=Sisask |first2=Olof |date=2023-02-14 |title=The Kelley–Meka bounds for sets free of three-term arithmetic progressions |journal=Essential Number Theory |volume=2 |pages=15–44 |doi=10.2140/ent.2023.2.15 |arxiv=2302.07211 }}</ref> who have since also improved the exponent of the Kelly-Meka bound to <math>\beta=1/9</math> (and conjectured <math>\beta=5/41</math>) in a preprint.<ref>{{Cite arXiv |eprint=2309.02353 |class=math.NT |first1=Thomas F. |last1=Bloom |first2=Olof |last2=Sisask |title=An improvement to the Kelley-Meka bounds on three-term arithmetic progressions |date=2023-09-05}}</ref>

==Construction==
A simple construction for a Salem–Spencer set (of size considerably smaller than Behrend's bound) is to choose the [[Ternary numeral system|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 <math>x</math> and <math>y</math> 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 <math>x</math> and <math>y</math> differ.{{r|d12}} 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 <math>2d-1</math>. His set consists of the numbers whose digits are restricted to the range from <math>0</math> to <math>d-1</math> (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 <math>k</math>.{{r|b46}} 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.{{r|e11}} 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.{{r|b46}}

With a careful choice of <math>d</math>, and a choice of <math>k</math> as the most frequently-occurring sum of squares of digits, Behrend achieves his bound.{{r|b46}}
In 1953, [[Leo Moser]] proved that there is a single infinite Salem–Spencer sequence achieving the same asymptotic density on every prefix as Behrend's construction.{{r|m53}}
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 <math>\sqrt{\log n}</math>.{{r|e11|gw10}} However, this does not affect the size bound in the form stated above.

== Generalization ==
The notion of Salem–Spencer sets (3-AP-free set) can be generalized to <math>k</math>-AP-free sets, in which <math>k</math> elements form an arithmetic progression if and only if they are all equal. {{harvtxt|Rankin|1961}} gave constructions of large <math>k</math>-AP-free sets.{{r|r61}}

==Computational results==
Gasarch, Glenn, and Kruskal have performed a comparison of different computational methods for large subsets of <math>\{1,\dots n\}</math> with no arithmetic progression.{{r|ggk}} Using these methods they found the exact size of the largest such set for <math>n\le 187</math>. Their results include several new  bounds for different values of <math>n</math>, found by [[branch-and-bound]] algorithms that use [[linear programming]] and problem-specific heuristics to bound the size that can be achieved in any branch of the search tree. One heuristic that they found to be particularly effective was the ''thirds method'', in which two shifted copies of a Salem–Spencer set for <math>n</math> are placed in the first and last thirds of a set for <math>3n</math>.{{r|ggk}}

==Applications==
{{Chess diagram|alignment=tright|fen=Q7/8/2Q5/3Q4/4Q3/8/6Q1/8|footer=Five queens on the main diagonal of a chessboard, attacking all other squares. The vacant squares on the diagonal are in rows 1, 3, and 7, an all-odd Salem–Spencer set.}}
In connection with the [[Ruzsa–Szemerédi problem]], Salem–Spencer sets have been used to construct dense graphs in which [[Locally linear graph|each edge belongs to a unique triangle]].{{r|rs78}} 

Salem–Spencer sets have also been used in theoretical computer science. They have been used in the design of the [[Coppersmith–Winograd algorithm]] for fast [[matrix multiplication]],{{r|cw90}} and in the construction of efficient [[non-interactive zero-knowledge proof]]s.{{r|l12}} Recently, they have been used to show size lower bounds for [[Graph spanner|graph spanners]],{{r|ab17}} and the [[strong exponential time hypothesis]] based hardness of the [[subset sum problem]].{{r|abhs17}}

These sets can also be applied in [[recreational mathematics]] to a [[mathematical chess problem]] of
placing as few queens as possible on the main diagonal of an <math>n\times n</math> chessboard so that all squares of the board are attacked. The set of diagonal squares that remain unoccupied must form a Salem–Spencer set, in which all values have the same parity (all odd or all even).
The smallest possible set of queens is the complement of the largest Salem–Spencer subset of the odd numbers in <math>\{1,\dots n\}</math>.
This Salem-Spencer subset can be found by doubling and subtracting one from the values in a Salem–Spencer subset of all the numbers in <math>\{1,\dots n/2\}.</math>{{r|ch}}

==References==
{{reflist|refs=

<ref name=a76>{{citation
 | last = Abbott | first = H. L.
 | contribution = On a conjecture of Erdős and Straus on non-averaging sets of integers
 | location = Winnipeg, Manitoba
 | mr = 0406967
 | pages = 1–4
 | publisher = Utilitas Math.
 | series = Congressus Numerantium
 | title = Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975)
 | volume = XV
 | year = 1976}}</ref>

<ref name=b46>{{citation
 | last = Behrend | first = F. A. | authorlink = Felix Behrend
 | date = December 1946
 | doi = 10.1073/pnas.32.12.331
 | issue = 12
 | journal = [[Proceedings of the National Academy of Sciences]]
 | pages = 331–332
 | title = On sets of integers which contain no three terms in arithmetical progression
 | volume = 32| pmc = 1078964
 | pmid=16578230
 | bibcode = 1946PNAS...32..331B | doi-access = free }}</ref>

<ref name=b16>{{citation
 | last = Bloom | first = T. F.
 | arxiv = 1405.5800
 | doi = 10.1112/jlms/jdw010
 | issue = 3
 | journal = [[Journal of the London Mathematical Society]]
 | mr = 3509957
 | pages = 643–663
 | series = Second Series
 | title = A quantitative improvement for Roth's theorem on arithmetic progressions
 | volume = 93
 | year = 2016| s2cid = 27536138
 }}</ref>

<ref name=bs19>{{citation
 | last1 = Bloom | first1 = Thomas
 | last2 = Sisask | first2 = Olaf
 | arxiv = 1810.12791v2
 | doi = 10.19086/da.7884
 | issue = 4
 | journal = [[Discrete Analysis]]
 | title = Logarithmic bounds for Roth's theorem via almost-periodicity
 | volume = 2019
 | year = 2019| s2cid = 119583263
 }}</ref>

<ref name=bs20>{{citation
 | last1 = Bloom | first1 = Thomas
 | last2 = Sisask | first2 = Olaf
 | arxiv = 2007.03528
 | title = Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions
 | year = 2020}}; see also {{citation
 | first = Gil | last = Kalai | authorlink = Gil Kalai
 | title = To cheer you up in difficult times 7: Bloom and Sisask just broke the logarithm barrier for Roth's theorem!
 | work = Combinatorics and more
 | url = https://gilkalai.wordpress.com/2020/07/08/to-cheer-you-up-in-difficult-times-7-bloom-and-sisask-just-broke-the-logarithm-barrier-for-roths-theorem/
 | date = July 8, 2020}}</ref>

<ref name=b99>{{citation
 | last = Bourgain | first = J. | authorlink = Jean Bourgain
 | doi = 10.1007/s000390050105
 | issue = 5
 | journal = [[Geometric and Functional Analysis]]
 | mr = 1726234
 | pages = 968–984
 | title = On triples in arithmetic progression
 | volume = 9
 | year = 1999| s2cid = 392820 }}</ref>

<ref name=ch>{{citation
 | last1 = Cockayne | first1 = E. J.
 | last2 = Hedetniemi | first2 = S. T.
 | doi = 10.1016/0097-3165(86)90012-9
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 843468
 | pages = 137–139
 | series = Series A
 | title = On the diagonal queens domination problem
 | volume = 42
 | year = 1986| doi-access = 
 }}</ref>

<ref name=cw90>{{citation
 | last1 = Coppersmith | first1 = Don | author1-link = Don Coppersmith
 | last2 = Winograd | first2 = Shmuel | author2-link = Shmuel Winograd
 | doi = 10.1016/S0747-7171(08)80013-2
 | issue = 3
 | journal = [[Journal of Symbolic Computation]]
 | mr = 1056627
 | pages = 251–280
 | title = Matrix multiplication via arithmetic progressions
 | volume = 9
 | year = 1990| doi-access = free
 }}</ref>

<ref name=d12>{{citation
 | last = Dybizbański | first = Janusz
 | issue = 2
 | journal = Electronic Journal of Combinatorics
 | mr = 2928630
 | pages = P15:1–P15:5
 | title = Sequences containing no 3-term arithmetic progressions
 | url = https://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p15
 | volume = 19
 | year = 2012| doi = 10.37236/2061
 | doi-access = free
 }}</ref>

<ref name=e11>{{citation
 | last = Elkin | first = Michael
 | arxiv = 0801.4310
 | doi = 10.1007/s11856-011-0061-1 | doi-access = free
 | journal = [[Israel Journal of Mathematics]]
 | mr = 2823971
 | pages = 93–128
 | title = An improved construction of progression-free sets
 | volume = 184
 | year = 2011}}</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 (journal)|Discrete Mathematics]]
 | mr = 1692285
 | pages = 119–135
 | title = Greedy algorithm, arithmetic progressions, subset sums and divisibility
 | volume = 200
 | year = 1999| doi-access = 
 }}</ref>

<ref name=et36>{{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=ggk>{{citation
 | last1 = Gasarch | first1 = William | author1-link = William Gasarch
 | last2 = Glenn | first2 = James
 | last3 = Kruskal | first3 = Clyde P. | author3-link = Clyde Kruskal
 | doi = 10.1016/j.jcss.2007.06.002
 | issue = 4
 | journal = [[Journal of Computer and System Sciences]]
 | mr = 2417032
 | pages = 628–655
 | title = Finding large 3-free sets. I. The small {{mvar|n}} case
 | url = https://www.cs.umd.edu/~gasarch/papers/3apI.pdf
 | volume = 74
 | year = 2008}}</ref>

<ref name=gw10>{{citation
 | last1 = Green | first1 = Ben | author1-link = Ben Green (mathematician)
 | last2 = Wolf | first2 = Julia | author2-link = Julia Wolf
 | editor1-last = Chudnovsky | editor1-first = David | editor1-link = Chudnovsky brothers
 | editor2-last = Chudnovsky | editor2-first = Gregory | editor2-link = Chudnovsky brothers
 | arxiv = 0810.0732
 | contribution = A note on Elkin's improvement of Behrend's construction
 | doi = 10.1007/978-0-387-68361-4_9
 | location = New York
 | mr = 2744752
 | pages = 141–144
 | publisher = Springer
 | title = Additive number theory: Festschrift in honor of the sixtieth birthday of Melvyn B. Nathanson
 | year = 2010| isbn = 978-0-387-37029-3 | s2cid = 10475217 }}</ref>

<ref name=hb87>{{citation
 | last = Heath-Brown | first = D. R. | authorlink = Roger Heath-Brown
 | doi = 10.1112/jlms/s2-35.3.385
 | issue = 3
 | journal = [[Journal of the London Mathematical Society]]
 | mr = 889362
 | pages = 385–394
 | series = Second Series
 | title = Integer sets containing no arithmetic progressions
 | volume = 35
 | year = 1987}}</ref>

<ref name=l12>{{citation
 | last = Lipmaa | first = Helger
 | editor-last = Cramer | editor-first = Ronald
 | contribution = Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments
 | contribution-url = http://eprint.iacr.org/2011/009
 | doi = 10.1007/978-3-642-28914-9_10
 | pages = 169–189
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Theory of Cryptography: 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19–21, 2012, Proceedings
 | volume = 7194
 | year = 2012| doi-access = free
 | isbn = 978-3-642-28913-2
 }}</ref>

<ref name=m53>{{citation
 | last = Moser | first = Leo | authorlink = Leo Moser
 | doi = 10.4153/cjm-1953-027-0
 | journal = [[Canadian Journal of Mathematics]]
 | mr = 0053140
 | pages = 245–252
 | title = On non-averaging sets of integers
 | volume = 5
 | year = 1953| s2cid = 124488483 | doi-access = free
 }}</ref>

<ref name=r52>{{citation
 | last = Roth | first = Klaus | authorlink = Klaus Roth
 | journal = [[Comptes rendus de l'Académie des Sciences]]
 | mr = 0046374
 | pages = 388–390
 | title = Sur quelques ensembles d'entiers
 | volume = 234
 | year = 1952}}</ref>

<ref name=rs78>{{citation
 | last1 = Ruzsa | first1 = I. Z. | author1-link = Imre Z. Ruzsa
 | last2 = Szemerédi | first2 = E. | author2-link = Endre Szemerédi
 | contribution = Triple systems with no six points carrying three triangles
 | mr = 519318
 | pages = 939–945
 | publisher = North-Holland | location = Amsterdam and New York
 | series = Colloq. Math. Soc. János Bolyai
 | title = Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II
 | volume = 18
 | year = 1978}}</ref>

<ref name=s90>{{citation
 | last = Szemerédi | first = E. | authorlink = Endre Szemerédi
 | doi = 10.1007/BF01903717 | doi-access = 
 | issue = 1–2
 | journal = [[Acta Mathematica Hungarica]]
 | mr = 1100788
 | pages = 155–158
 | title = Integer sets containing no arithmetic progressions
 | volume = 56
 | year = 1990}}</ref>

<ref name=s11>{{citation
 | last = Sanders | first = Tom | authorlink = Tom Sanders (mathematician)
 | doi = 10.4007/annals.2011.174.1.20
 | issue = 1
 | journal = [[Annals of Mathematics]]
 | mr = 2811612
 | pages = 619–636
 | series = Second Series
 | title = On Roth's theorem on progressions
 | volume = 174
 | year = 2011| arxiv = 1011.0104
 | s2cid = 53331882 }}</ref>

<ref name=ss42>{{citation
 | last1 = Salem | first1 = R. | author1-link = Raphaël Salem
 | last2 = Spencer | first2 = D. C. | author2-link = Donald C. Spencer
 | date = December 1942
 | doi = 10.1073/pnas.28.12.561
 | issue = 12
 | journal = [[Proceedings of the National Academy of Sciences]]
 | pages = 561–563
 | title = On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
 | volume = 28 | pmid=16588588 | pmc=1078539| bibcode = 1942PNAS...28..561S | doi-access = free }}</ref>

<ref name=r61>{{citation
 | last = Rankin | first = R. A. | author-link = Robert Alexander Rankin
 | doi = 10.1017/S0080454100017726
 | issue = 4
 | journal = Proceedings of the Royal Society of Edinburgh, Section A: Mathematical and Physical Sciences
 | pages = 332–344
 | title = XXIV: Sets of integers containing not more than a given number of terms in arithmetical progression
 | volume = 65
 | year = 1961| s2cid = 122037820 }}</ref>

<ref name=ab17>{{citation
 | last1 = Abboud | first1 = Amir
 | last2 = Bodwin | first2 = Greg
 | arxiv = 1511.00700
 | doi = 10.1145/3088511
 | issue = 4
 | journal = [[Journal of the ACM]]
 | mr = 3702458
 | page = A28:1–A28:20
 | title = The 4/3 additive spanner exponent is tight
 | volume = 64
 | year = 2017| s2cid = 209870748
 }}</ref>

<ref name=abhs17>{{citation
 | last1 = Abboud | first1 = Amir
 | last2 = Bringmann | first2 = Karl | author2-link = Karl Bringmann
 | last3 = Hermelin | first3 = Danny
 | last4 = Shabtay | first4 = Dvir
 | editor-last = Chan | editor-first = Timothy M. | editor-link = Timothy M. Chan
 | arxiv = 1704.04546
 | contribution = SETH-based lower bounds for subset sum and bicriteria path
 | doi = 10.1137/1.9781611975482.3
 | pages = 41–57
 | publisher = Society for Industrial and Applied Mathematics
 | title = Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019
 | year = 2019| isbn = 978-1-61197-548-2
 | s2cid = 15802062
 }}</ref>

}}

==External links==
*[http://www.math.uni.wroc.pl/~jwr/non-ave/ Nonaveraging sets search], Jarek Wroblewski, [[University of Wrocław]]

{{DEFAULTSORT:Salem-Spencer set}}
[[Category:Additive combinatorics]]