Kategoriarkiv: Matematik

70 millioners forskel

Udgivet den af
Svar

zhang

Yitang Zhang


mochizuki

Shinichi Mochizuki

11 og 13 er gammeldags karakterer – men også to primtal med en afstand på 2. Der er 17 og 19. Der er 51 og 53. Og så videre. Det er stadig et åbent problem om der findes uendeligt mange primtalspar. Men nu hævdes det at Yitang Zhang fra University of New Hampshire har bevist at der findes uendeligt mange par af primtal (p_1,p_2) hvor p_2 - p_1 \leq 70.000.000, dvs. at der er uendeligt mange par af primtal der “kun” er parvis forskellige med højst 70 millioner.

Dvs. der findes nu allerede et meget stærkere resultat, nemlig at der findes uendeligt mange primtalspar med en afstand på 16, men faktisk er dette ikke en sætning – i beviset anvender man nemlig Elliott og Halberstams formodning, der meget passende udtaler sig om hvordan primtal optræder i en aritmetisk progression.

Jeg kan ikke lade være med at tænke på Shinichi Mochizukis bevis for abc-formodningen, der befinder sig i 4 artikler på i alt 512 sider (man aner at det begyndte som en note på 2 sider, der efterhånden successivt fordobles i sideantal). ABC-formodningen er en påstand i talteori:

For ethvert \epsilon > 0 findes der kun endeligt mange tripler (a,b,c) \in \mathbb{N}^3 hvor a,b,c er indbyrdes primiske og a+b=c, så c > d^{1 + \epsilon}, hvor d betegner produktet af alle de forskellige primfaktorer i abc.

ABC-formodningen og formodningen om primtalspar har to ting til fælles: Der er tale om påstande, der er elementære at formulere og nogenlunde intuitivt plausible men hvor beviserne for dem tilsyneladende er meget omfattende. I en artikel om Mochizukis arbejde siger en kollega:

“His other papers – they’re readable, I can understand them and they’re fantastic,” says de Jong, who works in a similar field. Pacing in his office at Columbia University, de Jong shook his head as he recalled his first impression of the new papers. They were different. They were unreadable. After working in isolation for more than a decade, Mochizuki had built up a structure of mathematical language that only he could understand. To even begin to parse the four papers posted in August 2012, one would have to read through hundreds, maybe even thousands, of pages of previous work, none which had been vetted or peer-reviewed. It would take at least a year to read and understand everything. De Jong, who was about to go on sabbatical, briefly considered spending his year on Mochizuki’s papers, but when he saw height of the mountain, he quailed.

“I decided, I can’t possibly work on this. It would drive me nuts,” he said.

Bare den første artikel ser voldsom ud. Mochizuki skriver som noget af det første:

Unlike many mathematical papers, which are devoted to verifying properties of mathematical objects that are either well-known or easily constructed from well-known mathematical objects, in the present series of papers, most of our efforts will be devoted to constructing new mathematical objects.

Det minder måske lidt om at etablere en kæde af restauranter, fordi man er rigtig sulten.

I arbejdet med automatisk bevisførelse optræder begrebet beviskompleksitet som mål for størrelsen af et bevis (på samme måde som beregningskompleksitet angiver omfanget – tids- eller pladsforbrug – af en beregning). Gad vide om vi for de simple, men svære matematiske påstande har at gøre med en situation, hvor nogle tilsyneladende simple påstande nødvendigvis må have urimeligt lange beviser  – ligesom der er findes beslutningsproblemer, der er “født svære”.

Matematik? Det har vi folk til

Udgivet den af
Svar

dna2

Jeg har tidligere skrevet om den amerikanske evolutionsbiolog Edward O. Wilson og hans teori om gruppeselektion.

Nu gør han sig til talsmand for at matematik er overflødig i det meste naturvidenskab.

During my decades of teaching biology at Harvard, I watched sadly as bright undergraduates turned away from the possibility of a scientific career, fearing that, without strong math skills, they would fail. This mistaken assumption has deprived science of an immeasurable amount of sorely needed talent. It has created a hemorrhage of brain power we need to stanch.

I speak as an authority on this subject because I myself am an extreme case. Having spent my precollege years in relatively poor Southern schools, I didn’t take algebra until my freshman year at the University of Alabama. I finally got around to calculus as a 32-year-old tenured professor at Harvard, where I sat uncomfortably in classes with undergraduate students only a bit more than half my age.

Det er underligt at skulle sige dette om en berømt forsker, men måske har vi her at gøre med endnu et tilfælde af Dunning-Kruger-effekten: at være så inkompetent, at man ikke ved hvor lidt man ved. Når man ikke kender et værktøj godt nok, er det svært at se, hvor kraftigt det kan være. Wilson gør en dyd ud af at sige, at han skam har skrevet mange artikler sammen med matematikere og statistikere, men han betoner, at det er dem, der skal komme ham i møde.

