Endelig-genererte abelske grupper og Hermite-normalformen til heltallsmatriser

Dette blir en litt vanskeligere post enn ellers. Jeg vil kort skrive om et lite Python-skript jeg skrev for noen uker siden, og forklare hva det gjør.

Noen av leserne av denne bloggen (jeg vet ikke om dette er en ikke-tom mengde) har kanskje hatt et kurs i abstrakt algebra på universitetet, og lært om abelske grupper. Dette er matematiske objekter hvor du kan legge sammen og trekke fra, og slik at rekkefølgen ikke har noe å si (med andre ord er a+b = b+a alltid). Husker man spesielt godt, husker man også “fundamentalteoremet om endelig-genererte abelske grupper”. Dette teoremet sier at om du ikke trenger uendelig mange elementer for å beskrive gruppen din, kan den alltid beskrives ved hjelp av en n \times mm-matrise med heltallselementer.

Vi tar et par eksempler:

  • La G være heltallene modulo $11$. Dette betyr at 11 \equiv 0 i denne gruppen. Denne gruppen kan beskrives ved 1 \times 1-matrisen [11].
  • La G være gruppen av par (a,b), hvor a regnes modulo 11, og b er et vanlig heltall. Matrisen som presenterer denne gruppen er gitt ved \begin{pmatrix}11 & 0 \\ 0 & 0\end{pmatrix}.

Generelt vil gruppen \mathbb Z_{r_1} \oplus \mathbb Z_{r_2} \cdots \oplus \mathbb Z_{r_n} \oplus \mathbb Z^k beskrives ved en diagonalmatrise D med r_1,\ldots,r_n,0,0,\ldots,0 langs diagonalen. Dette er vel og fint, men presentasjonen er ikke unik! La meg forklare litt.

Denne presentasjon stammer fra å tenke på en heltallsmatrise som en avbildning \mathbb Z^n \xrightarrow{A} \mathbb Z^m. Den abelske gruppen \mathbb Z^m/im(A) (kokjernen til A) er da gruppen presentert av A. Ethvert basisskifte i \mathbb Z^n og \mathbb Z^m vil gi en isomorf kokjerne, så derfor er ikke A unik. Basisskifter svarer til å multiplisere A på venstre- eller høyresiden med inverterbare heltallsmatriser med determinant \pm 1. Dette svarer igjen til å utføre rad- eller søyleoperasjoner på A.

Så det vi ønsker, er å transformere A på en slik måte at det er lett å lese hvilken endelig-generert abelsk gruppe kokjernen er isomorf med. Helt ideelt ville det vært å få A på diagonalform, men det viser seg at vi ikke trenger å være så kravstore. Det holder at A er på triangulær-form, nemlig at alle elementer under diagonalen er null. Har vi A på denne formen, kan vi lese av diagonalelementene for å finne kokjernen.

Det finnes en algoritme for å gjøre dette, og formen matrisen ender opp på kalles for Hermite-normalform (strengt tatt er Hermite-normalformen en diagonalmatrise, men det trenger vi ikke). Det er en morsom øvelse å implementere denne i Python.

Det første jeg måtte gjøre, var å implementere min egen matrise-klasse i Python. Pakken Numpy har egne matriseobjekter, men disse konverterer alle elementene til flyttall, noe jeg ikke ville gjøre. Dette er ikke spesielt vanskelig, og også en morsom øvelse. Under gjengir jeg den relevante koden (det er mange flere ting man kan gjøre med matriser som jeg ennå ikke har implementert):

import ntheory
from operator import mul

