Theorem 3.10 — deficit profile of (corrected: odd bound excludes (s,t) = (1,1))
OpenMajorityDepthThree.Exact.Supplement.deficit_profilecircuit-complexityextremal-combinatoricsp2o-batch-stoc27sp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1
For an integer deficit and a natural number , let . Write for the maximum number of -transversals (satisfying assignments with exactly ones) of a -threshold monotone 3-CNF on variables, and for the same maximum over all -threshold 3-CNFs, negative literals allowed (Definition 3.6 identifies the two). Then
- for all , : ;
- for all and : ;
- for even with : ;
- for odd with and : .
The equalities are exact maxima: line 1 includes the upper bound that no -threshold 3-CNF on at least variables has more than transversals of size . At even, , line 3 gives , the lower-bound side of Theorem 1.4 of the mission.
Differences from the source:
- correction: odd lower bound for all 1 ≤ s ≤ t → odd lower bound for 1 ≤ s ≤ t except (s,t) = (1,1); reason: at s = t = 1 it claims Φ0(1,1) ≥ 7/3, but n = 2 and the theorem's own second line gives Φ0(1,1) = binom(2,1) = 2
- reading: Φ0(s,t), defined as a maximum over monotone 3-CNFs and "in other words" equal to Θ(3t − s, t, 3) → the equalities stated for both the monotone maximum and the maximum over all signed 3-CNFs, the lower bounds for the monotone maximum; reason: Definition 3.6 gives both descriptions; stating the equalities for both and the lower bounds for the smaller monotone maximum keeps the stronger content of each
- encoding: n = 3t − s variables → the carrier Fin (toNat (3t − s)), with 3t − s computed in ℤ; reason: on every stated range 3t − s ≥ t ≥ 0
- encoding: exponents s/2 and (s − 1)/2 → natural-number exponents (toNat s)/2 and (toNat s − 1)/2; reason: in their cases s ≥ 1 and the divisions are exact
Preamble
import Definitions.Def_MajorityDepthThree_Exact_Supplement_Constructions set_option autoImplicit false
Formal statement
namespace MajorityDepthThree.Exact.Supplement
open MajorityDepthThree.Exact
/-- Theorem 3.10 (p. 10), the deficit profile of `Φ₀(s,t)`, `n = 3t - s`.
Equalities (1), (2) hold both for the monotone maximum `Φ₀` and for the maximum
`Θ(3t - s, t, 3)` over all signed 3-CNFs (Definition 3.6 identifies the two).
Corrected: the odd lower bound (4) excludes `(s,t) = (1,1)`, where it would claim
`Φ₀(1,1) ≥ 7/3`, contradicting line (2), `Φ₀(1,1) = binom(2,1) = 2`. -/
theorem deficit_profile :
(∀ (s : ℤ) (t : ℕ), s ≤ 0 → Phi0 s t = 3 ^ t ∧ ThetaDeficit s t = 3 ^ t) ∧
(∀ (s : ℤ) (t : ℕ), 1 ≤ t → 0 ≤ 2 * (t : ℤ) - 2 → 2 * (t : ℤ) - 2 ≤ s →
s ≤ 2 * (t : ℤ) →
Phi0 s t = Nat.choose (3 * (t : ℤ) - s).toNat t ∧
ThetaDeficit s t = Nat.choose (3 * (t : ℤ) - s).toNat t) ∧
(∀ (s : ℤ) (t : ℕ), Even s → 1 ≤ s → s ≤ t →
(2 / 3 : ℝ) ^ (s.toNat / 2) * 3 ^ t ≤ (Phi0 s t : ℝ)) ∧
(∀ (s : ℤ) (t : ℕ), Odd s → 1 ≤ s → s ≤ t → ¬ (s = 1 ∧ t = 1) →
(7 / 9 : ℝ) * (2 / 3 : ℝ) ^ ((s.toNat - 1) / 2) * 3 ^ t ≤ (Phi0 s 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.10, Theorem 3.10 (with Definition 3.6, p.9)