🔢 mathematics

Resolution of Erdős Problem #728: a writeup of Aristotle's Lean proof

Dit artikel presenteert de eerste volledig autonome AI-resolutie van Erdős Probleem #728, gebruikmakend van een combinatie van GPT-5.2 Pro en het Aristotle-systeem om een formeel Lean-bewijs te genereren dat een logaritmisch-gap-fenomeen in faculteit-deelbaarheid aantoont door middel van een nieuwe priemgetal-voor-priemgetal-analyse van binomiale coëfficiënten.

Oorspronkelijke auteurs: Nat Sothanaphan

Gepubliceerd 2026-01-27

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Nat Sothanaphan

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

Het Grote Plaatje: Een Team van AI-Wiskundigen

Stel je een beroemde, gepensioneerde wiskundige genie voor, Paul Erdős, die zijn leven doorbracht met het achterlaten van een gigantische "to-do"-lijst van onopgeloste puzzels. Een van deze puzzels, #728, ligt al decennia onberoerd.

Onlangs heeft een team bestaande uit een superintelligente AI (GPT-5.2 Pro) en een gespecialiseerde wiskunde-controlerende robot (Aristoteles) het eindelijk opgelost. Ze hebben niet alleen het antwoord geraden; ze hebben een rigoureus, stapsgewijs bewijs gebouwd dat een computer kan verifiëren als 100% correct. De auteurs van dit papier zijn simpelweg die computercode aan het vertalen naar een verhaal dat mensen kunnen lezen.

De Puzzel: De Factoriële Balansact

De vraag gaat over faculteiten (getallen zoals $5! = 5 \times 4 \times 3 \times 2 \times 1$ ).

Stel je voor dat je een enorme stapel blokken hebt die $n!$ vertegenwoordigen. Je wilt zien of je twee kleinere torens kunt bouwen, $a!$ en $b!$ , en een derde kleine toren $k!$ , zodanig dat de twee kleine torens perfect in de grote passen zonder dat er blokken overblijven.

Wiskundig gezien betekent dit: Deelt $a! \times b!$ gelijkmatig in $n! \times k!$ ?

De puzzel vraagt: Hoe groot kan de "kloof" ( $k$ ) zijn?

Als $k$ klein is, is het makkelijk om de blokken te laten passen.
Als $k$ enorm groot is, is het meestal onmogelijk.
De truc is om een "Goldilocks-zone" te vinden waar $k$ groot genoeg is om interessant te zijn, maar niet zo groot dat de blokken niet meer passen.

Het AI-team bewees dat je oneindig veel situaties kunt vinden waarin deze kloof ( $k$ ) ongeveer de grootte heeft van de logaritme van het totaal aantal. In gewone mensentaal: als je totaal aantal blokken een miljoen is, kan de kloof rond de 14 liggen. Als je aantal een miljard is, kan de kloof rond de 20 liggen. Het groeit heel langzaam, maar het groeit wel.

De Strategie: Het "Overdracht"-spel

Om dit op te lossen, moesten de wiskundigen naar het probleem kijken door de lens van priemgetallen (2, 3, 5, 7, enz.). Ze gebruikten een regel genaamd Kummer's Theorema, wat lijkt op een spel van "overdrachten" bij optellen.

De Analogie: De Overstromende Emmer
Stel je voor dat je getallen optelt in een specifieke taal (basis $p$ ).

Wanneer je twee cijfers optelt en het resultaat is te groot voor één positie, "draag" je het extra deel over naar de volgende positie.
Het Doel: De AI moest een getal ( $m$ ) vinden dat, wanneer het verdubbeld wordt, zorgt voor veel overdrachten (zoals een emmer die herhaaldelijk overstroomt).
De Obstakel: Tegelijkertijd moest de AI ervoor zorgen dat de getallen die direct op $m$ volgen (zoals $m+1, m+2...$ ) geen "pieken" hadden—plotselinge, enorme deelbaarheid door een priemgetal die de balans zou verstoren.

Denk hierbij aan het lopen over een koorddanserslijn:

Het Koord (De "Overdracht"-conditie): Je moet een getal kiezen dat "rijk" is aan overdrachten. Wanneer je het verdubbelt, moet het zijn emmers zo vaak mogelijk laten overlopen. Dit creëert een "veiligheidsnet" van deelbaarheid dat helpt om de vergelijking te laten werken.
De Pieken (De "Slechte" conditie): Je moet getallen vermijden waarbij de volgende paar gehele getallen deelbaar zijn door enorme machten van een priemgetal. Dit zijn "pieken" die je van het koord kunnen werpen.

Hoe Ze de Oplossing Vonden

