Lemma 5 — all three transcript-repair invariants
OpenDynEdgeColorLLL.Main.Supplement.lemma_5dynamic-algorithmslovasz-local-lemmap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probability
Fix a truth-table family and a batch of distinct clause–variable toggles, with a completed old static transcript and shared randomness tables. Run the initialization of §3.4 and the five-step repair of §3.3. Before each stage :
- All selection sets and resampling bits for , and assignments for , have been recovered.
- Every clause whose stage- falsification bit or counter differs between old and new transcripts belongs to .
- The falsification bits and counters have been recovered for every clause and every .
Thus the stored state satisfies
The recurrence includes the paper's extension by empty stages after stopping. This invariant describes the actual recovered entries needed for the correctness of the dynamic solver.
Differences from the source:
- encoding: The old static transcript is stored before the repair, and recovered entries and assignments use the shared tables → FiniteOld makes the completed old static execution explicit; stored arrays and their readout are given by the repair recurrence; reason: Makes the operational precondition and every recovered quantity explicit without assuming an invariant
- generalization: Section 3 imposes probabilistic LLL and uniform parameter assumptions → The deterministic repair claim is stated for every truth-table family and the completed static transcripts specified here, without numerical LLL hypotheses; reason: The deterministic statement needs only truth-table locality and the actual repair recurrence, and specializes to every completed source execution
Preamble
import Definitions.Def_DynEdgeColorLLL_Main_Supplement_Repair set_option autoImplicit false
Formal statement
namespace DynEdgeColorLLL.Main.Supplement
/-- Lemma 5, printed p. 13 / PDF p. 15: all three invariants before every stage. -/
theorem lemma_5
{X : Type*} [Fintype X] [DecidableEq X] {Ω : X → Type*}
[∀ x, MeasurableSpace (Ω x)] {m : ℕ}
(f : TruthTables X Ω m) (hf : IsTruthTableFamily f)
(old : Fin m → Finset X) (B : Finset (Fin m × X))
(τ : (x : X) → ℕ → Ω x) (hold : FiniteOld f old τ)
(r : ℕ) (hr : 1 ≤ r) :
RepairInvariants f old B τ (repairAt f old B τ (r - 1)) r := by sorry
end DynEdgeColorLLL.Main.Supplement
Source
Sijin Peng, Mohsen Ghaffari, STOC 2027 submission #615 (October 2026), Lemma 5, printed p. 13 (PDF p. 15)