G. Nebe, M. Kirschmer

Gitter und Codes, WS 08/09

Lösung 11

Definition Sei C ≤ 𝔽_{ℓ}^{N} ein linearer Code.

• Für S ⊆ \underline{N} bezeichne π_{S}: 𝔽_{ℓ}^{N} → 𝔽_{ℓ}^{N} die Projektion auf die Stellen in S, d.h. π_{S}((x_{1}, …, x_{N})) =

(y_{1} …, y_{N}) mit y_{i} = \begin{cases}x_{i} & falls i ∈ S \\ 0 & falls i ∉ S \end{cases}.

• supp(C) := \{i ∈ \underline{N} | c_{i} ≠ 0 für ein (c_{1}, … c_{N}) ∈ C\} heißt der Support von C.

• Der Code C heißt zerlegbar, falls es eine Teilmenge ∅ ≠ S ⊊ supp(C) gibt so, daß π_{S}(C) und π_{supp(C)−S}(C) Teilcodes von C sind. (In diesem Fall ist C = π_{S}(C) ⊥ π_{supp(C)−S}(C) eine nichttriviale orthogonale Zerlegung von C.) Andernfalls heißt C unzerlegbar.

Lemma Zu jedem linearen Code C ≤ 𝔽_{ℓ}^{N} existiert eine (bis auf die Reihenfolge) eindeutig bestimmte Partition S = (S_{1}, …, S_{r}) von supp(C) so, daß π_{S_{i}}(C) ≤ C unzerlegbar ist für alle 1 ≤ i ≤ r. Weiter ist C =⊥_{i=1}^{r} π_{S_{i}}(C). Beweis: Existenz: Ist C unzerlegbar, so ist nichts zu zeigen. Andernfalls existiert ein ∅ ≠ S ⊊ supp(C) mit π_{S}(C), π_{supp(C)−S}(C) ≤ C. Dann ist C = π_{S}(C) ⊥ π_{supp(C)−S}(C). Jetzt iteriert man diese Zerlegung (beachte: Für T = S oder T = supp(C) − S ist supp(π_{T} (C)) = T). Dieses Verfahren endet, da 1 ≤ |S| < supp(C). Eindeutigkeit: Angenommen, T = (T_{1}, …, T_{t}) sei eine weitere solche Partition von supp(C). Zu 1 ≤ i ≤ s definieren wir I_{i} := {1 ≤ j ≤ t | S_{i} ∩ T_{j} ≠ ∅} weiter sei C_{i} = π_{S_{i}}(C). Sicher ist |I_{i}| ≥ 1. Für alle j ∈ I_{i} ist π_{S_{i}∩T_{j}}(C_{i}) = π_{S_{i}}(π_{T_{j}}(C)) ≤ π_{S_{i}}(C) = C_{i}. Wegen S_{i} − T_{j} = ⋃_{k∈I_{i}−{j}} S_{i} ∩ T_{k} folgt dann aber auch π_{supp(C_{i})−(S_{i}∩T_{j})}(C_{i}) = π_{S_{i}−T_{j}}(C_{i}) ≤ ⨁_{k∈I_{i}−{j}} π_{S_{i}∩T_{k}}(C_{i}) ≤ C_{i} stets. Da π_{S_{i}}(C) unzerlegbar ist, muß I_{j} = {i_{j}} einelementig sein. Also gilt S_{i} ⊆ T_{i_{j}} für alle i. Durch Vertauschen von S und T folgt daß auch jedes T_{j} in genau einem der S_{i} enthalten ist. Also unterscheiden sich S und T nur durch die Reihenfolge ihrer Teilmengen.

Korollar Sei C ≤ 𝔽_{ℓ}^{N} ein unzerlegbarer linearer Code mit supp(C) = \underline{N}. Ist D = \{(c_{1}, …, c_{k}) ∈ 𝔽_{ℓ}^{Nk} | c_{i} ∈ C\} für ein k ∈ ℕ, so ist

