Square-difference-free set

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 ${\displaystyle n}$ is only slightly sublinear, but the largest known sets of this form are significantly smaller, of size ${\displaystyle \approx n^{0.733412}}$. 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.^[1] 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:

0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44, … (sequence A030193 in the OEIS)

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.^[1][2] As Golomb observed, the cold positions are infinite, and more strongly the number of cold positions up to ${\displaystyle n}$  is at least proportional to ${\displaystyle {\sqrt {n}}}$ . For, if there were fewer cold positions, there wouldn't be enough of them to supply a winning move to each hot position.^[1] The Furstenberg–Sárközy theorem shows, however, that the cold positions are less frequent than hot positions: for every ${\displaystyle \varepsilon >0}$ , and for all large enough ${\displaystyle n}$ , the proportion of cold positions up to ${\displaystyle n}$  is at most ${\displaystyle \varepsilon }$ . That is, when faced with a starting position in the range from 1 to ${\displaystyle n}$ , the first player can win from most of these positions.^[3] Numerical evidence suggests that the actual number of cold positions up to ${\displaystyle n}$  is approximately ${\displaystyle n^{0.7}}$ .^[4]

Upper bounds

According to the Furstenberg–Sárközy theorem, if ${\displaystyle S}$  is a square-difference-free set, then the natural density of ${\displaystyle S}$  is zero. That is, for every ${\displaystyle \varepsilon >0}$ , and for all sufficiently large ${\displaystyle n}$ , the fraction of the numbers up to ${\displaystyle n}$  that are in ${\displaystyle S}$  is less than ${\displaystyle \varepsilon }$ . 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

$${\displaystyle O\!\left({\frac {n}{(\log n)^{c\log \log \log n}}}\right)}$$

 

of the integers from ${\displaystyle 0}$  to ${\displaystyle n}$ , as expressed in big O notation, where ${\displaystyle c>0}$  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.^[10]

Lower bounds

Paul Erdős conjectured that every square-difference-free set has

$${\displaystyle O(n^{1/2}\log ^{k}n)}$$

 

elements up to ${\displaystyle n}$ , for some constant ${\displaystyle k}$ , 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 ${\displaystyle \varepsilon >0}$ , every square-difference-free set has

$${\displaystyle O(n^{1/2+\varepsilon })}$$

 

elements up to ${\displaystyle n}$ .^[12] This, in turn, was disproved by Imre Z. Ruzsa, who found square-difference-free sets with up to

$${\displaystyle \Omega {\big (}n^{(1\,+\,\log _{65}7)/2}{\big )}\approx n^{0.733077}}$$

 

elements.^[13]

Ruzsa's construction chooses a square-free integer ${\displaystyle b}$  as the radix of the base-${\displaystyle b}$  notation for the integers, such that there exists a large set ${\displaystyle R}$  of numbers from ${\displaystyle 0}$  to ${\displaystyle b-1}$  none of whose difference are squares modulo ${\displaystyle b}$ . He then chooses his square-difference-free set to be the numbers that, in base-${\displaystyle b}$  notation, have members of ${\displaystyle R}$  in their even digit positions. The digits in odd positions of these numbers can be arbitrary. Ruzsa found the seven-element set ${\displaystyle R=\{0,15,21,27,42,48,59\}}$  modulo ${\displaystyle b=65}$ , giving the stated bound. Subsequently, Ruzsa's construction has been improved by using a different base, ${\displaystyle b=205}$ , to give square-difference-free sets with size^[14][15]

$${\displaystyle \Omega {\big (}n^{(1\,+\,\log _{205}12)/2}{\big )}\approx n^{0.733412}.}$$

 

When applied to the base ${\displaystyle b=2}$ , the same construction generates the Moser–de Bruijn sequence multiplied by two, a square-difference-free set of ${\displaystyle O(n^{1/2})}$  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.^[16]

Unsolved problem in mathematics:

Is there an exponent ${\displaystyle c<1}$  such that every square-difference-free subset of ${\displaystyle [0,n]}$  has ${\displaystyle O(n^{c})}$  elements?

(more unsolved problems in mathematics)

Based on these results, it has been conjectured that for every ${\displaystyle \varepsilon >0}$  and every sufficiently large ${\displaystyle n}$  there exist square-difference-free subsets of the numbers from ${\displaystyle 0}$  to ${\displaystyle n}$  with ${\displaystyle \Omega (n^{1-\varepsilon })}$  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.^[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]

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 ${\displaystyle p(\mathbb {N} )}$ , the values at integers of a polynomial ${\displaystyle p}$  with integer coefficients, as long as the values of ${\displaystyle p}$  include an integer multiple of every integer. The condition on multiples of integers is necessary for this result, because if there is an integer ${\displaystyle k}$  whose multiples do not appear in ${\displaystyle p(\mathbb {N} )}$ , then the multiples of ${\displaystyle k}$  would form a set of nonzero density with no differences in ${\displaystyle p(\mathbb {N} )}$ .^[18]

