G. Nebe, M. Kirschmer

Gitter und Codes, WS 08/09

Lösung 1

Aufgabe 1.

(a) Es sei B = (b_{1}, b_{2}) eine Basis von L mit G(B) = G. Weiter sei x = a_{1}b_{1} +a_{2}b_{2} ∈ L (also a_{i} ∈ ℤ).

• Für x ≠ 0 ist 0 < (x, x) = 2(a_{1}^{2} + a_{1}a_{2} + a_{2}^{2}) ∈ 2ℤ. Wegen (b_{1}, b_{1}) = 2 folgt min(L) = 2.

• Es ist x ∈ S(L) ⟺ (x, x) = min(L) = 2. Dies ist äquivalent zu a_{1}^{2} + a_{1}a_{2} + a_{2}^{2} − 1 = 0. Fassen wir dies als quadratische Gleichung in a_{1} auf, so hat diese genau dann eine Lösung, falls D := a_{2}^{2} − 4(a_{2}^{2} − 1) = 4 − 3a_{2}^{2} nicht negativ ist. Dies ist nur für a_{2} ∈ {−1, 0, 1} der Fall. Einsetzen dieser Werte für a_{2} liefert

S(L) = {±b_{1}, ±b_{2}, ±(b_{1} − b_{2})} .

• Ein Element φ ∈ End(V) identifizieren wir mit seiner Matrixdarstellung _{B}φ_{B} bezüglich der ℚ-Basis B von V. Dann ist φ ∈ Aut(L) genau dann wenn _{B}φ_{B} ∈ GL_{2}(ℤ) und (_{B}φ_{B})G(_{B}φ_{B})^{tr} = G gelten. Also ist φ ∈ Aut(L) genau dann, wenn b_{1}φ ∈ S(L), b_{2}φ ∈ S(L)\{±(b_{1}φ)} und (b_{1}φ, b_{2}φ) = 1 gelten. Explizites Nachrechnen liefert:

A := \{_{B}φ_{B} | φ ∈ Aut(L)\} = \{ \begin{matrix}( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ), & ( \begin{matrix}1 & 0 \\ 1 & −1 \end{matrix} ), & ( \begin{matrix}−1 & 0 \\ 0 & −1 \end{matrix} ), & ( \begin{matrix}−1 & 0 \\ −1 & 1 \end{matrix} ), \\ ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ), & ( \begin{matrix}0 & 1 \\ −1 & 1 \end{matrix} ), & ( \begin{matrix}0 & −1 \\ −1 & 0 \end{matrix} ), & ( \begin{matrix}0 & −1 \\ 1 & −1 \end{matrix} ), \\ ( \begin{matrix}1 & −1 \\ 1 & 0 \end{matrix} ), & ( \begin{matrix}1 & −1 \\ 0 & −1 \end{matrix} ), & ( \begin{matrix}−1 & 1 \\ −1 & 0 \end{matrix} ), & ( \begin{matrix}−1 & 1 \\ 0 & 1 \end{matrix} ) \end{matrix} \}

Damit ist | Aut(L)| = 12. Seien nun a := ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) und b := ( \begin{matrix}−1 & 1 \\ 0 & 1 \end{matrix} ) in A. Dann haben a und b Ordnung 2 und ab hat Ordnung 6. Also erzeugen die beiden Elemente a und b eine Untergruppe von A welche isomorph zu D_{12} ist. Also ist A = ⟨a, b⟩ ≅ D_{12}.

(b) Siehe (c).

(c) Es sei B = (b_{1}, …, b_{n}) eine Basis von L mit G(B) = G. Weiter sei x = ∑_{i=1}^{n} a_{i}b_{i} ∈ L.

• Für x ≠ 0 ist 0 < (x, x) = ∑_{i=1}^{n} a_{i}^{2} ∈ ℤ und (b_{1}, b_{1}) = 1. Also ist min(L) = 1.

• Es ist S(L) = {x ∈ L | (x, x) = 1} = {±b_{i} | 1 ≤ i ≤ n}.

