6.5 Minkowski's convex body theorem

Minkowski's convex body theorem (also called Minkowski's first theorem) says: if $K$ is a convex set in $\mathbb{R}^n$ that is symmetric about the origin and its volume is larger than $2^n \det(\Lambda)$, then $K$ contains a point of the lattice $\Lambda$ other than 0. The factor $2^n$ cannot be made smaller. It is the basic tool of the geometry of numbers and the reason every lattice has a provably short nonzero vector.

What does Minkowski's theorem say exactly?

Let $\Lambda \subset \mathbb{R}^n$ be a full-rank lattice with determinant (covolume) $\det(\Lambda)$, the volume of one fundamental cell. The notation is collected in 8.3 Lattice notation.

Because $K$ is symmetric, the lattice points come in pairs: if $v$ is in $K$, so is $-v$. The theorem guarantees one such pair. It says nothing about how many points there are or where they sit inside $K$.

Why is the bound 2ⁿ times the determinant?

Take $\Lambda = \mathbb{Z}^n$, so $\det(\Lambda) = 1$, and the open cube $K = (-1,1)^n$. It is convex, symmetric, and has volume exactly $2^n$. Every coordinate of a point inside it has absolute value below 1, so the only integer point is the origin. The strict inequality in the theorem is therefore necessary, and no constant smaller than $2^n$ can work. The closed cube $[-1,1]^n$ has the same volume and does contain nonzero integer points, such as $(1,0,\dots,0)$, which is what the compact version predicts.

Proof: Blichfeldt's lemma and half of K

The lemma is a continuous pigeonhole principle. Cut $S$ into pieces, one for each fundamental cell it meets, and translate every piece by a lattice vector into a single fundamental cell $P$. The translated pieces have total volume $\mathrm{vol}(S)$, which is more than $\mathrm{vol}(P) = \det(\Lambda)$, so two of them must overlap. A point in the overlap came from two points $x \ne y$ of $S$ that differ by a lattice vector.

Now apply the lemma to $S = \tfrac12 K$. Scaling by one half divides the volume by $2^n$:

So there are $a \ne b$ in $K$ with $v = \tfrac12 a - \tfrac12 b \in \Lambda$, and $v \ne 0$. Symmetry puts $-b$ in $K$, and convexity puts the midpoint of $a$ and $-b$ in $K$:

That is the nonzero lattice point. For the compact version, apply the strict version to $(1+\varepsilon)K$ for every $\varepsilon > 0$. Each contains a nonzero lattice point, all of them lie in the bounded set $2K$, which holds only finitely many lattice points, so one point works for every $\varepsilon$ and, $K$ being closed, it lies in $K$.

What happens without convexity or symmetry?

Both hypotheses are needed, and each fails in a simple way for $\Lambda = \mathbb{Z}^2$.

• Convex but not symmetric. The strip $(-N, N) \times (0, 1)$ has area $2N$, as large as you like, but every point has $0 < y < 1$, so no point of it is an integer point.
• Symmetric but not convex. Take the two rectangles $(\tfrac14, \tfrac34) \times (-N, N)$ and $(-\tfrac34, -\tfrac14) \times (-N, N)$. Together they are symmetric with area $2N$, yet no point has an integer $x$-coordinate. The proof breaks exactly at the midpoint step: the midpoint of a point in one rectangle and a point in the other has $x$ near 0, outside the set.

Worked example in two dimensions

Let $\Lambda$ be generated by $b_1 = (2, 1)$ and $b_2 = (1, 3)$. Its determinant is $|2 \cdot 3 - 1 \cdot 1| = 5$, so the threshold is $2^2 \cdot 5 = 20$.

• A disc. A disc of radius $r$ has area $\pi r^2$, which exceeds 20 once $r > \sqrt{20/\pi} \approx 2.523$. The disc of radius 2.6 (area 21.24) must contain a nonzero lattice point, and it does: $(2,1) = b_1$, $(-1,2) = b_2 - b_1$ and their negatives, all of length $\sqrt5 \approx 2.236$.
• A square. The closed square $[-\sqrt5, \sqrt5]^2$ has area exactly 20, so the compact version applies. It contains $(2,1)$, whose coordinates are both at most $\sqrt5$.

Corollary: every lattice has a short vector

Apply the theorem to a cube and to a ball. The cube $[-r, r]^n$ has volume $(2r)^n$, which equals $2^n \det(\Lambda)$ when $r = \det(\Lambda)^{1/n}$. The compact version gives a nonzero lattice vector with every coordinate at most $r$ in absolute value, so its length is at most $\sqrt{n}\,r$. A ball of radius $r$ has volume $V_n r^n$, where $V_n$ is the volume of the unit ball, and the same argument gives a sharper bound.

In the example above, $2\sqrt{5/\pi} \approx 2.523$ and $\sqrt2 \cdot \sqrt5 \approx 3.162$, while the true $\lambda_1$ is $\sqrt5 \approx 2.236$. Squaring the ball bound and dividing by $\det(\Lambda)^{2/n}$ gives the upper bound $\gamma_n \le 4 / V_n^{2/n}$ on Hermite's constant, which grows roughly like $2n/(\pi e)$ for large $n$. For $n = 2$ it gives $4/\pi \approx 1.273$; the true value is $2/\sqrt3 \approx 1.155$. These are existence results. Finding such a vector is the shortest vector problem, which is hard in high dimension; LLL only reaches an exponential approximation of it.

Where the theorem is used

• Sums of two squares. For a prime $p \equiv 1 \pmod 4$, pick $u$ with $u^2 \equiv -1 \pmod p$ and use the lattice $\{(a, b) : b \equiv u a \pmod p\}$ of determinant $p$. The disc of radius $\sqrt{2p}$ has area $2\pi p > 4p$, so it holds a nonzero point with $0 < a^2 + b^2 < 2p$ and $a^2 + b^2 \equiv a^2(1 + u^2) \equiv 0 \pmod p$. Hence $a^2 + b^2 = p$. For $p = 13$ and $u = 5$ the point $(3, 2)$ gives $9 + 4 = 13$. The same method proves Lagrange's four-square theorem in four dimensions.
• Lattice cryptography. The bound tells you the length a shortest vector can have at most. Parameter choices for SIS and LWE compare the planted short vector with this scale, usually through the Gaussian heuristic, which is the same volume argument for a random lattice.
• Successive minima. The theorem bounds only the first minimum. Its refinement to all $n$ minima is Minkowski's second theorem.

Common mistakes

• Forgetting the factor 2ⁿ. The threshold is $2^n \det(\Lambda)$, not $\det(\Lambda)$. Volume $\det(\Lambda)$ is the threshold of Blichfeldt's lemma, which gives a difference of two points, not a point of $K$.
• Using a set that is not centred at the origin. A disc of large area placed off-centre need not contain any lattice point.
• Reading it as an algorithm. The proof is non-constructive. It proves a short vector exists; it does not find one.
• Using the non-strict inequality for open sets. The open cube $(-1,1)^n$ shows that $\ge$ is only valid for compact $K$.

Further reading

J. W. S. Cassels, An Introduction to the Geometry of Numbers (Springer), chapter III, and D. Micciancio and S. Goldwasser, Complexity of Lattice Problems (Kluwer, 2002), chapter 1, both give the proof via Blichfeldt's lemma. The chapter numbers are cited from memory. The broader picture, including packing and covering radii, is in 1.3 Geometry of numbers.