If your level of mathematical competence is low, plan to raise it, but meanwhile, know that you can do outstanding scientific work with what you have. Think twice, though, about specializing in fields that require a close alternation of experiment and quantitative analysis. These include most of physics and chemistry, as well as a few specialties in molecular biology.

Newton invented calculus in order to give substance to his imagination. Darwin had little or no mathematical ability, but with the masses of information he had accumulated, he was able to conceive a process to which mathematics was later applied.

Det ironiske er, at Edward Wilsons model om gruppeselektion formodentlig kun kan gøres præcis og evalueres ved brug af en matematisk model. Og faktisk er en del af kritikken af gruppeselektion netop baseret på en kritik af Wilsons brug af matematik!

Charles Darwins indsigt er dyb og epokegørende og skyldes i høj grad at han var sin tids dygtigste naturhistoriker – det var Darwin, der var med til at skabe videnskaben biologi ud fra den beskrivende disciplin, som naturhistorie primært er. Men tænk hvis han havde haft matematisk indsigt tillige. Mange af de ørkesløse diskussioner om evolutionsteorien kan i hvert fald delvis skyldes, at nogle har den opfattelse at evolutionsteorien bare er en samling postulater. Måske ville dette kunne være undgået, hvis evolutionsteorien allerede tidligere havde fået et matematisk fundament også. Darwin brød sig slet ikke om matematik i størstedelen af sin karriere, men mod slutningen skiftede han mening, som man kan læse i en artikel i Science News om netop Darwins brug af statistik:

Darwin himself came around eventually in his attitude toward mathematics. While he wrote in his autobiography of his youthful distaste for math, he also wrote that he wished he had learned the basic principles of math, “for men thus endowed seem to have an extra sense.”

Tårn og muldvarpeskud

Udgivet den af
Svar
molehill1

I baggrunden ses et antal tårne.

I dag er det tid til tilståelser. Når jeg havner til et seminar om matematisk analyse, står jeg desværre hurtigt af. Jeg nåede aldrig længere end til målteori; differentialgeometri og algebraisk topologi er jeg aldrig blevet undervist i, og jeg har aldrig haft brug for det. Men hvis jeg havner til et seminar om f.eks. grafteori eller kombinatorik, kan jeg som regel følge med pænt meget længere. Underligt for så vidt, for da jeg studerede matematik, var det ikke emner, der var del af pensum, og min viden om disse emner er temmelig usystematisk.

På andre tidspunkter sidder jeg og bliver misundelig på “rigtig” matematik; min egen forskning i teoretisk datalogi virker af og til som konstruktionen af en lav mur af muldvarpeskud, der nemt kan fjernes med en skovl, mens netop matematisk analyse fremstår som et elegant tårn, hvis grundsten blev lagt af Newton og Leibnitz.

Og da er det at jeg kommer til at tænke på en artikel af Timothy Gowers om matematikkens “to kulturer”. Gowers skriver:

The “two cultures” I wish to discuss will be familiar to all professional mathematicians. Loosely speaking, I mean the distinction between mathematicians who regard their central aim as being to solve problems, and those who are more concerned with building and understanding theories. This difference of attitude has been remarked on by many people, and I do not claim any credit for noticing it.

Hans pointe er at matematisk analyse befinder sig i den éne, teoritunge kultur, mens “kombinatorik” (han bruger dette begreb så bredt, at det også ender med at omfatte datalogi!) er i den problemdrevne kultur. Af og til bliver det også for sådan en som mig tydeligt, at der er modsætninger mellem dem – tårnet mod muren af muldvarpeskud. Gowers skriver:

One can almost imagine a gathering of highly educated mathematicians expressing their incredulity at the ignorance of combinatorialists, most of whom could say nothing intelligent about quantum groups, mirror symmetry, Calabi-Yau manifolds, the Yang-Mills equation, solitons or even cohomology. If a combinatorialist were to interrupt such a gathering and ask roughly how many subsets of \{1, 2, . . . , n\} can be found such that the symmetric difference of any two of them has size at least n/3, the response might very well be a little frosty.

Hans pointe er at den “problemdrevne” matematik bestemt ikke handler om ubetydelige resultater – næppe mange tør vel affærdige Paul Erdös’ værk som ubetydeligt – men at bidragene her måske ikke er Den Store Samlende Teori, men nyttige generelle teknikker. Et kendt eksempel er de probabilistiske argumenter, som dukker op i bl.a. Ramsey–teori og som skyldes netop Erdös.

