6.6 Minkowski's second theorem and successive minima

Minkowski's second theorem says that for a lattice $\Lambda \subset \mathbb{R}^n$ and a convex body $K$ that is symmetric about the origin, the successive minima satisfy $\frac{2^n}{n!}\det(\Lambda) \le \lambda_1 \lambda_2 \cdots \lambda_n \cdot \mathrm{vol}(K) \le 2^n \det(\Lambda)$. The first theorem controls only the shortest vector. The second controls all n of them at once: their product can never be much larger, or much smaller, than the determinant divided by the volume of $K$.

What are the successive minima of a lattice?

Fix a lattice $\Lambda$ of full rank in $\mathbb{R}^n$ and a convex body $K$: compact, convex, with nonempty interior and symmetric ($x \in K$ implies $-x \in K$). Scale $K$ by a factor $r$ and count how many linearly independent lattice vectors the scaled body $rK$ contains.

The minima are sorted, $\lambda_1 \le \lambda_2 \le \dots \le \lambda_n$, and they do not depend on a basis. Chapter 1.4 treats them alongside the covering radius, and the notation reference lists every symbol used here.

What does Minkowski's second theorem say?

Each factor has a plain meaning. $\det(\Lambda)$ is the volume of one fundamental cell, so $\mathrm{vol}(K)/\det(\Lambda)$ is roughly how many lattice points $K$ should hold. The product of the minima is the volume factor you pay to scale $K$ along n independent directions until each direction contains a lattice vector. The factor $2^n$ appears because a symmetric body reaches both $v$ and $-v$; it is the same $2^n$ that appears in Minkowski's convex body theorem. The extra $1/n!$ on the left is the volume of a simplex compared with a box.

Both constants are sharp

Take $\Lambda = \mathbb{Z}^n$, so $\det(\Lambda) = 1$. For the cube $K = [-1, 1]^n$ every minimum is 1 (the unit vectors lie on the boundary) and $\mathrm{vol}(K) = 2^n$, so the upper bound is an equality. For the cross-polytope $K = \{x : |x_1| + \dots + |x_n| \le 1\}$ every minimum is again 1 and $\mathrm{vol}(K) = 2^n/n!$, so the lower bound is an equality.

The Euclidean ball

For $K = B_n$ the volume is $V_n = \pi^{n/2}/\Gamma(n/2 + 1)$, and the theorem reads

Taking n-th roots, the geometric mean of the minima is at most $(2^n/V_n)^{1/n}\det(\Lambda)^{1/n}$. The factor $(2^n/V_n)^{1/n}$ is 1.128 in dimension 2, 1.821 in dimension 10 and 4.981 in dimension 100, and grows like $\sqrt{2n/(\pi e)}$. Minkowski also proved the sharper Euclidean form $\lambda_1 \cdots \lambda_n \le \gamma_n^{n/2} \det(\Lambda)$, where $\gamma_n$ is Hermite's constant.

How is it stronger than the first theorem?

The minima are sorted, so $\lambda_1^n \le \lambda_1 \cdots \lambda_n$. The upper bound therefore gives $\lambda_1^n \,\mathrm{vol}(K) \le 2^n \det(\Lambda)$, which is the shortest-vector bound from Minkowski's first theorem. The second theorem says more: if $\lambda_1$ is unusually small, some later minimum must be large enough to keep the product near $\det(\Lambda)/\mathrm{vol}(K)$. A lattice cannot be short in every direction, and it cannot be long in every direction either.

Worked example in two dimensions

Take the lattice generated by $b_1 = (5, 2)$ and $b_2 = (2, 3)$. Its determinant is $|5 \cdot 3 - 2 \cdot 2| = 11$. A brute-force search over all combinations $a b_1 + b b_2$ with $|a|, |b| \le 20$ gives the shortest vectors:

• $\pm(3, -1) = \pm(b_1 - b_2)$, length $\sqrt{10} \approx 3.162$. So $\lambda_1 = \sqrt{10}$.
• $\pm(2, 3) = \pm b_2$, length $\sqrt{13} \approx 3.606$, not parallel to the first. So $\lambda_2 = \sqrt{13}$.

With the unit disc, $\mathrm{vol}(K) = \pi$ and $n = 2$:

