Lemma 6 — locality and late activity of every repair candidate
OpenDynEdgeColorLLL.Main.Supplement.lemma_6dynamic-algorithmslovasz-local-lemmap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probability
Fix a batch and the old and new completed static transcripts using the same randomness tables. Let be the clauses touched by the batch and let be the union of the old and new dependency graphs. For each and every produced by the actual repair,
Here uses old last-resampling stages over the union of the old and new variable sets, and is the last stage affecting a new variable of . The first conclusion is represented by an actual walk of length at most to a touched clause, which also excludes disconnected pairs. Both conclusions apply to the bar-candidate set itself. They connect the inspected region to late resampling activity for the expected-work bound.
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
- encoding: Distance from C to the touched-clause set is at most 2r → There is a touched clause D and a walk from C to D of length at most 2r; reason: Equivalent graph-distance formulation that cannot assign a default finite distance to disconnected vertices or the empty target set
- reading: The two static transcripts are compared after the static algorithm has terminated almost surely; the proof uses the final satisfying new assignment → The deterministic statement explicitly assumes that both static executions finish, without assuming termination of the repair; reason: The last-activity conclusion need not hold on an exceptional nonterminating static tape; §3.2 gives termination almost surely, so every source instance is recovered almost surely
- 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 6, printed p. 16 / PDF p. 18: locality and late resampling for every bar candidate. -/
theorem lemma_6
{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 τ)
(hnew : FiniteOld f (applyBatch old B) τ)
(r : ℕ) (hr : 1 ≤ r) (C : Fin m)
(hC : C ∈ (repairAt f old B τ r).previousBar) :
(∃ D ∈ touched B, ∃ p : (unionDepGraph old (applyBatch old B)).Walk C D,
p.length ≤ 2 * r) ∧
(r : ℕ∞) ≤ max (starLast f old (applyBatch old B) τ C)
(clauseLast (applyBatch old B) (rx f (applyBatch old B) τ) C) := by sorry
end DynEdgeColorLLL.Main.Supplement
Source
Sijin Peng, Mohsen Ghaffari, STOC 2027 submission #615 (October 2026), Lemma 6, printed p. 16 (PDF p. 18)