Fire farger-teoremet

Jeg postet for ikke lenge siden følgende tweet@MatematikkFakta:

Du vil aldri trenge mer enn 4 farger om du skal fargelegge et kart.

Kort tid etterpå var noen av mine observante følgere ute og kommenterte at påstanden ikke var helt presis. Dette er selvsagt riktig, og kudos til dem og alle andre med observant blikk.

For at påstanden skal stemme, må den gjøres presis. Det er to ting som er uklart slik påstanden står nå. 1) Hva menes med å fargelegge et kart? 2) Hva er et kart!?

I denne bloggposten skal jeg prate litt om punktene 1) og 2), og litt om hvordan påstanden til slutt ble bevist. Vi vil se at å reformulere problemer er vanlig og nyttig i matematikken.

"Moteksempel" til fire farger-teoremet. Fra Wikimedia Commons, laget av Inductiveload.

Først og fremst, i virkeligheten er påstanden feil. For at fire farger skal holde om vi skal fargelegge et kart, må landene være enkeltsammenhengende. Dette betyr at tilfeller som Russlands Kaliningrad eller andre land med enklaver ikke kan tillates. Se bildet til høyre. Det skal forestille et land A med en enklave. Resultatet er at vi er nødt til å bruke 5 farger. I tillegg må vi tillate at hjørnene til landene får lov til å møte i samme farge.

Så, siden vi har utelukket Russland med Kaliningrad (også Aserbajdsjan med Nakhitsjevan), så virker plutselig ikke teoremet særlig relevant for virkeligheten. Faktisk forteller Wikipedia-artikkelen om teoremet at selv ikke folk som lager kart bryr seg – for de velger som regel å bruke flere farger uansett.

Så vi kan likegjerne omdefinere hva problemet handler om. For å unngå problemer med rare kart, hjørner, pussige kurver, og så videre – reformulerer vi problemet ved hjelp av grafteori. Kort sagt: fra et kart lager vi en graf (en graf er en samling noder, med kanter mellom dem), som i bildet under:

Fra kart til graf. Fra Wikimedia Commons, laget av Inductiveload.

Det vi gjør er følgende: la hvert land være representert med en node (=prikk). Om to land grenser til hverandre, tegner vi en strek mellom dem. Fire farger-teoremet kan nå reformuleres til følgende:

Nodene til enhver graf i planet kan fargelegges med 4 farger slik at ingen nabo-noder har samme farge.

Eller mer teknisk: “enhver planar graf kan fire-farges”. Fordelen med denne omformuleringen er at vi nå kan bruke masse verktøy fra algebraisk topologi og grafteori for å arbeide med problemet (i tillegg til at problemstillingen er mye mer presis).

Teoremet har en lang historie. Det ble først formodet i 1852, hvoretter flere gale bevis ble presentert. I 1890 ble fem farger-teoremet bevist – som faktisk er betraktelig lettere å bevise enn fire farger-teoremet. Først på 60-70-tallet begynte man igjen å gjøre framskritt, og da ved hjelp av datamaskiner. I 1976 annonserte Kenneth Appel og Wolfgang Haken ved University of Illinois at de hadde bevist teoremet – mye ved hjelp av en datamaskin.

Det de hadde gjort, var å redusere problemet. De fant ut at, enkelt sagt, enhver slik graf kan bli bygd opp av et endelig antall enklere grafer. De fant 1,936 slike, så for å bevise teoremet var det nok å be en datamaskin gå gjennom alle disse mulighetene, og sjekke èn og èn.

Dette var langt fra enkelt, og krevde mye manuelt arbeid. For å finne disse 1,936 tilfellene, måtte de gjøre mye for hånd. Det endte opp med et over 400 sider langt bevis. De tekniske detaljene krevde mange originale ideer og annen matematisk analyse. En rekke observasjoner reduserer teoremet til såkalte triangulerte grafer, og litt tellearbeid setter begrensninger på eventuelle moteksempler. Til slutt med en metode som er inspirert fra fysikk brukt; på engelsk “method of discharging“. Man ser for seg at grafen er en elektrisk ledning, og har en viss ladning. Så kan man redusere grafen steg for steg sålenge man holder styr på “ladningen”. Mer informasjon om dette smarte trikset er på Wikipedia-artikkelen om beviset.

