(1.15), (1.23) — the basis reduction algorithm terminates and returns a reduced basis for L
ProvedLLLFactor.Reduction.algorithm_terminatesLet and let be a basis of , spanning the lattice . Run the basis reduction algorithm (1.15) from the state . Then:
- the algorithm terminates: there is no infinite sequence of states in which each arises from by one step;
- it does not get stuck: at every reachable state with some step applies;
- its output is a reduced basis for : at every reachable state , the vectors form a basis for that is reduced in the sense of (1.4)–(1.5).
In the paper's words: "(1.15) We shall now describe an algorithm that transforms a given basis for a lattice into a reduced one. … This finishes the description of the algorithm. Below we shall prove that the algorithm terminates." The proof is (1.23). Together with (1.6)–(1.12), which bound the vectors of a reduced basis, this theorem is what makes reduced bases computable and is the engine of the factoring algorithm of Sect. 3.
Formalization Note. Every choice the algorithm leaves open (the nearest integer at a tie) is quantified over, so the theorem covers every implementation of the text of (1.15). Item 2 rules out a vacuous reading of item 1.
import Mathlib import Definitions.Def_LLLFactor_Reduction_Algorithm
namespace LLLFactor.Reduction
theorem algorithm_terminates {n : ℕ} (hn : 0 < n) (b : Fin n → LLLFactor.RedBasis.Vec n)
(hb : LinearIndependent ℝ b) :
(¬ ∃ s : ℕ → State n, s 0 = (b, 2) ∧ ∀ t, Step (s t) (s (t + 1))) ∧
(∀ s : State n, Reachable b s → s.2 ≤ n → ∃ s' : State n, Step s s') ∧
(∀ s : State n, Reachable b s → s.2 = n + 1 →
LLLFactor.RedBasis.IsBasisFor s.1 (LLLFactor.RedBasis.latticeOf b) ∧ LLLFactor.RedBasis.IsReduced s.1) := by sorry
end LLLFactor.Reduction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.