Salem–Spencer set
However a later theorem of Klaus Roth shows that the size is always less than linear.
[4] This example is shifted by adding one to the elements of an infinite Salem–Spencer set, the Stanley sequence of numbers that, when written as a ternary number, use only the digits 0 and 1.
[6] In 1942, Salem and Spencer published a proof that the integers in the range from
[7] The denominator of this expression uses big O notation, and grows more slowly than any power of
, 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
[4][8] The construction of Salem and Spencer was improved by Felix Behrend in 1946, who found sets of size
[10] 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.
[11] After several additional improvements to Roth's theorem,[12][13][14][15] the size of a Salem–Spencer set has been proven to be
[18][19][20] was found by computers scientist Kelley and Meka and shortly after an exposition in more familiar mathematical terms was given by Bloom and Sisask[21][22] who have since also improved the exponent of the Kelly-Meka bound to
[23] 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.
[4] 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
His set consists of the numbers whose digits are restricted to the range from
(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
[24] 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.
as the most frequently-occurring sum of squares of digits, Behrend achieves his bound.
[9] 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.
[24][25] However, this does not affect the size bound in the form stated above.
elements form an arithmetic progression if and only if they are all equal.
[26] Gasarch, Glenn, and Kruskal have performed a comparison of different computational methods for large subsets of
[2] Using these methods they found the exact size of the largest such set for
Their results include several new bounds for different values of
, 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
[2] 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.
They have been used in the design of the Coppersmith–Winograd algorithm for fast matrix multiplication,[28] and in the construction of efficient non-interactive zero-knowledge proofs.
[29] Recently, they have been used to show size lower bounds for graph spanners,[30] and the strong exponential time hypothesis based hardness of the subset sum problem.
The smallest possible set of queens is the complement of the largest Salem–Spencer subset of the odd numbers in
