G. Nebe, M. Kirschmer

Gitter und Codes, WS 08/09

Lösung 8

Aufgabe 1. Es ist v(1) = v(1 · 1) = 2v(1), also v(1) = 0 und damit 1 ∈ R_{v}. Da R_{v} ein Ring ist, folgt ℤ ⊆ R_{v}. Weil v per Definition surjektiv ist, existieren teilerfremde ganze Zahlen a, b mit b ≠ 0 und 1 = v(\frac{a}{b}) = v(a) − v(b). Insbesondere ist v(a) = 1 + v(b) ≥ 1.

Da a und b teilerfremd sind, gibt es r, s ∈ ℤ mit 1 = ra + sb. Es folgt

0 = v(1) = v(ra + sb) ≥ min{v(a) + v(r), v(b) + v(s)} ≥ 0 .

Wegen v(a) ≥ 1 und v(b) ≥ 0 muß also v(b) = v(s) = 0 gelten. Damit wird v(a) = 1. Ferner dürfen wir ohne Einschränkung annehmen, daß a positiv ist.

Sei nun a = ∏_{i=1}^{t} p_{i}^{e_{i}} die Faktorisierung von a in paarweise verschiedene Primfaktoren mit e_{i} ≠ 0 für alle 1 ≤ i ≤ t. Dann ist 1 = v(a) = ∑_{i=1}^{t} \underbrace{e_{i}}_{≥1} · \underbrace{v(p_{i})}_{≥0}. Daraus folgt, daß genau eine der Primzahlen p_{i}

mit 1 bewertet wird. Diese heiße p.

Sei nun q ≠ p eine weitere Primzahl. Wir behaupten v(q) = 0. Dazu gehen wir analog zu oben vor. Wieder gibt es r, s ∈ ℤ mit 1 = rp + sq. Es folgt

0 = v(1) = v(rp + sq) ≥ min{v(r) + 1, v(s) + v(q)} ≥ 0 .

Wegen v(r) ≥ 0 folgt v(s) = v(q) = 0 wie behauptet.

Also ist v(z) = max{k ≥ 0 | p^{k} teilt z} für jede ganze Zahl z ∈ ℤ. Ist nun x ∈ ℚ, so existieren e, u, w ∈ ℤ mit x = p^{e} · \frac{u}{w} und gcd(p, uw) = 1. Damit wird v(x) = v(p^{e}) + v(u) − v(w) = e + 0 − 0 = e. Damit ist v die p-adische Bewertung von Beispiel 7.9. und R_{v} die Komplettierung von ℤ an pℤ.

Aufgabe 2.

(a) Ist |x|_{v} ≠ |y|_{v}, so ist v(x) ≠ v(y) also v(x + y) = min{v(x), v(y)}. Damit ist |x + y|_{v} = max{|x|_{v}, |y|_{v}}.

Seien nun x, y, z ∈ K beliebig aber paarweise verschieden. Wir haben zu zeigen, daß mindestens zwei der Längen |x − y|_{v}, |x − z|_{v} und |y − z|_{v} gleich sind. Ist das von den drei Punkten aufgespannte Dreieck nicht gleichseitig, so ist ohne Einschränkung |x − y|_{v} > |y − z|_{v}. Es folgt |x − z|_{v} = |(x − y) − (y − z)|_{v} = max{|x − y|_{v}, |y − z|_{v}} = |x − y|_{v}. Das war zu zeigen.

(b) Ist (a_{n}) eine Cauchy-Folge, so existiert ein N ∈ ℕ mit |a_{n} − a_{m}|_{v} ≤ 1 für alle n, m ≥ N. Dann gilt für alle n ≥ N

|a_{n}|_{v} = |a_{n} − a_{N} + a_{N}|_{v} ≤ max{|a_{n} − a_{N}|_{v}, |a_{N}|_{v}} .

Wählen wir also r = max({1} ∪ {|a_{i}|_{v} | 1 ≤ i ≤ N}) so ist |a_{n}|_{v} ≤ r für alle n ∈ ℕ.

(c) Angenommen die Aussage ist falsch. D.h. zu jedem δ > 0 und N ∈ ℕ gibt es ein m ≥ N mit |a_{n}|_{v} ≤ δ.

