Kategoriarkiv: Matematik

Hemmelig deling

Secretsharing-3-point

I dag var jeg til workshop om secret sharing på Institut for matematiske fag. Dette er et emne med forbindelse til kodningsteori og kryptologi, og der var både matematikere og dataloger til stede fra flere danske universiteter (og en enkelt industriel personlighed). Det er ikke nogen ny idé, vi har med at gøre – den skyldes israeleren Adi Shamir og amerikaneren George Blakley, der fandt hver deres løsning på samme udfordring hver for sig i 1979. Secret sharing er den udfordring at lade et antal deltagere have hver deres del af et hemmeligt stykke data, men på en sådan måde at der skal et vist, bestemt antal deltageres viden til for at det hemmelige stykke data kan rekonstrueres.

Blakleys løsning er måske den nemmeste at forstå; hvis hemmeligheden skal deles med n deltagere, skal vi opfatte den som et punkt i et n-dimensionalt rum og fortælle hver af de n deltagere en plan i rummet. Planerne skal man vælge sådan, at de skærer hinanden i ét punkt – nemlig det punkt, man vil holde hemmeligt. Kun når man har kendskab til alle n planer, ved man hvad det hemmelige punkt er.

Shamirs løsning går (meget løst sagt) ud på dette: Hvis vi vil holde et tal hemmeligt og dele det med n deltagere, og tærskelværdien skal være t, dvs. at der skal t af de n deltagere til for at finde frem til den hemmelige talværdi, skal man at konstruere et polynomium af grad t-1 og oplyse n punkter fra polynomiets graf. Vi ved nemlig at vi kan bestemme et polynomium af grad t-1 entydigt, hvis vi kender t punkter på dets graf. Den ledende koefficient i polynomielt (dvs. den, der har højest orden) skal være den hemmelige værdi; resten vælger vi tilfældigt. Her kommer forbindelsen til kodningsteori ind, for det vi har lavet her, er det man også kalder for en Reed-Solomon-kodning.

I al fald er emnet stadig vigtigt i både matematik og datalogi, og Olav Geil og Diego Ruano fra AAU har allerede en del interessante resultater om emnet – og de har for nylig fået forskningsrådspenge til at arbejde videre med det.

Til dagens workshop var der både italienere og spaniere til stede, og stemningen var så positiv, at de endog helt frivilligt begyndte at snakke om VM i frokostpausen!

flattr this!

Kragearitmetik

krage

Oppe bag ved vores hjem i Nørresundby ligger Skanseparken, hvor der er ganske mange krager, der bygger deres rede højt oppe i de gamle bøgetræer. Af og til kan jeg høre de gråsorte fugle skræppe op; derudover har jeg ikke tænkt så meget over hvad der er særligt ved kragerne.

Men artikel fra 2000 af tre ornitologer fra Moskvas Statsuniversitet tyder på at krager har et talbegreb. Forskerne serverede foder i to skåle for fuglene, der så kun måtte indtage foder fra den skål, de første valgte. Kragerne valgte typisk den skål, hvor der var flest stykker foder.

Det gjorde duer også, men de var ikke så gode til at tælle som kragerne – duer kunne kun vælge den mest fyldte skål, hvis der var mere end 3 stykker foder til forskel på antallet af de to skåle. Krager kan endda forstå en ordningsrelation; de kan skelne mellem en skål med få, større stykker føde og en anden skål med flere, men synligt mindre stykker foder.

Sådan et resultat er interessant, for det viser at talbegrebet også har en eksistens uden for den menneskelige forstand – hvis krager kan tælle, kan andre intelligensvæsener langt fra vores planet det sikkert også. Også en artikel fra Videnskab.dk fortæller om hvad krager forstår. Og alt dette får mig også til at tænke en noget mere jordnær tanke: at ganske vist er naturen vel ikke “besjælet”, men den er på den anden side heller ikke “dum”.

 

flattr this!

Er der en doktor til stede?

flag
Det “schweiziske flag” i 2 og flere dimensioner (fra Martin Raussens doktorafhandling).

I dag forsvarede Martin Raussen sin doktorafhandling i matematik her på Aalborg Universitet. Jeg har kendt Martin i mange år og har lidt på afstand prøvet at følge med i hvordan han sammen med bl.a. Lisbeth Fajstrup, der også er fra Institut for matematiske flag – undskyld, Institut for matematiske fag –og udenbys kolleger været motiveret af bestemte problemer inden for parallel programmering med gensidig udelukkelse til at udvikle et nyt område af algebraisk topologi, hvor man betragter homotopier mellem (klasser af) orienterede stier i planer. Stier svarer til “spor” i en programudførelse, og dimensionerne af det rum man betragter, svarer til antallet af parallelle komponenter. Orienteringen kommer ind i billedet på grund af den temporale ordning af programskridt.

