🔢 mathematics

The least quadratic residue and integers represented by quadratic forms

Diese Arbeit etabliert nahezu optimale Schranken für den kleinsten nicht-trivialen reduzierten quadratischen Rest modulo $n$ , konstruiert Moduli, bei denen dieser Wert unerwartet groß ist, und wendet diese Ergebnisse an, um die Rate zu bestimmen, mit der binäre quadratische Formen mit beschränkter Diskriminante alle positiven Ganzzahlen bis $N$ darstellen.

Ursprüngliche Autoren: Kannan Soundararajan, João C. C. Vargas

Veröffentlicht 2026-08-03

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Kannan Soundararajan, João C. C. Vargas

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Die große Zahlensuche: Die Suche nach dem ersten „guten“ Quadrat

Stellen Sie sich vor, Sie sind ein Detektiv, der versucht, einen geheimen Code zu knacken. In der Welt der Mathematik, speziell in einem Zweig namens Zahlentheorie, sind Zahlen nicht nur zum Zählen da; sie haben Persönlichkeiten und verborgene Beziehungen. Eines der berühmtesten Rätsel betrifft „quadratische Residuen“. Man kann sie sich als Zahlen vorstellen, die „quadriert“ werden können, um perfekt in ein bestimmtes Muster zu passen. Wenn man eine Zahl nimmt, sie quadriert (mit sich selbst multipliziert) und durch eine geheime Modulo-Zahl (eine große Zahl $n$ ) teilt, ist der Rest eine quadratische Residue. Es ist wie die Suche nach einem Schlüssel, der exakt in ein bestimmtes Schloss passt.

Die große Frage, die Mathematiker schon lange beschäftigt, lautet: Wie weit muss man suchen, bevor man den ersten passenden Schlüssel findet? Mit anderen Worten: Was ist die kleinste Zahl, die man prüfen muss, um ein funktionierendes Quadrat zu finden? Dies ist nicht nur ein Spiel; das Verständnis dieser „kleinsten“ Zahlen hilft uns, die Verteilung von Zahlen zu verstehen, was für die Kryptographie (die Mathematik hinter der Internetsicherheit) und das Verständnis der tiefen Struktur des Universums der Zahlen entscheidend ist. Jahrzehntelang hatten Mathematiker gute Vermutungen, aber sie wollten wissen, ob es „trügerische“ Schlösser gibt, die einen unerwartet großen Suchbereich erfordern, bevor man einen einzigen funktionierenden Schlüssel findet.

Die große Entdeckung des Papers: Die „unglücklichen“ Schlösser

In diesem Paper befassen sich K. Soundararajan und João C. C. Vargas mit dem Rätsel der kleinsten quadratischen Residue. Sie definen eine spezielle Zahl, nennen wir sie $\ell(n)$ , welche die kleinste „quadratfreie“ ganze Zahl (eine Zahl, die nicht durch ein perfektes Quadrat wie 4, 9 oder 16 teilbar ist) ist, die als quadratische Residue für eine gegebene Zahl $n$ fungiert.

Die Autoren beweisen zwei Hauptpunkte, die auf den ersten Blick widersprüchlich erscheinen mögen, aber zusammen eine faszinierende Geschichte über die Grenzen unseres Wissens erzählen.

1. Das Sicherheitsnetz (Die obere Schranke)
Zuerst beweisen sie, dass man niemals zu weit suchen muss. Egal wie kompliziert Ihre Zahl $n$ auch sein mag, es gibt eine mathematische „Decke“ dafür, wie groß der erste funktionierende Schlüssel ( $\ell(n)$ ) maximal sein kann. Sie zeigen, dass, wenn $n$ mit $k$ verschiedenen Primfaktoren versehen ist, der kleinste funktionierende Schlüssel garantiert kleiner als eine spezifische Formel ist, die $2^{4k}$ beinhaltet. Es ist wie zu sagen: „Selbst in einem verwirrenden Labyrinth wirst du den Ausgang finden, bevor du $2^{4k}$ Schritte machst.“ Dieser Teil ist eine direkte Anwendung des Schubfachprinzips – eines Logik-Tricks, der besagt, dass, wenn man mehr Tauben als Schubfächer hat, mindestens ein Schubfach zwei Tauben enthalten muss. Hier sind die „Tauben“ die Zahlen und die „Schubfächer“ die Muster der Reste.

