<p><em>Note:</em> This is an expansion of a previous comment, since the OP explicitely asked for weaker upper bounds.</p>

<p>The total degree of polynomial $f$ is bounded by $2^{L(f)}$ since each operation can at most double the degree of the polynomial. Thus, for each $m\in M$, $\deg(m)\le 2^{L(f)}$. </p>

<p>Now, for some variable $x$ and degree $d$, there is a SLP conputing $x^d$ by <a href="https://en.wikipedia.org/wiki/Exponentiation_by_squaring">binary exponentiation</a> if size at most $2\log(d)$. For a monomial $m=x_1^{d_1}\dotsb x_n^{d_n}$, one can separately compute each $x_i^{d_i}$ and then take their product. Thus $L(m)\le 2n\log(d) + (n-1)$ where $d$ is the total degree of $m$ (which is of course an upper bound on each $d_i$).</p>

<p>Together, one obtains for $m\in M$:
$$L(m)\le 2n\log(\deg(m))+(n-1)\le 2nL(f)+(n-1).$$</p>

<p>Since $n\le L(f)+1$, one can conclude
$$\forall m\in M, L(m) \le 2L(f)^2+3L(f).$$</p>

<p><strong>Remarks.</strong> The bound as stated is very rough. In particular, the upper bound on $L(m)$ given is the second paragraph is not tight. Yet, domotorp's answer shows that one cannot hope for a much better bound, and more precisely that the quadratic dependence on $L(f)$ cannot be removed. To tighten the construction, one could use the best known constructions on <a href="https://en.wikipedia.org/wiki/Addition_chain">addition chains</a>. Note that the precise bounds are still not known for this problem.</p>

CC BY-SA 3.0
2014-11-21T10:08:50.817Z
2014-11-21T10:08:50.817Z
Bruno
<p>If $$f=(\Sigma_{i=1}^n x_i)^{2^n}$$
then it has ${2^n+n-1\choose n-1} \approx 2^{n^2}$ monomials and $L(f)=O(n)$.
By a counting argument, there are $2^{O(n\log n)}$ straight-line programs of length $O(n)$.
As $f$ has more monomials, for some we need a longer program.
In fact this argument gives a monomial $m$ for which $L(m)=\widetilde\Omega(L^2(f))$.</p>

CC BY-SA 3.0
2014-11-20T07:27:50.340Z
As a small constructive example based on domotorp's answer, one can take $f=(x+y)^8$ with $L(f)=4$ while $L(x^7y)=L(x^7)+1=5$.
Bruno
CC BY-SA 3.0
2014-11-20T11:26:27.300Z
@domotorp, Thanks for the nice answer. Does this seem to be the upper bound also? Or there can be better lower bounds?
Gorav Jindal
CC BY-SA 3.0
2014-11-20T17:12:54.347Z
I don't know, but since this example was so simple, I would guess that the gap can be larger, possibly even exponential.
domotorp
CC BY-SA 3.0
2014-11-20T22:54:43.290Z
I have a "proof" that there is a linear upper bound... Where am I wrong (since you proved a quadratic lower bound)? It is as follows: With a SLP of size $L$, you compute a polynomial of total degree $\le 2^L$. Now $x^D$ has a SLP of size at most $2\log D$ with binary exponentiation. A degree-$D$ $n$-variate monomial has then a SLP of size at most $2n\log D+n-1$ (very rough bound): compute all the $x_i^{D_i}$, $D_i\le D$, and then their product. Thus if we consider a polynomial $f$, its total degree is at most $2^{L(f)}$, and each monomial has a SLP of size at most $2nL(f)+n-1$.
Bruno
CC BY-SA 3.0
2014-11-20T23:04:55.110Z
@Bruno: Nice proof and there's nothing wrong with it, but it's not linear, as you multiply $n$ and $L(f)$. But since we know that $f$ can depend on at most $L(f)+1$ variables, we can assume $n\le L(f)+1$, which implies the required quadratic bound. Thus $L(m)=O(L^2(f))$.
domotorp
CC BY-SA 3.0
2014-11-21T08:49:41.750Z
@domotorp: You're right!
Bruno
CC BY-SA 3.0
2014-11-19T20:17:01.330Z
2014-11-19T20:17:01.330Z
domotorp
<p>Let $k$ be some field. As usual, for an $f\in k[x_{1},x_{2},\ldots,x_{n}]$
we define $L(f)$ to be the straight-line complexity of $f$ over
$k$. Let $F$ be the set of monomials of $f$, namely the monomials
which appear in $f$ with non-zero coefficient. </p>