Hvis man tror, at det kun er “diskret matematik” (som vel ofte mest forstås som al den matematik, der ikke er “kontinuert matematik”) som har forbindelser til datalogi, tager man fejl. Martin hævder selv at hans resultater ikke er særligt dybe, men her er det vist hans beskedenhed, der sætter ind.

Jeg fik dog ikke hele forsvaret med, for jeg var kommet af sted til NOVI uden mit adgangskort – døren lukker kl. 16, og jeg ville nødig smækkes ude. Dog har jeg en særdeles velbegrundet formodning om at Martin får sin doktorgrad og tør derfor godt ønske ham tillykke!

flattr this!

Kim Ung-Yong

kimungyong

Kim Ung-Yong er fra Sydkorea og er født i marts 1962, dvs. knap to år ældre end mig. Ved et tilfælde faldt jeg over en artikel om ham, og da huskede jeg hvordan jeg første gang læste om ham, nemlig i Guiness’ rekordbog. Her var der en beretning om hvordan han i sin tid deltog i et tv-program i Japan. Det interessante i denne sammenhæng var at han på dét tidspunkt var 7 år gammel.  Kim Ung-Yong talte flere sprog flydende og viste at han kunne løse differentialligninger (lineære homogene af slagsen, ser det ud til). Få år senere kom han til USA og fik en kandidatgrad og en PhD i fysik. I 10 år arbejdede han for NASA.

Til sidst, som 18-årig, vendte Kim tilbage til Sydkorea for at studere. Han var faktisk nødt til at starte forfra, for han havde ikke noget eksamensbevis fra en skole i sit hjemland. En del mennesker i medierne udråbte Kim Ung-Yong til en fiasko, da han begyndte at studere til anlægsingeniør og fik et upåagtet job i et upåagtet firma. han levede ikke op til “idealerne”, syntes de. Men det han tilsyneladende mest af alt havde længtes efter var at have venner på sin egen alder og at få et godt liv.

I dag er Kim Ung-Yong blevet universitetslærer – han havde længe drømt om at komme til at undervise.

Kim claims that people invest too much meaning in IQ. “Some think people with high a IQ can be omnipotent, but that’s not true. Look at me, I don’t have musical talent, nor am I excelling in sports,” he said.

Just like the world records for athletes, having a high IQ is just another element of human talent. “If there is a long spectrum of categories with many different talents, I would only be a part of the spectrum. I’m just good in concentrating on one thing, and there are many others who have different talents,” he explained.

Dette citat lader vi lige stå lidt som en modvægt til både anti-intellektualisme og hovedløs dyrkelse af en bestemt forestilling om en elite.

flattr this!

De særligt udvalgte

genius

Amerikaneren Jordan Ellenberg var et særdeles fremmeligt barn, og i dag er han professor i matematik ved University of Wisconsin. Ellenberg påpeger en myte, mange tror på, nemlig at “matematik er for de særligt udvalgte”. Han skriver:

One of the most painful aspects of teaching mathematics is seeing my students damaged by the cult of the genius. That cult tells students that it’s not worth doing math unless you’re the best at math—because those special few are the only ones whose contributions really count. We don’t treat any other subject that way. I’ve never heard a student say, “I like ‘Hamlet,’ but I don’t really belong in AP English—that child who sits in the front row knows half the plays by heart, and he started reading Shakespeare when he was 7!” Basketball players don’t quit just because one of their teammates outshines them. But I see promising young mathematicians quit every year because someone in their range of vision is “ahead” of them.

Som  Ellenberg skriver, er dette en myte, der får nogle uddannelsessøgende til at blive fortvivlede og måske helt give op. Andre bruger myten til at undskylde deres manglende indsats i faget (jeg har en trist fornemmelse af at mange danske journalister abonnerer på myten). Og blandt dem, der interesserer sig for faget og bliver gode til matematik og endda kommer i gang med en akademisk karriere, kommer skuffelserne også – for der er som regel nogen et sted, der er bedre end én selv. Atter andre kan så til gengæld bruge myten til at opfatte sig selv som de “særligt udvalgte” i den akademiske verden – dvs. kun indtil de en dag måske bliver udfordret af én, der er bedre end dem selv. Nogle ganske få flyder ovenpå gennem det hele og bliver de “særligt udvalgte”. Myten bekræfter på denne måde sig selv.

