🔢 mathematics

Small complete 3-term progression free sets in cyclic groups and vector spaces

Diese Arbeit löst zwei offene Probleme, indem sie explizite Konstruktionen bereitstellt, die zeigen, dass die minimale Größe von Mengen ohne vollständige 3-er arithmetische Progressionen in zyklischen Gruppen und endlichen Vektorräumen im Wesentlichen eng mit der Quadratwurzel-Untergrenze verknüpft ist, wobei spezifisch Größen von weniger als $2\sqrt{m}$ für zyklische Gruppen und $p^{n/2+o(n)}$ für Vektorräume erreicht werden.

Ursprüngliche Autoren: Bence Csajbók, Zoltán Lóránt Nagy

Veröffentlicht 2026-06-30

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Bence Csajbók, Zoltán Lóránt Nagy

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

Stellen Sie sich vor, Sie organisieren eine Party in einem Raum mit einer sehr spezifischen Regel: Keine drei Gäste dürfen in einer perfekt geraden Linie stehen.

In der Welt der Mathematik wird diese „gerade Linie“ als arithmetische Progression bezeichnet. Wenn Sie drei Zahlen wie 2, 4 und 6 haben, liegen diese in einer geraden Linie, weil sie immer um den gleichen Betrag (2) ansteigen. Das Ziel dieses Papers ist es herauszufinden, wie groß die kleinste mögliche Gruppe von Menschen sein muss, die Sie zu der Party einladen, damit:

Keine drei Personen in Ihrer Gruppe eine gerade Linie bilden.
Wenn Sie versuchen, irgendjemand anderen aus der Außenwelt zu Ihrer Gruppe hinzuzufügen, bildet diese Person sofort eine gerade Linie mit zwei bereits anwesenden Personen.

Mathematiker nennen dies eine „vollständige progressionsfreie Menge“. Es ist wie ein Puzzle, bei dem Sie die kleinste Gruppe suchen, die „maximal sicher“ gegen die Bildung von Linien ist.

Das Paper befasst sich mit diesem Problem in zwei verschiedenen „Räumen“ (mathematischen Strukturen): Zyklischen Gruppen (wie eine Uhr) und Vektorräumen (mehrdimensionale Gitter).

Die große Frage: Wie klein kann das Team sein?

Mathematiker wussten bereits, dass die Teamgröße nicht winzig sein konnte. Wenn der Raum $N$ Plätze hat, muss das Team etwa die Quadratwurzel von $N$ groß sein (z. B. wenn der Raum 100 Plätze hat, benötigen Sie mindestens 10 Leute).

Die große Frage, die dieses Paper beantwortet, lautet: Ist das Quadratwurzel-Limit das Beste, was wir erreichen können, oder brauchen wir ein viel größeres Team?

Die Autoren sagen: „Sie brauchen kein viel größeres Team. Das Quadratwurzel-Limit ist im Grunde das Beste, was wir tun können.“

Hier ist die Lösung für die zwei verschiedenen Räume:

1. Der Uhren-Raum (Zyklische Gruppen)

Stellen Sie sich eine Uhr mit $m$ Stunden vor. Die Zahlen laufen im Kreis (nach der 12 kommt wieder die 1).

Das Problem: Finden Sie die kleinste Gruppe von Zahlen auf dieser Uhr, die keine geraden Linien hat, aber wenn man eine weitere Zahl hinzufügt, entsteht eine Linie.
Die alte Vermutung: Frühere Arbeiten deuteten darauf hin, dass Sie etwa $1,5 \times \sqrt{m}$ Personen benötigen könnten.
Das neue Ergebnis: Die Autoren haben ein spezielles Rezept erstellt, um diese Gruppen zu erschaffen. Sie haben bewiesen, dass man für jede beliebige Uhrengröße immer eine Gruppe finden kann, die kleiner als $2 \times \sqrt{m}$ ist.
- Analogie: Wenn Sie eine Uhr mit 10.000 Stunden haben, brauchen Sie nicht 10.000 Menschen. Sie benötigen nur etwa 200 Personen, um die Regeln zu erfüllen.
Die „Super“-Regel: Für die meisten großen Uhren haben sie nicht nur gerade Linien vermieden, sondern auch ein spezifischeres, strengeres Arten von Linienmustern, das sogenannte „(2, -1)-Muster“. Das ist so, als würde man sagen: „Nicht nur darfst du nicht in einer geraden Linie stehen, du darfst auch nicht einmal in einem bestimmten Zickzack-Muster stehen.“
Der Haken: Für sehr kleine Uhren (weniger als 81 Stunden) funktioniert die „Super“-Regel nicht immer, daher haben sie diese spezifischen kleinen Fälle einzeln mithilfe eines Computers überprüft.