<blockquote>
  <p>Is it true that $ \forall m\in F:L(m)\le L(f)$?</p>
</blockquote>

<p>Even some weaker upper bound for $L(m)$ is known?</p>

<cc.complexity-theory><algebraic-complexity><arithmetic-circuits>
Straight line complexity of monomials
Gorav Jindal
# Straight line complexity of monomials

(Asked by: username_0 on 2014-11-19)

Let $k$ be some field. As usual, for an $f\in k[x\_{1},x\_{2},\ldots,x\_{n}]$
we define $L(f)$ to be the straight-line complexity of $f$ over
$k$. Let $F$ be the set of monomials of $f$, namely the monomials
which appear in $f$ with non-zero coefficient.

> Is it true that $ \forall m\in F:L(m)\le L(f)$?

Even some weaker upper bound for $L(m)$ is known?

**Tags:** cc.complexity-theory, algebraic-complexity, arithmetic-circuits

---

## 2 answers

### Answer by username_2 on 2014-11-19. Score: 13 | Accepted answer

If $$f=(\Sigma\_{i=1}^n x\_i)^{2^n}$$
then it has ${2^n+n-1\choose n-1} \approx 2^{n^2}$ monomials and $L(f)=O(n)$.
By a counting argument, there are $2^{O(n\log n)}$ straight-line programs of length $O(n)$.
As $f$ has more monomials, for some we need a longer program.
In fact this argument gives a monomial $m$ for which $L(m)=\widetilde\Omega(L^2(f))$.

> **Comments:**
> **username_1**: As a small constructive example based on domotorp's answer, one can take $f=(x+y)^8$ with $L(f)=4$ while $L(x^7y)=L(x^7)+1=5$.  
> **username_0**: @domotorp, Thanks for the nice answer. Does this seem to be the upper bound also? Or there can be better lower bounds?  
> **username_2**: I don't know, but since this example was so simple, I would guess that the gap can be larger, possibly even exponential.  
> **username_1**: I have a "proof" that there is a linear upper bound... Where am I wrong (since you proved a quadratic lower bound)? It is as follows: With a SLP of size $L$, you compute a polynomial of total degree $\le 2^L$. Now $x^D$ has a SLP of size at most $2\log D$ with binary exponentiation. A degree-$D$ $n$-variate monomial has then a SLP of size at most $2n\log D+n-1$ (very rough bound): compute all the $x_i^{D_i}$, $D_i\le D$, and then their product. Thus if we consider a polynomial $f$, its total degree is at most $2^{L(f)}$, and each monomial has a SLP of size at most $2nL(f)+n-1$.  
> **username_2**: @Bruno: Nice proof and there's nothing wrong with it, but it's not linear, as you multiply $n$ and $L(f)$. But since we know that $f$ can depend on at most $L(f)+1$ variables, we can assume $n\le L(f)+1$, which implies the required quadratic bound. Thus $L(m)=O(L^2(f))$.  
> **username_1**: @domotorp: You're right!  

---

### Answer by username_1 on 2014-11-21. Score: 8

*Note:* This is an expansion of a previous comment, since the OP explicitely asked for weaker upper bounds.

The total degree of polynomial $f$ is bounded by $2^{L(f)}$ since each operation can at most double the degree of the polynomial. Thus, for each $m\in M$, $\deg(m)\le 2^{L(f)}$.

Now, for some variable $x$ and degree $d$, there is a SLP conputing $x^d$ by [binary exponentiation](https://en.wikipedia.org/wiki/Exponentiation_by_squaring) if size at most $2\log(d)$. For a monomial $m=x\_1^{d\_1}\dotsb x\_n^{d\_n}$, one can separately compute each $x\_i^{d\_i}$ and then take their product. Thus $L(m)\le 2n\log(d) + (n-1)$ where $d$ is the total degree of $m$ (which is of course an upper bound on each $d\_i$).

Together, one obtains for $m\in M$:
$$L(m)\le 2n\log(\deg(m))+(n-1)\le 2nL(f)+(n-1).$$

Since $n\le L(f)+1$, one can conclude
$$\forall m\in M, L(m) \le 2L(f)^2+3L(f).$$

**Remarks.** The bound as stated is very rough. In particular, the upper bound on $L(m)$ given is the second paragraph is not tight. Yet, domotorp's answer shows that one cannot hope for a much better bound, and more precisely that the quadratic dependence on $L(f)$ cannot be removed. To tighten the construction, one could use the best known constructions on [addition chains](https://en.wikipedia.org/wiki/Addition_chain). Note that the precise bounds are still not known for this problem.


---

