Uniform polynomial-time computation of the native integer LLL basis
ProvedInfoLossLAR.WorstCase.NativeLLL.Uniform.exists_reducealgorithmslar-regev-bridgelatticeslll
There exists a single deterministic polynomial-time function on lists of integer rows that computes the specified native LLL basis of every nonsingular square integer matrix. The dimension may vary with the input. Both input and output use the same row encoding, and the output agrees entry by entry with the specified reducer.
Preamble
import Definitions.Def_LARLLL_CurrentData import Definitions.Def_QuantumMaxCutFiniteNumericRuntime set_option autoImplicit false
Formal statement
namespace InfoLossLAR.WorstCase.NativeLLL.Uniform
theorem exists_reduce : ∃ f : List (List ℤ) → List (List ℤ), OAI.MetricKMedian.Binary.Automatic.Poly f ∧
∀ {n : ℕ} (B : Matrix (Fin n) (Fin n) ℤ), B.det ≠ 0 →
f (InfoLossLAR.WorstCase.RationalInverse.Native.inputRows B) =
InfoLossLAR.WorstCase.RationalInverse.Native.inputRows (InfoLossLAR.WorstCase.NativeLLL.basis B) := by
sorry
end InfoLossLAR.WorstCase.NativeLLL.UniformSource
Uniform variable-dimension implementation of the native fraction-free LLL algorithm. It is used by the initial Gaussian pool in the theorem InfoLossLAR.WorstCase.RegevSearch.coherent_shared_pool_fourier_sampler. The fixed-cutoff variant and the correctness of the elementary updates are theorems InfoLossLAR.WorstCase.RegevSketch.finite_cutoff_lll_poly and InfoLossLAR.WorstCase.NativeLLL.elementary_updates_preserve_validity on Prove2Me. The Lean source includes the license and attribution for its Hex-based integer LLL components.