🔢 mathematics

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

Dit artikel lost twee openstaande problemen op door expliciete constructies te bieden die aantonen dat de minimale grootte van verzamelingen zonder volledige 3-term rekenkundige progressies in cyclische groepen en eindige vectorruimten essentieel nauw aansluit bij de wortel-ondergrens, waarbij specifiek grootheden kleiner dan $2\sqrt{m}$ voor cyclische groepen en $p^{n/2+o(n)}$ voor vectorruimten worden bereikt.

Oorspronkelijke auteurs: Bence Csajbók, Zoltán Lóránt Nagy

Gepubliceerd 2026-06-30

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Bence Csajbók, Zoltán Lóránt Nagy

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een feestje organiseert in een kamer met een zeer specifieke regel: Geen drie gasten mogen in een perfect rechte lijn staan.

In de wereld van de wiskunde wordt deze "rechte lijn" een arithmetische progressie genoemd. Als je drie getallen hebt zoals 2, 4 en 6, staan ze in een rechte lijn omdat ze telkens met hetzelfde bedrag (2) omhoog gaan. Het doel van dit artikel is om te achterhalen wat de kleinste mogelijke groep mensen is die je moet uitnodigen voor het feestje zodat:

Geen drie mensen in jouw groep een rechte lijn vormen.
Als je ook maar iemand anders uit de buitenwereld aan de groep zou toevoegen, diegene onmiddellijk een rechte lijn vormt met twee mensen die al binnen zijn.

Wiskundigen noemen dit een "complete progressievrije verzameling." Het is als een puzzel waarbij je de kleinste groep wilt die "maximaal veilig" is tegen het vormen van lijnen.

Het artikel behandelt dit probleem in twee verschillende "kamers" (wiskundige structuren): Cyclische groepen (zoals een klokwijzer) en Vectorruimten (meerdimensionale roosters).

De Grote Vraag: Hoe klein kan het team zijn?

Wiskundigen wisten al dat de omvang van het team niet minuscuul kon zijn. Als je kamer $N$ plekken heeft, moet het team ongeveer de wortel van $N$ groot zijn (bijv. als de kamer 100 plekken heeft, heb je minstens 10 mensen nodig).

De grote vraag die dit artikel beantwoordt is: Is die wortel-limiet het beste wat we kunnen doen, of hebben we een veel groter team nodig?

De auteurs zeggen: "Je hebt geen veel groter team nodig. De wortel-limiet is in feite het beste wat we kunnen doen."

Hier is hoe ze het oplosten voor de twee verschillende kamers:

1. De Klokkamer (Cyclische Groepen)

Stel je een klok voor met $m$ uren. De getallen draaien rond (na 12 komt 1).

Het Probleem: Vind de kleinste groep getallen op deze klok die geen rechte lijnen heeft, maar als je een ander getal toevoegt, ontstaat er een lijn.
De Oude Gok: Vorig werk suggereerde dat je misschien ongeveer $1,5 \times \sqrt{m}$ mensen nodig zou hebben.
Het Nieuwe Resultaat: De auteurs hebben een specifiek recept gemaakt om deze groepen te creëren. Ze bewezen dat je voor elke klokgrootte altijd een groep kunt vinden die kleiner is dan $2 \times \sqrt{m}$ .
- Analogie: Als je een klok hebt met 10.000 uur, heb je niet 10.000 mensen nodig. Je hebt slechts ongeveer 200 mensen nodig om aan de regels te voldoen.
De "Super" Regel: Voor de meeste grote klokken vermeden ze niet alleen lijnen; ze vermeden een specifiek, strenger type lijnpatroon genaamd een "(2, -1) patroon." Dit is also'n zeggen: "Niet alleen mag je niet in een rechte lijn staan, je mag zelfs niet in een specif kind type zig-zag patroon staan."
De "Catch": Voor zeer kleine klokken (minder dan 81 uur) werkt de "super" regel niet altijd, dus hebben ze die specifieke kleine gevallen één voor één gecontroleerd met een computer.

2. Het Meerdimensionale Rooster (Vectorruimten)