2. Die Überraschung (Die untere Schranke)
Hier wird es spannend. Während die Autoren bewiesen haben, dass es eine Decke gibt, entdeckten sie auch, dass für bestimmte, speziell konstruierte Zahlen der erste funktionierende Schlüssel viel, viel größer ist, als man erwartet hätte.
Normalerweise, wenn ein Muster etwa bei 1 von jeder $2^k$ Zahl auftritt, würde man erwarten, nach etwa $2^k$ Prüfungen eine Übereinstimmung zu finden. Aber die Autoren konstruierten spezifische Zahlen $n$ , bei denen die erste Übereinstimmung erst auftritt, wenn man Zahlen prüft, die so groß wie $4^k$ (abzüglich einer kleinen Korrektur) sind.
Um dies in Perspektive zu setzen: Wenn Sie nach einer Nadel im Heuhaufen suchen würden, würden Sie erwarten, die Nadel nach der Suche in ein paar Ballen zu finden. Diese Autoren haben einen so schwierigen Heuhaufen gebaut, dass Sie vielleicht einen ganzen Berg Heu durchsuchen müssen, bevor Sie die Nadel finden. Sie erreichten dies durch die Verwendung von Ideen aus der Fehlerkorrektur (der Mathematik, die zur Reparatur korrupter Daten bei Weltraummissionen oder CDs verwendet wird), indem sie zeigten, dass das „Pech“ dieser Zahlen tatsächlich ein bewusst konstruiertes Merkmal ist.

3. Das „Was wäre wenn“-Szenario (Die Riemannsche Hypothese)
Das Paper untersucht auch, was passieren würde, wenn eine berühmte, unbewiesene Vermutung namens Verallgemeinerte Riemannsche Hypothese (GRH) wahr ist. Wenn die GRH korrekt ist, sind die „trügerischen“ Zahlen nicht ganz so schlimm wie die von den Autoren konstruierten Beispiele. Unter dieser Annahme würde der kleinste Schlüssel viel früher gefunden werden, etwa um $e^{C \log n \log \log n}$ . Da wir jedoch nicht sicher wissen, ob die GRH wahr ist, bleiben die von den Autoren konstruierten „Worst-Case“-Beispiele der beste Beweis, den wir haben, dass diese Zahlen überraschend groß sein können.

Warum ist das wichtig?

Die Autoren haben ihre Erkenntnisse nicht nur bei diesen trügerischen Zahlen gestoppt; sie haben ihre Ergebnisse genutzt, um ein verwandtes Rätsel über binäre quadratische Formen zu lösen. Dies sind mathematische Ausdrücke wie $ax^2 + bxy + cy^2$ , die verwendet werden können, um andere Zahlen zu erzeugen.
Das Paper fragt: „Wie groß muss der Diskriminant (eine spezifische Zahl, die die Form definiert) sein, um sicherzustellen, dass jede positive ganze Zahl bis zu einer bestimmten Größe $N$ dargestellt werden kann?“
Unter Verwendung ihrer neuen Schranken für $\ell(n)$ zeigen die Autoren:

Unbedingt (ohne die Annahme der GRH): Es gibt ganze Zahlen bis zu $N$ , die durch keine quadratische Form mit einem Diskriminanten kleiner als ein gewisser massiver Grenzwert dargestellt werden können.
Bedingt (unter Annahme der GRH): Wenn die Riemannsche Hypothese wahr ist, ist der Grenzwert viel kleiner, was bedeutet, dass wir fast alle Zahlen mit viel einfacheren Formen darstellen können.

Das Fazit

Dieses Paper ist eine Meisterklasse im Ausbalancieren von „Best-Case“- und „Worst-Case“-Szenarien. Es bestätigt, dass, obwohl es eine theoretische Grenze dafür gibt, wie schwierig es ist, eine quadratische Residue zu finden, das Universum der Zahlen „Fallen“ enthält, in denen die Suche signifikant länger dauert, als es die einfache Wahrscheinlichkeit vermuten ließe. Die Autoren haben diese Fallen nicht nur erraten; sie haben sie mathematisch konstruiert und bewiesen, dass sie existieren. Sie zeigten auch, dass, falls eine große mathematische Vermutung (GRH) wahr ist, diese Fallen weniger tückisch sind, als sie scheinen, aber solange diese Vermutung nicht bewiesen ist, müssen wir vom Schlimmsten ausgehen.

Letztendlich verfeinert diese Arbeit unser Verständnis darüber, wie Zahlen sich verbergen und offenbaren, und beweist, dass der kleinste Schlüssel zu einem Schloss manchmal an einem Ort verborgen ist, den man ohne eine sehr kluge Karte niemals vermutet hätte.

Technische Zusammenfassung: Der kleinste quadratische Rest und durch quadratische Formen darstellbare Zahlen

