Successive minima of a lattice with respect to a convex body, and a basis from the minima #
Let L be a discrete ℤ-submodule spanning a finite-dimensional real normed space E of
dimension n, and let K be a convex body in E with 0 in its interior. For i < n, the
i-th successive minimum λ i = ZLattice.successiveMin L K i (indexed from zero) is the least
t ≥ 0 for which the dilate t • K contains i + 1 vectors of L that are linearly independent
over ℝ. Measured by the gauge of K, λ i is the least t such that i + 1 independent lattice
vectors have gauge at most t.
The minima are attained simultaneously: there are independent lattice vectors a 0, …, a (n - 1)
with gauge K (a i) = λ i for every i. They are chosen greedily, each of least gauge among the
lattice vectors outside the span of the previous ones; a dimension count shows that this least
gauge is the next minimum. This greedy construction adapts the proof of
TauCeti.IntegralLattice.IsPosSemidef.exists_linearIndependent_integralNorm_eq_successiveMinimum
with the gauge of K in place of the integral norm. The a i need not form a ℤ-basis of L.
Combined with ZLattice.exists_basis_gauge_le_max_one_mul, they give a ℤ-basis b of L with
b i ∈ (max 1 ((i + 1) / 2) * λ i) • K for symmetric K. Against Minkowski's second theorem the
loss is the factor ∏ i < n, max 1 ((i + 1) / 2) = n! / 2 ^ (n - 1)
(TauCeti.prod_max_one_add_one_div_two).
Main definitions #
ZLattice.successiveMin L K i: thei-th successive minimum ofLwith respect toK.ZLattice.successiveMinNat L K i: the extension of the minima by0to all natural indices.
Main results #
MeasureTheory.coe_successiveMin: the minima are the foundational successive minimaMeasureTheory.successiveMinof the setK, defined through the rank ofr • K ∩ L;ZLattice.successiveMinNat_eqis the same comparison at all natural indices.ZLattice.exists_mem_notMem_forall_gauge_le: outside a proper subspace, a discrete spanning lattice has a vector of least gauge.ZLattice.exists_linearIndependent_gauge_eq_successiveMin: independent lattice vectors attain all the successive minima simultaneously.ZLattice.successiveMin_le_iff:λ i ≤ texactly whent • Kcontainsi + 1independent lattice vectors; in particular the infimum definingλ iis attained (ZLattice.successiveMin_isLeast).ZLattice.monotone_successiveMinandZLattice.successiveMin_pos: the minima are positive and nondecreasing.ZLattice.successiveMin_le_iff_finrankandZLattice.successiveMin_isLeast_gauge: the thresholds ofZLattice.successiveMin_le_iffas the dimension of the span of the lattice vectors int • K, or of gauge at mostt;ZLattice.successiveMin_zero_le_iffis the first minimum as the least dilate containing a nonzero lattice vector.ZLattice.successiveMin_antitone_body,ZLattice.successiveMin_antitone_latticeandZLattice.successiveMin_smul: enlarging the body or the lattice decreases the minima, and dilating the body byc > 0divides them byc.ZLattice.finite_setOf_gauge_le: a discrete lattice has finitely many vectors of bounded gauge.ZLattice.mem_span_image_Iio_of_gauge_lt_successiveMin: lattice vectors of gauge below thej-th minimum lie in the span of the firstjvectors attaining the minima; this is the hypothesis of Minkowski's second theorem (ZLattice.prod_mul_measure_le_two_pow_mul_covolume).ZLattice.exists_basis_gauge_eq_successiveMin: the vectors attaining the minima, as a basis ofEoverℝwhose flagsBasis.flagcontain the lattice vectors below each minimum.ZLattice.exists_basis_mem_flag_of_gauge_lt_successiveMin: aℤ-basis ofLwhose real flags contain the lattice vectors below each minimum.ZLattice.successiveMin_mapandZLattice.successiveMin_comap: the minima are invariant under an injective continuous linear map, or a linear equivalence, applied to both the lattice and the body.ZLattice.exists_basis_mem_smul_successiveMin: aℤ-basis ofLwhosei-th member lies in(max 1 ((i + 1) / 2) * λ i) • K.ZLattice.exists_basis_prod_gauge_le_prod_successiveMin: aℤ-basis ofLthe product of whose gauges is at mostn! / 2 ^ (n - 1)times the product of the minima.
References #
- J. W. S. Cassels, An Introduction to the Geometry of Numbers, Springer, 1959: Chapter VIII, §1 (successive minima and their attainment) and Lemma 2 (a lattice basis adapted to the minima), and Chapter V, Lemma 8 (the basis from the minima).
- J.-H. Evertse, Diophantine approximation, Chapter 2: Geometry of numbers, lecture notes,
Leiden University, 2023, §2.3, Lemma 2.8: https://pub.math.leidenuniv.nl/~evertsejh/dio19-2.pdf.
This is the source of
ZLattice.successiveMin_isLeast_gauge,ZLattice.successiveMin_le_iff_finrankandZLattice.successiveMin_smul.
The successive minima of a ℤ-submodule L of E with respect to a convex body K, indexed
from zero: successiveMin L K i is the infimum of the dilation factors t ≥ 0 for which t • K
contains i + 1 vectors of L that are linearly independent over ℝ.
When no dilate of K contains i + 1 independent vectors of L (for instance when L has rank
at most i, or when K is a segment containing 0 and 1 ≤ i), the infimum is over the empty
set and successiveMin L K i takes the junk value sInf ∅ = 0; the minima then need not be
positive or monotone. For a discrete spanning lattice L and 0 in the interior of K, the
hypotheses of the main results, the set is nonempty and the infimum is attained
(ZLattice.successiveMin_isLeast).
Instances For
A dilate t • K containing i + 1 independent lattice vectors bounds the i-th successive
minimum by t.
Scaling the body. Dilating the body by c > 0 divides every successive minimum by c.
No hypothesis on the lattice or the body is needed.
Lattice vectors below a minimum. Let a be independent lattice vectors with
gauge K (a i) ≤ successiveMin L K i for every i, such as the vectors attaining the minima
(ZLattice.exists_linearIndependent_gauge_eq_successiveMin). Every lattice vector of gauge less
than the j-th minimum lies in the span of a 0, …, a (j - 1).
Transport of the successive minima along a linear map. An injective continuous linear map
f : E →L[ℝ] F carries the successive minima of L with respect to K to those of the image
lattice f(L) with respect to the image body f(K): at indices i of E and j of F with the
same value, λ_j(f(L), f(K)) = λ_i(L, K). In particular the minima are invariant under any linear
equivalence applied to both the lattice and the body; it need be neither orthogonal nor unimodular.
Transport of the successive minima along a linear equivalence, with the lattice pulled
back as in ZLattice.comap and ZLattice.covolume_comap: for e : F ≃L[ℝ] E, the minima of the
pullback e⁻¹(L) with respect to the body e⁻¹(K) are those of L with respect to K.
The successive minima of L with respect to K extended to all natural indices: below the
dimension n of E this is successiveMin L K i, still indexed from zero, and from n on it
is 0. It is used where an index bound is a proved equality rather than a definitional one.
The minima themselves are positive and nondecreasing for a discrete spanning lattice L and 0
in the interior of K (ZLattice.successiveMin_pos, ZLattice.monotone_successiveMin), though
not in general (see ZLattice.successiveMin); even then the extension need not be monotone, since
it vanishes from n on.
Instances For
Below the dimension of E, the natural-index extension is the successive minimum.
At a Fin index, the natural-index extension is the successive minimum.
From the dimension of E on, the natural-index extension vanishes.
The foundational successive minima of a convex body. On a convex body K, the successive
minimum MeasureTheory.successiveMin L K i of an arbitrary set, defined through the rank of
r • K ∩ L, is the successive minimum successiveMin L K i, defined through independent families.
No hypothesis on L, K or E is needed: an index i forces E to be finite-dimensional.
The natural-index extension of the successive minima is the foundational successive minimum
MeasureTheory.successiveMin at every index: below the dimension by
MeasureTheory.coe_successiveMin, and beyond it both sides vanish.
Gauge sublevels of a lattice are finite. For a discrete ℤ-submodule L of the
finite-dimensional real normed space E and a convex body K with 0 in its interior, only
finitely many vectors of L have gauge at most r. The body need not be symmetric.
Let L be a discrete ℤ-submodule spanning the finite-dimensional real normed space E, and
let K be a convex body with 0 in its interior. Outside any proper subspace V, L has a vector
of least gauge with respect to K among the vectors of L outside V.
The successive minima are attained simultaneously. For a discrete spanning lattice L and
a convex body K with 0 in its interior, there are ℝ-linearly independent vectors a i of L
with gauge K (a i) = successiveMin L K i for every i. They need not form a ℤ-basis of L.
The successive minima are nondecreasing.
The successive minima of a discrete lattice with respect to a bounded body are positive.
The successive minima as thresholds. For t ≥ 0, the i-th successive minimum is at most
t exactly when the dilate t • K contains i + 1 independent vectors of L. In particular the
infimum defining successiveMin L K i is attained.
The successive minima are attained. The i-th successive minimum is the least t ≥ 0 for
which the dilate t • K contains i + 1 independent vectors of L.
The successive minima as rank thresholds. For t ≥ 0, the i-th successive minimum is
at most t exactly when the vectors of L in the dilate t • K span a subspace of dimension at
least i + 1.
The successive minima as gauge thresholds. The i-th successive minimum is the least
t ≥ 0 such that the vectors of L of gauge at most t span a subspace of dimension at least
i + 1. The body need not be symmetric.
The first successive minimum. For t ≥ 0, the first successive minimum is at most t
exactly when the dilate t • K contains a nonzero vector of L.
Enlarging the body decreases the successive minima. If K ⊆ K' and 0 is in the
interior of K, then every successive minimum of L with respect to K' is at most the
corresponding minimum with respect to K.
Enlarging the lattice decreases the successive minima. If L ≤ M for a discrete
spanning lattice L, then every successive minimum of M with respect to K is at most the
corresponding minimum of L.
A real basis attaining the successive minima. For a discrete spanning lattice L and a
convex body K with 0 in its interior, some basis b of E over ℝ consists of vectors of L
with gauge K (b i) = successiveMin L K i, so that b i ∈ successiveMin L K i • K, for every i.
Moreover every vector of L of gauge less than the i-th minimum lies in the flag
b.flag i.castSucc, the span of b 0, …, b (i - 1). The body need not be symmetric, and b need
not be a ℤ-basis of L.
A lattice basis adapted to the successive minima (Cassels, Chapter VIII, Lemma 2). For a
discrete spanning lattice L and a convex body K with 0 in its interior, some ℤ-basis b of
L has the following property: every vector of L of gauge less than the i-th minimum lies in
the span over ℝ of b 0, …, b (i - 1), the flag (b.ofZLatticeBasis ℝ L).flag i.castSucc. The
body need not be symmetric. No bound on the gauges of the b i is claimed; for symmetric K,
ZLattice.exists_basis_mem_smul_successiveMin gives one.
A basis from the successive minima (Cassels, Chapter V, Lemma 8). For a discrete spanning
lattice L and a symmetric convex body K with 0 in its interior, some ℤ-basis b of L has
b i ∈ (max 1 ((i + 1) / 2) * successiveMin L K i) • K for every i. The factor is 1 for
i ≤ 1, and the product of the factors is n! / 2 ^ (n - 1)
(TauCeti.prod_max_one_add_one_div_two).
A basis from the successive minima, product form. For a discrete spanning lattice L and
a symmetric convex body K with 0 in its interior, some ℤ-basis b of L has
∏ i, gauge K (b i) ≤ n! / 2 ^ (n - 1) * ∏ i, successiveMin L K i, where n = finrank ℝ E.