G. Nebe, M. Künzer 20.03.2007

Diskrete Strukturen, SS 06

Lösung zur Vordiplomsnachklausur

Aufgabe 1

(1) Wir haben 5 · 4 · 3 = 60 Möglichkeiten.

(2) Es wird

((1, 2, 3, 4) ∘ (2, 3, 5))^{4} = ((1, 2, 4)(3, 5))^{4}
= (1, 2, 4)^{4} ∘ (3, 5)^{4}
= (1, 2, 4) ,

und dieses Element hat Ordnung 3.

(3) Die Anzahl der fixpunktfreien Permutationen auf der Menge {1, 2, …, 6} ergibt sich zu

6! · ∑_{i=0}^{6} \frac{(−1)^{i}}{i!} = 6! · (\frac{1}{0!} − \frac{1}{1!} + \frac{1}{2!} − \frac{1}{3!} + \frac{1}{4!} − \frac{1}{5!} + \frac{1}{6!}) = 265 .

(4) Jedes irreduzible Polynom in F_{2}[X] ist normiert. Die Anzahl der irreduziblen Polynome von Grad 12 in F_{2}[X]

ergibt sich zu

\frac{1}{12} ∑_{d|12} 2^{d}μ(12/d) = \frac{1}{12} (2^{2}μ(12/2) + 2^{4}μ(12/4) + 2^{6}μ(12/6) + 2^{12}μ(12/12))
= \frac{1}{12} (4 − 16 − 64 + 4096)
= 335 .

Hierbei beachten wir, daß der μ-Wert von Zahlen, in welchen eine Primzahl mehr als einfach als Faktor auftritt, wie etwa 4 oder 12, verschwindet.

Aufgabe 2 Wir erstellen einen Baum zur Berechnung von G · 1 und von Stab_{G}(1).

[figure: •; 1; a; b; •; 2; a; b; •; 3; a; b; ^{•^{1} a^{3} · 1 = 1, redundant}; •; 4; a; b; ^{•^{4} aba^{2} · 1 = ba^{2} · 1, Erzeuger a^{−2}b^{−1}aba^{2} = (2, 4, 3)}; ^{•^{2} b^{2}a^{2} · 1 = a · 1, Erzeuger a^{−1}b^{2}a^{2} = (2, 3, 4)}; ^{•^{3} ba · 1 = a^{2} · 1, Erzeuger a^{−2}ba = (2, 4, 3)}; •^{1} b · 1 = 1, Erzeuger b = (2, 3, 4)]

Somit ist G · 1 = {1, 2, 3, 4}, und |G · 2| = 4 (Antwort zu (1)). Ferner ist Stab_{G}(1) = ⟨b = (2, 3, 4)⟩. Direkt erkennen wir, daß Stab_{G}(1) · 2 = {2, 3, 4} und | Stab_{G}(1) · 2| = 3 (Antwort zu (2)). Insgesamt wird |G| = \frac{|G|}{| Stab_{G}(1)|} · | Stab_{G}(1)| = |G · 1| · | Stab_{G}(1)| = 4 · 3 = 12 (Antwort zu (3)).

Aufgabe 3

(1) Es ist F_{7^{f}}^{∗} ≃ C_{7^{f} −1}. Es enthält C_{7^{f} −1} genau dann eine primitive 20-te Einheitswurzel, wenn 20 ein Teiler von 7^{f} − 1 ist, d.h. wenn 7^{f} ≡_{20} 1. Wir müssen also die Ordnung von 7 als Element von (Z/20Z)^{∗} ermitteln. Wir rechnen

7^{2} = 49 ≡_{20} 9
7^{3} ≡_{20} 9 · 7 = 63 ≡_{20} 3
7^{4} ≡_{20} 3 · 7 = 21 ≡_{20} 1 .

Als Lösung ergibt sich somit f = 4.

(2) Das Element i + 1 hat Ordnung 8. Da F_{9} = ⟨i + 1⟩ ≃ C_{8}, ergibt sich

{x ∈ F_{9}^{∗} : ⟨x⟩ = F_{9}^{∗}} = {ι + 1, (ι + 1)^{3}, (ι + 1)^{5}, (ι + 1)^{7}} = {ι + 1, −ι + 1, −ι − 1, ι − 1} ,

wobei letztere Gleichheit unter Beachtung von (ι + 1)^{2} = −ι am einfachsten zu bestimmen ist.

Aufgabe 4

Die Inzidenzmatrix unseres Graphen ist (\begin{matrix}1 & 3 \\ 3 & 0 \end{matrix}). Der Eintrag an Position (2, 2) von A^{4} gibt die Anzahl der Kantenzüge

von 2 nach 2 der Länge 4. Da A^{4} = (A^{2})^{2} = (\begin{matrix}10 & 3 \\ 3 & 9 \end{matrix})^{2} = (\begin{matrix}∗ & ∗ \\ ∗ & 90 \end{matrix}), gibt es 90 solcher Kantenzüge.

