{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreie3xxp4bye5raf6r2gnrky3nhcj6ju62ac6754gdx2eyfruq7ac6m",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mkhv44xbd452"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.22006v1",
  "publishedAt": "2026-04-27T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Ran Raz"
  ],
  "textContent": "**Authors:** Ran Raz\n\nWe prove a lower bound of $Ω\\left(n^{1.5}\\right)$ for the number of product gates in non-commutative arithmetic circuits for an explicit $n$-variate degree-$n$ polynomial $f_{n}$ (over every field). We observe that this implies that over certain non-commutative rings $R$, any arithmetic circuit that computes the induced polynomial function $f_{n}: R^n \\rightarrow R$, using the ring operations of addition and multiplication in $R$, requires at least $Ω\\left(n^{1.5}\\right)$ multiplications. More generally, for any $d\\geq 2$ and sufficiently large $n$, we obtain a lower bound of $Ω\\left(d\\sqrt{n}\\right)$ for $n$-variate degree-$d$ polynomials, for both these models. Prior to our work, the only known lower bounds for the size of non-commutative circuits, or for the size of arithmetic circuits over any ring, were slightly super-linear in $\\max\\\\{n,d\\\\}$: $Ω\\left(n\\log d\\right)$ by Baur and Strassen, and $Ω\\left(d\\log n\\right)$ by Nisan. (Nisan's bound was proved for non-commutative arithmetic circuits and implies a bound for arithmetic circuits over non-commutative rings by our observation).",
  "title": "Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings"
}