Selvfølgelig skal man ikke savne evner inden for det fag, man interesserer sig for. Ingen har glæde af en kok, der ikke kan lave mad. Men talentet bliver ikke til noget, hvis man ikke nærer det. Og man kan i mange tilfælde blive meget bedre, end nogen havde regnet med, hvis man gør sig umage.

Ellenbergs pointe er at man skal have et mindre fokus på dem, der er rigtig dygtige som børn – eller rettere, at man ikke skal fokusere kun på dem. Der er nemlig så mange andre, der også udmærker sig senere i livet.  De allerfleste, der gør karriere inden for matematik (eller i den akademiske biks i det hele taget) er faktisk ikke fremmelige børn. Det er dem, der er udholdende og gør en stor indsats. Det vigtige er at påpege vigtigheden af at gøre indsats som studerende og at være vedholdende. Myten om de “særligt udvalgte” forhindrer mange studerende i at være vedholdende, fordi myten “vælger dem fra”, og den fastholder billedet af en spontant opstået elite.

Og samtidig kan myten ikke forklare hvorfor det er vigtigt at have matematik som del af sin almene dannelse. Derimod giver myten mange mennesker en undskyldning for at lade være med at beskæftige sig med matematik. Jeg kender ikke så få familier, hvor en eller flere erklærer at de ikke kan finde ud af matematik og så får andre til at tage sig af dette.  Og jeg læser af og til om akademikere (typisk er det humanister) der nærmest virker stolte over ikke at kunne finde ud af selv helt grundlæggende matematik.

Hvilket ramaskrig ville der ikke lyde, hvis der var mange familier herhjemme, hvor det kun var ét enkelt familiemedlem, der kunne skrive,  eller hvis akademikere med naturvidenskabelig baggrund stolt erklærede, at de ikke kunne finde ud af skrive en læsbar tekst og gav op allerede i 5. klasse, og at det at skrive var en på én gang ligegyldig og uopnåelig færdighed forbeholdt professionelle forfattere?

flattr this!

P=NP, siger Knuth

hex

Da jeg studerede, var der et spil, vi ofte spillede, nemlig Hex. Spillet blev opfundet af Piet Hein tilbage i 1942 og spilles af to mennesker (vi kan jo kalde dem rød og blå) med blyant og ovenstående spillebræt på et stykke papir. Hver spiller har to modstående sider af rhomben.

De to spillere skiftes til at afkrydse et felt. Målet er at blive den første, der kan lave en ubrudt følge af krydser der forbinder de to modstående sider.

I 1949 viste John Nash (ham fra A Beautiful Mind) at der er vindende strategi i Hex men han viste ikke hvordan sådan en strategi ser ud! Man ved hvordan vindende strategier ser ud op til 9 gange 9 felter, derefter ved man ikke noget endnu. Hvis man skal se positivt på det, betyder det at det stadig bør være sjovt at spille Hex.

Men den slags ikke-konstruktive argumenter bør få én til at tænke. Det er underligt at vide at der findes et bestemt objekt (som her er en strategi) men ikke at vide hvordan det ser ud.

Der er et interessant interview med den legendariske datalog og matematiker Donald Knuth hvor han bruger Hex som del af en begrundelse for at tro at \mathrm{P=NP}-formodningen har et positivt svar, dvs. at \mathrm{P=NP}. Det er der ellers ikke så mange, der mener. Knuth er til gengæld tilbøjelig til at mene at der er et ikke-konstruktivt bevis for sætningen.

As you say, I’ve come to believe that \mathrm{P=NP}, namely that there does exist an integer M and an algorithm \mathcal{A} that will solve every n-bit problem belonging to the class \mathrm{NP} in n^M elementary steps.

Some of my reasoning is admittedly naïve: It’s hard to believe that \mathrm{P \neq NP} and that so many brilliant people have failed to discover why. On the other hand if you imagine a number M that’s finite but incredibly large—like say the number 10 3 discussed in my paper on “coping with finiteness”—then there’s a humongous number of possible algorithms that do n^M bitwise or addition or shift operations on n given bits, and it’s really hard to believe that all of those algorithms fail.

My main point, however, is that I don’t believe that the equality \mathrm{P=NP} will turn out to be helpful even if it is proved, because such a proof will almost surely be nonconstructive. Although I think M probably exists, I also think human beings will never know such a value. I even suspect that nobody will even know an upper bound on M.

