Boolean algebra and computer chips

Computers work by manipulating patterns of zeroes and ones, which are represented by electrical signals varying in intensity. It is fascinating to ponder the fact that starting with simple manipulations of these electrical signals, we can build Mac OS.

The most basic logic units in a computer are called (fittingly) logic gates. These are devices with a number of inputs, and a number of outputs. The only allowed input and output are zeroes and ones. Thus logic gates represent functions \{ 0,1 \}^n \to \{ 0,1\}^m. Such functions are called Boolean functions (after George Boole). We often think of zero as representing "false", and one as representing "true". Thus the input of a Boolean function is an array of "truth values", and the output is another array of truth values.

The whole function can be represented by a truth table:

And Value
0 0 0
0 1 0
1 0 0
1 1 1

Here we have the truth table for the logical function "and", which takes two inputs, and produces one input. It is "true" if and only if both its inputs are true.

Similarly, we have the truth table for the "or" function:

Or Value
0 0 0
0 1 1
1 0 1
1 1 1

The "or" function \mathrm{or} : \{ 0 , 1 \}^2 \to \{ 0 , 1\} is true if and only if one of its input variables are true.

We also have the "negation function" \mathrm{not} : \{ 0, 1 \} \to \{ 0, 1\}  which is true if and only its input is not true.

Given these three functions, we can construct all other Boolean functions.

We first introduce a handy algebraic notation for Boolean functions. We can define them by a formula with variables x,y. We write \mathrm{and}(x,y) = x \cdot y. A formula has no value until it is evaluated at some truth values. Say we put in x=0, and y=0, meaning that both x and y are false. Then we have x \cdot y = 0 \cdot 0=0, since the "And" function must return false here. Similarly, we have 1 \cdot 1 = 1.

For the "or" function we write \mathrm{or}(x,y) = x + y. With this notation, we can manipulate Boolean functions must like in high school algebra. For example, it is true that x \cdot y = y \cdot x, and also that x + y = y + x, since in "and" and "or", order doesn't matter. Not so obvious, but still true, we have that x \cdot (y + z) = x \cdot y + x \cdot z, just as in high school algebra. We also have x + 0 =x, 0 \cdot x = 0, and 1 \cdot x = x (where 0 is the boolean function that is always false).

But here stops the similarities with high school algebra. In this algebraic system, it is always true that x \cdot x = x (shorthanded x^2 =x). This is true because if a statement x is true, then clearly the statement x \mathrm{And} x is true (and conversely). Similarly, we have that x +x = x. Also: x + 1 = 1.

We also write \overline x for the negation function.

Every boolean function of two variables can be described using this three functions. We list all boolean functions of two variables:

Function x 0 0 1 1
y 0 1 0 1
Constant 0 0 0 0 0 0
And x \cdot y 0 0 0 1
x And Not y x \cdot \overline y 0 0 1 0
x x 0 0 1 1
Not x And y \overline x \cdot y 0 1 0 0
y y 0 1 0 1
Xor x \cdot \overline y + \overline x \cdot y 0 1 1 0
Or x + y 0 1 1 1
Nor \overline{x + y} 1 0 0 0
Equivalence x \cdot y + \overline x \cdot \overline y 1 0 0 1
Not y \overline y 1 0 1 0
If y then x x + \overline y 1 0 1 1
Not x \overline x 1 1 0 0
If x then y \overline x + y 1 1 0 1
Nand \overline {x \cdot y} 1 1 1 0
Constant 1 1 1 1 1 1

The boring way to prove this is to check that all the expressions evaluate to the values in the right columns.