Aut(D) = \underbrace{\{D → D, (c_{1}, …, c_{k}) ↦ (φ_{1}(c_{σ(1)}), …, φ_{k}(c_{σ(k)})) | σ ∈ S_{k}, φ_{i} ∈ Aut(C)\}}_{=:Aut(C)≀S_{k}≅Aut(C)^{k}⋊S_{k}} .

Beweis: Die Inklusion ⊇ ist klar. Sei umgekehrt ψ ∈ Aut(D). Dann ist S := (S_{1}, …, S_{k}) mit S_{i} = {(i− 1)N +1, …, iN\} die eindeutig bestimmte Partition von supp(C) = \underline{N} aus dem obigen Lemma. Weiter ist (ψ(S_{1}), …, ψ(S_{k})) ebenfalls eine solche Zerlegung. Also existiert ein τ ∈ S_{k} so, daß ψ(C_{i}) = C_{τ(i)} stets, wobei C_{i} = π_{S_{i}}(D). Nach dem bereits gezeigten, existiert ein ϕ ∈ Aut(D) welches dieselbe Permutation τ auf den C_{i} induziert. Nachdem man ψ durch ϕ^{−1} ∘ ψ ersetzt hat, gilt also ψ(C_{i}) = C_{i} für alle i. Also ist ψ|_{C_{i}} ∈ Aut(C_{i}) ≅ Aut(C) stets. Das war zu zeigen.

Aufgabe 1.

Sei Mass(n, ℓ) := \frac{z}{n!} ∏_{j=1}^{n/2−1}(ℓ^{j} + 1) mit z = \begin{cases}1 & falls ℓ gerade \\ 2 & sonst \end{cases} das Maß der selbstdualen Codes in

𝔽_{ℓ}^{1×n}.

(a) Sei ⟨α⟩ = 𝔽_{ℓ}^{∗}. Wegen ℓ ≡_{4} 1 ist \frac{ℓ−1}{2} gerade, also ist −1 = α^{\frac{ℓ−1}{2}} ein Quadrat in 𝔽_{ℓ}^{∗}. Sei −1 = a^{2} mit a ∈ 𝔽_{ℓ}^{∗} und C = ⟨(1, a)⟩ < 𝔽_{ℓ}^{1×2}. Dann ist C selbstdual. Wegen (a, 1) ∉ C ist Aut(C) trivial und somit \frac{1}{| Aut(C)|} = 1 = Mass(2, ℓ). Damit folgt die Behauptung.

(b) Sei D der 𝔽_{5}-lineare Code mit Erzeugermatrix ( \begin{matrix}1 & 2 & 0 & 0 \\ 0 & 0 & 1 & 2 \end{matrix} ) (also der Wiederholungscode zu Teil (a)). Dann ist D selbstdual. Nach dem obigen Korollar ist Aut(D) = ⟨( 1, 3)(2, 4)⟩ ≅ C_{2}. Wegen \frac{1}{| Aut(D)|} = \frac{1}{2} = Mass(4, 5) folgt die Behauptung.

(c) Sei C der 𝔽_{3}-lineare Code mit Erzeugermatrix ( \begin{matrix}1 & 1 & 1 & 0 \\ 0 & 1 & 2 & 1 \end{matrix} ). Sicher ist C selbstdual. Der Code C besitzt nur einen Vektor mit 3 Einseinträgen, nämlich (1, 1, 1, 0). Daher ist Aut(C) ≤ ⟨(1, 2), (1, 2, 3)⟩. Die Codewörter mit 1 an der letzten Stelle sind (2, 0, 1, 1), (0, 1, 2, 1), (1, 2, 0, 1). Also ist Aut(C) ≤ ⟨(1, 2, 3)⟩. Sei φ = (1, 2, 3). Wegen

(0, 1, 2, 1)φ = (2, 0, 1, 1) = 2(1, 1, 1, 0) + (0, 1, 2, 1) ∈ C

