OK titlen er på onkelhumor-niveau. Jeg kunne ikke lade være. Det, jeg vil fortælle jer om, er matematikken bag kortprojektioner, altså at lave en god repræsentation af (en del af) den runde jord på et kort, som jo er fladt.

Her ligger Svalbard.

Da Politiken i december skulle vise læserne, hvor Svalbard ligger, brugte de dette kort. Det er rigtig nok, at Svalbard ligger der, hvor den blå pil er. Men det er alligevel ikke helt godt. Der er noget med størrelsesforhold: Svalbard ser ud til at være på størrelse med Storbritannien. I virkeligheden er Svalbard 61.000 km^2 og Storbritannien er 4 gange så stort.   Der er også et problem med retninger. Hvor kommer man hen, hvis man flyver stik nord fra Svalbard og fortsætter i den retning (stik syd, når man passerer Nordpolen)? Det kan man ikke se her – Nordpolen er strakt ud til en ret linje i dette kort.  Kortet er lavet i Mercatorprojektionen. Her kan man lege med arealer i Mercatorprojektionen.

“Stereographic projection SW” by Strebe – Own work. Licensed under CC BY-SA 3.0 via Commons – 

Her er en anden fremstilling af, hvor Svalbard ligger. Det er lidt gnidret, men giver et bedre indtryk af, hvor områder tæt på Nordpolen ligger i forhold til hinanden. Man kan nu se, at en tur stik nord fra Svalbard vil ende et sted i Alaska. Der er stadig problemer med arealerne. Projektionen er en stereografisk projektion.

Google Earth. Nordpolen i centrum.

Google Earth giver et andet billede – men man får igen et meget bedre indtryk af områder tæt på Svalbard.

Hvad er så det bedste kort? Det er ikke så svært at indse, at man får problemer, hvis man vil vise hele Jorden i et enkelt kort. Man er i hvert fald nødt til at lave et hul et sted, før overfladen af Jorden kan strækkes ud i planen. (Hvis man vil ikke vil have flere punkter på Jorden til at ligge oveni hinanden i kortet.)

Her er den matematiske formulering af, hvad et kort er: Man kan give punkterne på Jorden geografiske koordinater (længdegrad, breddegrad)=. Et kort er så en funktion som tager to variable ind og giver to variable ud. For eksempel er Mercatorprojektion givet som 

Google Earth – kortet er sådan cirka 

Og Stereografisk projektion er

I alle tre eksempler, kan man skalere svarende til at squeeze på mobiltelefonen. Det svarer til at gange begge koordinater med en konstant (x,y) -> (kx,ky). Det ændrer ikke på de fundamentale egenskaber ved kortene. Nu kan vi regne på egenskaber ved kort og på et mere overordnet niveau spørge: Findes der kort, som opfylder xxx? Her er nogle spørgsmål og svar:

1. Findes der kort, der bevarer forholdet mellem arealer af landområder? Svar. Ja. (Se nederst for et eksempel)
2. Findes der kort, der bevarer vinkler? Svar: Ja. (Både Mercatorprojektion og Stereografisk projektion gør dette.)
3. Findes der kort med konstant målestoksforhold? Nej.
4. Findes der kort, som opfylder både 1 og 2? Nej.

3 og 4 siger, at der ikke findes et ideelt kort. Man må vælge det, der passer til formålet. Jeg vil ikke give et fuldt argument for 3 og 4 – det kan I jo komme til et af mine foredrag og høre om… Grundlæggende er problemet, at Jordens krumning forhindrer det.

Et kort argument for 3: Forsøg at lave sådan et kort med Nordpolen i centrum. lad os sige, det skal have målestoksforhold m. De punkter på Jorden, hvis afstand til Nordpolen er 50 km (afstand langs med Jordens runde overflade). skal i kortet have afstand km til punktet, der er f( Nordpolen). De ligger altså på en cirkel i planen med omkreds . Ser vi nu på den tilsvarende cirkel på Jorden, der altså udgøres af  punkter 50 km fra Nordpolen, når man måler langs Jordoverflade, så er dens omkreds mindre end . (Man går lidt “ind mod midten”, mens man går fra Nordpolen langs Jordoverfladen) Så skaleringsfaktoren langs denne cirkel er ikke målestoksforholdet m. Og altså er der ikke konstant målestoksforhold.

I Danmark har vi flere kort i spil. De er allesammen vinkelbevarende, da det er væsentligt for opmåling og gør, at “facon” bevares nogenlunde (og da man ikke kan få alting…): Mercatorprojektionen bruges til havområderne, og for landområderne har vi Transversal Mercator Projektion – Mercatorprojektion, hvor man først har drejet kuglen, så en længdegrad er lagt ned på Ækvator. Man skal vælge to ting: Hvilken længdegrad skal være i midten – midtemeridianen og hvad er variationen, afvigelsen fra hovedmålestoksforholdet  (målestoksforholdet er jo ikke konstant, men hvor galt må det gå) det fortæller implicit, hvor bredt kortet bliver. I Danmark har vi UTM med målestoksvariation og to zoner:  Zone 32 med midtemeridian og Zone 33 med midtemeridian  (Bredden på zonerne er altså til hver side. I virkeligheden bruger vi Zone 32 i hele landet undtagen Bornholm, men det er en anden historie.)

