<p>I don’t know where the lower bound comes from as Wigderson gives no reference, but it is suboptimal. One can easily prove the following bound:</p>
<blockquote>
<p><strong>Proposition:</strong> For any field <span class="math-container">$F$</span> and <span class="math-container">$d\in\mathbb N$</span>, there exists a degree-<span class="math-container">$d$</span> polynomial <span class="math-container">$f\in F[x]$</span> such that
<span class="math-container">$$S(f)=\begin{cases}\Omega(d)&amp;\text{if }|F|\ge d,\\
\Omega\left(\frac{d\log|F|}{\log d}\right)&amp;\text{otherwise.}
\end{cases}$$</span></p>
</blockquote>
<p><strong>Proof:</strong></p>
<p>If <span class="math-container">$F=\mathbb F_q$</span> is finite, a circuit of size <span class="math-container">$s$</span> can be described by <span class="math-container">$O\bigl(s(\log q+\log s)\bigr)$</span> bits, but there are <span class="math-container">$|F|^{d+1}$</span> distinct degree-<span class="math-container">$d$</span> polynomials, hence some require size <span class="math-container">$s$</span> such that
<span class="math-container">$$s(\log q+\log s)=\Omega(d\log q),$$</span>
i.e.,
<span class="math-container">$$s=\Omega(d)\qquad\text{or}\qquad s=\Omega\left(\frac{d\log q}{\log d}\right)$$</span>
whichever is smaller.</p>
<p>If <span class="math-container">$F$</span> has transcendence degree <span class="math-container">$\ge d+1$</span>, pick algebraically independent <span class="math-container">$a_0,\dots,a_d\in F$</span>. Then any circuit for <span class="math-container">$f=\sum_{i\le d}a_ix^i$</span> must use at least <span class="math-container">$d+1$</span> constants from <span class="math-container">$F$</span>, as the coefficients of the polynomial are in the subring of <span class="math-container">$F$</span> generated by these constants. Also, any circuit for <span class="math-container">$f$</span> must use at least <span class="math-container">$d+1$</span> additions and multiplications (by constant folding, we may simplify any circuit so that each addition or multiplication gate has at most one constant input), thus counting also the variable gate, it has total size at least <span class="math-container">$2d+3$</span>.</p>
<p>In general, if <span class="math-container">$F$</span> is infinite, it has an elementary extension <span class="math-container">$F^*\succeq F$</span> of infinite transcendence degree. By the previous paragraph, <span class="math-container">$F^*$</span> satisfies “there exist <span class="math-container">$a_0,\dots,a_{d+1}$</span> such that no circuit of size <span class="math-container">$\le2d+2$</span> or with <span class="math-container">$\le d$</span> addition and multiplication gates computes <span class="math-container">$\sum_{i\le d}a_ix^i$</span>”. This can be expressed by a first-order sentence, as for a fixed <span class="math-container">$s$</span>, there are only finitely many “circuit skeletons” (i.e., circuits disregarding the values of constants) of size <span class="math-container">$s$</span>, or constant-folded circuit skeletons with <span class="math-container">$s$</span> addition and multiplication gates. Thus, by elementarity, this sentence also holds in <span class="math-container">$F$</span>. QED</p>
<p>It is also easy to show that these bounds are tight up to a linear factor. Moreover, with a bit more effort, one can prove that they hold over arbitrary commutative rings rather than just fields (the main issue is to prove that every infinite ring <span class="math-container">$R$</span> has an elementary extension <span class="math-container">$R^*$</span> that contains a subset of size <span class="math-container">$d+1$</span> that is not included in any <span class="math-container">$d$</span>-generated subring).</p>
<p>Note also that for <span class="math-container">$F$</span> of infinite transcendence degree such as <span class="math-container">$\mathbb R$</span>, the proof above does give explicit examples of such polynomials: for example,
<span class="math-container">$$f(x)=e^{\sqrt2}+e^{\sqrt3}x+e^{\sqrt5}x^2+\dots+e^{\sqrt{p_{d+1}}}x^d,$$</span>
where <span class="math-container">$p_n$</span> denotes the <span class="math-container">$n$</span>th prime (these coefficients are algebraically independent by the Lindemann–Weierstrass theorem).</p>
<p>I don’t know whether this particular statement appears in the literature, but you can find various related linear lower bounds on the number of additions or multiplications e.g. in §4.6.4 of D. E. Knuth, <em>The Art of Computer Programming</em>,
Vol. 2: <em>Seminumerical Algorithms</em>.</p>

