G. Nebe, M. Kirschmer

Gitter und Codes, WS 08/09

Lösung 9

Aufgabe 1. Sei b_{n} = a_{n} − a_{n−1} = −f(a_{n−1})/f′(a_{n−1}). Aus der Vorlesung wissen wir:

• v(f(a_{n})) ≥ 2v(b_{n}) > v(f(a_{n−1})) für alle n ∈ ℕ.

• v(f′(a_{n})) = v(f′(a_{n−1})) für alle n ∈ ℕ.

Jetzt zu den Abschätzungen.

(a) Wir führen Induktion nach n. Im Fall n = 0 ist v(f(a_{0})) > 2v(f′(a_{0})) ≥ v(f′(a_{0})) wie behauptet.

Für n ≥ 1 wird

v(f(a_{n})) ≥ 2v(b_{n}) = 2v(f(a_{n−1})) − 2v(f′(a_{n−1}))
≥ 2(2^{n−1} − 1)d − 2v(f′(a_{0}))
= (2^{n} − 1)d − (d + 2v(f′(a_{0})))
= (2^{n} − 1)d − v(f(a_{0})) .

(b) Für alle n ≥ 1 ist

v(a_{n} − a_{n+1}) = v(b_{n−1}) = v(f(a_{n})) − v(f′(a_{n}))
> v(f(a_{n−1})) − v(f′(a_{n−1}))
= v(b_{n−1}) = v(a_{n−1} − a_{n}) .

Also ist die Folge (v(a_{n} − a_{n+1}))_{n} monoton wachsend.

Für jedes k > n ist dann

v(a_{n} − a_{k}) = v(∑_{i=n}^{k−1}(a_{i} − a_{i+1})) = v(a_{n} − a_{n+1}) = v(b_{n+1}) = v(f(a_{n})) − v(f′(a_{n})) .

Insbesondere ist damit auch v(a_{n} − a) = v(f(a_{n})) − v(f′(a_{n})).

(c) Folgt aus (a) und (b), denn es ist

v(a_{n} − a) = v(f(a_{n})) − v(f′(a_{0})) ≥ (2^{n} − 1)d + \underbrace{v(f(a_{0}))}_{≥d} −v(f′(a_{0})) ≥ 2^{n}d − v(f′(a_{0})) .

Aufgabe 2.

(a) Wir betrachten f(X) mod 3. Es wird f(0) = −1, f(1) = 1 und f(−1) = −1. Also existieren keine Nullstellen modulo 3 und somit keine in ℤ_{3}.

(b) Wir betrachten f(X) mod 5. Es ist f(3) = (3)^{3} − 2 = 25 und f′(3) = 3(3)^{2} = 27. Also liftet die Nullstelle a_{0} = 3 ∈ 𝔽_{5} zu einer Nullstelle a ∈ ℤ_{5}. Es ist d := v_{5}(f(a_{0})) − 2v_{5}(f′(a_{0})) = 2. Nach Aufgabe 1c gilt damit v_{2}(a_{n} − a) ≥ 2^{n} · 2. Also müssen wir n = 2 wählen um eine Näherung 6. Ordnung zu erhalten:

Es wird a_{1} = 3− \frac{25}{27} = \frac{56}{27} und a_{2} = \frac{56}{27} − \frac{f(a_{1})}{f′(a_{1})} = \frac{56}{27} − \frac{136250}{19683} \frac{243}{3136} = \frac{195299}{127008}. Der Standardvertreter von a_{2} + 5^{6}ℤ_{5} in {0, 1, …, 5^{6} − 1} ist 5303.

Also liefert 5303 = 3 + 0 · 5 + 2 · 5^{2} + 2 · 5^{3} + 3 · 5^{4} + 1 · 5^{5} die ersten sechs Stellen von a in der Standarddarstellung.

Angenommen es existieren noch weitere Nullstellen von f in ℤ_{5}, so würde f über ℤ_{5} und somit über 𝔽_{5} in Linearfaktoren zerfallen. Über 𝔽_{5} ist aber f(X) = (X + 2)(X^{2} − 2X − 1) und der zweite Faktor ist bereits irreduzibel wie man durch Einsetzen aller Elemente aus 𝔽_{5} feststellt.