class Matrix:
	"""
	Constructs a matrix object from a double list.
	"""
	def __init__(self, L):  
		self.L = L
		self.m = len(L[0]) # number of columns
		self.n = len(L) # number of rows

	def __add__(self,M):
		'''
		Returns the sum of self and M.
		'''
		newL = []
		for r in range(self.m):
			row = [self.L[r][i] + M.L[r][i] for i in range(self.n)]
			newL += [row]
		return Matrix(newL)

	def __sub__(self,N):
		return (self + (-N))

	def __neg__(self):
		newL = [[-r for r in R] for R in self.L]
		return Matrix(newL)

	def __mul__(self,N):
		'''
		Returns the product of self and N.
		'''
		NT = N.transpose()
		newL = []
		for i in range(self.n):
			newR = []
			for j in range(N.m):
				newR += [sum([self.L[i][k]*NT.L[j][k] for k in range(self.m)])]
			newL += [newR]
		return Matrix(newL)

	def transpose(self):
		'''
		Returns the transpose of self.
		'''
		newL = [[] for i in range(self.m)]
		for i in range(len(self.L)):
			for j in range(self.m):
				newL[j] += [self.L[i][j]]
		return Matrix(newL)

	def trace(self):
		'''
		If self is square, return trace.
		'''
		if self.n != self.m:
			return "NOT SQUARE"
		return sum([self.L[i][i] for i in range(self.n)])

	def switchRows(self,i,j):
		'''
		Returns the matrix obtained by switching rows i,j in self.
		Counting starts at 0.
		'''
		newL = list(self.L)
		newL[i], newL[j] = newL[j], newL[i]
		return Matrix(newL)

	def _prodDiagonal(self):
		return reduce(mul,[self.L[i][i] for i in range(len(self.L))],1)

	def det(self):
		return triangular(self)._prodDiagonal()


	def __str__(self):
		s = "{0}x{1}-matrix: ".format(self.m,self.n) + str(self.L[0]) + "\n"
		for row in self.L[1:]:
			 s+= 12*" " + str(row) + "\n"
		return s[:-1] + "."

def identity(n):
	'''
	Returns an n x n identity matrix.
	'''
	L = []
	for i in range(n):
		L += [[int(j == i) for j in range(n)]]
	return Matrix(L)

def concat(M,N):
	'''
	Input: M nxm matrix.
	       N n-1 x m-1 matrix.
	Output: A new matrix Q with N the
	 submatrix obtained by removing first col and row.
	 '''
	L = [M.L[0]]
	for i in range(1,len(M.L)):
		R = [M.L[i][0]]
		for j in range(len(N.L[0])):
			R += [N.L[i-1][j]]
		L += [R]
	return Matrix(L)

def submatrix(M,c=0,r=0):
	'''
	The submatrix obtained by removing col c and row r.
	'''
	L = []
	for i in range(len(M.L)):
		if i != r:
			R = []
			for j in range(len(M.L[0])):
				if j != c:
					R += [M.L[i][j]]
			L += [R]
	return Matrix(L)

Modulen “ntheory”, er en samling med tallteoretiske funksjoner jeg har skrevet tidligere. Den funksjonen jeg importerer regner ut største felles divisor mellom to tall a og b og returnerer en såkalt “Bezout-relasjon” mellom dem. Dette er et uttrykk på formen ax+by=d, hvor d er største felles divisor mellom a og $latex $b$. Koden til denne funksjonen ser slik ut:

def bezout(a,b):
    '''
    Returns a Bezout identity (as a tuple of two elts) for
    two numbers a,b. I.e. two numbers x,y such that
      ax+by=gcd(a,b)
    '''
    if b == 0:
        return (1,0)
    else:
        r = a % b
        q = (a-r)/b
        (s,t) = bezout(b,r)
        return (t,s-q*t)

Dette ble kanskje litt mye kode. Det viktigste er at dette er nok kode for å gjøre noen enkle men fundamentale operasjoner med heltallsmatriser. Nå er vi klare til å forklare litt om algoritmen bak funksjonen som transformerer en matrise til sin Hermite-normalform. Jeg skal ikke forklare det i detalj her, men ideen bak er dette: ved å multiplisere på venstresiden med elementærmatriser, kan vi på en systematisk måte fjerne elementene under diagonalen. Dette gjøres ved å finne det største elementet i første søyle, og bruke en Bezout-relasjon for å eliminere alle andre elementer.

Without further ado, her er koden:

def triangular(M):
	'''
	Input: an integer matrix M.
	Output: an upper triangulization U of M over the integers.
	Algorithm:
	 1. Find smallest nonzero element X in first column. Move this element to the top row.
	    If there are no nonzero elements go to step 3.
	 2. Use Bezout/Koszul-row operations to remove the nonzero elements below X. 
	 3. Repeat with the submatrix obtained by removing the first row and column.
	 4. Concatenate the result recursively.
	'''
	if len(M.L) == 1:
		if M.L[0][0] < 0:
			return -M
		return M
	(index, smallest) = (0,M.L[0][0])
	for i in range(len(M.L)):
		if abs(M.L[i][0])  < smallest:
			(index, smallest) = (i,M.L[i][0])
	if smallest == 0:
		return concat(M,triangular(submatrix(M)))
	if index != 0:
		N = M.switchRows(0,index)   ### row operation
	else:
		N = Matrix(M.L)
	for i in range(1,len(M.L)):
		d = ntheory.gcd(smallest, N.L[i][0])
		bez = ntheory.bezout(smallest, N.L[i][0])
		I = identity(len(N.L))
		I.L[0][0] = bez[0]
		I.L[0][i] = bez[1]
		I.L[i][0] = N.L[i][0]/d
		I.L[i][i] = -N.L[0][0]/d
		N = I * N
		if N.L[0][0] < 0:
			N = N.mult(-1)
	return concat(N,triangular(submatrix(N)))

