www.matematikk.org
Trinn 8-10Elever Trinn 8-10Lærer Trinn 8-10Foresatt

Abelprisvinneren 2012 er Endre Szemeredi!

Abelprisen 2012 går til Endre Szemerédi, Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, for «for hans fundamentale bidrag til diskret matematikk og teoretisk informatikk, og som anerkjennelse for disse bidragenes gjennomgripende og varige innflytelse på additiv tallteori og ergodeteori».

For Abelkomiteens begrunnelse og Abelprisvinnerens biografi, se i høyre spalte under Eksterne lenker. Vi har hentet et utdrag fra Arne B. Sletsjøes "En kort introduksjon til Endre Szemerédis teorem fra 1975" der han på en enkel måte forklarer bakgrunnen og bidraget til Szemerédi.

Gangetabellen er en viktig del av pensum på barneskolen. Barna skal kunne utenatt 2-gangen, 2,4,6,..., 3-gangen, 3, 6, 9, 12, 15, ..., osv. Det matematiske begrepet for slike regler er aritmetiske progresjoner. Begrepet aritmetisk progresjon omfatter imidlertid også endelige sekvenser som 10, 13, 16, 19. Dette er en aritmetisk progresjon av lengde 4, med (konstant) differanse 3 og startverdi 10. 2-gangen er en aritmetisk progresjon av uendelig lengde, med differanse 2 og startverdi 2. Når vi angir lengde, differanse og startverdi er den aritmetiske progresjonen entydig bestemt. Hvis vi blir bedt om å skrive opp en aritmetisk progresjon av lengde 5, differanse 7 og startverdi 23, er riktig svar 23, 30, 37, 44, 51. Merk at 4, 5, 6, 7, 8, 9 også er en aritmetisk progresjon, differansen er 1 i dette eksemplet.

I 1927 publiserte van der Waerden et berømt resultat om eksistens av aritmetiske progresjoner i vilkårlige oppdelinger av de naturlige tallene i endelig mange deler. Van der Waerden viste at dersom vi fargelegger de naturlige tallene med et endelig antall farger, så vil det for enhver k finnes ensfargede aritmetiske progresjoner av lengde k.

Dersom vi kun fargelegger med to farger, f.eks. rød og blå, er det lett å se at vi trenger tallene fra 1 og 9 for å være sikker på at vi finner en aritmetisk progresjon av lengde 3. Hvorfor?

La oss prøve på det motsatte, å skrive opp en sekvens av lengde 9 uten aritmetiske progresjoner av lengde 3. Tallene 1, 5 og 9 kan da ikke ha samme farge. Så anta først at 1 og 5 er røde og at 9 er blå. Da vil rødfarten til 1 og 5 tvinge 3 til å være blå. Men 9 er også blå, så 6 må være rød. Men da er 5 og 6 røde, og 4 og 7 må nødvendigvis være blå. Tallet 8 må være rødt siden 7 og 9 er blå, og tallet 2 må også være rødt siden 3 og 4 er blå. Men da er 2, 5 og 8 alle røde, som motsier antakelsen om at vi ikke har aritmetiske progresjoner av lengde 3. Tilfellet hvor 1 og 9 er røde og 5 er blå kan man behandle på samme måte.

På den annen side har sekvensen RBRBBRBR, av lengde 8, ingen aritmetiske progresjoner av lengde 3. Det betyr at 9 er den nøyaktige grensen for denne egenskapen. Denne grensen kalles van der Waerden tallet W(2,3).

 

I 1936 lanserte Erdös og Turán en skjerpet versjon av dette resultatet. De mente at den bakenforliggende årsaken til eksistens av aritmetiske progresjoner er at minst en av de ensfargede delmengdene må ha positiv tetthet. For en delmengde A av de naturlige tallene definerer vi begrepet øvre tetthet på følgende måte:

For ethvert naturlig tall N snitter vi mengden A med mengden {1,2,...,N}, teller antall hele tall i mengden og deler dette antallet med N.  Dette rasjonale tallet mellom 0 og 1 måler størrelsen til A sammenliknet med antall tall mellom 1 og N. Dette gjør vi for økende tall N. Dersom forholdet for store tall N ikke overskrider et gitt tall, sier vi at dette tallet er en øvre grense for disse forholdene. Den minste øvre grensen for store N kalles den øvre tettheten for A.

Vi kan også definere en nedre tetthet, gitt ved den største nedre grensen for foholdene, når N er et stort tall.

Vi skal gi to eksempler som illustrerer dette begrepet.

Eksempel 1. La være alle partallene. For en gitt N vil antallet partall mellom 1 og N være N/2 hvis N selv er et partall, og (N-1)/2 hvis N er et oddetall. Forholdet vi leter etter er derfor 1/2, som er den øvre tettheten for partallene.

Eksempel 2. La nå A være en endelig mengde for eksempel alle heltallene fra 1 til 100. For N mindre enn 100 vil forholdet være 1, men for N større enn 100 vil forholdet avta og etter hvert gå mot null. Så den øvre tettheten er 0 i dette tilfellet.


I 1953 viste Roth at enhver delmengde av de naturlige tallene med positiv (og ikke 0) øvre tetthet inneholder en aritmetisk progresjon av lengde 3. I 1969 viste Endre Szemerédi at delmengde må inneholde en aritmetisk progresjon av lengde 4, og så, i 1975, viste han at delmengden må inneholde en aritmetisk progresjon av vilkårlig lengde.

Szemerédis Teorem:

La A være en delmengde av de hele tallene av positiv tetthet, da inneholder A vilkårlig lange aritmetiske progresjoner.

Szemerédis bevis for dette resultatet baserer seg på et annet resultat, det såkalte Szemerédis regularitetslemma. Dette er et resultat innen grafteori. Szemerédis regularitetslemma sier at enhver stor nok graf kan deles opp i delmengder av omtrent samme størrelse på en slik måte at kantmengdene mellom ulike delmengder har omtrent samme størrelse som om de skulle være tilfeldig sammensatt. Szemerédi introduserte i 1975 en svakere versjon av dette lemmaet, hvor han begrenset seg til såkalte todelte grafer. Dette var det han trengte for å bevise Szemerédis teorem. I 1978 beviste han lemma i sin fulle generalitet.

Szemerédis bidrag til utviklingen av matematisk kunnskap omfatter blant annet Szemerédis teorem om aritmetiske progresjoner i heltallsmengder av positiv tetthet og Szemerédis regularitetslemma som igjen er en viktig del av beviset for teoremet.

Publisert: 20.03.2012 Endret: 20.08.2013

Eksterne lenker