Proposition 4.2 — Structure and exact sizes of the hard family F_L
OpenMTWalkSAT3CNF.TwoOcc.Supplement.proposition_4_2p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithmssatisfiability
For every integer , the formula of (7)–(11) is satisfiable, has no repeated clauses even after forgetting literal order, has maximum variable occurrence exactly three, and has three distinct variables in every clause. Its counts are
The variable count is stated both for the constructed carrier and for variables that actually occur. This establishes the structural properties of the hard family.
Differences from the source:
- encoding: one-based branch/module indices and indexed conjunctions → zero-based Fin indices and a bijective reindexing of the constructed clause family, retaining duplicate clauses; reason: only variable and clause labels change; every source instance is preserved
Preamble
import Definitions.Def_MTWalkSAT3CNF_TwoOcc_Supplement_Hard set_option autoImplicit false open MeasureTheory open scoped ENNReal
Formal statement
namespace MTWalkSAT3CNF.TwoOcc.Supplement
theorem proposition_4_2 (L : ℕ) (hL : 40 ≤ L) :
Satisfiable (hardFormula L hL) ∧ NoRepeated (hardFormula L hL) ∧
MaxOccThree (hardFormula L hL) ∧
(∀ i, Function.Injective ((hardFormula L hL) i).var) ∧
Fintype.card (HardIndex L) = 12*L^2-6*L-5 ∧
Fintype.card (HardVar L) = 12*L^2-3*L-6 ∧
numOccVars (hardFormula L hL) = 12*L^2-3*L-6 := by sorry
end MTWalkSAT3CNF.TwoOcc.Supplement
Source
Minbo Gao, Kun He, Tao Jiang, STOC 2027 submission #914 (October 2026), Proposition 4.2, p. 18; https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/914.pdf