Vi har også DKTM, Dansk Transversal Mercator. Der er 4 Zoner med en målforholds afvigelse på maksimalt . DKTM har to zoner i Jylland. Kravet om lille variation af målestoksforholdet giver altså flere zoner, så man må vælge. Få zoner eller lille variation. Det er jo bøvlet at skifte kort 14 gange, når man skal køre fra Aalborg til Thisted, så det vil man gerne undgå.

I Danmark vedligeholdes kort af Geodatastyrelsen og der kan man også læse lidt om matematikken bag. Noget af det, de skriver, kan jeg kende fra mit eget kursus for landinspektørstuderende, men det har en hel generation af landinspektører også været igennem. Og de bliver jo også ansat i Geodatastyrelsen. Lige nu kan jeg faktisk ikke finde noget som helst om teorien bag kort, referencenet etc. på deres hjemmeside, men det er måske fordi de er ved at flytte hele molevitten til Aalborg, så de har nok at se til.

Archimedes’ arealbevarende cylinderprojektion,

Her er en arealbevarende projektion. Som I kan se, er der problemer med faconen på områderne til gengæld.

Jeg har postet dette på Facebooksiden, men nu kommer det også her.

I slutningen af 1950’erne og godt 10 år frem producerede Mathematical Association of America videoer til understøttelse af matematikundervisningen.
Her er en om middelværdisætningen. . Der optræder en politimand og en anvendelse, som giver en studerende en fartbøde…Den er lavet af Bruce og Katherine Cornwell i 1966 og nu lagt på Vimeo af Eric Cornwell – en søn formentlig.

Der er mange andre af Cornwells film på Vimeo.

Om Grænseværdier, Pythagoras, omdrejningslegemer og andet godt. Den om omdrejningslegemer er ret kunstnerisk lavet-

Nu kan jeg minsandten embedde Vimeovideoer! Tak til support hos AAU’s IT-folk

Godt Nytår! Jeg vil undlade at skrive om diverse egenskaber ved tallet 2016 – læs om dem ved at følge linket. I stedet vil jeg lade mig inspirere af Ingrid Daubechies.

Ingrid Daubechies

Hun skrev i december et indlæg i Quanta Magazine “Big Data’s Mathematical Mysteries.” Hun beskriver forholdet mellem anvendt matematik og det, der tidligere hed “ren” matematik og nu ofte kaldes nysgerrighedsdrevet matematik. Jeg ved ikke, om jeg med dette får sagt andet og mere end Daubechies, men i matematik (og videnskab i det hele taget) har vi tradition for at “stå på kæmpernes skuldre“, så det kan jeg jo gøre.

Først lidt om Ingrid Daubechies: Hun er mest kendt som kvinden bag Wavelets – især for at have bragt wavelets fra teori til praktisk anvendelse. Wavelets bruges i signalbehandling og i komprimering af billeder og er bl.a. implementeret i JPEG2000 og til effektiv lagring af (og søgning efter) fingeraftryk i FBIs fingeraftryksdatabase. Her forklarer Arne Jensen, hvad Wavelets går ud på. Det stammer fra Numb3rsbloggen.

I Daubechies artikel citerer hun som indledning Eugenio Calabi for, at matematikere, der har en anvendelse som drivkraft (fremover kaldet anvendte matematikere) og matematikere, der er drevet af nysgerrighed (fremover kaldet rene matematikere), reagerer forskelligt, når de møder en forhindring: De rene matematikere vil indskrænke det problem, de kigger på, hvorimod de anvendte vil kigge sig om efter noget andet matematik at angribe problemet med. Noget andet værktøj.

At bringe resultater fra matematikkens indre og ud til praktisk anvendelse er ikke let. Nye områder såsom big data, kontrolteori, kvantecomputere,… har ofte behov for al den matematik, man kan kaste efter det. I den forstand, at når en fra sådan et område lærer sig noget ny matematik, så kan det meget ofte give bedre algoritmer eller ny forståelse. Når der er brug for noget nyt i en anvendelse kan man ofte finde svaret ved at tale med en fra det rette område af matematikken. Der kommer hvert år 100.000 nye matematiske artikler og matematikken er delt op i mere end 6000 underpunkter i MSC, Klassifikation af matematiske emner for eksempel er punktet Number theory delt op i 250-300 underpunkter (jeg har muligvis talt lidt forkert…). det er altså ikke let at finde den, man skal have fat i. Sommetider bliver den samme matematik så “genopdaget” i en anden sammenhæng, og der kan gå en rum tid, laves nye definitioner og beviser og skrives artikler, inden nogen opdager sammenfaldet.

