G. Nebe, M. Kirschmer

Gitter und Codes, WS 08/09

Lösung 7

Aufgabe 1.

(a) Nach Aufgabe 3 auf Blatt 4 ist 𝔻_{4} isometrisch zum Codegitter des Codes d_{4} und es gilt p_{d_{4}}(X, Y) = X^{4} + Y^{4}. Wir rechnen in ℂ[[q^{1/2}]]. Nach Satz 6.3 wird

Θ_{𝔻_{4}} = Θ_{L_{d_{4}}} = p_{d_{4}}(θ_{0,2}, θ_{1,2}) = θ_{0,2}^{4} + θ_{1,2}^{4}
≡_{q^{9}} (1 + 2q^{2} + 2q^{8})^{4} + (2q^{1/2} + 2q^{9/2})^{4}
≡_{q^{9}} 1 + 24q^{2} + 24q^{4} + 96q^{6} + 24q^{8} .

Insbesondere besteht {x ∈ 𝔻_{4} | (x, x) = 8} aus 24 Elementen. Ausserdem sehen wir, daß die Koeffizienten im allgemeinen nicht monoton wachsen.

(b) Nach Aufgabe 3 auf Blatt 4 ist 𝔼_{7} isometrisch zum Codegitter von H(𝔽_{2}, 3)^{⊥}. Bestimmen wir nun zuerst den Hamminggewichtszähler von H(𝔽_{2}, 3). Dort haben wir gezeigt, daß

( \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} )

eine Erzeugermatrix von H(𝔽_{2}, 3) ist. Also ist z.B.

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

eine Erzeugermatrix von H(𝔽_{2}, 3)^{⊥}. Der Code hat 8 Codewörter und alle Wörter ungleich Null haben Gewicht 4. Damit ist p_{𝔼_{7}}(X, Y) = p_{H(𝔽_{2},3)^{⊥}}(X, Y) = X^{7} + 7X^{3}Y^{4}. Nach Satz 6.3 ist dann

Θ_{𝔼_{7}} = θ_{0,2}^{7} + 7θ_{0,2}^{3}θ_{1,2}^{4}

≡_{q^{9}} (1 + 2q^{2} + 2q^{8})^{7} + 7(1 + 2q^{2} + 2q^{8})^{3}(2q^{1/2} + 2q^{9/2})^{4}

≡_{q^{9}} 1 + (7 · 2 + 7 · 16) · q^{2} + (\binom{7}{2} · 4 + 7 · 2 · 3 · 16) · q^{4} + (\binom{7}{3} · 8 + 7(4 · 2^{4} + 3 · 2^{6})) · q^{6}

+ (7 · 2 + 16 · \binom{7}{4} + 7(2^{7} + 2 · 3 · 4 · 16)) · q^{8}

≡_{q^{9}} 1 + 126q^{2} + 756q^{4} + 2072 · q^{6} + 4158q^{8}

Insbesondere besteht {x ∈ 𝔼_{7} | (x, x) = 8} aus 4158 Elementen.

Aufgabe 2. Es wird

Θ_{∑_{i=1}^{N} a_{i}b_{i}+pM}(q) = ∑_{d_{1}∈ℤ} ⋯ ∑_{d_{N} ∈ℤ} q^{(∑_{i=1}^{N}(a_{i}+pd_{i})b_{i}, ∑_{i=1}^{N}(a_{i}+pd_{i})b_{i})}

= ∑_{d_{1}∈ℤ} ⋯ ∑_{d_{N} ∈ℤ} q^{∑_{i=1}^{N}(a_{i}+pd_{i})^{2}/p}

= ∑_{d_{1}∈ℤ} ⋯ ∑_{d_{N} ∈ℤ} ∏_{i=1}^{N} q^{(a_{i}+pd_{i})^{2}/p}

= ∏_{i=1}^{N} \underbrace{∑_{d_{i}∈ℤ} q^{(a_{i}+pd_{i})^{2}/p}}_{θ_{a_{i},p}(q)}

Aufgabe 3. Im Fall p = 2 ist ℓ ungerade, Q = {1}, ζ = −1 und somit p_{Q}(X) = X +1 ∈ 𝔽_{ℓ}[X]. Also hat QR(𝔽_{ℓ}, 2) die Erzeugermatrix (1, 1) und damit Minimum 2. Sei nun p ungerade. Fassen wir Q als Teilmenge von 𝔽_{p} auf, so ist Q eine Untergruppe von 𝔽_{p}^{∗} von Ordnung \frac{p−1}{2}.

(a) Die Nullstellenmenge von p_{Q}(X) ist gerade M := {ζ^{q} | q ∈ Q}. Wegen ℓ ∈ Q ist M = {(ζ^{ℓ})^{q} | q ∈ Q}. Also ist M invariant unter dem Frobeniusautomorphismus x ↦ x^{ℓ}. Damit ist M ⊆ 𝔽_{ℓ}. Daraus folgt die Behauptung, da die Koeffizienten von p_{Q}(X) Linearkombinationen von Produkten von Elementen aus M sind. Insbesondere ist p_{Q}(X) ∈ 𝔽_{ℓ}[X].

