SF1688 Diskret matematik 6,0 hp

Tillfälleskod	Termin(er)	Period(er)	Föreläsare
51094	HT2025	1	Svante Linusson

Anteckningar med utgångspunkt i föreläsningsslides.

Föreläsning 1

I schemat: den 25 augusti 2025

Grafer

Graf: Betecknas $G=(V,E)$, där mängden $V$ består av noder (hörn) och $E$ består av kanter (oordnade par av noder).

Två noder $x,y\in V$ är grannar omm $xy\in E$.
Grannmängden för en nod $x$: $N(x)=\{y\ |\ xy\in E\}$
Antalet grannar (valens eller grad): $\delta(x)=|N(x)|$
Grannlista:
a b c d e f g
b a a a f e
c c b b
d d
Grannmatris $M=\{m_{ij}\}$, där $m_{ij}=\begin{cases}1,\quad ij\in E\\0,\quad\text{annars}\end{cases}$.

Isomorfi för grafer

Likhet för två grafer kan (informellt) sägas uppfyllas "när de kan ritas likadant så när som på nodernas namn".

Formellt:

Låt $G_1=(V_1,E_1),G_2=(V_2,E_2)$. Funktionen $f:V_1\to V_2$ är en grafisomorfi om

$f$ är en bijektion, samt

det gäller $\forall x,y\in V_1$ att $\{x,y\}\in E_1\iff\{f(x),f(y)\}\in E_2$

$G_1,G_2$ sägs då vara isomorfa ("lika").

Speciella grafer

Kompletta grafen: Alla noder är sammanlänkade.
Cykelgrafen: Graf med noder $\{1,2,\dots,n\}$ och kanter $\left\{\{1,2\},\{2,3\},\dots,\{n-1,n\},\{n,1\}\right\}$.
Kompletta bipartita grafen: Varje nod ur den ena nodmängden är ansluten till samtliga noder ur den andra. Mellan noder ur samma nodmängd saknas kanter.

Reguljära grafer: Grafer vars noder alla har samma valens.

Satsen om valensernas summa: $\sum_{x\in V}\delta(x)=2\cdot|E|$

Udda/jämna noder: En nod är udda resp. jämn om den har udda resp. jämn valens.

Handskakningslemmat:

\[\red{2\cdot|E|}=\sum_{x\in V}\delta(x)=\green{\sum_{x\in V_\text{jämna}}\delta(x)}+\blue{\sum_{x\in V_\text{udda}}\delta(x)}\]

där $V_\text{jämna},V_\text{udda}$ består av grafens jämna resp. udda noder.

Eftersom VL är jämnt, och första summaformeln i HL är jämn, måste även $\blue{\sum_{x\in V_\text{udda}}\delta(x)}$ vara det. Slutligen, eftersom varje $\delta(x)$ i denna summering är udda, måste antalet termer (och således $|V_\text{udda}|$) vara udda.

Föreläsning 2

I schemat: den 26 augusti 2025

Delgrafer och vandringar

Givet en graf $G=(V,E)$ säger vi att en annan graf $G_1=(V_1,E_1)$ är en delgraf till $G$ om $V_1\subseteq V$ och $E_1\subseteq E$.

En vandring (eller promenad) är en sekvens noder $v_1v_2\dots v_k$ där $v_iv_{i+1}\in E$ för $i=1\dots k-1$.

Några specialfall:

En väg är en vandring där alla passerade kanter är olika (men noder får upprepas).
En stig är en väg där inga noder upprepas.
En krets är en sluten väg, dvs. en väg $v_1v_2\dots v_{k+1}$ med $v_1=v_{k+1}$.
En cykel ("sluten stig") är en krets $v_1v_2\dots v_{k+1}$ varav $v_1v_2\dots v_k$ är en stig, $k\geq 3$.
- En cykel är därmed en delgraf isomorf med cykelgrafen $C_k$.

Sammanhängande grafer

En graf $G$ är sammanhängande om det, för varje par av noder $x,y\in V$, finns en stig från $x$ till $y$.

En komponent i $G$ är en maximal sammanhängande delgraf.

Antal vandringar

Sats: (bevis ingår ej)

Antalet vandringar av längd $r$ mellan noderna $i$ och $j$ i grafen $G$ är $ij$-elementet i matrisen $A^r$, där $A$ är grafens grannmatris.

T.ex. $\left(\begin{matrix}0&1&1&1\\1&0&1&0\\1&1&0&1\\1&0&1&0\end{matrix}\right)\cdot\left(\begin{matrix}0&1&1&1\\1&0&1&0\\1&1&0&1\\1&0&1&0\end{matrix}\right)=\left(\begin{matrix}3&1&2&1\\1&2&1&2\\2&1&3&1\\1&2&1&2\end{matrix}\right)$

Eulerska grafer

En eulersk graf är en graf som har en krets (sluten väg) som passerar varje kant i grafen exakt en gång. En sådan väg kallas för en eulerväg.

Sats: En sammanhängande graf $G$ är eulersk $\iff$ varje nod har jämn valens.

Bevis:

$\implies)$ Om $G$ är eulersk kan vi följa kretsen som besöker varje kant exakt en gång. För varje nod som besöks finns två kanter (en "inkommande" och en "utgående"). Eftersom startnoden är densamma som slutnoden gäller det även för denna nod.

$\impliedby)$ Antag att alla noder har jämn valens. Låt $W$ vara den längsta vägen (varje kant högst en gång, men varje nod kan förekomma flera gånger). Eftersom vi inte kan förlänga $W$ så används alla kanter redan. Eftersom antalet kanter är jämnt måste start- och slutnoden vara densamma -- dvs. $W$ är en krets.

Antag nu att $W$ inte är en eulersk krets. Då finns det någon kant som inte används i $W$. Eftersom $G$ är sammanhängande finns det en sådan kant där (minst) den ena noden, förekommer i $W$. Vi kallar noden för $v_i$ och kanten $v_iu$. Vi kan då konstruera vägen $v_iv_{i+1}\dots v_lv_1v_2\dots v_iu$ som är en kant längre än $W$. Detta är en motsägelse (dvs. antagandet måste vara felaktigt). $W$ måste således trots allt vara eulersk.

Som en följdsats av ovanstående sats fås att

Sats: En sammanhängande graf $G=(V,E)$ har en eulerväg omm antalet udda noder är $0$ eller $2$.

Bevis:

$\implies)$ som ovan

$\impliedby)$ Om $G$ har $0$ udda noder är vi klara. Om $G$ har exakt två udda noder $x,y$ så vet vi att grafen $G'=(V\cup\{z\},\ E\cup\{xz,yz\})$ bara har jämna noder och alltså också har en eulerkrets. Bryter vi upp den eulerkretsen där den passerar $z$ (och tar bort $z$) får vi en eulerväg för $G$.

Hamilton

En hamiltoncykel är en $|V|$-cykel (dvs. en cykel genom alla noder).

En hamiltonstig är en stig genom alla noder.

Det är i allmänhet svårt att avgöra om en graf är hamiltonsk (dvs. har en hamiltoncykel). Det finns dock en del satser.

Sats: (Dirac 1952)

Varje graf $G=(V,E)$ med minst 3 noder, sådan att $\forall X\in V,\ \delta(x)\geq\frac{|V|}2$ har en hamiltoncykel.

Bevis: (se pdf)

Föreläsning 3

Träd

En graf är ett träd $T=(V,E)$ är sammanhängande och saknar cykler.

Sats 15.5: För ett träd $T=V(V,E)$ gäller det att $\forall x,y\in V$ finns en unik stig från $x$ till $y$.

Det gäller dessutom att, om en kant tas bort, återstår två träd.

För alla träd gäller dessutom att $|E|=|V|-1$.

Skog

En skog är en graf som saknar cykler. En sådan graf består av komponenter som är träd.

Ett träd $T=(V',E')$ är ett (upp)spännande träd till en graf $G=(V,E)$ om $V'=V$ och $E'\subseteq E$.