Sei nun ε > 0 beliebig. Dann existiert ein N ∈ ℕ mit |a_{n} − a_{m}|_{v} ≤ ε für alle n, m ≥ N. Laut Annahme gibt es dann ein k ≥ N mit |a_{k}|_{v} ≤ ε. Es folgt |a_{n}|_{v} = |a_{n} − a_{k} + a_{k}|_{v} ≤ max{|a_{n} − a_{k}|_{v}, |a_{k}|_{v}} ≤ ε für alle n ≥ N. Also ist (a_{n})_{n} eine Nullfolge im Widerspruch zur Voraussetzung.

(d) Bezeichne X die Menge der Cauchy-Folgen. Dann enthält X die konstanten Folgen. Also insbesondere sind 1 und 0 in X. Seien nun (a_{n}) und (b_{n}) zwei Cauchy-Folgen.

Zu 1 ≥ ε > 0 existieren N ∈ ℕ mit |a_{n} − a_{m}|_{v} < ε und |b_{n} − b_{m}|_{v} < ε für alle n, m ≥ N. Sei nun (c_{n}) = (a_{n}) + (b_{n}) und (d_{n}) = (a_{n}) · (b_{n}) d.h. c_{n} = a_{n} + b_{n} und d_{n} = a_{n} · b_{n} für alle n ∈ ℕ.

Es ist |c_{n} − c_{m}|_{v} = |a_{n} + b_{n} − a_{m} − b_{m}|_{v} ≤ max{|a_{n} − a_{m}|_{v}, |b_{n} − b_{m}|_{v}} < ε für alle n, m ≥ N. Also ist (c_{n}) ∈ X.

Nach Teil (b) existiert ein r ∈ ℝ mit |a_{n}|_{v}, |b_{n}|_{v} ≤ r für alle n ∈ ℕ. Also ist

|d_{n} − d_{m}|_{v} = |a_{n} · b_{n} − a_{m} · b_{m}|_{v} = |a_{n} · (b_{n} − b_{m}) + b_{m} · (a_{n} − a_{m})|_{v}
≤ max{|a_{n}|_{v} · |b_{n} − b_{m}|_{v} + |b_{m}|_{v} · |a_{n} − a_{m}|_{v}} ≤ r · ε .

Dies zeigt (d_{n}) ∈ X. Damit ist X ein Teilring des Rings aller Folgen in K.

Bezeichne N die Menge aller Nullfolgen in K. Da N die Folge enthält welche konstant 0 ist, ist N nicht leer. Weiter ist klar, daß die Summe zweier Nullfolgen eine Nullfolge ist.

Ist (a_{n}) ∈ N und ε > 0 beliebig, so gibt es N ∈ ℕ mit |a_{n}|_{v} ≤ ε für alle n ≥ N. Es folgt |a_{n} − a_{m}|_{v} ≤ max{|a_{n}|_{v}, |a_{m}|_{v}} ≤ ε für alle n, m ≥ N. Also ist N ⊆ X. Ist zusätzlich (b_{n}) ∈ X, so gibt es nach Teil (b) ein r ∈ ℝ mit |a_{n}|_{v} ≤ r für alle n ∈ ℕ. Es folgt |a_{n}b_{n}|_{v} ≤ rε für alle n ≥ N. Damit ist (a_{n}) · (b_{n}) eine Nullfolge. Somit haben wir gezeigt, daß N ein Ideal in X ist.

Aufgabe 3. Bemerkung 1: Ist d ∈ ℤ teilerfremd zu p, so ist p ∈ (ℤ/dℤ)^{∗}. Bezeichne m die Ordnung von p in dieser Gruppe. Dann ist d ein Teiler von p^{m} − 1 also dk = p^{m} − 1 für ein k ∈ ℤ. Es folgt \frac{1}{d} = \frac{−k}{1−p^{m}} = −k ∑_{i=0}^{∞} p^{mi}.