ist Aut(C) = ⟨φ⟩ und somit \frac{1}{| Aut(C)|} = \frac{1}{3} = Mass(4, 3). Damit folgt die Behauptung.

(d) Sei D = {(c, d) | c, d ∈ C} wobei C den Code aus Teil (c) bezeichne. Sicher ist D selbstdual. Aus dem obigen Korollar ist Aut(D) ≅ C_{3} ≀ S_{2}. Wegen \frac{1}{| Aut(D)|} = \frac{1}{3^{2}·2} = \frac{1}{18} = Mass(8, 3) folgt die Behauptung.

Aufgabe 2.

(a) Wir behaupten |O_{2n}^{−}(𝔽_{ℓ})| = 2ℓ^{n(n−1)}(ℓ^{n} + 1) ∏_{i=1}^{n−1}(ℓ^{2i} − 1). Der Fall n = 1 wurde bereits in Blatt 11 Aufgabe 3b bewiesen. Sei nun n > 1 und (E, q) = H ⊥ V mit H ≅ ℍ und V ≅ ℍ^{n−1} ⊥ (𝔽_{ℓ^{2}}, N). Sei (h_{1}, h_{2}) eine Basis von H mit q(h_{1}) = q(h_{2}) = 0 und b_{q}(h_{1}, h_{2}) = 1. Für einen Teilraum F von E sei ferner S(F) = {x ∈ F − {0} | q(x) = 0}. Wir setzen U_{1} = Stab_{O(E,q)}(h_{1}) und U_{2} = Stab_{U_{1}}(h_{2}). Aus dem Bahnenlemma folgt dann |O_{2n}^{−}(𝔽_{ℓ})| = |O(E, q) · h_{1}| · |U_{1}| = |O(E, q) · h_{1}| · |U_{1} · h_{2}| · |U_{2}|. Wir bestimmen nun die drei Faktoren getrennt:

|U_{2}|: Sei φ ∈ U_{2}. Dann ist φ|_{H} = id_{H} und φ(V) ⊥ H. Also φ(V) = V. Damit ist τ: U_{2} → O(V), φ ↦ φ|_{H} wohldefiniert. Wegen φ|_{H} = id_{H} ist τ injektiv. Umgekehrt setzt jedes Element aus O(V) nach dem Fortsetzungssatz von Witt zu einem Element in O(E, q) fort. Also ist τ auch surjektiv und damit |U_{2}| = |O(V)| = |O_{2(n−1)}^{−}(𝔽_{ℓ})|.

|U_{1} · h_{2}|: Nach dem Wittschen Fortsetzungssatz ist U_{1} · h_{2} = {x ∈ E | q(x) = 0 und b_{q}(h_{1}, x) = 1}. Sei nun x := ah_{1} + bh_{2} + v mit a, b ∈ 𝔽_{ℓ} und v ∈ V. Dann gilt also

x ∈ U_{1} · h_{2} ⟺ b_{q}(x, h_{1}) = 1 und q(x) = 0
⟺ b = 1 und ab + q(v) = 0
⟺ (a, b) = (−q(v), 1)
Also ist |U_{1} · h_{2}| = |V | = ℓ^{2(n−1)}.

|O(E, q) · h_{1}|: Jedes Element in S(E) erzeugt einen scharf primitiven Teilaum von E. Nach dem Wittschen Fortsetzungssatz folgt daher wiederum S(E) = O(E, q) · h_{1}. Sei nun x := ah_{1} + bh_{2} + v ∈ S(E) mit a, b ∈ 𝔽_{ℓ} und v ∈ V. Wegen 0 = q(x) = ab + q(v) ist S(E) die Vereinigung der folgenden drei disjukten Mengen:

X_{1} = {λh_{i} | i ∈ {1, 2}, λ ∈ 𝔽_{ℓ}^{∗}}
X_{2} = {ah_{1} + bh_{2} + v | v ∈ S(V), a, b ∈ 𝔽_{ℓ}, ab = 0}
X_{3} = {ah_{1} + bh_{2} + v | v ∈ V, q(v) ≠ 0, a, b ∈ 𝔽_{ℓ}, ab = −q(v)}

Also ist

|S(E)| = |X_{1}| + |X_{2}| + |X_{3}|
= 2(ℓ − 1) + (2ℓ − 1) · |S(V)| + (|V | − |S(V)| − 1) · (ℓ − 1)
= ℓ − 1 + |S(V)| · ℓ + (ℓ − 1)ℓ^{2n−2} .

Für k ≥ 1 sei a_{k} = |S((𝔽_{ℓ^{2}}, N) ⊥ ℍ^{k−1})| und wir setzen x_{k} = a_{k} − ℓ^{2k−1} + 1. Wegen |S(V)| = a_{k−1} folgt aus der soeben gezeigten Identität die Rekursionsgleichung x_{k} = ℓx_{k−1}. Da (𝔽_{ℓ^{2}}, N) anisotrop ist, ist a_{1} = 0 also x_{1} = 1 − ℓ. Damit folgt

|S(E)| = a_{n} = x_{n} + ℓ^{2n−1} − 1 = ℓ^{n−1}(1 − ℓ) + ℓ^{2n−1} − 1 = (ℓ^{n} + 1)(ℓ^{n−1} − 1) .

Setzen wir nun alles zusammen, so folgt wie behauptet

|O_{2n}^{−}(𝔽_{ℓ})| = (ℓ^{n} + 1)(ℓ^{n−1} − 1) · ℓ^{2(n−1)} · |O_{2(n−1)}^{−}(𝔽_{ℓ})|

= (ℓ^{n} + 1)(ℓ^{n−1} − 1) · ℓ^{2(n−1)} · 2ℓ^{(n−1)(n−2)}(ℓ^{n−1} + 1) ∏_{i=1}^{n−2}(ℓ^{2i} − 1)

= 2ℓ^{n(n−1)}(ℓ^{n} + 1) ∏_{i=1}^{n−1}(ℓ^{2i} − 1)

(b) Wir behaupten |O_{2n+1}(𝔽_{ℓ})| = zℓ^{n^{2}} ∏_{i=1}^{n−1}(ℓ^{2i} − 1) mit z = 1 falls ℓ gerade und z = 2 sonst.

Sei (E, q) ≅ [1] ⊥ ℍ^{n}. Wieder führen wir eine Induktion nach n. Im Fall n = 0 besitzt jedes e ∈ E nur zwei mögliche Bilder unter O(E, q) nämlich e und −e. Also ist O(E, q) = {±id_{E}}.

Sei nun n ≥ 1. Wieder schreiben wir (E, q) = H ⊥ V mit H ≅ ℍ und V ≅ [1] ⊥ ℍ^{n−1}. Sei (h_{1}, h_{2}) eine Basis von H mit q(h_{1}) = q(h_{2}) = 0 und b_{q}(h_{1}, h_{2}) = 1. Für einen Teilraum F von E sei ferner S(F) = {x ∈ F − {0} | q(x) = 0}.

Wir setzen U_{1} = Stab_{O(E,q)}(h_{1}) und U_{2} = Stab_{U_{1}}(h_{2}). Dann folgt wiederum |O_{2n+1}(𝔽_{ℓ})| = |O(E, q) · h_{1}| · |U_{1} · h_{2}| · |U_{2}| mit |U_{2}| = |O_{2n−1}(𝔽_{ℓ})| und |U_{1} · h_{1}| = |V | = ℓ^{2n−1}. Es verbleibt daher |O(E, q) · h_{1}| = |S(E)| zu bestimmen.