Dvs. $T$ är ett träd som är en delgraf till $G$ som omfattar samtliga noder. Varje sammanhändande graf har ett spännande träd.

Nodfärgning

En godkänd färgning av noder skall ge grannar olika färg.

Formellt är en (godkänd) nodfärgning av $G=(V,E)$ en funktion $c:V\to\mathbb Z_+$ så att $xy\in E\implies c(x)\neq c(y)$.

Det kromatiska talet $\chi(G)$ är det minsta antalet unika färger som $G$ kan nodfärgas med.

En girig algoritm

Det kromatiska talet $\chi(G)$ är inte alltid lätt att beräkna. En övre gräns kan fås genom en explicit färgning, men inte säkert att denna är optimal.

En girig algoritm för att approximera $\chi(G)$:

Ordna noderna i någon ordning $v_1,v_2,\dots,v_n$.
Välj, i tur och ordning, $c(v_1),c(v_2),\dots,c(v_n)$ som minsta möjliga positiva heltal, givet vilka tal som redan tilldelats grannarna.

Sats 15.7.1: För varje graf $G$ gäller att

$\chi(G)\leq\Delta(G)+1$, samt att

(om $G$ är sammanhängande och inte reguljär) $\chi(G)\leq\Delta(G)$.

$\Delta(G)$ betecknar maxvalensen i $G$.

Bevis: Den giriga algoritmen ovan kan i värsta fall tilldela $c(v_i)=\delta(v_i)+1$. Eftersom maxvalensen är $\Delta(G)$ kan det kromatiska talet inte överstiga $\Delta(G)+1$.

För att motivera (2) konstrurerar vi en ordning på noderna så att den giriga färgningen använder högst $\Delta(G)$ färger. Mer precist skapar vi en ordning så att ingen nod har mer än $\Delta(G)-1$ grannar före sig i ordningen.

Då $G$ inte är reguljär så finns en nod $x$ med $\delta(x)\lt\Delta(G)$. Låt $x$ bli sista noden $v_n$.

Före $x$ placerar vi nu alla grannar $N(x)$ till $x$ som $v_{n-\delta(x)},\dots,v_{n-1}$. Dessa kommer att ha $x$ efter sig och därför högsta $\Delta(G)-1$ grannar framför sig.

Vi fortsätter rekursivt och placerar alla grannar till dessa noder.

Eftersom grafen är sammanhängande kommer det alltid finnas en ännu icke utplacerad nod som har en utplacerad granne. Den giriga algoritmen kommer då att använda högst $\Delta(G)-1+1$ färger. $\square$

Det kromatiska polynomet

Det kromatiska polynomet $\chi_G(k)$ ger antalet sätt att nodfärga grafen $G=(V,E)$ med (högst) $k$ färger.

Vi vill kunna beräkna det kromatiska polynomet för alla grafer och skall ge en rekursion för detta.

Vi definierar först

$G-e$ som grafen $G$ med kanten $e$ borttagen.
$G/e$ som grafen $G$ med kanten $e$ kontraherad (de båda noderna slås samman).

Sats: (thm 5.3.6 i extramaterialet)

För varje graf $G=(V,E),\ e\in E$ gäller att

\[\chi_G(k)=\chi_{G-e}(k)-\chi_{G/e}(k)\]

Bevisskiss: Eftersom graferna i högerledet har strikt färre kanter än $G$ bestämmer detta, tillsammans med basen $\chi_{(V,\empty)}(k)=k^{|V|}$, funktionen för alla (ändliga) grafer $G$. Induktion över $|E|$.

Det kromatiska talet $\chi(G)=\min_{\chi_G(k)\neq0,\ k\in\mathbb N_0}k$

Föreläsning 4

Planära grafer

En plan graf är en "konkret graf" i ett plan, där noder motsvaras av punkter i planet och vars kanter är kurvor (i planet) som har gemensamma punkter endast i sina noder.

En planär graf är en graf som är isomorf med en plan graf.

Regioner

Kanterna i en plan graf delar in planet i sammanhängande regioner (eller delytor, områden, fasetter).

För en plan graf betecknar vi

antalet noder -- $n$
antalet kanter -- $k$
antalet regioner -- $r$
antalet komponenter -- $c$

Sats: För varje plan graf gäller att

\[n-k+r-c=1\]

Bevis: Induktion över antal kanter.

Basfall: $k=0$, vilket ger $n=c$ och $r=1$, dvs. sant.

Antagande: Antag sant för alla grafer med $k\leq m$ kanter.

Steg: Tag en graf $G$ med $k=m+1$ kanter och låt $e$ vara en godtycklig kant i denna graf. Vi tar nu bort denna kant och får en ny graf $G'=G-e$. Observera att antal noder är oförändrat, dvs. $n_{G'}=n_G$.

Fall 1) Båda sidor av $e$ tillhör samma region. Tar vi bort $e$ kommer den aktuella komponenten alltså delas i två. Antalet regioner förändras ej.

Vi har

