I 2014 fandt en tysk statistiker, Thomas Royen, et bevis for en formodning fremsat i 1959. Royen skrev beviset ned og sendte det til Donald Richards, som er professor i statistik ved Pennsylvania State University. Og så bliver historien lidt mystisk:  Ifølge Quanta Magazine havde Richards forsøgt at bevise formodningen i 30-40 år; han forstod, at Royens bevis var korrekt og alligevel blev den viden ikke spredt særlig effektivt. Der ser ud til at have været et hav af forkerte beviser i omløb, så måske er det druknet i det hav.  Royen publicerede det i ArXiv, hvor vi allesammen lægger de næsten færdige versioner af artikler – nogenlunde samtidig med, vi sender dem til et tidsskrift. Royen valgte tidsskriftet The Far East Journal of Theoretical Statistics, et af de mange tidsskrifter med et tvivlsomt ry. Det burde nogen nok have frarådet. Men man kan da undre sig over, at det alligevel ikke blev spredt af eksempelvis Richards. Da to polske statistikere skrev en artikel, som er en gennemgang af beviset i  detaljer, fik flere øje på resultatet og det er præsenteret ved Bourbakiseminar i januar i år – samme dag som Helfgott talte om grafisomorfiproblemet. Nå, men hele “human interest” historien kan I finde mange steder. Lad os se, hvad det er for en formodning.

Slår man med  en terning, er sandsynligheden for en sekser . Slår man med to terninger, er sandsynligheden for, at begge giver en sekser – produktet af de to sandsynligheder. Det bliver et produkt, fordi der ikke er nogen korrelation mellem at slå en sekser med den ene terning og at gøre det med den anden. I et tidligere blogindlæg skrev jeg om uafhængighed. To hændelser A og  B er uafhængige, hvis , altså sandsynligheden for, at både A og B sker, er produktet af sandsynlighederne for hver af dem.

Den Gaussiske korrelationsulighed siger følgende: Hvis A og B er konvekse delmængder (hvis p og q er i A, så er linjestykket mellem p og q i A) af (tænk på planen eller rummet, n=2,3) og både A og B er symmetriske omkring origo (hvis x er i A, så er -x også i A), og man skyder til måls efter en skive med centrum i origo – og pilene rammer normalfordelt omkring origo, så er , altså at sandsynligheden for at ramme i både A og B er mindst lige så stor som produktet af de to.

En mere langhåret version siger: hvor er det Gaussiske mål på .

Den oprindelige version fra 1959 handler ikke umiddelbart om konvekse delmængder af planen, men om rektangler. Vi måler en række forskellige størrelser, eksempelvis højde, vægt og mellemrum mellem fortænderne. Vi ved tilfældigvis, at alle disse størrelser hver for sig er normalfordelt med middelværdi hhv. H, V og F. Vi ved nu, at 95% af alle målinger af højder falder i intervallet [H-h, H+h], 95% af alle vægtmålinger i intervallet [V-v, V+v] og mellemrum mellem fortænderne i intervallet [F-f, F+f].

Den Gaussiske korrelationsulighed siger, sandsynligheden for, at et datapunkt (x,y) (højde, vægt for en konkret person) ligger i rektanglet [H-h,H+h]x[V-v,V+v] er mindst , produktet af de to sandsynligheder. Det samme gælder (naturligvis) for (y,z), vægt og mellemrum mellem fortænderne. Sandsynligheden for, at (y,x) ligger i rektanglet [V-v,V+v]x[F-f,F+f]  er mindst . Hvis de to størrelser er uafhængige, er der lighedstegn. Eftersom en person af tæt på gennemsnitlig højde sandsynligvis også har tæt på gennemsnitlig vægt, vil vi forvente, at der ikke er lighedstegn i det første tilfælde . Mht. vægt og mellemrum mellem fortænderne, ved jeg det ikke. (Jeg havde skrevet, at noget tilsvarende gælder for kassen [H-h,H+h]x[V-v,V+v]x[F-f,F+f] – altså at et punkt ligger der med sandsynlighed , men det er der ikke nogen, der har vist – eller påstået (tror jeg da). Og sådan kan man lære at læse det, der faktisk står i artiklen – og at spørge Svante, som fandt min fejl…)

I Quanta Magazine er en fin illustration, som jeg naturligvis ikke kopierer ind her – det må man ikke… Men kig selv på den. Nedenfor er en version fra Wikipedia – tænk på højde og vægt ovenfor. Højden er den røde kurve, vægten den blå. Det samlede kan man tænke sig som en klokkeformet graf over x-y-planen, som figuren længere nede viser.  Den grønne ellipse illustrerer ellipsen, det område, hvor et punkt med 99,73% sandsynlighed vil ligge. Rektanglet må I tænke jer til.

