Gitter

Stefanie Brandt

22. Januar 2001

Ein Gitter im ℝ^{n} ist eine Teilmenge Γ ⊂ ℝ^{n} mit der Eigenschaft, daß eine Basis (v_{1}, …, v_{n}) des ℝ^{n} existiert, so daß Γ von der Form

Γ = ℤv_{1} ⊕ ⋯ ⊕ ℤv_{n}

ist, d.h. Γ besteht aus allen ganzzahligen Linearkombinationen der Vektoren v_{1}, … v_{n}. Eine Basis des ℝ^{n} mit dieser Eigenschaft nennt man eine Basis von Γ oder Gitterbasis.

Beispiel:

Das Standard-Beispiel ist das (kanonische) Gitter ℤ^{n} ⊂ ℝ^{n}, das aus allen Punkten des ℝ^{n} mit ganzzahligen Koordinaten besteht. Hier ist (e_{1} … e_{n}) die kanonische Basis des ℝ^{n}.

1 Der Quotient ℝ^{n}/Γ

Sei Γ ⊂ ℝ^{n} ein Gitter und (v_{1}, … v_{n}) die zugehörige Gitterbasis. Der Quotient oder Faktorraum ℝ^{n}/Γ ist definiert durch ℝ^{n}/Γ = {x̄ = x + Γ | x ∈ ℝ^{n}}. Man kann jedes x ∈ ℝ^{n} mit einem Punkt y im fundamentalen Parallelotop P = {λ_{1}v_{1} + λ_{2}v_{2} + … + λ_{n}v_{n} | 0 ≤ λ_{i} ≤ 1} und somit den gesamten Quotienten ℝ^{n}/Γ mit P identifizieren, was für die späteren Betrachtungen benötigt wird.

Satz:

Zu jedem x ∈ ℝ^{n} gibt es ein y ∈ P mit x̄=ȳ in ℝ^{n}/Γ.

Beweis:

Sei v_{1}, …, v_{n} eine Gitterbasis des ℝ^{n}. Jedes x ∈ ℝ^{n} kann man schreiben als x = ∑_{i=1}^{n} μ_{i}v_{i} mit μ_{i} ∈ ℝ. Jedes μ_{i} läßt sich schreiben als μ_{i} = λ_{i} + z_{i} mit z_{i} ∈ ℤ und 0 ≤ λ_{i} ≤ 1. ⇒ x = ∑_{i=1}^{n}(λ_{i} + z_{i})v_{i}. Sei nun y = ∑_{i=1}^{n} λ_{i}v_{i} gegeben (natürlich liegt y in P), so ist:

x − y = ∑_{i=1}^{n}(λ_{i} + z_{i})v_{i} − ∑_{i=1}^{n} λ_{i}v_{i}

= ∑_{i=1}^{n}(λ_{i} + z_{i})v_{i} − λ_{i}v_{i}

= ∑_{i=1}^{n}(λ_{i} + z_{i} − λ_{i})v_{i}

= ∑_{i=1}^{n} z_{i}v_{i}  ∈ Γ

Aus der Linearen Algebra ist bekannt, daß gilt: x − y ∈ Γ ⇔ x̄=ȳ in ℝ^{n}/Γ. Also gibt es zu jedem x ∈ ℝ^{n} ein y ∈ P mit x̄=ȳ in ℝ^{n}/Γ.

□

Unter der stärkeren Bedingung, daß man jeden Punkt auf dem Rand von P mit dem gegenüberliegenden identifiziert, bildet der Quotient ℝ^{n}/Γ einen ndimensionalen Torus, den man durch die Seiten des fundamentalen Parellelotops P erhält. Durch obige Überlegungen sieht man, daß ℝ^{n}/Γ abgeschlossen und beschränkt und somit kompakt ist.

2 Das Volumen eines Gitters

Das Volumen eines Gitters Γ ⊂ ℝ^{n} ist

vol(ℝ^{n}/Γ) := vol(P) = |det[v_{1}| … |v_{n}]|

wobei [v_{1}| … |v_{n}] die Matrix ist, deren Spalten von den Basisvektoren (v_{1} … v_{n}) gebildet werden. (Das zweite Gleichheitszeichen in dieser Gleichung resultiert aus einer Formel aus der Analysis.)