References

1. Golomb, Solomon W. (1966), "A mathematical investigation of games of "take-away"", Journal of Combinatorial Theory, 1 (4): 443–458, doi:10.1016/S0021-9800(66)80016-9, MR 0209015.
2. Sloane, N. J. A. (ed.), "Sequence A030193", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
3. The applicability of this theorem to the sequence produced by the greedy algorithm is implicit in Ruzsa (1984), who begins his paper with the statement that, "obviously", the greedy sequence must have size at least proportional to the square root. Lyall & Rice (2015) state that a construction of Ruzsa (1984) generates sets "much larger than the set yielded by the greedy algorithm", but do not provide bounds or citations that detail the size of the greedy set.
4. Eppstein, David (2018), "Faster evaluation of subtraction games", in Ito, Hiro; Leonardi, Stefano; Pagli, Linda; Prencipe, Giuseppe (eds.), Proc. 9th Int. Conf. Fun with Algorithms (FUN 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 100, Schloss Dagstuhl, pp. 20:1–20:12, arXiv:1804.06515, doi:10.4230/LIPIcs.FUN.2018.20, ISBN 9783959770675, S2CID 4952124
5. Eisner, Tanja; Farkas, Bálint; Haase, Markus; Nagel, Rainer (2015), "20.5 The Furstenberg–Sárközy Theorem", Operator Theoretic Aspects of Ergodic Theory, Graduate Texts in Mathematics, vol. 272, Cham, Switzerland: Springer, pp. 455–457, doi:10.1007/978-3-319-16898-2, ISBN 978-3-319-16897-5, MR 3410920.
6. Furstenberg, Harry (1977), "Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions", Journal d'Analyse Mathématique, 31: 204–256, doi:10.1007/BF02813304, MR 0498471, S2CID 120917478.
7. Sárkőzy, A. (1978), "On difference sets of sequences of integers. I" (PDF), Acta Mathematica Academiae Scientiarum Hungaricae, 31 (1–2): 125–149, doi:10.1007/BF01896079, MR 0466059, S2CID 122018775.
8. Green, Ben (2002), "On arithmetic structures in dense sets of integers", Duke Mathematical Journal, 114 (2): 215–238, doi:10.1215/S0012-7094-02-11422-7, MR 1920188.
9. Lyall, Neil (2013), "A new proof of Sárközy's theorem", Proceedings of the American Mathematical Society, 141 (7): 2253–2264, arXiv:1107.0243, doi:10.1090/S0002-9939-2013-11628-X, MR 3043007, S2CID 16842750.
10. Tao, Terry (February 28, 2013), "A Fourier-free proof of the Furstenberg-Sarkozy theorem", What's new
11. Bloom, Thomas F.; Maynard, James (24 February 2021). "A new upper bound for sets with no square differences". arXiv:2011.13266 [math.NT].
12. Sárközy, A. (1978), "On difference sets of sequences of integers. II", Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, 21: 45–53 (1979), MR 0536201.
13. Ruzsa, I. Z. (1984), "Difference sets without squares", Periodica Mathematica Hungarica, 15 (3): 205–209, doi:10.1007/BF02454169, MR 0756185, S2CID 122624503.
14. Beigel, Richard; Gasarch, William (2008), Square-difference-free sets of size ${\displaystyle \Omega (n^{0.7334\dots })}$ , arXiv:0804.4892, Bibcode:2008arXiv0804.4892B.
15. Lewko, Mark (2015), "An improved lower bound related to the Furstenberg-Sárközy theorem", Electronic Journal of Combinatorics, 22 (1), Paper P1.32, 6pp, doi:10.37236/4656, MR 3315474.
16. Sloane, N. J. A. (ed.), "Sequence A000695 (Moser-de Bruijn sequence)", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
17. Lyall, Neil; Rice, Alex (2015), Difference sets and polynomials, arXiv:1504.04904, Bibcode:2015arXiv150404904L.
18. Rice, Alex (2019), "A maximal extension of the best-known bounds for the Furstenberg–Sárközy theorem", Acta Arithmetica, 187 (1): 1–41, arXiv:1612.01760, doi:10.4064/aa170828-26-8, MR 3884220, S2CID 119139825