Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Threshold CNF, count expansion and solution sampler

Definition
CNFLearning873_Valiant_Supplement_ThresholdFormula

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

cnf-learningcombinatoricsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability

For a list SSS of width-kkk clauses, multiplicity is counted. Construct HSH_SHS​ from the disjunctions of compatible clause subsets J⊆supp(S)J\subseteq\mathrm{supp}(S)J⊆supp(S) satisfying ∣J∣<r+1|J|<r+1∣J∣<r+1 and total multiplicity at least rrr. Duplicate literals are removed; incompatible forbidden assignments yield tautologies and are omitted. Thus the intended threshold is

Ω(HS)={x:∑c∈S1[x violates c]<r}.\Omega(H_S)=\{x:\sum_{c\in S}\mathbf1[x\text{ violates }c]<r\}.Ω(HS​)={x:c∈S∑​1[x violates c]<r}.

Counts enumerate the distinct cases whose total violated multiplicity is strictly less than rrr. A case query satisfies every remaining clause and negates each violated clause into its unit clauses, adding greedy clauses or a conditional assignment prefix. Duplicate query clauses are removed and contradictory units are detected before querying. A solution is sampled by conditional counts, one variable at a time, carrying the remaining total. The program accumulates every counting query and charges subset enumeration, query construction, and prefix updates. Subsets are enumerated by bounded cardinality, rather than constructing all subsets and then discarding the large ones.

Definition code
import Definitions.Def_CNFLearning873_Valiant_Supplement_OracleProgram

noncomputable section

namespace CNFLearning873.Valiant.Supplement
open scoped BigOperators
local instance (p : Prop) : Decidable p := Classical.propDecidable p

/-- Enumerates subsets up to size b, without traversing all subsets of larger size. -/
def smallSubsets {n : ℕ} (C : CNF n) (b : ℕ) : List (CNF n) :=
  ((List.range (min b C.card + 1)).flatMap fun j => C.toList.sublistsLen j).map List.toFinset

def multiplicity {n : ℕ} (S : List (Clause n)) (c : Clause n) : ℕ := S.count c

def subsetWeight {n : ℕ} (S : List (Clause n)) (J : CNF n) : ℕ :=
  ∑ c ∈ J, multiplicity S c

def compatible {n : ℕ} (J : CNF n) : Prop :=
  ∀ c ∈ J, ∀ d ∈ J, ∀ v b e, c v = some b → d v = some e → b = e

/-- Union of the literals of a compatible family, with duplicate literals removed. -/
def mergeClause {n : ℕ} (J : CNF n) : Clause n :=
  fun v => J.toList.findSome? fun c => c v

/-- The actual CNF H_S of p.27, not a predicate stipulating its intended solution set. -/
def thresholdFormula {n : ℕ} (r : ℝ) (S : List (Clause n)) : CNF n :=
  (((smallSubsets S.toFinset (Nat.ceil r)).filter fun J =>
    (J.card : ℝ) < r + 1 ∧ r ≤ (subsetWeight S J : ℝ) ∧ compatible J).map mergeClause).toFinset

/-- Unit clause requiring x_v=b. -/
def unitClause {n : ℕ} (v : Fin n) (b : Bool) : Clause n :=
  fun u => if u = v then some b else none

/-- Negating a clause gives a conjunction of unit clauses at the forbidden values. -/
def negatedClause {n : ℕ} (c : Clause n) : CNF n :=
  (support c).image fun v => unitClause v (!(c v).getD false)

def contradictoryUnits {n : ℕ} (F : CNF n) : Prop :=
  ∃ v : Fin n, unitClause v false ∈ F ∧ unitClause v true ∈ F

/-- Count cases have strict total multiplicity <r, unlike H_S construction's ≥r. -/
def countCases {n : ℕ} (r : ℝ) (S : List (Clause n)) : List (CNF n) :=
  (smallSubsets S.toFinset (Nat.ceil r)).filter fun J => (subsetWeight S J : ℝ) < r

/-- Extras are the greedy clauses and the conditional fixedUnits. Finsets deduplicate all clauses. -/
def caseQuery {n : ℕ} (S : List (Clause n)) (J extras : CNF n) : CNF n :=
  (S.toFinset \ J) ∪ J.biUnion negatedClause ∪ extras

/-- Every count expands to explicitly supplied width-at-most-k queries. Contradictory units
are detected without calling the oracle. No desired bound is part of this program. -/
def countThreshold {n : ℕ} (r : ℝ) (S : List (Clause n)) (extras : CNF n) : OProg n ℕ :=
  let cases := countCases r S
  let setup := (S.length + 1) ^ 2 * (n + 1) * (Nat.ceil r + 1) *
    ((smallSubsets S.toFinset (Nat.ceil r)).length + 1)
  .work setup (cases.foldl (fun p J => p.bind fun a =>
    let F := caseQuery S J extras
    let w := (n + 1) ^ 2 * (S.length + extras.card + 1) ^ 2
    .work w (if contradictoryUnits F then .ret a else .count F fun z => .ret (a + z)))
    (.ret 0))

/-- Chain-rule solution sampling, using one conditional count per variable. The current total
is carried forward; it is computed once before calling this program. -/
def sampleThresholdAux {n : ℕ} (r : ℝ) (S : List (Clause n)) :
    List (Fin n) → CNF n → Assignment n → ℕ → OProg n (Assignment n)
  | [], _, x, _ => .ret x
  | v :: vs, fixedUnits, x, total => do
      let z ← countThreshold r S (insert (unitClause v false) fixedUnits)
      let u ← OProg.draw total OProg.ret
      let b := decide (z ≤ u)
      OProg.work ((n + 1) ^ 2) <|
        sampleThresholdAux r S vs (insert (unitClause v b) fixedUnits)
          (Function.update x v b) (if b then total - z else z)

def sampleThreshold {n : ℕ} (r : ℝ) (S : List (Clause n)) (total : ℕ) :
    OProg n (Assignment n) :=
  sampleThresholdAux r S (List.finRange n) ∅ (fun _ => false) total

end CNFLearning873.Valiant.Supplement
Source
Weiming Feng, Yixiao Yu, Yiyao Zhang, STOC 2027 submission #873 (October 2026), Definition of H_S and Lemma 6.6, printed pp.27–29 = 1-based PDF pp.27–29; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/873.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