G. Nebe, M. Kirschmer

Gitter und Codes, WS 08/09

Lösung 4

Aufgabe 1. Es sei (b_{1}, …, b_{4}) eine Orthogonalbasis von ℝ^{1×4} mit (b_{i}, b_{i}) = \frac{1}{3}. Weiter seien M := ⟨b_{1}, …, b_{4}⟩_{ℤ} und π: M → C, ∑_{i=1}^{4} a_{i}b_{i} ↦ (ā_{1}, …, ā_{4}). Wir setzen x := b_{1} + b_{2} − b_{3} und y := b_{2} + b_{3} + b_{4}. Dann ist ⟨π(x), π(y)⟩_{𝔽_{3}} = C und es gilt ker(π) = 3M. Daher ist L_{C} = π^{−1}(C) = ⟨x, y, 3M⟩_{ℤ}. Eine Basis von L_{C} ist damit z.B. gegeben durch B := (x, y, 3b_{3}, 3b_{4}).

Nun ist G(B) = ( \begin{matrix}1 & 0 & −1 & 0 \\ 0 & 1 & 1 & 1 \\ −1 & 1 & 3 & 0 \\ 0 & 1 & 0 & 3 \end{matrix} ). D.h. bezüglich der Basis (x, y, x − y + 3b_{3}, 3b_{4} − y) ergibt sich die

Grammatrix ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & −1 \\ 0 & 0 & −1 & 2 \end{matrix} ). Daher ergibts sich bezüglich Basis (x, y, x − y + 3b_{3}, x − 2y + 3b_{3} + 3b_{4})

von L_{C} die GramMatrix I_{4}. Also ist L_{C} isometrisch zum Standardgitter und damit ist min(L_{C}) = 1.

Aufgabe 2 Nach dem Elementarteilersatz existiert eine Basis B = (b_{1}, …, b_{n}) von L und ganze Zahlen a_{1}, …, a_{n} so, daß B′ := (a_{1}b_{1}, …, a_{n}b_{n}) eine Basis von L′ ist. Also ist

G(B′) = Diag(a_{1}, …, a_{n}) · G(B) · Diag(a_{1}, …, a_{n}) .

Bilden wir auf beiden Seiten die Determinanten, so erhalten wir det(L′) = det(L) · ∏_{i=1}^{n} a_{i}^{2}. Wegen [L : L′] = |L/L′| = |ℤ/a_{1}ℤ × ⋯ × ℤ/a_{n}ℤ| = ∏_{i=1}^{n} a_{i} folgt daraus die Behauptung.

Aufgabe 3. Eine Prüfmatrix von H(𝔽_{2}, 3) ist z.B. gegeben durch

P := ( \begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} ) .

Eine Erzeugermatrix ist dann z.B. (in Stufenform)

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

Also bilden die Zeilen von

T := ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 2 \end{matrix} )