Jeg skal la den interesserte og kapable leseren analysere funksjonen selv, og avslutter med noe noen eksempler på hvordan den fungerer.

La A være matrisen

A = \begin{pmatrix}1 & 2 \\ 3 & 4\end{pmatrix}.

Vi kjører da kommandoene “print(A)” og “print triangular(A)” i Python. Resultet er under:
2x2-matrix:
[1, 2]
[3, 4].
2x2-matrix:
[1, 2]
[0, 2].

Dermed kan vi se kokjernen er lik \mathbb Z/2. Nok et eksempel: La A være matrisen
A = \begin{pmatrix}1 & 2 & 3 \\ 4 & 5 & 6\end{pmatrix}

Resultatet blir da:

3x2-matrix:
[1, 2, 3]
[4, 5, 6].
3x2-matrix:
[1, 2, 3]
[0, 3, 6].

Dermed er kokjernen lik \mathbb Z/3 (det krever litt øvelse for å se sant umiddelbart, altså).

Til slutt en liten bemerkning: det finnes allerede matematisk programvare som regner ut ting som dette. For eksempel kan man i Macaulay2 skrive “prune coker A”, og svaret kommer med en gang. Hovedfordelen med å skrive slike funksjoner selv, er at en blir mer kjent med matematikken bak, og forståelsen blir større.

(dette ble en litt rotere bloggpost, men det får være. Hovedformålet var å subtilt skryte av at jeg bruke en lørdag til å implementere en interessant algoritme)

Fibonacci-tall og fraktaler

Leseren har kanskje hørt om Fibonacci-rekken. Det er en spesiell tallrekke som vokser veldig raskt. Regelen er enkel: vi må starte med to tall, 1 og 1. Så får vi neste tall i rekka ved å summere to to forrige. Så vi får 1+1=2. Dermed har vi 1,1,2. Så får vi neste ved å regne ut 1+2=3. Så vi har 1,1,2,3. Og så videre: 1,1,2,3,5,8,13,21,34,55,89,…

Det er lett å skrive et lite Python-skript som regner ut, si, de 200 første Fibonacci-tallene.

fiblist = [1,1]
n = 100
i = 2
while i != n:
 fiblist += [fiblist[i-1]+fiblist[i-2]]
 i += 1

Vi lager altså en liste på to elementer, og så lager vi en while-løkke hvor vi regner ut neste Fibonacci-tall ved hjelp av de to forrige. Resultatet ser omtrent slik ut (skroll til høyre for å se alle):

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842,10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738L, 19740274219868223167L, 31940434634990099905L, 51680708854858323072L, 83621143489848422977L, 135301852344706746049L, 218922995834555169026L, 354224848179261915075L, 573147844013817084101L]

Som vi ser, blir tallene fort utrolig store. Det er faktisk en nøyaktig formel for Fibonacci-tallene. La \varphi = \frac{1+\sqrt 5}{2} være “det gylne snitt”. Da viser det seg at det n’te Fibonacci-tallet er gitt ved

F_n = \frac{\varphi^n - (-\varphi)^n}{\sqrt 5}

Formelen ble bevist av de Moivre på 1700-tallet en gang. Vi skal ikke ha bruk for den. Vi skal nemlig snakke om et morsomt resultat av Zeckendorf: det sier at ethvert positivt tall kan skrives som en sum av forskjellige Fibonacci-tall. Dette er unikt om vi krever at vi ikke tillater etterfølgende Fibonacci-tall i summen. Hva betyr dette?

