Constructing strong starters of orders $3p$: triplication with SAT solver

Dit artikel presenteert een nieuwe 'triplicatie'-methode die, met behulp van een SAT-oplosser, sterke starters in cyclische groepen van orde $3p$construeert uit starters van orde$p$, waarmee een bijdrage wordt geleverd aan het bewijs van Hortons conjectuur.

De kern

Stel je voor dat wiskunde een enorme, ingewikkelde puzzel is, en dat deze puzzelstukjes "starters" heten. Deze starters zijn speciale groepen getallen die op een heel specifieke manier aan elkaar gekoppeld moeten worden. Ze worden gebruikt om complexe patronen te maken, net zoals je met LEGO-blokjes een heel specifiek model bouwt.

Deze wetenschappers (Oleg, Sergey en Margo) hebben een nieuwe manier bedacht om deze puzzelstukjes te maken, vooral voor situaties waar het totale aantal stukjes deelbaar is door 3 (zoals 21, 33, 39, enz.).

Hier is hoe hun methode werkt, vertaald naar alledaagse taal:

1. Het uitgangspunt: Een klein, perfect model

Stel je hebt een klein, perfect gebouwd huisje van 7 blokken (dit is hun "basis-starters"). Dit huisje is al in orde; alle blokken passen precies.
De vraag is: Hoe bouw je nu een enorm kasteel van 21 blokken (3 keer zo groot) dat ook perfect in elkaar zit?

2. De "Triplicatie": Verdubbelen en Verdrievoudigen

De naam van hun methode is "Triplicatie" (vermenigvuldiging met drie).
In plaats van het kasteel van nul af te bouwen, nemen ze dat kleine huisje van 7 blokken en zeggen ze: "Laten we dit drie keer kopiëren, maar dan een beetje verdraaid."

Ze maken drie kopieën van het kleine huisje:

1. De originele versie.
2. Een versie die een beetje is verschoven (alsof je de muren iets naar rechts schuift).
3. Een versie die is gespiegeld en verschoven.

Als je deze drie kopieën op een rijtje zet, krijg je een groot raster van 21 vakjes. Maar hier zit de twist: als je ze zomaar samenvoegt, kloppen de patronen niet. De blokken raken elkaar niet goed aan.

3. De Sudoku-probleem: De "Kleuren"

Hier komt het slimme deel. Om de drie kopieën perfect te laten samensmelten, moeten ze aan elk blokje een kleur geven. Er zijn maar drie kleuren beschikbaar: Rood, Geel en Blauw (in de wiskunde: 0, 1 en 2).

Ze moeten een Sudoku oplossen, maar dan in een heel vreemd jasje:

• De regel: In elke rij van hun grote raster moeten de kleuren zo worden verdeeld dat ze niet botsen.
• Het doel: Als ze de juiste kleuren op de juiste plekken zetten, "ontgrendelt" het hele systeem. De drie losse kopieën worden dan één groot, perfect kasteel.

Het probleem is dat ze niet precies weten welke kleur op welke plek moet komen. Het is als een Sudoku-puzzel waarbij je niet weet welke cijfers waar moeten, maar je wel weet dat ze aan heel specifieke, strenge regels moeten voldoen.

4. De "Supercomputer" (De SAT-solver)

Hoe vinden ze de oplossing voor deze Sudoku? Ze gebruiken een computerprogramma dat een "Super-Detective" wordt genoemd (in de wiskunde een SAT-solver, specifiek de software 'z3').

• Hoe werkt de detective? Stel je voor dat je een detective bent die duizenden verdachten heeft. Je hebt een lijst met regels (bijvoorbeeld: "De dader draagt geen rode jas" of "Als de dader links zit, moet hij rechts een hoed dragen"). De detective probeert razendsnel alle mogelijke combinaties te testen tot hij de ene combinatie vindt die aan alle regels voldoet.
• In dit geval test de computer programma duizenden manieren om de kleuren (0, 1, 2) in het raster te zetten totdat hij de perfecte oplossing vindt.

5. Waarom is dit belangrijk?

Sinds 1989 hebben wiskundigen een raadsel: "Bestaan deze perfecte starters altijd als het aantal blokken deelbaar is door 3?" Niemand kon het bewijzen, maar ze vermoedden van wel.

Deze auteurs zeggen: "We hoeven het niet te bewijzen met alleen maar papier en pen. We kunnen het bouwen!"

