The hard formulas and their occurrence completion
DefinitionMTWalkSAT3CNF_TwoOcc_Supplement_Hardp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithmssatisfiability
For an integer , let , , , and , , , be distinct Boolean variables. The indexed conjunction contains the root , and for every module it contains
The completed formula uses the same variables and adds for the last two variables of each module in cyclic lexicographic order, and two separately indexed copies of . 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