Benutzer:Mandelbrotmenge314/Fürstenberg-Sárközy-Theorem

Das Fürstenberg-Sárközy-Theorem ist eine Aussage über Mengen, 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.

Aussage

Die natürliche Dichte einer Menge $S$ mit quadratfreien Differenzen ist null . Für jedes $\delta >0$ und ein hinreichend großes $N(\delta )$ gilt für alle Teilmengen $A\subset \{1,...,N(\delta )\}=[N(\delta )]$ mit der Dichte ${\frac {A}{N}}>\delta$, dass mindestens ein Paar $n,n+r^{2}$ für $n,r\in N$ in $A$ enthalten ist. Äquivalent dazu ist für alle $\delta >0$ und hinreichend große $n$ die Dichte aller quadratfreien Teilmengen der natürlichen Zahlen kleiner als $n$ kleiner als $\delta$.

Anwendung

Ein Beispiel, in welchem Mengen dieser Art auftreten, ist das Spiel "subtract a square", in welchem von zwei Spielern von einem Münzhaufen eine Quadratzahl an Münzen entfernt wird. Gewonnen hat derjenige, der die letzte Münze entfernt. Nun kann die Anzahl der natürlichen Zahlen rekursiv in zwei Kategorien eingeteilt werden: Die "guten" Zahlen und die "schlechten" Zahlen, wobei die guten Zahlen für den Spieler durch Subtraktion einer Quadratzahl zu einem Gewinn und die schlechten Zahlen zu einem Verlust führen Aus dieser Definition folgt, dass die Menge der schlechten Zahlen quadratfrei ist:

$0,2,5,7,10,12,15,17,20,22,34,39,44,......$

Offensichtlich gibt es unendlich viele schlechte Zahlen. Da die Menge der schlechten Zahlen quadratfrei ist, lässt sich also hier der Satz anwenden, wonach sich in diesem speziellen Fall der relative Anteil an schlechten Zahlen mit stetig wachsender Obergrenze asymptotisch der Null annähert. Numerische Berechnungen deuten darauf hin, dass der Anteil an schlechten Zahlen bis zu einer Grenze $n$ ungefähr $n^{0,7}$ beträgt.

Ungelöstes Problem

Es gibt ein bisher ungelöstes Problem, welches quadratfreie Mengen betrifft. Es lautet:

Gibt es einen Exponenten $c<1$, sodass jede quadratfreie Menge in $[0,n]$ $O(n^{c})$ Elemente besitzt?

Einzelnachweise

Kategorie:Diskrete Mathematik Kategorie:Spieltheorie