Quadratdifferenzfreie Menge

In der Mathematik bezeichnet man eine Menge von natürlichen Zahlen , die sich nicht um eine Quadratzahl unterscheiden , als quadratdifferenzfrei . Hillel Furstenberg und András Sárközy bewiesen Ende der 1970er Jahre den Satz von Furstenberg-Sárközy der additiven Zahlentheorie, der besagt, dass diese Mengen in gewisser Hinsicht nicht sehr groß sein können. Im Spiel „ Subtrahiere ein Quadrat“ bilden die Positionen, auf denen der nächste Spieler verliert, eine quadratdifferenzfreie Menge. Eine weitere quadratdifferenzfreie Menge erhält man durch Verdoppeln der Moser-de-Bruijn-Folge .

Die beste bekannte obere Schranke für die Größe einer quadratdifferenzfreien Zahlenmenge bis zu ist nur geringfügig sublinear, doch die größten bekannten Mengen dieser Form sind deutlich kleiner und haben die Größe . Die Schließung der Lücke zwischen diesen oberen und unteren Schranken bleibt ein ungelöstes Problem . Die sublinearen Größenschranken für quadratdifferenzfreie Mengen lassen sich auf Mengen verallgemeinern, bei denen bestimmte andere Polynome als Differenzen zwischen Elementpaaren verboten sind. ${\displaystyle n}$${\displaystyle \approx n^{0.733412}}$

Ein Beispiel für eine Menge ohne quadratische Differenzen findet sich im Spiel „ Subtrahiere ein Quadrat“ , das von Richard A. Epstein erfunden und 1966 erstmals von Solomon W. Golomb beschrieben wurde . In diesem Spiel ziehen zwei Spieler abwechselnd Münzen von einem Stapel; der Spieler, der die letzte Münze zieht, gewinnt. In jedem Zug darf ein Spieler nur eine Quadratzahl ungleich null vom Stapel ziehen. ^{[ 1 ]} Jede Position in diesem Spiel lässt sich durch eine ganze Zahl n , die Anzahl der Münzen, beschreiben. Die nichtnegativen ganzen Zahlen lassen sich in „kalte“ Positionen, in denen der Spieler, der am Zug ist, verliert, und „heiße“ Positionen unterteilen. In letzteren kann der Spieler gewinnen, indem er auf eine kalte Position zieht. Zwei kalte Positionen dürfen sich nicht um ein Quadrat unterscheiden, denn sonst könnte ein Spieler, der vor der größeren der beiden Positionen steht, auf die kleinere ziehen und gewinnen. Daher bilden die kalten Positionen eine Menge ohne quadratische Differenz.

Diese Positionen können durch einen Greedy-Algorithmus erzeugt werden, bei dem die kalten Positionen in numerischer Reihenfolge generiert werden. In jedem Schritt wird die kleinste Zahl ausgewählt, deren quadratische Differenz zu keiner zuvor ausgewählten Zahl besteht. ^{[ 1 ] [ 2 ]} Wie Golomb feststellte, sind die kalten Positionen unendlich, und genauer gesagt, ist die Anzahl der kalten Positionen bis mindestens proportional zu . Denn gäbe es weniger kalte Positionen, reichten diese nicht aus, um für jede heiße Position einen Gewinnzug zu liefern. ^{[ 1 ]} Der Satz von Furstenberg-Sárközy zeigt jedoch, dass die kalten Positionen seltener sind als die heißen: Für jedes und für alle ausreichend großen ist der Anteil der kalten Positionen bis höchstens . Das heißt, bei einer Startposition im Bereich von 1 bis kann der erste Spieler von den meisten dieser Positionen aus gewinnen. [ ^{3 ] Numerische} Ergebnisse deuten darauf hin, dass die tatsächliche Anzahl der kalten Positionen bis ungefähr beträgt . ^{[ 4 ]}${\displaystyle n}$${\displaystyle {\sqrt {n}}}$${\displaystyle \varepsilon >0}$${\displaystyle n}$${\displaystyle n}$${\displaystyle \varepsilon }$${\displaystyle n}$${\displaystyle n}$${\displaystyle n^{0.7}}$

Nach dem Satz von Furstenberg-Sárközy ist die natürliche Dichte einer Menge ohne Quadratdifferenzen gleich null. Das heißt, für jedes n ∈ ℕ und alle hinreichend großen n ist der Anteil der Zahlen bis n, die in ℕ enthalten sind, kleiner als n . Äquivalent dazu enthält jede Menge natürlicher Zahlen mit positiver oberer Dichte zwei Zahlen, deren Differenz ein Quadrat ist, und jede Menge enthält unendlich viele solcher Paare. ^{[ 5 ]} Der Satz von Furstenberg-Sárközy wurde von László Lovász vermutet und Ende der 1970er Jahre unabhängig von Hillel Furstenberg und András Sárközy , nach dem er benannt ist, bewiesen. ^{[ 6 ] [ 7 ]} Seitdem wurden mehrere weitere Beweise desselben Ergebnisses veröffentlicht, die die vorherigen Beweise im Allgemeinen entweder vereinfachen oder die Schranken für die Dichte einer Menge ohne Quadratdifferenzen verschärfen. ^{[ 8 ] [ 9 ] [ 10 ]} Die derzeit beste bekannte obere Schranke stammt von Thomas Bloom und James Maynard , ^{[ 11 ]} die zeigen, dass eine quadratische Differenz-freie Menge höchstens die ganzen Zahlen von bis enthalten kann , ausgedrückt in der Big-O-Notation , wobei eine absolute Konstante ist. ${\displaystyle S}$${\displaystyle S}$${\displaystyle \varepsilon >0}$${\displaystyle n}$${\displaystyle n}$${\displaystyle S}$${\displaystyle \varepsilon }$$${\displaystyle O\!\left({\frac {n}{(\log n)^{c\log \log \log n}}}\right)}$$${\displaystyle 0}$${\displaystyle n}$${\displaystyle c>0}$