Jo, 1 er et Fibonacci-tall, og det er 2 også, så det er en “liten” sum. Det første ikke-Fibonacci-tallet er 4, som kan skrives 1+3. Neste tall er 5, som er et Fibonacci-tall. Neste igjen er 6, som kan skrives 6=1+5. Og 7=5+2. Og 9=1+8. 10=8+2. 11=8+3.

Så skjer det noe morsomt! Hittil har alle tallene kunne skrives med kun to Fibonacci-tall. Men dette går ikke når vi prøver med 12! Men vi kan skrive 12=8+3+1, som er en sum av 3 Fibonacci-tall. Det neste tallet som vi trenger 3 Fibonacci-tall for å skrive er 18, som kan skrives 18=13+1+5.

Ok, nå har vi lært dette. Så vi har lyst å skrive et program som skriver naturlige tall som summer av Fibonacci-tall. Det er flere måter å gjøre dette på, og min er sikkert ikke den mest effektive – kan du programmere, så kom gjerne med raskere forslag.

Det første jeg gjør, er å lage en liste over de 2000 første Fibonacci-tallene ved måten over. En måte å skrive et tall som en sum av andre Fibonacci-tall er “slags rekursivt”. Du finner det største Fibonacci-tallet som er lavere enn tallet du jobber med. Og så trekker du det fra. Da er oppgaven redusert til å skrive et lavere tall som sum av to Fibonacci-tall. Og slik jobber du deg bakover:

def fibrep(N):
 if N in fiblist:
   return [N]
 else:
   largest = 1
   for n in fiblist:
     if n >  N:
       break
     largest = n
   return fibrep(N-largest) + [largest]

Tester man dette, ser man dette går overraskende raskt (til tross for rekursjonen!). Faktisk vil denne koden også gi en såkalt Zeckendorf-representasjon av tallet N. Dette betyr at svaret vi får er den unike måten å skrive N på som sum av forskjellige, ikke etterfølgende Fibonacci-tall (et kort bevis på hvorfor: anta først at vi får ut en liste med to like Fibonacci-tall (f.eks 10=5+5). Dette kan ikke skje, fordi 5 er et Fibonacci-tall, og da vil koden terminere på den første av dem. Anta så at vi får to etterfølgende Fibonacci-tall: f.eks 21=13+8. Men da er 21 selv Fibonacci-tall, så koden terminerer allerede da)

Her er for eksempel Zeckendorf-representasjonen av de 100 første naturlige tallene:

[[1], [2], [3], [1, 3], [5], [1, 5], [2, 5], [8], [1, 8], [2, 8], [3, 8], [1, 3, 8], [13], [1, 13], [2, 13], [3, 13], [1, 3, 13], [5, 13], [1, 5, 13], [2, 5, 13], [21], [1, 21], [2, 21], [3, 21], [1, 3, 21], [5, 21], [1, 5, 21], [2, 5, 21], [8, 21], [1, 8, 21], [2, 8, 21], [3, 8, 21], [1, 3, 8, 21], [34], [1, 34], [2, 34], [3, 34], [1, 3, 34], [5, 34], [1, 5, 34], [2, 5, 34], [8, 34], [1, 8, 34], [2, 8, 34], [3, 8, 34], [1, 3, 8, 34], [13, 34], [1, 13, 34], [2, 13, 34], [3, 13, 34], [1, 3, 13, 34], [5, 13, 34], [1, 5, 13, 34], [2, 5, 13, 34], [55], [1, 55], [2, 55], [3, 55], [1, 3, 55], [5, 55], [1, 5, 55], [2, 5, 55], [8, 55], [1, 8, 55], [2, 8, 55], [3, 8, 55], [1, 3, 8, 55], [13, 55], [1, 13, 55], [2, 13, 55], [3, 13, 55], [1, 3, 13, 55], [5, 13, 55], [1, 5, 13, 55], [2, 5, 13, 55], [21, 55], [1, 21, 55], [2, 21, 55], [3, 21, 55], [1, 3, 21, 55], [5, 21, 55], [1, 5, 21, 55], [2, 5, 21, 55], [8, 21, 55], [1, 8, 21, 55], [2, 8, 21, 55], [3, 8, 21, 55], [1, 3, 8, 21, 55], [89], [1, 89], [2, 89], [3, 89], [1, 3, 89], [5, 89], [1, 5, 89], [2, 5, 89], [8, 89], [1, 8, 89], [2, 8, 89]]