Problemstellung
Diese Arbeit untersucht $\ell(n)$ , definiert als den kleinsten nicht-trivialen reduzierten quadratischen Rest modulo $n$ . Konkret ist $\ell(n)$ die kleinste quadratfreie ganze Zahl $r > 1$ , für die $\gcd(r, n) = 1$ gilt und $r \equiv x^2 \pmod n$ für eine ganze Zahl $x$ erfüllt ist. Die Autoren suchen nach Schranken für $\ell(n)$ sowohl in Abhängigkeit von der Größe von $n$ als auch von der Anzahl seiner Primfaktoren, $\omega(n)$ . Ein sekundäres Ziel ist es, diese Ergebnisse anzuwenden, um die Rate zu bestimmen, mit der Familien von binären quadratischen Formen mit beschränktem Diskriminant alle positiven ganzen Zahlen bis zu einer großen Schranke $N$ darstellen.

Methodik
Die Autoren verwenden eine Kombination aus kombinatorischen Argumenten, analytischer Zahlentheorie und algebraischen Strukturen über endlichen Körpern.

Kombinatorische und Schubfachprinzipien: Die obere Schranke für $\ell(n)$ wird unter Verwendung des Schubfachprinzips abgeleitet. Durch die Betrachtung von Primzahlen in arithmetischen Progressionen und deren Legendre-Symbolen zeigen die Autoren die Existenz eines Produkts zweier Primzahlen auf, das die erforderlichen Bedingungen für quadratische Reste erfüllt.
Algebraische Konstruktion (Untere Schranken): Um Moduli $n$ mit unerwartet großem $\ell(n)$ zu konstruieren, nutzen die Autoren eine Korrespondenz zwischen Primzahlen und irreduziblen Polynomen über dem Körper $\mathbb{F}_2$ . Sie definieren vollständig multiplikative Funktionen $f_j: \mathbb{N} \to \{-1, 1\}$ basierend auf den Wurzeln dieser Polynome im algebraischen Abschluss von $\mathbb{F}_2$ . Ein zentrales Lemma über Potenzsummen distinkter Elemente in $\mathbb{F}_2$ (verwandt mit den Newtonschen Identitäten) wird verwendet, um zu beweisen, dass eine quadratfreie ganze Zahl $r$ groß sein muss, falls $f_j(r) = 1$ für alle $j$ gilt.
Analytische Zahlentheorie und Dichteschätzungen der Nullstellen: Die Konstruktion von $n$ $n$ beruht darauf, eine Menge von Primzahlen zu finden, sodass für jeden fundamentale Diskriminanten $D$ $D$ in einem gegebenen Bereich mindestens eine Primzahl in der Menge ein quadratischer Nichtrest modulo $D$ $D$ ist.
- Unter Annahme der GRH: Die verallgemeinerte Riemannsche Hypothese (GRH) wird verwendet, um Charaktersummen über Primzahlen zu beschränken, wodurch die Existenz einer solchen Menge von Primzahlen mit einer Größe von etwa $\exp(C \log \Delta \log \log \Delta)$ sichergestellt wird.
- Unbedingt: Ohne die Annahme der GRH nutzen die Autoren Nullendichteschätzungen für Dirichlet-L-Funktionen. Sie partitionieren die Menge der Diskriminanten basierend auf dem Ort ihrer Nullstellen (Nullstellenfreien Regionen) und wenden ein gewichtetes Summenargument unter Verwendung einer spezifischen Gewichtungsfunktion $w(t)$ an, um die Existenz der erforderlichen Primzahlen zu etablieren.
Anwendung auf quadratische Formen: Die Ergebnisse werden auf die Darstellung ganzer Zahlen durch binäre quadratische Formen $f(x,y) = ax^2 + bxy + cy^2$ angewendet. Die Autoren nutzen die Tatsache, dass eine ganze Zahl $n$ durch eine Form mit Diskriminante $D$ dargestellt wird, wenn und nur wenn $D$ ein Quadrat modulo $4n$ ist (für ordentliche Darstellungen).

Wesentliche Beiträge und Ergebnisse

