Welke soort wiskunde beheersen LLM's goed?

Deze resultaten, en de andere acht op de lijst, zijn buitengewoon indrukwekkend, maar het lijkt nog steeds niet het geval te zijn dat LLM's in alle aspecten van de wiskunde beter zijn dan alle mensen. Als dat wel zo was, zou hun grote snelheidsvoordeel ten opzichte van ons betekenen dat er een veel grotere vloedgolf aan resultaten zou zijn. Het is daarom natuurlijk om ons af te vragen naar welke soorten problemen LLM's goed zijn en waar er nog ruimte is voor verbetering. Ik pretendeer niet een definitief antwoord op deze vraag te hebben — waarbij een goed antwoord een scherpe classificatie zou zijn die goed past bij de huidige voorbeelden — maar het is een interessante oefening om sommige foutieve antwoorden uit te sluiten en potentiële antwoorden te identificeren die niet overduidelijk worden weersproken door het bewijsmateriaal.

Zijn LLM's bijzonder goed in het vinden van tegenvoorbeelden?

Een eerste opmerking hier is dat LLM's niet alleen goed zijn in het vinden van tegenvoorbeelden: ze kunnen ook bewijzen vinden voor moeilijke stellingen. Het is echter opvallend dat de beroemdste problemen die ze hebben opgelost, bijna allemaal betrekking hadden op tegenvoorbeelden in plaats van bewijzen. Dat geldt voor de twee eerder genoemde problemen, maar ook voor het Jacobiaanse vermoeden en het unit distance vermoeden.

Als men wil theoriseren dat LLM's bijzonder goed zijn in het vinden van tegenvoorbeelden, dan zijn er twee zaken die nodig zijn om deze theorie overtuigender te maken. Ten eerste moet worden bepaald wanneer het oplossen van een probleem telt als het vinden van een tegenvoorbeeld. Zodra dat is uitgezocht, is de tweede stap het bedenken van een potentiële verklaring waarom LLM's bijzonder goed geschikt zouden zijn voor het oplossen van problemen van dit specifieke type.

Wat betekent het om een tegenvoorbeeld te vinden?

Waarom suggereer ik dat het niet volledig duidelijk is wat het betekent om een tegenvoorbeeld te vinden? Men zou kunnen suggereren dat het simpelweg betekent dat je een bewering hebt van de vorm "elk object van zodanig type heeft zodanige eigenschap," en dat je vervolgens een object van dat type tentoonstelt dat die eigenschap niet heeft.

Dit werkt echter niet altijd. Neem bijvoorbeeld een beroemd resultaat van Vinogradov, waarin staat dat elk voldoende groot positief geheel getal een som is van drie priemgetallen. De ontkenning van deze bewering is (of is equivalent aan) de stelling dat er voor elk positief geheel getal $n$ een getal $k$ bestaat zodanig dat $k$ geen som is van drie priemgetallen. Met andere woorden: het stelt dat elk positief geheel getal $k$ een bepaalde eigenschap heeft. Gezien vanuit dit perspectief vond Vinogradov een voorbeeld van een positief geheel getal $k$ dat de gegeven eigenschap niet heeft. Willen we dan zeggen dat Vinogradov een tegenvoorbeeld vond? Absoluut niet — het resultaat moet overduidelijk worden geclassificeerd als een stelling en niet als een tegenvoorbeeld.

We kunnen dus niet naïef zeggen dat LLM's bijzonder goed zijn in het ontkennen van universeel gekwantificeerde beweringen: er moet iets zijn aan de aard van de universele kwantificatie. In het voorbeeld met de drie priemgetallen is het duidelijk dat Vinogradov niet dacht: "Hoe ga ik een $k$ vinden met deze eigenschap?" In plaats daarvan zou hij eerder hebben gedacht: "Ik heb een geheel getal $n$ dat zeer groot is. Hoe ga ik aantonen dat dit een som is van drie priemgetallen?" Met andere woorden, al zijn focus lag op de universeel gekwantificeerde $n$, waarbij de existentieel gekwantificeerde $k$ een soort bijzaak was zodra de details van het bewijs waren uitgewerkt.

