Gitter (Mathematik)

Ausschnitt eines Gitters

Ein Gitter (engl. lattice) in der Mathematik ist eine diskrete Untergruppe des euklidischen Raums. Gitter finden innermathematisch Verwendung u. a. in der Gruppentheorie, der Zahlentheorie, der Geometrie und bei Approximationsfragestellungen.

Die einzelnen Elemente eines Gitters heißen Gitterpunkte oder Gittervektoren.

Gitter im euklidischen Raum

Es seien $b_1,b_2,\dots ,b_m$ linear unabhängige Vektoren des euklidischen Vektorraums ${ℝ}^n$. Dann nennt man

$\mathrm{\Gamma }:=⟨b_1,\dots ,b_m{⟩}_{\mathbb{Z}}:=\{\sum _{i=1}^m{g}_i{b}_i|g_i\in \mathbb{Z}\}$

ein Gitter mit Basis $\{b_1,b_2,\dots ,b_m\}$ vom Rang $m$. Die aus den Vektoren $b_1,\dots ,b_m$ gebildete Matrix $B:=(b_1,\dots ,b_m)\in {ℝ}^{n\times m}$ heißt Basismatrix von $\mathrm{\Gamma }$. Die Basis ist durch das Gitter nicht festgelegt. Jede Basis von $\mathrm{\Gamma }$ hat jedoch denselben Rang $m$. Als Untergruppe der additiven Gruppe von ${ℝ}^n$ ist $\mathrm{\Gamma }$ eine freie abelsche Gruppe vom Rang $m$.

Die beschränkte Menge

${ℱ}_{\mathrm{\Gamma }}:=\{\sum _{i=1}^m{r}_i{b}_i|0\le r_i<1\}$

heißt Grundmasche oder Fundamentalmasche von $\mathrm{\Gamma }$. Sie spannt im ${ℝ}^n$ einen $m$-dimensionalen Untervektorraum

$R:=\{\sum _{i=1}^m{r}_i{b}_i|r_i\in ℝ\}$

auf und bildet darin ein rechtsoffenes $m$-dimensionales Parallelepiped. Die Basis $\{b_1,b_2,\dots ,b_m\}$ des Gitters ist eine Basis dieses Vektorraums.

Durch das Gitter $\mathrm{\Gamma }$ wird auf ${ℝ}^n$ eine Äquivalenzrelation ${\sim }_{\mathrm{\Gamma }}$ wie folgt definiert:

$x{\sim }_{\mathrm{\Gamma }}y:\iff y-x\in \mathrm{\Gamma }$.

Jedes Element von $R$ ist zu genau einem Element aus der Grundmasche äquivalent. Jede Äquivalenzklasse hat also genau einen Repräsentanten in der Grundmasche.

Zu einem $y\in {ℝ}^n\setminus R$ gibt es kein $x\in R$ mit $y-x\in \mathrm{\Gamma }$. Da sich das Interessante also nur im Unterraum $R$ abspielt und dieser isomorph zu ${ℝ}^m$ ist, betrachten die meisten Autoren nur den Fall der Gleichheit $m=n$ (Gitter mit vollem Rang).

In diesem Fall kann der ganze ${ℝ}^n$ mit Maschen der Form der Grundmasche parkettiert werden. Jedoch sind auch Formen interessant, die kein Parallelepiped sind. Man spricht dann von einer Fundamentalregion.

Ein Gitter $\mathrm{\Gamma }$ heißt ganz, falls für alle $x,y\in \mathrm{\Gamma }$ das Skalarprodukt $⟨x,y⟩$ eine ganze Zahl ist. Ist sogar $⟨x,x⟩\in 2\mathbb{Z}$ für alle $x\in \mathrm{\Gamma }$, so nennt man das Gitter $\mathrm{\Gamma }$ gerade (gerade Gitter sind automatisch ganz). Ein ganzes Gitter $\mathrm{\Gamma }$ heißt unimodular, wenn die Gitterdiskriminante (s. u.) im Betrag 1 ist. Ein ganzes Gitter heißt Wurzelgitter, falls $\mathrm{\Gamma }=⟨\{v\in \mathrm{\Gamma }:⟨v,v⟩=2\}{⟩}_{\mathbb{Z}}$. Hierbei heißt $\{v\in \mathrm{\Gamma }:⟨v,v⟩=2\}$ die Menge der Wurzeln $\mathrm{\Gamma }$. Für ein Gitter $\mathrm{\Gamma }$ in ${ℝ}^n$ heißt ${\mathrm{\Gamma }}^{*}=\{x\in {ℝ}^n:⟨x,y⟩\in \mathbb{Z}\mathrm{\forall }y\in \mathrm{\Gamma }\}$ das duale Gitter.