• Jedes φ ∈ Aut(L) permutiert die Elemente in S(L). Da B eine Basis von L ist, legen die Bilder b_{1}φ, …, b_{n}φ ∈ S(L) den Automorphismus φ eindeutig fest. Insbesondere gilt b_{i}φ ∈ S(L) \ {±(b_{j}φ) | 1 ≤ j < i} stets. Damit ist | Aut(L)| nach oben beschränkt durch N := ∏_{i=1}^{n}(|S(L)| − 2(i − 1)) = ∏_{k=0}^{n−1}(2n − 2k) = 2^{n} · n! . Wir behaupten, es gilt | Aut(L)| = N. Dazu bestimmen wir einige Automorphismen, die eine Gruppen der Ordnung N erzeugen. Sei wieder A := {_{B}φ_{B} | φ ∈ Aut(L)}. Ist n = 1 so ist sicher A = ⟨(−1)⟩. Sei daher nun n ≥ 2 angenommen. Wir setzen X_{i} := Diag(1, …, 1, −1, 1, …, 1) ∈ GL_{n}(ℤ) mit −1 an der i-ten Stelle. Für σ ∈ S_{n} bezeichne Y_{σ} die zu σ gehörende Permutationsmatrix. Dann ist Y_{σ}GY_{σ}^{tr} = Y_{σ}Y_{σ}^{−1} = G. Also sind X := ⟨X_{1}, …, X_{n}⟩ und Y := ⟨Y_{σ} | σ ∈ S_{n}⟩ = ⟨Y_{(1,2)}, Y_{(1,...,n)}⟩ Untergruppen von A. Weiter ist X ein Normalteiler in ⟨X, Y ⟩ denn es gilt Y_{σ}^{−1}X_{i}Y_{σ} = Y_{σ^{−1}}X_{i}Y_{σ} = X_{σ(i)}. Da alle Elemente in X \ {I_{n}} einen negativen Eintrag haben, folgt X ∩ Y = {I_{n}}. Mit dem Homomorphiesatz folgt | ⟨X, Y ⟩ | = |X| · |Y | = 2^{n} · n! und somit A = ⟨X, Y ⟩. Insbesondere läßt sich A im Fall n ≥ 2 durch die zwei- bzw. dreielementige Menge {X_{1}, Y_{(1,2)}, Y_{(1,...,n)}} erzeugen.

Bemerkung: Es ist also Aut(L) isomorph zum semidirekten Produkt von C_{2} × ⋯ × C_{2} (n Kopien) und S_{n}, wobei die symmetrische Gruppe S_{n} auf den Kopien der C_{2} durch Permutation operiert. Dies wird auch Kranzprodukt (engl. wreath product) genannt.

Aufgabe 2. Dem Algorithmus entnehmen wir, daß

b_{i} = b′_{i} + ∑_{j=1}^{i−1} \frac{(b_{i}, b′_{j})}{(b′_{j}, b′_{j})} b′_{j} .

Wegen der Orthogonalität von (b′_{1}, …, b′_{i}) folgt, daß

(b_{i}, b_{i}) = (b′_{i}, b′_{i}) + ∑_{j=1}^{i−1} \frac{(b_{i}, b′_{j})^{2}}{(b′_{j}, b′_{j})^{2}} (b′_{j}, b′_{j}) ≥ (b′_{i}, b′_{i}) .

Aufgabe 3. Sei (b_{1}, b_{2}, b_{3}) eine Gitterbasis von L, bezüglich derer die angegebene Grammatrix G = (g_{i,j})_{i,j} :=

( \begin{matrix}3 & −1 & −1 \\ −1 & 3 & −1 \\ −1 & −1 & 3 \end{matrix} ) angenommen wird.