(b) Sei N = {i ∈ {1, …, p − 1} | i ∉ Q} die Menge der Nichtquadrate modulo p. Fixieren wir nun ein n ∈ N beliebig so ist N = nQ. Wegen (a) ist

(X^{p} − 1) = (X − 1) · p_{Q}(X) · p_{N}(X)

mit p_{N}(X) = ∏_{q∈Q}(X − ζ^{nq}) ∈ 𝔽_{ℓ}[X] da alle anderen Polynome der Gleichung in 𝔽_{ℓ}[X] sind.

Sei nun a(x) ein Codewort in QR(𝔽_{ℓ}, 2) von minimalem Gewicht d. Dann ist a(ζ^{q}) = 0 für alle q ∈ Q. Damit hat a(X)a(X^{n}) ∈ 𝔽_{ℓ}[X] die Nullstellenmenge Q ∪ N. D.h. ∑_{i=1}^{p} X^{i} ≡ p_{Q}(X)p_{N}(X) mod (X^{p} − 1). Insbesondere hat das Wort a(X)a(X^{n}) Gewicht p. Andererseits zeigt Ausmultiplizieren, daß a(X)a(X^{n}) höchstens d^{2} Koeffizienten ungleich Null haben kann. Also gilt d^{2} ≥ p.

(c) Ist p ≡_{4} −1, so dürfen wir n = −1 (bzw. p − 1) wählen. Ist a(X) = ∑_{i=0}^{p−1} a_{i}X^{i}, so ist a_{i}X^{i}a_{i}X^{−i} = 1 für genau d Koeffizienten a_{i} ≠ 0. Also liefern d Summanden von a(X)a(X^{−1}) den Beitrag 1. Damit ist das Gewicht von a(X)a(X^{−1}) maximal d^{2} − d + 1.

Aufgabe 4. Per Definition ist f̂(y) = ∫_{ℝ^{n}} exp(−\frac{π}{t} xx^{tr}) · exp(−2πixy^{tr})dx. Wir haben also

∫_{ℝ^{n}} exp(−\frac{π}{t} xx^{tr}) · exp(−2πixy^{tr})dx = t^{n/2} · exp(−πtyy^{tr})

für alle y ∈ ℝ^{n} und t ∈ ℝ_{>0} zu zeigen.

Wenden wir auf die linke Seite Fubini an, so erhalten wir ∏_{j=1}^{n} ∫_{ℝ} exp(−\frac{π}{t} x^{2}) · exp(−2πix_{j}y_{j})dx. Die rechte Seite läßt sich umformen zu ∏_{j=1}^{n} t^{1/2} · exp(−πty_{j}^{2}).

Daher genügt es die Behauptung nur für n = 1 zu zeigen. Also ist zu zeigen:

∫_{ℝ} exp(−\frac{π}{t} x^{2}) · exp(−2πixy)dx = t^{1/2} · exp(−πty^{2})

für alle y ∈ ℝ und t ∈ ℝ_{>0}. Ersetzen wir y durch t^{−1/2}y und substituieren links x ↦ t^{1/2}x, so dürfen wir annehmen, daß t = 1 ist.

Wir beweisen zunächst den bekannten Spezialfall y = 0, aus dem der allgemeine Fall folgen wird. Die linke Seite ist im Fall y = 0 gerade I := ∫_{ℝ} exp(−πx^{2})dx. Mittels dem üblichen Trick bestehend aus Quadrieren und Übergang zu Polarkoordinaten folgt

I^{2} = ∫_{ℝ^{2}} exp(−π(u^{2} + v^{2}))d(u, v) = ∫_{0}^{2π} ∫_{0}^{∞} exp(−πr^{2})rdr dα

=^{z=πr^{2}} 2π · \frac{1}{2π} ∫_{0}^{∞} exp(−z)dz = 1

Wegen I > 0 ist damit I = 1 wie behauptet.

Nun zum Fall y ≠ 0. Partielle Integration zeigt (mit u(x) = exp(−πx^{2}), v(x) = (−2πiy)^{−1} exp(−2πixy)):

f̂(y) = u(x)v(x)|_{−∞}^{+∞} − ∫_{ℝ} u′(x)v(x)dx = 0 − ∫_{ℝ} \frac{−2πx}{−2πiy} exp(−πx^{2}) exp(−2πixy)dx

Andererseits ist

f̂′(y) = ∫_{ℝ} exp(−πx^{2}) exp(−2πixy)(−2πix)dx

und somit f̂′(y) = (−2πy)f̂(y). Damit hat dann \frac{f̂(y)}{exp(−πy^{2})} die Ableitung Null. Also ist f̂(y) = c·exp(−πy^{2}) für ein c ∈ ℝ. Setzt man auf beiden Seiten y = 0 ein, so folgt c = f̂(0) = 1 wie wir bereits gezeigt haben. Damit ist der Beweis beendet.