Furstenberg–Sárközy theorem

The Furstenberg–Sárközy theorem is a result in additive number theory on sets of numbers no two of which differ by a square. It states that, if ${\displaystyle S}$ is a set of natural numbers with the property that no two numbers in ${\displaystyle S}$ differ by a square number, 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 infinitely many such pairs).[1] The theorem is named after Hillel Furstenberg and András Sárközy, who proved it in the late 1970s.

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 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.[2] 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.[2][3] 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.[2] 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.[4] Numerical evidence suggests that the actual number of cold positions up to ${\displaystyle n}$ is approximately ${\displaystyle n^{0.7}}$.[5]

Upper bounds

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] In particular, it is now known that a square-difference-free set can include at most

${\displaystyle O(n/(\log n)^{{\frac {1}{4}}\log \log \log \log n})}$

of the integers from ${\displaystyle 0}$ to ${\displaystyle n}$, as expressed in big O notation.[11]

Most of these proofs use Fourier analysis or ergodic theory. However, this is not necessary for a proof of the basic form of the theorem, 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 \left(n^{(1+\log _{65}7)/2}\right)\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

${\displaystyle \Omega \left(n^{(1+\log _{205}12)/2}\right)\approx n^{0.733412}.}$[14][15]

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 that is too sparse to provide nontrivial lower bounds on the Furstenberg–Sárközy theorem but one that 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. 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, 272, Cham, Switzerland: Springer, pp. 455–457, doi:10.1007/978-3-319-16898-2, ISBN 978-3-319-16897-5, MR 3410920.
2. 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.
3. Sloane, N. J. A. (ed.). "Sequence A030193". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
4. 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.
5. 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), 100, Schloss Dagstuhl, pp. 20:1–20:12, arXiv:1804.06515, doi:10.4230/LIPIcs.FUN.2018.20
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.
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.
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.
10. Tao, Terry (February 28, 2013), "A Fourier-free proof of the Furstenberg-Sarkozy theorem", What's new
11. Pintz, János; Steiger, W. L.; Szemerédi, Endre (1988), "On sets of natural numbers whose difference set contains no squares", Journal of the London Mathematical Society, Second Series, 37 (2): 219–231, doi:10.1112/jlms/s2-37.2.219, MR 0928519.
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.
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, 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