Omvendt udvikles der også ny “ren” matematik med udgangspunkt i et behov fra en anvendelse. Det er ikke altid, matematikerne har den matematik klar, som skal bruges. Langt det meste af den rene matematik har sin oprindelse i anvendelserne, men det kan godt være, man har bevæget sig langt væk fra den oprindelige anvendelse. Det sker for eksempel ved, at man generaliserer/abstraherer. Fordelen er, at det på den måde bliver udkrystalliseret, hvad den underliggende struktur for problemet er. Og vupti er det klar til anvendelser i helt andre områder – hvis man da kan finde den matematik, når man skal bruge den.

Tilbage til Daubechies’ artikel. Hun skriver om “Deep Learning” – det, der i 80’erne hed neurale netværk er nu organiseret i lag, hvor output fra et lag er input til det næste – så har man deep learning – det lyder også smart. Der er andre eksempler og det falder ind under “machine learning”. Et deep learning system lærer fra eksempler og skal så kunne behandle nye tilfælde fornuftigt.  Ifølge Daubechies, fungerer dette meget bedre, end matematikerne ville forvente:

I et billede, som kun er støj, har et deep learning netværk fundet på noget selv.

Man kan tænke på, at det drejer sig om at tilnærme en funktion (et billede kan eksempelvis også betragtes som en funktion) med bedre og bedre nøjagtighed for hvert “lag” i deep learning netværket. Man ved, at det vil give en rigtig god tilnærmelse, hvis man har nok lag. (Når antallet går mod uendelig) Men det ser ud til fra de praktiske erfaringer, at man kan nøjes med meget færre lag end forventet. Man bruger et sted mellem 2 og 15-20 lag. Det er “deep”. Jeg ved, som I nok har kunnet se, ikke meget om deep learning, men det kan I nok Google jer til. Googles Brain projekt har deep learning og har her i efteråret frigivet softwaren Tensor Flow som Open Source. Så der er nok at lege med…

Igen fra støj til indhold. Her er netværket blevet bedt om at kigge efter bygninger i et billede, som kun er støj. Eller er det…

I juni så vi flippede billeder lavet af deep learning netværk, som blev bedt om at “forbedre” kornede billeder. Jo, de drømmer om elektriske får.

Vi har samme fænomen andre stedet i matematik, hvor et værktøj virker bedre, end forventet – man når tæt på en grænseværdi i meget færre skridt, end man kunne forvente.  Og så bliver det spændende, for så er der brug for helt ny matematisk indsigt. Som så giver nyt værktøj etc.

Mit lidt forsinkede  nytårsønske er, at der fortsat vil være plads til både nysgerrighedsdrevet og anvendelsesdrevet forskning i matematik.

Det fine mønster på billedet er lavet af en projektgruppe på første semester for en del år siden. Deres vejleder, Steffen Lauritzen, har skrevet om projektet og dette mønster i gulvet i den gamle Hafniabygning, nu Codan. Der laves mange sjove projekter på første semester, men det er nu meget sjældent, der ligefrem findes ud af noget, ingen vidste i forvejen. I dette projekt fik grupperne at vide, at gulvet i Hafniabygningen er lavet, som jeg beskriver nedenfor, og en af grupperne fandt ud af, at grundtallet til at lave det var 71 (og det vidste vejlederen ikke, og det var der heller ikke andre, der gjorde). Lad mig tilføje, at projekter ofte har mere “anvendelsesagtige” anvendelser en dette – om spredning af sygdomme, om aktiekurser, om at bygge højttalere,…  I anledning af julen skal I have noget pænt at kigge på. Så jeg vil fortælle, hvad det fine mønster har med matematik at gøre. (Jeg har lige hørt, at der er nogen, der strikker sokker med den slags mønstre – det får i mere om, hvis jeg finder ud af noget)

De hele tal kan skrives som et produkt af primtal. Og et helt tal har kun en opsplitning i primfaktorer, (bortset fra, at man kan bytte om på rækkefølgen i produktet, men det gælder ikke).

I skolen har vi lært at gange tal sammen. Først positive hele tal og efterhånden også reelle tal, men der er mange andre “gangeoperationer” i matematik. Det helt generelle version hører til i området algebra. Her  vil jeg se på at gange punkter i planen sammen.

Opskriften er: (x,y)*(z,w)=(xz-yw, xw+yz)

Det er lettere at huske, hvis man betragter punkter i planen som komplekse tal. I stedet for (x,y) skriver vi x+iy hvor i er et nyt tal, som er en kvadratrod af -1. M.a.o. .

Bruger man nu de sædvanlige regler for at gange ind i paranteser, så er(x+iy)*(z+iw)= xz-yw + i(xw+yz) Man skal bare huske, at , så kommer resten af sig selv, hvis man kan regne med paranteser…