Men matematikere er kresne typer, og beviset fikk mye kritikk. De mente for eksempel at for at et bevis skulle være et ordentlig matematisk bevis, måtte det kunne sjekkes av mennesker. Andre mener at datamaskiner kun skal gjøre utregninger, og ikke steg i bevisene (det er en forskjell her).

Tross dette er det et faktum at maskiner tross alt gjør færre feil enn mennesker. Den største innsigelsen mot teoremer bevist av datamaskiner er estetisk: beviset gir ikke noen ny innsikt i problemet eller gir opphav til nye nyttige begreper. Det er jo tross alt dette som er vakkert med matematikk: det å få innsikt i et stort problem.

Til slutt: På en torus (=smultring) stemmer heller ikke 4-farge-teoremet. Her kreves 7 farger:

Torusen krever 7 farger.

En altfor vanskelig måte å løse en enkel ligning på

La oss si at vi har ligningen x=2x-2. Dette lærte man å løse på ungdomsskolen ved å få x-ene på èn side. (i dette tilfellet ser vi raskt at x=2 er eneste løsning). Men hva om vi har lyst til å være vanskelige?

Siden x=2x-2, kan vi skrive x=2(2x-2)-2=4x-6. Så vi har nå at x=4x-6. På samme måte kan vi sette inn for x i denne ligningen, og få x=4(2x-2)-6=8x-14. Fortsetter vi n ganger, får vi at x=2^nx-2^n-2^{n-1}+\cdots+2. Det siste leddet er en geometrisk rekke, som forenkler til 2^{n+1}-2.

Vi har altså nå at x=2^nx-2^{n+1}-2.  Vi deler på 2^n på begge sider og får \frac{x}{2^n}=x-2-\frac{2}{2^n}. Lar vi nå n gå mot uendelig, forsvinner venstresiden av ligningen og mye av høyresiden. Vi står igjen med 0=x-2, så x=2.

En veldig enkel tilfeldig tall-generator

Akkurat nå leser jeg boken “Chaos – A Very Short Introduction“. Den definerer et kaotisk system til å være et system som er veldig ømfintlig overfor initialbetingelsene. På et tidspunkt nevner boken et veldig enkelt dynamisk system.

Hva mener vi med et dynamisk system? For våre formål mener vi bare en følge med tall, $$x_0, x_1, \ldots$$. En enkel klasse av dynamiske systemer er på formen $$x_0=a$$ for en eller annen $$a$$, som vi kaller initialverdien. Så definerer vi rekursivt alle andre verdier av $$x_n$$ som $$x_{n+1}=f(x_n)$$ hvor $$f(x)$$ er en eller annen funksjon.

Nå skal vi la $$f(x)=4x(1-x)$$. Denne har to nullpunkter, nemlig $$x=0$$ og $$x=1$$. Den har et toppunkt i $$x=1/2$$.

Dette gir opphav til et dynamisk system så snart vi velger en initialverdi. Det kule med denne enkle funksjonen, er at i tidligere tider brukte man denne for å generere “tilfeldige” tall. La oss se litt på dette. En enkel, rekursiv implementasjon i SAGE er gitt ved:

def r(x,n):
    if n==0:
        return x
    else:
        return r(4*x*(1-x),n-1)

Vi genererer listen:

def generateList():
    return [[i,r(1/float(pi),i)] for i in range(0,500)];
L = generateList()

Og vi plotter den:

p = line(L)
p.show(xmin=0,xmax=500,ymin=0,ymax=1)

Her er resultatet vi får (klikk på bildet for noe større versjon):

Dette er kanskje litt overveldende. La oss bare ta 100 punkter:

Dette er ganske kult, for vi ser at oppførselen til følgen er helt vill. Betydningen av “vill” kan defineres matematisk, men la oss hoppe over det. Poenget er at følgen i stor grad oppfører seg “tilfeldig”. Vi ser også at små endringer i startverdien kan gi helt forskjellige følger. Under er først for startverdien 0.3, så for startverdien 0.31.

Vi ser at grafene er ganske like, men at verdiene opptrer på ganske forskjellige steder. Dette kan utnyttes for å lage tilfeldige tall. Man kan for eksempel først velge en initialverdi, så kjøre det dynamiske systemet, og bruke dette til å generere en følge av 100 tall. Neste gang velger man en annen initialverdi, og man vil få en følge som ikke ligner på den forrige.

Beregne volum av kuler

I anvendelser av matematikk har man ofte behov for å regne ut volumer av avanserte geometriske objekter. Som regel går det ikke an å regne ut slikt for hånd eller med pene formler, så matematikere jobber mye med å finne algoritmer som datamaskiner kan utføre for å finne en tilnærmet løsning.

Tenk deg at du har fått i oppdrag å regne ut arealet av en kule i n dimensjoner. Først av alt – hva i all verden mener vi med dette? En sirkel i planet med radius 1 kan beskrives som alle punkter $$(x,y)$$ i planet slik at  $$x^2+y^2=1$$ (hvorfor? hint: Pythagoras’ setning). På samme måte kan vi beskrive en kule som alle punkter $$(x,y,z)$$ i rommet slik at $$x^2+y^2+z^2=1$$.

Vi generaliserer, og definerer en  kule i n dimensjoner til å være alle punkter $$(x_1,x_2,\ldots,x_n)$$ i $$\mathbb{R}^n$$ slik at $$\sum_{i=1}^n x_i^2 = 1$$.

Men la oss nå si at du har lyst å regne ut arealet av en sirkel i planet. Vi kan anta sirkelen har radius 1 og er plassert i origo. Tegn så et kvadrat rundt sirkelen, med diagonaler med lengde 1, som på figuren under:

Enhetssirkelen på innsiden av en firkant.

Siden firkanten har sidelengder på 2, har den arel 4. Her kommer trikset: kast masse “dart-piler” (eller punkter, om du vil) på firkanten slik at de havner tilfeldig spredt omkring. Kall arealet til sirkelen for A. Da vil A/4 av dart-pilene havne på innsiden av sirkelen.  Dermed, for å få arealet av sirkelen, ganger vi dette forholdet med 4.

Fordelen med denne metoden er at det er veldig lett å sjekke om et punkt er på innsiden av sirkelen eller ikke. Vi sjekker bare om $$x^2+y^2 < 1$$ eller ikke. Om $$x^2+y^2 < 1$$, så er punktet $$(x,y)$$ på innsiden av sirkelen. Dette generaliserer lett til flere dimensjoner enn 2 og til andre figurer enn sirkler.

Jeg har testet denne metoden på sirkler i Python. Jeg laget et program som jeg kalte for areal_kule.py. Vi tester for sirkelen og med 1000 dart-piler:

Fredriks-MacBook-Air:Python Fredrik$ python areal_kule.py 2 1000
Tilfeldig volum: 3.196
Ekte volum: 3.14159265359
Error: 0.0544073464102

Ikke veldig imponerende, kanskje – vi kastet tross alt 1000 dart-piler! Vi tester med èn million dart-piler i stedet (dette tok litt under 10 sekunder på min maskin):

Fredriks-MacBook-Air:Python Fredrik$ python areal_kule.py 2 1000000
Tilfeldig volum: 3.144456
Ekte volum: 3.14159265359
Error: 0.00286334641021

Nå ble resultatet en god del bedre. La oss prøve å regne ut volumet av en kule:

Fredriks-MacBook-Air:Python Fredrik$ python areal_kule.py 3 1000000
Tilfeldig volum: 4.184968
Ekte volum: 4.18879020479
Error: 0.00382220478639

