Fürstenberg-Sárközy theorem

The set of Fürstenberg Sárközy is additive number theory a statement of quantities of natural numbers whose elements have no squares as differences. The first to make the conjecture was the mathematician László Lovász , it was proven independently by Hillel Fürstenberg and András Sárközy . Since then, further evidence has been published, for example by Ben Green or Neil Lyall, who mostly also use ergodic theory or harmonic analysis.

The sentence is sometimes named after Sárközy, but there is already another sentence from Sárközy .

statement

The asymptotic density of a set without squares as differences is zero. For each and a sufficiently large one holds for all subsets with the density that at least one pair is contained for in . ${\displaystyle S\subset \mathbb {N} }$ ${\displaystyle \delta >0}$ ${\displaystyle N(\delta )}$ ${\displaystyle A\subset \{1,\dotsc ,N(\delta )\}=[N(\delta )]}$ ${\displaystyle {\frac {A}{N}}>\delta }$ ${\displaystyle n,n+r^{2}}$ ${\displaystyle n,r\in \mathbb {N} }$ ${\displaystyle A}$

application

An example in which quantities of this kind occur is the take-a-square game (English "subtract a square") by Richard Arnold Epstein . In this two players take turns taking a square number of coins from a pile of coins, and the player who takes the last coin wins. It is a game with perfect information . In these games, the positions can be divided into two categories:

1. " Cold " positions ( positions at Berlekamp ), ${\displaystyle {\mathcal {N}}}$ from which a hot position is made by every valid move, and
2. " Hot " positions ( positions) ${\displaystyle {\mathcal {P}}}$ in which there is always a pull that takes them to a cold position.

If a player gets into a hot position, there is a square number, the subtraction of which results in a cold number. So he can force victory through continuously perfect game by removing a square number of coins selected in this way with each move. If he gets into a cold position, however , he must turn it into a hot one so that he cannot prevent a perfectly playing opponent from winning.

The natural numbers can be recursively categorized as follows: ${\displaystyle \mathbb {N} _{0}}$

• 0 is a cold number.
• Let and be the numbers in the interval already categorized. The number is hot when there is one with ${\displaystyle n\in \mathbb {N} _{>0}}$ ${\displaystyle [0,n-1]}$
  ${\displaystyle n}$ ${\displaystyle m\in \mathbb {N} }$
  • ${\displaystyle m^{2}\in [1,n]}$ and
  • with cold difference there; ${\displaystyle n-m^{2}}$

  otherwise, if for everyone the differences are hot, it is cold. ${\displaystyle m^{2}\in [1,n]}$ ${\displaystyle n-m^{2}}$ ${\displaystyle n}$

It follows that in the crowd

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

of cold numbers no two numbers differ by a square. Obviously there are infinitely many cold numbers below more than . From Fürstenberg-Sárközy's theorem it follows that the relative proportion of cold numbers becomes arbitrarily small as the upper limit increases. This means that the cold numbers in a very large tableau are relatively very rare and an imperfect player (even if the position is hot) has a good chance of making mistakes. Numerical research suggests that there are roughly cold numbers . ${\displaystyle n}$ ${\displaystyle n^{0,5}}$ ${\displaystyle n^{0,7}}$ ${\displaystyle \leq n}$

Unsolved problem

There is a so far unsolved problem concerning sets with non-quadratic differences. It is said:

Is there an exponent such that every set with non-quadratic differences in has elements? ${\displaystyle c<1}$ ${\displaystyle [0,n]}$ ${\displaystyle O(n^{c})}$

The best upper bound for the density of the sets with non-quadratic differences is:

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

for sets of natural numbers between 0 and n.

Individual evidence

1. ^ Harry Fürstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions , Journal d'Analyse Mathématique, Volume 31, 1977, pp. 204-256
2. ↑ A. Sárkőzy, On difference sets of sequences of integers. I , Acta Mathematica Academiae Scientiarum Hungaricae, Volume 31, 1978, pp. 125-149
3. ^ Green, On arithmetic structures in dense sets of integers , Duke Mathematical Journal, Volume 114, 2002, pp. 215-238
4. ^ Lyall, A new proof of Sárközy's theorem , Proceedings of the American Mathematical Society, Volume 141, 2013, pp. 2253-2264, Arxiv
5. ↑ According to Terence Tao , Ben Green and Tamar Ziegler , it can also be proven without Fourier analysis using the Cauchy-Schwarz inequality . Tao, A Fourier-free proof of the Furstenberg-Sarkozy theorem , blog by Tao 2013
6. ↑ Elwyn Berlekamp , John Horton Conway , Richard K. Guy : Winning (Braunschweig, 1985/86, 4 volumes, ISBN 3528085312 , ISBN 3528085320 , ISBN 3528085339 , ISBN 3528085347 ) Volume 3 case studies; at books.google.de
7. ↑ which also includes a Misère variant exists
8. ^ Solomon W. Golomb : A mathematical investigation of games of "take-away" . In: Journal of Combinatorial Theory . tape 1 , no. 4 , 1966, pp. 443-458 , doi : 10.1016 / S0021-9800 (66) 80016-9 (English).
9. ^ David Eppstein : Faster evaluation of subtraction games . In: Hiro Ito, Stefano Leonardi, Linda Pagli, Giuseppe Prencipe (eds.): Proc. 9th Int. Conf. Fun with Algorithms (= Schloss Dagstuhl [Hrsg.]: Leibniz International Proceedings in Informatics (LIPIcs) . FUN 2018). tape 100 , 2018, p. 20: 1–20: 12 , doi : 10.4230 / LIPIcs.FUN.2018.20 , arxiv : 1804.06515 (English).
10. ↑ J. Pintz, WL Steiger, E. Szemerédi, Journal of the London Mathematical Society, Volume 37, 1988, pp. 219-231