<p><a href="http://doi.ieeecomputersociety.org/10.1109/SWAT.1971.5" rel="nofollow">Paterson and Stockmeyer</a> show that for most $n$-tuples of rational numbers $(a_1, \dotsc, a_n)$, evaluating $\prod_{i=1}^{n} (x - a_i)$ requires $\Omega(\sqrt{n})$ arithmetic operations, and this is tight.</p>

<p>The following polynomials get within a logarithmic factor of the $\sqrt{n}$ bound, by results of Strassen, Schnorr, and Heintz &amp; Sieveking: $\sum_{i=1}^{n} 2^{2^{i}} x^{i}$, $\sum_{i=1}^{n} e^{2 \pi i / 2^{i}} x^{i}$, $\sum_{i=1}^{n} i^{r} x^{i}$ (for $r$ a rational that is not an integer), etc.  For exact references and for more on this, see pp. 324-325 of <a href="http://www.annualreviews.org/doi/abs/10.1146/annurev.cs.03.060188.001533" rel="nofollow">von zur Gathen's survey</a>.</p>

CC BY-SA 2.5
2010-11-30T22:07:08.947Z
Thanks.  So, it would seem that the open problem is that if you count additions also as operations, can one construct a polynomial which needs more than sqrt(n) operations, with the goal of constructing one which needs n operations.  Any results towards this? (I doubt it, because in the method that needs only sqrt(n) multiplications, the additions give some matrix multiplication and this probably reduces to lower bounds on complexity of a matrix-scalar multiplication)
matt hastings
CC BY-SA 2.5
2010-11-30T04:31:39.323Z
2010-11-30T14:13:22.057Z
2010-11-30T14:13:22.057Z
Joshua Grochow
<p>By counting arguments, one can show that there exist polynomials of degree n in 1 variable (i.e., something of the form $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0)$ which have circuit complexity n.  Also, one can show that a polynomial like $x^n$ requires at least $\log_2 n$ multiplications (you need that just to get a high enough degree).  Are there any explicit examples of polynomials in 1 variable with a superlogarithmic lower bound on complexity? (results over any field would be interesting)</p>