(skroll for å se alle) Vi ser nå at noen tall krever 4 Fibonacci-tall, for eksempel 33=1+3+8+21. Andre krever enda flere. Så vi kan spørre oss, hvis vi plotter naturlige tall mot lengden på en Zeckendorf-representasjon av dem, hvordan vil denne grafen se ut? Vi ser allerede at for de 11 første tallene er den konstant lik 2 (bortsett fra på Fibonacci-tallene hvor den er lik 1).

La oss se hvordan dette ser ut for de 200 første naturlige tallene:

Plot of the 200 first natural numbers versus the length of their Zeckendorf representation.
Plott av de 200 første naturlige tallene mot lengden på deres Zeckendorf-representasjon.

Vi ser et slags mønster, men det er ikke helt klart hva som skjer. La oss plotte de 1000 første også:

De 1000 første naturlige tallene og lengden til deres Zeckendorf-representasjon.
De 1000 første naturlige tallene og lengden til deres Zeckendorf-representasjon.

Hmhm. Mønsteret er ennå litt tydeligere! La oss prøve med de 10.000 første naturlige tallene!

De 10.000 første naturlige tallene og lengden på deres Zeckendorf-representasjon.
De 10.000 første naturlige tallene og lengden på deres Zeckendorf-representasjon.

Dette er morsomt! Nå ser vi helt tydelig et mønster. Det er til og med noe fraktal-lignenden over det. På den nederste “linjen” ser vi tall som har lengde 1 Zeckendorf-representasjon. Dette er Fibonacci-tallene. På linje 2 er det de som har lengde 2, og så videre. Det vi ser er at disse tynnes ut når vi nærmer oss neste Fibonacci-tall, og sånn er det på hver linje.

Nå kan vi spørre oss hvor raskt denne funksjonen vokser, hvor regulær den er, og så videre! Men det får vente til en anne bloggpost…

Hva er sannsynligheten for at ditt telefonnummer er primtall?

Et illustrasjonsbilde for å gjøre artikkelen mer interessant. Det har ingenting med matematikk å gjøre. Kilde: Wikipedia.
Et illustrasjonsbilde for å gjøre artikkelen mer interessant. Det har ingenting med matematikk å gjøre. Kilde: Wikipedia.

La oss snakke litt om telefonnummer og primtall og sannsynlighet. Hva er sannsynligheten for at ditt telefonnummer er primtall?

La oss starte med telefonnummer. I prinsippet kan et telefonnummer være en hvilken som helst åttesifret tallkombinasjon mellom 0 og $$10^8-1$$. Men la oss være litt mer realistiske. Ingen privatpersoner i Norge har et mobilnummer som begynner på 0, 1 eller 8. De resterende tallene er enten fasttelefon eller mobil (her er kilden min denne to år gamle tråden på Norsk Freakforum). Så for oss er definisjonen på et telefonnummer et hvilken som helst 8-sifret tall som starter på en av tallene 2,3,4,5,6,7 eller 9 (det gir $$7 \cdot 10^{7} $$ mulige nummer, altså ca. 14 nummer per person i Norge. Dette er egentlig ikke så mye – ettersom bedrifter ofte har mange nummer).

La oss snakke litt om primtall. Et primtall er et tall som ikke er en 1, og er delelig med kun seg selv og 1. (for de matematisk sofistikerte: vi vil at restkroppen $$\mathbb Z/(p)$$ skal være en kropp, og hvis $$p=1$$, får vi $$\mathbb Z/(p) =0$$, altså “kroppen med ett element“, som er problematisk). For å friske minnet, her er de første primtallene: 2,3,5,7,11,13,17,19,23,29,31,37,41,43..,101,… So far so good!

Det er lett å se at det er uendelig mange primtall. Dette ble bevist for flere tusen år siden, og det mest kjente beviset, som fremdeles er det eneste man lærer i dag, ble gitt av Euklid. Det går som følger: Vi skal konstruere en uendelige følge med primtall (ikke nødvendigvis alle, men likefullt en uendelig følge). La første tall i følgen være $$2$$. Anta så induktivt at vi har konstruert følgen opp til $$a_k$$. Dann så tallet $$a_1a_2a_3 \cdots a_k + 1$$ (produktet av alle tallene i følgen sålangt pluss en). Dette er et tall som ikke har noen faktor felles med noen av tallene i følgen så langt, så det må finnes et primtall $$p$$ som er ulik $$a_i$$ for $$i=1,2,\cdots,k$$. Sett $$a_{k+1}=p$$. Dette viser at vi kan danne en uendelig lang liste med forskjellige primtall. QED.

