Proof of Theorem 4.2 —
ProvedNCQuadLB.nd_le_six_mularithmetic-circuitscomputational-complexitylower-boundsnoncommutative-polynomialsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let , , and let be a natural number with . Then:
- if ,
- in every case, .
With the counting inequality for circuits, this is the numerical half of Theorem 4.2.
Formalization Note is stated as in ; and is the real power.
Differences from the source:
- generalization: the number of product gates of a circuit computing → any natural number with ; reason: the conclusion uses only this inequality, which every such circuit satisfies (the counting milestone)
- generalization: "" in the case , and "" in the case → in both cases; reason: an explicit constant implies ; the source's case-2 intermediate "this implies " is false for and is not stated
- encoding: ; ; → ; ; in ; reason: the same conditions and values
Preamble
import Mathlib
Formal statement
namespace NCQuadLB
/-- **Proof of Theorem 4.2, the numerical conclusion** (Shastri, Willumsgaard, *A Quadratic Lower Bound for Noncommutative Circuits*, arXiv:2604.20575, version of November 2, 2026, sha256 34159453…, p.8). Let `n ≥ 2`, `d ≥ 1` and let `S`
be a natural number with `n^d ≤ ∑_{k=0}^d (S choose k)`. If `d ≤ S/2` then
`S ≥ nd/(e(d+1)^{1/d}) ≥ (nd)/6`; and in every case `S ≥ (nd)/6`.
**Formalization Note** `S` is any natural number satisfying the counting inequality (for a circuit
computing `Pal_{n,d}`, its number of product gates, by the counting milestone). `d ≤ S/2` is `2d ≤ S`,
`e = Real.exp 1`, `(d+1)^{1/d}` is the real power. `S ≥ (nd)/6` is stated as `nd ≤ 6S` in `ℕ`. -/
theorem nd_le_six_mul (n d S : ℕ) (hn : 2 ≤ n) (hd : 1 ≤ d)
(hcount : n ^ d ≤ ∑ k ∈ Finset.range (d + 1), S.choose k) :
(2 * d ≤ S →
((n : ℝ) * d) / (Real.exp 1 * ((d : ℝ) + 1) ^ ((1 : ℝ) / d)) ≤ S ∧
((n : ℝ) * d) / 6 ≤ ((n : ℝ) * d) / (Real.exp 1 * ((d : ℝ) + 1) ^ ((1 : ℝ) / d))) ∧
n * d ≤ 6 * S := by sorry
end NCQuadLB
Source
Shastri, Willumsgaard, A Quadratic Lower Bound for Noncommutative Circuits, arXiv:2604.20575 (version of November 2, 2026, sha256 34159453…), proof of Theorem 4.2, p.8 ("Therefore, S ≥ nd/(e(d+1)^{1/d}) ≥ (nd)/6, and we're done.")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.