Numbers whose differences are not squares
In mathematics, a square-difference-free set is a set of natural numbers, no two of which differ by a square number. 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 formula_1 is only slightly sublinear, but the largest known sets of this form are significantly smaller, of size formula_2. Closing the gap between these upper and lower bounds remains an open problem. The sublinear size bounds on square-difference-free sets can be generalized to sets where certain other polynomials are forbidden as differences between pairs of elements.
Example.
An example of a set with no square differences arises in the game of subtract a square, invented by Richard A. Epstein and first described in 1966 by Solomon W. Golomb. In this game, two players take turns removing coins from a pile of coins; the player who removes the last coin wins. In each turn, the player can only remove a nonzero square number of coins from the pile. Any position in this game can be described by an integer, its number of coins.
The non-negative integers can be partitioned into "cold" positions, in which the player who is about to move is losing, and "hot" positions, in which the player who is about to move can win by moving to a cold position. No two cold positions can differ by a square, because if they did then a player faced with the larger of the two positions could move to the smaller position and win. Thus, the cold positions form a set with no square difference:
 ;templatestyles src="Block indent/styles.css"/ ;
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 As Golomb observed, the cold positions are infinite, and more strongly the number of cold positions up to formula_1 is at least proportional to formula_4. For, if there were fewer cold positions, there wouldn't be enough of them to supply a winning move to each hot position.
The Furstenberg–Sárközy theorem shows, however, that the cold positions are less frequent than hot positions: for every formula_5, and for all large enough formula_1, the proportion of cold positions up to formula_1 is at most formula_8. That is, when faced with a starting position in the range from 1 to formula_1, the first player can win from most of these positions.
Numerical evidence suggests that the actual number of cold positions up to formula_1 is approximately formula_11.
Upper bounds.
According to the Furstenberg–Sárközy theorem, if formula_12 is a square-difference-free set, then the natural density of formula_12 is zero. That is, for every formula_14, and for all sufficiently large formula_1, the fraction of the numbers up to formula_1 that are in formula_12 is less than formula_8. 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. 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. 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. The best upper bound currently known is due to Thomas Bloom and James Maynard, who show that a square-difference-free set can include at most
formula_19
of the integers from formula_20 to formula_1, as expressed in big O notation, where formula_22 is some absolute constant.
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.
Lower bounds.
Paul Erdős conjectured that every square-difference-free set has
formula_23
elements up to formula_1, for some constant formula_25, 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 formula_14, every square-difference-free set has
formula_27
elements up to formula_1. This, in turn, was disproved by Imre Z. Ruzsa, who found square-difference-free sets with up to
formula_29
elements.
Ruzsa's construction chooses a square-free integer formula_30 as the radix of the base-formula_30 notation for the integers, such that there exists a large set formula_32 of numbers from formula_20 to formula_34 none of whose difference are squares modulo formula_30. He then chooses his square-difference-free set to be the numbers that, in base-formula_30 notation, have members of formula_32 in their even digit positions. The digits in odd positions of these numbers can be arbitrary. Ruzsa found the seven-element set formula_38 modulo formula_39, giving the stated bound.
Subsequently, Ruzsa's construction has been improved by using a different base, formula_40, to give square-difference-free sets with size
formula_41
When applied to the base formula_42, the same construction generates the Moser–de Bruijn sequence multiplied by two, a square-difference-free set of formula_43 elements. 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.
 ;templatestyles src="Unsolved/styles.css" / ;
Unsolved problem in mathematics:
Is there an exponent formula_44 such that every square-difference-free subset of formula_45 has formula_46 elements?
Based on these results, it has been conjectured that for every formula_5
and every sufficiently large formula_1 there exist square-difference-free subsets of the numbers from formula_20 to formula_1 with formula_51 elements. 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.
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.
Generalization to other polynomials.
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 formula_52,
the values at integers of a polynomial formula_53 with integer coefficients, as long as the values of formula_53 include an integer multiple of every integer.
The condition on multiples of integers is necessary for this result, because if there is an integer formula_25 whose multiples do not appear in formula_52, then the multiples of formula_25 would form a set of nonzero density with no differences in formula_52.
References.
 ;templatestyles src="Reflist/styles.css" / ;