The sum-product problem for small sets II

Dit artikel bewijst dat elke verzameling van 10 of 11 natuurlijke getallen minstens respectievelijk 30 of 34 verschillende sommen of producten genereert, en levert een classificatie van de uitzonderlijke gevallen die deze drempels niet overschrijden.

De kern

De Som-Multiplicatie Raadsel: Een Verhaal over Getallen die Samenwerken

Stel je voor dat je een groep vrienden hebt. Je wilt weten hoe "sociaal" deze groep is. Je kunt dit op twee manieren meten:

1. De Som: Je laat elke twee vrienden een getal optellen. Hoeveel verschillende antwoorden krijg je?
2. De Product: Je laat elke twee vrienden een getal vermenigvuldigen. Hoeveel verschillende antwoorden krijg je hier?

In de wiskunde heet dit het Som-Product Probleem. De grote vraag is: Kun je een groep kiezen waarbij je heel weinig verschillende antwoorden krijgt op beide vragen tegelijk?

De wiskundigen in dit paper (Phillip, Holden, Caleigh, Elizabeth, Alex en Elyse) hebben gekeken naar groepjes van 10 en 11 natuurlijke getallen. Hun conclusie is verrassend simpel maar diep: Het is onmogelijk om op beide fronten "slim" te zijn.

De Analogie: De "Slimme" Groep

Stel je voor dat je een team samenstelt voor een spel.

• Als je kiest voor een rekenrij (bijv. 1, 2, 3, 4, 5...), dan zijn je sommen heel voorspelbaar en weinig (je krijgt weinig nieuwe antwoorden). Maar je vermenigvuldigingen worden een chaos: 1x2, 1x3, 2x3, 2x4... dat levert honderden verschillende producten op.
• Als je kiest voor een vermenigvuldigingsrij (bijv. 2, 4, 8, 16...), dan zijn je producten heel voorspelbaar. Maar je sommen (2+4=6, 2+8=10, 4+8=12...) worden weer een wirwar van nieuwe getallen.

De wiskundigen wilden weten: Is er een groepje van 10 getallen dat de "gouden middenweg" vindt? Een groepje dat zowel bij optellen als bij vermenigvuldigen heel weinig nieuwe getallen produceert?

Het Nieuwe Ontdekking

Voor groepjes van 1 tot 9 getallen wisten ze al het antwoord. Maar bij 10 getallen was het een raadsel.

Deze onderzoekers hebben bewezen dat voor elke groep van 10 getallen, je minstens 30 verschillende antwoorden moet hebben, ofwel bij het optellen, ofwel bij het vermenigvuldigen. Je kunt niet onder de 30 uitkomen op beide vlakken tegelijk.

En het mooiste deel? Er is maar één enkele groep (tot op schaling na) die precies op de grens zit. Dat is de groep:
{1, 2, 3, 4, 6, 8, 9, 12, 16, 18}

Dit is de "ultieme slimme groep". Als je deze getallen optelt, krijg je 30 unieke antwoorden. Als je ze vermenigvuldigt, krijg je 29 unieke antwoorden. Je kunt niet beter. Als je ook maar één getal verandert, krijg je op minstens één van de twee vlakken meer dan 30 antwoorden.

Voor een groep van 11 getallen is de grens 34. De winnende groep is hetzelfde als hierboven, maar dan met het getal 24 erbij.

Hoe hebben ze dit bewezen? (De "Computerspel"-methode)

Dit is geen probleem dat je op een kladblaadje kunt oplossen. De onderzoekers gebruikten een slimme combinatie van oude wiskundige theorieën en moderne computerkracht.