Im Standard-Beispiel ℤ^{n} ⊂ ℝ^{n} trifft dies zu. Hier ist P ein n-dimensionaler Einheits-Kubus und die obige Formel folgt im allgemeinen aus der Transformationsformel für ganze Zahlen. Die Matrix [v_{1}| … |v_{n}] ist hier die Transformationsmatrix (oder Basiswechselmatrix) von ℤ^{n} nach Γ.

Allgemeiner sei nun Γ′ ⊂ ℝ^{n} ein Gitter mit Γ′ ⊂ Γ. Dann ist der Index |Γ/Γ′| ausdrücklich begrenzt und es ist:

vol(ℝ^{n}/Γ′) = vol(ℝ^{n}/Γ)|Γ/Γ′|

Den Index kann man sich vorstellen als die Anzahl der Elemente im Schnitt von Γ und dem ’eingeschränkten’ Parallelotop zu P, definiert durch:

ℙ = {λ_{1}v_{1} + … + λ_{n}v_{n} | 0 ≤ λ_{i} < 1}

Beispiel:

Sei Γ ∈ ℝ^{2} das kanonische Gitter mit Gitterbasis (e_{1}, e_{2}) und Γ′ ⊂ Γ habe die Basis (v_{1}, v_{2}) mit v_{1} = 2e_{2} und v_{2} = 3e_{1} + e_{2}. Sei weiterhin P das fundamentale Parallelotop zu Γ, P′ das fundamentale Parallelotop zu Γ′ und ℙ′ das dazu eingeschränkte Parallelotop. Man weiß, daß vol(P) = 1 und man kann mit Hilfe von ’Schulgeometrie’ anhand einer Skizze sehen, daß vol(P′) = 6. Man sieht weiterhin, daß |Γ/Γ′| = |Γ ∩ ℙ′| = 6. Also sieht man: vol(ℝ^{2}/Γ′) = vol(ℝ^{2}/Γ)|Γ/Γ′| = 1 · 6 = 6.

3 Das Dualgitter

Sei nun das euklid’sche Skalarprodukt zweier Vektoren x, y ∈ ℝ^{n} gegeben durch:

⟨x, y⟩ = ∑_{i=1}^{n} x_{i}y_{i}

Das euklid’sche Skalarprodukt ist eine nicht-ausgeartete, symmetrische Bilinearform. Sei nun A = (a_{ij})_{ij} die durch a_{ij} = ⟨v_{i}, v_{j}⟩ gegebene Matrix. Sei C = [v_{1}| … |v_{n}]. Dann gilt A = CC^{t}. Also gilt:

vol(P) = |detC| = \sqrt{detA}

Sei nun Γ ein Gitter im ℝ^{n}. Wir nennen Γ^{∗} das Dualgitter von Γ. Es gilt:

Γ^{∗} = {x ∈ ℝ^{n} | ⟨x, y⟩ ∈ ℤ ∀y ∈ Γ}

Sei (v_{1}, …, v_{n}) eine Basis von Γ. Dann ist die dazu duale Basis (v_{1}^{∗}, …, v_{n}^{∗}) definiert durch: ⟨v_{i}^{∗}, v_{j}⟩ = δ_{ij}. Dafür gilt auch:

v_{i}^{∗} = ∑_{j=1}^{n} b_{ij}v_{j}

und es ist B = (b_{ij})_{ij} = A^{−1}, denn: aus den Formeln ⟨v_{i}, v_{j}⟩ = a_{ij}, v_{i}^{∗} = ∑_{j=1}^{n} b_{ij}v_{j} und ⟨v_{i}^{∗}, v_{j}⟩ = δ_{ij} folgt: ⟨v_{i}^{∗}, v_{j}⟩ = ⟨∑_{l=1}^{n} b_{il}v_{l}, v_{j}⟩ = ∑_{l=1}^{n} b_{il}⟨v_{l}, v_{j}⟩ = ∑_{l=1}^{n} b_{il}a_{lj} = δ_{ij} ⇒ B · A = I ⇒ B = A^{−1}.

Die so definierten v_{i}^{∗} bilden eine Basis von Γ^{∗}. Es folgt wieder aus den obigen Formeln, daß die Matrix mit Koeffizienten (⟨v_{i}^{∗}, v_{j}^{∗}⟩) gleich B ist. Dies zeigt insbesondere, daß gilt:

vol(ℝ^{n}/Γ^{∗}) = \frac{1}{vol(ℝ^{n}/Γ)}

denn:

