(1.15), pp. 519–520 — after each step we are again in the situation (1.16)–(1.17), with 1 ≤ k ≤ n + 1
ProvedLLLFactor.Reduction.step_preserves_situationalgorithminvariantlattice-basis-reductionlllp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be linearly independent and suppose that at subscript the conditions (1.16) and (1.17) hold:
If one step of the algorithm (1.15) leads from to , then (1.16) and (1.17) hold for at subscript , and .
This is the sentence ending both cases of (1.15): "Then we are in the situation described by (1.16) and (1.17), and we proceed with the algorithm from there." It is the loop invariant of the algorithm.
Formalization Note. The bound is the paper's "at each step of the algorithm we shall have a current subscript ".
Preamble
import Mathlib import Definitions.Def_LLLFactor_Reduction_Algorithm
Formal statement
namespace LLLFactor.Reduction
theorem step_preserves_situation {n : ℕ} (b b' : Fin n → LLLFactor.RedBasis.Vec n) (k k' : ℕ)
(hb : LinearIndependent ℝ b) (hsit : Situation b k)
(hstep : Step (b, k) (b', k')) :
Situation b' k' ∧ 1 ≤ k' ∧ k' ≤ n + 1 := by sorry
end LLLFactor.Reduction
Source
Lenstra, Lenstra, Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), pp. 519–520, (1.15)–(1.17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.