Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The hard formulas and their occurrence completion

Definition
MTWalkSAT3CNF_TwoOcc_Supplement_Hard

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

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

For an integer L≥40L\ge40L≥40, let pj,ip_{j,i}pj,i​, j∈{1,2,3}j\in\{1,2,3\}j∈{1,2,3}, 1≤i≤L1\le i\le L1≤i≤L, and xj,i,kx_{j,i,k}xj,i,k​, 1≤i<L1\le i<L1≤i<L, 0≤k≤4L+10\le k\le4L+10≤k≤4L+1, be distinct Boolean variables. The indexed conjunction FLF_LFL​ contains the root (p1,1∨p2,1∨p3,1)(p_{1,1}\vee p_{2,1}\vee p_{3,1})(p1,1​∨p2,1​∨p3,1​), and for every module (j,i)(j,i)(j,i) it contains

(¬pj,i∨xj,i,0∨pj,i+1),(¬pj,i∨¬xj,i,0∨xj,i,1),(\neg p_{j,i}\vee x_{j,i,0}\vee p_{j,i+1}),\quad(\neg p_{j,i}\vee\neg x_{j,i,0}\vee x_{j,i,1}),(¬pj,i​∨xj,i,0​∨pj,i+1​),(¬pj,i​∨¬xj,i,0​∨xj,i,1​), (xj,i,k∨¬xj,i,k−1∨¬xj,i,k−2)(2≤k≤4L+1).(x_{j,i,k}\vee\neg x_{j,i,k-1}\vee\neg x_{j,i,k-2})\quad(2\le k\le4L+1).(xj,i,k​∨¬xj,i,k−1​∨¬xj,i,k−2​)(2≤k≤4L+1).

The completed formula F^L\widehat F_LFL​ uses the same variables and adds (¬ua∨¬va∨¬va+1)(\neg u_a\vee\neg v_a\vee\neg v_{a+1})(¬ua​∨¬va​∨¬va+1​) for the last two variables ua,vau_a,v_aua​,va​ of each module in cyclic lexicographic order, and two separately indexed copies of (¬p1,L∨¬p2,L∨¬p3,L)(\neg p_{1,L}\vee\neg p_{2,L}\vee\neg p_{3,L})(¬p1,L​∨¬p2,L​∨¬p3,L​). The Boolean family selector chooses the original or completed formula. Counts, satisfiability and occurrence claims remain separate theorem obligations.

Definition code
import Definitions.Def_MTWalkSAT3CNF_TwoOcc_Supplement_Runtime

set_option autoImplicit false

namespace MTWalkSAT3CNF.TwoOcc.Supplement

/-- p has indices (branch,position); x has (branch,module,tail position). -/
abbrev HardVar (L : ℕ) := (Fin 3 × Fin L) ⊕ (Fin 3 × Fin (L-1) × Fin (4*L+2))
abbrev Module (L : ℕ) := Fin 3 × Fin (L-1)
abbrev HardIndex (L : ℕ) := Unit ⊕ (Module L × (Fin 2 ⊕ Fin (4*L)))
abbrev CompletedIndex (L : ℕ) := HardIndex L ⊕ (Module L ⊕ Fin 2)

def pvar {L : ℕ} (j : Fin 3) (i : Fin L) : HardVar L := .inl (j,i)
def xvar {L : ℕ} (j : Fin 3) (i : Fin (L-1)) (k : Fin (4*L+2)) : HardVar L :=
  .inr (j,i,k)

