Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Fact 3.7 — Ps,t3P^3_{s,t}Ps,t3​ is a t-threshold 3-uniform monotone CNF (corrected: s = 1 needs t ≥ 2)

Open
MajorityDepthThree.Exact.Supplement.construction_threshold

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

circuit-complexityextremal-combinatoricsp2o-batch-stoc27sp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let sss be an integer and ttt a natural number in the domain of the construction Ps,t3P^3_{s,t}Ps,t3​: either s≤0s\le0s≤0; or s=1s=1s=1 and t≥2t\ge2t≥2; or 2≤s≤t2\le s\le t2≤s≤t. Let V={0,1,…,3t−s−1}V=\{0,1,\dots,3t-s-1\}V={0,1,…,3t−s−1}, a set of 3t−s3t-s3t−s variables. Then Ps,t3P^3_{s,t}Ps,t3​ is a valid CNF on VVV (every clause uses only variables of VVV), every clause has exactly three literals, all literals are positive, and every satisfying assignment sets at least ttt variables to one:

Ps,t3 is a t-threshold 3-uniform monotone CNF on 3t−s variables.P^3_{s,t}\ \text{is a } t\text{-threshold 3-uniform monotone CNF on } 3t-s \text{ variables.}Ps,t3​ is a t-threshold 3-uniform monotone CNF on 3t−s variables.

This is the witness side of the lower bounds in Theorem 3.10: together with the count of Fact 3.8 it shows that Φ0(s,t)≥θt(Ps,t3)\Phi_0(s,t)\ge\theta_t(P^3_{s,t})Φ0​(s,t)≥θt​(Ps,t3​).

Differences from the source:

  • correction: the s = 1 branch for every t ≥ 1 → s = 1 only for t ≥ 2; reason: at t = 1 the branch is (t − 2)·K3 + T5 = (−1)·K3 + T5, which is undefined, and would sit on 3t − s = 2 variables while T5 needs 5
  • encoding: n = 3t − s variables → the variable set {0, …, 3t − s − 1} ⊂ ℕ, with 3t − s computed in ℤ; reason: relabeling variables changes no clause, assignment or weight; on the stated ranges 3t − s ≥ 0
Preamble
import Definitions.Def_MajorityDepthThree_Exact_Supplement_Constructions

set_option autoImplicit false
Formal statement
namespace MajorityDepthThree.Exact.Supplement

open MajorityDepthThree.Exact

/-- Fact 3.7 (p. 9): on the `3t - s` variables `range (3t - s)`, `P^3_{s,t}` is a valid
`t`-threshold 3-uniform monotone CNF, for every `(s,t)` in the domain of its definition:
`s ≤ 0`; `s = 1` with `t ≥ 2` (corrected: the printed `t ≥ 1` would use `-1` copies of
`K₃` at `t = 1`); `2 ≤ s ≤ t`. -/
theorem construction_threshold (s : ℤ) (t : ℕ)
    (hdom : s ≤ 0 ∨ (s = 1 ∧ 2 ≤ t) ∨ (2 ≤ s ∧ s ≤ t)) :
    let V : Finset ℕ := Finset.range (3 * (t : ℤ) - s).toNat
    ValidCNF V (P3 s t) ∧ Uniform 3 (P3 s t) ∧ Monotone (P3 s t) ∧
      Threshold V (P3 s t) t := by sorry

end MajorityDepthThree.Exact.Supplement
Source
Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Michael Saks, Navid Talebanfard, STOC 2027 submission #677 (October 2026), p.9, Fact 3.7 and the definition of P^3_{s,t} (Section 3.3)

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