Grid (math)

Section of a grid. The blue dots belong to the grid.

A grid (engl. Lattice ) in the mathematics is a discrete subset of Euclidean space. Grids are used u. a. in group theory , geometry and approximation issues.

The individual elements of a grid are called grid points or grid vectors.

Lattice in Euclidean space

Let there be linearly independent vectors of the Euclidean vector space . Then you call ${\ displaystyle b_ {1}, b_ {2}, \ ldots, b_ {m}}$ ${\ displaystyle \ mathbb {R} ^ {n}}$

{\ 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 \}}

a lattice with a base of rank . The matrix formed from the vectors is called the base matrix of . The grid does not define the basis. However, each base of has the same rank . As a subgroup of the additive group of is a free Abelian group of rank . ${\ displaystyle \ {b_ {1}, b_ {2}, \ ldots, b_ {m} \}}$ ${\ displaystyle m}$ ${\ displaystyle b_ {1}, \ dots, b_ {m}}$ ${\ displaystyle B: = (b_ {1}, \ dots, b_ {m}) \ in \ mathbb {R} ^ {n \ times m}}$ ${\ displaystyle \ Gamma}$ ${\ displaystyle \ Gamma}$ ${\ displaystyle m}$ ${\ displaystyle \ mathbb {R} ^ {n}}$ ${\ displaystyle \ Gamma}$ ${\ displaystyle m}$

The limited amount

{\ displaystyle {\ mathcal {F}} _ {\ Gamma}: = \ left \ {\ left. \ textstyle \ sum \ limits _ {i = 1} ^ {m} r_ {i} b_ {i} \ \ right | \, 0 \ leq r_ {i} <1 \ right \}}

is called the basic mesh or fundamental mesh of . It spans in a -dimensional sub-vector space ${\ displaystyle \ Gamma}$ ${\ displaystyle \ mathbb {R} ^ {n}}$ ${\ displaystyle m}$

{\ displaystyle R: = \ left \ {\ left. \ textstyle \ sum \ limits _ {i = 1} ^ {m} r_ {i} b_ {i} \ \ right | \, r_ {i} \ in \ mathbb {R} \ right \}}

and forms a right- dimensional parallelepiped open to the right . The basis of the lattice is a basis of this vector space. ${\ displaystyle m}$ ${\ displaystyle \ {b_ {1}, b_ {2}, \ ldots, b_ {m} \}}$

Through the grating is on an equivalence relation defined as follows: ${\ displaystyle \ Gamma}$ ${\ displaystyle \ mathbb {R} ^ {n}}$

{\ displaystyle x \ sim _ {\ Gamma} y \ quad: \ Leftrightarrow \ quad yx \ in \ Gamma}

.

Each element of is equivalent to exactly one element from the basic mesh. Each equivalence class has exactly one representative in the basic mesh. ${\ displaystyle R}$

A there is no with . Since the interesting thing only takes place in the subspace and this is isomorphic , most authors only consider the case of equality (grid with full rank ). ${\ displaystyle y \ in \ mathbb {R} ^ {n} \ setminus R}$ ${\ displaystyle x \ in R}$ ${\ displaystyle yx \ in \ Gamma}$ ${\ displaystyle R}$ ${\ displaystyle \ mathbb {R} ^ {m}}$ ${\ displaystyle m = n}$

In this case, the whole can of elementary mesh with a mesh shape parquetted be. However, shapes that are not parallelepiped are also interesting . One then speaks of a fundamental region . ${\ displaystyle \ mathbb {R} ^ {n}}$

A grid is called whole if the scalar product is an integer for all of them . Is even for everyone , the grid is called straight (straight grids are automatically complete). ${\ displaystyle \ Gamma}$ ${\ displaystyle x, y \ in \ Gamma}$ ${\ displaystyle \ langle x, y \ rangle}$ ${\ displaystyle \ langle x, x \ rangle \ in 2 \ mathbb {Z}}$ ${\ displaystyle x \ in \ Gamma}$ ${\ displaystyle \ Gamma}$

Examples:

The grid in the figure has the basis vectors and . It is neither whole nor straight. ${\ displaystyle b_ {1} = ({\ tfrac {2} {3}}, {\ tfrac {1} {3}})}$ ${\ displaystyle b_ {2} = ({\ tfrac {1} {3}}, - {\ tfrac {1} {3}})}$
The lattice with basis vectors and is both whole and straight. ${\ displaystyle b_ {1} = (3,1)}$ ${\ displaystyle b_ {2} = (1, -1)}$

Grid in the complex number plane

By considering the complex number plane as a real vector space, one can speak of lattices in ; they are free Abelian groups of rank 2. They play a central role in the theory of elliptic functions and elliptic curves . ${\ displaystyle \ mathbb {C}}$ ${\ displaystyle \ mathbb {C}}$

If, more generally, is a natural number, then lattices in real- dimensional space are related to complex Tori and Abelian varieties . ${\ displaystyle g}$ ${\ displaystyle 2g}$ ${\ displaystyle \ mathbb {C} ^ {g}}$

Lattice in Lie groups

