Hillel Furstenberg and András Sárközy proved in the late 1970s the Furstenberg–Sárközy theorem of additive number theory showing that, in a certain sense, these sets cannot be very large.
In the game of subtract a square, the positions where the next player loses form a square-difference-free set.
Another square-difference-free set is obtained by doubling the Moser–de Bruijn sequence.
The best known upper bound on the size of a square-difference-free set of numbers up to
is only slightly sublinear, but the largest known sets of this form are significantly smaller, of size
Closing the gap between these upper and lower bounds remains an open problem.
In each turn, the player can only remove a nonzero square number of coins from the pile.
[1] Any position in this game can be described by an integer, its number of coins.
Thus, the cold positions form a set with no square difference: These positions can be generated by a greedy algorithm in which the cold positions are generated in numerical order, at each step selecting the smallest number that does not have a square difference with any previously selected number.
[3] Numerical evidence suggests that the actual number of cold positions up to
Equivalently, every set of natural numbers with positive upper density contains two numbers whose difference is a square, and more strongly contains infinitely many such pairs.
[5] The Furstenberg–Sárközy theorem was conjectured by László Lovász, and proved independently in the late 1970s by Hillel Furstenberg and András Sárközy, after whom it is named.
[6][7] Since their work, several other proofs of the same result have been published, generally either simplifying the previous proofs or strengthening the bounds on how sparse a square-difference-free set must be.
[8][9][10] The best upper bound currently known is due to Thomas Bloom and James Maynard,[11] who show that a square-difference-free set can include at most
Most of these proofs that establish quantitative upper bounds use Fourier analysis or ergodic theory, although neither is necessary to prove the weaker result that every square-difference-free set has zero density.
[10] Paul Erdős conjectured that every square-difference-free set has
, but this was disproved by Sárközy, who proved that denser sequences exist.
Sárközy weakened Erdős's conjecture to suggest that, for every
[12] This, in turn, was disproved by Imre Z. Ruzsa, who found square-difference-free sets with up to
[13] Ruzsa's construction chooses a square-free integer
notation for the integers, such that there exists a large set
He then chooses his square-difference-free set to be the numbers that, in base-
The digits in odd positions of these numbers can be arbitrary.
Subsequently, Ruzsa's construction has been improved by using a different base,
, the same construction generates the Moser–de Bruijn sequence multiplied by two, a square-difference-free set of
This is too sparse to provide nontrivial lower bounds on the Furstenberg–Sárközy theorem but the same sequence has other notable mathematical properties.
That is, if this conjecture is true, the exponent of one in the upper bounds for the Furstenberg–Sárközy theorem cannot be lowered.
[9] As an alternative possibility, the exponent 3/4 has been identified as "a natural limitation to Ruzsa's construction" and another candidate for the true maximum growth rate of these sets.
[17] The upper bound of the Furstenberg–Sárközy theorem can be generalized from sets that avoid square differences to sets that avoid differences in
would form a set of nonzero density with no differences in