PhD ved et tilfælde

George Dantzig.

En af de mest fascinerende anekdoter i universitetsmatematik er vel beretningen om George Dantzig, manden bag simplex-algoritmen, kendt fra lineær programmering.

I et interview fra 1986 fortæller han, hvordan han i 1939 som første-års PhD-studerende på Berkeley engang kom for sent til en statistikforelæsning med Jerzy Neyman. Dantzig så at Neyman havde skrevet to problemer på tavlen, og han regnede med at der var tale om hjemmearbejde til næste kursusgang. Så gav Dantzig sig til at løse de to problemer; han undskyldte bagefter til Neyman at han afleverede sin besvarelse for sent.

Men det var slet ikke to hjemmeopgaver; det var faktisk to åbne problemer fra matematisk statistik, som Neyman havde skrevet på tavlen – og George Dantzig havde løst dem “i god tro”.

Jeg har ikke kunnet finde ret mange oplysninger om hvad det var for to åbne problemer, men det ene problem handler om det såkaldte Neyman-Pearson-lemma, der fortæller hvordan man finder den stærkeste test for et givet signifikansniveau.

Jerzy Neyman foreslog George Dantzig at publicere sine beviser og lade dem udgøre en PhD-afhandling. Så det gjorde han (Anden Verdenskrig kom ganske vist i vejen for en tid.)

Jeg burde lære det…

