Satz von Fürstenberg-Sárközy

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 $S\subset \mathbb {N}$ ohne Quadratzahlen als Differenzen ist null. Für jedes $\delta >0$ und ein hinreichend großes $N(\delta )$ gilt für alle Teilmengen $A\subset \{1,\dotsc ,N(\delta )\}=[N(\delta )]$ mit der Dichte ${\frac {A}{N}}>\delta$, dass mindestens ein Paar $n,n+r^{2}$ für $n,r\in \mathbb {N}$ in $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. Bei diesen Spielen kann man die Stellungen in zwei Kategorien einteilen:

1. „kalte“ Stellungen (${\mathcal {N}}$-Positionen bei Berlekamp), aus denen durch jeden gültigen Zug eine heiße Stellung gemacht wird, und
2. „heiße“ Stellungen (${\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 $\mathbb {N} _{0}$ lassen sich rekursiv wie folgt kategorisieren:

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

andernfalls, wenn für alle $m^{2}\in [1,n]$ die Differenzen $n-m^{2}$ heiß sind, ist $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 $n$ mehr als $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 $n^{0,7}$ kalte Zahlen $\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 $c<1$, sodass jede Menge mit nicht-quadratischen Differenzen in $[0,n]$ $O(n^{c})$ Elemente besitzt?

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

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

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