Aufgabe 5

(1) Der Euklidsche Algorithmus gibt 56 · 1 − 5 · 11 = 1. Also ist z = 56 · 1 = 56 möglich.

(2) Der Euklidsche Algorithmus gibt 40 · 3 − 7 · 17 = 1. Also ist z = 40 · 3 = 120 möglich.

(3) Der Euklidsche Algorithmus gibt 35 · 3 − 8 · 13 = 1. Also ist z = 35 · 3 = 105 möglich.

(4) Beachte 5 · 7 · 8 = 280. Sei zunächst 2 · 56 + 1 · 120 + 4 · 105 = 652 gebildet. Es ist 652 ≡_{280} 92 = z.

Aufgabe 6

(1) Die Erzeugermatrix hat die Zeilenstufenform (\begin{matrix}1 & ω & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & ω^{2} \end{matrix} ) . Dieser entnehmen wir die Prüfmatrix

(\begin{matrix}ω & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & ω^{2} \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ) .

(2) Da in unserer Prüfmatrix aus (1) je zwei verschiedene Zeilen ein linear unabhängiges, aber die letzten drei Zeilen ein linear abhängiges Tupel bilden, ist der Minimalabstand gleich 3.

Aufgabe 7

(1) Durch Probieren erhalten wir die Nullstelle γ^{6}. Da f(X) ∈ F_{4}[X], ist mit γ^{6} auch (γ^{6})^{4} = γ^{24} = γ^{9} eine Nullstelle von f(X). Da deg f = 2, ist die Menge der Nullstellen von f(X) bereits gegeben durch {γ^{6}, γ^{9}} = {γ^{3} + γ^{2}, γ^{3} + γ}.

(2) Unter den Potenzen von γ^{3} sind die beiden aufeinanderfolgenden (γ^{3})^{2} und (γ^{3})^{3} Nullstellen von f(X). Der designierte Minimalabstand von X ergibt sich also zu 2 + 1 = 3.

(3) Eine Polynomdivision liefert das Prüfpolynom g(X) := (X^{5} − 1)/f(X) = X^{3} + ωX^{2} + ωX + 1.

Eine Prüfmatrix von C ist vermöge g(X) gegeben durch

(\begin{matrix}1 & 0 \\ ω & 1 \\ ω & ω \\ 1 & ω \\ 0 & 1 \end{matrix}) .

In dieser bilden je zwei Zeilen ein linear unabhängiges Tupel. Da die Matrix nur zwei Spalten hat, ist sogar jedes aus drei ihrer Zeilen bestehende Tupel linear abhängig. Dies gibt d(C) = 3.

(4) Z.B. die Gestalt der Prüfmatrix liefert 5 − 2 = 3 als Dimension von C. Für die Hammingschranke bestimmen

wir zunächst

V_{4}(5, 1) = (\begin{matrix}5 \\ 0 \end{matrix}) (4 − 1)^{0} + (\begin{matrix}5 \\ 1 \end{matrix}) (4 − 1)^{1} = 16 .

Somit wird die Hammingschranke zu

5 − log_{4} (V_{4}(5, 1)) = 5 − log_{4} 16 = 3 .

Ein Vergleich zeigt, daß die Dimension unseres Codes C die Hammingschranke genau erreicht.

Dies ist wegen der Antwort zu (5) auch nicht erstaunlich.

(5) Ja, C ist ein Hammingcode. Zu jeder der Geraden

⟨(^{1 0})⟩, ⟨(^{1 1})⟩, ⟨(^{1 ω})⟩, ⟨(^{1} ^{ω^{2}} )⟩, ⟨(^{0 1})⟩

in F_{4}^{1×2} gibt es in der in (3) gefundenen Prüfmatrix

(\begin{matrix}1 & 0 \\ ω & 1 \\ ω & ω \\ 1 & ω \\ 0 & 1 \end{matrix}) .

von C genau eine Zeile, welche in dieser Geraden liegt. Genauer, es liegen

(^{1 0}) ∈ ⟨(^{1 0})⟩, (^{ω ω}) ∈ ⟨(^{1 1})⟩, (^{1 ω}) ∈ ⟨(^{1 ω})⟩, (^{ω 1}) ∈ ⟨(^{1} ^{ω^{2}} )⟩, (^{0 1}) ∈ ⟨(^{0 1})⟩ .

Aufgabe 8 Die Aussage ist falsch. In der Tat liefert der Euklidsche Algorithmus

ggT (f(X), f′(X)) = ggT (X^{9} + X^{7} + X^{4} + X^{3} + X^{2} + X + 1, X^{8} + X^{6} + X^{2} + 1) = X^{4} + X^{2} + 1 ≠ 1 . Somit enthält f(X) einen irreduziblen Faktor mit Multiplizität größer 1.