(1.23), p. 522 — along any run from k = 2, case 2 is passed at most n − 1 more times than case 1
ProvedLLLFactor.Reduction.case2_count_lealgorithmlattice-basis-reductionlllp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1termination
Let and . Let be a run of the algorithm (1.15) started at , i.e. each arises from by one step, for . Let and be the numbers of at which the step is of case 1, resp. case 2. Then
This is the counting argument of (1.23): case 1 lowers by , case 2 raises it by , starts at and never exceeds . Combined with the bound on the number of case-1 steps, it bounds the length of every run.
Preamble
import Mathlib import Definitions.Def_LLLFactor_Reduction_Algorithm
Formal statement
namespace LLLFactor.Reduction
open Classical in
theorem case2_count_le {n : ℕ} (hn : 0 < n) (b : Fin n → LLLFactor.RedBasis.Vec n)
(s : ℕ → State n) (T : ℕ) (hs0 : s 0 = (b, 2))
(hrun : ∀ t < T, Step (s t) (s (t + 1))) :
((Finset.range T).filter (fun t => Case2 (s t) (s (t + 1)))).card ≤
((Finset.range T).filter (fun t => Case1 (s t) (s (t + 1)))).card + (n - 1) := 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.