Stel je nu een kamer voor die niet een klok is, maar een rooster dat in veel richtingen uitstrekt (dimensies). Denk aan een 3D-videospelwereld, maar dan met $n$ dimensies.

Het Probleem: Vind het kleinste team in dit $n$ -dimensionale rooster dat geen rechte lijnen heeft, maar wel "compleet" is (niet meer uitgebreid kan worden).
De Uitdaging: In deze roosters wordt de wiskunde erg lastig, vooral wanneer het rooster een specifiek type getallensysteem gebruikt (oneven priemvelden).
Het Nieuwe Resultaat: De auteurs gebruikten een slimme truc met gekromde oppervlakken (kwadratische grafieken).
- Analogie: Stel je voor dat je mensen op een glooiende heuvel plaatst. Omdat de heuvel gebogen is, is het heel moeilijk voor drie mensen om per ongeluk precies in een rechte lijn te staan.
- Ze bouwden een team op een groot deel van het rooster met behulp van deze glooiende heuvel-methode. Voor de resterende lege plekken vulden ze de gaten aan met een standaard "veilig" team.
De Uitkomst: Ze bewezen dat voor elk vastgesteld type rooster, de teamgrootte ongeveer $\sqrt{N}$ is (waarbij $N$ $N$ het totaal aantal plekken is), plus een klein beetje extra "onzekerheid" die verwaarloosbaar wordt naarmate het rooster enorm groot wordt.
- In gewone taal: De teamgrootte groeit met dezelfde snelheid als de wortel van de totale grootte van de kamer. Je hebt geen enorm leger nodig; de wortel-limiet is in essentie de perfecte grootte.

Het "Geheime Ingrediënt" van het Artikel

De auteurs gebruikten twee hoofdinstrumenten om hun teams te bouwen:

Het "Binaire" Recept (voor Klokken): Ze creëerden een verzameling getallen gebaseerd op een speciaal patroon van optellen en overslaan (zoals een binaire code). Dit stelde hen in staat om het team compact te verpakken zonder lijnen te vormen, terwijl ze ervoor zorgden dat elke lege plek op de klok "gedekt" werd door het team.
De "Gevormde Heuvel" Truc (voor Roosters): Ze gebruikten algebraïsche krommen (vergelijkingen die lijken op parabolen) om mensen te plaatsen. Omdat krommen van nature weerstand bieden tegen rechte lijnen, creëert deze methode zeer efficiënte teams. Vervolgens combineerden ze deze gekromde teams met standaard teams om elke dimensie te dekken.

Wat ze Niet Zeiden

Ze zeiden niet dat dit directe toepassingen heeft in cryptografie, geneeskunde of techniek. Dit is pure wiskunde over de structuur van getallen.
Ze beweerden niet dat ze het absoluut kleinste team voor elk enkel geval hadden gevonden (het "perfecte" team). Ze vonden teams die zeer dicht bij de theoretische limiet liggen (binnen een kleine constante factor).
Ze zeiden niet dat ze het probleem voor elk type getallensysteem hadden opgelost (ze richtten zich specif으로 op oneven priemvelden voor de roosters).

Samenvatting

Beschouw dit artikel als een meesterbouwer die ons laat zien hoe we de kleinst mogelijke omheining rond een veld kunnen bouwen.

Het Doel: De omheining moet sterk genoeg zijn zodat als je probeert nog één post toe te voegen, de omheining breekt (een lijn vormt).
De Ontdekking: De bouwer bewees dat je geen enorme omheining nodig hebt. Je hebt alleen een omheining nodig waarvan de lengte ongeveer de wortel is van de grootte van het veld.
De Methode: Ze gebruikten slimme patronen (zoals binaire codes) en gebogen vormen (zoals heuvels) om de hekpalen zo compact mogelijk te verpakken zonder dat ze een rechte lijn vormen.

Dit bevestigt dat de "wortel-regel" niet alleen een ondergrens is; het is in essentie de werkelijke omvang van het probleem.

Technische Samenvatting: Kleine Volledige 3-Term Progressie-vrije Sets in Cyclische Groepen en Vectorenruimten