In het algemeen beginnen veel interessante resultaten, wanneer ze formeel worden geformuleerd, met een alternatie van twee of drie (of meer) kwantificatoren. De vraag is dan om te bepalen welke de eerste "interessante" gekwantificeerde variabele is.

Voorbeeld: Het Banach-Mazur compactum

Om dit punt te illustreren, volgt hier een voorbeeld uit de theorie van einddimensionale genormeerde ruimtes.

Stel dat $X$ en $Y$ twee $n$-dimensionale genormeerde ruimtes zijn en laat $T$ een lineaire afbeelding zijn van $X$ naar $Y$. We zeggen dat $T$ een $C$-isomorfisme is als er een $C$ bestaat zodanig dat $\|T\| \cdot \|T^{-1}\| \le C$ voor elke $x$. Door schaling kunnen we $C$ altijd op 1 stellen, in welk geval we hebben dat $\|Tx\| = \|x\|$ voor elke $x$. Als $C=1$, dan is $T$ een isometrie. In het algemeen is de Banach-Mazur afstand $d(X, Y)$ tussen $X$ en $Y$ gedefinieerd als de kleinste $C$ zodanig dat er een $C$-isomorfisme bestaat van $X$ naar $Y$. De logaritme van de Banach-Mazur afstand is een metriek op de verzameling isometrieklassen van $n$-dimensionale genormeerde ruimtes. Deze metrieke ruimte is compact en staat bekend als het Banach-Mazur compactum.

Het is natuurlijk om ons af te vragen wat de diameter van het Banach-Mazur compactum is. Een resultaat van Fritz John stelt dat elke $n$-dimensionale ruimte $X$ een afstand van maximaal $n$ heeft tot $\ell_2^n$. Hieruit volgt dat voor elke twee $n$-dimensionale genormeerde ruimtes geldt dat $d(X, Y) \le n$. De diameter is dus maximaal $n$, maar zou deze aanzienlijk kleiner kunnen zijn?

In 1981 loste Gluskin dit probleem op door de correcte asymptotiek voor de diameter te bepalen. Informeel toonde hij aan dat de diameter binnen een constante factor van de bovengrens uit het theorema van Fritz John ligt. Expliciet geformuleerd: er bestaat een positieve constante $C$ zodanig dat voor elk positief geheel getal $n$ ruimtes $X$ en $Y$ bestaan zodanig dat de Banach-Mazur afstand tussen $X$ en $Y$ ten minste $Cn$ is.

Gluskin gebruikte hiervoor een prachtige idee: hij koos $X$ and $Y$ als genormeerde ruimtes waarvan de eenheidsballen willekeurige symmetrische convexe verzamelingen waren, gedefinieerd door de convexe huls van standaardbasisvectoren en een handvol andere willekeurige eenheidsvectoren (en hun negatieven). Hij toonde aan dat als twee ruimtes uit deze distributie werden gekozen, hun Banach-Mazur afstand met hoge waarschijnlijkheid ten minste $Cn$ was.

De logische vorm van Gluskins bewering is zeer vergelijkbaar met die van Vinogradovs theorema. Toch is het resultaat van Vinogradov onmiskenbaar een stelling, terwijl dat van Gluskin onmiskenbaar een tegenvoorbeeld (of in ieder geval een voorbeeld) is.

Wat is het belangrijke verschil tussen deze twee beweringen?

Het lijkt erop dat in Vinogradovs theorema over de drie priemgetallen het getal $n$ een essentieelere rol speelt in de bewering die bewezen moet worden. De uitdaging daar is om die drie priemgetallen precies op te tellen tot $n$. Bij Gluskin is het daarentegen totaal niet uitdagend om de dimensies van $X$ en $Y$ gelijk te maken aan $n$; de uitdaging is om $X$ en $Y$ zeer ver van elkaar te krijgen, relatief aan hun gemeenschappelijke dimensie.

Er is een verdere complicatie: via het proces genaamd Skolemization kan een universeel gekwantificeerde bewering van de vorm $\forall n \exists X P(n, X)$ worden omgezet in een existentieel gekwantificeerde bewering $\exists f \forall n P(n, f(n))$. Dit weerspiegelt vaak hoe we over problemen nadenken. Het is natuurlijker om Gluskins voorbeeld te zien als een recept voor het construeren van een paar geschikte ruimtes voor elke gegeven dimensie $n$, dan als een bewering dat elk positief geheel getal $n$ een bepaalde complexe eigenschap heeft.