Ikke dårlig! Denne metoden kalles for Monte Carlo-integrasjon, og det viser seg at slike “tilfeldige” metoder ofte er mer effektivt i høyere dimensjoner.

Når vi først snakker om sirkler, kan man lure på hva som skjer med volumet til sfærer når vi øker dimensjonene. Resultatet er litt kontraintuitivt:

Volum kuler

Vi ser at volumet til kulene øker fram til dimensjon 4, hvor det begynner å falle. Faktisk går kulevolumet i dimensjon n mot null når n går mot uendelig. Dette er fordi diagonallengden på kvadratet rundt kulen blir større og større etterhvert som n øker.

For ordens skyld, her er Python-programmet jeg brukte for å regne ut volumene:

from random import random
from math import pi, gamma, fabs
import sys

if len(sys.argv) == 1:
    sys.exit("Skriv areal_kule d n. d dimensjon, n antall, std n=1000")
if len(sys.argv) == 2:
    d = int(sys.argv[1])
    n = 1000
if len(sys.argv) == 3:
    d = int(sys.argv[1])
    n = int(sys.argv[2])

i = 1
s = 0.
cube_area = 2**d #area of cube in dimension d

while i < n:
    if (sum([random()**2 for j in range(d)])) < 1:
        s += 1
    i += 1

random_area = (s/n)*cube_area
true_volume = pi**(0.5*d)/gamma(0.5*(d+2))

print "Tilfeldig volum: " + str(random_area)
print "Ekte volum: " + str(true_volume)
print "Error: " + str(fabs(random_area-true_volume))

Banach-Tarski paradox, very weak version

I post this mainly to test the MathJax JavaScript on this blog (if you have by some paranoid reason turned off JavaScript, you will see only LaTeX code below). However, this post is not totally without substance. The usual Banach-Tarski paradox states that any two bounded subsets with non-empty interior A,B of $$\mathbb{R}^3$$, it is possible to partition A into finitely many pieces, move the pieces around using rotations only and end with a copy of B (possibly somewhere else). The proof is lengthy and involves the Axiom of Choice. This should not foster any doubts about the Choice Axiom, however. It is possible to find paradoxical constructions without the Choice Axiom (without mentioning all its reasonable consequences). $$S^2$$ is paradoxical without Choice, by the way.  Anyhow, I’m drifting away from the main topic of this post.

Very weak version of the Banach-Tarski paradox: Let $$S^1$$ be the usual unit circle in $$\mathbb{R}^2$$. Remove one point from from the circle (for example $$1$$), and call this punctured unit circle $$C$$. Then it is possible to find two subsets $$A,B$$ of $$C$$ such that after rotating $$B$$ to $$r(B)$$, we have $$A \cup r(B)=S^1$$.

Proof: The proof is short and easy. Identify the plane with $$\mathbb{C}$$ for convencience. Let $$C=S^1-\{1\}$$. Let $$B=\{ e^{in} | n \in \mathbb{N} \}$$ (we adopt the convention that $$0 \notin \mathbb{N}$$).  Then $$B$$ is a proper (countable) infinite subset of $$C$$. Let $$A=C-B$$. We have $$C=A \cup B$$. Now, let $$r:\mathbb{C} \to \mathbb{C}$$ be the rotation $$z \mapsto ze^{-i}$$. Then $$r(B)=B \cup \{ 1 \}$$ and $$A \cup r(B)=S^1$$.

The proof is easy to follow, but the technique is conceptually the same as the technique used to prove the strong version of the paradox.  The technique is basically to find some infinite subset of $$C$$ that is regular enough to “almost rotate into itself” – with “almost” here meaning “all but finitely many points”.

Why is the above result interesting? My personal opinion is its conceptual carriage; it gives us the idea of how to prove stronger results such as the Banach Tarski-paradox. And also that mathematics is not always intuitive.

I’ll end this post with  a link to my own undergrad project paper about the strong Banach-Tarski paradox (contains some minor typos, by the way). CLICK HERE.