På samme måde kan man, vil jeg hævde, forstå teoretisk datalogi ud fra de generelle teknikker, der dukker op, snarere end for Den Store Samlende Teori. Datalogi er i høj grad en problemdrevet videnskab. Derfor bør vi gøre mere for at synliggøre de generelle matematiske teknikker, der dukker op i teoretisk datalogi – det er teknikker som f.eks. reducibilitet i rekursionsteori, diagonalisering i kompleksitetsteori, induktion/koinduktion i denotationel semantik og rekurrenser i algoritmeanalyse – og ikke kun håbe på at kunne bygge det store tårn i et anfald af misundelse. Omvendt vil jeg også gerne have at de, der befinder sig i et stort tårn, kan betragte muldvarpeskud uden at se ned på dem (om man så må sige).

Jens Friis

Udgivet den af
Svar

2013-03-15 14.42.36

I dag var jeg til afskedsreception for Jens Friis, der om 14 dage går på pension i en alder af 65. Vi sad der sammen, mange af os der har kendt Jens i årenes løb og holder af ham – og jeg mødte igen Jens’ hustru Martha og (for første gang i mange år) hans to nu voksne døtre.

På sådan en dag opdager jeg, hvor tiden dog er fløjet – jeg har kendt Jens i 34 år. Han var min matematiklærer i gymnasiet, og det var i høj grad Jens, der inspirerede mig til at studere matematik i sin tid. Hans grundige og indlevede undervisning og store faglige dygtighed fangede mig ind, og jeg ved at jeg langt fra er den eneste, der synes at Jens er en endog meget dygtig underviser. Den indre ro, omtanke og faglige omhu og præcision, der altid har præget Jens, vil jeg gerne kunne leve op til.

Vi har holdt kontakten ved lige, og vi er også mødtes sidenhen i kraft af vores karrierevalg. F.eks. så jeg Jens igen, mens jeg studerede datalogi – han tog et bifag (som det hed dengang) i datalogi og fulgte i den anledning nogle kurser på Aalborg Universitet. Så nu sad vi pludselig til de samme forelæsninger. Senere igen begyndte Jens at undervise i førsteårs-kurser i matematik på Aalborg Universitet, og siden tog han springet, forlod Fjerritslev Gymnasium og blev studielektor på vores adgangskursus. Nu var Jens og jeg faktisk blevet kolleger.

Jens’ store passion for Italien og italiensk kultur (inklusive kogekunst og vin) og hans store viden om og interesse for lokalhistorie og for dansk litteratur er også en del af billedet af ham som det hele menneske, han er. De triste myter om matematikeren som fagidiot skyldes bestemt ikke ham.

Når nogen, jeg har kendt længe, går på pension, begynder jeg selv at spekulere over hvordan det mon vil være for mig. Det er trods alt ved at være et par år siden, jeg selv holdt mit 25-års jubilæum. Vi snakkede til receptionen lidt om hvordan det er at trække sig tilbage – om der mon ikke er en slags abstinenssymptomer, når man nu har beskæftiget sig med sit fag så længe. Og det er der vel, sagde Jens – han mente nok at han ville læse lidt matematik engang imellem. Det tror jeg også han vil ende med at gøre; når man holder af sit fag, er det ikke sådan at slippe det.

Jeg glæder mig til at se ham igen.

Liden semi-Thue kan vælte stort læs, eller: Programmering ved omskrivning

Udgivet den af
Svar

Thue

Da jeg var studerende og fulgte kurset Modeller for beregnelighed, var ét af emnerne andre modeller for beregnelighed end Turing-maskiner. Her stødte jeg på Chomskys generelle grammatikker og på Thue-systemer. Den slags underviser vi ikke i længere (nu er det nemlig mig, der underviser i efterkommeren af det gamle kursus) – lærebogen lægger ikke op til det, og der er andre emner, der er mere centrale. På en måde er det nu en skam.

Thue-systemer dukker op allerede omkring forrige århundredeskifte i den norske matematiker Axel Thues arbejde om såkaldte ordproblemer for frie algebraer. Et Thue-system T er en endelig mængde af uordnede par af strenge

T = \{ (u_1,v_1), \ldots, (u_k,v_k)\}

Tænk på dem som at u_i kan skrives om til v_i – og at v_i kan skrives om til u_i. Vi tillader også at strenge kan skrives om i en kontekst, dvs. at s u_i t kan skrives om til s v_i t – og omvendt. En streng kan selvfølgelig altid “skrives om” til sig selv. Det vi har fat i her, er altså en ækvivalensrelation, “kan skrives om til ved brug af T“, og ordproblemet for Thue-systemer er nu