(c) Wir betrachten f(X) mod 3. Es wird f(0) = 0 und f(−1) = f(1) = 1. Die Nullstelle x = 0 kann nicht mit Hensel geliftet werden, da v_{3}(f(0)) = v_{3}(9) = 2 aber v_{3}(f′(0)) = v_{3}(f′(3)) = 1. Auch modulo 9 bringt uns nicht weiter, also betrachten wir die Nullstellen modulo 27. Es ist

f(0) ≡ f(3) ≡ f(9) ≡ f(12) ≡ f(18) ≡ f(21) ≡ −9 mod 27
f(6) ≡ f(15) ≡ f(24) ≡ 9 mod 27

Also existieren keine Nullstellen modulo 27ℤ_{3} und damit auch keine in ℤ_{3}.

(d) Bereits über ℤ ist f(X) = (X + 1)(X^{2} − X + 1). Also ist −1 ∈ ℤ_{7} eine Nullstelle. Das Polynom g(X) := X^{2} − X + 1 besitzt in 𝔽_{7} die Nullstellen −2 und 3.

Sei nun a_{0} = 3. Dann ist d := v_{7}(g(a_{0})) − 2v_{7}(g′(a_{0})) = v_{2}(7) + 2v_{2}(5) = 1. Also liftet a_{0} zu einer Nullstelle a ∈ ℤ_{7} und nach Aufgabe 1c liefert a_{3} die gesuchte Näherung. Es wird a_{1} = 8/5, a_{2} = 39/55 und a_{3} = −1504/1265. Der Standardvertreter von a_{3} + 7^{6}ℤ_{7} ist 34968.

Also liefert 34968 = 3 + 4 · 7 + 6 · 7^{2} + 3 · 7^{3} + 0 · 7^{4} + 2 · 7^{5} die ersten sechs Stellen von a in der Standarddarstellung.

Sei nun b_{0} = −2. Dann ist d := v_{7}(g(b_{0})) − 2v_{7}(g′(b_{0})) = v_{2}(7) + 2v_{2}(−5) = 1. Also liftet b_{0} zu einer Nullstelle b ∈ ℤ_{7} und nach Aufgabe 1c dürfen wir erneut nach der 3. Iteration abbrechen. Es wird b_{1} = −3/5, b_{2} = 16/55, b_{3} = 2769/1265. Der Standardvertreter von b_{3} +7^{6}ℤ_{7} ist 82682.

Also liefert 82682 = 5 + 2 · 7 + 0 · 7^{2} + 3 · 7^{3} + 6 · 7^{4} + 4 · 7^{5} die ersten sechs Stellen von b in der Standarddarstellung.

(e) Sei a_{0} = 1. Dann ist d := v_{3}(f(a_{0})) − 2v_{3}(f′(a_{0})) = v_{3}(18) − 2v_{3}(4) = 2. Also liftet a_{0} zu einer Nullstelle a ∈ ℤ_{3} und nach Aufgabe 1c dürfen wir nach der 2. Iteration abbrechen.

Es wird a_{1} = −7/2 und a_{2} = −362/115. Der Standardvertreter von a_{2} + 3^{6}ℤ_{7} ist 523.

Also liefert 523 = 1 + 0 · 3 + 1 · 3^{2} + 1 · 3^{3} + 0 · 3^{4} + 2 · 3^{5} die ersten sechs Stellen von a in der Standarddarstellung.

Sei b_{0} = 2. Dann ist d := v_{3}(f(b_{0})) + 2v_{3}(f′(b_{0})) = v_{3}(27) − v_{3}(15) = 3 − 2 = 1. Also liftet b_{0} zu einer Nullstelle b ∈ ℤ_{3} und nach Aufgabe 1c dürfen wir nach der 3. Iteration abbrechen.