Die (im vorliegenden Fall ganzzahlige) Grammatrix G beschreibt die Einbettung L ⊆ L^{#} bezüglich der Basen (b_{1}, b_{2}, b_{3}) von L und (b_{1}^{∗}, b_{2}^{∗}, b_{3}^{∗}) von L^{#}. Denn es ist b_{j} = ∑_{i=1}^{3} g_{i,j}b_{i}^{∗} stets, wie eine Anwendung von (−, b_{k}) zeigt. Um L^{#}/L zu berechnen, bestimmen wir also die ℤ-linearen Elementarteiler von G; es ergibt sich (1, 4, 4). Somit ist L^{#}/L ≅ ℤ/1ℤ ⊕ ℤ/4ℤ ⊕ ℤ/4ℤ ≅ C_{4} × C_{4}.

Aufgabe 4. Sei B = (b_{1}, …, b_{n}). Für a ∈ ℝ schreiben wir ⌊a⌋ := max(ℤ ∩ (−∞, a]).

(i) Wir wollen zeigen, daß P(B) = {∑_{i=1}^{n} a_{i}b_{i} | a_{i} ∈ [0, 1]} eine abgeschlossene Teilmenge von (V, (−, =)) ist. Aus dem Gram-Schmidt-Verfahren (oder der Tatsache, daß je zwei Normen auf V äquivalent sind) folgt, daß (−, b_{j}^{∗}) : V → ℝ, ∑_{i=1}^{n} a_{i}b_{i} ↦ a_{j} stetig ist für alle 1 ≤ j ≤ n. Sei A_{j} das Urbild von [0, 1] ⊂ ℝ unter dieser Abbildung. Als Urbild einer abgeschlossenen Menge ist A_{j} abgeschlossen. Da ∑_{i=1}^{n} a_{i}b_{i} unter (−, b_{j}^{∗}) auf a_{j} abgebildet wird, ist P(B) = ⋂_{i=1}^{n} A_{j}, und somit als Schnitt abgeschlossener Mengen abgeschlossen. Bestimmen wir noch gleich den Rand ∂P(B) von P(B). Sei U_{j} das Urbild von (0, 1) ⊂ ℝ unter (−, b_{j}^{∗}) : V → ℝ. Als Urbild einer offenen Menge ist A_{j} offen. Sei P^{0}(B) := ⋂_{i=1}^{n} U_{j} ⊂ P(B). Es ist P^{0}(B) ⊂ V offen als Schnitt offener Mengen. Um zu zeigen, daß ∂P(B) = P(B) \ P^{0}(B), müssen wir zeigen, daß P^{0}(B) der offene Kern von P(B) ist, daß also jeder innere Punkt von P(B) bereits in P^{0}(B) liegt. In anderen Worten, wir müssen zeigen, daß für ein gegebenes Element x ∈ P(B) \ P^{0}(B) und ein gegebenes ε > 0 die offene Kugel B_{ε}(x) keine Teilmenge von P(B) ist. Sei x = ∑_{i=1}^{n} a_{i}b_{i} mit a_{i} ∈ [0, 1]. Es ist für ein i der Koeffizient a_{i} in {0, 1}. Sei ohne Einschränkung a_{1} = 0. Schreibe δ := ε|b_{1}|^{−1}/2 > 0. Sei x′ := −δb_{1} + ∑_{i=2}^{n} a_{i}b_{i} definiert. Es ist x′ ∉ P(B). Es ist |x − x′| = δ|b_{1}| = ε/2 < ε, und somit x′ ∈ B_{ε}(x). Also ist B_{ε}(x) ⊈ P(B). Ausgeschrieben wird also

∂P(B) = {∑_{i=1}^{n} a_{i}b_{i} : a_{i} ∈ [0, 1] für alle i und es gibt ein 1 ≤ j ≤ n mit a_{j} ∈ {0, 1}} .

(ii) Sei x ∈ V. Schreibe x = ∑_{i=1}^{n} a_{i}b_{i} mit a_{i} ∈ ℝ. Dann ist ℓ := ∑_{i=1}^{n}⌊a_{i}⌋b_{i} ∈ ⟨B⟩_{ℤ} = L und x − ℓ = ∑_{i=1}^{n} (a_{i} − ⌊a_{i}⌋) b_{i} ∈ P(B), da ja a_{i} − ⌊a_{i}⌋ ∈ [0, 1) stets.

(iii) Seien x = ∑_{i=1}^{n} a_{i}b_{i} und x′ = ∑_{i=1}^{n} a′_{i}b_{i} in P(B), und sei x − x′ in L. In anderen Worten, stets seien a_{i} und a′_{i} in [0, 1], und stets sei a_{i} − a′_{i} ∈ ℤ. Für ein festes i ist also

entweder a_{i} = a′_{i} oder (a′_{i} = 0 und a_{i} = 1) oder (a′_{i} = 1 und a_{i} = 0).

Wegen x ≠ x′ kann nun nicht für alle i der Fall a_{i} = a′_{i} eintreten. Somit gibt es ein i mit a_{i}, a′_{i} ∈ {0, 1}. Gemäß der Bestimmung von ∂P(B) aus (i) sind also x, x′ ∈ ∂P(B).

               http://www.math.rwth-aachen.de/~kirschme/gc