Givet et Thue-system T og to strenge u og v, kan u så skrives om til v ved brug af T?

Dette problem er uafgørbart (ideen i beviset er at lave et Thue-system ud fra en Turing-maskine M; konstruktionen er oplagt: strengene i Thue-systemet er konfigurationer i M).

I et semi-Thue-system

S = \{ (u_1,v_1), \ldots, (u_k,v_k)\}

er parrene nu ordnede, og (u_i,v_i) betegner at u_i kan omskrives til v_i – men ikke omvendt (medmindre (v_i,u_i) \in S). Også for semi-Thue-systemer er ordproblemet uafgørbart, for et Thue-system er jo bare et symmetrisk semi-Thue-system.

Først for ganske nylig er det gået op for mig, at der findes et programmeringssprog, der baserer sig på semi-Thue-systemer! Sproget hedder Thue (men burde hedde Semi-Thue). Det blev udviklet i 2000 af en amerikaner ved navn John Colagioia. I et Thue-program def

Her er et lille eksempel (lånt fra Esolangs side om Thue, en af de få kilder til oplysninger om dette sprog). Det er et program, der kan lægge 1 til et binært tal (der i dette eksempel er 1111111111).

1_::=1++
0_::=1

01++::=10
11++::=1++0

_0::=_
_1++::=10

::= _1111111111_

Egentlig er ideen ikke så urimelig. Genskrivning af strenge kunne man selvfølgelig også udtrykke i et sædvanligt applikativt programmeringssprog som ML eller Haskell – eller i et logikprogrammeringssprog, for den sags skyld. Men man kunne bruge ideen til at give en koncis repræsentation af strukturel operationel semantik for abstrakte maskiner eller såmænd “bare” for almindelige programmeringssprog, for alle regler i den slags semantikker er jo netop genskrivningsregler (eller kan formuleres som sådanne, hvis man bruger evalueringskontekster).

Det kunne faktisk være et interessant projekt for studerende – at genoplive Thue eller lave et helt nyt programmeringssprog, hvor termgenskrivning er den centrale kontrolstruktur.

Rózsa Péter

Udgivet den af
Svar

Rozsa Peter

Hvis man kender til funktionsorienteret programmering, er det nok ikke overraskende, at teorien om beregnbare funktioner er af central betydning i datalogi. Når man i matematik og teoretisk datalogi taler om de beregnbare funktioner, er det kendt af mange at Kurt Gödel indførte de primitive rekursive funktioner i sit berømte arbejde om ufuldstændighed af logiske teorier. Mange ved også at Stephen Kleene definerede klassen af \mu-rekursive funktioner. Og mange ved at Alonzo Church er ophavsmand til \lambda-kalkylen$. Noget mindre kendt er Rózsa Péter. Det eneste, jeg hørte om hende i min egen studietid, var en kort bemærkning fra min kursusholder i kurset “Modeller for beregnelighed” om hendes bog Recursive Functions.

Det er Rózsa Peter, der indførte betegnelsen primitive rekursive funktioner. Dette er klassen af de funktioner over de naturlige tal, der kan defineres ud fra konstantfunktionen 0, efterfølgerfunktionen, projektion, funktionssammensætning og primitiv rekursion, dvs. rekursive definitioner der (løst sagt) definerer f(n+1) ud fra f(n). De \mu-rekursive funktioner kan man få ved også at tillade ubegrænset minimalisering \mu x.f(x), der som værdi har det mindste x så f(x) = 0. Det er ikke sikkert, at en sådan “rod” findes, og derfor kan \mu-rekursive funktioner risikere at være partielle og ikke totale funktioner. De primitive rekursive funktioner er derimod alle totale.

Rózsa Peter blev født i 1905 og voksede således op i en omskiftelig tid for Ungarn og Europa i det hele taget, og det var dengang stadig usædvanligt at kvinder studerede matematik. Hun opgav en overgang karrieren som matematiker og koncentrerede sig om at skrive digte. Men Rósza Peter begyndte igen, og hendes arbejde om rekursiv funktionsteori i 1930′erne var væsentligt. Da fascisterne fik magten i Ungarn og i 1939 vedtog en række antisemitisk love blev Rózsa Peter ramt af dem (som en del andre kendte ungarere havde hun jødisk baggrund), men hun overlevede 2. verdenskrig og blev sidenhen en væsentlig skikkelse i ungarsk matematik. Blandt andet blev Rózsa Péter en kendt foredragsholder og popularisator – mange af hendes foredrag havde titlen “Matematik er smukt”. Dover Press har stadig hendes populærmatematiske bog Playing With Infinity. En af hendes sidste bøger, Recursive Functions in Computer Theory, der udkom året før hendes død, viser at hun i høj grad var opmærksom på anvendeligheden af rekursive funktioner i datalogi. Som man vil opdage af biografien hos The MacTutor History of Mathematics, døde Rózsa Péter dagen før sin 72-års fødselsdag.

