Submitted Successfully!
To reward your contribution, here is a gift for you: A free trial for our video production service.
Thank you for your contribution! You can also upload a video entry or images related to this topic.
Version Summary Created by Modification Content Size Created at Operation
1 handwiki -- 1165 2022-11-10 01:43:27

Video Upload Options

Do you have a full video?

Confirm

Are you sure to Delete?
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
HandWiki. Furstenberg–Sárközy Theorem. Encyclopedia. Available online: https://encyclopedia.pub/entry/33785 (accessed on 24 June 2024).
HandWiki. Furstenberg–Sárközy Theorem. Encyclopedia. Available at: https://encyclopedia.pub/entry/33785. Accessed June 24, 2024.
HandWiki. "Furstenberg–Sárközy Theorem" Encyclopedia, https://encyclopedia.pub/entry/33785 (accessed June 24, 2024).
HandWiki. (2022, November 10). Furstenberg–Sárközy Theorem. In Encyclopedia. https://encyclopedia.pub/entry/33785
HandWiki. "Furstenberg–Sárközy Theorem." Encyclopedia. Web. 10 November, 2022.
Furstenberg–Sárközy Theorem
Edit

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 [math]\displaystyle{ S }[/math] is a set of natural numbers with the property that no two numbers in [math]\displaystyle{ S }[/math] differ by a square number, then the natural density of [math]\displaystyle{ S }[/math] is zero. That is, for every [math]\displaystyle{ \varepsilon \gt 0 }[/math], and for all sufficiently large [math]\displaystyle{ n }[/math], the fraction of the numbers up to [math]\displaystyle{ n }[/math] that are in [math]\displaystyle{ S }[/math] is less than [math]\displaystyle{ \varepsilon }[/math]. 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). The theorem is named after Hillel Furstenberg and András Sárközy, who proved it in the late 1970s.

natural numbers hillel natural density

1. 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.[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 [math]\displaystyle{ n }[/math] is at least proportional to [math]\displaystyle{ \sqrt n }[/math]. 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 [math]\displaystyle{ \varepsilon\gt 0 }[/math], and for all large enough [math]\displaystyle{ n }[/math], the proportion of cold positions up to [math]\displaystyle{ n }[/math] is at most [math]\displaystyle{ \varepsilon }[/math]. That is, when faced with a starting position in the range from 1 to [math]\displaystyle{ n }[/math], the first player can win from most of these positions.[3] Numerical evidence suggests that the actual number of cold positions up to [math]\displaystyle{ n }[/math] is approximately [math]\displaystyle{ n^{0.7} }[/math].[4]

2. 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.[5][6] 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.[7]Cite error: Closing </ref> missing for <ref> tag

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.[8]

3. Lower Bounds

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

[math]\displaystyle{ O(n^{1/2}\log^k n) }[/math]

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

[math]\displaystyle{ O(n^{1/2+\varepsilon}) }[/math]

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

[math]\displaystyle{ \Omega\left(n^{(1+\log_{65}7)/2}\right)\approx n^{0.733077} }[/math]

elements.[10]

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

[math]\displaystyle{ \Omega\left(n^{(1+\log_{205}12)/2}\right)\approx n^{0.733412}. }[/math][11][12]

When applied to the base [math]\displaystyle{ b=2 }[/math], 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.[13]

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

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

References

  1. "A mathematical investigation of games of "take-away"", Journal of Combinatorial Theory 1 (4): 443–458, 1966, doi:10.1016/S0021-9800(66)80016-9 . https://dx.doi.org/10.1016%2FS0021-9800%2866%2980016-9
  2. Sloane, N. J. A., ed. "Sequence A030193". OEIS Foundation. https://oeis.org/A030193. 
  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) 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. Ito, Hiro; Leonardi, Stefano, eds. (2018), "Faster evaluation of subtraction games", Proc. 9th Int. Conf. Fun with Algorithms (FUN 2018), Leibniz International Proceedings in Informatics (LIPIcs), 100, Schloss Dagstuhl, pp. 20:1–20:12, doi:10.4230/LIPIcs.FUN.2018.20  https://dx.doi.org/10.4230%2FLIPIcs.FUN.2018.20
  5. "Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions", Journal d'Analyse Mathématique 31: 204–256, 1977, doi:10.1007/BF02813304 . https://dx.doi.org/10.1007%2FBF02813304
  6. "On difference sets of sequences of integers. I", Acta Mathematica Academiae Scientiarum Hungaricae 31 (1–2): 125–149, 1978, doi:10.1007/BF01896079, https://www.renyi.hu/~p_erdos/1978-19a.pdf .
  7. "On arithmetic structures in dense sets of integers", Duke Mathematical Journal 114 (2): 215–238, 2002, doi:10.1215/S0012-7094-02-11422-7 . https://dx.doi.org/10.1215%2FS0012-7094-02-11422-7
  8. error
  9. "On difference sets of sequences of integers. II", Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae 21: 45–53 (1979), 1978 .
  10. "Difference sets without squares", Periodica Mathematica Hungarica 15 (3): 205–209, 1984, doi:10.1007/BF02454169 . https://dx.doi.org/10.1007%2FBF02454169
  11. Beigel, Richard (2008), Square-difference-free sets of size [math]\displaystyle{ \Omega(n^) }[/math], Bibcode: 2008arXiv0804.4892B . http://adsabs.harvard.edu/abs/2008arXiv0804.4892B
  12. 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, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p32 .
  13. Sloane, N. J. A., ed. "Sequence A000695 (Moser-de Bruijn sequence)". OEIS Foundation. https://oeis.org/A000695. 
  14. error
  15. Lyall, Neil; Rice, Alex (2015), Difference sets and polynomials, Bibcode: 2015arXiv150404904L . http://adsabs.harvard.edu/abs/2015arXiv150404904L
  16. Rice, Alex (2019), "A maximal extension of the best-known bounds for the Furstenberg–Sárközy theorem", Acta Arithmetica 187 (1): 1–41, doi:10.4064/aa170828-26-8  https://dx.doi.org/10.4064%2Faa170828-26-8
More
Information
Subjects: Others
Contributor MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
View Times: 263
Entry Collection: HandWiki
Revision: 1 time (View History)
Update Date: 10 Nov 2022
1000/1000
Video Production Service