$\(\begin{aligned}n_G&-k_G&+r_G&-c_G\\=n_{G'}&-(k_{G'}+1)&+r_{G'}&-(c_{G'}-1)\\=n_{G'}&-k_{G'}{\color{#f00}-1}&+r_{G'}&-c_{G'}{\color{#f00}+1}\\=n_{G'}&-k_{G'}&+r_{G'}&-c_{G'}&=\{\text{ind.ant.}\}=1\end{aligned}$\)

Fall 2) Olika regioner på olika sidor av $e$. Dessa regioner kommer alltså att sammanslås när $e$ tas bort. Samtidigt måste det finnas en annan väg mellan $e$:s noder -- antalet komponenter är alltså oförändrat.

Vi har

$\(\begin{aligned}n_G&-k_G&+r_G&-c_G\\=n_{G'}&-(k_{G'}+1)&+(r_{G'}+1)&-c_{G'}\\=n_{G'}&-k_{G'}{\color{#f00}-1}&+r_{G'}{\color{#f00}+1}&-c_{G'}\\=n_{G'}&-k_{G'}&+r_{G'}&-c_{G'}&=\{\text{ind.ant.}\}=1\end{aligned}$\)

\[\begin{align*}\tag*{\large\char"25A1}\end{align*}\]

Om grafen är sammanhängande ($c=1$) gäller speciellt (Eulers polyederformel) att

\[n-k+r=2\]

Följder av polyederformeln:

Följdsats 0: Antalet regioner $r$ är lika för alla inbäddningar av en planär graf.
Följdsats 1: För en planär graf gäller, om $k\geq 2$, att $3n\geq k+3(c+1)$.
- Om grafen är sammanhängande ($c=1$): $3n\geq k+6$
- Likhet gäller precis om alla regioner (även den obegränsade) har exakt tre kanter (för en, och därmed alla, plana versioner av grafen).
Följdsats 2: Om $G$ är planär, bipartit och $k\geq 2$ gäller att $2n\geq k+2(c+1)$.
- Om grafen är sammanhängande: $2n\geq k+4$
Följdsats 3: ...?

Wagners sats

Wagners sats:

Grafen $G$ är icke-planär $\iff$ en graf, isomorf med $K_5$ eller $K_{3,3}$, kan fås genom att utföra någon kombination av

ta bort en nod

ta bort en kant

kontrahera en kant

En graf som fås på detta vis kallas för en minor.

Fyrfärgssatsen

Fyrfärgssatsen: (manuellt räknat bevis ej känt)

För alla planära grafer gäller att $\chi(G)\leq 4$.

Sexfärgssatsen

$G\ \text{planär}\implies\chi(G)\leq 6$. Mycket lättare att bevisa.

Duala grafen

Givet en plan graf $G$ kan vi finnas dess duala graf $G^\perp$ s.a.

lägg till en $G^\perp$-nod i var och en av regionerna i $G$, samt
för varje kant i $G$, lägg till en $G^\perp$-kant (genom endast den aktuella $G$-kanten) mellan $G^\perp$-noderna i de angränsande $G$-regionerna (även om det är samma $G^\perp$-nod).

$G^\perp$ är alltid en plan graf, men den kan ha öglor och/eller multipla kanter (dvs. den är ej säkert en enkel graf). $G$ behöver inte heller vara en enkel graf.

För varje plan graf $G$ är dess duala graf $G^\perp$ sammanhängande.

Sats:

För varje plan graf $G$ gäller att

\[G\ \text{sammanhängande}\iff G\cong(G^\perp)^\perp\]

Regelbundna polyedrar

En regelbunden polyeder är en konvex polyeder vars sidytor är regelbundna $b$-hörningar och alla hörn är kongruenta & av grad $a$.

Vi skall nu visa att det finns exakt fem stycken: tetraedern, kuben, oktaedern, dodekaedern och ikosaedern -- de s.k. platonska kropparna.

Plana grafen för en regelbunden polyeder är dubbelt reguljär:

\[n-k+r=2\text{ samt }2k=an=br\]

Detta ger

\[2=\frac{2k}a-k+\frac{2k}b=(2a-ab+2b)\frac k{ab}\]

och därför måste $2a-ab+2b\gt 0$, dvs.

\[(a-2)(b-2)\lt 4\]

$\therefore$ visar det sig att det bara finns dessa fem möjligheter.

Föreläsning 5

Repetition

Plana grafer - graf ritad i planet
Planära grafer - graf som kan ritas i planet (eller på sfären)
Eulers polyederformel: $n-k+r-c=1$
Vi visade att vissa grafer inte är planära, särskilt $K_5$ och $K_{3,3}$.
Wagners sats (bevis ingår ej): G planär $\iff$ G inte har $K_5$ eller $K_{3,3}$ som minor
Fyrfärgssatsen: G planär $\implies\chi(G)\leq 4$ (bevis ingår/finns ej)

...

Bipartita grafer

En graf som kan färgas med två färger. I denna kurs räknas varje graf $G$ s.a. $\chi(G)\leq 2$ som bipartit.

En bipartit graf $G=(X\cup Y,\ E)$

$X\cap Y=\empty$, alla kanter mellan $X$ och $Y$ $\iff$ G är 2-(nod)färgbar

Sats 17.1: Valensernas summa för bipartita grafer

$G$ bipartit $\implies\sum_{x\in X}\delta(x)=\sum_{y\in Y}\delta(y)=|E|$

Sats 15.7.2: $G$ är bipartit $\iff$ det finns ingen udda cykel i $G$.

Bevis:

$\implies)$ I en cykel måste varannan nod tillhöra $X$ och varannan $Y$. Således måste antalet noder vara jämnt.

$\impliedby)$ Vi kan anta att $G$ är sammanhängande, eftersom vi kan färga varje komponent för sig. Antag att $G=(V,\ E)$ saknar udda cykler.

Vi väljer något $x\in V$. Definiera nu

\[V_j=\left\{v\in V\ |\ \text{kortaste stigen från }v\text{ till }x\text{ har längd }j\right\},\ j\geq 0\]

Observera: $V_0=\{x\}$, det vill säga avstånd 0 till $x$ har endast $x$ självt.

Påstående: Alla kanter i $G går mellan $V_{j-1}$ och $V_j$ (för alla $j$).

Bevis:

Inga kanter finns mellan $V_i$ och $V_j$, $|i-j|\geq 2$, ty detta skulle innebära en motsägelse.

Det finns inga kanter inom $V_j\forall j$, ty anta att $yz\in E$ och $y,z\in V_j$. Båda har stigar till $x$ av längd $j$. Låt $w$ vara första (från $V_j$ räknat) noden som är gemensam på stigarna. Dvs. $w\in V_i$ för något $i$. Det finns då en udda cykel av längd $2(j-i)+1$ med noderna $w,y,z$.

Nu kan vi färga noderna i $V_j$ med en färg för udda $j$ och en annan färg för jämna $j$. Tack vare påståendet är detta en godkänd färgning och $\chi(G)\leq 2$. $\square$

Kantfärgningar

En kantfärgning av grafen $G=(V,\ E)$ är en funktion $f:\ E\to\mathbb Z_+$ sådan att $|e_1\cap e_2|=1\implies f(e_1)\neq f(e_2)$, det vill säga kanter till samma nod har olika färg.

Kromatiskt index (namnet nämns inte i boken) $\chi'(G)$ för $G$ är det minsta antalet färger som $G$ kan kantfärgas med.

Lemma: Givet en graf $G=(V,\ E)$ gäller $\chi'(G)\geq\Delta(G)$

Bevis:

$\forall x\in V,\ \chi'(G)=\delta(x)\implies\chi(G)\geq\Delta(G)$

Sats: För bipartita grafer gäller alltid att $\chi'(G)=\Delta(G)$

Bevis: Induktion över $|E|$.

Basfall: $|E|=1\implies\Delta(G)=1\implies\chi'(G)=1$

Antagande: Antag att påståendet är sant för alla bipartita grafer med högst $m$ kanter.

Steg: Låt $G=(X\cup Y,\ E),\ |E|=m+1$.

Ta bort en kant $e=xy$ och låt denna graf $H=G-xy$.

Enligt antagandet gäller $\chi'(H)=\Delta(H)$.

$\Delta(H)=\Delta(G)$ eller $\Delta(G)-1$

Dvs. kanterna i $H$ kan färgas med $\Delta(G)$ färger.

$\delta_H(x)\lt\Delta(G)$, dvs. någon färg är ledig - säg $\alpha$.

$\delta_H(y)\lt\Delta(G)$, ........ - säg $\beta$.

Vi vill nu hitta en färg till $e=xy$.

Fall 1: Om $\alpha,\beta$ kan väljas lika så tar vi den färgen.

Fall 2: $\alpha\neq\beta$.

Definiera en alternerande stig $S:x,y_1,x_1,y_2,x_2,\dots$

$y_1$ är noden så att $xy_1$ har färgen $\beta$

Om någon kant vid $y_j$ är färgad med $\alpha$, så låter vi $x_j$ vara den noden sådan att $y_jx_j$ är färgad $\alpha$.

Om någon kant vid $x_j$ har färg $\beta$, så låter vi $y_{j+1}$ vara noden sådan att $x_jy_{j+1}$ har färg $\beta$.

De två tidigare punkterna upprepas så länge det går.

Slutligen byter vi färg på alla kanter i $S$.

Kanten $xy$ kan då ges färgen $\beta$.

Sats: (inte med i boken)

För alla grafer $G$ gäller att $\Delta(G)\leq\chi'(G)\leq\Delta(G)+1$

Latinska kvadrater

En latinsk kvadrat är en $n\ \times\ n$-matris där talen $1,\dots,n$ finns exakt en gång i varje rad och i varje kolumn.

T.ex. $\begin{matrix}1&2&4&3\\2&4&3&1\\4&3&1&2\\3&1&2&4\end{matrix}$

En möjlig bijektion mellan $n\ \times\ n$-latinska vadrater och kantfärgningar av $K_{n,n}$. Kanten mellan $r_i$ och $k_j$ färgas med siffran $s$ som står på position $(i,j)$.

Vi skall dock studera en annan bijektion, där kanten mellan $s$ och $k_j$ färgas med raden $r_i$ om $s$ står på position $(i,j)$ i matrisen.

Specifikt skall vi studera frågan om huruvida man kan fullfölja en delvis ifylld matris till en latinsk kvadrat. Låt en $m\ \times\ n$-latinsk rektangel vara en $m\ \times\ n$-matris där $1,\dots,n$ förekommer exakt en gång i varje rad och högst en gång i varje kolumn. Denna matris skall nu utvidgas till en kvadratisk matris.

Exempel:

$\begin{matrix}1&2&3&4&5\\5&1&4&2&3\\2&3&5&1&4\end{matrix}$

...

Sats: (thm 17.3.1)

En latinsk $m\ \times\ n$-rektangel ($m\lt n$) kan utvidgas till en latinsk $n\ \times\ n$-kvadrat.

Bevis: gicks ej igenom. ingår det?

Föreläsning 6

TODO

Föreläsning 7

I schemat: den 9 september 2025

Permutationer

En permutation är en bijektion $\pi:X\to X$, där vi ofta antar $X=\{1,2,\dots,n\}$ för något $n\in\mathbb Z_+$.

Låt $\pi(1)=4,\pi(2)=5,\pi(3)=2,\pi(4)=1,\pi(5)=3,\pi(6)=6$.

Tvåradersnotation: $\begin{bmatrix}1&2&3&4&5&6\\4&5&2&1&3&6\end{bmatrix}$
Enradersnotation: $4\ 5\ 2\ 1\ 3\ 6$
Cykelnotation: $(1\ 4)(2\ 5\ 3)(6)$ -- motsvarar en riktad graf med cykler

Mängden med alla permutationer av $\{1,2,\dots,n\}$ betecknas $S_n$.

Observera att det naturligt gäller att $|S_n|=n!$.

Sammansättning

Låt $\pi=\begin{bmatrix}1&2&3&4&5&6\\4&5&2&1&3&6\end{bmatrix},\ \sigma=\begin{bmatrix}1&2&3&4&5&6\\3&6&5&1&4&2\end{bmatrix}$

\[\pi\sigma=\pi(\sigma)=\begin{bmatrix}1&2&3&4&5&6\\2&6&3&4&1&5\end{bmatrix}\]

Fyra viktiga egenskaper för permutationer ($\pi,\sigma,\tau\in S_n$):

$\pi\sigma\in S_n$
$\pi(\sigma\tau)=(\pi\sigma)\tau$
Det existerar någon permutation $\text{id}\in S_n$ s.a. $\pi\ \text{id}=\text{id}\ \pi=\pi$ för alla $\pi$.
Det finns något $\pi^{-1}\in S_n$ s.a. $\pi\pi^{-1}=\pi^{-1}\pi=\text{id}$

Ordning

Ordningen, $o(\pi)=k$, av en permutation $\pi$ är det minsta $k\geq1$ så att $\pi^k=\text{id}$.

Kan enkelt utläsas från cykelformen som MGM av cykellängderna.

Permutationsmatriser

Permutationsmatrisen för $\pi\in S_n$ är en $n\times n$-matris $M_\pi$ med element

\[m_{ij}=\begin{cases}1&\text{om }\pi(j)=i\\0&\text{annars}\end{cases}\]

Det gäller att $M_{\pi\sigma}=M_\pi M_\sigma$, dvs. sammansättning motsvaras av matrismultiplikation.

Partitioner av heltal

En partition av $n\in N$ ges som

\[n=n_1+n_2+\cdots+n_k,\qquad n_1\geq n_2\geq\cdots\geq n_k\geq 1\]

Antalet partitioner betecknas $p(n)$, varav antalet i exakt $k$ delar ges av $p_k(n)$.

Exempel:

Låt $f_m(n)$ vara antalet partitioner med högst $m$ termer och $g_m(n)$ vara antalet partitioner med termer alla $\leq m$.

Det visar sig att $f_m(n)=g_m(n)$.

Cykeltyp

En permutations cykeltyp är den partition som ges av cykellängderna.

Permutationen $\pi=(1\ 2\ 7)(3\ 5)(4\ 11\ 8\ 6)(9\ 10)$ har cykeltyp

\[[2^2\ 3\ 4]\]

Sats:

Antalet permutationer av typ $[1^{c_1}\ 2^{c_2}\ \dots\ k^{c_k}]$ är

\[\frac{n!}{(1 ^{c_1}\cdot 2^{c_2}\cdots k^{c_k})\cdot (c_1!\cdots c_k!)}\]

Föreläsning 8

Konjugerade permutationer

Två permutationer $\alpha,\beta\in S_n$ är konjugerade om det finns en permutation $\sigma\in S_n$ sådan att $\beta=\sigma\alpha\sigma^{-1}$.

Detta definierar en ekvivalensrelation på $S_n$.

Sats:

$\alpha,\beta\in S_n$ är konjugerade omm de har samma cykeltyp.

Udda/jämna permutationer

En transposition är en permutation av typ $[1^{n-2}2]$, dvs.

\[\tau=(a\ b)\in S_n,\quad a\neq b\]

Varje permutation kan skrivas som en sammansättning av transpositioner. För en given permutation är antalet sammansatta transpositioner alltid jämnt eller alltid udda.

Definition: $\pi=\tau_r\cdots\tau_2\tau_1$ är en jämn permutation omm $r$ är jämnt -- annars en udda permutation.

Definition: Signum-funktionen för permutationer definieras

\[\text{sgn}(\pi)=\left(-1\right)^r=\begin{cases}1&\pi\text{ jämn}\\-1&\pi\text{ udda}\end{cases}\]

För en cykel av längd $j$ gäller

\[(x_1\ x_2\ \cdots\ x_j)=(x_1\ x_j)(x_1\ x_{j-1})\cdots(x_1\ x_3)(x_1\ x_2)\]

Dvs. en cykel är en jämn permutation omm den har udda längd.

Alla permutationer i en konjugatklass har samma tecken. Om $\pi$ är av typ $[1^{c_1}\ 2^{c_2}\ \cdots\ k^{c_k}]$ är

\[\text{sgn}(\pi)=\left(-1\right)^{n-c(\pi)}\]

En jämn permutation har jämnt antal cykler av jämn längd.

Sats 12.6.2:

I $S_n,\ n\geq 2$ är hälften av permutationerna jämna och hälften udda.

En permutations tecken är lika med permutationsmatrisens determinant:

\[\text{sgn}(\pi)=\det M_\pi\]

Föreläsning 9

I schemat: den 12 september 2025

Grupper

En grupp $(G,\ *)$ är en mängd $G$ tillsammans med en binär operation $*$ med

(slutenhet) $\forall x,y\in G$ gäller att $x*y\in G$,
(associativitet) $\forall x,y,z\in G$ gäller $(x*y)*z=x*(y*z)$,
(identitet) $\exists e\in G$ sådan att $e*x=x*e=x$, samt
(invers) $\forall x\in G$ finns $x'\in G$ sådan att $x'*x=x*x'=e$.

OBS! Vi kräver inte att $x*y=y*x$ för alla $x,y\in G$. En sådan grupp kallas för kommutativ eller abelsk.

Förenklad notation: $(\text a)\ x*y\to xy,\quad(\text b)\ e\to 1,\quad(\text c)\ x'\to x^{-1}$

Sats 20.3.1: Givet $x,y,z\in G$ gäller att

$x*y=x*z\implies y=z$

$y*x=z*x\implies y=z$

Sats 20.3.2: Givet $a,b\in G$ har ekvationen $a*x=b$ en unik lösning i $G$.

Följdsats:

$\forall a\in G,\ a*x=a$ har unik lösning $\implies$ identiteten $1$ är unik.

$\forall a\in G,\ a*x=1$ har unik lösning $\implies$ inversen $a'$ är unik.

Grupptabellen är en latinsk kvadrat (om gruppen är ändlig)

Ordning

Vi kan definiera heltalspotenser av gruppelement med rekursion

\[x^r:=\begin{cases}x&r=1\\x*x^{-1}&r\geq 2\end{cases},\qquad x^{-s}:=\begin{cases}x^{-1}&s=1\\x^{-1}x^{1-s}&s\geq 2\end{cases}\]

Ordningen, $o(g)$, för ett element $g\in G$ ges av

\[o(g)=\min\left[\left\{n\in\mathbb Z_+\ |\ g^n=1\right\}\cup\left\{\infty\right\}\right]\]

Sats 20.4: $g^s=1\iff o(g)\ |\ s$

Obs! $o(g)$ betecknar ordningen för ett element och skall ej förväxlas med $|G|$ som betecknar hela gruppens ordning.

Exempel: För gruppen $(\mathbb Z\setminus\left\{0\right\},\ \cdot)$, där $\cdot$ betecknar multiplikation (mod 7), är

\[o(5)=6\]

eftersom $5^6=(5*5)*(5*5)*(5*5)=(4*4)*4=2*4=1$.

Gruppisomorfi

Låt $(G_1,\ *),\ (G_2,\ \circ)$ vara två grupper, och $\beta:G_1\to G_2$ vara en bijektion.

$\beta$ är en isomorfi om det $\forall g,g'\in G_1$ gäller att

\[\beta(g*g')=\beta(g)\circ\beta(g')\]

Vi säger då att $G_1$ och $G_2$ är isomorfa, vilket betecknas $(G_1,\ *)\approx(G_2,\ \circ)$ eller $G_1\approx G_2$.

Isomorfi är en ekvivalensrelation på mängden av alla grupper.

Föreläsning 10

I schemat: den 16 september 2025

Cykliska grupper

En grupp $G$ är cyklisk om det, för något $x\in G$, gäller att varje $g\in G$ är $x^n$ för något $n\in\mathbb Z$.

Man säger då att $x$ genererar $G$, vilket betecknas $G=\langle x\rangle$.

Direkt produkt

Den direkta produkten av två grupper $A,B$ definieras som $(A\times B,\ *)$, där $(a_1,\ b_1)*(a_2,\ b_2)=(a_1a_2,\ b_1b_2)$.

Sats 20.6:

Om $m$ och $n$ är relativt prima, gäller att $C_{mn}\approx C_m\times C_n$

Bevis: se boken...

Enligt kinesiska restsatsen (nästa vecka) gäller, om $\text{sgd}(m_i,\ m_j)=1$ då $i\neq j$, att

\[C_{m_1\cdots m_k}\approx C_{m_1}\times\cdots\times C_{m_k}\]

$G_1$ och $G_2$ abelska $\implies G_1\times G_2$ abelsk

Inverterbara element i $\mathbb Z_m$

Kom ihåg (SF1671): Ett element $k\in\mathbb Z_m$ är inverterbart (har multiplikativ invers) $\iff\text{sgd}(k,m)=1$.

Låt $U(\mathbb Z_m)$ vara mängden av inverterbara element i $\mathbb Z_m$. Det gäller att $(U(\mathbb Z_m),\ \cdot)$ är en grupp för alla $m\geq 2$.

Exempel:

Låt elementen i $G_\square$ vara symmetriavbildningar för en kvadrat.

Grupp genereras av $\{x,\ r\}$, dvs. varje element kan skrivas som $x^ir^j$ där $i\in\{0,1\},\ j\in\{0,1,2,3\}$. Vi låter här $x$ beteckna en spegling och $r$ en 90-graders (moturs) rotation.

Delgrupper

$H$ är en delgrupp till $(G,\ *)$ om $H\subseteq G$ och $(H,\ *)$ är en grupp.

Ex 1. $\{i,r,r^2,r^3\}$ är en delgrupp till $G_\square$.
Ex 2. De jämna heltalen är en delgrupp till $(\mathbb Z,\ +)$

Sats 20.7:

Om $G$ är en grupp och $H\subseteq G$ icke-tom, gäller följande ekvivalens:

$H$ är en delgrupp till $G\iff\begin{cases}S1&x,y\in H\implies xy\in H\text{, och}\\S2&x\in H\implies x^{-1}\in H\end{cases}$

Om $H$ är ändlig räcker $S1$.

Om $G$ är en grupp är

\[\mathcal Z(G)=\{z\in G\ |\ zg=gz\text{ för alla }g\in G\}\]

en delgrupp till $G$. Denna delgrupp kallas för $G$:s centrum.

Varje $x\in G$ genererar en cyklisk delgrupp, $\langle x\rangle=\{x^i\ |\ i\in\mathbb Z\}$. Då är $o(x)=|\langle x\rangle|$.

Cayleygrafer, orientering

En cayleygraf för en grupp (egentligen för en framställning av gruppen med generatorer) beskriver gruppen fullständigt.

Grafen har ett hörn för varje element i gruppen och om gruppen genereras av $a,b,\dots$ (dvs. om varje $g\in G$ kan skrivas som en produkt av sådana och deras inverser) har den riktade kanter med olika mörkningar (färger), svarande mot $a,b,\dots$. En $a$-kant från hörn $g$ slutar i hörn $ag$ osv.

En grupp kan ha olika (icke-isomorfa) cayleygrafer med olika generatorer.

Föreläsning 11

Sidoklasser

Definition:

Om $H$ är en delgrupp till $G$ och $g\in G$, säger vi att

$gH=\{gh\ |\ h\in H\}$ är en vänstersidoklass till $H$ i $G$, och att $Hg=\{hg\ |\ h\in H\}$ är en högersidoklass.

\[|H|=|gH|=|Hg|\]

Observera att även både höger- och vänstersidoklasser $gH,Hg\leq G$.

Sats 20.8.1:

$H$ är en delgrupp till $G$. Vänstersidoklasserna till $H$ formar en mängdpartition av $G$. D.v.s. för $g_1\neq g_2\in G$ gäller att

\[g_1H=g_2H\quad\text{eller}\quad g_1H\cap g_2H=\empty\]

Bevis: se boken.

Samma gäller högersidoklasserna.

Lagranges sats

Sats 20.8.2:

Låt $G$ vara en ändlig grupp och $H$ en delgrupp till denna. Då gäller att

\[|H|\text{ delar }|G|\]

Bevis:

...

Antalet olika sidoklasser till $H$ i $G$ betecknas $|G:H|=\frac{|G|}{|H|}$ och kallas $H$:s index i $G$.

Följder av Lagranges sats

Sats 20.8.3:

Om $G$ är en ändlig grupp, $g\in G$ och $|G|=n$, gäller att

$o(g)\ |\ n$, och

$g^n=1$

Sats 20.8.4:

Låt $G$ vara en grupp och $|G|=p$ för något primtal $p$. Då gäller att $G\approx C_p$.

Alternerande gruppen $A_n$

Se bokens genomgång av delgrupper till $A_4$.

Normal delgrupp

"Avancerat ämne" -- kan förekomma endast i svårare tentauppgifter.

Föreläsning 12

Automorfier

Låt $\Gamma=(V,\ E)$ vara en graf med $V=\{1,2,\dots,n\}$.

En automorfi är en bijektion $\pi:V\to V$ s.a. $xy\in E\iff\pi(x)\pi(y)\in E$, det vill säga en isomorfi från grafen till sig själv.

Mängden av alla automorfier betecknas $\text{Aut}(\Gamma)$ och bildar en grupp med sammansättning av bijektioner som operation (se axiomen!).

Gruppverkan

För en grupp $(G,\ *)$ säger vi att $G$ verkar på en mängd $X$ om det

$\forall g\in G$ gäller att $g:X\to X$ är en bijektion,
$\forall g_1,g_2\in G,\ x\in X$ gäller att $(g_1*g_2)(x)=g_1(g_2(x))$, samt
$\forall x\in X$ gäller att $1_G(x)=x$

Bana

Om $G$ verkar på $X$ och $x\in X$ kallas

\[G_X=\{g(x)\ |\ g\in G\}\]

för banan och är en delmängd av $X$.

Banorna bildar en mängdpartition av $X$ ty relationen $x\sim y$ om $g(x)=y$ för något $g\in G$ är en ekvivalensrelation.

Stabilisatorn

Stabilisatorn för något $x\in X$ definieras som

\[G_x=\{g\in G\ |\ g(x)=x\}\]

och är en delgrupp till $G$.

Sats:

\[|G|=|G_X|\cdot|G_x|\]

För $g\in G$ definieras $g$:s fixpunktsmängd som

\[F(g)=\{x\in X\ |\ g(x)=x\}\]

(alternativ beteckning: $X_g$)

Sats: (Burnsides lemma)

Antalet banor $N$ då $G$ verkar på $X$ kan beräknas med

\[N=\frac1{|G|}\sum_{g\in G}\left|F(g)\right|\]

Föreläsning 13

Modulär aritmetik

Kongruens modulo $m$ betecknas $x\equiv y\ (\text{mod }m)$ eller $x\equiv_my$

Heltalen $\mathbb Z$ kan delas in i $m$ st klasser kongruenta tal:

\[\begin{aligned}&{\left\lbrack 0\right\rbrack}_m&&=\{\dots,\ &-2m+0,\ &&-m+0,\ &&0,\ &&m+0,\ &&2m+0,\ &\dots\}\\&{\left\lbrack 1\right\rbrack}_m&&=\{\dots,\ &-2m+1,\ &&-m+1,\ &&1,\ &&m+1,\ &&2m+1,\ &\dots\}\\&&&&&&\vdots\\&{\left\lbrack m-1\right\rbrack}_m&&=\{\dots,\ &-m-1,\ &&-1,\ &&m-1,\ &&2m+1,\ &&2m+1,\ &\dots\}\end{aligned}\]

För något $m\in\mathbb Z_+$ ges heltalen modulo $m$ av

\[\mathbb Z_m=\{{\left\lbrack 0\right\rbrack}_m,\ {\left\lbrack 1\right\rbrack}_m,\ \dots,\ {\left\lbrack m-1\right\rbrack}_m\}\]

Inverterbarhet

I modulär aritmetik innebär inverterbarhet för något $r\in\mathbb Z_m$, att det $\exists x\in\mathbb Z_m$ (s.k. invers) så att $rx=1$ i $\mathbb Z_m$.

Kinesiska restsatsen

Sats:

Låt $m_1,\ m_2,\ \dots,\ m_k$ vara positiva, inbördes relativt prima tal. Då har systemet av kongruenser (där alla $a_i\in\mathbb Z$)

\[\begin{cases}x&\equiv&a_1&(\text{mod }m_1)\\x&\equiv&a_2&(\text{mod }m_2)\\&&\vdots\\x&\equiv&a_k&(\text{mod }m_k)\end{cases}\]

exakt en lösning, och denna är unik modulo $m=m_1\cdots m_k$.

Föreläsning 14

Eulers $\phi$-funktion

\[\phi(n)=\left|\left\{x\in\{1,2,\dots,n\}\ |\ \text{sgd}(x,n)=1\right\}\right|\]

Sats 11.5.1:

Om $n\geq 2,\ n=p_1^{e_1}\cdots p_r^{e_r}$, där $p_1,\dots,p_r$ är olika primtal och alla $e_i\geq 1$, gäller att

\[\phi(n)=n\left(1-\frac1{p_1}\right)\cdots\left(1-\frac1{p_r}\right)\]

Av satsen ovan följer att $\phi$ är multiplikativ, dvs. att

\[\text{sgd}(m,n)=1\implies\phi(mn)=\phi(m)\phi(n)\]

Sats 13.3.2 (Eulers sats):

$a^{\phi(n)}\equiv 1\ \left(\text{mod }n\right)$ om $a,n$ relativt prima dvs. $\text{gcd}(a,n)=1$.

Bevis: (video)

Låt $S=\{x\in\{1,2,\dots,n\}\ |\ \text{sgd}(x,n)=1\}$ och låt $T=\{ax\ |\ x\in S\}$.

Eftersom varjt $s\in S$ är relativt prim $n$, och sedan talet $a$ också är relativt prim $n$, gäller att även varje $as\in T$ är relativt prim $n$.

Vi reducerar nu $T$ modulo $n$. Detta ger mängden $T'=\{ax\mod n\ |\ x\in S\}$.

Notera att inget $0\notin T'$, eftersom det skulle innebära att något $x\in S$ kongruent med $0$ (modulo $n$).

Vi har alltså för varje element $t'\in T'$:

Alla element är inkongruenta, modulo $n$

Alla är relativt prima $n$

$1\leq t'\leq n$

För varje element $t\in T$ är kongruent med exakt ett element $x\in S$.

Vi kan skriva detta som

\[\prod_{x\in S} x\equiv\prod_{x_in S}ax\ \left(\text{mod }n\right)\]

Eftersom alla $x\in S$ är relativt prima $n$, är också deras produkt det. Vi kan därför stryka dessa ur båda led och får slutligen

\[1\equiv a^{\phi(n)}\ \left(\text{mod }n\right)\]

Sats 10.3:

För alla positiva heltal $n$ gäller att $\sum_{d|n}\phi(d)=n$.

Bevis:

Observera att $\phi(d)$ är lika med antalet generatorer av den cykliska gruppen $C_d$.

Observera också att varje delgrupp till en (finit) cyklisk grupp $C_n$ har någon ordning $d\ |\ n$ (den s.k. fundamentala satsen för cykliska grupper).

Varje element i $C_n$ är generator åt precis en cyklisk delgrupp. Varje sådan delgrupp $C_d\subseteq C_n$ genereras av precis $\phi(d)$ element i $C_n$. Summan av antalet generatorer för varje cyklisk delgrupp är naturligen lika med totala antalet element (ordningen) $n$. $\square$

Möbiusfunktionen

\[\mu(d)=\begin{cases}1&d=1\\0&k^2\ |\ d,\ \text{något heltal }k\geq 2\\(-1)^r&d=p_1p_2\cdots p_r,\ \text{unika primtal}\end{cases}\]

Sats: $\phi(n)=\sum_{d|n}\left\lbrack\mu(d)\frac nd\right\rbrack$

Sats: $\sum_{d|n}\mu(d)=\delta(n)=\begin{cases}1&n=1\\0&n\geq 2,\ n\ \text{ett heltal}\end{cases}$

Bevis: (video)

Låt $n=p_1^{r_1}p_2^{r_2}\cdots p_m^{r_m}$ och varje delare $d=q_1^{s_1}q_2^{s_2}\cdots q_k^{s_k}$, där $p_i,q_j$ är primtal.

Observera att det, för de delare där något $s_i\gt 1$, gäller att $q_i^2\ |\ d$, dvs. $\mu(d)=0$ och vi är i dessa fall färdiga.

Vi antar nu istället att alla $s_i=1$ och får då

\[\begin{array}{rcccl}\sum_{d\ |\ n}\mu(d)&=&\mu(1)&+&\left\lbrack\mu(p_1)+\mu(p_2)+\cdots+\mu(p_k)\right\rbrack\\&&&+&\left\lbrack\mu(p_1p_2)+\mu(p_1p_3)+\cdots+\mu(p_{m-1}p_m)\right\rbrack\\&&&\vdots&\\&&&+&\mu(n)\\&&&=&{m\choose 0}-{m\choose 1}\ +\ {m\choose 2}\ -\ {m\choose 3}\ +\ \cdots\ +\left(-1\right)^m{m\choose}\\&&&=&\left(1+(-1)\right)^m\ =\ 0\end{array}\]

Möbius inversformel

Givet två funktioner $f,g:\mathbb N\to\mathbb C$ gäller att

\[{\color{#f44}f(n)=\sum_{d\ |\ n}g(d)}\iff{\color{#5d4}g(n)=\sum_{d\ |\ n}\left\lbrack\mu(d)\cdot f\left(\frac nd\right)\right\rbrack}\]

Bevis: (video)

$\implies)$ Antag $\forall n\in\mathbb N$ att $f(n)=\sum_{d\ |\ n}g(d)$

\[{\color{#5d4}\sum_{d\ |\ n}\mu(d)f\left(\frac nd\right)}=\sum_{dk=n}\mu(d)f(k)\\=\sum_{dk=n}\mu(d)\sum_{e\ |\ k}g(e)=\left\{\begin{matrix}\frac ke=l\iff k=el\\\iff del=n\end{matrix}\right\}\\=\sum_{del=n}\mu(d)g(e)=\sum_{em=n}g(e)\sum_{d\ |\ m}\mu(d)\\=\left\{\begin{matrix}\text{enl. sats ovan blir den inre}\\\text{summan }1\text{ när }m=1\text{, annars }0\end{matrix}\right\}=\sum_{e=n}g(e)={\color{#5d4}g(n)}\]

$\impliedby)$ Antag $\forall n\in\mathbb N$ att $g(n)=\sum_{d\ |\ n}\left\lbrack\mu(d)\cdot f\left(\frac nd\right)\right\rbrack$

\[{\color{#f44}\sum_{d\ |\ n}g(d)}=\sum_{d\ |\ n}\sum_{d'\ |\ d}\left\lbrack\mu(d')\cdot f\left(\frac d{d'}\right)\right\rbrack\\=\left\{\begin{matrix}\frac d{d'}=e\iff d=ed'\\\frac nd=k\iff n=ed'k\end{matrix}\right\}=\sum_{d'ek=n}\left\lbrack\mu(d')\cdot f(e)\right\rbrack\\=\sum_{ek'=n}\left\lbrack f(e)\sum_{d'\ |\ k'}\mu(d')\right\rbrack={\color{#f44}f(n)}\]

Föreläsning 15

Kroppar

En kropp $(F,\ +,\ \cdot)$ (eng. field) är en mängd $F$ och två operationer $+,\ \cdot$ s.a.

$(F,\ +)$, den additiva gruppen, är en kommutativ (abelsk) grupp med $0$ som identitet,
$(F\setminus\{0\},\ \cdot)$, den multiplikativa gruppen, är en kommutativ (abelsk) grupp, samt
$\cdot$ är distributiv m.a.p. $+$, det vill säga $a\cdot(b+c)=a\cdot b+a\cdot c$ för alla $a,b,c\in F$.

Exempel: $(\mathbb R,\ +,\ \cdot)$

Ringar

En ring $(R,\ +,\ \cdot)$ är en struktur för vilken

$(R,\ +)$ är en kommutativ (abelsk) grupp med $0$ som identitet,
$(R,\ \cdot)$ är sluten och associativ, med identitet 1, samt
$\cdot$ är distributiv m.a.p. $+$.

Exempel: $(\mathbb Z,\ +,\ \cdot)$

För en ring $R$ säger vi att $a\in R$ är inverterbar om det finns en multiplikativ invers $a^{-1}\in R$. De inverterbara elementen i $R$ betecknas $U(R)$.

Sats:

För en ring $(R,\ +,\ \cdot)$ är $(U(R),\ \cdot)$ en grupp.

Observera: Alla kroppar är ringar.

Polynomringar

$\mathbb Z\lbrack x\rbrack$ betecknar mängden av polynom med heltalskoefficienter

\[a(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n,\quad a_i\in\mathbb Z\]

$\mathbb Z\lbrack x\rbrack$ är en ring med addition och multiplikation. Den additiva identiteten är $0$ och den multiplikativa $1$.

På samma sätt är $R\lbrack x\rbrack$, där $R$ är en ring, mängden av alla polynom med koefficienter $a_i\in R$.

$R\lbrack x\rbrack$ är en ring med addition & multiplikation av polynom. Gradtalet, $\deg a(x)$ definieras som det största $n$ s.a. $a_n\neq 0$, alternativt $-\infty$.

Om $a(x),b(x)\in F\lbrack x\rbrack$, där $F$ är en kropp, gäller att

\[\deg(a(x)b(x))=\deg a(x)+\deg b(x)\]

Observera att $F\lbrack x\rbrack$ också är en ring.

Om $F$ är en ring, men inte en kropp, gäller inte säkert ovanstående likhet mellan produktens gradtal och summan av faktorernas, ex.vis om $F=\mathbb Z/4\mathbb Z$ (heltalen modulo 4).

Föreläsning 16

Polynomdivision

Sats 22.5: Om $a(x),b(x)\in F\lbrack x\rbrack,\ b(x)\neq 0$ finns entydigt bestämda $q(x),r(x)\in F\lbrack x\rbrack,\ \deg r(x)\lt\deg b(x)$ sådana att

\[a(x)=b(x)q(x)+r(x)\]

Bevis: TODO

Största gemensamma delare (SGD)

Definition:

Om det för $a(x),b(x)\in F\lbrack x\rbrack$ gäller att

$d(x)\ |\ a(x),\ d(x)\ |\ b(x)$, samt

$c(x)\ |\ a(x),\ c(x)\ |\ b(x)\implies c(x)\ |\ d(x)$

så kallas $d(x)$ en största gemensam delare.

Om dessutom polynomet $d(x)$ är moniskt (dvs. högstagradskoefficienten är $1$), kallas $d(x)$ för den (moniska) SGD till $a(x)$ och $b(x)$ och är entydig.

Sats 22.6: För $a(x),b(x)\in F\lbrack x\rbrack$, där $F$ är en kropp, existerar ett entydigt $d(x)=\text{sgd}(a(x),\ b(x))$, och

\[d(x)=\lambda(x)a(x)+\mu(x)b(x)\]

för några $\lambda(x),\mu(x)\in F\lbrack x\rbrack$.

$d(x)$ fås med Euklides algoritm:

\[\begin{aligned}a(x)=b(x)q_1(x)+r_1(x)\qquad&\deg r_1\lt\deg b\\b(x)=r_1(x)q_2(x)+r_2(x)\qquad&\deg r_2\lt\deg r_1\\\vdots\quad&\\r_{k-3}(x)=r_{k-2}(x)q_{k-1}(x)+r_{k-1}(x)\qquad&\deg r_{k-1}\lt\deg r_{k-2}\\ r_{k-2}(x)=r_{k-1}(x)q_k(x)\qquad&\end{aligned}\]

Då är $\text{sgd}(a(x),\ b(x))=u\cdot r_{k-1}(x)$, för något $u\in F\setminus\{0\}$.

Irreducibla polynom

För en kropp $F$ och ett polynom $f(x)\in F\lbrack x\rbrack$ säger vi att $f(x)$ är irreducibelt om $\deg f(x)\geq 1$ och polynomet inte kan skrivas på formen $f(x)=g(x)h(x)$ för två andra polynom $g,h\in F\lbrack x\rbrack$ och $\deg g,\deg h\geq 1$.

Sats:

Låt $F$ vara en kropp. Om ett polynom $r(x)\in F\lbrack x\rbrack$ är irreducibelt och $r(x)\ |\ s_1(x)\cdots s_k(x)$ så gäller att $r(x)\ |\ s_i(x)$ för något $i$.

Sats 22.7:

Låt $F$ vara en kropp. Om

\[F\lbrack x\rbrack\ni f(x)=g_1(x)\cdots g_r(x)=h_1(x)\cdots h_s(x)\]

där $g_i(x),h_j(x)$ irreducibla, gäller det att (1) $r=s$ samt att (2) $g_i(x)=u_ih_{\pi(i)}(x)$, för alla $i$ och där $u_i\in F\setminus\{0\}$, $\pi\in S_r$.

Sats 22.8.1 (faktorsatsen):

Låt $F$ vara en kropp, $f(x)\in F\lbrack x\rbrack$ och $\alpha\in F$. Då gäller ekvivalensen

\[(x-\alpha)\ |\ f(x)\quad\iff\quad f(\alpha)=0\ \text{i}\ F\]

Sats 22.8.2:

Låt $F$ vara en kropp, $f(x)\in F\lbrack x\rbrack$ och $\deg f(x)=n\geq 1$.

Då gäller att $f(x)=0$ har högst $n$ rötter i $F$.

Föreläsning 17

Ändliga kroppar

Om $F$ är en ändlig kropp är $F$:s karakteristik, ordningen för multiplikativ identitet under addition, $o_+(1)$. Karakteristiken är det minsta positiva heltalet $n$ s.a. $\sum_{i=1}^n1=0$ i $F$.

Sats: Karakteristiken är ett primtal $p$.

Bevis: Ett icke-primtal kan skrivas som en produkt $m_1m_2$, och om $m_1m_2=0$ gäller naturligt att $m_1=0$ eller $m_2=0$.

Sats 23.2:

Låt $F$ vara en ändlig kropp med karakteristik $p$. Då är den additiva gruppen $(F,\ +)\approx C_p\times\cdots\times C_p=\left(C_p\right)^r$ för något heltal $r\geq 1$. Speciellt är $|F|=p^r$.

Exempel: En kropp med 9 element. Ta $x^2+x+2\in\mathbb Z_3\lbrack x\rbrack$, vi "räknar $\left(\text{mod }{x^2+x+2}\right)$".

Formellt definieras detta som en ekvivalensrelation $\sim$ i $\mathbb Z_3\lbrack x\rbrack$:

\[a(x)\sim b(x)\iff\left(x^2+x+2\right)\ |\ \left(a(x)-b(x)\right)\]

Betecknas $\mathbb Z_3\lbrack x\rbrack/(x^2+x+2)$ och består av följande element:

\[\{\lbrack 0\rbrack,\ \lbrack 1\rbrack,\ \lbrack 2\rbrack,\ \lbrack x\rbrack,\ \lbrack x+1\rbrack,\ \lbrack x+2\rbrack,\ \lbrack 2x\rbrack,\ \lbrack 2x+1\rbrack,\ \lbrack 2x+2\rbrack\}\]

Med ord: Ringen (kroppen) av ekvivalensklasser i $\mathbb Z_3\lbrack x\rbrack$ modulo $x^2+x+2$. Varje ekvivalensklass representeras enligt konvention av det ingående polynom av lägst grad.

Antiexempel: $\mathbb Z_3\lbrack x\rbrack/(x^2+2)$ är inte en kropp, ty $\lbrack x+1\rbrack\lbrack x+2\rbrack=\lbrack x^2+2\rbrack=\lbrack 0\rbrack$ ger att $\lbrack x+1\rbrack$ saknar invers.

Förklaringen ligger i att $x^2+2$ är reducibelt i $\mathbb Z_3\lbrack x\rbrack$.

Sats:

Låt $p$ vara ett primtal och $k(x)$ ett polynom irreducibelt i $\mathbb Z_p\lbrack x\rbrack$ med $\deg k=r\geq 1$.

Då är $\mathbb Z_p\lbrack x\rbrack/k(x)$ en kropp med $p^r$ element.

Föreläsning 18

Ändliga kroppar, multiplikativa gruppen

Vårt exempel: $\mathbb Z_3\lbrack x\rbrack/(x^2+x+2)$

Sats 23.4:

Den multiplikativa gruppen för en ändlig kropp är cyklisk. Dvs. för $|F|=p^r$ gäller att $\left(F\setminus\{0\},\ \cdot\right)\approx C_{p^r-1}$.

Megasatsen

Sats: För varje ändlig kropp $F$ med karakteristik $p$ gäller att

\[\begin{align*}|F|=p^r&&&\text{något }r\geq 1\$F,\ +)\approx(C_p)^r&&&r\text{-dimensionellt vektorrum över }\mathbb Z_p\\(F\setminus\{0\},\ \cdot)\approx C_{p^r-1}&&&\text{multiplikativa gruppen är cyklisk}\end{align*}\]

För varje \(r\geq 1$ och primtal $p$ finns precis en kropp $F$ med $|F|=p^r$.

För att visa att det finns en kropp $F$ med $p^r$ element räcker det att visa att det existerar ett irreducibelt polynom av grad $r$ i $\mathbb Z_p\lbrack x\rbrack$. Beviset ingår ej i kursen.

Primitiva polynom och element

Ett element $f\in F$ kallas för ett primitivt element i $F$ om det genererar hela kroppens multiplikativa grupp, dvs. om

\[\langle f\rangle=(F\setminus\{0\},\ \cdot)\]

T.ex. är $\lbrack x\rbrack$ ett primitivt element i $\mathbb Z_3\lbrack x\rbrack/(x^2+x+2)$.

Ett primitivt irreducibelt polynom är ett $k(x)\in F\lbrack x\rbrack$ s.a. $\lbrack x\rbrack$ är ett primitivt element i $F\lbrack x\rbrack/k(x)$.

Exempel: Tag polynomet $k(x)=x^3+2x+1\in\mathbb Z_3\lbrack x\rbrack$ och ringen $R=\mathbb Z_3\lbrack x\rbrack/(k(x))$.

Avgör om $\lbrack x\rbrack$ är ett primitivt element i $R$.

Lösning:

$k(x)$ är irreducibelt, vilket innebär att $R$ är en kropp med $p^r=\left(o_+(1)\right)^{\deg k}=3^3=27$ element. Den multiplikativa gruppen har alltså $26$ element. Möjliga ordningar för elementen i $R^*=\left(R\setminus\{0\},\ \cdot\right)$ är därför $1,2,13,26$. Ett primitivt element bör alltså ha ordning $|R^*|=26$.

$\lbrack x^1\rbrack\neq\lbrack 1\rbrack\\\lbrack x^2\rbrack\neq\lbrack 1\rbrack\\\lbrack x^{13}\rbrack=\lbrack(x^3)^4\cdot x\rbrack=\lbrack(x+2)^4\cdot x\rbrack=\lbrack (x^2 + 2)\cdot x\rbrack=\lbrack 2\rbrack\neq\lbrack 1\rbrack\\\lbrack x^{26}\rbrack=\lbrack 2^2\rbrack=\lbrack 1\rbrack\ \color{#5e5}\textbf{OK}$

Svar: $\lbrack x\rbrack$ är ett primitivt element i $R$ eftersom $x$ genererar hela den multiplikativa gruppen.

Mer om kroppar

Om $k(x)$ är irreducibelt i $\mathbb Z_p\lbrack x\rbrack$ av grad $r$, så är $\mathbb Z_p\lbrack x\rbrack/(k(x))$ en kropp med $p^r$ element.

Vi definierar ett element $\alpha$ som uppfyller $k(\alpha)=0$.

Då kan vi se $\mathbb Z_p\lbrack x\rbrack/(k(x))$ som

\[\mathbb Z_p\lbrack\alpha\rbrack=\{a_{r-1}\alpha^{r-1}+\cdots+a_1\alpha+a_0\ |\ a_i\in\mathbb Z_p\}\]

ty $\alpha^r$ kan reduceras med $k(\alpha)=0$.

Samma idé som $\mathbb C=\mathbb R\lbrack i\rbrack$, där $i^2=-1$. Kan också skrivas $\mathbb C=\mathbb R\lbrack x\rbrack/(x^2+1)$.

Föreläsning 19

Kryptografi TODO

Föreläsning 20

Felrättande koder TODO

SF1688 Diskret matematik 6,0 hp

Föreläsning 1

Grafer

Isomorfi för grafer

Speciella grafer

Föreläsning 2

Delgrafer och vandringar

Sammanhängande grafer

Antal vandringar

Eulerska grafer

Hamilton

Föreläsning 3

Träd

Skog

Nodfärgning

En girig algoritm

Det kromatiska polynomet

Föreläsning 4

Planära grafer

Regioner

Wagners sats

Fyrfärgssatsen

Sexfärgssatsen

Duala grafen

Regelbundna polyedrar

Föreläsning 5

Repetition

Bipartita grafer

Kantfärgningar

Latinska kvadrater

Föreläsning 6

Föreläsning 7

Permutationer

Sammansättning

Ordning

Permutationsmatriser

Partitioner av heltal

Cykeltyp

Föreläsning 8

Konjugerade permutationer

Udda/jämna permutationer

Föreläsning 9

Grupper

Ordning

Gruppisomorfi

Föreläsning 10

Cykliska grupper

Direkt produkt

Inverterbara element i \(\mathbb Z_m\)

Delgrupper

Cayleygrafer, orientering

Föreläsning 11

Sidoklasser

Lagranges sats

Följder av Lagranges sats

Alternerande gruppen \(A_n\)

Normal delgrupp

Föreläsning 12

Automorfier

Gruppverkan

Bana

Stabilisatorn

Föreläsning 13

Modulär aritmetik

Inverterbarhet

Kinesiska restsatsen

Föreläsning 14

Eulers \(\phi\)-funktion

Möbiusfunktionen

Möbius inversformel

Föreläsning 15

Kroppar

Ringar

Polynomringar

Föreläsning 16

Polynomdivision

Största gemensamma delare (SGD)

Irreducibla polynom

Föreläsning 17

Ändliga kroppar