Theorem 4.2 (with Theorem 1.2) — circuits for have at least product gates, hence size
ProvedNCQuadLB.theorem_4_2Let be any field, and , and let be a fan-in 2 noncommutative arithmetic circuit (with edge scalars) computing the palindrome polynomial . Then has product gates, and hence size ; explicitly,
At this is the quadratic lower bound for general noncommutative circuits; since has circuits of size , the bound is tight up to the constant.
Formalization Note A circuit lists its vertices in a topological order; every gate carries a scalar on each of its two in-edges, both in-edges may come from one vertex, and a designated vertex is the output. is the number of gates; the size counts all vertices, leaves included. The constant is absolute: it does not depend on , , or the circuit.
Differences from the source:
- generalization: product gates (Theorem 4.2) and size (Theorem 1.2) → and for every field, every , and every circuit; reason: the source's proof ends with ""; an explicit absolute constant implies
- reading: Theorem 1.2 states size with no range of → the size bound under Theorem 4.2's , ; reason: at , has circuits of size by repeated squaring, so needs ; at the bound is empty
- generalization: fan-in 2 circuits on a directed acyclic graph (two in-edges per gate) → both in-edges of a gate may come from the same vertex; reason: enlarges the class of circuits; every circuit of the source is one of these
- generalization: the root of the circuit → a designated output vertex; further vertices, even ones not below the output, are allowed and counted in the size and in the number of product gates; reason: enlarges the class of circuits; a circuit with a single root is the case where every vertex lies below the output
- encoding: a directed acyclic graph → vertices listed in a topological order, the children of vertex having index ; reason: every finite DAG has a topological order; the same circuits
- encoding: with , → the free algebra on , the left and the right copy of , indices from ; reason: a renaming of the variables
import Mathlib import Definitions.Def_NCQuadLB_Circuit import Definitions.Def_NCQuadLB_pal
namespace NCQuadLB
/-- **Theorem 4.2**, with **Theorem 1.2** (Shastri, Willumsgaard, *A Quadratic Lower Bound for Noncommutative Circuits*, arXiv:2604.20575, version of November 2, 2026, sha256 34159453…, Theorem 4.2, p.8; Theorem 1.2, p.3). Let `n ≥ 2`
and `d ≥ 1`, and let `Ψ` be a fan-in 2 noncommutative arithmetic circuit computing `Pal_{n,d}(X, Y)`.
Then `Ψ` has `S = Ω(nd)` many product gates; hence `Ψ` has size `Ω(nd)`.
**Formalization Note** `Ω(nd)` is stated with the explicit absolute constant of the source's proof
("`S ≥ … ≥ (nd)/6`"): `n·d ≤ 6·S` and `n·d ≤ 6·size`, for every field `F`, every `n ≥ 2`, `d ≥ 1` and
every circuit; the constant depends on nothing. Circuits are `Circuit F (Fin n ⊕ Fin n)`
(Definition 2.2: vertices in topological order, a scalar on every in-edge, both in-edges of a gate may
come from one vertex, a designated output vertex); `S` is `numMul`, the number of `×` gates, and the
size is the number of vertices, leaves included. `Pal_{n,d}` is `pal F n d` (`x_j = ι (Sum.inl j)`,
`y_j = ι (Sum.inr j)`). -/
theorem theorem_4_2 {F : Type*} [Field F] (n d : ℕ) (hn : 2 ≤ n) (hd : 1 ≤ d)
(C : Circuit F (Fin n ⊕ Fin n)) (hC : C.Computes (pal F n d)) :
n * d ≤ 6 * C.numMul ∧ n * d ≤ 6 * C.size := by sorry
end NCQuadLB
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.