Een andere complicatie is dat sommige universele beweringen natuurlijk voortvloeien uit existentiële beweringen. Bijvoorbeeld, de stelling dat een 2-dimensionale torus niet homeomorf is aan een 2-dimensionale sfeer is existentieel (elke afbeelding faalt als homeomorfisme), maar de natuurlijke manier om dit te bewijzen is door een invariant te vinden die de twee ruimtes onderscheidt.

Een algemener argument tegen het idee dat existentiële beweringen bijzonder geschikt zijn voor AI, is dat de noodzaak om existentiële beweringen vast te stellen doordringt in bijna alle wiskundige research. Of men nu een inductiebewijs voert of zoekt naar een versterking van een hypothese; het gaat vaak om existentievragen. Wanneer we proberen een stelling $P$ te bewijzen, is de belangrijkste vraag in ons hoofd vaak niet "Waarom is $P$ waar?", maar "Hoe zou een bewijs van $P$ eruit kunnen zien?".

Wat is het verschil tussen een voorbeeld en een tegenvoorbeeld?

Logisch gezien is elke bewering van de vorm $\exists X \neg P(X)$ een tegenvoorbeeld voor de universele bewering $\forall X P(X)$. Toch noemen we niet alle existentiële beweringen tegenvoorbeelden. Als ik zou zeggen: "De $\ellp$-ruimtes met $p < \infty$ zijn allemaal separabel, maar $\ell\infty$ is dat niet," dan zou ik het tweede deel niet beschrijven als een tegenvoorbeeld voor de claim dat alle Banach-ruimten separabel zijn. Ik zou het presenteren als het meest basale voorbeeld van een niet-separabele ruimte.

Het belangrijkste punt lijkt te zijn dat we eerder geneigd zijn een object een tegenvoorbeeld te noemen als het bestaan van dat object een bewering weerlegt die we voor goede redenen geloofden.

Mijn indruk is dat de constructie van een niet-sofische groep in deze categorie valt. Er waren al diverse voorstellen in de literatuur over hoe men zo'n groep zou kunnen construeren, en ik denk niet dat er veel experts waren die sterk geloofden dat alle groepen sofisch waren. Daarom voelt het natuurlijker om te zeggen: "OpenAI kwam met het eerste voorbeeld van een niet-sofische groep" dan te zeggen: "OpenAI vond een tegenvoorbeeld voor het soficiteitsvermoeden".

Hetzelfde geldt voor de nieuwe ondergrens voor meerkleuren Ramsey-getallen. Voor sommigen was het een tegenvoorbeeld omdat zij geloofden dat de grens exponentieel moest zijn, maar voor anderen (mijzelf inclusief) was het een voorbeeld van wat ik zwakjes verwachtte.

Waar laat dit ons?

Ik zou graag een coherente verklaring vinden voor de combinatie van de volgende feiten:

1. De meest opvallende wiskundige resultaten van LLM's neigen naar voorbeelden of tegenvoorbeelden (existentiebeweringen die beweringen weerleggen die we verwachtten dat waar waren).
2. Veel beweringen kunnen zowel als existentieel als universeel worden geformuleerd; wat we een "voorbeeld" noemen hangt af van de context en niet alleen van de logische vorm.
3. LLM's zijn ook redelijk goed in het bewijzen van universele beweringen, maar de sterkste stellingen die ze hebben bewezen, bereiken nog niet het niveau van de sterkste tegenvoorbeelden die ze hebben gevonden.

Het lijkt waarschijnlijk dat LLM's goed zijn in iets anders, wat als consequentie heeft dat ze goed zijn in het soort existentieproblemen dat we normaal gesproken classificeren als het zoeken naar een niet-triviaal voorbeeld.

Laten we kijken naar twee zaken waarvan we zeker weten dat LLM's daar goed in zijn:

• Brede kennis: Als een probleem kan worden opgelost met een relatief standaardargument, is de kans groot dat een LLM dit vindt en gebruikt.
• Snelheid (computerkracht): Een LLM kan op enorme snelheid werken en kan het zich veroorloven om een groot aantal mislukte pogingen te doen voordat het een oplossing vindt.