CC BY-SA 2.5
2010-11-30T04:33:21.787Z
Are the examples you have in mind with circuit complexity $n$ over a finite field? I don't see how a counting argument would work over an infinite field, and over the rationals I'm pretty sure Paterson-Stockmeyer's $\sqrt{n}$ bound is tight (see also my answer below).
Joshua Grochow
CC BY-SA 2.5
2010-11-30T22:04:51.213Z
The sqrt(n) bound you mention is just an upper bound on the number of multiplications (over any field), but if we count both additions and multiplications as operations, then we need n operations over an infinite field for almost every polynomial, just because there are n distinct coefficients in the polynomial and there's no way to evaluate all possible polynomials with less than n operations (I'm not sure if this should be called a counting argument or not).
matt hastings
CC BY-SA 2.5
2010-12-01T03:04:11.463Z
I think you have to be a bit more precise in the statement "there's no way to evaluate all possible polynomials with less than n ops." One way to interpret that is: if we think of the polynomial $\sum a_i x^i$ as a polynomial not just in $x$, but also treat the $a_i$'s as variables (or, equivalently, suppose the $a_i$ are algebraically independent), then the result that this requires n additions is Pan's (1966) and is not just a counting argument (though it's not too difficult). Otherwise, I'm not quite sure what result you're referring to with that statement.
Joshua Grochow
CC BY-SA 2.5
2010-12-01T15:45:25.777Z
What I mean is: the circuit consists of addition and multiplication gates.  The inputs for a given gate can be outputs of previous gates, or x, or some constants.  The question is: for a given polynomial, can we find a circuit and choice of constants in that circuit to compute it?  But, we have an (n+1)-dimensional space of polynomials, but if we fix the structure of a circuit with less than n gates (by "structure", I mean which gates use outputs of which other gates) and consider all possible choices of constants this gives less than an n dimensional space of polynomials that can be computed.
matt hastings
CC BY-SA 2.5
2010-12-01T15:51:56.907Z
Btw---the impression I get is that constructing explicit examples over R or C without further restrictions on the coefficients is mostly solved.  On the other hand, constructing explicit examples where all the coefficients a_i are integers and not growing too rapidly, it still open?  There is an example with all integer constants in the survey you mention, but they grow doubly exponentially.
matt hastings
CC BY-SA 2.5
2010-12-01T16:45:57.017Z
Ah, I see now. Nice counting argument :). (It took me a second to realize why Pan's result needed anything stronger than your argument, but Pan actually shows you need n multiplications, which is a stronger statement.)
Joshua Grochow
CC BY-SA 2.5
2010-12-01T16:46:53.233Z
As to your second comment, for multivariate polynomials there are good lower bound on some explicit polynomials even with only 0-1 coefficients (e.g. elementary symmetric polynomials). I do not know whether there are explicit hard-to-compute single-variable polynomials with small integer coefficients.
Joshua Grochow
<cc.complexity-theory><circuit-complexity><polynomials><algebraic-complexity>
Explicit polynomials in 1 variable with superlogarithmic circuit complexity lower bounds?
matt hastings
# Explicit polynomials in 1 variable with superlogarithmic circuit complexity lower bounds?

(Asked by: username_0 on 2010-11-29)

By counting arguments, one can show that there exist polynomials of degree n in 1 variable (i.e., something of the form $a\_n x^n + a\_{n-1} x^{n-1} + \cdots + a\_0)$ which have circuit complexity n. Also, one can show that a polynomial like $x^n$ requires at least $\log\_2 n$ multiplications (you need that just to get a high enough degree). Are there any explicit examples of polynomials in 1 variable with a superlogarithmic lower bound on complexity? (results over any field would be interesting)

**Tags:** cc.complexity-theory, circuit-complexity, polynomials, algebraic-complexity
> **Comments:**
> **username_1**: Are the examples you have in mind with circuit complexity $n$ over a finite field? I don't see how a counting argument would work over an infinite field, and over the rationals I'm pretty sure Paterson-Stockmeyer's $\sqrt{n}$ bound is tight (see also my answer below).  
> **username_0**: The sqrt(n) bound you mention is just an upper bound on the number of multiplications (over any field), but if we count both additions and multiplications as operations, then we need n operations over an infinite field for almost every polynomial, just because there are n distinct coefficients in the polynomial and there's no way to evaluate all possible polynomials with less than n operations (I'm not sure if this should be called a counting argument or not).  
> **username_1**: I think you have to be a bit more precise in the statement "there's no way to evaluate all possible polynomials with less than n ops." One way to interpret that is: if we think of the polynomial $\sum a_i x^i$ as a polynomial not just in $x$, but also treat the $a_i$'s as variables (or, equivalently, suppose the $a_i$ are algebraically independent), then the result that this requires n additions is Pan's (1966) and is not just a counting argument (though it's not too difficult). Otherwise, I'm not quite sure what result you're referring to with that statement.  
> **username_0**: What I mean is: the circuit consists of addition and multiplication gates.  The inputs for a given gate can be outputs of previous gates, or x, or some constants.  The question is: for a given polynomial, can we find a circuit and choice of constants in that circuit to compute it?  But, we have an (n+1)-dimensional space of polynomials, but if we fix the structure of a circuit with less than n gates (by "structure", I mean which gates use outputs of which other gates) and consider all possible choices of constants this gives less than an n dimensional space of polynomials that can be computed.  
> **username_0**: Btw---the impression I get is that constructing explicit examples over R or C without further restrictions on the coefficients is mostly solved.  On the other hand, constructing explicit examples where all the coefficients a_i are integers and not growing too rapidly, it still open?  There is an example with all integer constants in the survey you mention, but they grow doubly exponentially.  
> **username_1**: Ah, I see now. Nice counting argument :). (It took me a second to realize why Pan's result needed anything stronger than your argument, but Pan actually shows you need n multiplications, which is a stronger statement.)  
> **username_1**: As to your second comment, for multivariate polynomials there are good lower bound on some explicit polynomials even with only 0-1 coefficients (e.g. elementary symmetric polynomials). I do not know whether there are explicit hard-to-compute single-variable polynomials with small integer coefficients.  

---

## 1 answers

### Answer by username_1 on 2010-11-30. Score: 11 | Accepted answer

[Paterson and Stockmeyer](http://doi.ieeecomputersociety.org/10.1109/SWAT.1971.5) show that for most $n$-tuples of rational numbers $(a\_1, \dotsc, a\_n)$, evaluating $\prod\_{i=1}^{n} (x - a\_i)$ requires $\Omega(\sqrt{n})$ arithmetic operations, and this is tight.

The following polynomials get within a logarithmic factor of the $\sqrt{n}$ bound, by results of Strassen, Schnorr, and Heintz & Sieveking: $\sum\_{i=1}^{n} 2^{2^{i}} x^{i}$, $\sum\_{i=1}^{n} e^{2 \pi i / 2^{i}} x^{i}$, $\sum\_{i=1}^{n} i^{r} x^{i}$ (for $r$ a rational that is not an integer), etc. For exact references and for more on this, see pp. 324-325 of [von zur Gathen's survey](http://www.annualreviews.org/doi/abs/10.1146/annurev.cs.03.060188.001533).

> **Comments:**
> **username_0**: Thanks.  So, it would seem that the open problem is that if you count additions also as operations, can one construct a polynomial which needs more than sqrt(n) operations, with the goal of constructing one which needs n operations.  Any results towards this? (I doubt it, because in the method that needs only sqrt(n) multiplications, the additions give some matrix multiplication and this probably reduces to lower bounds on complexity of a matrix-scalar multiplication)  

---