1. De "Architecten" (Freiman's theorie): Ze begonnen met de idee dat als een groepje getallen weinig sommen heeft, het eruit moet zien als een strakke rij (een rekenrij) of een combinatie van twee rijen.
2. De "Detective" (Python-code): Ze schreven een computerprogramma (een soort digitale detective) dat alle mogelijke structuren van deze getalrijen doorzoekt. Het programma bouwde groepjes op, steen voor steen, en keek of ze nog steeds onder de limiet van 30 bleven.
3. De "Valstrikken" (Collisions): Soms "botsen" sommen tegen elkaar. Bijvoorbeeld: $2 + 6 = 8$en$3 + 5 = 8$. Dit is een "botsing" (collision). De computer telde precies hoeveel van deze botsingen er mogelijk zijn. Ze ontdekten dat er maar heel specifieke, zeldzame combinaties zijn waarbij je genoeg botsingen krijgt om onder de limiet te blijven.
4. De "Uitzonderingen": Ze vonden een lijst met "verdachte" combinaties van getallen (zoals specifieke verhoudingen tussen 2 en 3). Voor elk van deze verdachten checkten ze handmatig of ze echt onder de limiet bleven.

Waarom is dit belangrijk?

Het klinkt misschien als een droge rekensom, maar het gaat over de fundamentele structuur van getallen.

• Het laat zien dat wiskundige patronen (zoals optellen en vermenigvuldigen) vaak met elkaar op de loop gaan. Je kunt niet in beide werelden tegelijk "slim" zijn.
• Het is een stap in de richting van een groter mysterie: hoe gedragen zich getallen als je groepen heel groot worden? (De onderzoekers noemen dit de "treacherous path" of gevaarlijke weg voor groepen groter dan 11).

Samenvatting in één zin

De onderzoekers hebben bewezen dat er voor groepjes van 10 of 11 getallen maar één "perfecte" combinatie bestaat die zo min mogelijk nieuwe antwoorden geeft bij zowel optellen als vermenigvuldigen, en dat elke andere combinatie erger is; ze hebben dit gedaan door slimme wiskunde te combineren met een enorme hoeveelheid computerrekenkracht om alle mogelijke "valstrikken" te vinden.

Kortom: Je kunt niet winnen op twee fronten tegelijk. De natuur dwingt je om te kiezen: of je bent goed in optellen, of je bent goed in vermenigvuldigen, maar niet in beide tegelijk (tenzij je precies die ene magische groep van 10 getallen kiest).

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "The Sum-Product Problem for Small Sets II" van Antis et al., gepresenteerd in het Nederlands.

Titel: The Sum-Product Problem for Small Sets II

Auteurs: Phillip Antis, Holden Britt, Caleigh Chapman, Elizabeth Hawkins, Alex Rice, Elyse Warren.

---

1. Het Probleem

Het artikel richt zich op het klassieke som-productprobleem in de additieve combinatoriek, geïnitieerd door Erdős en Szemerédi in de jaren 80. Het centrale vraagstuk is: in hoeverre kunnen eindige deelverzamelingen $A$ van de gehele getallen (of reële getallen) tegelijkertijd een klein aantal verschillende sommen ($|A+A|$) en een klein aantal verschillende producten ($|AA|$) genereren?

De auteurs definiëren $SP(k)$ als het minimum van het maximum van het aantal sommen en producten voor een verzameling van $k$ natuurlijke getallen:
$$SP(k) = \min_{A \subseteq \mathbb{N}, |A|=k} \left( \max\{|A+A|, |AA|\} \right)$$

De algemene conjectuur is dat $SP(k) = k^{2-o(1)}$, wat impliceert dat een verzameling niet zowel een zeer kleine sommenverzameling als een zeer kleine productverzameling kan hebben. Hoewel de asymptotische groei intensief bestudeerd is, focust dit artikel op exacte waarden voor kleine $k$. Eerdere werk (van Rice et al., 2025) had de exacte waarden vastgesteld voor $k \leq 9$. Dit artikel breidt dit uit naar $k=10$ en $k=11$.

2. Methodologie

De aanpak combineert structurele classificatietheorie (gebaseerd op Freiman's theorema's) met uitgebreide computationele zoektochten. De redenering verloopt als volgt:

1. Logaritmische Transformatie:
   Om het probleem te analyseren, wordt de verzameling $A$ getransformeerd naar $L = \{\log_r(a) : a \in A\}$, waarbij $r$ het kleinste element van $A$ (na 1) is. Hierdoor wordt het productprobleem omgezet in een somprobleem in $L$. Als $|AA|$ klein is, dan is $|L+L|$ klein.

2. Classificatie van Structuren (Theorema's 1.2 & 1.3):
   Als een verzameling $L$ een klein aantal sommen heeft, moet deze een specifieke structuur hebben:

   • Deel van één rekenkundige rij.
   • Een vereniging van twee rekenkundige rijen met dezelfde stapgrootte.
   • Voor $k=10$ en $k=11$ met $|L+L| \leq 29$ (resp. 33) zijn de klassieke theorema's van Freiman niet direct toepasbaar omdat de grenzen net buiten hun directe classificatie vallen.

3. Computationele Classificatie (Algoritme WinnersSearch):
   De auteurs ontwikkelen een recursief algoritme (WinnersSearch) om alle mogelijke structuren van $L$ te vinden die voldoen aan de beperkingen van de sommen.

   • Ze zoeken naar verzamelingen $P \subseteq \mathbb{Z}^2$ die corresponderen met $L = \{m + n\alpha : (m,n) \in P\}$, waarbij $\alpha$ irrationaal is.
   • Dit leidt tot de conclusie dat als $L$ niet in één rekenkundige rij zit, deze moet bestaan uit elementen van een twee-dimensionale geometrische progressie van de vorm $\{r^m s^n\}$.
   • Specifiek worden twee hoofdstructuren geïdentificeerd:
     • $G_1 = \{r^m s^n : 0 \leq m \leq 7, n \in \{0, 1\}\}$
     • $G_2 = \{r^m s^n : 0 \leq m \leq 3, 0 \leq n \leq 2\}$

4. Controle van "Collisions" (Sommen die samenvallen):
   Om de exacte waarde van $|A+A|$ te bepalen, moeten de auteurs tellen hoeveel sommen "kollideren" (d.w.z. $a+b = c+d$ met verschillende paren).

   • Ze analyseren systemen van bivariate polynomen om oplossingen te vinden voor vergelijkingen zoals $r^a + r^b = s^c r^d + \dots$.
   • Ze identificeren uitzonderlijke paren $(r, s)$ waarbij extra kollities optreden (bijv. dubbele kollities).
   • Voor niet-uitzonderlijke paren wordt bewezen dat het aantal kollities beperkt is, wat leidt tot een ondergrens voor $|A+A|$.

5. Verificatie:
   Voor alle geïdentificeerde structuren en uitzonderlijke $(r, s)$-paren wordt computergestuurd gecontroleerd of er een verzameling bestaat met minder dan de verwachte sommen.

3. Belangrijkste Resultaten

Hoofdstelling (Theorema 1.5):
De auteurs bewijzen de exacte waarden voor $k=10$ en $k=11$:

• $SP(10) = 30$
• $SP(11) = 34$

Uniciteit:
De verzamelingen die deze waarden bereiken, zijn uniek (tot op schaling):

• Voor $k=10$: $A = \{1, 2, 3, 4, 6, 8, 9, 12, 16, 18\}$.
  • $|A+A| = 30$, $|AA| = 29$.
• Voor $k=11$: $A = \{1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24\}$.
  • $|A+A| = 34$, $|AA| = 32$.

Classificatie van Realen:
Het artikel bevat ook classificatieresultaten voor verzamelingen van reële getallen. Bijvoorbeeld, als een verzameling van 10 reële getallen maximaal 29 sommen heeft en geen 8 elementen bevat in één rekenkundige rij, dan moet deze een specifieke tweedimensionale structuur hebben.

Toekomstige Grenzen:
Voor $k=12$ wordt de conjectuur $SP(12) = 41$ ondersteund door het voorbeeld $\{1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 32\}$. Voor $k=13$ lijkt de structuur echter te breken; het beste voorbeeld is een driedimensionale structuur, wat aangeeft dat de huidige methoden voor $k > 11$ mogelijk niet meer voldoende zijn zonder nieuwe inzichten.

4. Significatie en Bijdrage

1. Doorbraak in Exacte Waarden: Dit is een van de eerste werken dat de exacte waarden van $SP(k)$ voor $k=10$ en $k=11$ vaststelt, een stap die eerder als te moeilijk werd beschouwd omdat de klassieke Freiman-theorema's niet direct toepasbaar waren op deze specifieke drempels.
2. Methodologische Innovatie: De paper demonstreert de kracht van het combineren van diepe structurele wiskunde (Freiman-theorie) met brute-force computationele zoektochten. Het gebruik van Python en Jupyter Notebooks voor het doorzoeken van polynoomsystemen en het tellen van kollities is een model voor toekomstig onderzoek in de additieve combinatoriek.
3. Classificatie van Uitzonderingen: De auteurs leveren een complete lijst van "uitzonderlijke" $(r, s)$-paren die extra kollities veroorzaken. Dit biedt een gedetailleerd inzicht in de randgevallen van het som-productprobleem.
4. Openbare Code: Alle code en output zijn openbaar beschikbaar gemaakt, wat reproduceerbaarheid en verdere research door anderen mogelijk maakt.

Kortom, dit artikel sluit een belangrijke kloof in de kennis over het som-productprobleem voor kleine verzamelingen en levert een robuust raamwerk voor het analyseren van de structuur van verzamelingen met kleine som- en productgroottes.