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

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

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

Gitter im euklidischen RaumBearbeiten

Es seien   linear unabhängige Vektoren des euklidischen Vektorraums  . Dann nennt man

 

ein Gitter mit Basis   vom Rang  . Die aus den Vektoren   gebildete Matrix   heißt Basismatrix von  . Die Basis ist durch das Gitter nicht festgelegt. Jede Basis von   hat jedoch denselben Rang  . Als Untergruppe der additiven Gruppe von   ist   eine freie abelsche Gruppe vom Rang  .

Die beschränkte Menge

 

heißt Grundmasche oder Fundamentalmasche von  . Sie spannt im   einen  -dimensionalen Untervektorraum

 

auf und bildet darin ein rechtsoffenes  -dimensionales Parallelepiped. Die Basis   des Gitters ist eine Basis dieses Vektorraums.

Durch das Gitter   wird auf   eine Äquivalenzrelation wie folgt definiert:

 .

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

Zu einem   gibt es kein   mit  . Da sich das Interessante also nur im Unterraum   abspielt und dieser isomorph zu   ist, betrachten die meisten Autoren nur den Fall der Gleichheit   (Gitter mit vollem Rang).

In diesem Fall kann der ganze   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   heißt ganz, falls für alle   das Skalarprodukt   eine ganze Zahl ist. Ist sogar   für alle  , so nennt man das Gitter   gerade (gerade Gitter sind automatisch ganz).

Beispiele:

  1. Das Gitter in der Abbildung hat die Basisvektoren   und  . Es ist weder ganz noch gerade.
  2. Das Gitter mit Basisvektoren   und   ist sowohl ganz als auch gerade.

Gitter in der komplexen ZahlenebeneBearbeiten

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 und elliptischen Kurven.

Ist allgemeiner   eine natürliche Zahl, so stehen Gitter im reell  -dimensionalen Raum   in Beziehung zu komplexen Tori und abelschen Varietäten.

Gitter in Lie-GruppenBearbeiten

Eine Untergruppe   einer topologischen Gruppe   heißt diskret, wenn es zu jedem   eine offene Umgebung   mit

 

gibt.

Wenn   eine lokalkompakte Gruppe mit Haarschem Maß   ist, dann heißt eine diskrete Untergruppe   ein Gitter, falls der Quotient   endliches Volumen (bzgl. des Haarschen Maßes) hat.

Ein Gitter heißt uniform oder kokompakt, falls   kompakt ist.

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

BeispieleBearbeiten

  • Sei   das zur Basismatrix   gehörige Gitter vom Rang 2. Dann ist  .
  • Sei  . Dann ist die Grundmasche von   der  -dimensionale Hyperwürfel  , und es gilt z. B.  .
  • Der Ring der gaußschen Zahlen   ist ein Gitter in  .
  • Der Ring der Hurwitzquaternionen ist ein Gitter im Schiefkörper   der Quaternionen.
  • Das Leech-Gitter ist ein besonderes Gitter im  

GitterdiskriminanteBearbeiten

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

 

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

 

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

 

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

GitterreduktionBearbeiten

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.

LiteraturBearbeiten

WeblinksBearbeiten

Siehe auchBearbeiten