eine Basis B′ von L_{H(𝔽_{2},3)} bezüglich B. Die Grammatrix G := G(B′) ist dann \frac{1}{2}T T^{tr}. Also bilden die Zeilen von G^{−1} · T = 2T^{-tr} eine Basis von L_{H(𝔽_{2},3)}^{#} = L_{H(𝔽_{2},3)^{⊥}} bezüglich B.

Sei nun S := ( \begin{matrix}0 & 0 & 0 & 0 & 0 & −2 & 0 \\ −1 & 0 & 1 & −1 & 0 & 1 & 0 \\ 1 & 0 & −1 & 0 & −1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & −2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & −1 & −1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & −2 \end{matrix} ) wie im Hinweis. Wegen S · (2T^{-tr})^{−1} = S · \frac{1}{2}T^{tr} ∈ GL_{7}(ℤ)

(nachrechnen) bilden daher auch die Zeilen von S eine Basis B′′ von L_{H(𝔽_{2},3)^{⊥}}. Als letzten Schritt überprüft man nun, daß G(B′′) = \frac{1}{2}SS^{tr} die Gestalt aus Bem. 1.16 besitzt.

Aufgabe 4.

(a) Wir zeigen zunächst:

Lemma: Sei K ein endlicher Körper oder ein Körper der Charakteristik 0. Dann ist f′ ≠ 0 für jedes irreduzible Polynom f ∈ K[X] mit deg(f) > 0.

Beweis: Sei p die Charakteristik von K. Im Fall p = 0 ist nichts zu zeigen. Sei nun K endlich. Weiter sei f′ = 0 angenommen. Dann existiert ein Polynom g(X) = ∑_{i=0}^{n} a_{i}X^{i} ∈ K[X] mit f(X) = g(X^{p}). Es ist K = {x^{p} | x ∈ K}, da der Frobeniusmonomorphismus auf endlichen Körpern bijektiv ist. Also ist a_{i} = b_{i}^{p} für geeignete b_{i} ∈ K. Damit wird g(X^{p}) = ∑_{i=1}^{n} b_{i}^{p}X^{pi} = h(X)^{p} mit h(X) = ∑_{i=0}^{n} b_{i}X^{i}. Dann aber ist f(X) = g(X^{p}) = h(X)^{p} reduzibel.

Nun zur eigentlichen Aufgabe:

Sei f = cf_{1} · · · · · f_{s} mit c ∈ K und f_{i} ∈ K[X] \ K irreduzibel und normiert. Angenommen die f_{i} sind nicht paarweise verschieden, sagen wir f_{1} = f_{2}. Dann ist f = f_{1}^{2} · h mit h = c · ∏_{i≥3} f_{i} und f′ = 2f_{1}h + f_{1}^{2}h′. Also ist f_{1} ein nichtkonstantes Polynom welches f und f′ teilt.

Seien umgekehrt alle f_{i} paarweise verschieden. Dann ist f = gcd(f, f′)·g für g ∈ K[X] geeignet. Da die Zerlegung in normierte irreduzible Faktoren eindeutig ist, folgt gcd(f, f′) ist das Produkt einiger f_{i}. Angenommen f_{i} teilt f′, so setze g_{i} := ∏_{j≠i} f_{j}. Dann wird f′ = f′_{i}g_{i} + f_{i}g′_{i} aber nicht von f′ geteilt, denn nach Voraussetzung teilt f_{i} weder g_{i} noch f′_{i}. (Beachte: Es ist f′_{i} ≠ 0 nach obigem Lemma.) Also wird f′ von keinem der f_{i} geteilt. Daher ist gcd(f, f′) konstant.

(b) Sei q = p^{e} und f = X^{N}−1. Ist gcd(N, q) ≠ 1 so gilt p | N. Also ist gcd(f, f′) = gcd(f, NX^{N−1}) = gcd(f, 0) = f nicht konstant. Ist gcd(N, q) ≠ 1, so ist gcd(f, NX^{N−1}) = 1, denn es ist X^{N} − 1 = (NX^{N−1})(N^{−1}X) − 1. Die Behauptung folgt nun mit Teil (a).

(c) Es faktorisiert X^{4} − 1 ∈ 𝔽_{7}[X] in die irreduziblen Faktoren X − 1, X + 1 und X^{2} + 1. Der letzte Faktor ist irreduzibel da er vom Grad ≤ 3 ist und keine Nullstelle in 𝔽_{7} besitzt.

Es ergeben sich also die folgenden 8 Prüfpolynome:

g_{1} := 1  g_{2} := X + 1
g_{3} := X − 1  g_{4} := X^{2} + 1
g_{5} := (X + 1)(X − 1) = X^{2} − 1  g_{6} := (X + 1)(X^{2} + 1) = X^{3} + X^{2} + X + 1
g_{7} := (X − 1)(X^{2} + 1) = X^{3} − X^{2} + X − 1 g_{8} := X^{4} − 1

Bezeichne G_{i} die zu g_{i} gehörende Erzeugermatrix, so erhalten wir:

G_{1} = I_{4}  G_{8} = 0 ∈ 𝔽_{7}^{0×4}
G_{2} = ( \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{matrix} )  G_{3} = ( \begin{matrix}1 & −1 & 0 & 0 \\ 0 & 1 & −1 & 0 \\ 0 & 0 & 1 & −1 \end{matrix} )
G_{4} = ( \begin{matrix}1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{matrix} )  G_{5} = ( \begin{matrix}1 & 0 & −1 & 0 \\ 0 & 1 & 0 & −1 \end{matrix} )
G_{6} = (^{1} ^{1} ^{1} ^{1} )  G_{7} = (^{1 −1 1 −1} )

Ferner ist g_{i}g_{9−i} = X^{4} − 1 für alle 1 ≤ i ≤ 8. Also ist g_{9−i} ein Prüfpolynom von g_{i}. Bezeichne H_{i} die zugehörige Prüfmatrix, so erhalten wir:

H_{1} = 0 ∈ 𝔽_{7}^{4×0}  H_{8} = I_{4}
H_{2} = (^{1} ^{1} ^{1} ^{1} )^{tr}  H_{3} = (^{−1 1 −1 1} )^{tr}
H_{4} = ( \begin{matrix}−1 & 0 & 1 & 0 \\ 0 & −1 & 0 & 1 \end{matrix} )^{tr}  H_{5} = ( \begin{matrix}1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{matrix} )^{tr}
H_{6} = ( \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{matrix} )^{tr}  H_{7} = ( \begin{matrix}−1 & 1 & 0 & 0 \\ 0 & −1 & 1 & 0 \\ 0 & 0 & −1 & 1 \end{matrix} )^{tr}