CC BY-SA 4.0
2024-11-17T04:14:00.303Z
Thanks for the detailed answered. It is interesting that this construction exists but was not mentioned in the text. You say "Note also that for $F$ of infinite transcendence degree such as $\mathbb{R}$, the proof above does give explicit examples of such polynomials." But still the problem is open for general fields (and I guess general commutative rings)?
Anakin Dey
CC BY-SA 4.0
2024-11-17T06:16:33.097Z
Strassen gives some examples of hard polynomials with large rational coefficients in [Polynomials with Rational Coefficients Which are Hard to Compute](https://doi.org/10.1137/0203010). You can find more about this topic in Chapter 9 of Bürgisser--Clausen--Shokrollahi.
Robert Andrews
CC BY-SA 4.0
2024-11-17T06:19:43.987Z
By the way, the $\Omega(\sqrt{d})$ lower bound from Avi's book may have been intended as a reference to lower bounds on multiplicative complexity, not circuit size. Proposition 9.1 in BCS proves a $2 \sqrt{d}$ upper bound on the multiplicative complexity of any degree-$d$ univariate polynomial, so $\Omega(\sqrt{d})$ is the best-possible lower bound on multiplicative complexity.
Robert Andrews
CC BY-SA 4.0
2024-11-17T07:18:12.133Z
@RobertAndrews This is a plausible interpretation, but then the wording in the book is misleading (he explicitly defines $S(f)$ as counting both additions and multiplications, and does not mention that the bound is meant for multiplications only).
Emil Jeřábek
CC BY-SA 4.0
2024-11-16T11:27:15.877Z
2024-11-16T11:32:38.603Z
2024-11-16T11:32:38.603Z
Emil Jeřábek
<p>This is in reference to Open Problem 12.1 in Wigdersons's <a href="https://www.math.ias.edu/files/Book-online-Aug0619.pdf#page=140" rel="nofollow noreferrer">Mathematics and Computation</a>. It states that while we know that some polynomial <span class="math-container">$f \in \mathbb{F}[x]$</span> exists such that it requires a circuit of size <span class="math-container">$\Omega(\sqrt{d})$</span>, no such explicit example is known. I am curious about where this result comes from as well as analogous existance-without-example results in the multivariable setting.</p>

<polynomials><algebraic-complexity>
Some polynomials in $\mathbb{F}[x]$ require $O(\sqrt{d})$ circuit size
Anakin Dey
# Some polynomials in $\mathbb{F}[x]$ require $O(\sqrt{d})$ circuit size

(Asked by: username_0 on 2024-11-16)

This is in reference to Open Problem 12.1 in Wigdersons's [Mathematics and Computation](https://www.math.ias.edu/files/Book-online-Aug0619.pdf#page=140). It states that while we know that some polynomial $f \in \mathbb{F}[x]$ exists such that it requires a circuit of size $\Omega(\sqrt{d})$, no such explicit example is known. I am curious about where this result comes from as well as analogous existance-without-example results in the multivariable setting.

**Tags:** polynomials, algebraic-complexity


---

## 1 answers

### Answer by username_1 on 2024-11-16. Score: 5 | Accepted answer

I don’t know where the lower bound comes from as Wigderson gives no reference, but it is suboptimal. One can easily prove the following bound:

> **Proposition:** For any field $F$ and $d\in\mathbb N$, there exists a degree-$d$ polynomial $f\in F[x]$ such that
> $$S(f)=\begin{cases}\Omega(d)&\text{if }|F|\ge d,\\
> \Omega\left(\frac{d\log|F|}{\log d}\right)&\text{otherwise.}
> \end{cases}$$

**Proof:**

If $F=\mathbb F\_q$ is finite, a circuit of size $s$ can be described by $O\bigl(s(\log q+\log s)\bigr)$ bits, but there are $|F|^{d+1}$ distinct degree-$d$ polynomials, hence some require size $s$ such that
$$s(\log q+\log s)=\Omega(d\log q),$$
i.e.,
$$s=\Omega(d)\qquad\text{or}\qquad s=\Omega\left(\frac{d\log q}{\log d}\right)$$
whichever is smaller.

If $F$ has transcendence degree $\ge d+1$, pick algebraically independent $a\_0,\dots,a\_d\in F$. Then any circuit for $f=\sum\_{i\le d}a\_ix^i$ must use at least $d+1$ constants from $F$, as the coefficients of the polynomial are in the subring of $F$ generated by these constants. Also, any circuit for $f$ must use at least $d+1$ additions and multiplications (by constant folding, we may simplify any circuit so that each addition or multiplication gate has at most one constant input), thus counting also the variable gate, it has total size at least $2d+3$.

In general, if $F$ is infinite, it has an elementary extension $F^\*\succeq F$ of infinite transcendence degree. By the previous paragraph, $F^\*$ satisfies “there exist $a\_0,\dots,a\_{d+1}$ such that no circuit of size $\le2d+2$ or with $\le d$ addition and multiplication gates computes $\sum\_{i\le d}a\_ix^i$”. This can be expressed by a first-order sentence, as for a fixed $s$, there are only finitely many “circuit skeletons” (i.e., circuits disregarding the values of constants) of size $s$, or constant-folded circuit skeletons with $s$ addition and multiplication gates. Thus, by elementarity, this sentence also holds in $F$. QED

It is also easy to show that these bounds are tight up to a linear factor. Moreover, with a bit more effort, one can prove that they hold over arbitrary commutative rings rather than just fields (the main issue is to prove that every infinite ring $R$ has an elementary extension $R^\*$ that contains a subset of size $d+1$ that is not included in any $d$-generated subring).

Note also that for $F$ of infinite transcendence degree such as $\mathbb R$, the proof above does give explicit examples of such polynomials: for example,
$$f(x)=e^{\sqrt2}+e^{\sqrt3}x+e^{\sqrt5}x^2+\dots+e^{\sqrt{p\_{d+1}}}x^d,$$
where $p\_n$ denotes the $n$th prime (these coefficients are algebraically independent by the Lindemann–Weierstrass theorem).

I don’t know whether this particular statement appears in the literature, but you can find various related linear lower bounds on the number of additions or multiplications e.g. in §4.6.4 of D. E. Knuth, *The Art of Computer Programming*,
Vol. 2: *Seminumerical Algorithms*.

> **Comments:**
> **username_0**: Thanks for the detailed answered. It is interesting that this construction exists but was not mentioned in the text. You say "Note also that for $F$ of infinite transcendence degree such as $\mathbb{R}$, the proof above does give explicit examples of such polynomials." But still the problem is open for general fields (and I guess general commutative rings)?  
> **username_2**: Strassen gives some examples of hard polynomials with large rational coefficients in [Polynomials with Rational Coefficients Which are Hard to Compute](https://doi.org/10.1137/0203010). You can find more about this topic in Chapter 9 of Bürgisser--Clausen--Shokrollahi.  
> **username_2**: By the way, the $\Omega(\sqrt{d})$ lower bound from Avi's book may have been intended as a reference to lower bounds on multiplicative complexity, not circuit size. Proposition 9.1 in BCS proves a $2 \sqrt{d}$ upper bound on the multiplicative complexity of any degree-$d$ univariate polynomial, so $\Omega(\sqrt{d})$ is the best-possible lower bound on multiplicative complexity.  
> **username_1**: @RobertAndrews This is a plausible interpretation, but then the wording in the book is misleading (he explicitly defines $S(f)$ as counting both additions and multiplications, and does not mention that the bound is meant for multiplications only).  

---