Wie bereits zuvor ist |S(E)| = ℓ−1+|S(V)|·ℓ+(ℓ−1)ℓ^{2n−2}. Für k ≥ 0 sei a_{k} = |S([1] ⊥ ℍ^{k−1})| und x_{k} = a_{k} − ℓ^{2k−1} + 1. Dann gilt wiederum x_{n} = ℓx_{n−1} aber im Gegensatz zu Teil (a) ist nun a_{0} = S([1]) = 0 und somit x_{0} = 0. Also ist x_{k} = 0 für alle k ∈ ℕ. Damit wird |S(E)| = a_{n} = ℓ^{2n} − 1.

Setzen wir nun alles zusammen, so folgt wie behauptet:

|O_{2n+1}(𝔽_{ℓ})| = (ℓ^{2n} − 1) · ℓ^{2n−1} · |O_{2n−1}(𝔽_{ℓ})|

= (ℓ^{2n} − 1) · ℓ^{2n−1} · zℓ^{(n−1)^{2}} ∏_{i=1}^{n−2}(ℓ^{2i} − 1)

= zℓ^{n^{2}} ∏_{i=1}^{n−1}(ℓ^{2i} − 1)

Aufgabe 3.

(a) Wir führen Induktion nach s. In den Fällen s ∈ {0, 1} ist nichts zu zeigen. Sei nun s ≥ 2.

Im Fall V_{s} ∈ ⋃_{i=1}^{s−1} V_{i} folgt aus der Induktionsvoraussetzung bereits

⋃_{i=1}^{s} V_{i} = ⋃_{i=1}^{s−1} V_{i} ≠ V .

Im Fall V_{1} ≤ V_{s} folgt ebenfalls aus der Induktionsvoraussetzung

⋃_{i=1}^{s} V_{i} = ⋃_{i=2}^{s} V_{i} ≠ V .

Also dürfen wir annehmen, daß es ein v ∈ V_{s} −⋃_{i=1}^{s−1} V_{i} und ein w ∈ V_{1} −V_{s} gibt. Wir behaupten nun, daß es für jedes 1 ≤ i ≤ s höchstens ein λ_{i} ∈ K gibt mit w + λ_{i}v ∈ V_{i}.

Beweis: Angenommen es ist λ ∈ K mit w + λv ∈ V_{s}. Dann folgt w = (w + λv) − λv ∈ V_{s} was der Wahl von w widerspricht. Also existiert kein solcher Skalar λ.

Angenommmen, es gibt λ, μ ∈ K mit w + λv, w + μv ∈ V_{i} für ein i ≤ s − 1. Dann ist V_{i} ∋ (w + λv) − (w + μv) = (λ − μ)v. Wegen v ∉ V_{i} folgt λ = μ. Damit ist die Behauptung bewiesen.

Also ist |{λ ∈ K | w+λv ∈ ⋃_{i=1}^{s} V_{i}}| ≤ s < |K|. Daher existiert ein λ ∈ K mit w+λv ∉ ⋃_{i=1}^{s} V_{i}.

(Hinweis: Wir haben sogar |{λ ∈ K | w + λv ∈ ⋃_{i=1}^{s} V_{i}}| ≤ s − 1 gezeigt. D.h. Teil (a) ist auch richtig im Fall s = |K| < ∞.)

(b) Sei U = ⟨V − ⋃_{i=1}^{s} V_{i}⟩. Es genügt zu zeigen, daß V_{j} ∈ U für alle 1 ≤ j ≤ s. Sei dazu w ∈ V_{j}. Nach (a) existiert ein v ∈ V −⋃_{i=1}^{s} V_{i}. Wie in Teil (a) folgt, daß es für jedes 1 ≤ i ≤ s höchstens ein λ_{i} ∈ K mit w+λ_{i}v ∈ V_{i} gibt. Wegen s < |K| existiert daher ein λ ∈ K mit w+λv ∉ ⋃_{i=1}^{s} V_{i}. Also ist w + λv ∈ U und somit auch w = (w + λv) − λv ∈ U.