Probleemstelling
Het artikel behandelt het probleem van het bepalen van de minimale grootte van een volledige 3-term rekenkundige progressie (3-AP) vrije verzameling in algebraïsche structuren, specifgens cyclische groepen ( $\mathbb{Z}_m$ ) en eindige vectorenruimten ( $\mathbb{F}_p^n$ ). Terwijl de maximale grootte van 3-AP-vrije verzamelingen een centraal thema is in de additieve combinatoriek (bijv. Roths stelling, Croot-Lev-Pach, Ellenberg-Gijswijt), vertegenwoordigt de minimale grootte van een volledige verzameling (een verzameling die niet vergroot kan worden zonder een 3-AP te creëren) het tegenovergestelde aan de onderzijde. Een eenvoudige telling bepaalt dat de orde van grootte voor deze minimale grootte ten minste de vierkantswortel is van de kardinaliteit van de structuur. De auteurs onderzoeken of deze ondergrens nauw aansluit, waarbij zij openstaande problemen adresseren met betrekking tot de existentie van dergelijke verzamelingen met grootte $O(\sqrt{|G|})$ in cyclische groepen en $p^{n/2}$ in vectorenruimten.

Methodologie
De auteurs maken gebruik van een combinatie van expliciete combinatorische constructies, modulaire reductietechnieken en algebraïsche meetkunde over eindige velden.

Cyclische Groepen ( $\mathbb{Z}_m$ ):
- Sterkere Eigenschap: De auteurs richten zich op volledige (2, -1)-vermijdende verzamelingen. Een verzameling $A$ is (2, -1)-vermijdend als $A \cap (2A \dot{-} A) = \emptyset$ (waarbij $2A \dot{-} A = \{2a - b : a, b \in A, a \neq b\}$ ). Een verzameling is volledig als $G = A \cup (2A \dot{-} A)$ . Deze eigenschap is sterker dan het zijn van een volledige 3-AP-vrije verzameling, omdat het afdwingt dat elk punt buiten de verzameling een eindpunt is van een progressie met eindpunten in $A$ , in plaats van dat het buitenpunt een middelpunt mag zijn.
- R-volledige Verzamelingen: De constructie rust op "R-volledige" verzamelingen—gehele getal-verzamelingen in $[0, R]$ die intern (2, -1)-vermijdend zijn en het interval $[-R, 2R]$ verzadigen.
- Binair Digitaal Constructie: Met behulp van een gegeneraliseerde binaire digitale constructie (Lemma 3.3) genereren de auteurs verzamelingen $P$ van grootte $2^n$ die $S_n$ -volledig zijn. Door de digitale sequentie $d_i$ zorgvuldig te kiezen, zorgen zij ervoor dat de resulterende verzameling een breed bereik aan moduli $m$ dekt.
- Modulaire Reductie: Lemma 3.2 toont aan dat een $R$ -volledige verzameling in $\mathbb{Z}$ afdaalt naar een volledige (2, -1)-vermijdende verzameling in $\mathbb{Z}_m$ telkens wanneer $2R < m \leq 3R + 1$ .
- Eindige Verificatie: Voor kleine moduli ( $m < 81$ ) waar de algemene constructie niet van toepassing is of waar volledige (2, -1)-vermijdende verzamelingen mogelijk niet bestaan, voeren de auteurs een uitputtende enumeratie uit om exacte minimale grootten te bepalen.
Vectorenruimten ( $\mathbb{F}_p^n$ ):
- Kwadratische Grafieken: De kernconstructie maakt gebruik van grafieken van homogene kwadratische afbeeldingen $Q: U \to W$ . Specifiek construeren zij verzamelingen van de vorm $A_Q = \{(u, Q(u)) : u \in U\}$ .
- Eindpunt-Middelpunt Volledigheid: De auteurs definiëren "eindpunt-middelpunt volledige" verzamelingen, waarbij elk punt buiten de verzameling zowel als een eindpunt ( $x = 2a - b$ ) als een middelpunt ( $2x = c + d$ ) van een progressie kan worden gerepresenteerd die gevormd wordt door elementen in $A$ . Deze eigenschap is cruciaal voor de productconstructie.
- Subveld Constructie: Zij construeren een kwadratische afbeelding $Q(x, s) = x^2 - \delta s^2$ over een extensieveld $E = \mathbb{F}_{p^{kL}}$ en een subveld $T = \mathbb{F}_{p^k}$ , waarbij $\delta$ een niet-kwadraat is. Met behulp van karakterzommen en de Weil-grens bewijzen zij dat deze afbeelding surjectief is en een triviale kern heeft, wat een volledige (2, -1)-vermijdende verzameling oplevert in een specifieke dimensie $n_0 = k(2L+1)$ .
- Product-Lemma: Om het resultaat naar alle dimensies $n$ uit te breiden, gebruiken zij een product-lemma (Lemma 4.2). Als $A$ eindpunt-middelpunt volledig is in een onderruimte en $B$ volledig 3-AP-vrij is in de resterende coördinaten, dan is hun product $A \times B$ volledig 3-AP-vrij in de volledige ruimte. Dit maakt het mogelijk om de speciale dimensies op te vullen met kleinere verzamelingen om willekeurige $n$ te dekken.

