www.wikidata.de-de.nina.az

Gitter Mathematik Ein Gitter engl lattice in der Mathematik ist eine diskrete Untergruppe des euklidischen Raums Gitter

Gitter (Mathematik)

Ein Gitter (engl. lattice) in der Mathematik ist eine diskrete Untergruppe des euklidischen Raums. Gitter finden innermathematisch Verwendung u. a. in der Gruppentheorie, der Zahlentheorie, der Geometrie und bei Approximationsfragestellungen. Außermathematisch werden Gitter in der Chemie und Physik z. B. in der Kristallographie oder im Zusammenhang mit Ionengittern studiert.

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

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

Gitter im euklidischen Raum Bearbeiten

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). Ein ganzes Gitter heißt unimodular, wenn die Gitterdiskriminante (s. u.) im Betrag 1 ist. Ein ganzes Gitter heißt Wurzelgitter, falls . Hierbei heißt die Menge der Wurzeln . Für ein Gitter in heißt das duale Gitter.

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.
  3. Das duale Gitter von ist .

Eigenschaften Bearbeiten

  • Sei eine Untergruppe von . Dann ist genau dann ein Gitter, wenn diskret und kokompakt ist.

Gitter in der komplexen Zahlenebene Bearbeiten

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 (Periodengitter) 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-Gruppen Bearbeiten

Eine Untergruppe einer topologischen Gruppe heißt diskrete Untergruppe, 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.

Beispiele Bearbeiten

Gitterdiskriminante Bearbeiten

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.

Gitterreduktion Bearbeiten

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.

Codegitter Bearbeiten

Aus linearen Binärcodes können Gitter konstruiert werden. Dazu wird das Standardgitter und der Gruppenhomomorphismus betrachtet. Sei nun ein binärer -Code. Da , ist eine Untergruppe von vom Index . Man nennt das zu gehörige Codegitter. Aus dem erweiterten Hamming-Code kann das -Gitter konstruiert werden.

Literatur Bearbeiten

  • 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.
  • 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 Bearbeiten

Siehe auch Bearbeiten

