Gitter (Mathematik)

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

In der Mathematik sind Gitter in gewissem Sinne regelmäßige Mengen. Sie finden u. a. Anwendung in der Gruppentheorie, der Geometrie und bei Approximationsfragestellungen.

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

Inhaltsverzeichnis

Gitter im euklidischen Raum

Es seien b_1, b_2, \ldots, b_m linear unabhängige Vektoren des euklidischen Vektorraums \mathbb{R}^n. Dann nennt man

\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 \{b_1, b_2, \ldots, b_m\} vom Rang m. Die aus den Vektoren b_1, \dots, b_m gebildete Matrix B:=(b_1,\dots,b_m)\in\mathbb{R}^{n\times m} heißt Basismatrix von Γ. Die Basis ist durch das Gitter nicht festgelegt. Jede Basis von Γ hat jedoch denselben Rang m. Als Untergruppe der additiven Gruppe von \R^n ist Γ eine freie abelsche Gruppe vom Rang m.

Die beschränkte Menge

\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 Γ. Sie spannt im \mathbb{R}^n einen m-dimensionalen Unterraum

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 m-dimensionales Parallelepiped.

Durch das Gitter Γ wird auf \mathbb{R}^n eine Äquivalenzrelation wie folgt definiert:

x\sim_\Gamma y \quad:\Leftrightarrow \quad y-x\in\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 \mathbb{R}^n \setminus R gibt es kein x \in R mit y - x\in\Gamma. Da sich das Interessante also nur im Unterraum R abspielt und dieser isomorph zu \mathbb{R}^m ist, betrachten die meisten Autoren nur den Fall der Gleichheit m = n (Gitter mit vollem Rang).

In diesem Fall kann der ganze \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 Γ heißt ganz, falls für alle x, y \in \Gamma das Skalarprodukt  x \cdot y eine ganze Zahl ist. Ist darüber hinaus x \cdot x \in 2\mathbb{Z}, so nennt man das Gitter Γ gerade.

Beispiele:

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

Gitter in der komplexen Zahlenebene

Hauptartikel: Fundamentalbereich

Indem man die komplexe Zahlenebene \mathbb C als reellen Vektorraum auffasst, kann man von Gittern in \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 g eine natürliche Zahl, so stehen Gitter im reell 2g-dimensionalen Raum \mathbb C^g in Beziehung zu komplexen Tori und abelschen Varietäten.

Beispiele

Gitterdiskriminante

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

d(\Gamma) = \operatorname{vol}(b_1,b_2,\ldots,b_m)

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

d(\Gamma) = \sqrt{\left|\det\left(B^TB\right)\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 sehr kurze Gittervektoren erhält. In der Tat liegt die Länge des ersten Vektors einer LLL-reduzierten Basis sehr nah 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.

Literatur

Weblinks

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Gitter (Begriffsklärung) — Gitter ist: ein Stadtteil von Salzgitter, siehe Salzgitter Gitter Gitter bezeichnet im Sinne einer regelmäßigen Struktur: eine Trennvorrichtung, siehe Gitter ein Heroldsbild in der Wappenkunde, siehe Gitter (Heraldik) in den Naturwissenschaften:… …   Deutsch Wikipedia

  • Gitter (Geometrie) — Ein Gitter in der Geometrie ist eine lückenlose und überlappungsfreie Partition eines Bereichs des Raumes durch eine Menge von Gitterzellen. Die Gitterzellen werden definiert durch eine Menge von Gitterpunkten, die untereinander durch eine Menge… …   Deutsch Wikipedia

  • Gitter — Gitternetz; Rastermuster; Raster; Matrix; Gefüge; Mikrostruktur; Struktur; Gatter; Zaun * * * Git|ter [ gɪtɐ], das; s, : meist aus parallel angeordneten oder gekreuzten miteinander verbundenen Stäben bestehende Vorricht …   Universal-Lexikon

  • Kubisch-flächenzentriertes Gitter — Kubisch primitiver Kristall Das kubische Kristallsystem oder auch kubisches Gitter ist ein System zur Beschreibung des Kristall Aufbaus eines Festkörpers. Es weist unter den sieben Kristallsystemen die höchste Symmetrie auf. Das Koordinatensystem …   Deutsch Wikipedia

  • Kubisches Gitter — Kubisch primitiver Kristall Das kubische Kristallsystem oder auch kubisches Gitter ist ein System zur Beschreibung des Kristall Aufbaus eines Festkörpers. Es weist unter den sieben Kristallsystemen die höchste Symmetrie auf. Das Koordinatensystem …   Deutsch Wikipedia

  • Dyadisches Gitter — Die Menge der dyadischen Elementarzellen ist eine Partitionierung des p dimensionalen Raumes und ist folgendermaßen definiert: Mit definiert man einen halboffenen Würfel im , der die Kantenlänge 2 − n hat. bezeichnet die Menge de …   Deutsch Wikipedia

  • Goldenes Dreieck (Mathematik) — Der Goldene Schnitt (lat. sectio aurea) ist ein bestimmtes Verhältnis zweier Zahlen oder Größen: Zwei Strecken stehen im Verhältnis des Goldenen Schnittes, wenn sich die größere zur kleineren Strecke verhält wie die Summe aus beiden zur größeren …   Deutsch Wikipedia

  • Konsistenz (Mathematik) — In der numerischen Mathematik ist Konsistenz eine Eigenschaft eines numerischen Verfahrens, die bedeutet, dass der Algorithmus in einer gewissen grundlegenden Weise tatsächlich das gegebene Problem löst und nicht ein anderes. Die drei in der… …   Deutsch Wikipedia

  • Modell (Mathematik) — Mathematische Modelle versuchen, die wesentlichen Parameter von Phänomenen zu erfassen und diese in einem berechenbaren Gleichungssystem, Differentialgleichungssystem o.ä. zur Vorhersage des beobachteten Systems zu nutzen. Berechenbarkeit meint… …   Deutsch Wikipedia

  • Verband (Mathematik) — In der Mathematik ist ein Verband eine bestimmte algebraische Struktur mit zwei Verknüpfungen bzw. eine halbgeordnete Menge mit bestimmten Eigenschaften. Inhaltsverzeichnis 1 Definition 2 Verbandsordnung 2.1 Hasse Diagramme …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”