2. Das mehrdimensionale Gitter (Vektorräume)

Stellen Sie sich nun einen Raum vor, der nicht wie eine Uhr ist, sondern ein Gitter, das sich in vielen Richtungen ausdehnt (Dimensionen). Denken Sie an eine 3D-Videospielwelt mit $n$ Dimensionen.

Das Problem: Finden Sie das kleinste Team in diesem $n$ -dimensionalen Gitter, das keine geraden Linien hat, aber „vollständig“ ist (also nicht weiter ergänzt werden kann).
Die Herausforderung: In diesen Gittern wird die Mathematik sehr kompliziert, besonders wenn das Gitter ein spezifisches Zahlensystem verwendet (ungerade Primkörper).
Das neue Ergebnis: Die Autoren nutzten einen klugen Trick unter Verwendung von gekrümmten Oberflächen (quadratische Graphen).
- Analogie: Stellen Sie sich vor, Sie platzieren Menschen auf einem gekrümmten Hügel. Weil der Hügel gekrümmt ist, ist es sehr schwer für drei Menschen, sich zufällig perfekt in einer geraden Linie aufzustellen.
- Sie bauten ein Team auf einem großen Teil des Gitters mit dieser „gekrümmte Hügel“-Methode auf. Für die verbleibenden leeren Stellen füllten sie mit einem Standard-„sicheren“ Team auf.
Das Ergebnis: Sie haben bewiesen, dass die Teamgröße für jedes feste Gitter etwa $\sqrt{N}$ beträgt (wobei $N$ $N$ die Gesamtzahl der Plätze ist), plus ein winziges bisschen zusätzlicher „Unschärfe“, die vernachlässigbar wird, wenn das Gitter riesig wird.
- In einfachen Worten: Die Teamgröße wächst im gleichen Tempo wie die Quadratwurzel der gesamten Raumgröße. Sie brauchen keine riesige Armee; das Quadratwurzel-Limit ist im Wesentlichen die perfekte Größe.

Das „Geheimrezept“ des Papers

Die Autoren verwendeten zwei Hauptwerkzeuge, um ihre Teams aufzubauen:

Das „Binäre“ Rezept (für Uhren): Sie erstellten eine Menge von Zahlen basierend auf einem speziellen Muster aus Hinzufügen und Überspringen von Zahlen (wie ein Binärcode). Dies ermöglichte es ihnen, das Team dicht zu packen, ohne Linien zu bilden, und gleichzeitig sicherzustellen, dass jeder leeren Platz auf der Uhr durch das Team „abgedeckt“ ist.
Der „Gekrümmte Hügel“-Trick (für Gitter): Sie verwendeten algebraische Kurven (Gleichungen, die wie Parabeln aussehen), um Menschen zu platzieren. Da Kurven von Natur aus geraden Linien widerstehen, erzeugt diese Methode sehr effiziente Teams. Sie kombinierten diese gekrümmten Teams dann mit Standard-Teams, um jede Dimension abzudecken.

Was sie nicht gesagt haben

Sie haben nicht gesagt, dass dies unmittelbare Anwendungen in der Kryptographie, Medizin oder Technik hat. Dies ist reine Mathematik über die Struktur von Zahlen.
Sie haben nicht behauptet, dass sie das absolut kleinste Team für jeden einzelnen Fall (das „perfekte“ Team) gefunden haben. Sie haben Teams gefunden, die sehr nah an dem theoretischen Limit liegen (innerhalb eines kleinen konstanten Faktors).
Sie haben das Problem nicht für jedes Typ von Zahlensystem gelöst (speziell konzentrierten sie sich auf ungerade Primkörper für die Gitter).

Zusammenfassung

Betrachten Sie dieses Paper als einen Meisterbaumeister, der uns zeigt, wie man den kleinstmöglichen Zaun um ein Feld baut.

Das Ziel: Der Zaun muss stark genug sein, dass der Zaun bricht (eine Linie entsteht), wenn man versucht, einen weiteren Pfosten hinzuzufügen.
Die Entdeckung: Der Baumeister hat bewiesen, dass man keinen riesigen Zaun braucht. Man benötigt nur einen Zaun, dessen Länge etwa der Quadratwurzel der Größe des Feldes entspricht.
Die Methode: Sie verwendeten kluge Muster (wie Binärcodes) und gekrümmte Formen (wie Hügel), um die Zaunpfosten so dicht wie mathematisch möglich zu packen, ohne dass sie eine gerade Linie bilden.

Dies bestätigt, dass die „Quadratwurzel“-Regel nicht nur eine Untergrenze ist, sondern im Wesentlichen die wahre Größe des Problems darstellt.