Einzelnachweise Bearbeiten

  1. Vgl. Beweis des Zwei-Quadrate-Satzes mit dem Gitterpunktsatz von Minkowski.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Ein Gitter engl lattice in der Mathematik ist eine diskrete Untergruppe des euklidischen Raums Gitter finden innermathematisch Verwendung u a in der Gruppentheorie der Zahlentheorie 1 der Geometrie und bei Approximationsfragestellungen Aussermathematisch werden Gitter in der Chemie und Physik z B in der Kristallographie oder im Zusammenhang mit Ionengittern studiert Ausschnitt eines Gitters Die blauen Punkte gehoren zum Gitter Die einzelnen Elemente eines Gitters heissen Gitterpunkte oder Gittervektoren Inhaltsverzeichnis 1 Gitter im euklidischen Raum 2 Eigenschaften 3 Gitter in der komplexen Zahlenebene 4 Gitter in Lie Gruppen 5 Beispiele 6 Gitterdiskriminante 7 Gitterreduktion 8 Codegitter 9 Literatur 10 Weblinks 11 Siehe auch 12 EinzelnachweiseGitter im euklidischen Raum BearbeitenEs seien b 1 b 2 b m displaystyle b 1 b 2 ldots b m nbsp linear unabhangige Vektoren des euklidischen Vektorraums R n displaystyle mathbb R n nbsp Dann nennt man G b 1 b m Z i 1 m g i b i g i Z 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 nbsp ein Gitter mit Basis b 1 b 2 b m displaystyle b 1 b 2 ldots b m nbsp vom Rang m displaystyle m nbsp Die aus den Vektoren b 1 b m displaystyle b 1 dots b m nbsp gebildete Matrix B b 1 b m R n m displaystyle B b 1 dots b m in mathbb R n times m nbsp heisst Basismatrix von G displaystyle Gamma nbsp Die Basis ist durch das Gitter nicht festgelegt Jede Basis von G displaystyle Gamma nbsp hat jedoch denselben Rang m displaystyle m nbsp Als Untergruppe der additiven Gruppe von R n displaystyle mathbb R n nbsp ist G displaystyle Gamma nbsp eine freie abelsche Gruppe vom Rang m displaystyle m nbsp Die beschrankte Menge F G i 1 m r i b i 0 r i lt 1 displaystyle mathcal F Gamma left left textstyle sum limits i 1 m r i b i right 0 leq r i lt 1 right nbsp heisst Grundmasche oder Fundamentalmasche von G displaystyle Gamma nbsp Sie spannt im R n displaystyle mathbb R n nbsp einen m displaystyle m nbsp dimensionalen Untervektorraum R i 1 m r i b i r i R displaystyle R left left textstyle sum limits i 1 m r i b i right r i in mathbb R right nbsp auf und bildet darin ein rechtsoffenes m displaystyle m nbsp dimensionales Parallelepiped Die Basis b 1 b 2 b m displaystyle b 1 b 2 ldots b m nbsp des Gitters ist eine Basis dieses Vektorraums Durch das Gitter G displaystyle Gamma nbsp wird auf R n displaystyle mathbb R n nbsp eine Aquivalenzrelation G displaystyle sim Gamma nbsp wie folgt definiert x G y y x G displaystyle x sim Gamma y quad Leftrightarrow quad y x in Gamma nbsp Jedes Element von R displaystyle R nbsp ist zu genau einem Element aus der Grundmasche aquivalent Jede Aquivalenzklasse hat also genau einen Reprasentanten in der Grundmasche Zu einem y R n R displaystyle y in mathbb R n setminus R nbsp gibt es kein x R displaystyle x in R nbsp mit y x G displaystyle y x in Gamma nbsp Da sich das Interessante also nur im Unterraum R displaystyle R nbsp abspielt und dieser isomorph zu R m displaystyle mathbb R m nbsp ist betrachten die meisten Autoren nur den Fall der Gleichheit m n displaystyle m n nbsp Gitter mit vollem Rang In diesem Fall kann der ganze R n displaystyle mathbb R n nbsp 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 G displaystyle Gamma nbsp heisst ganz falls fur alle x y G displaystyle x y in Gamma nbsp das Skalarprodukt x y displaystyle langle x y rangle nbsp eine ganze Zahl ist Ist sogar x x 2 Z displaystyle langle x x rangle in 2 mathbb Z nbsp fur alle x G displaystyle x in Gamma nbsp so nennt man das Gitter G displaystyle Gamma nbsp gerade gerade Gitter sind automatisch ganz Ein ganzes Gitter G displaystyle Gamma nbsp heisst unimodular wenn die Gitterdiskriminante s u im Betrag 1 ist Ein ganzes Gitter heisst Wurzelgitter falls G v G v v 2 Z displaystyle Gamma langle v in Gamma langle v v rangle 2 rangle mathbb Z nbsp Hierbei heisst v G v v 2 displaystyle v in Gamma langle v v rangle 2 nbsp die Menge der Wurzeln G displaystyle Gamma nbsp Fur ein Gitter G displaystyle Gamma nbsp in R n displaystyle mathbb R n nbsp heisst G x R n x y Z y G displaystyle Gamma x in mathbb R n langle x y rangle in mathbb Z forall y in Gamma nbsp das duale Gitter Beispiele Das Gitter in der Abbildung hat die Basisvektoren b 1 2 3 1 3 displaystyle b 1 left tfrac 2 3 tfrac 1 3 right nbsp und b 2 1 3 1 3 displaystyle b 2 left tfrac 1 3 tfrac 1 3 right nbsp Es ist weder ganz noch gerade Das Gitter mit Basisvektoren b 1 3 1 displaystyle b 1 3 1 nbsp und b 2 1 1 displaystyle b 2 1 1 nbsp ist sowohl ganz als auch gerade Das duale Gitter von G Z n displaystyle Gamma mathbb Z n nbsp ist Z n displaystyle mathbb Z n nbsp Eigenschaften BearbeitenSei G displaystyle Gamma nbsp eine Untergruppe von R n displaystyle mathbb R n nbsp Dann ist G displaystyle Gamma nbsp genau dann ein Gitter wenn G displaystyle Gamma nbsp diskret und kokompakt ist Gitter in der komplexen Zahlenebene Bearbeiten Hauptartikel Fundamentalbereich Indem man die komplexe Zahlenebene C displaystyle mathbb C nbsp als reellen Vektorraum auffasst kann man von Gittern in C displaystyle mathbb C nbsp sprechen sie sind freie abelsche Gruppen vom Rang 2 Sie spielen eine zentrale Rolle in der Theorie der elliptischen Funktionen Periodengitter und elliptischen Kurven Ist allgemeiner g displaystyle g nbsp eine naturliche Zahl so stehen Gitter im reell 2 g displaystyle 2g nbsp dimensionalen Raum C g displaystyle mathbb C g nbsp in Beziehung zu komplexen Tori und abelschen Varietaten Gitter in Lie Gruppen BearbeitenEine Untergruppe G G displaystyle Gamma subset G nbsp einer topologischen Gruppe G displaystyle G nbsp heisst diskrete Untergruppe wenn es zu jedem g G displaystyle gamma in Gamma nbsp eine offene Umgebung U g G displaystyle U gamma subset G nbsp mit U g G g displaystyle U gamma cap Gamma left gamma right nbsp gibt Wenn G displaystyle G nbsp eine lokalkompakte Gruppe mit Haarschem Mass m displaystyle mu nbsp ist dann heisst eine diskrete Untergruppe G G displaystyle Gamma subset G nbsp ein Gitter falls der Quotient G G displaystyle G Gamma nbsp endliches Volumen bzgl des Haarschen Masses hat Ein Gitter heisst uniform oder kokompakt falls G G displaystyle G Gamma nbsp kompakt ist Gitter in Lie Gruppen spielen eine wichtige Rolle in Thurstons Geometrisierungsprogramm Beispiele BearbeitenSei G displaystyle Gamma nbsp das zur Basismatrix 1 1 2 0 2 displaystyle begin pmatrix 1 amp tfrac 1 2 0 amp sqrt 2 end pmatrix nbsp gehorige Gitter vom Rang 2 Dann ist det G 2 displaystyle det Gamma sqrt 2 nbsp Sei G Z n R n displaystyle Gamma mathbb Z n subseteq mathbb R n nbsp Dann ist die Grundmasche von G displaystyle Gamma nbsp der n displaystyle n nbsp dimensionale Hyperwurfel F G 0 1 n displaystyle mathcal F Gamma 0 1 n nbsp und es gilt z B 3 2 0 0 G 7 2 1 1 displaystyle left tfrac 3 2 0 dots 0 right equiv Gamma left tfrac 7 2 1 dots 1 right nbsp Der Ring der gaussschen Zahlen Z i displaystyle mathbb Z mathrm i nbsp ist ein Gitter in C displaystyle mathbb C nbsp Der Ring der Hurwitzquaternionen ist ein Gitter im Schiefkorper H displaystyle mathbb H nbsp der Quaternionen Das Leech Gitter ist ein besonderes Gitter im R 24 displaystyle mathbb R 24 nbsp Das E8 Gitter ist ein unimodulares Gitter im R 8 displaystyle mathbb R 8 nbsp Gitterdiskriminante BearbeitenEine Kenngrosse zur Klassifikation von Gittern ist die Gitterdiskriminante Sie berechnet sich als Volumen der Grundmasche d G vol b 1 b 2 b m displaystyle d Gamma operatorname vol b 1 b 2 ldots b m nbsp Bei Gittern im euklidischen Raum mit der Basismatrix B displaystyle B nbsp entspricht dies der Formel d G det B T B displaystyle d Gamma sqrt det left B T B right nbsp Hat B displaystyle B nbsp vollen Rang so lasst sich dies zu folgendem Ausdruck vereinfachen d G det B displaystyle d Gamma left det left B right right nbsp Als Invariante ist der Wert der Gitterdiskriminante unabhangig von der gewahlten Basis Gitterreduktion BearbeitenDie 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 Lovasz berechnet in polynomieller Zeit eine sogenannte LLL reduzierte Basis mit deren Hilfe man beweisbar kurze Gittervektoren erhalt In der Tat liegt die Lange des ersten Vektors einer LLL reduzierten Basis nahe an der Lange des kurzesten nichttrivialen Gittervektors Der LLL Algorithmus hat zahlreiche Anwendungen in der Kryptoanalyse von asymmetrischen Verschlusselungsverfahren wie dem RSA Kryptosystem und dem Merkle Hellman Kryptosystem gefunden Codegitter BearbeitenAus linearen Binarcodes konnen Gitter konstruiert werden Dazu wird das Standardgitter Z n R n displaystyle mathbb Z n subset mathbb R n nbsp und der Gruppenhomomorphismus r Z n Z 2 Z n F 2 n a 1 a n a 1 mod 2 a n mod 2 displaystyle 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 nbsp betrachtet Sei C displaystyle C nbsp nun ein binarer n k d displaystyle n k d nbsp Code Da F 2 n C F 2 n k displaystyle mathbb F 2 n C cong mathbb F 2 n k nbsp ist C displaystyle C nbsp eine Untergruppe von F 2 n displaystyle mathbb F 2 n nbsp vom Index 2 n k displaystyle 2 n k nbsp Man nennt G C 1 2 r 1 C displaystyle Gamma C tfrac 1 sqrt 2 rho 1 C nbsp das zu C displaystyle C nbsp gehorige Codegitter Aus dem erweiterten Hamming Code kann das E 8 displaystyle E 8 nbsp Gitter konstruiert werden Literatur BearbeitenGudrun 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 amp Springer 2002 ISBN 978 0 7923 7688 0 Phong Q Nguyen Brigitte Vallee Hrsg 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 BearbeitenNoam 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 Birkhauser 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 CryptosystemsSiehe auch BearbeitenRaumgruppe 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 Einzelnachweise Bearbeiten Vgl Beweis des Zwei Quadrate Satzes mit dem Gitterpunktsatz von Minkowski Abgerufen von https de wikipedia org w index php title Gitter Mathematik amp oldid 226104007