A subgroup of a topological group is discrete subgroup , if for every one open environment with ${\ displaystyle \ Gamma \ subset G}$ ${\ displaystyle G}$ ${\ displaystyle \ gamma \ in \ Gamma}$ ${\ displaystyle U _ {\ gamma} \ subset G}$

{\ displaystyle U _ {\ gamma} \ cap \ Gamma = \ left \ {\ gamma \ right \}}

gives.

If a locally compact group is with Haar's measure , then a discrete subgroup is called a lattice if the quotient has finite volume (with respect to Haar's measure). ${\ displaystyle G}$ ${\ displaystyle \ mu}$ ${\ displaystyle \ Gamma \ subset G}$ ${\ displaystyle G / \ Gamma}$

A grid is called uniform or co-compact if it is compact. ${\ displaystyle G / \ Gamma}$

Lattices in Lie groups play an important role in Thurston's geometry program .

Examples

Let the grid belonging to the basis matrix be of rank 2. Then is .

{\ displaystyle \ Gamma}

{\ displaystyle {\ begin {pmatrix} 1 & {\ tfrac {1} {2}} \\ 0 & {\ sqrt {2}} \ end {pmatrix}}}

{\ displaystyle \ det \ Gamma = {\ sqrt {2}}}

Be . Then the basic mesh is of the -dimensional hypercube , and we have e.g. B. . ${\ displaystyle \ Gamma: = \ mathbb {Z} ^ {n} \ subseteq \ mathbb {R} ^ {n}}$ ${\ displaystyle \ Gamma}$ ${\ displaystyle n}$ ${\ displaystyle {\ mathcal {F}} _ {\ Gamma} = [0,1) ^ {n}}$ ${\ displaystyle ({\ tfrac {3} {2}}, 0, \ dots, 0) \ equiv _ {\ Gamma} (- {\ tfrac {7} {2}}, 1, \ dots, 1)}$

The ring of Gaussian numbers is a grid in .

{\ displaystyle \ mathbb {Z} [\ mathrm {i}]}

{\ displaystyle \ mathbb {C}}

The ring of the Hurwitz quaternions is a lattice in the oblique body of the quaternions .

{\ displaystyle \ mathbb {H}}

The Leech grid is a special grid in the

{\ displaystyle \ mathbb {R} ^ {24}.}

Lattice discriminator

One parameter for the classification of grids is the grid discriminant. It is calculated as the volume of the basic mesh.

{\ displaystyle d (\ Gamma) = \ operatorname {vol} (b_ {1}, b_ {2}, \ ldots, b_ {m})}

For grids in Euclidean space with the base matrix , this corresponds to the formula ${\ displaystyle B}$

{\ displaystyle d (\ Gamma) = {\ sqrt {\ det \ left (B ^ {T} B \ right)}}}

Has full rank, this can be simplified to the following expression: ${\ displaystyle B}$

{\ displaystyle d (\ Gamma) = \ left | \ det \ left (B \ right) \ right |}

As an invariant , the value of the grid discriminant is independent of the chosen basis.

Grid reduction

Lattice reduction is the problem of calculating a basis with certain properties from a given lattice basis, such as a basis with short, almost orthogonal vectors. The LLL algorithm (after Lenstra, Lenstra and Lovász) calculates a so-called LLL-reduced basis in polynomial time, with the help of which one obtains demonstrably short lattice vectors. Indeed, the length of the first vector of an LLL reduced basis is close to the length of the shortest nontrivial lattice vector.

The LLL algorithm has found numerous applications in the cryptanalysis of asymmetric encryption methods such as the RSA cryptosystem and the Merkle-Hellman cryptosystem .

literature

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. Basic teaching of mathematical sciences 290, Springer, 3rd edition 1999, ISBN 0-387-98585-9 .
Phong Q. Nguyen, Jacques Stern : The two faces of lattices in cryptology. In: Joseph Silverman (Ed.): Cryptography and lattices (Proceedings CALC 2001), Lecture Notes Computer Science 2146, Springer 2001, pp. 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 (Eds.): The LLL algorithm. Survey and applications. Information Security and Cryptography series, Springer 2010, ISBN 978-3-642-02294-4 .

Web links

Noam Elkies : Lattices, linear codes, and invariants. Part I (PDF; 156 kB) Notices AMS 47 (2000), No. 10, pp. 1238-1245 Part II (PDF; 176 kB) Notices AMS 47 (2000), No. 11, pp. 1382-1391
Hendrik Lenstra : Flags and lattice basis reduction. in Carles Casacuberta et al. (Ed.): European Congress of Mathematics. Barcelona 2000, Vol. I. Birkhäuser 2002, ISBN 978-3-7643-6417-5 , pp. 37-52. Online here (PDF; 165 kB) or there
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 (Eds.): Algorithmic Number Theory . MSRI Publications Vol. 44, Cambridge University Press 2008, ISBN 978-0-521-80854-5 , pp. 127-181. Online here or there (PDF; 368 kB)
Daniel J. Bernstein : Bibliography on Lattice-based public-key cryptography
Keita Xagawa: Bibliography on Lattice-based Cryptosystems