Morten Nielsen har skrevet om årets Abelpris – og Arne Jensen har tidligere skrevet om Wavelets. Tak for det! – tilsammen giver det:

Abelprisen 2017
går til Yves F. Meyer (billede B. Eymann, Académie des Sciences)

for hans væsentlige bidrag til teorien om wa-
velets. Wavelets er funktionsystemer, der fremkommer ved dilatering
(udstrækning) og translation af én fast funktion :

:

hvor j og k gennemløber heltallene. Langt de fleste funktioner frem-
bringer “ubrugelige” systemer, men tilbage i 1909 observerede Alfred
Haar at funktionen

=

giver et såkaldt ortonormal system, der kan benyttes til at dekomponere
alle “rimelige” funktioner.
Haars funktion er ikke specielt “pæn”. Den er f.eks. ikke kontinuert
og det blev længe betragtet som en nær håbløs opgave at finde bedre
frembringere . Desuden kunne ingen på daværende tidspunkt forestille
sig praktiske anvendelser af sådanne systemer. Faktisk skulle der gå
omkring 70 år fra Haars opdagelse indtil tiden (og teknologien) var
moden til næste skridt.
Omkring 1980 kom geofysikeren Jean Morlet frem til, at systemer
med samme struktur som Haars system, ved implementation på en
computer, tilsyneladende var meget effektive til brug ved analyse af
seismografudskrifter fra olieeftersøgning. Dog havde Morlet ingen teo-
retisk forklaring på observationerne, men Morlets resultater satte gang
i intens ny forskning indenfor området.
Nogle af de vigtigste fremskridt stod Yves Meyer for. Meyer kon-
struerede sammen med P. G. Lemarié-Rieusset det første eksempel på
en glat ortonormal wavelet, og Meyers analyse af konstruktionen ba-
seret på Fourieranalyse førte til en fuldstændig beskrivelse af glatte
wavelets. (Grafen viser Lemarié-Rieusset og Meyers wavelet – funktionsudtryk kan man finde her)

Wavelets anvendes i dag til mange ting, for eksempel kompression af
musik, billeder og video. Der er bl.a. en nyere standard for billedkom-
pression (JPEG2000) som er baseret på wavelets.
Yderligere information om wavelets kan f.eks. findes i denne tekst
skrevet af Arne Jensen til Numb3rsbloggen.

Tirsdag 21/3 afsløres dette års Abelprisvinder(e). Det kan følges via livestreaming fra klokken ca. 11.30. Er man i Oslo, kan man følge det i rigtig levende live i Videnskabernes Akademis sal, på Drammensveien. Der er forfriskninger i Gobelinsalen fra 11.30. Annonceringen efterfølges af en beskrivelse af prisvinderens(eller vindernes) arbejde. Det står Terence Tao for.

Her i Aalborg ser vi det på instituttet på Fredrik Bajers Vej 7- i G5-109. Der må man selv medbringe forfriskninger.

I Oslo er der fra 17.30 mulighed for at spise Abelkage i Litteraturhuset og høre Terence Tao (Filedsmedaljevinder og matematisk superstjerne) fortælle om prisvinderen(vinderne).

Her er programmet

• Eldrid Borgan (forskningsformidler og kjent fra NRKs forskningsprogram Schrødingers Katt) og Magnus Dehli Vigeland; (matematiker og profesjonell sirkusartist) er kveldens verter.

• Terence Tao presenterer prisvinners arbeid. Han skal også  samtale med Eldrid Borgan om liv og lære innen matematikken.

• Det blir paneldiskusjon med blant andre Nadia Larsen og Øyvind Ryan fra Matematisk institutt ved Universitetet i Oslo.

• Magnus Dehli Vigeland kombinerer sine ferdigheter som sirkusartist og matematiker.

• Alle kluter settes inn på å få prisvinner i tale på direkten

• Abelkaken serveres fra kl. 17.30

 Sådan ser en Abelkage ud. Google troede, jeg mente æblekage.

Så skal vi til det igen: Er vi nørdede nok på bloggen til at fejre -dag? Selvfølgelig er vi det. Især hvis nogen serverer pie. Begrundelser for at spise kage skal man ikke kimse af. Men eftersom det er en tilbagevendende begivenhed, så henviser jeg til sidste års indlæg.