Det gode eksempel på en funktion, der ikke er primitiv rekursiv, er Ackermanns funktion. Den blev, som navnet antyder, opdaget af Wilhelm Ackermann, men den formulering af definition, som man normalt ser i dag, skyldes Rósza Péter:

A(0, y) = y + 1
A(x + 1, 0) = A(x, 1)
A(x + 1, y + 1) = A(x, A(x + 1, y))

Og så var Rózsa Péter også engageret i arbejdet for at gøre det mere accepteret og udbredt for piger og kvinder at beskæftige sig med matematik. At Rózsa Péter ikke er mere kendt end hun er, skyldes dog nok ikke så meget hendes køn (hun var jo trods alt temmelig kendt i sit hjemland) som det skyldes de internationale relationer under den kolde krig, hvor mange østeuropæiske forskeres væsentlige bidrag til matematik og naturvidenskab ikke fik den anerkendelse, de fortjente.

Alle veje fører bort fra Rom

Udgivet den af
Svar

2013-01-25 17.34.21

 

Det uventede sker altid, når man mindst venter det. Sådan en tautologisk formulering kunne der så i en af de projektrapporter fra 1. semester, jeg i disse dage prøver at læse uden alt for voldsom brug af rød kuglepen. Men faktisk passer det jo.

Jeg kom tilbage til hotellet efter en ikke særligt festlig festmiddag til POPL, pakkede og gik i seng. Morgenen startede på hotellet, hvor jeg delte morgenbord med bl.a. Earl Barr (en amerikaner i London), der skulle holde foredrag om eftermiddagen – hvor jeg desværre var på vej hjem – og Loris D’Antoni (en italiener i Philadelphia). Han fortalte mig om et lille projekt, han er ved at lave om automatisk retning af opgaver i automatteori. Ideen er baseret på at de regulære sprog har samme udtrykskraft som andenordens monadisk logik over endelige strukturer; dvs. at man ud fra en logisk formel, der beskriver et regulært sprog, med en algoritme kan konstruere en automat, der genkender sproget. Alle opgaver om at konstruere automater i f.eks. Sipsers bog bruger formuleringer, der ligner andenordens monadisk logik en hel del. Og på baggrund af dette kan man så lave et stykke software, der kan hjælpe med at give feedback på studerendes løsninger på opgaver af denne slags. Den sidste idé var især overraskende.

Oppe på mit værelse skulle jeg til at hente min kuffert, da telefonen ringede. Min mor, der er dement og har boet på plejehjem siden 2001, havde fået en blodprop og var faldet. Det var noget af et chok at få denne besked, og efter jeg havde tjekket ud og var henne til de sidste POPL-foredrag jeg kunne nå, kneb det lidt for mig at koncentrere mig om at følge med i det inviterede foredrag. Men min kone tog hen for at besøge min mor og kunne skrive til mig, at min mor allerede var i klar bedring. Min kone er et helt utroligt godt menneske!

Således lettet kunne jeg gå til pausen, og her traf jeg igen Daniel Hirschkoff, der er lektor på universitetet i Lyon. Vi havde snakket sammen til BETTY-mødet i Bruxelles tilbage i oktober, og igen her til POPL. Daniel var interesseret i både mit arbejde fra 2011 om simpelt typede psi-kalkyler og det arbejde, jeg lige nu slås med at få færdigt om resursesensitive typesystemer for psi-kalkyler. Så det endte vi med at sidde og snakke om, og jeg endte med at love at jeg vil have min nye artikel klar til sidst i marts. Det lover jeg hermed også her.

Sådan havde jeg ved POPL i løbet af 35-40 minutter haft bedre muligheder for at snakke med nogen om min aktuelle forskning end jeg har haft i hele det forgangne år hjemme i Aalborg. Det er desværre lidt for sigende.

Jeg nåede at høre endnu et foredrag, hvor Damien Pous (en af Daniel Hirschkoffs tidligere PhD-studerende) holdt et forbløffende enkelt foredrag om noget så tilsyneladende elementært som en ny og enkel afgørbarhedsprocedure for ækvivalens af NFA’er; den bruger det, vi kalder koinduktion og op-til-teknikker. Dette var et foredrag, som en kvik tredjeårsstuderende nemt ville kunne følge med i og holde af. Til sidst stillede en fyr fra Birmingham en værre glædesdræber af et spørgsmål, nemlig om ikke alt dette kunne formuleres kategoriteoretisk. Og jo, det kunne det. Mere fik vil (heldigvis) ikke at vide her.