vol(ℝ^{n}/Γ^{∗}) = \sqrt{detB} = \sqrt{detA^{−1}} = \sqrt{\frac{1}{detA}} = \frac{1}{\sqrt{detA}} = \frac{1}{vol(ℝ^{n}/Γ)}

Beispiel:

Sei Γ ⊂ ℝ^{2} ein Gitter mit Gitterbasis (v_{1}, v_{2}) mit v_{1} = 2e_{1} und v_{2} = e_{1} + e_{2}. Wir berechnen die duale Basis mit obigen Formeln. Wir suchen jeweils einen Vektor v_{1}^{∗} = (x, y) bzw. v_{2}^{∗} = (v, w), der die folgenden Gleichungen erfüllt: ⟨v_{1}, v_{1}^{∗}⟩ = 2x = 1 ⇒ x = \frac{1}{2}, ⟨v_{2}, v_{1}^{∗}⟩ = x + y = 0 ⇒ y = −\frac{1}{2} ⟹ v_{1}^{∗} = \frac{1}{2}(e_{1} − e_{2}) bzw. ⟨v_{1}, v_{2}^{∗}⟩ = 2v = 0 ⇒ v = 0, ⟨v_{2}, v_{2}^{∗}⟩ = v + w = 1 ⇒ w = 1 ⟹ v_{2}^{∗} = e_{2}. Also haben wir eine zu (v_{1}, v_{2}) duale Basis (v_{1}^{∗}, v_{2}^{∗}) gefunden. An einer Zeichnung sieht man außerdem leicht, daß gilt: vol(ℝ^{n}/Γ) = 2 und vol(ℝ^{n}/Γ^{∗}) = \frac{1}{2}.

4 Ganzzahlige Gitter

Ein Gitter Γ ∈ ℝ^{n} heißt ganzzahlig, wenn ⟨x, y⟩ ∈ ℤ ∀ x, y ∈ Γ.

Sei nun Γ ein ganzzahliges Gitter mit Basis (v_{1}, …, v_{n}) und sei A die Matrix A = (⟨v_{i}, v_{j}⟩)_{ij}. Dann ist A eine ganzzahlige Matrix und die Determinante detA ist eine ganze Zahl. Diese ganze Zahl hängt nicht von der Wahl der Basis ab. Denn sei (w_{1}, … w_{n}) eine andere Basis von Γ und sei A′ = (⟨w_{i}, w_{j}⟩)_{ij}. Dann gilt

w_{i} = ∑_{j=1}^{n} q_{ij}v_{j}

und die Matrix Q = (q_{ij})_{ij} ist invertierbar über ℤ, was insbesondere bedeutet, daß gilt detQ = ±1. Aber es gilt auch:

A′ = QAQ^{t}

also gilt detA′ = detA. Also hängt detA nicht von der Wahl der Basis (v_{1}, …, v_{n}) ab und man nennt diese Zahl die Diskriminante des Gitters Γ und man schreibt disc(Γ).

Wir haben schon gesehen, daß gilt:

vol(ℝ^{n}/Γ) = \sqrt{disc(Γ)}

vol(ℝ^{n}/Γ^{∗}) = \frac{1}{\sqrt{disc(Γ)}}

Aus der Formel

vol(ℝ^{n}/Γ) = vol(ℝ^{n}/Γ^{∗})|Γ^{∗}/Γ|

erhalten wir die folgende Formel für die Diskriminante von Γ:

disc(Γ) = |Γ^{∗}/Γ|

5 Unimodulare Gitter

Ein Gitter Γ ⊂ ℝ^{n} heißt unimodular, falls gilt: Γ^{∗} = Γ. Die gewählte Basis eines unimodularen Gitters muß allerdings nicht gleich ihrer Dualbasis sein. In ’Matrix-Sprache’ heißt das Folgendes:

Satz:

Sei Γ ein ganzzahliges Gitter mit Basis (v_{1}, …, v_{n}). Dann ist Γ unimodular genau dann, wenn die Matrix A = (⟨v_{i}, v_{j}⟩)_{ij} ganzzahlige Koeffizienten hat und ihre Determinante disc(Γ) gleich 1 ist. Die letzte Bedingung ist äquivalent zu: vol(P) = 1 (Dies ist klar.)

Beweis:

