Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Fixed-initialization MT and structural formula predicates

Definition
MTWalkSAT3CNF_TwoOcc_Supplement_Runtime

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

p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithmssatisfiability

For an indexed 3-CNF formula FFF, a legal history-adaptive rule RRR and a fixed assignment σ\sigmaσ, the MT trajectory starts at the Dirac law of (σ,none)(\sigma,\mathrm{none})(σ,none) and uses the published MT transition kernel unchanged. Its mean is

Eσ[TMT(F)]=∫TMT(ω) dPF,R,σ(ω)∈[0,∞].E_\sigma[T_{MT}(F)]=\int T_{MT}(\omega)\,dP_{F,R,\sigma}(\omega)\in[0,\infty].Eσ​[TMT​(F)]=∫TMT​(ω)dPF,R,σ​(ω)∈[0,∞].

The additional structural predicates mean that FFF admits a satisfying assignment, that different clause indices have different sets of signed literals, that the largest occurrence count is exactly three, and that a variable has a specified number of positive or negative occurrences. The triple constructor checks only distinctness of its three variables. Finite clause families are reindexed by a bijection with Fin⁡m\operatorname{Fin}mFinm, preserving all duplicate indices. These interfaces supply the fixed-initialization bounds and structural conclusions of §4 without assuming them.

Definition code
import Definitions.Def_MTWalkSAT3CNF_TwoOcc_MoserTardos
import Definitions.Def_MTWalkSAT3CNF_TwoOcc_WalkSAT

set_option autoImplicit false

namespace MTWalkSAT3CNF.TwoOcc.Supplement
open MeasureTheory ProbabilityTheory
open scoped ENNReal

variable {V : Type} [Fintype V] [DecidableEq V] {m : ℕ}

/-- Fixed-initial-assignment MT law; the published transition kernel is unchanged. -/
noncomputable def mtLawFrom (F : Formula V m) (R : MTRule (cnfSystem F))
    (σ : V → Bool) : Measure (ℕ → MTState (fun _ : V => Bool) (Fin m)) :=
  Kernel.trajMeasure (Measure.dirac (σ, Choice.none)) ((cnfSystem F).mtStep R)

noncomputable def mtMeanFrom (F : Formula V m) (R : MTRule (cnfSystem F))
    (σ : V → Bool) : ℝ≥0∞ :=
  ∫⁻ ω, ((cnfSystem F).mtTimeOf ω : ℝ≥0∞) ∂mtLawFrom F R σ

/-- Satisfaction of all indexed clauses. -/
def Satisfiable (F : Formula V m) : Prop := ∃ σ, bad F σ = ∅

/-- Clause equality ignores permutation of literal positions; indices are retained. -/
def NoRepeated (F : Formula V m) : Prop :=
  Function.Injective (fun i => Finset.univ.image (fun p => ((F i).var p, (F i).sign p)))

def MaxOccThree (F : Formula V m) : Prop :=
  (∀ v, occCount F v ≤ 3) ∧ ∃ v, occCount F v = 3

def signedOcc (F : Formula V m) (v : V) (s : Bool) : ℕ :=
  (Finset.univ.filter (fun ip : Fin m × Fin 3 =>
    (F ip.1).var ip.2 = v ∧ (F ip.1).sign ip.2 = s)).card

/-- A structural constructor only: its proof establishes that the three positions are distinct. -/
def triple (a b c : V) (s t u : Bool) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) :
    Clause V where
  var := ![a,b,c]
  sign := ![s,t,u]
  var_inj := by
    intro i j hij
    fin_cases i <;> fin_cases j <;> simp_all

/-- Reindex a finite clause family without identifying repeated clauses. -/
noncomputable def indexed {I : Type} [Fintype I] (C : I → Clause V) :
    Formula V (Fintype.card I) := fun i => C ((Fintype.equivFin I).symm i)

end MTWalkSAT3CNF.TwoOcc.Supplement
Source
Minbo Gao, Kun He, Tao Jiang, STOC 2027 submission #914 (October 2026), §2.2 and §4.1, §4.5–§4.6, pp. 9–10, 17–18, 24–27; https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/914.pdf

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