Derefter verdens hurtigste frokost – penne all’arrabbiata på under 10 minutter – og så i taxi ned til banegården til det gennemgående tog ud til lufthavnen. Toget leverede i dagens anledning en forsinkelse af den slags, som dataloger kan bruge i foredrag, når de skal overbevise alle om at programanalyse er vigtig. Midt i det hele standsede det gennemgående tog, og lyset og alle informationsskærme gik ud. Efter nogle minutter tændtes informationsskærmene igen, og sørme om ikke det viste at togets computer var ved at genstarte! Vi var strandet her på grund af hvad der formodentlig var en softwarefejl.

Vel ude i lufthavnen, henne ved gaten mødte jeg ingen ringere end Hanne Riis Nielson fra DTU. Hun var mindst lige så overrasket over at se mig som var jeg var over at se hende. Og nej, hun havde ikke været til POPL, men til et møde i forbindelse et EU-projekt om “security and safety”. Jeg var nødt til at fortælle hende historien om toget.

Og her sidder jeg så nu i Københavns Lufthavn (i den italienske café efter indtagelse af en pizza med en meget uitaliensk og lidt for paplignende bund), hvor vinteren er på sikker afstand af en rude. Min kone kunne fortælle mig, at vores datter har fået konstateret en penicilinkrævende streptokok-infektion; det er derfor hun stadig har ondt i halsen. På den måde lykkedes det vores familie at få strakt vores infektions-sæson på tværs af julen ind i februar. Surt for alle parter. Men om et par timer er jeg hjemme.

POPL

Udgivet den af
Svar
popl

Udsigt over parallelfrokost nr. 1 ved POPL 2013.

I dag startede hovedkonferencen Principles of Programming Languages, bedre kendt som POPL. POPL er på mere end én måde en af de største konferencer, jeg har været til (jeg har været med flere gange tidligere). For det første er antallet af deltagere overvældende stort – der er så mange, at der er tre parallelle frokost-serveringer i tre store lokaler. Dét har jeg aldrig set før, heller ikke til de tidligere POPL, jeg har deltaget i. Og for det andet er kvaliteten af bidragene rigtig høj. Det er måske ikke alt, der er lige spændende for alle og heller ikke for mig, men jeg bed mig som sædvanlig fat i nogle foredrag.

Dagens første foredrag var et indbudt foredrag af Georges Gonthier fra INRIA/Microsoft Research, der fortalte om det maskintjekkede bevis for Feit-Thompsons sætning om entydig faktorisering af grupper af ulige orden. Det har jeg tidligere skrevet om her. Gonthier fortalte først om sætningen og dens gruppeteoretiske grundlag og dernæst om arbejdet med at repræsentere beviset i typeteorien Calculus of Constructions eller rettere i værktøjet Coq, der er en implementation af denne. Den helt centrale indsigt som Feit og Thompson gjorde var at betingelserne for at være en gruppe, der ikke opfylder entydighedsbetingelsen i sætningen kan fanges i Galois-teori. Men det betyder så også at en repræsentation i Coq skal fange en hel masse standardbegreber i gruppeteori og resultater om dem – helt fra simple begreber som grupper, normale undergrupper og sideklasser over Sylows sætninger, Frobenius-grupper og sætninger i Galois-teori. Intet under at det tog så mange mennesker så lang tid at lave dette maskintjekkede bevis; én ting er at forstå gruppeteorien, en anden er at beskrive den inden for typeteori og formalisere hvert eneste lille lemma i Coq. Gonthiers foredrag var lidt for langt og af og til fortabte han sig i de mange interessante detaljer af både matematisk, typeteoretisk og mere programmeringsnær art, dette imponerende projekt rummer. Men jeg hæftede mig ved to ting. For det første lader det til at “rigtige” algebraikere (ifølge Gonthier) synes at dette er spændende. For det andet opdagede Gonthier og hans kolleger undervejs at der faktisk var en træls trykfejl i Feit og Thompsons artikel, der sneg sig videre fra den første af deres første lange artikler med det oprindelige bevis ind i den anden – men at denne trykfejl ingen betydning havde, da den optrådte i en betingelse, der i det computertjekkede bevis viste sig at være overflødig!

Der var også andre interessante foredrag om bl.a nominelle mængder (et emne, jeg selv er endt med at berøre), om typeinferens for forfiningstyper (et andet emne, jeg engang kastede mig over – men min tidligere samarbejdspartner Naoki Kobayashi opdagede at han kunne genbruge et trick med at reducere dette problem til løsning af lineære uligheder!) og et spændende foredrag af Sam Staton om hvordan man kan forstå typereglerne for funktionsorienterede programmeringssprog ved brug af kategoriteori. Alle tre foredrag rummede resultater af stor værdi, men hvad bedre var: foredragsholderne fik præsenteret de vigtige ideer uden at fortabe sig i detaljer. Det er bestemt ikke altid at selv et foredrag på en prestigefyldt konference når ud over scenekanten.

