(1.25), p. 521 — d_i = ∏_{j≤i} |b_j*|², so d_i > 0, d₀ = 1 and dₙ = d(L)²
ProvedLLLFactor.Reduction.gram_eq_prod_gsgram-determinantgram-schmidtlatticelllp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be linearly independent and let be the Gram determinant of the first vectors (1.24). Then for
hence ; moreover and , where .
Identity (1.25) expresses the Gram determinants through the Gram–Schmidt lengths; it is how the potential of the termination proof is controlled.
Formalization Note. The product is over Lean indices , i.e. the paper's .
Preamble
import Mathlib import Definitions.Def_LLLFactor_Reduction_Algorithm
Formal statement
namespace LLLFactor.Reduction
theorem gram_eq_prod_gs {n : ℕ} (b : Fin n → LLLFactor.RedBasis.Vec n) (hb : LinearIndependent ℝ b) :
(∀ (i : ℕ) (hi : i ≤ n),
gram b i = ∏ j : Fin i, ‖LLLFactor.RedBasis.gs b (Fin.castLE hi j)‖ ^ 2 ∧ 0 < gram b i) ∧
gram b 0 = 1 ∧ gram b n = LLLFactor.RedBasis.latticeDet b ^ 2 := by sorry
end LLLFactor.Reduction
Source
Lenstra, Lenstra, Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), p. 521, (1.23)–(1.25)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.