Er det så et godt argument at sige at “Jeg kan ikke forestille mig at det ikke er tilfældet”? Jeg ved det ikke rigtig, men det er interessant og (synes jeg) også lidt skræmmende hvis \mathrm{P=NP} og vi ikke kan få glæde af den viden.

flattr this!

Glæden ved 6

8

Den britiske forfatter Alex Bellos skriver om de to emner, der optager ham: matematik og fodbold, her især brasiliansk fodbold. Sidstnævnte får en del opmærksom fra mange af os inden så længe, så her vil jeg tage fat i tallenes verden.

I sin nye bog, Alex Through The Looking Glass, skriver Alex Bellos blandt meget andet om de følelser, der er forbundet med tal! På sit websted røber han resultatet af en verdensomspændende afstemning om det mest populære tal: Hvilket tal har flest mennesker som deres yndlingstal? Det mest populære tal er ifølge afstemningen 7. Alex Bellos bad også bidragyderne om at begrunde deres valg. En britisk kvinde på 35 svarede om tallet 7:

Nice shape, simple line with vertical and horizontal interest … a number that is growing up. It’s a bit awkward; it can’t be equally divided and won’t bend to the rules so easily!

Herunder er et radioklip fra USA, hvor Alex Bellos bliver interviewet om netop dette.

Men jeg vil ikke selv nøjes med 7. Mit eget yndlingstal er nemlig 8. Jeg er født den 8. januar, og så er 8 jo også en pæn potens af 2, det mindste ikke-trivielle kubiktal og forøvrigt også pænt og rundt at kigge på (et veltegnet ottetal ligner en hyggelig snemand).

flattr this!

P=NP og Hilberts basissætning

pudlak

Et af de emner, som mange inden for datalogi og matematik ynder at tale om er \mathrm{P=NP}-problemet. Problemet er underligt fristende og frustrerende; vi kender problemet godt nok til at kunne formulere det præcist, men løsningen kender vi ikke. Det er lidt som det pæretræ, der står et sted i min svigerfars have; fem meter oppe sidder der hvert år en masse flotte pærer. Men stammen er helt lige og med få grene.

Jeg kan ikke lade være med at tænke på hvordan andre åbne problemer i matematik først er blevet løst efter at der er kommet ny og overraskende indsigt. Bagefter kom standardpensum og lærebøgerne. Et af de helt store problemer i 1800-tallets matematik var det, vi nu kender som Hilberts basissætning i algebra. Er det tilfældet at hvis R er en Noethersk ring, da er ethvert ideal i polynomiumsringen R[x_1,\ldots,x_n] endeligt frembragt? Hermed menes der at der skal findes der en endelig mængde \{k_1,\ldots,k_m\} af elementer i idealet M, således at ethvert element i det kan skrives som en linearkombination af dem.

En Noethersk ring R er en ring, hvor enhver ikke-tom familie af idealer fra R har et maksimalt element. Legemer (men såmænd også bare den sædvanlige ring over  \mathbb{Z}) er eksempler på Noetherske ringe.

Vi har med andre ord at gøre med begreber, som man i dag lærer i algebrakurset på første del af en matematikuddannelse. Så dette problem er inden for rækkevidde på samme måde som \mathrm{P=NP}-problemet er det for datalogistuderende.

Hilberts bevis var et snedigt induktionsbevis – og ikke-konstruktivt. Det er bestemt ikke en overdrivelse at sige, at ikke alle var glade for at dét var tilfældet. Også beviset er i dag inden for rækkevidde af en studerende på første del af en matematikuddannelse. (Senere er der kommet konstruktive beviser for udgaver af basissætningen.)

Klaus Frovin Jørgensen har en gennemgang af hvad Hilberts basissætning førte med sig. På nogle måder er konstruktiv matematik og alt det, den har ført med sig, en reaktion mod Hilberts ikke-konstruktive tilgang. Jeg tror selv at et bevis for \mathrm{P=NP}-problemet vil føre til et lignende jordskred og at beviset for at \mathrm{P=NP} (eller for at \mathrm{P \neq NP}) en dag bliver del af pensum på datalogiuddannelsen. Om jeg så selv når at komme til at undervise i det, er en helt anden snak.

flattr this!

Børn af Brouwer og Prior

Luitzen_Egbertus_Jan_Brouwer
L.E.J. Brouwer
prior
Arthur N. Prior

Det er værd at tænke over at to af de vigtige erkendelser i datalogi kommer fra filosofiens verden. Også jeg er blevet grundlæggende påvirket af disse erkendelser.