Legg merke til at teknikken i beviset ikke produserer alle primtall. For å se dette, prøv å konstruér følgen over, og se hvilke primtall som mangler. Hint: følgen vil starte med $$2,3,7,…$$.

Men dette var en digresjon. Det neste store spørsmålet med primtall, nå når vi vet at det er uendelig mange av dem, er: hvordan fordeler primtallene seg? Med andre ord, hvor mange primtall er det i intervallet $$[0,x]$$ når $$x$$ varierer? For eksempel, for $$x=10$$, ser vi at det er 4 primtall mellom $$0$$ 0g $$x=10$$. Mellom $$0$$ og $$20$$ har vi $$8$$ primtall. Mellom $$0$$ og $$30$$ har vi $$10$$ primtall. Allerede nå ser vi et mønster: primtallene blir sjeldnere og sjeldnere. Faktisk kan vi komme med en tilnærmet formel for hvordan hvor mange primtall det er lavere enn $$x$$ (vi kaller “antall primtall lavere enn $$x$$ for $$\pi(x)$$):

\[ \pi(x) \sim \frac{x}{\ln x}. \]

Her betyr “$$\sim$$” at formelen er en god tilnærming for store $$x$$. Denne formelen er kjent som “primtallssatsen“, og ble først bevist av Hadamard og Poussin ved hjelp av komplekse teknikker (både billedlig og bokstavelig talt). Et mer elementært bevis ble gitt mye senere av den norske matematikeren Atle Selberg og den ungarske matematikeren Paul Erdös uavhengig av hverandre (noe som forøvrig skapte en ørliten plagiatkonflikt i matematikermiljøet, men det er annen sak…).

y-aksen viser antall primtall lavere enn x. Bildet er sakset fra Wolphram Mathworld.
y-aksen viser antall primtall lavere enn x. Bildet er sakset fra Wolphram Mathworld.

Det som er så fint med primtallssatsen, er at vi nå kan beregne hvor mange telefonnummer som er primtall (circa, selvfølgelig!). Siden ingen telefonnummer starter på 8, må vi gjøre dette i to omganger. Først regner vi ut hvor mange primtalltelefonnummer det er som begynner på 2,3,4,5,6,7, og så hvor mange som begynner 9. Det første tallet er $$\pi(80000000)-\pi(20000000)$$ (klarer leseren å se hvorfor??). Det andre tallet er $$\pi(100000000)-\pi(90000000)$$. Nå kan vi bruke primtallformelen over for å regne ut hva disse differansene er. Gjør vi det får vi henholdsvis 3.206.519  og 514.762 (rundet til nærmeste heltall). Dermed er det circa $$3.206.519+514.762=3.721.281 \approx 3.7 \cdot 10^6$$ telefonnummer som er primtall.

Vi konkluderer med at prosentmessig er det

\[ 100 \cdot \frac{3.7 \cdot 10 ^6}{7 \cdot 10^7}\approx 5.3\% \]

Så med andre ord, det er omtrent like mange folk med primtallstelefonnummer som Venstre-velgere i dette landet.

Matematisk julepynt

Det er jul og eksamenstid. Det betyr at vi har ekstra motivasjon til å gjøre ting som ikke innebærer å lese til eksamen – for eksempel å lage julepynt.

Først en liten forhistorie

Et polyeder er en matematisk figur som er satt sammen av polygoner. Eksempler på polyedre er:

image003 Leonardo_polyhedra

Polyedret til venstre er satt sammen av 18 kvadrater og 8 trekanter. Polyedret til høyre, også kjent som en såkalt “fotball” (red. anm: utstyr brukt av sportsinteresserte), er satt sammen av 12 femkanter og 20 sekskanter.

Men noen polyedre er likere enn andre. Dette er polyedre som er satt sammen av helt like figurer, og der alle figurene møtes på samme måte i hvert hjørne. Dette er de platonske legemene:

 platonic

Disse er satt sammen av trekanter, kvadrater eller femkanter. Det gule polyedret er satt sammen av fire trekanter, det grønne er satt sammen av åtte trekanter, det røde er satt sammen av seks kvadrater (red. anm: også kalt en terning). Det lilla er satt sammen av 20 trekanter, og det blå er satt sammen av 12 femkanter. De kalles (i samme rekkefølge) for tetraeder, oktaeder, hexaeder, icosaeder og dodekaeder (på engelsk bytter man ut “eder” med “hedron”).