Die meisten dieser Beweise, die quantitative obere Schranken herleiten, verwenden Fourier-Analyse oder Ergodentheorie , obwohl keines von beiden notwendig ist, um das schwächere Ergebnis zu beweisen, dass jede quadratische Differenzen-freie Menge die Dichte Null hat. ^{[ 10 ]}

Paul Erdős vermutete, dass jede quadratdifferenzfreie Menge Elemente bis zu einer Konstanten enthält . Dies wurde jedoch von Sárközy widerlegt, der die Existenz dichterer Folgen bewies. Sárközy schwächte Erdős’ Vermutung ab und schlug vor, dass für jedes jede quadratdifferenzfreie Menge Elemente bis zu enthält . ^{[ 12 ]} Dies wiederum wurde von Imre Z. Ruzsa widerlegt , der quadratdifferenzfreie Mengen mit bis zu Elementen fand. ^{[ 13 ]}$${\displaystyle O(n^{1/2}\log ^{k}n)}$$${\displaystyle n}$${\displaystyle k}$${\displaystyle \varepsilon >0}$$${\displaystyle O(n^{1/2+\varepsilon })}$$${\displaystyle n}$$${\displaystyle \Omega {\big (}n^{(1\,+\,\log _{65}7)/2}{\big )}\approx n^{0.733077}}$$

Ruzsas Konstruktion wählt eine quadratfreie ganze Zahl als Basis der Basisnotation für die ganzen Zahlen, sodass eine große Menge von Zahlen von bis existiert , deren Differenzen keine Quadrate modulo sind . Anschließend wählt er die Menge der quadratdifferenzfreien Zahlen als diejenigen Zahlen, die in der Basisnotation Elemente von an ihren geraden Stellen haben . Die Ziffern an den ungeraden Stellen dieser Zahlen können beliebig sein. Ruzsa fand die siebenelementige Menge modulo , womit die angegebene Schranke gegeben ist. In der Folge wurde Ruzsas Konstruktion durch die Verwendung einer anderen Basis, , verbessert, um quadratdifferenzfreie Mengen der Größe zu erhalten ^{[ 14 ] [ 15 ].} Angewendet auf die Basis , erzeugt dieselbe Konstruktion die mit zwei multiplizierte Moser-de-Bruijn-Folge , eine quadratdifferenzfreie Menge von Elementen. Diese ist zu dünn besetzt, um nichttriviale untere Schranken für den Satz von Furstenberg-Sárközy zu liefern, aber dieselbe Folge hat andere bemerkenswerte mathematische Eigenschaften. ^{[ 16 ]}${\displaystyle b}$${\displaystyle b}$${\displaystyle R}$${\displaystyle 0}$${\displaystyle b-1}$${\displaystyle b}$${\displaystyle b}$${\displaystyle R}$${\displaystyle R=\{0,15,21,27,42,48,59\}}$${\displaystyle b=65}$${\displaystyle b=205}$$${\displaystyle \Omega {\big (}n^{(1\,+\,\log _{205}12)/2}{\big )}\approx n^{0.733412}.}$$${\displaystyle b=2}$${\displaystyle O(n^{1/2})}$

Ungelöstes Problem in der Mathematik

Gibt es einen Exponenten, sodass jede quadratische Differenz-freie Teilmenge von Elemente enthält ?${\displaystyle c<1}$${\displaystyle [0,n]}$${\displaystyle O(n^{c})}$

Weitere ungelöste Probleme in der Mathematik

Auf Grundlage dieser Ergebnisse wurde vermutet, dass es für jedes n und jedes hinreichend große n quadratische Differenz-freie Teilmengen der Zahlen von n bis n mit n Elementen gibt. Das heißt, falls diese Vermutung zutrifft, kann der Exponent 1 in den oberen Schranken des Satzes von Furstenberg-Sárközy nicht verringert werden. ^{[ 9 ]} Alternativ wurde der Exponent 3/4 als „natürliche Beschränkung von Ruzsas Konstruktion“ und als weiterer Kandidat für die maximale Wachstumsrate dieser Mengen identifiziert. ^{[ 17 ]}${\displaystyle \varepsilon >0}$${\displaystyle n}$${\displaystyle 0}$${\displaystyle n}$${\displaystyle \Omega (n^{1-\varepsilon })}$

Die obere Schranke des Satzes von Furstenberg-Sárközy lässt sich von Mengen, die quadratische Differenzen vermeiden, auf Mengen verallgemeinern , die Differenzen in den Werten eines Polynoms mit ganzzahligen Koeffizienten an den ganzen Zahlen vermeiden , sofern die Werte von ein ganzzahliges Vielfaches jeder ganzen Zahl enthalten. Die Bedingung bezüglich der Vielfachen ganzer Zahlen ist für dieses Ergebnis notwendig, denn gäbe es eine ganze Zahl, deren Vielfache nicht in vorkommen , so würden die Vielfachen von eine Menge mit von Null verschiedener Dichte bilden, die keine Differenzen in aufweist . ^{[ 18 ]}${\displaystyle p(\mathbb {N} )}$${\displaystyle p}$${\displaystyle p}$${\displaystyle k}$${\displaystyle p(\mathbb {N} )}$${\displaystyle k}$${\displaystyle p(\mathbb {N} )}$