Beispiele:

1. Das Gitter in der Abbildung hat die Basisvektoren $b_1=(\frac{2}{3},\frac{1}{3})$ und $b_2=(\frac{1}{3},-\frac{1}{3})$. Es ist weder ganz noch gerade.
2. Das Gitter mit Basisvektoren $b_1=(3,1)$ und $b_2=(1,-1)$ ist sowohl ganz als auch gerade.
3. Das duale Gitter von $\mathrm{\Gamma }={\mathbb{Z}}^n$ ist ${\mathbb{Z}}^n$.

Eigenschaften

• Sei $\mathrm{\Gamma }$ eine Untergruppe von ${ℝ}^n$. Dann ist $\mathrm{\Gamma }$ genau dann ein Gitter, wenn $\mathrm{\Gamma }$ diskret und kokompakt ist.

Gitter in der komplexen Zahlenebene

Vorlage:Hauptartikel Indem man die komplexe Zahlenebene $ℂ$ als reellen Vektorraum auffasst, kann man von Gittern in $ℂ$ sprechen; sie sind freie abelsche Gruppen vom Rang 2. Sie spielen eine zentrale Rolle in der Theorie der elliptischen Funktionen (Periodengitter) und elliptischen Kurven.

Ist allgemeiner $g$ eine natürliche Zahl, so stehen Gitter im reell $2g$-dimensionalen Raum ${ℂ}^g$ in Beziehung zu komplexen Tori und abelschen Varietäten.

Gitter in Lie-Gruppen

Eine Untergruppe $\mathrm{\Gamma }\subset G$ einer topologischen Gruppe $G$ heißt diskrete Untergruppe, wenn es zu jedem $\gamma \in \mathrm{\Gamma }$ eine offene Umgebung $U_{\gamma }\subset G$ mit

$U_{\gamma }\cap \mathrm{\Gamma }=\left\{\gamma \right\}$

gibt.

Wenn $G$ eine lokalkompakte Gruppe mit Haarschem Maß $\mu$ ist, dann heißt eine diskrete Untergruppe $\mathrm{\Gamma }\subset G$ ein Gitter, falls der Quotient $G/\mathrm{\Gamma }$ endliches Volumen (bzgl. des Haarschen Maßes) hat.

Ein Gitter heißt uniform oder kokompakt, falls $G/\mathrm{\Gamma }$ kompakt ist.

Gitter in Lie-Gruppen spielen eine wichtige Rolle in Thurstons Geometrisierungsprogramm.

Beispiele

• Sei $\mathrm{\Gamma }$ das zur Basismatrix $\left(\begin{array}{cc}1& \frac{1}{2}\\ 0& \sqrt{2}\end{array}\right)$ gehörige Gitter vom Rang 2. Dann ist $\det \mathrm{\Gamma }=\sqrt{2}$.
• Sei $\mathrm{\Gamma }:={\mathbb{Z}}^n\subseteq {ℝ}^n$. Dann ist die Grundmasche von $\mathrm{\Gamma }$ der $n$-dimensionale Hyperwürfel ${ℱ}_{\mathrm{\Gamma }}=[0,1{)}^n$, und es gilt z. B. $(\frac{3}{2},0,\dots ,0){\equiv }_{\mathrm{\Gamma }}(-\frac{7}{2},1,\dots ,1)$.
• Der Ring der gaußschen Zahlen $\mathbb{Z}[\mathrm{i}]$ ist ein Gitter in $ℂ$.
• Der Ring der Hurwitzquaternionen ist ein Gitter im Schiefkörper $ℍ$ der Quaternionen.
• Das Leech-Gitter ist ein besonderes Gitter im ${ℝ}^{24}.$
• Das E₈-Gitter ist ein unimodulares Gitter im ${ℝ}^8$.

Gitterdiskriminante

Eine Kenngröße zur Klassifikation von Gittern ist die Gitterdiskriminante. Sie berechnet sich als Volumen der Grundmasche.

$d(\mathrm{\Gamma })=\mathrm{vol}(b_1,b_2,\dots ,b_m)$

Bei Gittern im euklidischen Raum mit der Basismatrix $B$ entspricht dies der Formel

$d(\mathrm{\Gamma })=\sqrt{\det \left(B^{T}B\right)}$

Hat $B$ vollen Rang, so lässt sich dies zu folgendem Ausdruck vereinfachen:

$d(\mathrm{\Gamma })=|\det \left(B\right)|$

Als Invariante ist der Wert der Gitterdiskriminante unabhängig von der gewählten Basis.

Gitterreduktion

