Gitter (Mathematik)

Ein Gitter (engl. lattice) i​n der Mathematik i​st eine diskrete Untergruppe d​es euklidischen Raums. Gitter finden Verwendung u. a. i​n der Gruppentheorie, d​er Geometrie u​nd bei Approximationsfragestellungen.

Ausschnitt eines Gitters. Die blauen Punkte gehören zum Gitter.

Die einzelnen Elemente e​ines Gitters heißen Gitterpunkte o​der Gittervektoren.

Gitter im euklidischen Raum

Es seien ${\displaystyle b_{1},b_{2},\ldots ,b_{m}}$ linear unabhängige Vektoren des euklidischen Vektorraums ${\displaystyle \mathbb {R} ^{n}}$. Dann nennt man

${\displaystyle \Gamma$ :=\langle b_{1},\dots ,b_{m}\rangle _{\mathbb {Z} }:=\left\{\left.\textstyle \sum \limits _{i=1}^{m}g_{i}b_{i}\ \right|\,g_{i}\in \mathbb {Z} \right\}}

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

Die beschränkte Menge

${\displaystyle {\mathcal {F}}_{\Gamma }:=\left\{\left.\textstyle \sum \limits _{i=1}^{m}r_{i}b_{i}\ \right|\,0\leq r_{i}<1\right\}}$

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

${\displaystyle R:=\left\{\left.\textstyle \sum \limits _{i=1}^{m}r_{i}b_{i}\ \right|\,r_{i}\in \mathbb {R} \right\}}$

auf und bildet darin ein rechtsoffenes ${\displaystyle m}$-dimensionales Parallelepiped. Die Basis ${\displaystyle \{b_{1},b_{2},\ldots ,b_{m}\}}$ des Gitters ist eine Basis dieses Vektorraums.

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

${\displaystyle x\sim _{\Gamma }y\quad$ :\Leftrightarrow \quad y-x\in \Gamma } .

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

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

In diesem Fall kann der ganze ${\displaystyle \mathbb {R} ^{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 ${\displaystyle \Gamma }$ heißt ganz, falls für alle ${\displaystyle x,y\in \Gamma }$ das Skalarprodukt ${\displaystyle \langle x,y\rangle }$ eine ganze Zahl ist. Ist sogar ${\displaystyle \langle x,x\rangle \in 2\mathbb {Z} }$ für alle ${\displaystyle x\in \Gamma }$, so nennt man das Gitter ${\displaystyle \Gamma }$ gerade (gerade Gitter sind automatisch ganz).

Beispiele:

1. Das Gitter in der Abbildung hat die Basisvektoren ${\displaystyle b_{1}=({\tfrac {2}{3}},{\tfrac {1}{3}})}$ und ${\displaystyle b_{2}=({\tfrac {1}{3}},-{\tfrac {1}{3}})}$. Es ist weder ganz noch gerade.
2. Das Gitter mit Basisvektoren ${\displaystyle b_{1}=(3,1)}$ und ${\displaystyle b_{2}=(1,-1)}$ ist sowohl ganz als auch gerade.

Gitter in der komplexen Zahlenebene

→ Hauptartikel: Fundamentalbereich

Indem man die komplexe Zahlenebene ${\displaystyle \mathbb {C} }$ als reellen Vektorraum auffasst, kann man von Gittern in ${\displaystyle \mathbb {C} }$ sprechen; sie sind freie abelsche Gruppen vom Rang 2. Sie spielen eine zentrale Rolle in der Theorie der elliptischen Funktionen und elliptischen Kurven.

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

Gitter in Lie-Gruppen

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

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

gibt.

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

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

Gitter i​n Lie-Gruppen spielen e​ine wichtige Rolle i​n Thurstons Geometrisierungsprogramm.

Beispiele

• Sei ${\displaystyle \Gamma }$ das zur Basismatrix ${\displaystyle {\begin{pmatrix}1&{\tfrac {1}{2}}\\0&{\sqrt {2}}\end{pmatrix}}}$ gehörige Gitter vom Rang 2. Dann ist ${\displaystyle \det \Gamma ={\sqrt {2}}}$.
• Sei ${\displaystyle \Gamma$ :=\mathbb {Z} ^{n}\subseteq \mathbb {R} ^{n}} . Dann ist die Grundmasche von ${\displaystyle \Gamma }$ der ${\displaystyle n}$-dimensionale Hyperwürfel ${\displaystyle {\mathcal {F}}_{\Gamma }=[0,1)^{n}}$, und es gilt z. B. ${\displaystyle ({\tfrac {3}{2}},0,\dots ,0)\equiv _{\Gamma }(-{\tfrac {7}{2}},1,\dots ,1)}$.
• Der Ring der gaußschen Zahlen ${\displaystyle \mathbb {Z} [\mathrm {i} ]}$ ist ein Gitter in ${\displaystyle \mathbb {C} }$.
• Der Ring der Hurwitzquaternionen ist ein Gitter im Schiefkörper ${\displaystyle \mathbb {H} }$ der Quaternionen.
• Das Leech-Gitter ist ein besonderes Gitter im ${\displaystyle \mathbb {R} ^{24}.}$

Gitterdiskriminante

Eine Kenngröße z​ur Klassifikation v​on Gittern i​st die Gitterdiskriminante. Sie berechnet s​ich als Volumen d​er Grundmasche.

${\displaystyle d(\Gamma )=\operatorname {vol} (b_{1},b_{2},\ldots ,b_{m})}$

Bei Gittern im euklidischen Raum mit der Basismatrix ${\displaystyle B}$ entspricht dies der Formel

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

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

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

Als Invariante i​st der Wert d​er Gitterdiskriminante unabhängig v​on der gewählten Basis.

Gitterreduktion

Die Gitterreduktion i​st das Problem, a​us einer gegebenen Gitterbasis e​ine Basis m​it gewissen Eigenschaften z​u berechnen, w​ie zum Beispiel e​ine Basis m​it kurzen, nahezu orthogonalen Vektoren. Der LLL-Algorithmus (nach Lenstra, Lenstra u​nd Lovász) berechnet i​n polynomieller Zeit e​ine sogenannte LLL-reduzierte Basis, m​it deren Hilfe m​an beweisbar k​urze Gittervektoren erhält. In d​er Tat l​iegt die Länge d​es ersten Vektors e​iner LLL-reduzierten Basis n​ahe an d​er Länge d​es kürzesten nichttrivialen Gittervektors.

Der LLL-Algorithmus h​at zahlreiche Anwendungen i​n der Kryptoanalyse v​on asymmetrischen Verschlüsselungsverfahren w​ie dem RSA-Kryptosystem u​nd dem Merkle-Hellman-Kryptosystem gefunden.

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.

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
• Bravais-Gitter
• Spezielle Gitter werden nach Dedekind bei der Untersuchung algebraisch ganzer Zahlen verwendet. Siehe dazu Ordnung (algebraische Zahlentheorie)
• Der mathematische Fachbegriff ist an die umgangssprachliche Verwendung eines Gitters angelehnt.