(1.15), p. 519 — (1.16)–(1.17) hold trivially at k = 2, and at k = n + 1 they say the basis is reduced
ProvedLLLFactor.Reduction.situation_initial_finalalgorithmlattice-basis-reductionlllp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let . Write for the situation of (1.15) at subscript :
Then:
- holds for every ("these conditions are trivially satisfied if ");
- if holds, then satisfies (1.4) and (1.5), i.e. the basis is reduced ("if then the basis is reduced").
Together with the invariance of the situation under a step, this shows that the algorithm, when it stops, has produced a reduced basis.
Formalization Note. The indices are 0-based in Lean; (1.16) is stated for Lean indices with , and (1.17) for the paper's with , .
Preamble
import Mathlib import Definitions.Def_LLLFactor_Reduction_Algorithm
Formal statement
namespace LLLFactor.Reduction
theorem situation_initial_final {n : ℕ} (b : Fin n → LLLFactor.RedBasis.Vec n) :
Situation b 2 ∧ (Situation b (n + 1) → LLLFactor.RedBasis.IsReduced b) := by sorry
end LLLFactor.Reduction
Source
Lenstra, Lenstra, Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), p. 519, (1.15)–(1.17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.