Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Deficit maxima Φ0(s,t)\Phi_0(s,t)Φ0​(s,t), disjoint sums and the constructions Ps,t3P^3_{s,t}Ps,t3​

Definition
MajorityDepthThree_Exact_Supplement_Constructions

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

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

This file builds on the published CNF interface (finite ambient variable set VVV, signed clauses, transversals, the count θt\theta_tθt​ of satisfying sets of size exactly ttt, the ttt-threshold property and the maximum Θ(∣V∣,t,k)\Theta(|V|,t,k)Θ(∣V∣,t,k) over all signed valid ttt-threshold CNFs of width at most kkk).

Monotone maximum. For a finite variable set VVV, the number Θ+(V,t,k)\Theta^{+}(V,t,k)Θ+(V,t,k) is the maximum of θt(F)\theta_t(F)θt​(F) over all valid, width-at-most-kkk, ttt-threshold CNFs FFF on VVV that are monotone (no negative literals); it is 000 when no such CNF exists.

Deficit parameterization (Definition 3.6). For an integer sss (the deficit) and a natural number ttt, put n=3t−sn=3t-sn=3t−s (read as 000 if negative) and V={0,…,n−1}V=\{0,\dots,n-1\}V={0,…,n−1}. Then

Φ0(s,t)=Θ+(V,t,3),Θdef(s,t)=Θ(n,t,3),\Phi_0(s,t)=\Theta^{+}(V,t,3),\qquad \Theta_{\mathrm{def}}(s,t)=\Theta(n,t,3),Φ0​(s,t)=Θ+(V,t,3),Θdef​(s,t)=Θ(n,t,3),

the maxima of the number of ttt-transversals over monotone, respectively all signed, ttt-threshold 3-CNFs on 3t−s3t-s3t−s variables.