De AI koos niet zomaar een willekeurig getal. Het gebruikte een telargument (een statistische strategie):

Het Zoekgebied: Ze keken naar een enorme reeks getallen (van $M$ tot $2M$ ).
De Filter: Ze berekenden hoeveel getallen in deze reeks "slecht" waren (of ze hadden niet genoeg overdrachten, of ze hadden een piek).
Het Resultaat: Ze bewezen dat het aantal "slechte" kandidaten eigenlijk kleiner is dan het totaal aantal kandidjes in de reeks.
De Conclusie: Omdat er meer getallen zijn dan "slechte" getallen, moet er in de stapel ten minste één "goed" getal overblijven.

Het is alsof je zegt: "Als je een pot hebt met 1.000 knikkers, en slechts 900 daarvan zijn rood (slecht), dan moeten er ten minste 100 blauwe (goede) overblijven." De AI bewees dat voor elke groot genoeg pot, er altijd een "goed" knikkertje bestaat.

Waarom Dit Belangrijk Is (Volgens het Papier)

Eerste AI-alleen Bewijs: Dit is de eerste keer dat een AI-systeem autonoom een van de beroemde problemen van Erdős heeft opgelost en een formeel bewijs heeft geproduceerd dat mensen kunnen verifiëren.
De "Logaritmische Kloof": Ze bevestigden dat de kloof tussen de getallen logaritmisch kan zijn. Hoewel het papier opmerkt dat de kloof potentieel iets groter zou kunnen zijn (zoals gesuggereerd door wiskundige Terence Tao), vestigt dit bewijs een solide, gegarandeerde basislijn.
Methodologie: De gebruikte methode (het tellen van overdrachten en het vermijden van pieken) is vergelijkbaar met technieken die Erdős zelf in het verleden gebruikte, maar toegepast op een complexer, bewegend doelwit.

Samenvatting

Het papier is een verslag over hoe een AI-team een 40 jaar oude wiskundepuzzel heeft opgelost. Ze lieten zien dat je altijd een specifieke set getallen kunt vinden waarbij een complexe faculteelvergelijking perfect in balans is. Ze deden dit door getallen te behandelen als emmers die overstromen (overdrachten) en door te bewijzen dat je altijd een emmer kunt vinden die net genoeg overstroomt om nuttig te zijn, zonder dat er te veel op de verkeerde plekken wordt gemorst.

Technische Samenvatting: Resolutie van Erdős Probleem #728

Probleemstelling
Het artikel behandelt Erdős Probleem #728, dat de maximale mogelijke grootte van de kloof $k := a + b - n$ onderzoekt onder de beperking van faculteitsdeelbaarheid:
$a! b! \mid n! (a + b - n)!$
Zonder aanvullende beperkingen bestaan er triviale oplossingen waarbij $k$ willekeurig groot kan zijn (bijvoorbeeld door $a$ en $b$ zeer groot te maken). Om het probleem niet-triviaal te maken, leggen de auteurs de voorwaarde op dat $a$ en $b$ afgeweken zijn van de extremen, specifiek $\varepsilon n \le a, b \le (1-\varepsilon)n$ voor een bepaalde $0 < \varepsilon < 1/2$ . Het doel is om te bepalen hoe groot $k$ kan zijn ten opzime van $n$ onder deze beperkingen.

Methodologie en Bewijsstrategie
Het bewijs verloopt door de faculteitsdeelbaarheidsvoorwaarde te transformeren naar een probleem betreffende binomiale coëfficiënten en $p$ -adische waarderingen.