Gaussiske primtal Fig. 2

I de komplekse tal har vi de Gaussiske heltal – tal på formen n+im, hvor n og m er hele tal, og vi kan spørge, om et Gaussisk heltal er et produkt af andre Gaussiske heltal. For at undgå platte eksempler, kræver man, at disse tal ikke er i, -i, 1 og -1 (da disse går op i hvad som helst – vi synes ikke er en faktorisering). Et Gaussisk heltal, som ikke kan skrives som et produkt af andre, er et Gaussisk primtal.

De hele tal er en del af de Gaussiske heltal – de er blot tal på formen n+i0. Men det, der tidligere var primtal, er ikke nødvendigvis Gaussiske primtal. For eksempel er 5 ikke et Gaussisk primtal, da . Men 7 er. Figur 2 viser de Gaussiske primtal som punkter i planen.

Fig. 3 Gaussiske primtal

Zoomer man ind (se figur 3) kan man se, det er et rigtig fint mønster.

Det mønster, jeg har sat ind i starten, bruger lidt mere matematik.

Vi skal bruge regning “modulo et tal” og kvadratiske rester. I mønstrene er valgt et Gaussisk heltal c. Et Gaussisk heltal d er en kvadratisk rest modulo c, hvis der findes Gaussiske heltal x og z så altså c går op i i vores nye talsystem.  Det skriver man . Hvis nu d faktisk har en heltallig kvadratrod er det særlig nemt – man lader bare z=0.

Mønstrene laves ved at inddele planen i 1×1 felter og nummerere dem efter det Gaussiske heltal eksempelvis er  5+2i  feltet med midtpunkt (5,2). I mønstrene farver man feltet svarende til d, hvis d er en kvadratisk rest modulo c.  For c=7 er spørgsmålet altså, om man kan finde et x, så 7 “går op i” (altså om er et Gaussisk helt tal gange 7). Hvis 7 går op i d, kan man vælge x=0, så det er et særligt simpelt tilfælde (det er de grå felter). De andre er på formen  hvor $z$ er et Gaussisk heltal.

Her er eksempler på mønster med forskelligt valg af tallet c. Man kan se, at de bliver meget forskellige og at der kan opstå spiraler, når c=n+mi og hverken n eller m er 0. Der er meget rigtig fin matematik i at se på disse kvadratiske rester, men det må I selv pusle med – ligesom de studerende på først semester gjorde det.

Titlen på bloggens julekalender skulle have været Epsilons Hemmelighed – det foreslog Søren Højsgaard i hvert fald.

Sådan en fik vi ikke lige lavet, men der er heldigvis andre, der har lavet julekalendere med matematik, så her er nogle forslag til, hvor I kan jule med matematik:

The Aperiodical, som jeg tidligere har linket til, har en julekalender med både nørdede beskrivelser af datoerne ( 3 er det heltal, der ligger tættest på både Pi og e) og noget pudsigt, spændende, flot eller … matematik hver dag. Eksempelvis et link til House of Graphs 8/12.

Plus Magazine har en julekalender med pusleopgaver, klippe-klistre og andre aktiviteter. Broerne i Kønigsberg, Galleriproblemet,…

Fra Mathematik.de har jeg fundet julekalenderen ix-kvadrat med en ny video hver dag.

Det britiske nrich har en kalender med mere elementære opgaver og aktiviteter.

Der er uden tvivl andre, men jeg er til konference i Mexico og matematikken venter.

I indlægget Mod det Uendelige Univers bruger jeg, at logaritmefunktionen går mod uendelig, altså:

For ethvert, uanset hvor stort, tal K, findes et M så når blot . Det er nemlig det, vi mener med, at funktionen går mod uendelig for x gående mod uendelig.

Jeg kunne have skrevet dette til i den blogpost, men det er lidt noget rod, hvis nogen allerede har læst det. Så derfor får I lige en lille ekstra blogpost her.

Hvor ved vi fra, at vi altid kan finde sådan et M. Uanset hvilket K, nogen kommer med? Jo, vi har en opskrift til at lave det M (udfra et K, vi har fået). Bemærk, at logaritmefunktionen er voksende, så hvis og , så er

Opskriften på at finde M er lavet ved følgende argument:

ville gælde, hvis , så vi kan altså vælge .

Et andet argument (som min kollega Horia lige har sendt til mig – der var en fejl i ovenstående) er:

1. Logaritmefunktionen er voksende.

2). Eulers tal er mindre end 3

3).

4). Lad . For alle har vi .

Det illustrerer også, hvor langsomt logaritmefunktionen vokser – hvis altså man har gjort sig klart, hvor hurtigt eksponentialfunktioner vokser… Og man kan måske også bedre se, hvorfor algoritmer med logaritmisk tidskompleksitet eller bare er gode.