However, a more surprising fact, is that the only boolean function we really need is the "Nand" function: all other boolean functions can be built from combinations of Nand's. This can be proved using the algebraic laws we discussed above.

  • The not-function \{ 0,1 \} \to \{ 0,1 \} is the same as \mathrm{nand}(x,x) = \overline{ x \cdot x } = \overline {x } = \mathrm{not}(x). If we had physical nand gates and wires, we could then form the not-function as follows: 
  • Given this, it is easy to build the and-function: \mathrm{and}(x,y) = \mathrm{not} \circ \mathrm{nand}(x,y). This is done by wireing as follows:The gates are nand gates.
  • The construction of "or" is slightly more complicated. We first show a solution diagram: All gates are nand gates. That this is actually an "or" gate follows from de Morgan's laws: the wireing can be translated to the following formula
    \mathrm{nand}(\mathrm{nand}(x,x), \mathrm{nand}(y,y)). Inserting the definitions, this is \mathrm{nand}(\mathrm{not}(x), \mathrm{not}(y)), which is \overline{ \overline{x}, \overline{y}}. By de Morgan's law, this expression is equal to \overline{\overline{x}} + \overline{\overline{y}} = x + y.

Since we can build "not", "and", and "or", it follows that we can build all other logic gates. Thus everything a computer does comes from a simple "nand".

So far we have talked about the basic logic gates, and introduced an algebraic notation for computing with boolean functions. The next steps in explaining how a computer works would be to talk about arithmetic units, for example. That would be in a future blog post!

(an interesting mathematical question is this: what kind of algebra does the boolean functions constitute? They do not form a ring, since there is no additive inverse...)

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

The probability distribution of the length of pop songs

Taking a course in probability can be extremely fun if you try to apply some of acquired knowledge to real world data sets. Finding data types that are easy to gather and at the same time interesting is a problem in itself. By a flash of inspiration, I came to think of this incredible easy example: the length (in seconds) of pop songs.

After a succesful Google search, I ended up with NRK's Spotify list "NRK mP3 - siste 400" and sampled the 42 first song lenghts.  Using the Python function below, the lengths were converted to seconds:

def mintilsek(n):
    min = floor(n)
    s   = (n-min)*100
    return int(round(min*60+s))

The sample data ended up as follows:

w = [52 241 223 231 225 242 263 222 200 220 238 213 210 213 210 183 321
 265 228 200 206 200 228 193 269 289 197 211 211 236 252 222 224 184
232 198 207 220 178 192 258 192]

The natural question to ask is: Which distribution does these numbers belong to? As so many real world populations distribute normally, the first thing I did was to plot the observed sample values in a normal QQ-plot (that is, normal quantiles on one axis, and sample quantiles on the other axis). I did that using the following R code:

> qqnorm(w); qqline(w)

Where w is the data set. The result is seen below:

The fit is not too bad, but there are noticable probability mass on the tails, so a probability distribution with heavier tails should be considered.

Let us for the moment assume that the distrubution is normal. We can do a maximum likelihood estimation, to estimate the parameters \mu,\sigma, the mean and standard deviation respectively. R has (obviously) a function for this:

> fitdistr(w, "normal")
      mean          sd    
  223.785714    29.214751 
 (  4.507934) (  3.187591) 

That is, if we assume that the distribution is normal, then a maximum likelihood estimate of the parameters tells us that the mean song length is 3:43 with a standard deviation of 29 seconds. That is, about 68% of all songs are between 3:14 and 4:12 minutes long.

If we now however assume that the population has a Cauchy distribution, which has heavier tails, then we get the following:

> fitdistr(w, "cauchy")
    location      scale   
  217.829335    15.684886 
 (  3.897386) (  3.090949)

Since neither the mean nor the variance exists for a Cauchy distribution because of its heavy tails, these numbers are difficult to compare with the previous numbers. According to this, however, 50% of all pop songs have length less than 3:37 minutes.

Finally: We know that for sufficiently large samples, the sample average \overline{X} is approximately normal. Thus we can find an approximate confidence interval for the real median \mu (page 386, Devore & Berk). The sample mean is 223.8 and the sample standard deviation is 29.6. Thus by the formula \overline{x} \pm z_{\alpha/2} \frac{s}{\sqrt{n}} we find that a confidence interval for \mu with approximately 95% confidence is  (215, 233).

Conclusion: Though I could, and maybe should, have written a lot more, it seems that assuming song lengths are normally distributed is a fair assumption, given that the data fit was nearly linear for values near the mean. (that is, if we ignore the "extremes", then the distribution is certainly "very" normal)

This proves that playing with statistics can be fun (as I have just been doing it for the last 3-4 hours).