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, 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. 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 k = 1 , 2 , … {\displaystyle k=1,2,\dots } the smallest values of n {\displaystyle n} such that the numbers from 1 {\displaystyle 1} to n {\displaystyle n} have a k {\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. 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. 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.
Size
In 1942, Salem and Spencer published a proof that the integers in the range from 1 {\displaystyle 1} to n {\displaystyle n} have large Salem–Spencer sets, of size n / e O ( log n / log log n ) {\displaystyle n/e^{O(\log n/\log \log n)}} . The denominator of this expression uses big O notation, and grows more slowly than any power of n {\displaystyle n} , 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 n 1 − δ {\displaystyle n^{1-\delta }} for some δ > 0 {\displaystyle \delta >0} . The construction of Salem and Spencer was improved by Felix Behrend in 1946, who found sets of size n / e O ( log n ) {\displaystyle n/e^{O({\sqrt {\log n}})}} . In 1952, Klaus Roth proved Roth's theorem establishing that the size of a Salem-Spencer set must be O ( n / log log n ) {\displaystyle O(n/\log \log n)} . 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. To distinguish Roth's bound on Salem–Spencer sets from Roth's theorem on Diophantine approximation of algebraic numbers, this result has been called Roth's theorem on arithmetic progressions. After several additional improvements to Roth's theorem, the size of a Salem–Spencer set has been proven to be O ( n ( log log n ) 4 / log n ) {\displaystyle O{\bigl (}n(\log \log n)^{4}/\log n{\bigr )}} . An even better bound of O ( n / ( log n ) 1 + δ ) {\displaystyle O{\bigl (}n/(\log n)^{1+\delta }{\bigr )}} (for some δ > 0 {\displaystyle \delta >0} that has not been explicitly computed) was announced in 2020 in a preprint. In 2023 a new bound of exp ( − c ( log N ) 1 / 12 ) N {\displaystyle \exp(-c(\log N)^{1/12})N} was found by computers scientist Kelley and Meka and shortly after an exposition in more familiar mathematical terms was given by Bloom and Sisask who have since also improved the exponent of the Kelly-Meka bound to β = 1 / 9 {\displaystyle \beta =1/9} (and conjectured β = 5 / 41 {\displaystyle \beta =5/41} ) in a preprint.
… excerpt ends here. Continue reading the full article.