Technische Zusammenfassung: Kleine vollständige 3-Term-Progressionsfreie Mengen in zyklischen Gruppen und Vektorräumen

Problemstellung
Die Arbeit befasst sich mit der Frage nach der minimalen Größe einer vollständigen 3-Term-arithmetischen Progression (3-AP)-freien Menge in algebraischen Strukturen, spezifisch zyklischen Gruppen ( $\mathbb{Z}_m$ ) und endlichen Vektorräumen ( $\mathbb{F}_p^n$ ). Während die maximale Größe von 3-AP-freien Mengen ein zentrales Thema der additiven Kombinatorik ist (z. B. Roths Theorem, Croot-Lev-Pach, Ellenberg-Gijswijt), stellt die minimale Größe einer vollständigen Menge (einer Menge, die nicht vergrößert werden kann, ohne eine 3-AP zu erzeugen) das Analogon am unteren Ende dar. Ein einfaches Zählargument legt fest, dass die Größenordnung dieser minimalen Größe mindestens der Quadratwurzel der Kardinalität der Struktur entspricht. Die Autoren untersuchen, ob diese untere Schranke eng ist, und adressieren offene Probleme bezüglich der Existenz solcher Mengen mit der Größe $O(\sqrt{|G|})$ in zyklischen Gruppen und $p^{n/2}$ in Vektorräumen.

Methodik
Die Autoren verwenden eine Kombination aus expliziten kombinatorischen Konstruktionen, Modulreduktionstechniken und algebraischer Geometrie über endlichen Körpern.

Zyklische Gruppen ( $\mathbb{Z}_m$ ):
- Stärkeres Eigentum: Die Autoren konzentrieren sich auf vollständige (2, -1)-vermeidende Mengen. Eine Menge $A$ ist (2, -1)-vermeidend, wenn $A \cap (2A \dot{-} A) = \emptyset$ (wobei $2A \dot{-} A = \{2a - b : a, b \in A, a \neq b\}$ ). Sie ist vollständig, wenn $G = A \cup (2A \dot{-} A)$ . Diese Eigenschaft ist stärker als die der vollständigen 3-AP-Freiheit, da sie erzwingt, dass jeder Punkt außerhalb der Menge ein Endpunkt einer Progression mit Endpunkten in $A$ ist, anstatt zuzulassen, dass der Punkt außerhalb der Menge ein Mittelpunkt ist.
- R-vollständige Mengen: Die Konstruktion beruht auf „R-vollständigen“ Mengen – ganzzahligen Teilmengen von $[0, R]$ , die intern (2, -1)-vermeidend sind und das Intervall $[-R, 2R]$ sättigen.
- Binäre Digit-Konstruktion: Unter Verwendung einer generalisierten binären Digit-Konstruktion (Lemma 3.3) generieren die Autoren Mengen $P$ der Größe $2^n$ , die $S_n$ -vollständig sind. Durch die sorgfältige Wahl der Digit-Sequenz $d_i$ stellen sie sicher, dass die resultierende Menge ein breites Spektrum an Moduli $m$ abdeckt.
- Modulreduktion: Lemma 3.2 zeigt, dass eine $R$ -vollständige Menge in $\mathbb{Z}$ auf eine vollständige (2, -1)-vermeidende Menge in $\mathbb{Z}_m$ herabsteigt, wann immer $2R < m \leq 3R + 1$ .
- Endliche Verifikation: Für kleine Moduli ( $m < 81$ ), für die die allgemeine Konstruktion nicht anwendbar ist oder für die keine vollständigen (2, -1)-vermeidenden Mengen existieren können, führen die Autoren eine exzessive Enumeration durch, um die exakten minimalen Größen zu bestimmen.
Vektorräume ( $\mathbb{F}_p^n$ ):
- Quadratische Graphen: Die Kernkonstruktion nutzt die Graphen homogener quadratischer Abbildungen $Q: U \to W$ . Speziell konstruieren sie Mengen der Form $A_Q = \{(u, Q(u)) : u \in U\}$ .
- Endpunkt-Mittelpunkt-Vollständigkeit: Die Autoren definieren „Endpunkt-Mittelpunkt-vollständige“ Mengen, bei denen jeder Punkt außerhalb der Menge sowohl als Endpunkt ( $x = 2a - b$ ) als auch als Mittelpunkt ( $2x = c + d$ ) einer durch Elemente in $A$ gebildeten Progression dargestellt werden kann. Diese Eigenschaft ist entscheidend für die Produktkonstruktion.
- Unterkörper-Konstruktion: Sie konstruieren eine quadratische Abbildung $Q(x, s) = x^2 - \delta s^2$ über einer Erweiterungskörper $E = \mathbb{F}_{p^{kL}}$ und einem Unterkörper $T = \mathbb{F}_{p^k}$ , wobei $\delta$ ein Nicht-Quadrat ist. Unter Verwendung von Charakter-Summen und der Weil-Schranke beweisen sie, dass diese Abbildung surjektiv ist und einen trivialen Kern besitzt, was eine vollständige (2, -1)-vermeidende Menge in einer spezifischen Dimension $n_0 = k(2L+1)$ ergibt.
- Produkt-Lemma: Um das Ergebnis auf alle Dimensionen $n$ zu erweitern, verwenden sie ein Produkt-Lemma (Lemma 4.2). Wenn $A$ Endpunkt-Mittelpunkt-vollständig in einem Unterraum ist und $B$ 3-AP-frei in den verbleibenden Koordinaten ist, dann ist ihr Produkt $A \times B$ 3-AP-frei im vollen Raum. Dies ermöglicht das „Auffüllen“ der speziellen Dimensionen mit kleineren Mengen, um beliebige $n$ abzudecken.