Her er en funfact kjent som Eulers teorem: teller du antall hjørner (H), antall kanter (E) og antall flater (F) i figurene over, får du alltid at forskjellen H-E+F=2. (prøv selv!)

Julepynt

Nå har vi kommet til poenget med denne posten. Polyedre eksisterer ikke bare i matematikernes fantasi, men også på juletrærne – ihvertfall om man henger dem der. Du må bare lage dem først.

Alt du trenger er piperensere, gjerne av typen som glitrer. Jeg fant mine på juggelbutikken “Tiger” på Arkaden i Oslo. Antakelig selges de andre steder også.

Greia er følgende: bruk en linjal, og brett piperenserne slik at du deler dem i tre, fire, eller fem like store deler (ha en liten del til overs slik at du “knyte” kantene). Så setter man dem sammen. Her er noen bilder:

2013-12-12 10.40.18De over er tetraederet, kuben og oktaederet. (Beklager bildekvaliteten, men jeg skal liksom drive med matematikk og ikke drasse på gode kameraer!)2013-12-12 10.40.22Her er oktaederet på nytt, og på høyresiden er dodekaederet.

2013-12-12 10.40.30Til slutt har vi ikosaederet. Det var vanskeligst å lage, og ble ikke så veldig symmetrisk. Utfordring: gjør det bedre selv.

“hva er MATEMATIKK” av Liza Lorentzen

Hva er matematikk?Boken “hva er MATEMATIKK” av professor i matematikk ved NTNU, Lisa Lorentzen, kom ut i november. Den er en del av Universitetsforlagets “hva er”-serie. Jeg fullførte nylig boken.

Boken er ment for folk flest, og det er meningen at hvem som helst skal kunne lese boken uten å gå glipp av noe.  Boken har syv kapitler, hvor de seks siste begynner med “matematikk og …”: tall, verden, struktur, sannhet, uendeligheten og skjønnhet.

Målet med boken er ikke å gi noe hurtigkurs i matematikk eller å være noe “survival kit” gjennom Kalkulus-kurset. Den prøver, tvert om, å beskrive hva matematikk er gjennom å appellere til hva en matematiker gjør og hva som er så fascinerende med matematikk. Nettopp på siste punktet skinner forfatterens egen fascinasjon gjennom. Matematikk er utrolig fascinerende, og har man ikke allerede denne fascinasjonen, smitter den over fra Lorentzens engasjerte beskrivelser.

På enkelte steder virker hun så fascinert at det nesten virker kunstig – men man skal ikke klage så mye over overdreven fascinasjon for matematikk! Slikt finner man ikke over alt.

Hun tar blant annet opp Möbius-båndet, at \sqrt{2} er irrasjonal, Koch-snøflak, fraktaler, matriser, matematiske modeller, uendelighet, tesseleringer av planet, Euler-karakteritistikk, med mer.

Boken er lettlest (kan hende enkelte deler ikke er kjempelettlest om man ikke er vant til å lese tung matte) – fin sengelesing/trikkelesestoff.

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.

Litt om telling

La oss være litt filosofiske. Du er et steinaldermenneske, eller noe enda eldre enn det, eller bare dum. Du kan nemlig ikke tallene, men vil likevel finne ut om det er du eller naboen som har flest fisk.

Hadde du kunnet telle,  hadde det vært mye enklere, for det er lett å sjekke om et tall er større enn et annet. Matematisk kan vi si at du har en funksjon fra mengden av fiskehauger (F) til heltallene. La oss kalle den $$f:F \to \mathbb{N}$$. Så om din fiskehaug kalles A, og naboen B, er alt vi trenger å sjekke om $$f(A) > f(B)$$.

Men du kjenner ikke til heltallene $$\mathbb{N}$$! Fiskehauger er mengder bestående av fisk. Symbolsk kan vi si $$A = \bigcup_{a \text{ fisk}} \{a\}$$. Så hvordan kan vi telle uten tall? Vel, det kan vi ikke! Men vi er ikke helt fortapte. La oss si at du har to hauger, A og B,  med like mange fisk. Da kan hver fisk fra haug A “parres” med nøyaktig en fisk fra haug B, og hver fisk fra haug B kan parres med èn fra haug A. Vi ser at vi får en 1-1-korrespondanse mellom fisk i haug A og fisk i haug B.  Matematisk har vi en bijeksjon $$g:A \to B$$, det vil si en funksjon fra A til B som er både 1-1 og “på”/surjektiv.

