Het decenniaoude ‘sofaprobleem’ is eindelijk met wiskundig bewijs ontrafeld. Een Zuid-Koreaanse wiskundige loste zonder computer, en op vernieuwende wijze, het probleem op. Zijn methode laat zien dat simpele problemen soms onverwacht complexe oplossingen hebben.
Je hebt het vast wel meegemaakt: je bent aan het verhuizen en moet een meubelstuk door een krappe gang of een lastige hoek manoeuvreren. Toen Leo Moser dit probleem in 1966 kwantificeerde, begonnen wiskundigen zich erover te buigen. Stel je wil een tweedimensionaal object – de bank (de hoogte laten we buiten beschouwing) – door een L-vormige gang krijgen. Voor het gemak is de breedte van de gang 1. Hoe groot is het grootste object dat door de bocht heen kan?
Het is vrij eenvoudig om vormen te vinden die door de hoek van 90 graden heen kunnen. Een vierkant met zijden van lengte 1 bijvoorbeeld. Een halve cirkel met een straal van 1 (en een oppervlakte van π/2, ongeveer 1,57) ook. Maar die vormen zijn vrij klein. Voor een betere oplossing voor het zogenoemde sofaprobleem is wat meer denkwerk nodig.
Joseph Gerver van de Rutgers-universiteit in New Brunswick bedacht in 1992 een slimme vorm met een oppervlakte van ongeveer 2,2195. Wiskundigen dachten dat dit misschien de oplossing was, maar konden dit niet bewijzen.
Tot nu. Jineon Baek, postdoctoraal onderzoeker aan de Yonsei-universiteit in Seoul, heeft in een 119 pagina’s lang paper bewezen dat de bank van Gerver de grootste vorm is die door de gang past.
Hiermee is een zestig jaar oud probleem opgelost, en meer dan dat, want veel wiskundigen dachten dat het niet zonder een computer kon. Maar Baek heeft het zelf bewezen. Wiskundigen hopen nu dat Baeks methodologie kan helpen bij andere optimaliseringsproblemen.
Wat de bank van Gerver verder ook interessant maakt is dat zijn oppervlakte niet (zoals bij veel andere vormen) in bekende grootheden, zoals π of machtswortels, kan worden uitgedrukt. Toch is deze vreemde vorm de optimale oplossing voor het makkelijk ogende sofaprobleem. Hieruit blijkt maar dat simpele problemen soms onverwacht complexe oplossingen hebben.
Sofaprobleem
In 1968, twee jaar nadat Moser het sofaprobleem had geformuleerd, kwam er voor het eerst schot in de zaak. John Hammersley plakte twee kwartcirkels aan een rechthoek en sneed er een halve cirkel uit, zodat je een soort ouderwetse telefoon kreeg. De oppervlakte was π/2 + 2/π, ongeveer 2,2074.
Hammersley bewees ook dat een oplossing voor het probleem een oppervlakte van niet meer dan 2√2 kon hebben, dat is rond de 2,8284.
Een paar jaar later hoorde Gerver, toen een promovendus aan de University of California in Berkeley, van het sofaprobleem. ‘Een studiegenoot daagde me uit om de oplossing te vinden,’ zei hij. ‘Hij had nooit gezegd dat het een onopgelost probleem was, dus heb ik er een paar dagen op gebroed. Uiteindelijk kwam ik bij hem terug en zei: “Ik geef het op. Wat is de oplossing?” Maar hij wilde het niet zeggen! Hij zei: “Denk er nog maar eens goed over na. Uiteindelijk valt het kwartje wel.”’
In de twintig jaar daarna dacht Gerver er nu en dan over na, en pas in 1990, toen hij het probleem aan de beroemde wiskundige John Conway voorlegde, kwam hij erachter dat er nog geen oplossing bestond. Gerver raakte hierdoor juist gemotiveerd.
De bank van Gerver lijkt heel erg op Hammersleys telefoon, maar is een stuk moeilijker te beschrijven
De bank van Gerver lijkt heel erg op Hammersleys telefoon, maar is een stuk moeilijker te beschrijven, omdat hij uit achttien verschillende stukken bestaat. (Later bleek dat Ben Logan, een ingenieur bij Bell Labs, deze vorm ook had ontdekt, maar zijn werk niet had gepubliceerd.) Sommige onderdelen zijn simpele lijnstukken of cirkelbogen, maar andere zijn ongewoner en moeilijker te beschrijven.
Toch dacht Gerver dat deze vorm weleens optimaal zou kunnen zijn. Hij had veel eigenschappen waarvan andere wiskundigen ook vermoedden dat de optimale bank ze moest bezitten, en hij kon aantonen dat je met kleine veranderingen niet op een grotere geschikte vorm uitkwam.
In 2016 maakte Dan Romik, een wiskundige aan de University of California in Davis, een conceptuele beschrijving van de bank van Gerver. Hij schreef een stelsel van 22 vergelijkingen met 22 variabelen op met een unieke oplossing, die weergegeven in een grafiek de vorm van Gervers bank laten zien.
In het jaar daarop gebruikten Romik en Yoav Kallus een computer om Hammersleys bovengrens omlaag te krijgen, waardoor hij steeds dichter bij Gervers ondergrens kwam. Maar er zat nog wat speling tussen, dus moesten ze iets anders proberen.
Bankgrafiek
In 2016 was Baek nog maar net aan zijn vervolgopleiding begonnen aan de Universiteit van Michigan, maar die moest hij vier jaar op pauze zetten om zijn militaire dienstplicht in Zuid-Korea te vervullen. In die tijd kwam hij het sofaprobleem in een blog tegen. Eerst puzzelde hij af en toe aan het probleem ‘ter ontspanning’, aldus Baek, maar langzamerhand begon hij het steeds serieuzer te nemen. Hij had het idee dat het bewijs voor Gervers oplossing in zicht was, maar hij moest nog wat details uitwerken. Toen hij in 2021 terugging naar de universiteit, besloot hij zich volledig op dit probleem te storten.
Normaal gesproken kies je als wiskundepromovendus een begeleider, die jou vervolgens een probleem toewijst. Baek was echter vastbesloten om aan het sofaprobleem te werken. Dit maakte het moeilijk om een begeleider te vinden, omdat niemand aan de Universiteit van Michigan de juiste expertise had. Toch wist Baek uiteindelijk iemand te vinden: Michael Zieve, met als specialisatie algebra. Hij zei ja. ‘Ik heb nog nooit iemand geadviseerd over iets dat zich zo ver van mijn bed bevindt,’ zegt Zieve. ‘Maar ik wil studenten overal in kunnen begeleiden.’
Bij zijn promotieonderzoek bouwde Baek voort op het werk van Kallus en Romik, en ontwikkelde hij betere computerprogramma’s waarmee de bovengrens nog lager kwam te liggen. ‘Jin is op computergebied verreweg de beste student die ik ooit heb begeleid,’ zegt Zieve. ‘Hij kan met behulp van de computer patronen herkennen die niemand anders kan zien.’
Baek wilde dieper de computerwetenschap in duiken om voor eens en voor altijd af te rekenen met het sofaprobleem
Nadat hij zijn vervolgopleiding had afgerond wilde Baek aanvankelijk dieper de computerwetenschap in duiken om voor eens en voor altijd af te rekenen met het sofaprobleem. Maar na een paar maanden besefte hij dat hij helemaal geen computer nodig had.
Wiskundigen wisten al dat een oplossing van het sofaprobleem aan bepaalde eisen moest voldoen. De optimale vorm moet, onder andere, op een bepaalde manier kunnen draaien en er moet een uitsparing in de onderkant zitten zodat hij om de hoek heen kan.
Er zijn oneindig veel vormen die aan deze eisen voldoen. Baek wist deze te beperken en liet zien dat de optimale sofa er ongeveer als de bank van Gerver uit moest komen te zien. Vervolgens beschreef hij elke sofa – waar er nog steeds oneindig veel van waren – als een punt in een ruimte met oneindig veel dimensies. Idealiter zou de oppervlakte van elke denkbeeldige sofa met behulp van een functie te bepalen zijn. Dan zou hij enkel het punt moeten vinden waar deze functie de maximale waarde bereikt.
Maar dat is een onmogelijke taak: er is geen formule die de oppervlakte van elke mogelijke vorm geeft. (Voor een cirkel en een driehoek zijn bijvoorbeeld al heel andere formules nodig.)
Dus besloot Baek de oppervlakte van de verschillende vormen indirect te onderzoeken. Hij bedacht een nieuwe functie, die hij Q noemde. Hij had de functie gedefinieerd met een aantal belangrijke eigenschappen.
Het bewijs
Eerst bewees hij dat als je een sofa uit zijn multidimensionale ruimte in de formule Q stopte, het resultaat altijd minstens zo groot was als de oppervlakte van de sofa. Kortom, de formule gaf de oppervlakte van een vorm waar de sofa in paste. Als hij vervolgens de maximale waarde van Q bepaalde, had hij dus een goede bovengrens voor de oppervlakte van de optimale sofa.
Maar hiermee had hij nog niet de oplossing. Baek had Q ook op zo’n manier gedefinieerd dat de formule voor de bank van Gerver niet alleen de bovengrens gaf; de uitkomst was in dat geval precies gelijk aan de oppervlakte van de bank van Gerver. Vervolgens moest hij bewijzen dat Q een maximum bereikte als je de bank van Gerver invoerde, oftewel, dat de bank van Gerver van alle mogelijke sofa’s de grootste oppervlakte had. Daarmee zou het bewijs geleverd zijn.
Hier wordt de definitie van Q heel belangrijk. Baek had zijn functie zodanig opgesteld dat Q zich netjes gedroeg – eigenlijk als een soort parabool. Het is redelijk eenvoudig om de maximale waarde van zo’n functie te vinden. Baek liet zien dat het maximum van Q een vorm gaf die aan bepaalde specifieke voorwaarden voldeed en dat de vergelijkingen die de bank van Gerver definieerden aan diezelfde voorwaarden voldeden.
‘Het is ongelooflijk dat Jin dit zonder een computer klaar wist te spelen’
Hiermee had hij een zestig jaar oud vermoeden bewezen. De bank van Gerver is de grootste vorm die door de gang heen past zonder dat hij bij de hoek blijft steken.
Het bewijs, dat nog aan een peerreview wordt onderworpen, biedt een nieuwe benadering van optimaliseringsproblemen. Baek combineert technieken uit verschillende wiskundige vakgebieden om een lastig probleem hanteerbaar te maken, zonder van een computer gebruik te hoeven maken. ‘Het is ongelooflijk dat Jin dit zonder een computer klaar wist te spelen,’ zegt Zieve. ‘Er zitten wezenlijk nieuwe ideeën in zijn bewijs.’
Joseph Gerver, die zijn vorm meer dan 30 jaar geleden bedacht, is er opgetogen over. ‘Ik ben nu 75,’ zegt hij. ‘Ik ben blij dat ik de oplossing heb mogen meemaken.’