Ist A ganzzahlig und ist det(A) = 1, so ist dies äquivalent zu der Tatsache, daß A über ℤ invertierbar ist, also ist auch A^{−1} ganzzahlig. Dies ist ist gerade die Basiswechselmatrix von der Basis von Γ in die dazu duale Basis in Γ^{∗}. Da diese Basiswechselmatrix ganzzahlig ist, gilt: Γ^{∗} ⊆ Γ. Andersherum ist mit A auch die Basiswechselmatrix von der dualen Basis von Γ^{∗} in die Basis von Γ ganzzahlig und somit gilt auch: Γ ⊆ Γ^{∗}. Wegen Γ^{∗} ⊆ Γ ⊆ Γ^{∗} gilt: Γ = Γ^{∗}. Γ ist also unimodular.

□

Beispiel:

Ein Beispiel für ein unimodulares Gitter ist das kanonische Gitter. Wir betrachten es hier allerdings mit der Basis (v_{1}, v_{2}) mit v_{1} = e_{1} und v_{2} = e_{1} + e_{2}. Die dazu duale Basis (v_{1}^{∗}, v_{2}^{∗}) erhält man analog zum vorigen Beispiel. Sie lautet v_{1}^{∗} = e_{1} − e_{2} und v_{2}^{∗} = e_{2}

Obwohl hier offensichtlich Γ = Γ^{∗} gilt, ist die Basis von Γ nicht gleich ihrer dualen Basis und somit sieht auch das fundamentale Parallelotop P^{∗} von Γ^{∗} anders aus als das von Γ.

6 Direkte Zerlegung von Gittern

Sei Γ ein ganzzahliges Gitter im ℝ^{n}. Ein ℤ-Untermodul Λ von Γ heißt Untergitter von Γ. Es ist ein Gitter einem Unterraum W ⊂ ℝ^{k}, der isomorph zu ℝ^{k} für ein k ist. Ist K eine Teilmenge von Γ, so nennen wir den ℤ-Untermodul

K^{⊥} = { y ∈ Γ | ⟨x, y⟩ = 0 ∀ x ∈ K}

das zu K orthogonale Untergitter.

Seien Λ_{1}, …, Λ_{m} Untergitter von Γ. Das Gitter Γ heißt Orthogonale direkte Summe von Untergittern Λ_{1}, …, Λ_{m} und man schreibt

Γ = Λ_{1} ⊕ ⋯ ⊕ Λ_{m}

wenn Γ die direkte Summe von Untermoduln Λ_{1}, …, Λ_{m} ist und wenn gilt: ⟨x, y⟩ = 0 ∀x ∈ Λ_{i}, y ∈ Λ_{j} und i ≠ j.

7 Gerade Gitter

Ein ganzzahliges Gitter Γ heißt gerade, wenn ⟨x, x⟩ ≡ 0 (mod 2) ∀x ∈ Γ. In ’Matrix-Sprache’ heißt das, daß die Diagonalkoeffizienten ⟨v_{i}, v_{i}⟩ der Matrix A alle gerade sind.

Beispiel:

Ein Beispiel für ein gerades Gitter ist das Gitter Γ mit Basis v_{1} = 3e_{1} + e_{2}, v_{2} = 2e_{2}. Durch nachrechenen erhält man ⟨v_{1}, v_{1}⟩ = 9 + 1 = 10, ⟨v_{2}, v_{2}⟩ = 4 und ⟨v_{1}, v_{2}⟩ = 2. Da jedes x ∈ Γ von der Form x = av_{1} + bv_{2} mit a, b ∈ ℤ ist, gilt für alle x ∈ Γ:

⟨x, x⟩ = ⟨av_{1} + bv_{2}, av_{1} + bv_{2}⟩
= ⟨av_{1}, av_{1}⟩ + ⟨av_{1}, bv_{2}⟩ + ⟨bv_{2}, av_{1}⟩ + ⟨bv_{2}, bv_{2}⟩
= a^{2}⟨v_{1}, v_{1}⟩ + ab⟨v_{1}, v_{2}⟩ + ba⟨v_{2}, v_{1}⟩ + b^{2}⟨v_{2}, v_{2}⟩
= a^{2}10 + ab2 + ba2 + b^{2}4
= 2(5a^{2} + 2ab + 2b)
≡ 0 (mod 2)

Natürlich sind auch hier die Diagonalkoeffizienten ⟨v_{i}, v_{i}⟩ der darstellenden Matrix A gerade, ganze Zahlen.

⋆ Quelle: Wolfgang Ebeling, ’Lattices and Codes’