Logoet for Coq (http://www.inria.fr)

I dag var der statusseminar på 4. semester af datalogiuddannelsen, hvor projektgrupper fremlagde problemformuleringerne i deres projekter. En projektgruppe, som jeg vejleder, havde i deres materiale nævnt bevisassistenten Coq (som et eksempel på hvordan man ved hjælp af en bevisassistent kan implementere en bevisligt korrekt oversætter til et programmeringssprog). og da måtte jeg modstræbende indrømme, at jeg inden for de seneste år ofte har haft en ambition om at komme til at lære at bruge Coq, så jeg kunne formalisere alle mine beviser én gang for alle. Jeg har tidligere her skrevet om de store resultater inden for formaliseret matematik, som er nået gennem brug af Coq. Og jeg røbede, at jeg havde købt Adam Chlipalas bog om Coq, da jeg var til POPL2019 i Portugal i januar i år. Nu ligger bogen og truer på et bord på mit kontor; jeg havde lovet mig selv at bruge en eftermiddag om ugen på at komme i gang med at lære at bruge bevisassistenten. Men endnu har jeg end ikke fået læst bogens forord. Min ambition om at lære Coq er desværre på vej samme sted hen som min ambition om at blive bedre til at spille guitar. Og jeg ved, at jeg ikke er den eneste, der har det på denne måde. Til POPL2019 mødte jeg flere, der havde det på den måde og havde samme underlige længsel som mig.

En studerende fra en anden gruppe spurgte til statusseminaret, om ikke jeg kunne give ham en henvisning til Chlipalas bog, for det ville han da gerne give sig i kast med. Og det kunne jeg selvfølgelig – bogen kan hentes kvit og frit hos forfatteren som PDF-fil.Det vil være noget helt særligt, hvis den første person på Aalborg, der lærer at bruge Coq, bliver en studerende på 4. semester af bacheloruddannelsen!

En af de sidste af slagsen?

Foto: Brian Flaherty/New York Times.

I New York Times’ netudgave er der i dag en lang portrætartikel om Donald Knuth, den (for mig og andre af min slags) legendariske amerikanske datalog og matematiker, der har så mange store opdagelser på samvittigheden. Jeg har skrevet om Knuth før her på bloggen; han er altid værd at vende tilbage til. Han er gammel nu – den 10. januar bliver han 81.

Knuth-Morris-Pratt-algoritmen til søgning i tekst (som alle, der søger i en tekst med CTRL-F bruger) ig dokumentbehandlingssystemet TeX (som jeg bruger dagligt – i form af LaTeX) er bare to af mange af Knuths bidrag.

Portrætartiklen er i det store og hele præcis (omend jeg ikke er så glad for forsøget på at forklare hvad et højniveau-programmeringssprog er), og den røber, at vi kan regne med snart at se næste bind af The Art of Computer Programming., Til ikke-fagfolk: Dette flerbindsværk er ikke er en bog om programmering, men derimod er en bog om algoritmeteori og langt hen ad vejen en lærebog i matematik (og en god én af slagsen).

Det, der slår mig for alvor, er dog at Donald Knuth måske er en af de sidste af sin slags. Knuth begyndte sin karriere, mens datalogi endnu blev set som en gren af anvendt matematik. Så alene her favner han bredere, end moderne dataloger som oftest gør. Han interesserer sig for musik, sprog, typografi og litteratur og har noget interessant at sige om hvert af disse områder. Og hans måde at publicere på har været en helt anden end den, man ser i dag. Han har ikke publiceret siden 2012 – ikke så sært, for det er meget længe siden, han gik på pension. Knuths publikationer op gennem årene er temmelig få, og også i hans egentlige aktive periode var der år, hvor han ikke publicerede. Andre år havde han kun én publikation, men den var så til gengæld en bog.

I dag laver vi (og jeg er medskyldig her) mere og mere specialiserede kandidater i alle universitetsfagene, og selvfølgelig også i datalogi. Men jeg ville ønske, at vi også kunne stimulere de studerende til også at have en anden slags forbilleder end de hyppigt publicerende og iværksætter-aktive kandidater med formuer af forskningsmidler, der så ofte bliver hyldet i disse år. Jeg tror selv, at det er dét. der skal til for at skabe en ny Donald Knuth-skikkelse.

Logicomix

For hele syv et halvt år siden skrev jeg her på  siden om Frege og nævnte da kort den grafiske roman Logicomix fra 2008, der er skrevet af Christos Papadimitriou og Apostolos Doxiadis og tegnet af Alecos Papadatos og Annie di Donna. Logicomix tager fat på fortællingen om matematikkens grundlagskrise og alt, hvad den afstedkom. Vi møder Gottlob Frege, Georg Cantor, David Hilbert, Kurt Gödel og Ludwig Wittgenstein – men først og fremmest Bertrand Russell. 

Jeg var tidligere i år blevet inviteret til at være gæsteunderviser for Aalborg Katedralskoles 2.k, som er den klasse, min datter går i. Planen var nemlig, at 2.k skulle læse Logicomix i forbindelse med et flerfagligt forløb. Og i dag besøgte jeg så 2.k. På vej dertil skulle jeg have en sandwich, og tilfældet ville, at jeg i sandwich-baren mødte Emil Ottosen, der er adjunkt i matematik (og gammel elev fra Aalborg Katedralskole)! Emil og jeg fik talt lidt om firefarveproblemet, der nok er det problem, der nemmest illustrerer hvorfor der var en grundlagskrise for matematikken sidst i 1800-tallet.

Besøget i 2.k gik vist ikke så dårligt; jeg fortalte om Cantors resultater om uendelighed, Russells paradoks og lidt om typeteori (i Russell og Whiteheads udgave). Eleverne stillede gode spørgsmål og virkede faktisk til at være interesserede. Jeg kunne undervejs ikke lade være med at bemærke, at alle de mest forstyrrede personer i Logicomix – Frege, Cantor, Hilbert, Gödel og Wittgenstein – alle talte tysk.

Det var også godt for mig at møde nogle af dem, vi måske en dag kan møde på universitetet. Desværre fik en elev et voldsomt ildebefindende i en pause og måtte hjælpes ud af klasselokalet. Forhåbentlig har hun det bedre nu.

Enten-eller

I dag, da jeg underviste i Beregnelighed og kompleksitet, undrede flere studerende sig uafhængigt af hinanden over en opgave, jeg stillede, hvor man skulle finde en beregnbar funktion mellem to mængder af strenge, A og B. Det eneste, opgaven fortalte, var at der fandtes strenge, som var elementer i B og andre strenge, der ikke var med i B.

Så kunne man derfor definere funktionen, så den på elementer fra A gav en fast streng u fra B som resultat og fra elementer uden for A gav en fast streng v uden for B som resultat. Funktionen er endda beregnbar, hvis man med en algoritme kan afgøre om strenge er elementer i A. Men de studerende, der undrede sig, syntes at det virkede som snyd. Vi får aldrig at vide, hvad u og v egentlig er. Så vi ved egentlig ikke, hvordan funktionen skal beregnes.

Og jeg måtte give dem ret. Hvis funktionen, som jeg har skrevet ovenfor, er en funktion over de naturlige tal, er den veldefineret og den er endda også beregnelig. Den er nemlig en konstant funktion, og konstante funktioner er nemme at beregne. Vi ved bare ikke, om dens værdi altid er 1 eller altid er 0. Men på en eller måde synes man, at beregningen af funktionsværdien kræver at vi skal vide om der er liv uden for solsystemet eller ej.

I det omfang jeg overhovedet kan siges at være matematiker, er jeg konstruktiv matematiker, og de studerendes betænkeligheder er helt rimelige, hvis man spørger mig. Det store underliggende problem er nemlig, at påstanden Enten er der liv i solsystemet eller også er der ikke har en sandhedsværdi ifølge klassisk logik, men er meningsløs i konstruktiv matematik. I konstruktiv matematik kan jeg nemlig kun bevise en påstand på formen P eller Q ved at præsentere enten et bevis for påstanden eller et bevis for påstanden Q. Så jeg skal enten bevise, at der er liv uden for solsystemet eller bevise, at der ikke er. (Det er lidt svært.)

Børn skal ikke lære at regne!

For en del år siden snakkede jeg med en ung mand i gymnasiealderen, der gik på en Rudolf Steiner-skole. Han havde ikke lært at læse, før han var 12. For indtil da havde han ikke haft brug for at kunne læse! Men nu læste han så til gengæld rigtig meget. Jeg var målløs – kunne han ikke have risikeret at gå gennem livet som analfabet? Men, som han sagde: En dag ville jeg jo alligevel få brug for at læse, og så skulle jeg nok lære det.

Den amerikanske skoleleder Louis P. Bénézet foretog fra efteråret 1929 og frem et eksperiment med ikke at undervise børn på sin skole i New Hampshire i regning, til de gik i 6. klasse – det ville i datidens USA sige, at han ventede til de var omkring 11 år gamle. De skulle til gengæld stadig lære at læse og skrive.

Hans bevæggrund var at børn ikke skal lære noget, før de får brug for det. Børnene skulle stadig lære om tallene, men undervisningen kom i forbindelse med at de blev undervist i de andre fag. På denne måde lærte de f.eks. om sidetallene i bogen. Der var ingen udenadslære af regneregler mm.

Det overraskende resultat var at børnene, der deltog i eksperimentet, faktisk blev bedre til mundtligt og skriftligt engelsk og faktisk også blev bedre til regning og til at ræsonnere om matematiske problemer på deres alderstrin.

Bénézets eksperiment er i sandhed radikalt. Sanjoy Mahajan fra Cavendish Laboratory ved Cambridge University har skrevet en kort artikel om det, og hans konklusion er at det er værd at forsøge igen. Jeg er i syv sind om det er en god tilgang; med de nuværende politiske strømninger med voldsomt fokus på tests vil det under alle omstændigheder næppe være muligt at gennemføre et tilsvarende eksperiment i Danmark.

Det rigtig interessante ved Bénézets tilgang er at udenadslæren er elimineret og at de matematiske kompetencer bygger direkte ovenpå de sproglige – og så er der også en mulig fordel i at eleverne kan koncentrere sig om at opnå få, men store kompetencer ad gangen i stedet for at få hakket skoledagene i stykker.

Sig det med 1000 ord

Til den berømte internationale matematikkongres i Paris i 1900 sagde David Hilbert at

En gammel fransk matematiker sagde: “En matematisk teori anses ikke for fuldstændig før man har gjort den klar, at man kan forklare den til den første, den bedste mand som man møder på gaden”

– citatet er her min oversættelse fra engelsk, efter en artikel i Historia Mathematica af June Barrow-Green og Reinhard Siegmund-Schultze, der prøver at identificere hvem den gamle franske matematiker er. Jeg troede i mange år, at det var Poincaré, men der er faktisk tale om Gergonne, viser det sig.

Men hvor nemt er det egentlig at forklare sine ideer til den første, den bedste, man møder? Det kan såmænd også være svært nok, selv om der er tale om nogen, man kender i forvejen. Da jeg studerede matematik for mange år siden, kunne jeg aldrig forklare familien, hvad det var, jeg havde givet mig i kast med. Senere, da jeg studerede datalogi, blev det faktisk ikke nemmere.

Hvis sproget til forklaringen er engelsk, er der nu en helt konkret test i form en teksteditor, der undersøger om man kun bruger de 1000 mest almindelige ord på engelsk. Editoren skyldes Theo Sanderson, der er biolog og forsker i parasitologi.

Jeg har selv forsøgt at forklare min forskning inden for programmeringssprogsteori på den måde, men det er godt nok svært, for al terminologi er bandlyst. Ordet “program ” er ikke blandt de 1000 mest almindelige ord på engelsk! Det er “type” så til gengæld. Billedet ovenfor viser mit forsøg; det forbudte ord “program” seks gange. Nu spekulerer jeg så på, hvordan jeg kan undgå dét – noget godt svar har jeg desværre ikke fundet endnu. En tilladt udvej er at sætte ordet i anførselstegn, men det er egenlig lidt snyd.

Presburger og hans speciale på 9 sider

Her i ferien har jeg omsider fået tid til at få læst Anita og Solomon Fefermans biografi Alfred Tarski – Life and Logic færdig. Bogen giver et fascinerende indblik i det livlige miljø blandt matematikere og logikere i 1920erne og 1930erne. En af bogens mange sidehistorier er den om Alfred Tarskis studerende Mojzesz Presburger; Tarski var blevet interesseret i hvordan man viser at logiske teorier er afgørbare ved hjælp af den dengang nye teknik, der kaldes elimination af kvantorer. Og som en øvelse i sin undervisning gav han en af sine studerende, Mojzesz Presburger, den udfordring at prøve at vise at teorien for naturlige tal under addition er afgørbar. Dvs. at vise, at der er en algoritme, der kan fortælle os om udsagn som

\forall x. \exists y.y + 1 = x

er sande. Udsagnet ovenfor siger i øvrigt, at for ethvert naturligt tal findes der et naturligt tal, som er dets forgænger. (Dette udsagn er falsk, for det gælder ikke for det mindste naturlige tal.)

Presburger viste at teorien for naturlige tal under addition er afgørbar ved en snedig brug af elimination af kvantorer og den resulterende artikel på 9 sider blev til hans speciale. Nogle mente senere, at dette resultat burde være nok til at give ham en Ph.D. Dette ville i så fald have været en af de korteste Ph.D-afhandlinger nogensinde (det var allerede et kort speciale!).

Mojzesz Presburger forlod dog universitetet og blev ansat ved et forsikringsselskabet. Men man kalder i dag teorien for naturlige tal under addition for Presburger-aritmetik. Og I 2010 opkaldte European Association for Theoretical Computer Science en særlig pris, Presburger-prisen, efter ham. Prisen gives til en ung forsker inden for teoretisk datalogi for banebrydende resultater.

Den meget tragiske del af historien er, at Mojzesz Presburger aldrig nåede at opleve noget af dette. Han døde i Holocaust, formodentlig i 1943.

Bohr-fodbold

Det danske landshold ved OL-finalen i 1908. Det er Harald Bohr på forreste række, hvor han er nummer tre fra venstre.

Nogle har hørt om Harald Bohr, fordi han var matematiker og bror til Niels Bohr. Andre (nok ikke så mange mere) kan huske hans og Johannes Mollerups bog om matematisk analyse, som engang var meget udbredt i Danmark. Mollerup og Bohr er forresten også ophavsmænd til en sætning, der bærer deres navn, og som siger at gammafunktionen er den eneste reelle funktion, der opfylder den funktionalligning, som fakultetsfunktionen ofte defineres ved.

Men inden Harald Bohr blev professor i matematik ved Københavns Universitet var han faktisk også en af sin tids store fodboldstjerner. Han spillede for Akademisk Boldklub, der er i dag er absorberet i FC København, og han var også på landsholdet. I 1908 nåede det danske landshold finalen ved de olympiske lege, hvor de desværre blev slået 0-2 af England. Da Harald skulle forsvare sin doktorafhandling, mødte der efter sigende flere fodboldfans end matematikere op i auditoriet!

Jeg ved, at Lars Bastrup, der i sin tid spillede for HSV i Bundesligaen, var cand.mag i dansk – og mange år senere stiftede han sin egen messianske sekt! Og Klaus Berggren, der også spillede mange kampe på det danske landshold, var cand.merc. Og den brasilianske stjerne Sócrates levede op til sit navn; han var uddannet læge og fik langt senere en PhD-grad i filosofi.

Men vore dages fodboldstjerner er anderledes ubelæste. Er f.eks. Ronaldo, Messi eller Neymar nogensinde blevet set med en bog?

Hilbert og de selvkørende biler

Hilberts syttende problem er

Givet et ikke-negativt multivariat polynomium, kan det da altid skrives som en sum af kvadrater af rationelle funktioner?

Svaret er ja, og beviset herfor blev fundet i 1927 af Emil Artin. Desværre var beviset ikke konstruktivt. Et konstruktivt bevis kom i 1940, og først i 1967 fandt man ud fra hvor mange rationelle funktioner, der skal optræde i kvadratsummen. Konrad Schmüdgen har en lille oversigtsartikel om netop Hilberts syttende problem.

Der er en interessant artikel i Wired, hvor udgangspunktet er en forbindelse til selvkørende biler. Det er nemlig rigtig nyttigt i optimeringssammenhæng at vide, om et polynomium kan antage negative værdier, og her er løsningen til Hilberts syttende problem guld værd – og især da de algoritmer, der giver en kvadratsum, hvis den findes. Og hvis man vil minimere et multivariat polynomium, kan man så prøve at forskyde det langs y-aksen og blive ved, til polynomiet ikke længere er ikke-negativt. Forbindelsen til selvkørende biler kommer fra behovet for hurtigt at kunne beregne minimum af multivariate polynomier, der dukker op i beskrivelserne af selvkørende bilers adfærd (f.eks. et polynomium, der beskriver afstanden til en forhindring).

Det rigtig interessante er egentlig, at det, der tilbage i år 1900 var ren matematisk grundforskning, nu her et århundrede senere har fået nogle meget konkrete anvendelser. Gad vide, om vores nuværende forskningsminister er klar over denne forbindelse mellem grundforskning og anvendelser? (Jeg tillader mig at tvivle.)