Namespaces
Variants
Actions

Flatness theorem

From Encyclopedia of Mathematics
Jump to: navigation, search

2010 Mathematics Subject Classification: Primary: 11H06 Secondary: 11D07 [MSN][ZBL]

(in the geometry of numbers)

Let $K$ be a closed bounded convex set in $\mathbf{R}^n$> of non-zero volume. If the width of $K$ is at least $n^{5/2}/2$, then $K$ contains an element of the integer lattice $\mathbf{Z}^n$.

Here, the width of $K$ (with respect to $\mathbf{Z}^n$) is the minimum width of $K$ along any non-zero integer vector. Here the "width" of $K$ along a vector $v$ in $\mathbf{R}^n$ is $$ \max \{ \langle x,v \rangle : x \in K \} - \min \{ \langle x,v \rangle : x \in K \} $$

The width of $K$ with respect to $\mathbf{Z}^n$ is greater or equal than the geometric width of $K$, which is the minimum width of $K$ along all unit-length vectors.

If $K$ is a rational polyhedron, i.e. is defined by a system of linear inequalities with rational coefficients, then the "non-zero volume condition" in the flatness theorem can be dispensed with. The flatness theorem finds application in, e.g., the Frobenius problem.

References

[a1] J. Hastad, "Dual vectors and lower bounds for the nearest lattice point problem" Combinatorica , 8 (1988) pp. 75–81
[a2] J. Lagarias, H.W. Lenstra, C.P. Schnorr, "Korkine–Zolotarev bases and successive minima of a lattice and its reciprocal lattice" Combinatorica , 10 (1990) pp. 333–348
How to Cite This Entry:
Flatness theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Flatness_theorem&oldid=43101
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article