Dit suggereert dat LLM's een voordeel hebben wanneer er een probabilistisch element in het bewijs-zoekproces zit: ze zijn goed in problemen waarbij de beste methode is om veel ideeën te proberen totdat je geluk hebt. Mensen zijn daarentegen (voorlopig) beter in het vinden van "verrassende" en "conceptuele" argumenten, waarbij de juiste methode is om steeds dieper in een probleem te graven tot de oplossing zich openbaart.

De "LLM-stijl" vs. de menselijke "neus"

Deze "menselijke neus" voor onderzoek stelt ons in staat om de zoekboom drastisch te snoeien. LLM's lijken dit nog niet op dezelfde manier te doen. In mijn interacties met ChatGPT heb ik de indruk dat ze benaderingen presenteren die veelbelovend klinken tot je er zorgvuldig over nadenkt, waarna ze minder promising blijken. Ze reduceren een probleem vaak tot een smallere vraag, maar zonder dat er wezenlijke progressie wordt geboekt.

Het is niet onmogelijk dat deze "neus" een emergente eigenschap is van training en scaling, maar vooralsnog lijkt het erop dat LLM's vertrouwen op hun superieure snelheid en kennis om de combinatorische explosie te overleven, in plaats van de zoekboom effectief te snoeien.

Om te begrijpen waarom LLM's goed zijn in (tegen)voorbeelden, kunnen we kijken naar verschillende methoden voor het vinden van voorbeelden:

• Zoeken naar een standaardvoorbeeld: Het testen van een set bekende "stock" voorbeelden.
• Opbouwen uit basisvoorbeelden: Starten met standaardvoorbeelden en deze combineren via producten, quotiënten of limieten.
• Gebruik maken van metavariabelen: Werken met variabelen ("waarbij $X$ later gekozen wordt") om eigenschappen vast te leggen voordat het object volledig is gespecificeerd.
• Het tegenovergestelde proberen te bewijzen: Proberen $\forall X P(X)$ te bewijzen om zo een sleutellemma of een zwakkere eigenschap te vinden die makkelijker te weerleggen is.
• Opeenvolgende benadering: Een plausibele gok doen, diagnosticeren waarom deze faalt, en de gok verfijnen.
• 'Gewoon-doen'-bewijzen (Just-do-it proofs): Het inductief stukje bij beetje bouwen van een object dat aan oneindig veel eigenschappen moet voldoen.
• Een willekeurig voorbeeld kiezen: Gebruik maken van de probabilistische methode om aan te tonen dat een willekeurig gekozen object met hoge waarschijnlijkheid aan de eisen voldoet.
• Een generiek voorbeeld kiezen: Aantonen dat de verzameling objecten die niet aan de eigenschap voldoen, klein is (bijv. maat nul).

Het is aannemelijk dat LLM's bijzonder goed zijn in methoden zoals het checken van standaardvoorbeelden, 'gewoon-doen'-bewijzen en de probabilistische methode. De methoden die meer intuïtie vereisen over welke richting vruchtbaar is (zoals metavariabelen of opeenvolgende benadering), blijven waarschijnlijk langer het domein van de menselijke wiskundige.

Conclusie

Mijn belangrijkste conclusies zijn als volgt:

1. "Een voorbeeld vinden" is in de praktijk niet hetzelfde als het bewijzen van een bewering die begint met een existentiële kwantificator.
2. Als huidige modellen bijzonder goed zijn in het vinden van voorbeelden, komt dat waarschijnlijk niet door een affiniteit voor existentiële beweringen, maar omdat de methoden die hiervoor nodig zijn (brede kennis en brute-force exploratie) precies aansluiten bij de sterktes van LLM's.
3. Mensen behouden voorlopig het voordeel bij problemen waarbij de zoekboom zo diep en breed is dat rigoureus snoeien (via intuïtie/de "neus") essentieel is om tot een oplossing te komen.

Een echt teken dat LLM's het menselijke niveau hebben bereikt voor een veel bredere klasse van problemen, zal zijn wanneer ze stellingen bewijzen met methoden die nieuw en verrassend zijn, maar achteraf gezien prachtig en natuurlijk aanvoelen — methoden die je niet per ongeluk vindt door simpelweg heel veel opties te proberen.