Fact 3.8 — exact (corrected: odd case excludes (s,t) = (1,1))
OpenMajorityDepthThree.Exact.Supplement.construction_countcircuit-complexityextremal-combinatoricsp2o-batch-stoc27sp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1
For an integer and a natural number , let and let be the number of satisfying assignments of the construction on with exactly variables set to one. Then
These are exact equalities of real numbers. They give the lower bounds of Theorem 3.10 for the monotone maximum via the witness of Fact 3.7.
Differences from the source:
- correction: odd case for all 1 ≤ s ≤ t → odd case for 1 ≤ s ≤ t except (s,t) = (1,1); reason: at s = t = 1 the printed value is 7/3, not an integer, so no count can equal it; P^3_{1,1} is moreover undefined
- encoding: n = 3t − s variables → the variable set {0, …, 3t − s − 1} ⊂ ℕ, with 3t − s computed in ℤ; reason: relabeling changes no count; on the stated ranges 3t − s ≥ 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
/-- Fact 3.8 (p. 9): the exact number of `t`-transversals of `P^3_{s,t}` on the
variables `range (3t - s)`. Corrected: the odd case excludes `(s,t) = (1,1)`, where
the printed value `7/3` is not an integer (and `P^3_{1,1}` is undefined). -/
theorem construction_count :
(∀ (s : ℤ) (t : ℕ), s ≤ 0 →
(theta (Finset.range (3 * (t : ℤ) - s).toNat) (P3 s t) t : ℝ) = 3 ^ t) ∧
(∀ (s : ℤ) (t : ℕ), Even s → 1 ≤ s → s ≤ t →
(theta (Finset.range (3 * (t : ℤ) - s).toNat) (P3 s t) t : ℝ) =
(2 / 3 : ℝ) ^ (s.toNat / 2) * 3 ^ t) ∧
(∀ (s : ℤ) (t : ℕ), Odd s → 1 ≤ s → s ≤ t → ¬ (s = 1 ∧ t = 1) →
(theta (Finset.range (3 * (t : ℤ) - s).toNat) (P3 s t) t : ℝ) =
(7 / 9 : ℝ) * (2 / 3 : ℝ) ^ ((s.toNat - 1) / 2) * 3 ^ 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.8