(1.15), p. 519 — every step of the algorithm keeps b₁, …, bₙ a basis for the same lattice L
ProvedLLLFactor.Reduction.step_preserves_basisalgorithmlatticelattice-basis-reductionlllp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be linearly independent and let be a subscript. If one step of the basis reduction algorithm (1.15) (case 1 or case 2, including the achievement of (1.18) and the loop of case 2) leads from the state to the state , then are linearly independent and
This is the paper's claim that "in the course of the algorithm the vectors will be changed several times, but always in such a way that they form a basis for ", and it is what makes the output of the algorithm a basis of the input lattice.
Formalization Note. A step is the relation Step of the definitions module; it allows either nearest integer at a tie.
Preamble
import Mathlib import Definitions.Def_LLLFactor_Reduction_Algorithm
Formal statement
namespace LLLFactor.Reduction
theorem step_preserves_basis {n : ℕ} (b b' : Fin n → LLLFactor.RedBasis.Vec n) (k k' : ℕ)
(hb : LinearIndependent ℝ b) (hstep : Step (b, k) (b', k')) :
LinearIndependent ℝ b' ∧ LLLFactor.RedBasis.latticeOf b' = LLLFactor.RedBasis.latticeOf b := by sorry
end LLLFactor.Reduction
Source
Lenstra, Lenstra, Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), p. 519, (1.15)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.