Fraction-free LLL state validity is preserved by size reduction and adjacent swaps
ProvedInfoLossLAR.WorstCase.NativeLLL.elementary_updates_preserve_validityalgorithmslar-regev-bridgelatticeslll
Consider a fraction-free integer LLL state with rows in ambient dimension . Call the state valid if the stored Gram determinants and lower-triangular scaled Gram–Schmidt coefficients agree with those of its current basis. For each valid state ,
The native swap returns the input state when or . These two identities allow a finite LLL run to reuse its stored data after each elementary update.
Preamble
import Definitions.Def_LARLLL_CurrentData set_option autoImplicit false
Formal statement
namespace InfoLossLAR.WorstCase.NativeLLL
theorem elementary_updates_preserve_validity {n m : ℕ} (s : Hex.Internal.LLLState n m) (hvalid : s.Valid) :
(∀ (j k : Fin n) (hjk : j.val < k.val), (s.sizeReduceColumn j k hjk).Valid) ∧
(s.b.independent → ∀ k : ℕ, (s.swapStep k).Valid) := by
sorry
end InfoLossLAR.WorstCase.NativeLLLSource
Kim Morrison, HexLLLTheory/ReductionInvariant.lean, theorems Hex.Internal.LLLState.sizeReduceColumn_valid and Hex.Internal.LLLState.swapStep_valid, https://github.com/leanprover/hex-lll-theory/blob/main/HexLLLTheory/ReductionInvariant.lean. These are the two preservation clauses for the native integer LLL data; the statement groups them at their shared valid input state.