• Ze nemen een bewezen klein voorbeeld.
• Ze gebruiken de "Sudoku-methode" om er een groot voorbeeld van te maken.
• De computer lost de Sudoku op en bouwt het grote voorbeeld.

Samenvattend met een metafoor

Stel je voor dat je een recept hebt voor een perfecte taart van 7 laagjes. Je wilt nu een enorme taart van 21 laagjes maken.

1. Je neemt je recept en maakt er drie kopieën van.
2. Je weet dat je de drie lagen op een specifieke manier moet stapelen, maar je weet niet precies welke vulling (chocolade, aardbei, vanille) tussen welke lagen moet.
3. Je gebruikt een slimme robot (de SAT-solver) om alle mogelijke combinaties van vullingen te testen.
4. Zodra de robot de juiste combinatie vindt, heb je een perfecte, enorme taart van 21 laagjes.

Deze methode laat zien dat je grote, complexe wiskundige problemen kunt oplossen door ze op te splitsen in een klein, bekend probleem en een "Sudoku-puzzel" die een computer voor je oplost. Het is een brug tussen oude wiskundige theorie en moderne computertechnologie.

Technische samenvatting

Titel: Constructie van sterke starters van orde $3p$: verdrievoudiging met een SAT-oplosser

Auteurs: Oleg Ogandzhanyants, Sergey Sadov, Margo Kondratieva
Publicatiedatum: Juni 2025 (arXiv)

---

1. Probleemstelling

Het paper richt zich op de constructie van sterke starters (strong starters) in cyclische groepen $Z_n$ waarbij $n$ een oneven getal is dat deelbaar is door 3.

• Definitie: Een sterke starter in $Z_n$ is een partitie van de verzameling $\{1, 2, \dots, n-1\}$ in paren $\{a_i, b_i\}$ zodanig dat:
  1. Alle sommen $a_i + b_i$ verschillend en niet-nul zijn modulo $n$.
  2. Alle verschillen $\pm(a_i - b_i)$ verschillend en niet-nul zijn modulo $n$.
• De Uitdaging: Het bestaan van sterke starters is bewezen voor alle oneven $n$ die niet deelbaar zijn door 3 (behalve $n=3, 5, 9$). Voor $n$ die wel deelbaar zijn door 3 (specifiek $n=3p$ met $\gcd(p,3)=1$) is het bestaan echter slechts gedeeltelijk bewezen. De Horton-conjecture (1989) stelt dat sterke starters bestaan voor alle oneven $n$ behalve $n=3, 5, 9$, maar dit is voor $n=3p > 1000$ theoretisch nog niet bewezen.
• Doel: Een nieuwe, praktische methode ontwikkelen om sterke starters van orde $3p$te construeren uit een bestaande sterke starter van orde$p$.

2. Methodologie: Verdrievoudiging (Triplication)

De auteurs introduceren een constructiemethode genaamd "triplication". Deze methode reduceert het probleem van het vinden van een sterke starter van orde $3p$ tot het oplossen van een speciaal type Sudoku-achtig probleem modulo 3.

Het proces verloopt als volgt:

1. Basis: Start met een sterke starter $T$ van orde $p$ (waarbij $\gcd(p,3)=1$) en kies een "sleutel" $t \in \{0, \dots, p-1\}$.
2. Constructie van $\Sigma_p$: Er wordt een uitbreidingstabel $\Sigma_p$ gemaakt met $3q+1$paren (waarbij$q=(p-1)/2$). Deze tabel bestaat uit drie kolommen:
   • Kolom 1: De originele starter $T$.
   • Kolom 2: De translatie $T+t$ (modulo $p$).
   • Kolom 3: Een gespiegelde en getranslateerde versie $T-t$.
   • De bovenste rij bevat het paar $(t, t)$.
3. Het Sudoku-probleem modulo 3:
   • Er wordt een tabel $\Sigma_3$ geïntroduceerd met onbekende waarden $U_i, V_i \in \{0, 1, 2\}$.
   • Deze waarden moeten voldoen aan drie soorten constraints (beperkingen) afgeleid van de structuur van $\Sigma_p$:
     • Rij-constraints: De verschillen $U_i - V_i$ in elke rij moeten modulo 3 verschillend zijn.
     • Zwakke verzameling-constraints (Weak Sets): Paren in $\Sigma_p$ met dezelfde som modulo $p$ moeten in $\Sigma_3$ corresponderen met paren met verschillende sommen modulo 3 (en niet-nul voor som 0).
     • Kleur-drietal-constraints (Monochrome sets): Posities in $\Sigma_p$ met dezelfde numerieke waarde moeten in $\Sigma_3$ verschillende waarden aannemen.