I mange år var temporallogik, dvs. studiet af de logiske egenskaber ved udsagn om tid, et rent filosofisk område. Det hele begyndte med Aristoteles. Senere gav den newzealandske logiker Arthur N. Prior (hans navn er et fantastisk ordspil – det er i sig selv en temporal modalitet!) præcise matematiske formuleringer af temporallogikkens grundlag. Temporallogik som en tilgang til beskrivelse af programegenskaber skyldes israelske og amerikanske matematikere med nu afdøde Amir Pnueli som en af de helt centrale skikkelser. Temporallogik er et område inden for modallogik, og også modallogik som sådan har fået vigtige anvendelser i datalogi. Mange af de gamle diskussioner om hvorvidt modallogik og temporallogik overhovedet giver mening at beskæftige sig med er blevet lagt døde af de konkrete anvendelser.

Også intuitionisme har været et kontroversielt emne inden for matematik. L.E.J. Brouwers konstruktions-orienterede tilgang til matematik var begrundet i hans filosofiske overvejelser om matematikkens grundlag. Men inden for de seneste 30 år er intuitionistisk typeteori blevet vigtig inden for datalogi. Bindeleddet er den svenske logiker og matematiker Per Martin-Löf. I dag finder findes interaktive bevistjekkere som Isabelle og Coq stor anvendelse både til formalisering af eksisterende matematik og til kontrol af nye resultater. Især inden for programmeringssprogsteori er dette barnebarn af Brouwer blevet et vigtigt redskab. Tidligere har jeg skrevet om hvordan den fransk-canadiske datalog Georges Gonthier har formaliseret store resultater i grafteori ved brug af netop Coq. I kraft af alle disse praktiske anvendelser er mange af de gamle diskussioner om berettigelsen af konstruktiv matematik reelt blevet lagt døde af konkrete anvendelser.

Det, der er sket i begge tilfælde, er samtidig at det er det  matematiske begrebsapparat, der er blevet til, som har vist sig at udgøre berettigelse, ikke den underliggende filosofiske motivation. Samtidig har der i datalogi været forskere med baggrund inden for matematik og filosofisk logik, som har kunnet se forbindelsen – folk som Dana Scott, Robin Milner og Per Martin-Löf har udgjort dette vigtige bindeled.

flattr this!

En personlig matematisk grundlagskrise

Hver dag sin opdagelse på YouTube. Senest har jeg fundet N.J. Wildberger, der er en canadisk matematiker som er lektor ved University of New South Wales i Australien. Wildberger har lavet en lang række præsentationer, hvis fælles budskab er at matematikkens grundlag skulle være usikkert, og at han derfor nu vil rette op på det. Specielt er Wildberger ked af de reelle tal og vil gerne kunne nøjes med de rationelle tal.

Den slags får uvægerligt alarmklokker til at ringe. Lige nu går diskussion da også på hvad N.J. Wildberger er – er han en crackpot eller er der en faktisk indsigt bag alle hans præsentationer? Jeg har før hørt personer, som havde en kandidatgrad i matematik, udtale at de reelle tal burde afskaffes.

I præsentationen ovenfor kan man se hvor stor vægt Wildberger tillægger konstruktionsprocessen i matematik – for at kunne give en beskrivelse af det velkendte irrationelle tal \sqrt{2}, må han give en konstruktiv beskrivelse af udvidelseslegemer.

Men det forklarer også at Wildberger hverken er en egentlig crackpot eller i gang med at skabe en stor, ny indsigt i matematikkens grundlag. Han er så vidt jeg kan se simpelthen i gang med at genopfinde en form for konstruktiv matematik. Matematikkens grundlagskrise fandt sted for omkring 100 år siden, og N.J. Wildberger ser ud til at gennemleve sin egen lille udgave af den. Der er klare paralleller i hans tankegang til både Brouwers intuitionisme og til Kroneckers finitisme (omend ikke nær så godt formuleret). Wildberger lader til at ønske sig en konstruktiv matematik, der er konsistent med den klassiske – og i dét ønske minder han om den amerikanske matematiker Errett Bishop, der stræbte efter at skabe en konstruktiv matematik, der kun etablerede resultater, der også er klassisk gyldige. I Brouwers intuitionistiske matematik er det anderledes fat – bl.a. er et af de berømte/berygtede resultater at alle reelle funktioner er kontinuerte.

Om Wildberger direkte relaterer sit arbejde til nogen af dem, har jeg endnu ikke fundet ud af. Hvis der er noget nyt hos ham, er det en insisteren på at konstruktiv matematik er den rette tilgang at anvende i matematikundervisning.

flattr this!