Bemerkung 2: Ist x = ∑_{i=0}^{∞} a_{i}p^{i} mit 0 ≤ a_{i} ≤ p − 1 und a_{0} ≠ 0, so ist −x = ∑_{i=0}^{∞} b_{i}p^{i} wobei b_{0} = p − a_{0} und b_{i} = p − 1 − a_{i} sonst. (Beachte: Es ist 0 ≤ b_{j} ≤ p − 1 stets.) Beweis: Es ist ∑_{i=0}^{∞} b_{i}p^{i} = p − a_{0} + ∑_{i=1}^{∞}(p − 1 − a_{i})p^{i} = p − a_{0} + ∑_{i=1}^{∞}(p − 1)p^{i} − ∑_{i=1}^{∞} a_{i}p^{i} = 1 − ∑_{i=0}^{∞}(p − 1)p^{i} − ∑_{i=0}^{∞} a_{i}p^{i} = 1 − 1 − x = −x wie behauptet.

(a) Schreiben wir die Koeffizienten untereinander, so ergibt sich (wenn man links beginnt)

0 1 2 3 4 4
2 4 1 0 3 0
Übertrag 1 1
∑  2 0 4 3 2 0 1

Also ist a + b = 2 · 5^{−2} + 4 + 3 · 5 + 2 · 5^{2} + 5^{4}.

Genauso multiplizieren wir a und b:

2a  2 4 1 4 4 1
4a  4 3 3 3 2 3
a  1 2 3 4 4
3a  3 1 0 4 4 2
Übertrag  1 1 2 3 2 1 1 1
∑  2 3 1 0 0 3 4 0 0 3

Also ist ab = 2 · 5^{−3} + 3 · 5^{−2} + 5^{−1} + 3 · 5^{2} + 4 · 5^{3} + 3 · 5^{6}.

(b) Nach Bemerkung 2 ist −1 = ∑_{i=0}^{∞}(p − 1)p^{i}.

(c) Wenden wir die Bemerkungen 1 und 2 auf d = 3 und p = 7 an. Es ist dann m = 1 und 7 − 1 = 3 · 2. Also \frac{1}{3} = − ∑_{i=0}^{∞} 2 · 7^{i} = 5 + ∑_{i=1}^{∞} 4 · 7^{i}.

(d) In diesem Fall ist d = 3 und p = 5. Es wird m = 2 und 5^{2} − 1 = 3 · 8. Also

\frac{1}{3} = −8 ∑_{i=0}^{∞} 5^{2i} = − ∑_{i=0}^{∞}(3 + 1 · 5) · 5^{2i} = 2 + ∑_{i=0}^{∞}(3 + 1 · 5) · 5^{2i+1} .

(e) In diesem Fall ist d = 13 und p = 5. Es wird m = 4 und 5^{4} − 1 = 13 · 48. Also

\frac{1}{5 · 13} = −48 ∑_{i=0}^{∞} 5^{4i−1} = − ∑_{i=0}^{∞}(3+4·5+1·5^{2} +0·5^{3})·5^{4i−1} = 2+∑_{i=0}^{∞}(0+3·5+4·5^{2} +1·5^{3})·5^{4i} .

Aufgabe 4.

(a) Klar, denn jedes x ∈ ℕ_{0} hat bekanntlich eine Darstellung in der Basis p.

(b) Angenommen, es ist x = ∑_{i=k}^{∞} a_{i}p^{i} mit a_{i} = a_{i+ℓ} für alle i ≥ N. Subtrahiert man ∑_{i=k}^{N−1} a_{i}p^{i} ∈ ℕ_{0} von x und mulipliziert anschließend mit einer geeigneten p-Potenz, so darf man annehmen, daß x = ∑_{i=0}^{∞} a_{i}p^{i} mit a_{i} = a_{i+ℓ} für alle i ≥ 0. Dann folgt

x = ∑_{i=0}^{∞} \underbrace{(a_{0} + a_{1} · p + ⋯ + a_{ℓ−1}p^{ℓ−1})}_{=:b∈ℤ} ·p^{iℓ} = \frac{b}{1 − p^{ℓ}} ∈ ℚ .

Sei nun umgekehrt x ∈ ℚ. Ohne Einschränkung ist x > 0 wie Bemerkung 2 von oben zeigt. Wir schreiben dann x = p^{ℓ} · (a + \frac{b}{d}) mit ℓ ∈ ℤ, a, b ∈ ℕ_{0}, gcd(p, bd) = 1 und b < d. Es genügt dann zu zeigen, daß die p-adische Entwicklung von a + \frac{b}{d} periodisch ist, denn die Multiplikation mit p^{ℓ} verschiebt die Darstellung lediglich.

