Successive minima in the sup norm are bounded by the covolume

Let W be a subspace of dimension k of the Euclidean space ℝ^ι and let L be a full lattice in W. The central slice W ∩ [-1, 1]^ι of the cube is a symmetric convex body in W whose gauge is the sup norm, and by Vaaler's cube-slicing theorem its volume is at least 2 ^ k. Minkowski's second theorem therefore bounds the product of the successive minima of L with respect to the cube slice by the covolume of L, with no constant:

λ₀ ⋯ λₖ₋₁ ≤ covolume L.

For the lattice V ∩ ℤ^ι of integral points of a subspace V of ℚ^ι the covolume is the absolute Euclidean height of V. For the integral solutions of A y = 0, with A an integer matrix, the covolume times the greatest common divisor minorGcd A of the maximal minors of A is √det (A Aᵀ); when the rows of A are linearly independent, minorGcd A is positive and the covolume is the quotient √det (A Aᵀ) / minorGcd A. These bounds are the geometric half of Bombieri and Vaaler's version of Siegel's lemma. Since the gauge of the cube slice is the sup norm, they bound the sup norms of independent integral solutions attaining the minima (ZLattice.exists_linearIndependent_gauge_eq_successiveMin), and of a lattice basis built from the minima, which loses at most a factor k! / 2 ^ (k - 1) against them (ZLattice.exists_basis_mem_smul_successiveMin). The vectors attaining the minima are moreover primitive in L, so L contains k linearly independent primitive vectors a i with

‖a 0‖_∞ ⋯ ‖a (k - 1)‖_∞ ≤ covolume L,

which is the sup-norm form of Bombieri and Vaaler's Theorem 2. These vectors need not form a ℤ-basis of L.

The statements hold for every symmetric convex body containing the cube slice, since enlarging the body only lowers the minima; the cube slice itself is the case of interest.

Main results

• ZLattice.prod_successiveMin_le_covolume_of_setOf_forall_abs_le_one_subset: the bound for a full lattice in a subspace of ℝ^ι.
• ZLattice.exists_linearIndependent_prod_norm_ofLp_le_covolume: independent primitive lattice vectors whose sup norms have product at most covolume L.
• Submodule.prod_successiveMin_intLattice_le_subspaceHeight: for the integral points of a subspace V of ℚ^ι, the product of the minima is at most the height of V.
• Matrix.minorGcd_mul_prod_successiveMin_le_sqrt_det: for the integral solutions of A y = 0, the product of the minima times minorGcd A is at most √det (A Aᵀ).

References

• E. Bombieri and J. Vaaler, On Siegel's lemma, Invent. Math. 73 (1983), 11–32, §§2–3, Theorem 2.
• J. D. Vaaler, A geometric inequality with applications to linear forms, Pacific J. Math. 83 (1979), 543–553.
• I. Aliev and M. Henk, Minkowski's successive minima in convex and discrete geometry, Commun. Math. 31 (2023), no. 2, 35–59, §6.

theorem ZLattice.prod_successiveMin_le_covolume_of_setOf_forall_abs_le_one_subset {ι : Type u_1} [Fintype ι] {W : Submodule ℝ (EuclideanSpace ℝ ι)} (L : Submodule ℤ ↥W) [DiscreteTopology ↥L] [IsZLattice ℝ L] {K : ConvexBody ↥W} (hK : {x : ↥W | ∀ (i : ι), |(↑x).ofLp i| ≤ 1} ⊆ ↑K) (hKs : ∀ x ∈ K, -x ∈ K) : ∏ i : Fin (Module.finrank ℝ ↥W), successiveMin L K i ≤ covolume L MeasureTheory.volume

The geometric half of Bombieri–Vaaler. Let L be a full lattice in a subspace W of the Euclidean space ℝ^ι, and let K be a symmetric convex body in W containing the central slice W ∩ [-1, 1]^ι of the cube, for instance that slice itself. Then the successive minima of L with respect to K satisfy λ₀ ⋯ λₖ₋₁ ≤ covolume L.

theorem ZLattice.exists_linearIndependent_prod_norm_ofLp_le_covolume {ι : Type u_1} [Fintype ι] {W : Submodule ℝ (EuclideanSpace ℝ ι)} (L : Submodule ℤ ↥W) [DiscreteTopology ↥L] [IsZLattice ℝ L] : ∃ (a : Fin (Module.finrank ℝ ↥W) → ↥W), LinearIndependent ℝ a ∧ (∀ (i : Fin (Module.finrank ℝ ↥W)), a i ∈ L) ∧ (∀ (i : Fin (Module.finrank ℝ ↥W)), ∀ y ∈ L, ∀ (c : ℤ), c • y = a i → IsUnit c) ∧ ∏ i : Fin (Module.finrank ℝ ↥W), ‖(↑(a i)).ofLp‖ ≤ covolume L MeasureTheory.volume

Independent lattice vectors of small sup norm (Bombieri–Vaaler). A full lattice L in a subspace W of the Euclidean space ℝ^ι contains finrank ℝ W linearly independent vectors a i, each primitive in L, whose sup norms ‖a i‖_∞ = max_j |a i j| have product at most the covolume of L.

theorem Submodule.prod_successiveMin_intLattice_le_subspaceHeight {ι : Type u_1} [Fintype ι] [LinearOrder ι] (V : Submodule ℚ (ι → ℚ)) {K : ConvexBody ↥V.realSpan} (hK : {x : ↥V.realSpan | ∀ (i : ι), |(↑x).ofLp i| ≤ 1} ⊆ ↑K) (hKs : ∀ x ∈ K, -x ∈ K) : ∏ i : Fin (Module.finrank ℝ ↥V.realSpan), ZLattice.successiveMin V.intLattice K i ≤ V.subspaceHeight

The minima of the integral points of a rational subspace in the sup norm. For a subspace V of ℚ^ι, the successive minima of the lattice V ∩ ℤ^ι in the real span of V, with respect to a symmetric convex body containing the central slice of the cube [-1, 1]^ι, have product at most the absolute Euclidean height of V.

theorem Matrix.minorGcd_mul_prod_successiveMin_le_sqrt_det {ι : Type u_1} [Fintype ι] [LinearOrder ι] {p : ℕ} (A : Matrix (Fin p) ι ℤ) {K : ConvexBody ↥(A.map Int.cast).mulVecLin.ker.realSpan} (hK : {x : ↥(A.map Int.cast).mulVecLin.ker.realSpan | ∀ (i : ι), |(↑x).ofLp i| ≤ 1} ⊆ ↑K) (hKs : ∀ x ∈ K, -x ∈ K) : ↑A.minorGcd * ∏ i : Fin (Module.finrank ℝ ↥(A.map Int.cast).mulVecLin.ker.realSpan), ZLattice.successiveMin (A.map Int.cast).mulVecLin.ker.intLattice K i ≤ √↑(A * A.transpose).det

The minima of the integral solutions of A y = 0 in the sup norm. For an integer matrix A, the successive minima of the lattice of integral solutions of A y = 0, with respect to a symmetric convex body containing the central slice of the cube [-1, 1]^ι, satisfy minorGcd A · λ₀ ⋯ λₖ₋₁ ≤ √det (A Aᵀ). When the rows of A are linearly independent, minorGcd A is positive and this bounds the product of the minima by √det (A Aᵀ) / minorGcd A; otherwise both sides vanish.