Men hvordan er situasjonen om det er færre fisk i haug A enn i haug B? (for enkelhets skyld kan du tenke at det er to fisk i haug A og 5 i haug B) Da ser vi at det er umulig å få til en funksjon fra A til B som er “på” B, eller surjektiv. Det betyr at det er umulig å gi hver fisk i haug B en “partner” i A, fordi det er færre fisk i haug A.

Motsatt, om det er flere fisk i haug A enn i haug B, sier litt ettertanke oss at det er umulig å få til en injeksjon $$A \to B$$. En injeksjon er en funksjon som ikke sender to forskjellige tall til samme tall $$b$$ . Om det er flere fisk i haug A, må minst to $$a$$ sendes til samme $$b$$.

Dermed ser vi at det eneste tilfellet hvor vi klarer å få til en funksjon som er både surjektiv og injektiv, er når det er like mange fisk i haug A som i haug B. Dette gir oss også muligheten til å si når det er færre eller flere fisk i haug A enn i haug B. Vi definerer det til å være flere fisk i haug A enn i haug B om det ikke finnes noen injeksjoner $$A \to B$$, og vi definerer det til å være færre fisk i haug A enn i haug B om det ikke finnes noen surjeksjoner $$A \to B$$. Til slutt sier vi at det er like mange fisk om det finnes en bijeksjon mellom A og B, altså både en injeksjon og surjeksjon.

Hva forteller alt dette oss? Det første vi kan si, er at heltallene har mye mer struktur enn vi trenger om vi bare skal sjekke om noe har like mange elementer som noe annet. Å sjekke om det finnes en injeksjon/surjeksjon/bijeksjon sier ingenting om hvor mange elementer det er i mengdene, bare om det er færre/flere/like mange. Å telle er en kvantitativ operasjon, mens å sjekke hva slags funksjoner det finnes mellom to mengder er en kvalitativ operasjon.

Men ok, vi har kommet fram til at vi ikke trenger heltallene for å sjekke hvilken mengde som har flest elementer. Men hva er poenget? Hvorfor gjøre det så tungvindt? Vel – nå har vi en mer elementær måte å sjekke størrelse på mengder på, og dette hinter om at vi kanskje kan generalisere definisjonene av “flere/færre enn” til andre mengder enn bare endelige.

For nå, la oss anta at leseren skjønner hva som menes med en uendelig mengde. Et eksempel på en slik mengde er mengden av alle heltall. Det er lett å sjekke at det er flere heltall enn, la oss si, elementer i mengden $$A=\{1,2,3,4,5\}$$. Det finnes nemlig ingen surjeksjoner $$A \to \mathbb{N}$$ (Bevis: om det finnes en slik surjeksjon, finnes også en surjeksjon $$A \to \{1,2,3,4,5,6\}$$ ved restriksjon. Dette går bare ikke).

Et annet eksempel på en uendelig mengde er mengden av partall, altså tallene $$E=\{2,4,6,8,\cdots\}$$. Siden partallene er en ekte delmengde av heltallene (det finnes heltall som ikke er partall), er det naturlig å tro at det er flere heltall enn partall. La oss sjekke med vår definisjon: Kan vi bevise at det ikke finnes noen injeksjoner $$\mathbb{N} \to E$$? Svaret er nemlig nei: et eksempel på en injeksjon er funksjonen $$n \to 2n$$. Det er lett å sjekke at denne er injektiv, så vi må konkludere (med vår definisjon av “færre enn”) at det er færre/like mange heltall som partall. Det er også lett å se at den er surjektiv, så vi er faktisk nødt til å konkludere med at det er like mange partall som heltall, selv om det åpenbart finnes mange heltall som ikke er partall.

Nå blir du kanskje frustrert, river deg i håret, og tenker at matematikere lager helt pussige definisjoner. Er alle mengder like store, bare de er uendelige? Nei, det finnes mange forskjellige “uendeligheter”, alle av forskjellige størrelse (det vil si, det finnes ingen bijeksjoner mellom dem). Det kan vi ta i en senere bloggpost.

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))