/-- Clauses (7)--(11), with the first two indices shifted from one-based to zero-based. -/
def hardClause (L : ℕ) (hL : 40 ≤ L) : HardIndex L → Clause (HardVar L)
  | .inl _ => triple
      (pvar 0 ⟨0, by omega⟩) (pvar 1 ⟨0, by omega⟩) (pvar 2 ⟨0, by omega⟩)
      true true true (by simp [pvar]) (by simp [pvar]) (by simp [pvar])
  | .inr ((j,i), .inl ab) =>
      if ab.val = 0 then
        triple (pvar j ⟨i.val, by omega⟩) (xvar j i 0)
          (pvar j ⟨i.val+1, by omega⟩) false true true
          (by simp [pvar,xvar]) (by simp [pvar]) (by simp [pvar,xvar])
      else
        triple (pvar j ⟨i.val, by omega⟩) (xvar j i 0) (xvar j i 1)
          false false true (by simp [pvar,xvar]) (by simp [pvar,xvar])
          (by simp [xvar])
  | .inr ((j,i), .inr k) =>
      triple (xvar j i ⟨k.val+2, by omega⟩) (xvar j i ⟨k.val+1, by omega⟩)
        (xvar j i ⟨k.val, by omega⟩) true false false
        (by simp [xvar]) (by simp [xvar]) (by simp [xvar])

/-- Lexicographic successor of modules, cyclically. -/
def nextModule (L : ℕ) (_hL : 40 ≤ L) (a : Module L) : Module L :=
  if hi : a.2.val+1 < L-1 then (a.1, ⟨a.2.val+1, hi⟩)
  else (⟨(a.1.val+1)%3, Nat.mod_lt _ (by omega)⟩, ⟨0, by omega⟩)

/-- Completion (29)--(30). The last summand Fin 2 contains two identical E clauses. -/
def completedClause (L : ℕ) (hL : 40 ≤ L) : CompletedIndex L → Clause (HardVar L)
  | .inl c => hardClause L hL c
  | .inr (.inl a) =>
      triple (xvar a.1 a.2 ⟨4*L, by omega⟩) (xvar a.1 a.2 ⟨4*L+1, by omega⟩)
        (xvar (nextModule L hL a).1 (nextModule L hL a).2 ⟨4*L+1, by omega⟩)
        false false false
        (by simp [xvar]) (by simp [xvar])
        (by
          intro heq
          have he : a.1 = (nextModule L hL a).1 ∧ a.2 = (nextModule L hL a).2 := by
            simpa [xvar] using heq
          unfold nextModule at he
          split_ifs at he with hi
          · have hi' := congrArg Fin.val he.2
            simp only at hi'
            omega
          · have hj := a.1.isLt
            have hj' := congrArg Fin.val he.1
            simp only at hj'
            omega)
  | .inr (.inr _) =>
      triple (pvar 0 ⟨L-1, by omega⟩) (pvar 1 ⟨L-1, by omega⟩)
        (pvar 2 ⟨L-1, by omega⟩) false false false
        (by simp [pvar]) (by simp [pvar]) (by simp [pvar])

noncomputable def hardFormula (L : ℕ) (hL : 40 ≤ L) := indexed (hardClause L hL)
noncomputable def completedFormula (L : ℕ) (hL : 40 ≤ L) := indexed (completedClause L hL)

/-- Select either family on their shared variable set; sizes are computed, not postulated. -/
abbrev FamilyIndex (L : ℕ) (completed : Bool) :=
  if completed then CompletedIndex L else HardIndex L

noncomputable instance (L : ℕ) (b : Bool) : Fintype (FamilyIndex L b) := by
  cases b <;> dsimp [FamilyIndex] <;> infer_instance

def familyClause (L : ℕ) (hL : 40 ≤ L) (b : Bool) : FamilyIndex L b → Clause (HardVar L) :=
  match b with
  | false => hardClause L hL
  | true => completedClause L hL

noncomputable def familyFormula (L : ℕ) (hL : 40 ≤ L) (b : Bool) :=
  indexed (familyClause L hL b)

end MTWalkSAT3CNF.TwoOcc.Supplement
Source
Minbo Gao, Kun He, Tao Jiang, STOC 2027 submission #914 (October 2026), §4.1, (7)–(11), pp. 17–18; §4.5, (29)–(30), p. 24; 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