Het artikel beschrijft hoe frontier AI-modellen (GPT-5.6 en Claude Fable) een decennia oud probleem in de draadloze communicatie hebben opgelost: de MIMO-detectie.
De kern van het probleem Sinds het begin van de jaren 2000 was bekend dat het theoretisch mogelijk is om $N$ bits perfect te herstellen via een $N \times N$ Gaussisch draadloos kanaal wanneer de signaal-ruisverhouding (SNR) ten minste $2 \log N$ is. Echter, dit kon tot nu toe alleen worden bereikt met exponentiële zoekalgoritmen, wat het in de praktijk ondoenlijk maakte.
De AI-oplossing Door middel van intensieve interactie met GPT en Claude heeft de auteur een bewijs ontwikkeld voor een algoritme met polynomiale complexiteit dat slaagt bij exact dezelfde drempelwaarde. Het algoritme combineert LMMSE (Linear Minimum Mean Square Error) afronding met greedy bit-flipping. Na vijf dagen van verfijning en handmatige controle is het bewijs als correct geclassificeerd.
Conclusie over AI in de wetenschap De auteur merkt op dat er geen nieuwe wiskunde is uitgevonden. De kracht van de AI lag in het assembleren van bestaande, bekende technieken tot een sluitend geheel—een taak die menselijke onderzoekers al lang hadden laten varen.
AI lost een 25 jaar oud probleem op dat we achterlieten
Het resultaat: wanneer je $N$ bits verstuurt via een $N \times N$ Gaussisch draadloos kanaal, moet de ontvanger al deze bits exact kunnen herstellen. Sinds de jaren 2000 is bekend dat dit informatietheoretisch mogelijk is wanneer de signaal-ruisverhouding (SNR) ten minste $2 \log N$ is. Tot nu toe was het enige bekende methode om dit te bereiken een exponentieel zoekalgoritme. Er is nu echter bewijs dat een eenvoudig algoritme met polynomiale complexiteit slaagt bij exact dezelfde drempelwaarde.
Wat is MIMO-detectie?
Een zender stuurt een vector van $N$ bits via een draadloos kanaal met $N$ zend- en $N$ ontvangstantennes. Het kanaal mengt de bits en voegt ruis toe. De ontvanger, die de kanaalmatrix kent, moet vervolgens achterhalen welke bits er zijn verzonden.
De blokfout-optimale ontvanger, ook wel de maximum likelihood (ML) detector genoemd, lost dit probleem op door de meest waarschijnlijke vector te vinden die verzonden zou kunnen zijn, gegeven het ontvangen signaal. In dit geval komt ML-detectie neer op het oplossen van een fundamenteel discreet kleinste-kwadratenprobleem.
Helaas is ML-detectie NP-hard. Omdat draadloze kanalen echter willekeurig zijn en niet het slechtst denkbare scenario (worst-case) vertegenwoordigen, stelde de gemeenschap sinds begin 2000 de volgende vraag: kunnen we de verzonden bits in polynomiale tijd herstellen wanneer dit statistisch mogelijk is?
Dit probleem bleef, voor zover ik weet, een kwart eeuw open staan. Het antwoord is nu: Ja. Telkens wanneer perfecte detectie statistisch mogelijk is, kan dit in polynomiale tijd worden gedaan. MIMO-detectie is hiermee opgelost.
De technische context
Bij dit probleem verzend je een binaire vector $x$ in $\{\pm 1\}^N$, en ontvang je:
${\bf y} = \sqrt{\frac{SNR}{N}}{\bf H}{\bf x}+{\bf w}$
Hierbij is $H$ een $N \times N$ matrix, waarbij zowel $H$ als $w$ onafhankelijke iid $N(0,1)$ elementen hebben. De ontvanger kent $H$ en de ruisstatistieken, maar niet $w$, en wil $x$ herstellen uit $y$.
Deze optimalisatie komt in verschillende vormen voor: MIMO-detectie, CDMA multi-user detectie, integer least squares en het vinden van de dichtstbijzijnde vector in een rooster.
Wanneer $\text{SNR} = \infty$ (geen ruis), is het probleem triviaal: de kanaalmatrix $H$ is met waarschijnlijkheid 1 omkeerbaar, waardoor $x$ direct kan worden hersteld via $\text{inv}(H) \cdot y$. Bij $\text{SNR} = 0$ faalt ML-detectie volledig. Tussen deze twee extremen in slaagt ML-detectie precies bij $\text{SNR} = 2 \log N$. Boven deze drempelwaarde kan de verzonden $N$-bit sequentie perfect worden hersteld, maar het oplossen hiervan leek tot nu toe een uitputtende zoektocht over alle mogelijke binaire sequenties te vereisen.
Een korte geschiedenis
De vraag naar de oplosbaarheid van het integer least squares probleem dateert van ten minste 1989, toen Verdú bewees dat het in het algemene geval NP-hard is.
In 2001 beargumenteerden Hassibi en Vikalo dat er hoop was voor een polynomiale oplossing in het gemiddelde geval via de Sphere Decoder (SD). Hoewel SD in de praktijk snel leek, toonden Jaldén en Ottersten in 2005 aan dat de verwachte complexiteit van sphere decoding bij elke vaste SNR in feite exponentieel is ten opzichte van de dimensie van het probleem.
Vervolgens richtte het vakgebied zich op benaderingen van het ML-optimalisatieprobleem:
- Semidefinite relaxations: Bood garanties bij hoge SNR, maar geen scherpe drempelwaarde.
- Bit-flipping local search: Leek in simulaties op ML, maar miste volledige bewijzen.
- AMP (Approximate Message Passing): Karakteriseerde de fout per bit, maar niet het blokherstel.
- MCMC-methoden: In een paper uit 2010 werd bewezen dat de stationaire distributie massa plaatst op de correcte oplossing, maar de mengtijd (het lastige deel) bleef onbewezen.
In 2020 verscheen de box relaxation, die blokherstel kon garanderen wanneer de SNR schaalde als $4 \log N$, maar niet daaronder. De kloof tussen wat ML bereikte en wat een polynomiale methode kon bewijzen, bleef dus bestaan.
Hoe GPT en Claude het probleem oplosten
Gestimuleerd door de successen van frontier-modellen in complexe wiskunde, heb ik GPT-5.6 en Claude Fable gevraagd wanneer ML MIMO-detectie in polynomiale tijd kan worden opgelost. Beiden produceerden bewijzen voor verschillende algoritmen die stelden dat er geen kloof is: er bestaat een polynomiaal-tijdsalgoritme dat slaagt bij $\text{SNR} > 2 \log N$.
Het proces om dit te verifiëren was intensief:
- Algoritmekeuze: GPT stelde een AMP-variant voor, maar Claude suggereerde signed LMMSE, gevolgd door greedy bit flips—een methode die in de praktijk al bekend was.
- Correctie: GPT wees erop dat het bewijs van Claude grotendeels onjuist was, maar wel redbaar. Ik vroeg GPT om het bewijs van Claude te repareren.
- Vereenvoudiging: Het resultaat was aanvankelijk onleesbaar door een muur van complexe notaties en exotische matrixanalyse. Ik heb vervolgens vier tot vijf dagen besteed aan het heen-en-weer prompten met beide modellen om de stappen zo simpel mogelijk te maken, zodat ik ze zelf kon verifiëren zonder externe tools zoals Lean.
Het resultaat is een bewijs dat ik regel voor regel heb gecontroleerd en dat correct is. Het produceren van het initiële bewijs nam 30 minuten in beslag; het verifieerbaar maken ervan kostte vijf dagen.
De kern van het bewijs
Het algoritme is verrassend eenvoudig:
- LMMSE en afronding: Dit brengt je, in termen van Hamming-afstand, binnen een fractie ($o(N)$) van het verzonden signaal.
- Greedy bit-flipping: Omdat de daling per stap wordt bepaald door Gaussische grootheden, is er altijd een verbeterende bit-flip mogelijk zolang men zich niet op de grondwaarheid bevindt.
- Kostenbarrière: Hoewel de Hamming-afstand tijdelijk kan toenemen, zorgt de kostenfunctie ervoor dat het algoritme binnen een bepaalde "bal" blijft. De startkosten liggen niet veel boven het optimum en elke stap verlaagt de kosten met een bedrag dat begrensd is vanaf nul.
- Convergentie: Hierdoor moet het proces na $N \log N$ stappen stoppen. De enige plek waar het algoritme kan stoppen zonder verdere verbetering mogelijk te zijn, is bij de verzonden vector.
Reflecties over AI en vergeten problemen
In 2010 zou dit resultaat waarschijnlijk hebben geleid tot prestigieuze prijzen en aanbiedingen van topuniversiteiten. Nu is het vakgebied grotendeels verder gegaan. Er zijn veel problemen die decennialang belangrijk waren, maar vervolgens werden verlaten—niet omdat ze onmogelijk waren, maar omdat men er simpelweg mee stopte zich ermee bezig te houden.
Het is fascinerend dat je nu met AI terug kunt gaan naar deze "verlaten hoeken" van de literatuur en ze kunt oplossen voor een paar honderd dollar per maand.
Een belangrijke observatie over het bewijs is dat er geen nieuwe wiskunde is uitgevonden. Er zijn geen nieuwe ongelijkheden of technieken gebruikt die in 2010 niet al bestonden. De moeilijkheid zat niet in conceptuele vernieuwing, maar in de enorme inspanning om twintig pagina's aan standaardstappen perfect op elkaar af te stemmen.
Dit definieert een klasse van problemen waarvan de oplossing geen nieuwe wiskunde vereist, maar enkel de assemblage van bekende ideeën over een lengte die langer is dan iemand bereid was te besteden. AI is uitmuntend in het herhaaldelijk proberen van combinaties totdat iets klikt. Deze modellen zijn wellicht distillaties van onze geaccumuleerde instincten, aangescherpt door Reinforcement Learning.
We weten nu: MIMO ML-detectie is eenvoudig, zodra het mogelijk is.
AI lost een 25 jaar oud probleem op dat we achterlieten
Het resultaat: wanneer je $N$ bits verstuurt via een $N \times N$ Gaussisch draadloos kanaal, moet de ontvanger al deze bits exact kunnen herstellen. Sinds de jaren 2000 is bekend dat dit informatietheoretisch mogelijk is wanneer de signaal-ruisverhouding (SNR) ten minste $2 \log N$ is. Tot nu toe was het enige bekende methode om dit te bereiken een exponentieel zoekalgoritme. Er is nu echter bewijs dat een eenvoudig algoritme met polynomiale complexiteit slaagt bij exact dezelfde drempelwaarde.
Wat is MIMO-detectie?
Een zender stuurt een vector van $N$ bits via een draadloos kanaal met $N$ zend- en $N$ ontvangstantennes. Het kanaal mengt de bits en voegt ruis toe. De ontvanger, die de kanaalmatrix kent, moet vervolgens achterhalen welke bits er zijn verzonden.
De blokfout-optimale ontvanger, ook wel de maximum likelihood (ML) detector genoemd, lost dit probleem op door de meest waarschijnlijke vector te vinden die verzonden zou kunnen zijn, gegeven het ontvangen signaal. In dit geval komt ML-detectie neer op het oplossen van een fundamenteel discreet kleinste-kwadratenprobleem.
Helaas is ML-detectie NP-hard. Omdat draadloze kanalen echter willekeurig zijn en niet het slechtst denkbare scenario (worst-case) vertegenwoordigen, stelde de gemeenschap sinds begin 2000 de volgende vraag: kunnen we de verzonden bits in polynomiale tijd herstellen wanneer dit statistisch mogelijk is?
Dit probleem bleef, voor zover ik weet, een kwart eeuw open staan. Het antwoord is nu: Ja. Telkens wanneer perfecte detectie statistisch mogelijk is, kan dit in polynomiale tijd worden gedaan. MIMO-detectie is hiermee opgelost.
De technische context
Bij dit probleem verzend je een binaire vector $x$ in $\{\pm 1\}^N$, en ontvang je:
${\bf y} = \sqrt{\frac{SNR}{N}}{\bf H}{\bf x}+{\bf w}$
Hierbij is $H$ een $N \times N$ matrix, waarbij zowel $H$ als $w$ onafhankelijke iid $N(0,1)$ elementen hebben. De ontvanger kent $H$ en de ruisstatistieken, maar niet $w$, en wil $x$ herstellen uit $y$.
Deze optimalisatie komt in verschillende vormen voor: MIMO-detectie, CDMA multi-user detectie, integer least squares en het vinden van de dichtstbijzijnde vector in een rooster.
Wanneer $\text{SNR} = \infty$ (geen ruis), is het probleem triviaal: de kanaalmatrix $H$ is met waarschijnlijkheid 1 omkeerbaar, waardoor $x$ direct kan worden hersteld via $\text{inv}(H) \cdot y$. Bij $\text{SNR} = 0$ faalt ML-detectie volledig. Tussen deze twee extremen in slaagt ML-detectie precies bij $\text{SNR} = 2 \log N$. Boven deze drempelwaarde kan de verzonden $N$-bit sequentie perfect worden hersteld, maar het oplossen hiervan leek tot nu toe een uitputtende zoektocht over alle mogelijke binaire sequenties te vereisen.
Een korte geschiedenis
De vraag naar de oplosbaarheid van het integer least squares probleem dateert van ten minste 1989, toen Verdú bewees dat het in het algemene geval NP-hard is.
In 2001 beargumenteerden Hassibi en Vikalo dat er hoop was voor een polynomiale oplossing in het gemiddelde geval via de Sphere Decoder (SD). Hoewel SD in de praktijk snel leek, toonden Jaldén en Ottersten in 2005 aan dat de verwachte complexiteit van sphere decoding bij elke vaste SNR in feite exponentieel is ten opzichte van de dimensie van het probleem.
Vervolgens richtte het vakgebied zich op benaderingen van het ML-optimalisatieprobleem:
- Semidefinite relaxations: Bood garanties bij hoge SNR, maar geen scherpe drempelwaarde.
- Bit-flipping local search: Leek in simulaties op ML, maar miste volledige bewijzen.
- AMP (Approximate Message Passing): Karakteriseerde de fout per bit, maar niet het blokherstel.
- MCMC-methoden: In een paper uit 2010 werd bewezen dat de stationaire distributie massa plaatst op de correcte oplossing, maar de mengtijd (het lastige deel) bleef onbewezen.
In 2020 verscheen de box relaxation, die blokherstel kon garanderen wanneer de SNR schaalde als $4 \log N$, maar niet daaronder. De kloof tussen wat ML bereikte en wat een polynomiale methode kon bewijzen, bleef dus bestaan.
Hoe GPT en Claude het probleem oplosten
Gestimuleerd door de successen van frontier-modellen in complexe wiskunde, heb ik GPT-5.6 en Claude Fable gevraagd wanneer ML MIMO-detectie in polynomiale tijd kan worden opgelost. Beiden produceerden bewijzen voor verschillende algoritmen die stelden dat er geen kloof is: er bestaat een polynomiaal-tijdsalgoritme dat slaagt bij $\text{SNR} > 2 \log N$.
Het proces om dit te verifiëren was intensief:
- Algoritmekeuze: GPT stelde een AMP-variant voor, maar Claude suggereerde signed LMMSE, gevolgd door greedy bit flips—een methode die in de praktijk al bekend was.
- Correctie: GPT wees erop dat het bewijs van Claude grotendeels onjuist was, maar wel redbaar. Ik vroeg GPT om het bewijs van Claude te repareren.
- Vereenvoudiging: Het resultaat was aanvankelijk onleesbaar door een muur van complexe notaties en exotische matrixanalyse. Ik heb vervolgens vier tot vijf dagen besteed aan het heen-en-weer prompten met beide modellen om de stappen zo simpel mogelijk te maken, zodat ik ze zelf kon verifiëren zonder externe tools zoals Lean.
Het resultaat is een bewijs dat ik regel voor regel heb gecontroleerd en dat correct is. Het produceren van het initiële bewijs nam 30 minuten in beslag; het verifieerbaar maken ervan kostte vijf dagen.
De kern van het bewijs
Het algoritme is verrassend eenvoudig:
- LMMSE en afronding: Dit brengt je, in termen van Hamming-afstand, binnen een fractie ($o(N)$) van het verzonden signaal.
- Greedy bit-flipping: Omdat de daling per stap wordt bepaald door Gaussische grootheden, is er altijd een verbeterende bit-flip mogelijk zolang men zich niet op de grondwaarheid bevindt.
- Kostenbarrière: Hoewel de Hamming-afstand tijdelijk kan toenemen, zorgt de kostenfunctie ervoor dat het algoritme binnen een bepaalde "bal" blijft. De startkosten liggen niet veel boven het optimum en elke stap verlaagt de kosten met een bedrag dat begrensd is vanaf nul.
- Convergentie: Hierdoor moet het proces na $N \log N$ stappen stoppen. De enige plek waar het algoritme kan stoppen zonder verdere verbetering mogelijk te zijn, is bij de verzonden vector.
Reflecties over AI en vergeten problemen
In 2010 zou dit resultaat waarschijnlijk hebben geleid tot prestigieuze prijzen en aanbiedingen van topuniversiteiten. Nu is het vakgebied grotendeels verder gegaan. Er zijn veel problemen die decennialang belangrijk waren, maar vervolgens werden verlaten—niet omdat ze onmogelijk waren, maar omdat men er simpelweg mee stopte zich ermee bezig te houden.
Het is fascinerend dat je nu met AI terug kunt gaan naar deze "verlaten hoeken" van de literatuur en ze kunt oplossen voor een paar honderd dollar per maand.
Een belangrijke observatie over het bewijs is dat er geen nieuwe wiskunde is uitgevonden. Er zijn geen nieuwe ongelijkheden of technieken gebruikt die in 2010 niet al bestonden. De moeilijkheid zat niet in conceptuele vernieuwing, maar in de enorme inspanning om twintig pagina's aan standaardstappen perfect op elkaar af te stemmen.
Dit definieert een klasse van problemen waarvan de oplossing geen nieuwe wiskunde vereist, maar enkel de assemblage van bekende ideeën over een lengte die langer is dan iemand bereid was te besteden. AI is uitmuntend in het herhaaldelijk proberen van combinaties totdat iets klikt. Deze modellen zijn wellicht distillaties van onze geaccumuleerde instincten, aangescherpt door Reinforcement Learning.
We weten nu: MIMO ML-detectie is eenvoudig, zodra het mogelijk is.
Groetjes,