I The Guardian varmer Alex Bellos op til -dag med et par opgaver, som man kan forsøge at løse, inden han kommer med løsningerne i morgen. I opgave 2 har han placeret ni inficerede computere i et net . Se illustrationen nedenfor.  Man bliver smittet hvis og kun hvis to nabocomputere (nabo= forbundet med en kant) er smittet. Spørgsmålet er: Vil alle computere blive inficeret uanset, hvordan man placerer de ni smittede? Vil der altid være nogen, som ikke er smittet? Eller afhænger det af, hvordan man placerer de ni smittede? Tænk over det. Og hvad har det mon med at gøre? Man kan selv finde på andre spørgsmål om situationen…

I 2009 publicerede en forfatter med navnet D.H.J. Polymath en matematisk artikel “A new proof of the density Hales-Jewett theorem”. D.H.J. Polymath er ikke navnet på en matematiker, men dækker deltagerne i det første Polymath-projekt, som førte til et nyt bevis for Hales-Jewett problemet. Polymath blev startet af  Timothy Gowers i januar 2009 som et eksperiment: Kan man samarbejde online og i fuld åbenhed om at løse et matematisk problem? Det kan man tydeligvis – her fortæller Timothy Gowers og Michael Nielsen i Nature om erfaringerne fra det første projekt.

Projekterne foregår på The Polymath Blog|Massively Collaborative mathematical projects.  I kommentarsporet. Det første problem blev sat i søen af Gowers med en liste over regler for samarbejdet og naturligvis en beskrivelse af problemet og forskellige veje, man kunne forestille sig at gå. Det gik hurtigt, da først det gik igang. Der kom mere end 800 kommentarer. De blev ikke sat fortløbende under en enkelt blogpost, men i stedet samlet sammen ind imellem, på Polymath Wiki  så man kunne overskue, hvad der nu var bevist. Terence Tao (Fieldsmedaljevinder ligesom Gowers) har deltaget aktivt i en del af disse projekter – han gav kommentar nummer 3 om Hales Jewett –  og har også forsøgt sig med mere elementære opgaver, nemlig dem fra matematikolympiaden. Meningen var så, at gymnasieelever fra hele verden kunne samarbejde.

I alle tilfældene viser det sig, at det er ret begræset, hvor mange der deltager. For Hales Jewett var det 27 ifølge Natureartiklen ovenfor. Det er alligevel mange i forhold til et sædvanligt matematikprojekt.

Der er lige sat et nyt projekt i søen. Om Rotas basisformodning, som siger følgende: Hvis man har n baser B1,…,Bn for et n-dimensionalt vektorrum, er det så muligt at organisere dem i en matrixstruktur (med en vektor i hver indgang), så den i’te række indeholder basisvektorerne fra basen Bi og hver søjle også udgør en basis for V. Altså, at man kan lave n nye baser, som hver indeholder en vektor fra hver af Bi. (Og uden at genbruge dem.)

Det er en formodning (at svaret er ja, altså) i lineær algebra og mere generelt i branchen “matroids” og den er fremsat af Gian-Carlo Rota.

Billedet forestiller en 3d version af formodningen, selvom det umiddelbart forestiller punkter i planen. Tegningen illustrerer punkter med koordinater (x,y,1) i.e. basisvektorerne i formodningen går fra  fra (0,0,0) til punkterne på billedet. De tre baser har hver sin farve. De nye baser (søjlerne i formodningen) er markeret med de sorte kanter i tre trekanter- med hjørner i hver af de tre farver.

Der er foreløbig kommet 95 kommentarer, men det er ikke løst, så har man ideer, er der her en mulighed for at lave forskning i en helt ny ramme.

April er  “Mathematics and Statistics Awareness Month” i USA. Der er mange aktiviteter, online underholdning etc. Der kommer mere i april, men her er noget af det, jeg faldt over:

Illustrationer af statistiske og sandsynlighedsteoretiske begreber fra Brown University, Seeing Theory.

Significance  er et fælles tidsskrift for det britiske Royal Statistical Society og den amerikanske American Statistical Association. Skrevet i et ikke-teknisk sprog. Februarudgaven har en artikel om statistik og Oscars, om log-normalfordelingen (fordelingernes Askepot…) og meget andet.

Chance er også forholdsvis let at gå til. Eksempler på artikler:

• Zika is Here, and We Need Statistics, hvor man bl.a. kan se en avanceret version af SIR-modellen (Sund, Inficeret, Recovered (eller død)) med forskellige smitteveje og steder.
• Statistics Books to Read for Pleasure
• Searching for the Black Box. Misconceptions of Linearity

SIAM (Society of Industrial and Applied Mathematics) har masser af eksempler på anvendelser af matematik, på karrierer med matematik og meget andet. I får deres videoer om matematisk modellering – fra problemanalyse til rapportering af en løsning:

Det er gået op for mig, at rumopfyldende kurver – space filling curves i min oversættelse – har anvendelser. Til lagring af data. Her troede jeg, at det var noget, matematikerne kunne have for sig selv, men nej. Det skal da på bloggen.
Man skulle ikke tro, at det er muligt at lave en kurve, som går igennem hvert eneste punkt i et kvadrat i planen, men det er det. Og man kan såmænd også fylde hele planen eller hele rummet eller hele det 17-dimensionale rum Det gav i slutningen af 1800-tallet anledning til, at man måtte skærpe definitioner og ideer om bl.a. kontinuitet. Hvordan ser sådan en kurve mon ud? Tegner man kurven ind, får man malet hele planen, så der må en anden forklaring til og andre illustrationer.

Her er Hilbertkurven:

(Illustration, Byron Mayfield, Wikimedia Commons) Som man kan se, fremkommer kurven som en grænse – kurverne bliver tættere og tættere – rammer flere og flere punkter –  og man må vise, at der faktisk er en grænsekurve – at det giver mening, at denne grænsekurve er kontinuert og at den går igennem ethvert punkt i kvadratet. Der er mange eksempler på rumudfyldende kurver. De kaldes også Peanokurver, fordi Giuseppe Peano gav det første eksempel på en. Jeg holder mig til Hilbertkurven. Her er de første 6 kurver i den følge af kurver, som i grænsen er Hilbertkurven – drejet i forhold til illustrationen ovenfor.

(Billede fra Wikipedia) En beskrivelse af den iterative proces er som følger (leg med det her): 1) Del kvadratet op i fire og lav en kurve mellem centrene bestående af tre linjestykker som i første billede. 2) Opdel hvert af de fire kvadrater i fire, hvor kurven fra step 1 tegnes ind. Nu har vi fire mindre versioner af kurven fra step 1. Kald dem Sydvest, Nordvest,  Nordøst, Sydøst. Roter det syd-vestlige kvadrat 90 grader med uret. Roter det sydøstlige kvadrat 90 grader mod uret. Forbind nu de fra SØ til NØ og fra SV til NV. 3) gentag manøvren i mindre og mindre kvadrater. Se en mere præcis forklaring nedenfor, men lad mig lige sparke anvendelsen ind først: Har man data med to koordinater og vil søge i dem, er det (som jeg forstår det) nyttigt at omsætte til dimension 1, altså at ordne punkterne med 2 koordinater. Det kan man gøre på mange måder, men gør man det ved at følge en passende iteration på vejen til eksempelvis en Hilbertkurve (dem vil jeg også kalde Hilbertkurver nedenfor, selvom det egentlig kun er grænsekurven, der er en Hilbertkurve), så får man følgende sidegevinst:

Punkter, som ligger tæt på hinanden, når man måler langs kurven, ligger også tæt på hinanden i kvadratet. OBS: Ikke omvendt. Det skyldes den iterative konstruktion – man ændrer kurven lokalt, når man laver en iteration mere. Billedet nedenfor er en afbildning af regnbuens farver ordnet langs linjen ind i planen med en Hilbertkurve. Bemærk, at der er bratte overgange svarende til skift af kvadrater (mellem rød og gul for eksempel), men alt med sammen farve er tæt på noget med samme farve.

En anden beskrivelse af kurven i iteration nummer n, altså en kontinuert afbildning fås ved at fortælle hvilken rækkefølge, kurven går igennem centrum for kvadraterne. De første fire centre nummereres 1,2,3,4 fra nederste venstre center og med uret – SV, NV, NØ, SØ med beskrivelsen ovenfor. Brug intervallet til at give kurven i kvadrat nummer k for kurven .

Den n+1’ste nummerering laves ud fra den n’te som følger: Der er kvadrater grupperet med i hhv. SV, NV, NØ, SØ.

Start i SV. Brug ordenen fra step n – roter 90 grader med uret og brug den omvendte orden. I NV bruges ordenen fra step n, men man begynder med nummer . I NØ bruges igen ordenen fra step n, men begynd med nummer . I SØ nummereres med orden fra step n, der roteres 90 grader mod uret og nummerordenen vendes om – og man lægger  til.

Observer, at både og afbilder til samme kvadrat – med sidelængde . Altså er for alle x. Det kan man bruge til at se, at er en Cauchyfølge mht. supremumsafstanden – altså konvergerer følgen og grænsefunktionen er kontinuert. At grænsekurven går igennem alle punkter viser man ved, at der for hvert punkt og hvert er et punkt på kurven i højst afstand . Brug nu, at er kompakt, så er lukket til at konkludere, at .

