Definition B.1 — restricted and unrestricted layered gadgets
DefinitionCNFLearning873_Valiant_Supplement_GadgetBcnf-learningcombinatoricsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Arrange Boolean variables in layers of size . Between layers and , include one clause for each , on every variable of layer except , together with variable of layer . With printed layer indices starting at one, these clauses forbid all True when is odd and all False when is even. The restricted gadget additionally forbids all True on the first layer. The unrestricted gadget's actual number of satisfying assignments is , and
The construction is the recalled Definition B.1, for integers , ; the eigenvalue bound is stated separately for . Variables in Lean are flattened to with zero-based layer indices. The count is not defined by a recurrence or a desired estimate.
Definition code
import Definitions.Def_CNFLearning873_Valiant_CNF
noncomputable section
namespace CNFLearning873.Valiant.Supplement
/-- Definition B.1, pp.35-36 = PDF pp.35-36. Zero-based layer i corresponds to printed i+1. -/
def gadgetClause (k ℓ : ℕ) (i j : ℕ) : Clause (k * ℓ) :=
fun v => if (v.val / k = i ∧ v.val % k ≠ j) ∨
(v.val / k = i + 1 ∧ v.val % k = j) then some (i % 2 != 0) else none
def unrestrictedGadget (k ℓ : ℕ) : CNF (k * ℓ) := by
classical
exact ((Finset.range (ℓ - 1)).product (Finset.range k)).image
(fun ij => gadgetClause k ℓ ij.1 ij.2)
def restrictedGadget (k ℓ : ℕ) : CNF (k * ℓ) := by
classical
exact insert (fun v => if v.val < k then some false else none) (unrestrictedGadget k ℓ)
def gadgetCount (k ℓ : ℕ) : ℕ := (solutions (unrestrictedGadget k ℓ)).card
def eigenvalue (k : ℕ) : ℝ :=
(2 : ℝ) ^ (k - 1) - 1 +
Real.sqrt ((2 : ℝ) ^ (k - 1) * ((2 : ℝ) ^ (k - 1) - k))
end CNFLearning873.Valiant.Supplement
Source
Weiming Feng, Yixiao Yu, Yiyao Zhang, STOC 2027 submission #873 (October 2026), Definition B.1 and the notation before Lemma B.2, printed pp.35–36 = 1-based PDF pp.35–36; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/873.pdf