ReciprocalTest operational counter bound
ProvedCountingLLL.ReciprocalTest.operational_counter_boundalgorithmsprobability
In every finite execution of the small-step ReciprocalTest algorithm, for every possible entropy sequence, the level counter is at most twice the size counter . This direct operational invariant supports the bit-length bound in the computational-overhead argument. It does not by itself prove termination, the output distribution, or the expected bit cost.
Preamble
import Definitions.Def_CountingLLL_ReciprocalTest open CountingLLL.ReciprocalTest
Formal statement
theorem CountingLLL.ReciprocalTest.operational_counter_bound (ω : Entropy) (n : ℕ) : (run ω n).i ≤ 2 * (run ω n).j := by sorry
Source
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC #442, proof of Lemma 6.5, computational overhead, p. 28, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf