Gitter (Mathematik) - LinkFang.de





Gitter (Mathematik)


Dieser Artikel befasst sich mit dem Gitter im mathematischen Sinne, andere Bedeutungen unter Gitter (Begriffsklärung)

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.

Gitter im euklidischen Raum

Es seien [math]b_1, b_2, \ldots, b_m[/math] linear unabhängige Vektoren des 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 von [math]\R^n[/math] ist [math]\Gamma[/math] eine freie abelsche Gruppe vom 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 \lt 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 rechtsoffenes [math]m[/math]-dimensionales Parallelepiped. Die Basis [math]\{b_1, b_2, \ldots, b_m\}[/math] des Gitters ist eine Basis dieses Vektorraums.

Durch das Gitter [math]\Gamma[/math] wird auf [math]\mathbb{R}^n[/math] eine Äquivalenzrelation 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 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] x \cdot y [/math] eine ganze Zahl ist. Ist darüber hinaus [math]x \cdot x \in 2\mathbb{Z}[/math], so nennt man das Gitter [math]\Gamma[/math] gerade.

Beispiele:

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

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 elliptischen Funktionen und 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 komplexen Tori und abelschen Varietäten.

Gitter in Lie-Gruppen

Eine Untergruppe [math]\Gamma\subset G[/math] einer topologischen Gruppe [math]G[/math] heißt diskret, wenn es zu jedem [math]\gamma\in\Gamma[/math] eine 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 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-Gruppen spielen eine wichtige Rolle in 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](\tfrac{3}{2}, 0, \dots, 0)\equiv_\Gamma (-\tfrac{7}{2}, 1, \dots, 1)[/math].
  • Der Ring der gaußschen Zahlen [math]\mathbb{Z}[\mathrm{i}][/math] ist ein Gitter in [math]\mathbb{C}[/math].
  • Der Ring der Hurwitzquaternionen ist ein Gitter im Schiefkörper [math]\mathbb{H}[/math] der Quaternionen.

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{\left|\det\left(B^TB\right)\right|}[/math]

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.

Literatur

Weblinks

Siehe auch


Kategorien: Gruppentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Gitter (Mathematik) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.