Jeg blev væk fra nogle foredrag for at tage en lille tur ud i byen. Jeg fik skimtet Colosseum og Vittorio Emmanuele-monumentet i det fjerne og det gik op for mig, at jeg var havnet i samme del af den italienske hovedstad som jeg havde set, sidst jeg var for over 26 år siden! En mindre stolt oplevelse er at jeg ikke kunne finde ud af at tage bussen – eller rettere: Det kunne jeg godt, men jeg vidste ikke, at man ikke kunne købe billetter i bussen. De kan købes i kiosker og tobaksforretninger og kun dér. Så hvis buschaufføren læser dette indlæg, kan han vel egentlig afkræve mig kontrolafgift for at have kørt i bus uden billet (jeg fik dog købt en billet på tilbagevejen).

Internetforbindelsen på mit hotel er ikke fantastisk, vel ofte sammenlignelig med gamle dages 28 kilobaud-modemmer, og til konferencen er forbindelsen hurtigere men til gengæld ekstremt overbelastet (vel at forvente, når man placerer flere hundrede mennesker med hver deres computer i samme lokale), så underligt nok er jeg mere offline end jeg ellers er på rejse. Til gengæld lærer jeg en del om stoisk tålmodighed på denne rejse af dårlige netforbindelser og køer i lufthavne og hoteller og til servering af mad og drikke; det er måske ikke så overraskende, at stoicismens vigtigste repræsentanter Seneca og Marcus Aurelius var romere.

Tårnene i Benares

Udgivet den af
Svar

2013-01-15 09.16.23

Sommetider er jeg uhyggeligt lang tid om at opdage noget indlysende. Det var faktisk først i den uge, der nu snart er forbi, at jeg opdagede det: den store mosaik, der pryder en af facaderne på Selma Lagerlöfs Vej 300, hvor Institut for datalogi holder til, må være en illustration af tårnene i Hanoi, der retteligt bør kaldes for tårnene i Benares. Mange, der har fulgt kurser i diskret matematik eller algoritmeteori, har set dette lille puslespil. Vores bygning (der er designet af Friis og Moltke og faktisk minder mig lidt om en anden af deres bygninger, nemlig Fjerritslev Gymnasium, hvorfra jeg blev student) er nu ikke vores oprindelig. Den blev oprindelig brugt af KMD, så allerede dengang må man have tænkt over tårn-puslespillets forbindelse til programmering.

Selv læste jeg for første gang om tårnene i Alle tiders tal, en populærvidenskabelig bog om matematik fra Politikens forlag. Det var en bog, jeg pløjede igennem igen og igen, da jeg gik i folkeskolen. Allerede dengang vidste jeg at tårnene i Benares (som bogen kaldte spillet) var en historie, som skyldes den franske matematiker Edouard Lucas. I 1883 lancerede han under pseudonymet N. Claus de Siam fortællingen om et tempel i Benares i Indien, hvor der står tre små diamantnåle. På nål nr. 1 var oprindelig lagt 64 skiver af guld, den ene mindre i diameter end den anden. Et hold præster er travlt beskæftiget med at flytte skiverne over på nål nr. 3 én ad gangen, idet de kun må flytte en skive over på en skive med større diameter. Når nålene er flyttet over på nål nr. 3, går verden under. (Alt dette lyder lidt som en beskæftigelsesministers ønskedrøm, ikke?)

Hvorfor er tårnene i Benares endt med at blive kaldt for tårnene i Hanoi? Måske fordi N. Claus de Siam skulle forestille at være på universitetet i Hanoi; Vietnam var dengang kolonien Fransk Indokina. Forvirringen er formodentlig sket i oversættelsen fra les tours de Hanoï, der nemlig både kan betyde “tårnene fra Hanoi” og “tårnene i Hanoi”.

Ligesom de regulære udtryk er tårnene i virkeligheden en forbilledlig illustration af en lang række beslægtede begreber – her inden for datalogi og diskret matematik. Algoritmen, der løser flytteproblemet, kan beskrives rekursivt – og den rekursive algoritme giver anledning til rekurrensligninger, der bestemmer algoritmens tidskompleksitet (målt i antal flytninger). Et bud på løsningen til ligningerne kan bevises at være korrekt ved brug af matematisk induktion – og man opdager at tidskompleksiteten er eksponentiel i antallet af skiver. Så langt når de fleste.