Som matematiker er jeg, ligesom Buzz Lightyear, vant til at tale om og at omgås uendelig – 1/x går mod 0, når x går mod uendelig – og lignende udsagn giver mening for mig. Det gør det, fordi jeg ved, der er præcise definitioner bag. Denne blogpost skal handle om at lægge tal sammen, rigtig mange tal. I en vis forstand at lægge uendelig mange sammen.

Summen kommer tættere og tættere på jo flere led, der tages med. Mere præcist, så er det sådan, at uanset hvor lille et tal , min værste fjende vælger, så vil jeg kunne finde et (måske meget stort) tal N, så  ligger mellem   og og det gør også, når .

Og det er det, vi mener med, at en sum “går mod” og faktisk at den uendelige sum “er lig med”  et tal, så vi skriver

At det rent faktisk er  , er et klassisk problem, Baselproblemet, som Leonhard Euler (se billedet) gav det første bevis for. Man kan bruge resultatet til at approksimere  – ved at lægge flere og flere tal sammen i denne sum – det går nu ret langsomt i forhold til andre metoder, som også bygger på, at noget “går mod” noget med $latex\pi$.

Andre eksempler er

, den naturlige logaritme til 2. Bemærk, at nogle led bliver lagt til, andre trukket fra, så efterhånden som flere led lægges til, skyder man skiftevis over og under , men mindre og mindre over og under.

En uendelig sum kaldes en række (series på engelsk, hvis I vil Google) og summen op til et vist kaldes en afsnitssum. En række er altså ikke selv en sum, men en opskrift på afsnitssummer.

, grundtallet for den naturlige logaritme.

Der er mange forskellige metoder til at afgøre, om sådan en sum konvergerer og i så fald mod hvad. En uendelig sum er konvergent, hvis der findes et tal, den “går mod”, når flere og flere led lægges til, sådan som ovenfor. er den ikke konvergent, så er den divergent. Sommetider er det meget let at afgøre, at summen divergerer. For at rækken skal konvergere, må de led, man lægger til, blive mindre og mindre. Gør de ikke det, er den i hvert fald ikke konvergent. Et klassisk eksempel på en divergent række, er den harmoniske række:

Der er flere forskellige argumenter for, at den divergerer: Et går via sammenligning med et integrale:

Figuren viser grafen for funktionen 1/x. Den illustrerer, at arealet under denne kurve, fra 1 til uendelig, er mindre end summen af den harmoniske række. Og dette integrale får man ved at lade M gå mod uendelig i  . Det går mod uendelig. Så den harmoniske række er divergent. Men det går langsomt mod uendelig. Meget, meget langsomt.

I går lærte jeg, ved at læse min gode kollega Kevin Knudsons indlæg i Forbes, følgende svimlende faktum:

Hvis vi var begyndt ved Big Bang med at lægge tallene i den harmoniske række sammen og havde lagt et til hvert sekund, så var vi nu nået til et sted mellem 40,6 og 41,6. Udregningen går på, at Big Bang var for 13,8 milliarder år siden , år. Et år har 31 556 926 sekunder, ca. (nogen siger for at huske det). Det er altså sekunder. Tag den naturlige logaritme ( og se, at Kevin har ret – Intervallet, Kevin har med, er en kombination af, at tidspunktet for Big Bang ikke er helt klart, og at den harmoniske række er større end det integrale, vi her regner på.

En formodning er et matematisk udsagn, som en eller anden, typisk en indflydelsesrig matematiker,  mener, må være rigtigt. Uden at have et bevis. Det kendteste eksempel er nok Fermats formodning om, at ligninger ikke har løsninger hvor både x, y og z er hele tal og . (Den er bevist, men det tog 300 år). Andre store formodninger er Riemannhypotesen (ikke bevist) og Poincare-formodningen (er bevist). De spiller rollen som pejlemærker for matematikere og som sten i skoen – det er rigtig irriterende ikke at kunne bevise noget, man er ret sikker på, er rigtigt. Og så giver de ofte anledning til løsning af andre resultater i forbifarten – for at få skovlen under et svært resultat, må man ofte opdage(opfinde) nye matematiske metoder, som kan vise sig at være vigtige for noget, man slet ikke havde regnet med. Wikipedia har en lang liste  med formodninger. Bemærk, at der også er en liste over formodninger, som nu er bevist og en liste over formodninger, som nu er modbevist. Så selvom man tror, noget er rigtigt, og selvom store matematikere har troet det, så kan det godt være forkert. 

abc-formodningen drejer sig om de hele tal. Den er fra 1985. Den har konsekvenser for løsning af heltalsligninger (findes der hele tal, der løser …) og vores forståelse af de hele tal og er derfor væsentlig. Matematikeren Shinichi Mochizuki påstår at have bevist formodningen, men hans bevis er enormt svært at læse. I december 2015 holdes en workshop i Oxford, hvor man bl.a. vil forsøge at forstå den nye matematik, det indgår i beviset, “inter-universal Teichmuller theory” – det er et nyt matematisk værktøj, så det giver formentlig helt nye muligheder. Nature har en artikel om abc-formodningen og især om menneskene bag. Jeg er en stor Monty Python fan og er derfor  ret vild med denne formulering:  “Everybody who I’m aware of who’s come close to this stuff is quite reasonable, but afterwards they become incapable of communicating it,” says one mathematician who did not want his name to be mentioned. The situation, he says, reminds him of the Monty Pythonskit about a writer who jots down the world’s funniest joke. Anyone who reads it dies from laughing and can never relate it to anyone else.

Billedet til venstre forestiller efter sigende universal Teichmüller theory. Jeg vil forklare, hvad formodningen siger, men ikke beviset – vi skulle jo nødig dø af grin.

Her er abc-formodningen: For ethvert ϵ>0 er der kun endeligt mange tripler a+b=c, hvor a,b,c er parvis primiske hele positive tal og 

Hvad betyder det så? Husk, at alle hele tal kan skrives som et produkt af primtal. For eksempel er . Primtallene kan “genbruges”. abc-formodningen drejer sig om de forskellige primtal, der bruges, og ikke hvor mange gange, de genbruges. Man tager så produktet af disse. Det kaldes radikalet. Eksempelvis er

• rad(100)=
• rad(25)=5, (da 25 =5×5)
• rad (64)=2, (da 64=2^4)
• rad(10)=10=rad(100)=rad(200), da primfaktorerne i alle tilfældene er 2 og 5

abc-formodningen sammenligner rad(abc)  med c. Lad os se nogle eksempler:

• 3+17=20=4×5.  rad(abc)=3x17x2x5=510 >20, så rad(abc)>c
• 100+33=133, rad(abc)=2x5x3x11x 7x 19= 17689 som er større end 133.
• 3+125=128 og 125=5^3, 128= 2^7, så rad(3x125x128)=3x2x5=30, så rad(abc)<c
• a = 2,b = 3¹⁰·109 = 6.436.341,c = 23⁵ = 6.436.343, rad(abc) = 15042 <c.

abc-formodningen siger, at rad(abc) typisk er større end c. Det ville man nok også regne med – de to sidste eksempler ovenfor et konstrueret så b og c er et primtal i en høj potens, så altså a+ p^m=q^n og det er ikke typisk. Men hvad mener man med det. Faktisk er der uendelig mange tripler med rad(abc)<c, men altså kun endeligt mange med  for et fast   uanset hvor lille dette er, men det må selvfølgelig ikke være 0. Så for eksempel er der endelig mange med  .

Skriver man lidt om – tager logaritmen på begge sider, så står der, at der kun er endelig mange tripler med

Højresiden er “kvaliteten” q(a,b,c). der er altså uendelig mange tripler med q(a,b,c)>1, men kun endelig mange med q(a,b,c)>1,00001 eller 1,000000001.

Hvis formodningen er bevist, så kan den bruges til at bevise en lang stribe resultater om de hele tal. For eksempel er Fermats sætning en konsekvens. Den har Andrew Wiles allerede bevist, men at få et nyt bevis for noget svært, er altid oplysende. Så er der en forbindelse, man ikke havde kendt til. Det ved vi sikkert mere om, når konferencen i Oxford er forbi.

Studiepraktik er forbi for i år. Vi håber, I fik noget med hjem.  Nedenfor fortæller Søren Højsgaard om, hvad der foregik på instituttet til studiepraktik, så hvis du ikke kom med, kan du alligevel få lidt at vide. Næste studiepraktik er i efteråret 2016, men der er andre muligheder for at besøge os, se eksempelvis links her.

Søren Højsgaard, Institutleder, skriver:

For et par uger siden lagde et halvt hundrede elever fra de gymnasiale uddannelsers sidste år vejen forbi vores institut til tre dages studiepraktik. Det er altid en fornøjelse at møde disse mange unge mennesker, der med livet foran sig er fulde af gå-på-mod og
nysgerrighed.

AAU har tre matematiske uddannelser,
1) Matematik (der også omfatter statistik)
2) Matematik-økonomi
3) Matematik-teknologi
og gæsterne blev introduceret til dele af den matematik der indgår i disse uddannelser:
* Morten Nielsen fortalte om lineære filtre;
* Esben Høg fortalte om anvendelse af matematik og statistik i økonomiske problemstillinger,
* Olav Geil talte algebra og dens anvendelse i kryptografi og kodningsteori,
* Lisbeth Fajstrup fortalte om, hvordan matematik i høj grad drejer sig om at stille de rigtige spørgsmål – herunder at give gode definitioner.
* Søren Højsgaard talte om differensligninger og regressionsmodeller.
Alt i alt en vifte af emner, som man kan komme i
berøring med på de matematiske uddannelser. I studiepraktikken mødte
gæsterne også ældre studerende, der fortalte om livet som
matematikstuderende.

