Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5 — all three transcript-repair invariants

Open
DynEdgeColorLLL.Main.Supplement.lemma_5

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

dynamic-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 r≥1r\ge1r≥1:

  1. All selection sets IjnewI_j^{\rm new}Ijnew​ and resampling bits bx,jnewb_{x,j}^{\rm new}bx,jnew​ for 1≤j<r1\le j<r1≤j<r, and assignments σjnew\sigma_j^{\rm new}σjnew​ for 0≤j<r0\le j<r0≤j<r, have been recovered.
  2. Every clause whose stage-rrr falsification bit or counter differs between old and new transcripts belongs to Cr\mathcal C_rCr​.
  3. The falsification bits and counters have been recovered for every clause and every 1≤j≤r1\le j\le r1≤j≤r.

Thus the stored state satisfies

RepairInvariants⁡(r).\operatorname{RepairInvariants}(r).RepairInvariants(r).

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)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me