The product sits at about 0.81 of the upper bound. The sharper Euclidean form also holds: $\lambda_1\lambda_2 = \sqrt{130} \approx 11.40 \le \gamma_2 \det(\Lambda) = \tfrac{2}{\sqrt 3}\cdot 11 \approx 12.70$. The two minimal vectors happen to form a basis here: $|3 \cdot 3 - (-1)\cdot 2| = 11$, the same determinant. That basis is what LLL returns for this lattice.

Why the lower bound holds

Choose linearly independent lattice vectors $v_1, \dots, v_n$ with $v_i \in \lambda_i K$. Then each $\pm v_i/\lambda_i$ lies in $K$, and because $K$ is convex it contains their convex hull, a cross-polytope. That cross-polytope has volume $\frac{2^n}{n!}\,|\det(v_1, \dots, v_n)| / (\lambda_1 \cdots \lambda_n)$. The vectors $v_i$ generate a sublattice of $\Lambda$, so $|\det(v_1, \dots, v_n)| \ge \det(\Lambda)$. Putting the two together:

Why the upper bound is harder (proof idea)

This section is a sketch, not a proof. The first theorem is proved by packing translates of $\tfrac12 \lambda_1 K$ around lattice points: they cannot overlap, so their total volume is bounded by the volume available per lattice point. For the second theorem the body is stretched by a different factor in each direction $v_1, \dots, v_n$, using a map that is not linear, and one shows that the stretched copies around lattice points still do not overlap while the volume grows by the factor $\lambda_1 \cdots \lambda_n / \lambda_1^n$. Making the non-linear stretch precise is the technical part. Complete proofs are in Cassels, An Introduction to the Geometry of Numbers, chapter VIII, and in Gruber's Convex and Discrete Geometry.

Counting lattice points with successive minima

The minima also bound how many lattice points a body contains. Write $G(K) = \#(K \cap \Lambda)$, counting the origin. Betke, Henk and Wills proved

and conjectured the stronger bound $\prod_i \lfloor 2/\lambda_i + 1 \rfloor$. Henk later proved the conjectured bound up to a factor $2^{n-1}$. In the example above, the disc of radius 5 has minima $\sqrt{10}/5 \approx 0.632$ and $\sqrt{13}/5 \approx 0.721$ and contains 7 lattice points (the origin and three pairs). The proved bound gives $\lfloor 4.16 \rfloor \cdot \lfloor 6.55 \rfloor = 4 \cdot 6 = 24$ and the conjectured one gives $4 \cdot 3 = 12$. Both hold.

Consequences for reduced bases

Any basis $b_1, \dots, b_n$ of $\Lambda$, sorted by length, satisfies $\|b_i\| \ge \lambda_i$, because the first $i$ basis vectors are independent. Hadamard's inequality gives $\det(\Lambda) \le \|b_1\| \cdots \|b_n\|$. Combined with the second theorem, a basis whose vectors are close to the minima has a product of lengths close to the determinant, which is exactly what reduction algorithms such as LLL aim for. In dimension 5 and above, though, the vectors that achieve the minima need not form a basis. The standard example is $\mathbb{Z}^5 + \mathbb{Z}\,(\tfrac12, \dots, \tfrac12)$: all five minima equal 1 and are attained by $e_1, \dots, e_5$, which generate only $\mathbb{Z}^5$, a sublattice of index 2.

Common mistakes

• Putting n! on the wrong side. The $1/n!$ belongs to the lower bound. The upper bound has only $2^n$.
• Using a body that is not symmetric. The theorem needs $K = -K$. For a non-symmetric body the minima are defined differently and the constants change.
• Treating the minima as a basis. The minima are lengths. The vectors achieving them are linearly independent but, from dimension 5, may not generate the lattice.
• Mixing up det of a basis and det of the lattice. $\det(\Lambda)$ is the positive covolume; it does not depend on the basis.

Further reading

• J. W. S. Cassels, An Introduction to the Geometry of Numbers, Springer, chapter VIII (successive minima and the second theorem). Chapter number cited from memory.
• P. M. Gruber, Convex and Discrete Geometry, Springer, 2007, section on the second theorem of Minkowski. Cited from memory.
• U. Betke, M. Henk, J. M. Wills, “Successive-minima-type inequalities”, Discrete & Computational Geometry 9 (1993); M. Henk, “Successive minima and lattice points”, 2002. Cited from memory.

For the first theorem and the pictures behind it, continue with 6.5 Minkowski's convex body theorem or the chapter 1.3 Geometry of numbers.