En matematisk uddannelse er helt sikkert en vej til gode og spændende jobs gennem et helt abejdsliv. Jeg har aldrig hørt om kandidater, der har været arbejdsløse. Tværtimod, så har vore kandidater typisk deres første job inden den afsluttende eksamen. Kandidaterne finder jobs mange forskellige steder, men de store aftagere i disse år er: Den finansielle sektor, energisektoren (herunder bl.a. vindmølleindustrien), medicinalindustrien, fødevaresektoren, forskningsverdenen og gymnasieskolerne.

Er der da slet ingen slanger i paradis? Joh – det er der altid!

Den første slange paradiset er, at man skal være god til matematik for at kunne tage en matematisk uddannelse. Det kan forekomme lidt underligt, at jeg skriver det her, men vi ser hvert år nogle studerende, der kommer med 4-taller (sågar enkelte 2-taller) som matematikkarakterer fra de gymnasiale uddannelser, og det går næsten aldrig godt for disse unge mennesker. Et godt pejlemærke er, at de matematikkarakterer man har igennem gymnasiet i overvejende grad er 10- og 12-taller.
Den anden slange i paradiset er arbejdsbyrden. Det kræver en meget solid buksebag at tage en matematisk uddannelse; det kræver mange timers arbejde på universitetet om dagen og mange timer derhjemme om aftenen og i weekenden. Især 2. og 3. studieår plejer at være hårdt. Kommer man igennem 3. studieår, så kommer man som regel også igennem 4. og 5. studieår og kommer ud som kandidat.

Lisbeth: Undervejs er der til gengæld de mest fantastiske aha-oplevelser. Noget, der var meget, meget svært, forstår man lige pludselig, og så er det soleklart – som når man tænder lyset i et mørkt lokale. Det kræver, at man arbejder med det, man ikke forstår – laver opgaver, læser eksempler, taler med de andre i gruppen etc., og altså slider på den solide buksebag, Søren skriver om.  Og så en dag, når man cykler hjem, så er ahaoplevelsen der. Og den er altså noget federe, hvis det er noget, man virkelig ikke fattede, da man så det første gang.

Rygterne går blandt matematikere og dataloger. Det ser ud til, at Laszlo Babai på tirsdag vil holde et foredrag om et stort resultat: Her er annonceringen Title: Laszlo Babai (University of Chicago): Graph Isomorphism in Quasipolynomial Time (Combinatorics and TCS seminar)
When: Tue Nov 10, 2015 3pm to 4pm  CST
Where: Ry 251
Description: We outline an algorithm that solves the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (SI) and Coset Intersection (CI) in quasipolynomial (exp(polylog n)) time. 

Babai holder tre foredrag (i aftes, da jeg begyndte at skrive dette indlæg, var der kun annonceret et foredrag, men de har nok insisteret på at få en længere historie).

Hvad går det ud på? Vi skal have to ting på plads, nemlig grafisomorfier og quasipolynomiel tid.

Graf-isomorfi-problemet:

Her er en graf. Den består af nogle knuder (de runde bobler) og nogle kanter (linjestykkerne imellem).

To grafer er ens, isomorfe, hvis man kan matche knuderne i den ene med knuderne i den anden og samtidig få kanterne til at passe sammen. OBS: Det er ikke det samme som dette problem,.

Her er to grafer, som faktisk er isomorfe. Det kan man måske ikke lige se, men på grafen nedenunder er skrevet en matching af knuderne ind (ved hver knude står navnet på en knude fra hver af de to grafer) og kanterne passer.

Når man har et forslag til en isomorfi kan man checke, om det faktisk er en isomorfi, og det er let nok. Men at finde en, eller bare vide, om der findes en, er straks værre.

Grafisomorfiproblemet går ud på at lave en algoritme, som kan undersøge, om der findes sådan en matching af to grafer. Men udover det, og det er det interessante: At bestemme, hvor god en algoritme, det er muligt at lave. Altså, hvor mange skridt en algoritme, der løser dette problem, mindst skal bruge som funktion af størrelsen af input.

Tidsompleksiteten for en grafisomorfialgoritme er et udtryk for, hvordan antallet af skridt, som algoritmen i værste fald skal bruge, afhænger af grafens størrelse. Man kan let lave sin egen algoritme, som starter fra en ende af – vælg en knude i graf 1 og match den til en knude i graf 2. Vælg så en ny knude i graf 1 og match til en, som ikke er matchet endnu i graf 2. Og så fremdeles. Hvis graferne begge to har n knuder, er der n knuder i graf 2 at vælge imellem, når den første skal matches, n-1, når den næste skal matches etc. Så der er nx(n-1)x(n-2)x….2×1 =n! mulige match af knuderne i den en med knuder i den anden. Så skal man for hvert match af knuder checke, om kanterne passer. Er der en, der passer, er svaret “ja, der findes en isomorfi.” Ellers er svaret “Nej”. Det er ikke effektivt. Når man går fra at have 100 knuder til 1000 knuder, er antallet af mulige match for 100 knuder 100!, som er cirka 10^157 (157 nuller efter 1-tallet). Har man 1000, er der 1000! cirka 10^2567, altså 2567 nuller efter 1-tallet. Dette er en algoritme med en helt urimelig  tidskompleksitet. Blot ved at få en graf, der har 10 gange så mange knuder, skal algoritmen bruge 10^2410 gange så lang tid. Men det er også en meget ubegavet algoritme.

