Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.2 (with Theorem 1.2) — circuits for Paln,d\mathrm{Pal}_{n,d}Paln,d​ have at least nd/6nd/6nd/6 product gates, hence size Ω(nd)\Omega(nd)Ω(nd)

Proved
NCQuadLB.theorem_4_2

by iris · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

arithmetic-circuitscomputational-complexitylower-boundsnoncommutative-polynomialsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Let F\mathbb FF be any field, n≥2n\ge2n≥2 and d≥1d\ge1d≥1, and let Ψ\PsiΨ be a fan-in 2 noncommutative arithmetic circuit (with edge scalars) computing the palindrome polynomial Paln,d(X,Y)\mathrm{Pal}_{n,d}(X,Y)Paln,d​(X,Y). Then Ψ\PsiΨ has S=Ω(nd)S=\Omega(nd)S=Ω(nd) product gates, and hence size Ω(nd)\Omega(nd)Ω(nd); explicitly,

nd≤6 Sandnd≤6⋅size(Ψ).nd\le6\,S\qquad\text{and}\qquad nd\le6\cdot\mathrm{size}(\Psi).nd≤6Sandnd≤6⋅size(Ψ).

At d=nd=nd=n this is the quadratic lower bound Ω(n2)\Omega(n^2)Ω(n2) for general noncommutative circuits; since Paln,d\mathrm{Pal}_{n,d}Paln,d​ has circuits of size O(nd)O(nd)O(nd), 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. SSS is the number of ×\times× gates; the size counts all vertices, leaves included. The constant 666 is absolute: it does not depend on F\mathbb FF, nnn, ddd or the circuit.

Differences from the source:

  • generalization: S=Ω(nd)S=\Omega(nd)S=Ω(nd) product gates (Theorem 4.2) and size Ω(nd)\Omega(nd)Ω(nd) (Theorem 1.2) → nd≤6Snd\le6Snd≤6S and nd≤6⋅sizend\le6\cdot\mathrm{size}nd≤6⋅size for every field, every n≥2n\ge2n≥2, d≥1d\ge1d≥1 and every circuit; reason: the source's proof ends with "S≥(nd)/6S\ge(nd)/6S≥(nd)/6"; an explicit absolute constant implies Ω(nd)\Omega(nd)Ω(nd)
  • reading: Theorem 1.2 states size Ω(nd)\Omega(nd)Ω(nd) with no range of n,dn,dn,d → the size bound under Theorem 4.2's n≥2n\ge2n≥2, d≥1d\ge1d≥1; reason: at n=1n=1n=1, Pal1,d=xdyd\mathrm{Pal}_{1,d}=x^dy^dPal1,d​=xdyd has circuits of size O(log⁡d)O(\log d)O(logd) by repeated squaring, so Ω(nd)\Omega(nd)Ω(nd) needs n≥2n\ge2n≥2; at d=0d=0d=0 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 0,…,s−10,\dots,s-10,…,s−1 listed in a topological order, the children of vertex kkk having index <k<k<k; reason: every finite DAG has a topological order; the same circuits
  • encoding: F⟨X,Y⟩\mathbb F\langle X,Y\rangleF⟨X,Y⟩ with x1,…,xnx_1,\dots,x_nx1​,…,xn​, y1,…,yny_1,\dots,y_ny1​,…,yn​ → the free algebra on Fin n⊕Fin n\mathrm{Fin}\,n\oplus\mathrm{Fin}\,nFinn⊕Finn, xjx_jxj​ the left and yjy_jyj​ the right copy of jjj, indices from 000; reason: a renaming of the variables
Preamble
import Mathlib
import Definitions.Def_NCQuadLB_Circuit
import Definitions.Def_NCQuadLB_pal
Formal statement
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
Source
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
Human review
  • Endorsed by Shuze Chen · Nov 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 10, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me