Belangrijkste Bijdragen en Resultaten

Cyclische Groepen:
- Stelling 1.2: Voor elke integer $m \geq 1$ bestaat er een volledige 3-AP-vrije verzameling $A \subseteq \mathbb{Z}_m$ met grootte $|A| < 2\sqrt{m}$ .
- Sterker Resultaat voor Grote $m$ : Voor $m \geq 81$ voldoet de geconstrueerde verzameling aan de sterkere volledige (2, -1)-vermijdende eigenschap.
- Kleine Moduli: Het artikel levert een tabel met exacte waarden voor $a(3\text{-AP}, \mathbb{Z}_m)$ en $a(2, -1)(\mathbb{Z}_m)$ voor $m \leq 80$ , waarbij wordt opgemerkt dat volledige (2, -1)-vermijdende verzamelingen niet bestaan voor bepaalde kleine moduli (bijv. $m \in \{2, 5, 6, 8, 17, 18, 19, 20\}$ ).
Vectorenruimten:
- Stelling 1.3: Voor elke vaste oneven priem $p$ en $\epsilon > 0$ , bestaat er een constante $C_{p,\epsilon}$ zodanig dat voor alle $n \geq 1$ :
  $a(3\text{-AP}, \mathbb{F}_p^n) \leq C_{p,\epsilon} n^{1+\epsilon} p^{n/2} = p^{n/2 + o(n)}$
- Dit resultaat lost de variant voor vectorenruimten op in de zin dat de exponent van $p$ exact $n/2$ is, wat de ondergrens benadert tot een sub-exponentiële factor.

Betekenis en Claims
Het artikel claimt twee openstaande problemen te hebben opgelost met betrekking tot de nauwheid van de wortel-ondergrens voor volledige progressie-vrije verzamelingen:

Cyclische Groepen: Het stelt vast dat de ondergrens nauw aansluit bij een absolute constante (specifiek 2) voor alle cyclische groepen, en biedt expliciete constructies voor de sterkere (2, -1)-vermijdende eigenschap voor $m \geq 81$ .
Vectorenruimten: Het beslecht de exponentversie van het probleem voor vaste oneven priemvelden, waarbij wordt aangetoond dat de minimale grootte $p^{n/2 + o(n)}$ is. Dit bevestigt dat de triviale telling-ondergrens essentieel scherp is in termen van de exponentiële groei.

De auteurs merken op dat hoewel de constante factor in het resultaat voor cyclische groepen ($2$) boven de $3/2$ ligt die in hun vorige werk werd gesuggereerd, de constructie doelbewust beperkt is tot de sterkere (2, -1)-vermijdende eigenschap. Zij suggereren dat het benutten van de extra vrijheid van standaard 3-AP-volledigheid (waarbij buitenstaande punten ook een middelpunt kunnen zijn) kleinere constructies zou kunnen opleveren. Evenzo blijft voor vectorenruimten de vraag of er een uniforme absolute constante onafhankelijk van $n$ bestaat en of er dergelijke grenzen bestaan voor volledige (2, -1)-vermijdende verzamelingen in elke dimensie. Het werk verbindt deze additieve combinatorische problemen met eindige meetkunde, specifiek volledige caps en verzadigende verzamelingen.