Es wird b_{1} = 1/5, b_{2} = 353/10 und b_{3} = 14867174/634645. Der Standardvertreter von b_{3} +3^{6}ℤ_{7} ist 497.

Also liefert 497 = 2 + 0 · 3 + 1 · 3^{2} + 0 · 3^{3} + 0 · 3^{4} + 2 · 3^{5} die ersten sechs Stellen von b in der Standarddarstellung.

Das Polynom f(X) hat also mindestends zwei und damit sogar genau drei Nullstellen in ℚ_{3} bzw. ℤ_{3}. Wegen f(0) ≡_{3} 1 muß die dritte Nullstelle also ebenfalls kongruent zu ±1 modulo 3 sein. Wir betrachten das Polynom also modulo 9 und finden:

Sei c_{0} = 5. Dann ist d := v_{3}(f(c_{0})) + 2v_{3}(f′(c_{0})) = v_{3}(162) − 2v_{3}(84) = 4 − 2 = 2. Also liftet c_{0} zu einer Nullstelle c ∈ ℤ_{3} und nach Aufgabe 1c dürfen wir nach der 2. Iteration abbrechen.

Es ist c_{1} = 43/14 und c_{2} = 23042/15295. Der Standardvertreter von c_{2} + 3^{6}ℤ_{7} ist 437.

Also liefert 437 = 2 + 1 · 3 + 0 · 3^{2} + 1 · 3^{3} + 2 · 3^{4} + 1 · 3^{5} die ersten sechs Stellen von c in der Standarddarstellung.

Die drei Nullstellen unterscheiden sich bereits modulo 9, also sind sie verschieden.

Aufgabe 3. Klar ist, daß die gesuchten Gruppen elementar abelsche 2-Gruppen sind (sofern sie endlich sind).

Sei zunächst p ≠ 2. Ist x ∈ (ℤ_{p}^{∗})^{2}, so ist auch x + pℤ_{p}^{∗} ein Quadrat in ℤ_{p}^{∗}/pℤ_{p}^{∗} ≅ 𝔽_{p}^{∗}. Wir behaupten, daß auch die Umkehrung der Aussage gilt. Sei dazu x ∈ ℤ_{p}^{∗} so, daß es ein a_{0} ∈ ℤ_{p} gibt mit x ≡ a_{0}^{2} mod pℤ_{p}. Sicher ist dann a_{0} ∉ pℤ_{p}. Setzen wir f(X) := X^{2} − x, so ist also v_{p}(f(a_{0})) ≥ 1 und v_{p}(f′(a_{0})) = v_{p}(2a_{0}) = 0. Daher liftet a_{0} zu einer Nullstelle a ∈ ℤ_{p} von f. Damit ist a^{2} = x und a ∈ ℤ_{p}^{∗} wie behauptet. Wir haben somit ℤ_{p}^{∗}/(ℤ_{p}^{∗})^{2} ≅ 𝔽_{p}^{∗}/(𝔽_{p}^{∗})^{2} ≅ C_{2} gezeigt.

Sei nun p = 2. Wir setzen R = ℤ/8ℤ. Dann ist (x + 8ℤ)^{2} = 1 + 8ℤ für alle x ∈ {1, 3, 5, 7}. Also ist R^{∗}/(R^{∗})^{2} ≅ C_{2} × C_{2} erzeugt von (3 + 8ℤ)(R^{∗})^{2} und (5 + 8ℤ)(R^{∗})^{2}. Wieder ist klar, daß jedes x ∈ (ℤ_{p}^{∗})^{2} auch ein Quadrat modulo 8ℤ_{2} ist und wir behaupten, daß auch die Umkehrung gilt. Sei also x ∈ ℤ_{2}^{∗} so, daß es ein a_{0} ∈ ℤ_{2} gibt mit x ≡ a_{0}^{2} mod 8ℤ_{2}. Sicher ist dann a_{0} ∉ 2ℤ_{2}. Setzen wir f(X) := X^{2} − x, so ist also v_{2}(f(a_{0})) ≥ 3 und v_{p}(f′(a_{0})) = v_{p}(2a_{0}) = 1. Daher liftet a_{0} zu einer Nullstelle a ∈ ℤ_{2} von f. Damit ist a^{2} = x und a ∈ ℤ_{2}^{∗} wie behauptet. Also ist ℤ_{2}^{∗}/(ℤ_{2}^{∗})^{2} ≅ R^{∗}/(R^{∗})^{2} ≅ C_{2} × C_{2} und der kanonische Isomorphismus ℤ_{2}^{∗}/(ℤ_{2}^{∗})^{2} ≅ R^{∗}/(R^{∗})^{2} bildet die Erzeuger (3 + 8ℤ)(R^{∗})^{2} und (5 + 8ℤ)(R^{∗})^{2} von R^{∗}/(R^{∗})^{2} ab auf 3(ℤ_{2}^{∗})^{2} bzw. 5(ℤ_{2}^{∗})^{2}.