Wir behandeln zunächst den Fall a = 0. Dann ist nach Bemerkung 1 von oben: \frac{b}{d} = ∑_{i=0}^{∞} b·p^{mi} mit m = min{k > 0 | d teilt p^{k} − 1}. Insbesondere ist 0 ≤ b < d ≤ p^{m} − 1 < p^{m}. Daher ist die Darstelung von b zur Basis p von der Form b_{0} + b_{1}p^{1} + b_{2}p^{2} + ⋯ + b_{m−1}p^{m−1} mit 0 ≤ b_{i} ≤ p − 1 stets. Also hat \frac{b}{d} eine periodische Darstellung (vgl. Aufgabe 3), sagen wir \frac{b}{d} = ∑_{i=0}^{∞} b′_{i}p^{i} mit b′_{i} = b_{j} wobei i = rm + j mit 0 ≤ j ≤ m − 1 und r ∈ ℕ_{0}.

Sei nun a ∈ ℕ beliebig. Dann hat a nach Teil (1) eine endliche Darstellung sagen wir nur die ersten t Summanden seien ungleich 0. Nun addieren wir diese endliche Summe zur p-adischen Darstellung von \frac{b}{d} hinzu. Wir erhalten so a + \frac{b}{d} = ∑_{i=0}^{∞} c_{i}p^{i} mit 0 ≤ c_{i} ≤ p − 1 stets.

Klar ist: beim ersten Koeffizienten addieren wir zwei Zahlen ≤ p − 1, also kann der Übertrag maximal 1 sein. Beim zweiten Koeffizienten addieren wir wiederum zwei Zahlen ≤ p − 1 und maximal einen Übertrag von 1. Diese Zahl ist echt kleiner als 2p. Also tritt wiederum höchstens ein Übertrag von 1 auf, usw..

Es gibt also zwei Fälle:

1.) Es gibt einen Index i > t bei dem kein Übertrag stattfindet. Dann ist c_{j} = b′_{j} für alle j ≥ i und die p-adische Darstellung ∑_{i=0}^{∞} c_{i}p^{i} ist daher periodisch.

2.) Für jedes i > t findet ein Übertrag um 1 statt. Aber dann ist die Darstellung natürlich auch periodisch!

Hier ist noch ein zweiter Beweis nach A. Nehnes und N. Pawlitta für die Tatsache, daß jedes x ∈ ℚ eine periodische p-adische Entwicklung hat:

Sei x := \frac{a}{b} ∈ ℚ mit teilerfremden a, b ∈ ℤ und b > 0. Ohne Einschränkung ist x ∈ ℤ_{p} also p ∤ b.

Dann gibt es a_{i} ∈ {0, …, p−1} mit x = ∑_{i=0}^{∞} a_{i}p^{i}. Damit erfüllt a_{0} die Kongruenz a−ba_{0} ≡_{p} 0 und allgemein a − b ∑_{i=0}^{n−1} a_{i}p^{i} ≡_{p^{n}} 0.

Setzen wir c_{n} := (a − b ∑_{i=0}^{n−1} a_{i}p^{i})/p^{n} für alle n ≥ 0, so ist also

c_{n} ∈ ℤ und c_{n} ≡_{p} a_{n} für alle n ∈ ℕ_{0} .

D.h. c_{n} bestimmt a_{n} eindeutig. Weiter ist c_{n+1} = (c_{n} − ba_{n})/p stets. Damit bestimmen a_{n} und c_{n} auch c_{n+1} eindeutig. Zusammenfassend haben wir damit gezeigt daß c_{n} die die Zahl c_{n+1} bereits eindeutig festlegt! Insbesondere genügt es daher zu zeigen, daß die Folge (c_{n}) mindestens eine Wiederholung besitzt.

Bezeichne |.| den gewöhnlichen Betrag in ℚ, so gilt

|c_{n}| ≤ |a|/p^{n} + bp^{−n} ∑_{i=0}^{n−1} a_{i}p^{i} ≤ |a| + bp^{−n} ∑_{i=0}^{n−1}(p − 1)p^{i}
= |a| + b(p^{n} − 1)/p^{n} ≤ |a| + b .

Insbesondere nimmt die Folge (c_{n}) also nur endlich viele Werte an. Damit kommt es unweigerlich zu einer Wiederholung. Wie bereits gezeigt, führt dies zu einer Periode in (a_{n}).