Die Gitterreduktion ist das Problem, aus einer gegebenen Gitterbasis eine Basis mit gewissen Eigenschaften zu berechnen, wie zum Beispiel eine Basis mit kurzen, nahezu orthogonalen Vektoren. Der LLL-Algorithmus (nach Lenstra, Lenstra und Lovász) berechnet in polynomieller Zeit eine sogenannte LLL-reduzierte Basis, mit deren Hilfe man beweisbar kurze Gittervektoren erhält. In der Tat liegt die Länge des ersten Vektors einer LLL-reduzierten Basis nahe an der Länge des kürzesten nichttrivialen Gittervektors.

Der LLL-Algorithmus hat zahlreiche Anwendungen in der Kryptoanalyse von asymmetrischen Verschlüsselungsverfahren wie dem RSA-Kryptosystem und dem Merkle-Hellman-Kryptosystem gefunden.

Codegitter

Aus linearen Binärcodes können Gitter konstruiert werden. Dazu wird das Standardgitter ${\mathbb{Z}}^n\subset {ℝ}^n$ und der Gruppenhomomorphismus $\rho :{\mathbb{Z}}^n\to (\mathbb{Z}/2\mathbb{Z}{)}^n={𝔽}_2^n,(a_1,...,a_n)\mapsto (a_1\mathrm{mod}2,...,a_n\mathrm{mod}2)$ betrachtet. Sei $C$ nun ein binärer $[n,k,d]$-Code. Da ${𝔽}_2^n/C\cong {𝔽}_2^{n-k}$, ist $C$ eine Untergruppe von ${𝔽}_2^n$ vom Index $2^{n-k}$. Man nennt ${\mathrm{\Gamma }}_C=\frac{1}{\sqrt{2}}{\rho }^{-1}(C)$ das zu $C$ gehörige Codegitter. Aus dem erweiterten Hamming-Code kann das $E_8$-Gitter konstruiert werden.

Literatur

• Gudrun Susanne Wetzel: Lattice basis reduction algorithms and their applications. Shaker Verlag, Aachen 1998, ISBN 3-8265-4543-5.
• John Horton Conway, Neil Sloane: Sphere packings, lattices and groups. Grundlehren der mathematischen Wissenschaften 290, Springer, 3. Auflage 1999, ISBN 0-387-98585-9.
• Phong Q. Nguyen, Jacques Stern: The two faces of lattices in cryptology. In: Joseph Silverman (Hrsg.): Cryptography and lattices (Proceedings CALC 2001), Lecture Notes Computer Science 2146, Springer 2001, S. 146–180
• Daniele Micciancio, Shafrira Goldwasser: Complexity of lattice problems. A cryptographic perspective. Kluwer Academic & Springer 2002, ISBN 978-0-7923-7688-0.
• Phong Q. Nguyen, Brigitte Vallée (Hrsg.): The LLL algorithm. Survey and applications. Reihe Information Security and Cryptography, Springer 2010, ISBN 978-3-642-02294-4.
• Ebeling, W. (2012). Lattices and Codes: A Course Partially Based on Lectures by Friedrich Hirzebruch (Advanced Lectures in Mathematics) (3rd ed. 2013 Aufl.). Springer Spektrum, ISBN 978-3658003593.

Weblinks

• Noam Elkies: Lattices, linear codes, and invariants. Part I (PDF; 156 kB) Notices AMS 47 (2000), No. 10, S. 1238–1245 Part II (PDF; 176 kB) Notices AMS 47 (2000), No. 11, S. 1382–1391
• Hendrik Lenstra: Flags and lattice basis reduction. in Carles Casacuberta et al. (Hrsg.): European Congress of Mathematics. Barcelona 2000, Vol. I. Birkhäuser 2002, ISBN 978-3-7643-6417-5, S. 37–52. Online hier (PDF; 165 kB)
• Oded Regev: Lattices in Computer Science. Tel-Aviv University, 2004
• Daniele Micciancio: Lecture Notes on lattice algorithms and applications University of California, 2007
• Hendrik Lenstra: Lattices. in Joseph P. Buhler, Peter Stevenhagen (Hrsg.): Algorithmic Number Theory. MSRI Publications Vol. 44, Cambridge University Press 2008, ISBN 978-0-521-80854-5, S. 127–181. Online hier oder dort (PDF; 368 kB)
• Daniel J. Bernstein: Bibliography on Lattice-based public-key cryptography
• Keita Xagawa: Bibliography on Lattice-based Cryptosystems

Siehe auch

• Raumgruppe
• Spezielle Gitter werden nach Dedekind bei der Untersuchung algebraisch ganzer Zahlen verwendet. Siehe dazu Ordnung (algebraische Zahlentheorie)