Deficit maxima , disjoint sums and the constructions
DefinitionMajorityDepthThree_Exact_Supplement_ConstructionsThis file builds on the published CNF interface (finite ambient variable set , signed clauses, transversals, the count of satisfying sets of size exactly , the -threshold property and the maximum over all signed valid -threshold CNFs of width at most ).
Monotone maximum. For a finite variable set , the number is the maximum of over all valid, width-at-most-, -threshold CNFs on that are monotone (no negative literals); it is when no such CNF exists.
Deficit parameterization (Definition 3.6). For an integer (the deficit) and a natural number , put (read as if negative) and . Then
the maxima of the number of -transversals over monotone, respectively all signed, -threshold 3-CNFs on variables.
Blocks and sums. Block CNFs use the natural numbers as variables; a block on variables uses . Shifting a CNF by adds to every variable. The disjoint sum , with on variables, is together with shifted by ; the multiple of a CNF on variables is the union of the copies of shifted by . The blocks are ; , all four 3-subsets of ; (the paper's with every variable lowered by one); and with , the six clauses .
The construction is the monotone 3-CNF, on the variables ,
For the last variables are isolated; in the other cases the blocks use exactly 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 is only meaningful for .
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