Der Satz von Fürstenberg-Sárközy ist in der additiven Zahlentheorie eine Aussage über Mengen natürlicher Zahlen, deren Elemente keine Quadrate als Differenzen haben. Der erste, der die Vermutung aufstellte, war der Mathematiker László Lovász, bewiesen wurde sie unabhängig von Hillel Fürstenberg und András Sárközy. Seitdem sind weitere Beweise veröffentlicht worden, zum Beispiel von Ben Green, oder Neil Lyall, die meist ebenfalls Ergodentheorie oder harmonische Analysis benutzen.

Der Satz wird manchmal nur nach Sárközy benannt, doch gibt es schon einen anderen Satz von Sárközy.

Aussage

Die asymptotische Dichte einer Menge ${\displaystyle S\subset \mathbb {N} }$ ohne Quadratzahlen als Differenzen ist null. Für jedes ${\displaystyle \delta >0}$ und ein hinreichend großes ${\displaystyle N(\delta )}$ gilt für alle Teilmengen ${\displaystyle A\subset \{1,\dotsc ,N(\delta )\}=[N(\delta )]}$ mit der Dichte ${\displaystyle {\frac {A}{N}}>\delta }$, dass mindestens ein Paar ${\displaystyle n,n+r^{2}}$ für ${\displaystyle n,r\in \mathbb {N} }$ in ${\displaystyle A}$ enthalten ist.

Anwendung

Ein Beispiel, in welchem Mengen dieser Art auftreten, ist das Nimm-ein-Quadrat-Spiel (engl. „subtract a square“) von Richard Arnold Epstein. In diesem haben zwei Spieler abwechselnd von einem Münzhaufen eine Quadratzahl an Münzen wegzunehmen, und es gewinnt derjenige Spieler, der die letzte Münze nimmt. Es handelt sich um ein [[Spiel mit perfekter Information|Spiel mit perfekter Information]]. Bei diesen Spielen kann man die Stellungen in zwei Kategorien einteilen:

1. „kalte“ Stellungen (${\displaystyle {\mathcal {N}}}$-Positionen bei Berlekamp), aus denen durch jeden gültigen Zug eine heiße Stellung gemacht wird, und
2. „heiße“ Stellungen (${\displaystyle {\mathcal {P}}}$-Positionen), bei denen es immer einen Zug gibt, der sie in eine kalte Stellung überführt.

Gerät demnach ein Spieler an eine heiße Stellung, dann gibt es eine Quadratzahl, deren Subtraktion eine kalte Zahl ergibt. Er kann also durch kontinuierlich perfektes Spiel den Sieg erzwingen, indem er bei jedem Zug eine derart ausgewählte Quadratzahl an Münzen wegnimmt. Gerät er jedoch an eine kalte Stellung, so muss er eine heiße daraus machen, so dass er den Sieg eines perfekt spielenden Gegenspielers nicht verhindern kann.

Die natürlichen Zahlen ${\displaystyle \mathbb {N} _{0}}$ lassen sich rekursiv wie folgt kategorisieren:

• 0 ist eine kalte Zahl.
• Sei ${\displaystyle n\in \mathbb {N} _{>0}}$ und seien die Zahlen im Intervall ${\displaystyle [0,n-1]}$ bereits kategorisiert.
  Die Zahl ${\displaystyle n}$ ist dann heiß, wenn es ein ${\displaystyle m\in \mathbb {N} }$ mit
  • ${\displaystyle m^{2}\in [1,n]}$ und
  • mit kalter Differenz ${\displaystyle n-m^{2}}$ gibt;

  andernfalls, wenn für alle ${\displaystyle m^{2}\in [1,n]}$ die Differenzen ${\displaystyle n-m^{2}}$ heiß sind, ist ${\displaystyle n}$ kalt.

Daraus folgt, dass in der Menge

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

der kalten Zahlen keine zwei Zahlen sich um ein Quadrat unterscheiden. Offensichtlich gibt es unendlich viele kalte Zahlen, und zwar unterhalb ${\displaystyle n}$ mehr als ${\displaystyle n^{0,5}}$. Aus dem Satz von Fürstenberg-Sárközy folgt nun, dass der relative Anteil an kalten Zahlen mit wachsender Obergrenze beliebig klein wird. Das bedeutet, dass die kalten Zahlen in einem sehr großen Tableau relativ sehr selten sind und ein nicht-perfekter Spieler (auch bei vorliegender heißer Stellung) große Chancen hat, Fehler zu begehen. Numerische Untersuchungen deuten darauf hin, dass es ungefähr ${\displaystyle n^{0,7}}$ kalte Zahlen ${\displaystyle \leq n}$ gibt.

Ungelöstes Problem

Es gibt ein bisher ungelöstes Problem, welches Mengen mit nicht-quadratischen Differenzen betrifft. Es lautet:

Gibt es einen Exponenten ${\displaystyle c<1}$, sodass jede Menge mit nicht-quadratischen Differenzen in ${\displaystyle [0,n]}$ ${\displaystyle O(n^{c})}$ Elemente besitzt?

Die bis dahin beste obere Schranken für die Dichte der Mengen mit nicht-quadratischen Differenzen ist:

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

für Mengen aus natürlichen Zahlen zwischen 0 und n.

Einzelnachweise

1. ↑ Harry Fürstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, Journal d'Analyse Mathématique, Band 31, 1977, S. 204–256
2. ↑ A. Sárkőzy, On difference sets of sequences of integers. I, Acta Mathematica Academiae Scientiarum Hungaricae, Band 31, 1978, S. 125–149
3. ↑ Green, On arithmetic structures in dense sets of integers, Duke Mathematical Journal, Band 114, 2002, S. 215–238
4. ↑ Lyall, A new proof of Sárközy's theorem, Proceedings of the American Mathematical Society, Band 141, 2013, S. 2253–2264, Arxiv
5. ↑ Nach Terence Tao, Ben Green und Tamar Ziegler kann er auch ohne Fourieranalyse nur mit der Cauchy-Schwarz-Ungleichung bewiesen werden. Tao, A Fourier-free proof of the Furstenberg-Sarkozy theorem, Blog von Tao 2013
6. ↑ Elwyn Berlekamp, John Horton Conway, Richard K. Guy: Gewinnen (Braunschweig, 1985/86, 4 Bände, ISBN 3528085312, ISBN 3528085320, ISBN 3528085339, ISBN 3528085347) Band 3 Fallstudien; bei books.google.de
7. ↑ zu dem auch eine Misère-Variante existiert
8. ↑ Solomon W. Golomb: A mathematical investigation of games of "take-away". In: Journal of Combinatorial Theory. Band 1, Nr. 4, 1966, S. 443–458, doi:10.1016/S0021-9800(66)80016-9 (englisch). 
9. ↑ David Eppstein: Faster evaluation of subtraction games. In: Hiro Ito, Stefano Leonardi, Linda Pagli, Giuseppe Prencipe (Hrsg.): Proc. 9th Int. Conf. Fun with Algorithms (= Schloss Dagstuhl [Hrsg.]: Leibniz International Proceedings in Informatics (LIPIcs). FUN 2018). Band 100, 2018, S. 20:1–20:12, doi:10.4230/LIPIcs.FUN.2018.20, arxiv:1804.06515 (englisch). 
10. ↑ J. Pintz, W. L. Steiger, E. Szemerédi, Journal of the London Mathematical Society, Band 37, 1988, S. 219–231