imported>FlMcc: /* growthexperiments-addlink-summary-summary:3|0|0 */

2025-01-08T06:03:28Z

growthexperiments-addlink-summary-summary:3|0|0

Neue Seite

{{Dieser Artikel|1=beschreibt Gitter in der Mathematik. Spezifisch zu Gittern in der Geometrie siehe [[Gitter (Geometrie)]]. Zu weiteren, außermathematischen Bedeutungen siehe [[Gitter (Begriffsklärung)]].}}

[[Datei:Equilateral Triangle Lattice.svg|miniatur|rechts|Ausschnitt eines Gitters]]
Ein '''Gitter''' (engl. ''lattice'') in der [[Mathematik]] ist eine [[Diskrete Teilmenge|diskrete]] [[Untergruppe]] des euklidischen Raums. Gitter finden innermathematisch Verwendung u. a. in der [[Gruppentheorie]], der [[Zahlentheorie]]<ref>Vgl. [[Zwei-Quadrate-Satz#Beweise des Zwei-Quadrate-Satzes|Beweis des Zwei-Quadrate-Satzes]] mit dem [[Minkowskischer Gitterpunktsatz|Gitterpunktsatz von Minkowski]].</ref>, der [[Geometrie]] und bei [[Approximation]]s<nowiki/>fragestellungen.

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

== Gitter im euklidischen Raum ==

Es seien <math>b_1, b_2, \ldots, b_m</math> [[Lineare Unabhängigkeit|linear unabhängige]] Vektoren des [[Euklidischer Raum#Euklidische Vektorräume|euklidischen Vektorraums]] <math>\mathbb{R}^n</math>. Dann nennt man
:<math>\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\}</math>
ein Gitter mit Basis <math>\{b_1, b_2, \ldots, b_m\}</math> vom Rang <math>m</math>. Die aus den Vektoren <math>b_1, \dots, b_m</math> gebildete Matrix <math>B:=(b_1,\dots,b_m)\in\mathbb{R}^{n\times m}</math> heißt Basismatrix von <math>\Gamma</math>. Die Basis ist durch das Gitter nicht festgelegt. Jede Basis von <math>\Gamma</math> hat jedoch denselben Rang <math>m</math>. Als [[Untergruppe]] der additiven [[Gruppe (Mathematik)|Gruppe]] von <math>\R^n</math> ist <math>\Gamma</math> eine [[freie abelsche Gruppe]] vom [[Rang einer abelschen Gruppe|Rang]] <math>m</math>.

Die [[beschränkte Menge]]
:<math>\mathcal{F}_\Gamma := \left\{\left.\textstyle\sum\limits_{i=1}^m r_i b_i \ \right|\, 0\leq r_i < 1\right\}</math>
heißt ''Grundmasche'' oder ''Fundamentalmasche'' von <math>\Gamma</math>. Sie spannt im <math>\mathbb{R}^n</math> einen <math>m</math>-dimensionalen [[Untervektorraum]]
:<math>R := \left\{\left.\textstyle\sum\limits_{i=1}^m r_i b_i \ \right|\, r_i\in\mathbb{R}\right\}</math>
auf und bildet darin ein [[Intervall (Mathematik)#n-dimensionales Intervall|rechtsoffenes]] <math>m</math>-dimensionales [[Parallelepiped]]. Die Basis <math>\{b_1, b_2, \ldots, b_m\}</math> des Gitters ist eine [[Basis (Vektorraum)|Basis]] dieses Vektorraums.

Durch das Gitter <math>\Gamma</math> wird auf <math>\mathbb{R}^n</math> eine [[Äquivalenzrelation]] <math>\sim_\Gamma</math> wie folgt definiert:
:<math>x\sim_\Gamma y \quad:\Leftrightarrow \quad y-x\in\Gamma</math>.
Jedes Element von <math>R</math> ist zu genau einem Element aus der Grundmasche äquivalent.
Jede Äquivalenzklasse hat also genau einen Repräsentanten in der Grundmasche.

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

In diesem Fall kann der ganze <math>\mathbb{R}^n</math> mit Maschen der Form der Grundmasche [[Parkettierung|parkettiert]] werden. Jedoch sind auch Formen interessant, die kein [[Parallelepiped]] sind. Man spricht dann von einer ''Fundamentalregion''.

Ein Gitter <math>\Gamma</math> heißt ''ganz'', falls für alle <math>x, y \in \Gamma</math>
das [[Skalarprodukt]] <math> \langle x , y \rangle </math> eine [[ganze Zahl]] ist.
Ist sogar <math> \langle x , x \rangle \in 2\mathbb{Z}</math> für alle <math>x \in \Gamma</math>, so nennt man das Gitter <math>\Gamma</math> ''gerade'' (gerade Gitter sind automatisch ganz). Ein ganzes Gitter <math>\Gamma</math> heißt ''unimodular'', wenn die Gitterdiskriminante (s. u.) im Betrag 1 ist. Ein ganzes Gitter heißt ''Wurzelgitter'', falls <math>\Gamma=\langle \{v\in \Gamma : \langle v,v \rangle =2 \} \rangle_{\mathbb{Z}}</math>. Hierbei heißt <math>\{v\in \Gamma : \langle v,v \rangle =2\}</math> die Menge der Wurzeln <math>\Gamma</math>. Für ein Gitter <math>\Gamma</math> in <math>\mathbb{R}^n</math> heißt <math>\Gamma^*=\{x\in \mathbb{R}^n : \langle x,y\rangle \in \mathbb{Z}\, \forall y\in \Gamma\}</math> das ''duale Gitter''.

'''Beispiele:'''
# Das Gitter in der Abbildung hat die Basisvektoren <math>b_1=\left(\tfrac{2}{3},\tfrac{1}{3}\right)</math> und <math>b_2=\left(\tfrac{1}{3},-\tfrac{1}{3}\right)</math>. Es ist weder ganz noch gerade.
# Das Gitter mit Basisvektoren <math>b_1=(3,1)</math> und <math>b_2=(1,-1)</math> ist sowohl ganz als auch gerade.
# Das duale Gitter von <math>\Gamma=\mathbb{Z}^n</math> ist <math>\mathbb{Z}^n</math>.

== Eigenschaften ==

* Sei <math>\Gamma</math> eine Untergruppe von <math>\mathbb{R}^n</math>. Dann ist <math>\Gamma</math> genau dann ein Gitter, wenn <math>\Gamma</math> diskret und kokompakt ist.

== Gitter in der komplexen Zahlenebene ==
{{Hauptartikel|Fundamentalbereich}}
Indem man die komplexe Zahlenebene <math>\mathbb C</math> als reellen Vektorraum auffasst, kann man von Gittern in <math>\mathbb C</math> sprechen; sie sind freie abelsche Gruppen vom Rang 2. Sie spielen eine zentrale Rolle in der Theorie der [[Elliptische Funktion|elliptischen Funktionen]] (Periodengitter) und [[Elliptische Kurve|elliptischen Kurven]].

Ist allgemeiner <math>g</math> eine [[natürliche Zahl]], so stehen Gitter im reell <math>2g</math>-dimensionalen Raum <math>\mathbb C^g</math> in Beziehung zu [[Komplexer Torus|komplexen Tori]] und [[Abelsche Varietät|abelschen Varietäten]].

== Gitter in Lie-Gruppen ==

Eine Untergruppe <math>\Gamma\subset G</math> einer [[Topologische Gruppe|topologischen Gruppe]] <math>G</math> heißt [[diskrete Untergruppe]], wenn es zu jedem <math>\gamma\in\Gamma</math> eine [[Umgebung (Mathematik)|offene Umgebung]] <math>U_{\gamma}\subset G</math> mit
:<math>U_{\gamma}\cap\Gamma=\left\{\gamma\right\}</math>
gibt.

Wenn <math>G</math> eine [[lokalkompakte Gruppe]] mit [[Haarsches Maß|Haarschem Maß]] <math>\mu</math> ist, dann heißt eine diskrete Untergruppe <math>\Gamma\subset G</math> ein ''Gitter'', falls der Quotient <math>G/\Gamma</math> endliches Volumen (bzgl. des Haarschen Maßes) hat.

Ein Gitter heißt ''uniform'' oder ''kokompakt'', falls <math>G/\Gamma</math> kompakt ist.

Gitter in [[Lie-Gruppe]]n spielen eine wichtige Rolle in [[Geometrisierung von 3-Mannigfaltigkeiten|Thurstons Geometrisierungsprogramm]].

== Beispiele ==
* Sei <math>\Gamma</math> das zur Basismatrix <math>\begin{pmatrix}1 & \tfrac{1}{2} \\ 0 & \sqrt{2}\end{pmatrix}</math> gehörige Gitter vom Rang 2. Dann ist <math>\det\Gamma = \sqrt{2}</math>.
* Sei <math>\Gamma:=\mathbb{Z}^n\subseteq\mathbb{R}^n</math>. Dann ist die Grundmasche von <math>\Gamma</math> der <math>n</math>-dimensionale [[Hyperwürfel]] <math>\mathcal{F}_\Gamma=[0,1)^n</math>, und es gilt z. B. <math>\left(\tfrac{3}{2}, 0, \dots, 0\right)\equiv_\Gamma \left(-\tfrac{7}{2}, 1, \dots, 1\right)</math>.
* Der Ring der [[Gaußsche Zahl|gaußschen Zahlen]] <math>\mathbb{Z}[\mathrm{i}]</math> ist ein Gitter in <math>\mathbb{C}</math>.
* Der Ring der [[Hurwitzquaternion]]en ist ein Gitter im [[Schiefkörper]] <math>\mathbb{H}</math> der [[Quaternion]]en.
* Das [[Leech-Gitter]] ist ein besonderes Gitter im <math>\R^{24}.</math>
* Das [[E8-Gitter|E<sub>8</sub>-Gitter]] ist ein unimodulares Gitter im <math>\mathbb{R}^8</math>.

== Gitterdiskriminante ==
Eine Kenngröße zur Klassifikation von Gittern ist die Gitterdiskriminante. Sie berechnet sich als Volumen der Grundmasche.
:<math>d(\Gamma) = \operatorname{vol}(b_1,b_2,\ldots,b_m)</math>
Bei Gittern im euklidischen Raum mit der Basismatrix <math>B</math> entspricht dies der Formel
:<math>d(\Gamma) = \sqrt{\det\left(B^TB\right)}</math>
Hat <math>B</math> vollen Rang, so lässt sich dies zu folgendem Ausdruck vereinfachen:
:<math>d(\Gamma) = \left|\det\left(B\right)\right|</math>
Als [[Invariante (Mathematik)|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 [[Asymmetrisches Kryptosystem|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 <math>\mathbb{Z}^n\subset \mathbb{R}^n</math> und der Gruppenhomomorphismus <math>\rho : \mathbb{Z}^n\to (\mathbb{Z}/2\mathbb{Z})^n=\mathbb{F}_2^n, \, (a_1,...,a_n)\mapsto (a_1 \operatorname{mod} 2, ..., a_n \operatorname{mod} 2)</math> betrachtet. Sei <math>C</math> nun ein binärer <math>[n,k,d]</math>-Code. Da <math>\mathbb{F}_2^n/C\cong \mathbb{F}_2^{n-k}</math>, ist <math>C</math> eine Untergruppe von <math>\mathbb{F}_2^n</math> vom Index <math>2^{n-k}</math>. Man nennt <math>\Gamma_C=\tfrac{1}{\sqrt{2}}\rho^{-1}(C)</math> das zu <math>C</math> gehörige Codegitter. Aus dem erweiterten [[Hamming-Code]] kann das <math>E_8</math>-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 (Kryptologe)|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.): [http://www.springer.com/computer/security+and+cryptology/book/978-3-642-02294-4?changeHeader ''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]]: [http://www.ams.org/notices/200010/fea-elkies-1.pdf ''Lattices, linear codes, and invariants.'' Part I] (PDF; 156 kB) Notices AMS 47 (2000), No. 10, S. 1238–1245 [http://www.ams.org/notices/200011/fea-elkies-2.pdf 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 [http://www.mathematik.uni-bielefeld.de/~rehmann/ECM/cdrom/3ecm/pdfs/pant3/lenstra.pdf hier] (PDF; 165 kB)
* Oded Regev: [http://www.cs.tau.ac.il/~odedr/teaching/lattices_fall_2004/ ''Lattices in Computer Science.''] Tel-Aviv University, 2004
* Daniele Micciancio: [http://cseweb.ucsd.edu/classes/sp07/cse206a/ ''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 [http://www.math.leidenuniv.nl/en/reports/1102/223/ hier] oder [http://library.msri.org/books/Book44/files/06hwl.pdf dort] (PDF; 368 kB)
* [[Daniel J. Bernstein]]: [http://pqcrypto.org/lattice.html Bibliography on Lattice-based public-key cryptography]
* Keita Xagawa: [http://xagawa.net/bib-lattice/ Bibliography on Lattice-based Cryptosystems]

== Siehe auch ==
* [[Raumgruppe]]
* Spezielle Gitter werden nach [[Richard Dedekind|Dedekind]] bei der Untersuchung algebraisch ganzer Zahlen verwendet. Siehe dazu [[Ordnung (algebraische Zahlentheorie)]]

== Einzelnachweise ==
<references />

[[Kategorie:Geometrische Gruppentheorie]]

Gitter (Mathematik) - Versionsgeschichte

imported>FlMcc: /* growthexperiments-addlink-summary-summary:3|0|0 */