Reductie naar Binomiale Deelbaarheid:
Door $n = 2m$ , $b = m$ , en $a = m + k$ te stellen, is de oorspronkelijke voorwaarde equivalent aan:
$\binom{m+k}{k} \mid \binom{2m}{m}$
Dit vereist het aantonen dat voor elke priem $p$ , de $p$ -adische waardering van de linkerzijde kleiner dan of gelijk is aan die van de rechterzijde:
$\nu_p\left(\binom{m+k}{k}\right) \le \nu_p\left(\binom{2m}{m}\right)$
Waarderingsanalyse via Kummer's Stelling:
Gebruikmakend van Kummer's stelling, wordt $\nu_p\left(\binom{2m}{m}\right)$ geïdentificeerd met het aantal carries (overdrachten) dat optreedt bij het optellen van $m + m$ in basis $p$ . De term $\nu_p\left(\binom{m+k}{k}\right)$ wordt begrensd door de maximale waardering van een term in het opeenvolgende blok $m+1, \dots, m+k$ , aangeduid als $V_p(m, k)$ .
De kernongelijkheid die voldaan moet worden is:
$V_p(m, k) \le \kappa_p(m)$
waarbij $\kappa_p(m)$ het aantal carries is voor $m+m$ in basis $p$ .
Priem-per-priem Analyse:
De auteurs splitsen de analyse op in twee regimes gebaseerd op de grootte van de priem $p$ relatief aan $k$ :
- Grote Priemen ( $p > 2k$ ): In dit bereik wordt de ongelijkheid automatisch voldaan. Omdat de intervallengte $k$ kleiner is dan $p/2$ , kan maximaal één getal in het blok $m+1, \dots, m+k$ deelbaar zijn door $p$ . Als een hoge macht $p^J$ een term deelt, dwingen de basis- $p$ cijfers van $m$ ten minste $J$ carries af bij het verdubbelen, wat aan de voorwaarde voldoet.
- Kleine Priemen ( $p \le 2k$ ): Dit is de belangrijkste moeilijkheid. De auteurs gebruiken een probabilistische telmethode om een geheel getal $m$ $m$ in een groot interval $[M, 2M]$ $[M, 2 M]$ te vinden dat simultaan twee voorwaarden voldoet voor alle $p \le 2k$ $p \leq 2 k$ :
  - Carry-Rich: De basis- $p$ expansie van $m$ heeft veel cijfers $\ge \lceil p/2 \rceil$ in de eerste $L_p$ posities. Dit dwingt een hoog aantal carries ( $\kappa_p(m)$ ) af wanneer $m$ wordt verdubbeld.
  - Spike-Free: Geen geheel getal in het blok $m+1, \dots, m+k$ is deelbaar door een ongebruikelijk hoge macht van $p$ (specifiek wordt $V_p(m, k)$ onder een drempel $J_p + t(M)$ gehouden).
Bestaan via de Union Bound:
De auteurs definiëren "slechte" verzamelingen van gehele getallen $m$ die ofwel niet voldoen aan de carry-voorwaarde of de spike-voorwaarde. Door gebruik te maken van Chernoff-bounds voor de distributie van grote cijfers en eenvoudige telling voor de spike-voorwaarde, tonen zij aan dat de totale maat van deze slechte verzamelingen strikt kleiner is dan de grootte van het interval $[M, 2M]$ . Bijgevolg bestaat er een "goed" $m$ dat de deelbaarheidsvoorwaarde voor alle relevante priemgetallen simultaan vervult.

Kernresultaten
Het artikel vestigt Stelling 1 (Logaritmisch kloofvenster):
Voor elke constanten $0 < C_1 < C_2$ en $0 < \varepsilon < 1/2$ , bestaan er oneindig veel triples $(a, b, n) \in \mathbb{N}^3$ waarvoor:

$\varepsilon n \le a, b \le (1-\varepsilon)n$
$a! b! \mid n! (a + b - n)!$
$C_1 \log n < a + b - n < C_2 \log n$

De constructie levert een kloof $k$ op die logaritmisch groeit met $n$ . De auteurs merken op dat de huidige bewijsvoering $k \asymp \log n$ oplevert, maar dat de methode potentieel uitgebreid kan worden naar $k = \exp(c\sqrt{\log n})$ met verdere verfijning, hoewel de huidige tekst zich richt op het logaritmische regime.

Betekenis en Claims

Eerste door AI opgeloste Erdős Probleem: De auteurs claimen dat dit het eerste Erdős probleem is dat "volledig autonoom door een AI-systeem is opgelost". Het systeem dat werd gebruikt, was een combinatie van GPT-5.2 Pro en de theorem prover "Aristotle" van Harmonic.
Formele Verificatie: Het bewijs is gegenereerd als een formeel bewijs in de Lean theorem prover en is vervolgens vertaald naar de informele wiskunde gepresenteerd in deze samenvatting.
Methodologische Bijdrage: Het werk breidt eerdere technieken van Erdős en Pomerance met betrekking tot de delers van centrale binomiale coëfficiënten uit. In tegenstelling tot eerder werk dat zich richtte op "carry-poor" gehele getallen (weinig carries) of vaste kloofgroottes, construeert dit bewijs "carry-rich" gehele getallen om een groeiend venster van grootte $k \asymp \log n$ te behandelen.
Onafhankelijkheid: De auteurs merken op dat na hun initiële werk, Carl Pomerance onafhankelijk vergelijkbare resultaten heeft afgeleid, en dat aanpassingen van dit argument werden gebruikt om Erdős Problemen #729 en #401 op te lossen.

Het artikel beweert niet het probleem in zijn absoluut sterkst mogelijke vorm te hebben opgelost (er wordt opgemerkt dat grotere kloven mogelijk zijn), maar stelt de succesvolle resolutie van de specifieke logaritmische kloofvraag gesteld door Erdős vast.