Jetzt zu ℚ_{p}^{∗}/(ℚ_{p}^{∗})^{2} mit p beliebig. Wegen v((ℚ_{p}^{∗})^{2}) = 2ℤ ist (ℚ_{p}^{∗})^{2}∩ℤ_{p}^{∗} = (ℤ_{p}^{∗})^{2}. Weiter ist p ∉ (ℚ_{p}^{∗})^{2}ℤ_{p}^{∗} aber p^{2} ∈ (ℚ_{p}^{∗})^{2}ℤ_{p}^{∗} und offensichtlich ist ⟨p, (ℚ_{p}^{∗})^{2}, ℤ_{p}^{∗}⟩ = ℚ_{p}^{∗}. Also haben wir folgende Situation:

[figure: •; ℚ_{p}^{∗}; ≅C_{2}; •; (ℚ_{p}^{∗})^{2}ℤ_{p}^{∗}; •; ℤ_{p}^{∗}; •; (ℚ_{p}^{∗})^{2}; •; (ℤ_{p}^{∗})^{2}; •; 1]

Also ist ℚ_{p}^{∗}/(ℚ_{p}^{∗})^{2} ≅ C_{2} × ℤ_{p}^{∗}/(ℤ_{p}^{∗})^{2} ≅ \begin{cases}C_{2} × C_{2} & falls p ≠ 2 \\ C_{2} × C_{2} × C_{2} & falls p = 2 \end{cases} erzeugt von p(ℚ_{p}^{∗})^{2} sowie den

(ℚ_{p}^{∗})^{2}-Nebenklassen von Vertretern von ℤ_{p}^{∗}/(ℤ_{p}^{∗})^{2}.

Aufgabe 4.

Lemma Sei R ein kommutativer Ring. Dann ist GL_{n}(R) = {x ∈ R^{n×n} | det(x) ∈ R^{∗}}. Beweis: Ist x ∈ GL_{n}(R) so existiert per Definition ein y ∈ R^{n×n} mit xy = I_{n}. Die Determinante ist multiplikativ, also 1 = det(I_{n}) = \underbrace{det(x)}_{∈R} \underbrace{det(y)}_{∈R}. Also ist det(x) ∈ R^{∗}.

Ist umgekehrt x ∈ R^{n×n} mit det(x) ∈ R^{∗}, so erfüllt die zu x adjunguierte Matrix y ∈ R^{n×n} die Identität xy = det(x)I_{n} also ist x ∈ GL_{n}(R).

Jetzt zur eigentlichen Aufgabe. Es ist

(E, b) regulär ⟺ b_{E} ist bijektiv
⟺ für alle a_{1}, …, a_{n} ∈ R existiert genau ein x ∈ E mit b(x, e_{i}) = a_{i} stets
⟺ für alle a ∈ R^{1×n} existiert genau ein y ∈ R^{1×n} mit yG = a
⟺ G ∈ GL_{n}(R)
⟺ det(G) ∈ R^{∗} .

Für ein ganzes Gitter L gilt also: L regulär ⟺ det(L) = 1. Aber für ein ganzes Gitter ist die letzte Bedingung äquivalent zu L = L^{#}.