Men der er mere, meget mere at sige om tårnene. Man opdager, at tårnspillet er selv-similært i den forstand at spillet med n skiver rummer to kopier af spillet med n-1 skiver og at spil-grafen for tårn-spillet derfor er en approksimant til Sierpinskis trekant. Den optimale løsning (dvs. den strategi, der anvender færrest flytninger) svarer til en Hamilton-sti i spil-grafen. Og man kan repræsentere løsningen til spillet ved brug af de såkaldte Gray-koder (dem har Donald Knuth skrevet en grundig introduktion til). MathWorld og Wikipedia er gode steder at læse mere til en start.

Men én gåde er stadig uopklaret, i al fald for mig: Forestiller mosaikken virkelig tårnene i Benares, eller er det mig der opdager et “ansigt i tapetet”?

Firs-tyve

Udgivet den af
Svar

firstyve

Af og til hører jeg om “80/20″-reglen. Det anslås at 80 procent af alle køretidsfejl i Microsofts software skyldes 20 procent af fejlene i koden. Jeg kan også læse, at det i USA er 20 procent af de kriminelle, der begår 80 procent af al kriminalitet.

Jeg tør ikke sætte tal på, men jeg har også selv en fornemmelse af at det til offentlige møder oftest er en lille andel af de tilstedeværende, der taler suverænt mest (ved de foredrag, jeg har givet om gruppebaseret projekteksamen har det hver gang været sådan) og af at det både i studerendes projektarbejde og i egen og andres forskning så godt som altid er tilfældet at det meste og det mest spændende sker i den sidste måned – så der bliver brugt uforholdsmæssigt meget tid i starten på noget, der senere viser sig at være af begrænset værdi.

80/20-reglen blev formuleret i 1906 af den italienske økonom Vilfredo Pareto (1848-1923), der bl.a observerede at 20 procent af hans ærteplanter leverede 80 procent af udbyttet og at 80 procent af al jord i Italien, da Pareto levede, blev ejet af 20 procent af befolkningen. Den tid, hvor Pareto var aktiv, var i øvrigt også den tid hvor en anden italiener, Corrado Gini, gav sit bud på et kvantitativt mål for økonomisk ulighed, den såkaldte Gini-koefficient. Også Ginis arbejde er baseret på studiet af fordelingsfunktioner.

Reglen hænger sammen med en antagelse om at mange fænomener følger det, man nu kalder en Pareto-fordeling. En stokastisk variabel X er Pareto-fordelt med parametre \alpha og x_m hvis dens fordelingsfunktion er givet ved

F_X(x) = \begin{cases} 1 - (\frac{x_m}{x})^{\alpha} & \mbox{for } x \geq x_m \\ 0 & \text{for } x < x_m \end{cases}

Så x_m angiver en minimumsværdi, som X kan antage. Hvis man sætter \alpha = \log_4 5 \approx 1.16, får vi netop 80/20-reglen.

Er Pareto-fordelingen “naturlig”? Det ved jeg ikke – jeg er ikke matematikøkonom (læser du min blog, Esben?) – men der findes en samling resultater som giver tilstrækkelige betingelser for hvornår en stokastisk variabel er Pareto-fordelt. På den måde er de vel en slags pendanter til den centrale grænseværdisætning.

Hvis arbejdsindsats også er Pareto-fordelt og følger 80/20-loven, skulle man tro at man kunne effektivisere sin arbejdsplanlægning. Men hvis man udvælger 20 procent af opgaverne og nøjes med at koncentrere sig om dem, betyder det kun, at man stadig vil ende med at bruge 80 procent af sine resurser på 20 procent af dette udvalg. Fordelingskurven er nemlig selv-similær i matematisk forstand!

80/20-reglen er under alle omstændigheder ikke en universel lov, og det er vigtigt at huske. I bedste fald er 80/20-reglen vel en beskrivelse af bestemte situationer, hvor man ikke regulerer det, man måler. Tallene er ikke naturkonstanter. I samfund med stor social ulighed ser det som bekendt ganske anderledes ud – for eksempel er det i nogle lande i verden en meget lille procentdel af befolkningen, der ejer næsten al jord. Hvis vi vil forhindre at 80 procent af jorden ejes af 20 procent af befolkningen, kan det ske gennem en jordreform. På tilsvarende vis kan man påvirke fordelingen af den tid, man bruger på bestemte arbejdsopgaver.

Desuden er det vigtigt at huske, at vi har en tendens til at hæfte os ved de tilfælde, der bekræfter vores hypotese – nemlig de tilfælde, der opfylder 80/20-reglen. I virkeligheden er de interessante tilfælde jo de mange tilfælde, hvor det ikke sker!