Schranken für $\ell(n)$ in Abhängigkeit von den Primfaktoren:
- Obere Schranke: Wenn $k$ die Anzahl der ungeraden Primfaktoren von $n$ ist, dann gilt $\ell(n) \le C k 2^{4k}$ für eine absolute Konstante $C$ .
- Untere Schranke: Für jedes $k \ge 2$ existieren unendlich viele ungerade ganze Zahlen $n$ mit genau $k$ distinkten Primfaktoren, sodass $\ell(n) \ge 4^{k - C k / \log k}$ gilt. Dieses Ergebnis ist überraschend angesichts der Tatsache, dass die Dichte der quadratischen Reste $\asymp 2^{-k}$ ist, was nahelegt, dass man erwarten würde, dass $\ell(n)$ näher bei $2^k$ liegt.
Schranken für $\ell(n)$ in Abhängigkeit von der Größe $n$ :
- Die Autoren konstruieren eine ungerade, quadratfreie ganze Zahl $n \le N(\Delta)$ , sodass für jede fundamentale Diskriminante $D$ mit $1 < |D| \le \Delta$ es einen Primfaktor $p$ von $n$ gibt, für den $\left(\frac{D}{p}\right) = -1$ gilt.
- Unbedingt: $N(\Delta)$ kann als $\exp(C \log \Delta (\log \log \Delta)^2)$ gewählt werden.
- Unter Annahme der GRH: $N(\Delta)$ kann als $\exp(C \log \Delta \log \log \Delta)$ für ein beliebiges $C > 2/\log 2$ gewählt werden.
- Folglich kann $\ell(n)$ unbedingt so groß wie $\exp\left(c \frac{\log n}{(\log \log n)^2}\right)$ und unter der GRH als $\exp\left(\left(\frac{\log 2}{2} + o(1)\right) \frac{\log n}{\log \log n}\right)$ sein.
Darstellungen durch binäre quadratische Formen:
- Indefinite Formen: Jede positive ganze Zahl bis zu $N$ kann durch eine primitive, nicht-degenerierte, indefinite binäre quadratische Form mit Diskriminante $1 < D_f \le \Delta$ dargestellt werden, wobei $\Delta = \exp\left((\log 4 + o(1)) \frac{\log N}{\log \log N}\right)$ .
- Positive definite Formen (Bedingt): Unter Annahme der GRH kann jede positive ganze Zahl bis zu $N$ durch eine primitive, positiv definite binäre quadratische Form mit Diskriminante $|D_f| \le \Delta$ dargestellt werden (mit demselben $\Delta$ wie oben).
- Einschränkungen: Es existiert eine positive ganze Zahl $n \le N$ , die durch keine primitive, nicht-degenerate binäre quadratische Form mit $|D_f| \le \Delta$ dargestellt werden kann, falls $\Delta = \exp(c \log N / (\log \log N)^2)$ . Unter der GRH verbessert sich dieser Schwellenwert auf $\exp((\frac{\log 2}{2} - \epsilon) \frac{\log N}{\log \log N})$ .

Bedeutung und Behauptungen
Das Paper beansprucht, „nahezu optimale Schranken“ für den kleinsten quadratischen Rest zu etablieren, sowohl in Bezug auf die Größe des Modulus als auch auf die Anzahl seiner Primfaktoren. Die Konstruktion von Moduli mit großem $\ell(n)$ wird durch Ideen aus der Fehlerkorrektur kodiert und stellt einen signifikanten Fortschritt gegenüber probabilistischen Erwartungen dar, indem sie zeigt, dass $\ell(n)$ wesentlich größer als der Kehrwert der Dichte der quadratischen Reste sein kann.

Die Autoren positionieren ihre Arbeit als eine Variante des klassischen Problems, das kleinste Primzahl $p$ zu finden, für die $\chi(p) = -1$ für einen primitiven quadratischen Charakter $\chi$ gilt. Während das klassische Problem unter der GRH gut verstanden ist, erweitert dieses Paper den Umfang auf zusammengesetzte Moduli und liefert unbedingte Ergebnisse, die nur geringfügig schwächer als die bedingten sind.

Darüber hinaus liefert das Paper präzise quantitative Fortschritte bei dem Problem, alle ganzen Zahlen bis $N$ durch binäre quadratische Formen mit beschränktem Diskriminanten abzudecken. Während frühere Arbeiten (Green und Soundararajan) behandelten, „fast alle“ ganzen Zahlen abzudecken, befasst sich dieses Paper mit dem schwierigeren Problem, „alle“ ganzen Zahlen abzudecken, und etabliert explizite Schwellenwerte für den Diskriminanten, die eine Darstellung garantieren.

Schließlich weisen die Autoren auf eine Verbindung zur Arbeit von Hanson, Vaughan und Zhang bezüglich des kleinsten $N$ , das erforderlich ist, damit alle Vorzeichensequenzen der Länge $k$ als Legendre-Symbol-Vektoren erscheinen, hin, was auf einen breiteren Kontext der verwendeten kombinatorischen Methoden hindeutet.

Die große Zahlensuche: Die Suche nach dem ersten „guten“ Quadrat

Die große Entdeckung des Papers: Die „unglücklichen“ Schlösser

Warum ist das wichtig?

Das Fazit

Mehr davon