Vi skal da have en XKCD ind her: Fra IP-adresser – altså noget data på en linje – til et kvadrat via en Hilbertkurve:

For kort tid siden skrev jeg, at Helfgott havde fundet en fejl i Babais beregning af tidskompleksiteten for Babais grafisomorfialgoritme. Nu er der igen en kvasipolynomiel grafisomorfialgoritme. Lazslo Babai har rettet algoritmen. Jeg har skrevet om algoritmen. Jeg kan ikke sætte links pænt ind her fra min iPad, men nedenfor er links til det tidligere blogindlæg og nærmere omtale hos Quanta Magazine. Det er ret spændende at kunne følge processen – selvom Babai nok hellere ville have undværet det. Helfgott er nu enig med Babai: Den nye algoritme er kvasipolynomiel.
Tilføjelse 19/1: At et problem er kvasipolynomielt betyder, der findes en løsningsalgoritme, hvis tidskompleksitet , som eren funktion, der giver antal skridt, algoritmen bruger, som funktion af størrelsen af input (antal knuder plus antal kanter i grafen eksempelvis) , er kvasipolynomiel.
En funktion er kvasipolynomiel, hvis den for ethvert opfylder: Der findes et , så når , hvor c er en konstant.
Problemet er subeksponentielt, hvis der findes en algoritme, som løser problemet og hvis tidskompleksitet opfylder:
Der findes for ethvert et helt tal , så når
Da den nye (tilrettede) algoritme er kvasipolynomiel, er grafisomorfiproblemet nu kvasipolynomielt.

Helfgott finder fejl i Babais artikel om grafisomorfiproblemet

https://www.quantamagazine.org/20170114-graph-isomorphism-babai-fix/

Gymnasiematematikbøgerne “Hvad er Matematik” ledsages af diverse materiale. Herunder et filmprojekt “10 danske matematikere“.

Opgaven for de 10 er at fortælle om egen forskning og at fortælle om noget matematik, der giver mening for gymnasierne. Det er en vanskelig opgave. Men foreløbig er vi fire, der har vovet pelsen, heraf to fra AAU:

Olav Geil om Fejlkorrigerende Koder. 

Lisbeth Fajstrup (yours truly) om Algebraisk topologi – Om deformationer og huller i rummet.

De to andre er Susanne Ditlevsen fra KU om Statistiske metoder i hverdagsliv og neurovidenskab:

og Steen Markvorsen fra DTU om Skumstrukturer og minimalflader.:

I 2015 troede vi, der var nyt om kompleksiteten af grafisomorfiproblemet. Det skrev jeg om på bloggen (med undertitlen “rygters bureau” – man skulle tro, jeg havde en krystalkugle).

Nyheden var dengang, at Laszlo Babai havde lavet en ny algoritme til at afgøre, om to grafer er isomorfe og at tidskompleksiteten for den nye algoritme er  , hvor c er en konstant.

Nu har Harald Helfgott, som er berømt (i visse kredse…) for at have bevist den svage Goldbachformodning, fundet en fejl i Babais artikel. Det viser sig, at kompleksiteten af algoritmen er og det er ikke quasipolynomielt, som Babai troede, men subeksponentielt (hurtigere end for ethvert ) .

Helfgott skriver på sin blog, at han fandt fejlen, da han forberedte sig til at holde Bourbakiforedrag om Babais resultat. I den forbindelse skal man skrive beviset  ud (eller op eller ned), så matematikere fra andre områder også kan læse det –  og der var altså noget, der ikke stemte. Algoritmen virker, men analysen af tidskompleksiteten er forkert. Helfgott skriver, man måske kan forbedre algoritmen. I hvert fald er det klart, hvor problemet er.

Babai skriver på sin hjemmeside  om det nye.

The technical content of the paper remains virtually unchanged. The previous analysis breaks down for one of the recursive steps of the combinatorial “Split-or-Johnson” procedure; but the “Split-or-Johnson” theorem remains valid with the updated timing analysis. All other results are unaffected. I am working on an updated arXiv posting (with a different title) that will also improve the presentation, following comments from several colleagues.

Og så er han en smule sarkastisk: I apologize to those who were drawn to my lectures on this subject solely because of the quasipolynomial claim, prematurely magnified on the internet in spite of my disclaimers. I believe those looking for an interesting combination of group theory, combinatorics, and algorithms need not feel disappointed.

“Prematurely magnified on the internet” – jow jow, bloggen her var ikke den eneste, der løb med en halv vind. Undskyld 🙂 Får man mon tilgivelse, når man har skrevet “rygters bureau”?