(1.23), p. 522 — m(L) > 0 is attained and d_i ≥ (3/4)^{i(i−1)/2} m(L)^i for every basis of L
ProvedLLLFactor.Reduction.gram_lower_boundgram-determinanthermite-constantlatticelllp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let be a lattice and a basis for . Put . Then is a positive real number, it is attained by a non-zero vector of , and the Gram determinants satisfy
The bound depends only on , not on the basis; since every basis met by the algorithm is a basis for , it gives the positive lower bound for on which termination rests.
Formalization Note. is written as the infimum of ; the statement asserts that this infimum is attained. The exponent is a natural number, so it is a natural-number power.
Preamble
import Mathlib import Definitions.Def_LLLFactor_Reduction_Algorithm
Formal statement
namespace LLLFactor.Reduction
theorem gram_lower_bound {n : ℕ} (hn : 0 < n) (c : Fin n → LLLFactor.RedBasis.Vec n)
(L : Submodule ℤ (LLLFactor.RedBasis.Vec n)) (hc : LLLFactor.RedBasis.IsBasisFor c L) :
0 < minSqNorm L ∧
(∃ x ∈ L, x ≠ 0 ∧ ‖x‖ ^ 2 = minSqNorm L) ∧
∀ i : ℕ, 1 ≤ i → i ≤ n →
(3 / 4 : ℝ) ^ (i * (i - 1) / 2) * minSqNorm L ^ i ≤ gram c i := by sorry
end LLLFactor.Reduction
Source
Lenstra, Lenstra, Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), p. 522, (1.23)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.