ColumnIonica Smeets

Het romantische verhaal achter het LLL-algoritme dat de prestigieuze Abelprijs kreeg

null Beeld

Dinsdag ontvangen wiskundigen László Lovász en Avi Wigderson de prestigieuze Abelprijs. Dat is met 7,5 miljoen Noorse kronen (omgerekend zo’n 747.152,62 euro) vergelijkbaar met een Nobelprijs. Lezer Jeroen Zuiddam stuurde in maart een verbaasde mail toen de winnaars bekend waren gemaakt en de Volkskrant het nieuws helemaal oversloeg: ‘En dat terwijl LLL zo verbonden is aan Nederland!’

LLL is het LLL-algoritme, door de jury van de Abelprijs geroemd als een van de visionaire ideeën van László Lovász. Het is een rekenmethode om snel een basis te vinden voor puntenroosters – met allerlei toepassingen, onder andere in cryptosystemen. De Nederlandse link zijn de wiskundigen Arjen en Hendrik Lenstra en u mag nu raden hoe het LLL-algoritme aan zijn naam komt.

Als promovendus schreef ik de ontstaansgeschiedenis op voor een boek ter ere van het 25-jarig bestaan van het LLL-algoritme. Dat Engelstalige hoofdstuk is te vinden op mijn site en daarin staat ook wat het algoritme precies doet (met plaatjes). Hier vertel ik vandaag alleen het romantische verhaal vol toevalligheden en briefkaarten van achter het IJzeren Gordijn.

De Hongaarse László Lovász werkte aan een methode ontwikkeld door Sovjet-wetenschappers, waarover in het Westen destijds alleen maar geruchten gingen. Lovász kreeg soms toestemming om te reizen en in 1979 keerde hij vanuit Amerika terug naar Hongarije. Onderweg maakte hij een paar tussenstops, want hij wist niet wanneer hij weer naar het Westen zou kunnen. Het goedkoopste vluchtschema leidde hem onder andere langs Bonn, waar hij toevallig een lezing zag van de Nederlandse wiskundige Hendrik Lenstra.

Een jaar later werd deze Lenstra in zijn Amsterdamse werkkamer lastiggevallen door collega’s met een vraag die Lenstra al eens beantwoord had. Hij legde het nog eens uit en probeerde van hen af te komen met de vraag waarom dit überhaupt interessant was. Het bleek een speciaal geval van een belangrijk open probleem. Een uurtje later had Lenstra bewezen dat dit op eenzelfde manier was op te lossen. Hij publiceerde zijn methode, maar het lukte hem niet om te bepalen hoe snel die precies was. Hij schreef in het artikel dat hij ruimte zag om zijn analyse van de rekentijd te verbeteren.

Intussen zat Lovász in Hongarije te prutsen op een detail van zijn Sovjet-methode. Ineens herinnerde hij zich dat hij bij zijn tussenstop in Bonn in de lezing van Hendrik Lenstra iets had gezien dat leek op wat hij nodig had. Lovász vond het net gepubliceerde artikel van Lenstra. En in plaats van dat hij de analyse van de rekentijd aanscherpte, bedacht hij een manier om de rekenmethode zelf te verbeteren. Er volgde een opgewonden briefwisseling tussen Hongarije en Nederland.

Hendrik Lenstra bedacht vervolgens dat dit idee gebruikt kon worden voor een probleem waarop zijn jongere broer Arjen toevallig net afstudeerde – en waarvan iedereen dacht dat je dit onmogelijk zo snel kon doen als nu met Lovász’ variant op Hendriks algoritme lukte. Dit idee bleek precies de laatste stap die Arjen Lenstra nodig had. Lenstra, Lenstra en Lovász schaafden samen aan de details en publiceerden in 1982 hun LLL-algoritme.

In 2009 deed ik een dappere poging om een populair-wetenschappelijk stuk te maken met dit geweldige verhaal en alle wiskundige details. Na drie keer herschrijven wees de redactie het definitief af omdat het te moeilijk was. Destijds was ik woedend. Nu, ruim tien jaar later, lees ik de tekst terug en snap ik de redactie. Ik kan de details niet meer volgen en haat mijn jongere zelf die schreef ‘het idee achter deze methode is niet moeilijk’, om vervolgens iets te beschrijven waarop ik een avond rustig moet studeren voor ik het begrijp. En dan ben ik nota bene gepromoveerd op dit soort wiskunde. Daarom lees je dus zelden iets over de Abelprijs in de krant, maar vandaag wel.

Wilt u belangrijke informatie delen met de Volkskrant?

Tip hier onze journalisten


Op alle verhalen van de Volkskrant rust uiteraard copyright. Linken kan altijd, eventueel met de intro van het stuk erboven.
Wil je tekst overnemen of een video(fragment), foto of illustratie gebruiken, mail dan naar copyright @volkskrant.nl.
© 2021 DPG Media B.V. - alle rechten voorbehouden