Blocks and sums. Block CNFs use the natural numbers as variables; a block on mmm variables uses 0,…,m−10,\dots,m-10,…,m−1. Shifting a CNF by ooo adds ooo to every variable. The disjoint sum F1+F2F_1+F_2F1​+F2​, with F1F_1F1​ on m1m_1m1​ variables, is F1F_1F1​ together with F2F_2F2​ shifted by m1m_1m1​; the multiple ℓ⋅F\ell\cdot Fℓ⋅F of a CNF on mmm variables is the union of the copies of FFF shifted by 0,m,…,(ℓ−1)m0,m,\dots,(\ell-1)m0,m,…,(ℓ−1)m. The blocks are K3(3)={{0,1,2}}K_3^{(3)}=\{\{0,1,2\}\}K3(3)​={{0,1,2}}; K4(3)K_4^{(3)}K4(3)​, all four 3-subsets of {0,1,2,3}\{0,1,2,3\}{0,1,2,3}; T5(3)={{0,1,2},{2,3,4},{0,1,3}}T_5^{(3)}=\{\{0,1,2\},\{2,3,4\},\{0,1,3\}\}T5(3)​={{0,1,2},{2,3,4},{0,1,3}} (the paper's {{1,2,3},{3,4,5},{1,2,4}}\{\{1,2,3\},\{3,4,5\},\{1,2,4\}\}{{1,2,3},{3,4,5},{1,2,4}} with every variable lowered by one); and T6(3)T_6^{(3)}T6(3)​ with x0,y0,x1,y1,x2,y2=0,…,5x_0,y_0,x_1,y_1,x_2,y_2=0,\dots,5x0​,y0​,x1​,y1​,x2​,y2​=0,…,5, the six clauses {x0,y0,x1},{x0,y0,y1},{x1,y1,x2},{x1,y1,y2},{x2,y2,x0},{x2,y2,y0}\{x_0,y_0,x_1\},\{x_0,y_0,y_1\},\{x_1,y_1,x_2\},\{x_1,y_1,y_2\},\{x_2,y_2,x_0\},\{x_2,y_2,y_0\}{x0​,y0​,x1​},{x0​,y0​,y1​},{x1​,y1​,x2​},{x1​,y1​,y2​},{x2​,y2​,x0​},{x2​,y2​,y0​}.

The construction Ps,t3P^3_{s,t}Ps,t3​ is the monotone 3-CNF, on the variables {0,…,3t−s−1}\{0,\dots,3t-s-1\}{0,…,3t−s−1},

Ps,t3={t⋅K3(3)s≤0,(t−2)⋅K3(3)+T5(3)s=1,(t−s)⋅K3(3)+s2⋅K4(3)s even, 2≤s≤t,(t−s)⋅K3(3)+s−32⋅K4(3)+T6(3)s odd, 3≤s≤t.P^3_{s,t}=\begin{cases} t\cdot K_3^{(3)} & s\le 0,\\ (t-2)\cdot K_3^{(3)}+T_5^{(3)} & s=1,\\ (t-s)\cdot K_3^{(3)}+\tfrac s2\cdot K_4^{(3)} & s \text{ even},\ 2\le s\le t,\\ (t-s)\cdot K_3^{(3)}+\tfrac{s-3}2\cdot K_4^{(3)}+T_6^{(3)} & s\text{ odd},\ 3\le s\le t.\end{cases}Ps,t3​=⎩⎨⎧​t⋅K3(3)​(t−2)⋅K3(3)​+T5(3)​(t−s)⋅K3(3)​+2s​⋅K4(3)​(t−s)⋅K3(3)​+2s−3​⋅K4(3)​+T6(3)​​s≤0,s=1,s even, 2≤s≤t,s odd, 3≤s≤t.​

For s≤0s\le0s≤0 the last −s-s−s variables are isolated; in the other cases the blocks use exactly 3t−s3t-s3t−s variables.

These objects carry the paper's §3.3 constructions and the deficit profile of Theorem 3.10.

Formalization Note. Outside the parameter ranges listed above, P3 s t is a meaningless value (natural-number subtraction truncates); every theorem using it restricts to those ranges. The case s=1s=1s=1 is only meaningful for t≥2t\ge2t≥2.

Definition code
import Definitions.Def_MajorityDepthThree_Exact_CNF

set_option autoImplicit false

namespace MajorityDepthThree.Exact.Supplement

open MajorityDepthThree.Exact

/-! Gurumukhani–Kleber–Paturi–Rosin–Saks–Talebanfard, STOC 2027 submission #677,
pp. 7–9: Definition 3.1, Examples 3.3–3.4, Definition 3.6 and the construction
`P^3_{s,t}` of §3.3. Block CNFs live on the variables `ℕ`; a block on `m` variables
uses exactly the variables `0, …, m - 1`, and the ambient variable set of a CNF built
here is `Finset.range n`. -/

section Maxima

variable {α : Type} [DecidableEq α] [Fintype α]

/-- Valid, width-at-most-`k`, `t`-threshold CNFs on `V` that are moreover monotone. -/
noncomputable def monoCandidates (V : Finset α) (t k : ℕ) : Finset (CNF α) := by
  classical
  exact (candidates V t k).filter (fun F => Monotone F)

/-- The maximum of `θ_t` over the monotone `t`-threshold `k`-CNFs on `V`
(zero if there is none). -/
noncomputable def thetaMaxMono (V : Finset α) (t k : ℕ) : ℕ :=
  (monoCandidates V t k).sup (fun F => theta V F t)

end Maxima

/-- `Φ₀(s,t)` (Definition 3.6): the maximum number of `t`-transversals of a `t`-threshold
monotone 3-CNF on `n = 3t - s` variables. -/
noncomputable def Phi0 (s : ℤ) (t : ℕ) : ℕ :=
  thetaMaxMono (Finset.univ : Finset (Fin (3 * (t : ℤ) - s).toNat)) t 3

/-- `Θ(3t - s, t, 3)`: the maximum over all (signed) `t`-threshold 3-CNFs on `3t - s`
variables, i.e. the base `thetaMax` at deficit `s`. -/
noncomputable def ThetaDeficit (s : ℤ) (t : ℕ) : ℕ :=
  thetaMax (Finset.univ : Finset (Fin (3 * (t : ℤ) - s).toNat)) t 3

/-- Shift every variable of a clause by `o`. -/
def shiftClause (o : ℕ) (c : Clause ℕ) : Clause ℕ :=
  (c.1.map (addRightEmbedding o), c.2.map (addRightEmbedding o))

/-- Shift every variable of a CNF by `o`. -/
def shift (o : ℕ) (F : CNF ℕ) : CNF ℕ := F.image (shiftClause o)

/-- Disjoint sum `F₁ + F₂`: `F₁` on the variables `0, …, m₁ - 1` and a copy of `F₂`
placed on the variables `m₁, m₁ + 1, …`. -/
def disjSum (m₁ : ℕ) (F₁ F₂ : CNF ℕ) : CNF ℕ := F₁ ∪ shift m₁ F₂

/-- `ℓ · F`: `ℓ` disjoint copies of a CNF `F` on `m` variables, copy `j` on the
variables `j m, …, j m + m - 1`. -/
def copies (ℓ m : ℕ) (F : CNF ℕ) : CNF ℕ :=
  (Finset.range ℓ).biUnion (fun j => shift (j * m) F)

/-- The monotone clause with positive variable set `S`. -/
def posClause (S : Finset ℕ) : Clause ℕ := (S, ∅)

/-- `K₃^{(3)} = {{1,2,3}}` on the variables `0,1,2`. -/
noncomputable def K3 : CNF ℕ := clique (Finset.range 3) 3

/-- `K₄^{(3)}`: all four 3-subsets of the variables `0,1,2,3`. -/
noncomputable def K4 : CNF ℕ := clique (Finset.range 4) 3

/-- `T₅^{(3)} = {{1,2,3},{3,4,5},{1,2,4}}` (Example 3.3), variables `1,…,5` renamed
`0,…,4`. -/
def T5 : CNF ℕ :=
  {posClause {0, 1, 2}, posClause {2, 3, 4}, posClause {0, 1, 3}}

/-- `T₆^{(3)}` (Example 3.4) with `x₀,y₀,x₁,y₁,x₂,y₂ = 0,1,2,3,4,5`:
`{x₀,y₀,x₁}, {x₀,y₀,y₁}, {x₁,y₁,x₂}, {x₁,y₁,y₂}, {x₂,y₂,x₀}, {x₂,y₂,y₀}`. -/
def T6 : CNF ℕ :=
  {posClause {0, 1, 2}, posClause {0, 1, 3}, posClause {2, 3, 4},
   posClause {2, 3, 5}, posClause {4, 5, 0}, posClause {4, 5, 1}}

/-- `P^3_{s,t}` (§3.3, p. 9), a monotone 3-CNF on the variables `range (3t - s)`:
* `t · K₃` if `s ≤ 0` (the remaining `-s` variables are isolated);
* `(t - 2) · K₃ + T₅` if `s = 1`;
* `(t - s) · K₃ + (s/2) · K₄` if `s` is even, `2 ≤ s ≤ t`;
* `(t - s) · K₃ + ((s - 3)/2) · K₄ + T₆` if `s` is odd, `3 ≤ s ≤ t`.
Outside these parameter ranges the value carries no meaning. -/
noncomputable def P3 (s : ℤ) (t : ℕ) : CNF ℕ :=
  if s ≤ 0 then copies t 3 K3
  else if s = 1 then disjSum (3 * (t - 2)) (copies (t - 2) 3 K3) T5
  else if s % 2 = 0 then
    disjSum (3 * (t - s.toNat)) (copies (t - s.toNat) 3 K3) (copies (s.toNat / 2) 4 K4)
  else
    disjSum (3 * (t - s.toNat)) (copies (t - s.toNat) 3 K3)
      (disjSum (4 * ((s.toNat - 3) / 2)) (copies ((s.toNat - 3) / 2) 4 K4) T6)

end MajorityDepthThree.Exact.Supplement
Source
Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Michael Saks, Navid Talebanfard, STOC 2027 submission #677 (October 2026), pp.7–9, Definition 3.1, Examples 3.3–3.4, Definition 3.6 and the definition of P^3_{s,t} in 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