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

## Map, filter, reduce

En av de viktige tingene jeg har lært meg om programmering i de siste par årene, er at for-løkker er utdaterte og stygge. I dag er høyere ordens funksjoner og lambda-funksjoner greia. Dette er eksempler på begreper som gjennomsyrer funksjonell programmering. Her skal jeg forklare de tre viktigste funksjonelle funksjonene.

La oss starte med et enkelt problem og løse det på den “gammeldagse” måten. Oppgaven er å summere alle de odde tallene fra 1 og opp til et tall n. I Javascript kan dette gjøres slik:

const sumNumbers = function(upperLimit) {
sum = 0;
for (let i = 0; i <= upperLimit; i++) {
if (i % 2 == 1) {
sum += i;
}
}
return sum;
}


Det første vi legger merke til er at det er ganske mye kode. For det andre er ikke koden veldig selvforklarende. Vi har en midlertidlig variabel i, og vi setter sum lik 0 i begynnelsen, noe som ikke er sant. Ved hjelp av map, filter og reduce kan denne funksjonen gjøres mye mer lesbar og semantisk korrekt.

Vi starte med å forklare map. Kort sagt: gitt en liste med elementer av en viss type og en funksjon $f:A \to B$ (fra type A til type B), kan funksjonen f anvendes på hvert element i listen:
$(x_1,\ldots,x_n) \mapsto (f(x_1), \ldots,f(x_n)).$

Vi tar et eksempel (i Clojure, for å være morsomme). Vi starter med listen over tallene 1 til 5, og ønsker å gange alle med to:

(map (fn [x] (* x 2))
(list 1 2 3 4 5)
)

Notasjonen er enkel. Først definerer vi “gang med to”-funksjonen, deretter definerer vi listen vi starter med. Resultatet er listen [2,4,6,8,10]. Vi kan gjøre det samme i Javascript:

[1,2,3,4,5].map( (x) => 2*x)
// [ 2, 4, 6, 8, 10 ]


I begge eksemplene over matet vi map med anonyme funksjoner. Det er fullt mulig å gi dem mer kompliserte funksjoner. Anta vi for eksempel har lyst å sjekke om tall er primtall. Da kan vi gjøre følgende (Javascript):

const isPrime = function(n) {
if (n == 1) return false;
if (n == 2) return true;

for (let i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
};

[1,2,3,4,5,6,7,8,9,10].map(isPrime)
// [ false, true, true, false, true, false, true, false, false, false ]


(her startet vi med en funksjon $\mathrm{isPrime}:\mathbb N_+ \to \mathrm{Bool}$, og brukte funktoren map, og fikk en funksjon $\mathrm{isPrime}:\mathbb N_+^{10} \to \mathrm{Bool}^{10}$)

Okay, det får være nok om map. La oss forklare filter. Filter gjør det det høres ut som: den filtrerer en liste, gitt en boolsk funksjon. Vi tar et eksempel i Javascript og et i Clojure:

[1,2,3,4,5,6,7,8,9,10].filter( (x) => x % 2 == 0)
// [ 2, 4, 6, 8, 10 ]

(filter
(fn [x] (= (mod x 2) 0))
(list 1 2 3 4 5 6 7 8 9 10)
)
;; (2 4 6 8 10)


I begge eksemplene starter vi med listen over tallene 1 til og med 10, og så tar vi kun vare på partallene.

Vi kan dra primtalleksemplet litt lenger:

[1,2,3,4,5,6,7,8,9,10].filter(isPrime)
//  [ 2, 3, 5, 7 ]


På dette tidspunktet ville det vært kjekt med en funksjon tilsvarende Pythons range, som gitt start- og slutt-verdier gir en liste over alle tallene i dette intervallet. Dessverre har ikke Javascript noen innebygd funksjon som gjør dette, men vi kan lage en (litt hacky):

const range = function(start, end) {
return (new Array(end-start+1))
.fill(null)
.map((_,idx) => idx+start)
}


Eksempel:

range(1,10)
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]


Nå er det på tide å introdusere reduce. Den er hakket mer abstrakt enn de to andre. For å bruke reduce, trenger vi en startverdi, og en akkumulatorfunksjon. Det klassiske eksemplet er å summere elementene i en liste: anta du har lyst å summere tallene 1 til 10. Måten du gjør det på er å starte med 0 (acc = 0). Så legger du til første elementet i lista (acc += 1), så legger du til andre elementet i lista (acc+= 2), og så videre. Når du er ferdig med å akkumulere, har du svaret.

I Javascript skrives dette slik:

range(1,10).reduce( (x,y) => x + y, 0)
// 55


I Clojure:

(reduce + (range 1 11))
;; 55


Reduce er et veldig kraftig verktøy når man gjenkjenner når det kan brukes. Anta for eksempel at du har flere lister som du har lyst å lime sammen til én lang liste. Da kan vi skrive slik:

[[1,2],[4,5],[6,7]].reduce( (a1,a2) =>  a1.concat(a2), [])
// [ 1, 2, 4, 5, 6, 7 ]


Eller anta at du vil finne maks-verdien i en liste:

[1,2,3,4,2.5,0,-5].reduce( (x,y) => Math.max(x,y))
// 4


(om man ikke oppgir en initialverdi i Javascript, vil det første elementet i listen brukes som initialverdi)

Vi er nå klare til å summere alle de odde tallene:

const sumNumbers = function(upperLimit) {
return range(1,upperLimit)
.filter( (x) => x % 2 == 1)
.reduce( (x,y) => x + y, 0)
}


Se der! Funksjonen er flere linjer kortere, og det er ingen variabler som endrer verdi underveis. Vi starter med listen over alle tall fra 1 til den øvre grensen, så fjerner vi alle partall, og så summerer vi alle tallene. Svaret returnerer vi.

Og i Clojure:

(defn sumNumbers [n]
(reduce +
(filter
(fn [x] (= (mod x 2) 1 ))
(range 1 (+ n 1))
)
)
)


Til slutt: som en bonus kan vi skrive om isPrime-funksjonen i litt mer funksjonell stil:

const isPrime = function(n) {
if (n == 1) return false;
if (n == 2) return true;
return range(2,Math.floor(Math.sqrt(n))+1)
.every( divisor => n % divisor != 0)
}


Ingen for-løkker!

## 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 m$m-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

'''
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:

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

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

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?

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

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:

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:

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:

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

Til 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

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.

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:

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:

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