Wesentliche Beiträge und Ergebnisse

Zyklische Gruppen:
- Theorem 1.2: Für jede ganze Zahl $m \geq 1$ existiert eine vollständige 3-AP-freie Menge $A \subseteq \mathbb{Z}_m$ mit der Größe $|A| < 2\sqrt{m}$ .
- Stärkeres Ergebnis für große $m$ : Für $m \geq 81$ erfüllt die konstruierte Menge die stärkere Eigenschaft der vollständigen (2, -1)-Vermeidung.
- Kleine Moduli: Das Paper liefert eine Tabelle der exakten Werte für $a(3\text{-AP}, \mathbb{Z}_m)$ und $a(2, -1)(\mathbb{Z}_m)$ für $m \leq 80$ und stellt fest, dass vollständige (2, -1)-vermeidende Mengen für bestimmte kleine Moduli nicht existieren (z. B. $m \in \{2, 5, 6, 8, 17, 18, 19, 20\}$ ).
Vektorräume:
- Theorem 1.3: Für jede feste ungerade Primzahl $p$ und $\epsilon > 0$ existiert eine Konstante $C_{p,\epsilon}$ , so dass für alle $n \geq 1$ gilt:
  $a(3\text{-AP}, \mathbb{F}_p^n) \leq C_{p,\epsilon} n^{1+\epsilon} p^{n/2} = p^{n/2 + o(n)}$
- Dieses Ergebnis löst die Variante für Vektorräume in dem Sinne, dass der Exponent von $p$ genau $n/2$ ist, was die untere Schranke bis auf einen subexponentiellen Faktor erreicht.

Bedeutung und Behauptungen
Das Paper behauptet, zwei offene Probleme bezüglich der Tightness der Quadratwurzel-unteren Schranke für vollständige progressionsfreie Mengen gelöst zu haben:

Zyklische Gruppen: Es etabliert, dass die untere Schranke bis auf eine absolute Konstante (speziell 2) für alle zyklischen Gruppen eng ist, und liefert explizite Konstruktionen für die stärkere (2, -1)-vermeidende Eigenschaft für $m \geq 81$ .
Vektorräume: Es klärt die Exponenten-Version des Problems für feste ungerade Primkörper und zeigt, dass die minimale Größe $p^{n/2 + o(n)}$ beträgt. Dies bestätigt, dass die triviale Zähl-Schranke hinsichtlich der exponentiellen Wachstumsrate im Wesentlichen scharf ist.

Die Autoren merken an, dass die Konstante des Faktors im Ergebnis für zyklische Gruppen (2) über dem Zielwert von $3/2$ liegt, den sie in ihrer vorangegangenen Arbeit vorgeschlagen hatten; die Konstruktion ist jedoch bewusst auf die stärkere (2, -1)-vermeidende Eigenschaft beschränkt. Sie deuten an, dass die Ausnutzung der zusätzlichen Freiheit der Standard-3-AP-Vollständigkeit (die es erlaubt, dass Punkte außerhalb der Menge auch Mittelpunkte sind) kleinere Konstruktionen liefern könnte. Ähnlich bleibt für Vektorräume die Frage nach einer einheitlichen absoluten Konstante, die unabhängig von $n$ ist, sowie die Existenz solcher Schranken für vollständige (2, -1)-vermeidende Mengen in jeder Dimension, offen. Die Arbeit verbindet diese Probleme der additiven Kombinatorik mit der endlichen Geometrie, spezifisch mit vollständigen Caps und Sättigungs-Mengen.