4. Oplossing en Reconstructie:
   • Als een oplossing voor $\Sigma_3$ bestaat, wordt de uiteindelijke sterke starter $S$ van orde $3p$gereconstrueerd met behulp van de **Chinese Reststelling (CRT)**. De elementen$a_i, b_i$van$S$ voldoen aan:
     $$a_i \equiv u_i \pmod p, \quad a_i \equiv U_i \pmod 3$$
     (en analoog voor $b_i$).

3. Belangrijkste Bijdragen

• Nieuwe Constructiemethode: De paper presenteert een algoritme dat het bestaan van sterke starters voor $n=3p$ koppelt aan de oplosbaarheid van een constraint-satisfaction probleem (CSP) modulo 3.
• Theoretische Bewijzen:
  • Stelling 1: Een oplossing van het Sudoku-probleem modulo 3 garandeert het bestaan van een sterke starter van orde $3p$.
  • Stelling 2: Een noodzakelijke voorwaarde voor oplosbaarheid is dat de sleutel $t$ niet gelijk mag zijn aan 0 en niet mag voorkomen in de sommen van paren van de basisstarter $T$.
  • Stelling 3: Oplossingen komen in paren voor door een permutatie van de waarden 1 en 2 modulo 3.
• Omgekeerd Probleem: Er wordt een algoritme gepresenteerd om te testen of een bestaande sterke starter van orde $3p$ via deze "triplication"-methode is gegenereerd.
• Praktische Implementatie: De auteurs demonstreren de haalbaarheid door het probleem op te lossen met de algemene SAT-oplosser z3 (Microsoft).

4. Resultaten en Prestaties

De auteurs hebben numerieke experimenten uitgevoerd op een Intel i7 processor met 32GB RAM, gebruikmakend van Python en de z3-bibliotheek.

• Schaalbaarheid:
  • Voor basisstarters met orde $m < 100$: De gemiddelde oplostijd varieert van 0,065 seconden ($m=7$) tot ongeveer 90 seconden ($m=97$). De tijd groeit ongeveer volgens een kwadratische trend ($\tau \approx m^2 \ln m$).
  • Voor grotere ordes ($100 < m < 500$): De tijden nemen toe tot enkele duizenden seconden (bijv. ~20.000 seconden voor$m=439$). De groei lijkt niet strikt monotoon, maar volgt over het algemeen een exponentiële of hoge polynoomtrend.
• Vergelijking met directe zoektocht:
  • Het direct zoeken naar een sterke starter van orde 39 met z3 duurt ongeveer 200 seconden.
  • Het gebruik van de triplication-methode (startend met een starter van orde 13) duurt minder dan 1 seconde. Dit toont aan dat de methode aanzienlijk efficiënter is dan brute-force zoektochten voor grotere groepen.
• Randomness: Er is geobserveerd dat de oplostijd sterk varieert afhankelijk van de gekozen sleutel $t$, zelfs voor dezelfde basisstarter.

5. Betekenis en Conclusie

• Invulling van een theoretische lacune: Hoewel de Horton-conjecture nog niet volledig bewezen is, biedt deze methode een krachtig instrument om het bestaan van sterke starters voor $n=3p$ te verifiëren en te construeren voor waarden die theoretisch nog onzeker waren.
• Efficiëntie: De combinatie van een slimme constructieve aanpak (reductie naar een kleiner probleem) met moderne SAT-oplossers is bewezen superieur aan directe zoekalgoritmen of hill-climbing voor specifieke ordes.
• Toekomstperspectief: De auteurs merken op dat een gespecialiseerd algoritme voor het oplossen van dit specifieke Sudoku-probleem modulo 3 waarschijnlijk veel efficiënter zal zijn dan de algemene z3-solver. Ze plannen dit in een vervolgpaper te presenteren.
• Beperking: Niet elke sterke starter van orde $3p$ kan via deze methode worden gegenereerd (zoals geïllustreerd in de voorbeelden), maar de methode dekt een aanzienlijk deel van de mogelijke oplossingen.

Samenvattend biedt dit paper een brug tussen combinatorisch ontwerp en constraint satisfaction, met een succesvolle toepassing op een langdurig openstaand probleem in de groepentheorie.