Har man små datamængder, kan man nøjes med sådanne dumme algoritmer, der prøver alle muligheder  (de kaldes også brute force algoritmer) og leve højt på, at computere er hurtige. Men vi har store, meget store, datamængder. så vi skal være dygtigere.

Kompleksiteten af en algoritme er det antal operationer, der skal til, som funktion af størrelsen af input. En graf består af en mængde knuder og kanter, så her er størrelsen af input den samlede størrelse af disse to mængder. Mere præcist er det “størrelsesordenen” af antallet af operationer. Hvis antal operationer er er kompleksiteten O() og man er ikke interesseret i konstanten 32 eller leddene med lavere grad.

Man inddeler beslutningsproblemer, altså ja/nej problemer, som eksempelvis, om der findes en matching af to grafer, efter kompleksitetsklasser – polynomiel, logaritmisk, eksponentiel etc.. Altså efter, hvad tidskompleksiteten er af den bedste algoritme. At finde en optimal algoritme er selvsagt mindst lige så vanskeligt som at afgøre, hvad kompleksiteten af en sådan algoritme ville være, hvis man kunne finde den.

Graferne på billedet illustrerer, hvordan klasser af funktioner vokser i forhold til hinanden. Læg mærke til, at n! er den, der vokser hurtigst. Den orange er , altså eksponentiel ( Grafisomorfiproblemet beskriver sin egen kompleksitetsklasse GI, som er alle problemer, man ved har samme kompleksitet som grafisomorfiproblemet – fordi man kan formulere det at løse det ene beslutningsproblem som et spørgsmål indenfor løsning af det andet problem og omvendt. Grafisomorfialgoritmerne har man hidtil haft i en klasse for sig, hvor man ikke har vidst, hvor de hører til. Det åbne spørgsmål er, om der findes en algoritme med polynomiel tidskompleksitet, der altid korrekt kan fortælle, om to grafer er isomorfe.  Altså en algoritme, hvis tidskompleksitet er et polynomium. Og det må gerne være et 2000-grads polynomium. Men man har ikke været i nærheden af at have en sådan algoritme. Man vidste, man kunne lave en, der er højst , hvor n er antal knuder. Den kompleksitet kaldes subeksponentiel – ikke polynomiel, men heller ikke så voldsom, at den er eksponentiel. Den algoritme er fra 1983, så det er derfor, der er røre i andedammen, når der kommer nyt.

Laszlo Babai har, hvis altså beviset holder, lavet en algoritme med tidskompleksitet hvor c er en konstant. Det er “quasipolynomielt” og klart mindre end det tidligere opnåede. Konstruktionen af algoritmen har involveret resultater fra det matematiske område gruppeteori.

På Numb3rsbloggen har Hans Hüttel skrevet om P versus NP. Kompleksitet af algoritmer har både teoretiske og praktiske sider. Eksempelvis har jeg lige hørt i kaffestuen, at digitalt tv ikke ville fungere, hvis vi brugte den dumme signalbehandlingsalgoritme, som er . Heldigvis bruger vi Fast Fourier Transform, som er , og så er der Vild med Dans på skærmen.

Nu er det spændende, om Babai er på vej mod en polynomiel algoritme. Grafisomorfi har også praktiske anvendelser – og der er såmænd gode algoritmer til at bestemme om visse typer af grafer er isomorfe. Helt generelt gælder det, at man med mere viden om det data, der skal behandles, kan lave hurtigere algoritmer.

Jeg har bedt min gode kollega Hans Hüttel om hjælp til at undgå alt for meget vrøvl i ovenstående – jeg er nemlig overhovedet slet ikke ekspert i kompleksitet, og han har reddet mange af mine misforståelser – der er muligvis nogen tilbage. Det er ikke Hans’ skyld. Hans skriver yderligere:  Noget andet, der er rigtig interessant, er om grafisomorfi-problemet mon også er i coNP, dvs. om problemet om to grafer _ikke_ er isomorfe mon er i NP. Ingen ved nemlig om NP er lukket under komplement (selv om der hvert år er studerende på 5. semester på datalogi, der mener at vide at det er tilfældet). Hvis vi finder en polynomiel afgører for grafisomorfi har vi samtidig fået aflivet en kandidat til at vise at NP ikke er lukket under komplement.