Straight line complexity of monomials

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?

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))$.

• 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 Nov 20 '14 at 7:27
• @domotorp, Thanks for the nice answer. Does this seem to be the upper bound also? Or there can be better lower bounds? – Gorav Jindal Nov 20 '14 at 11:26
• I don't know, but since this example was so simple, I would guess that the gap can be larger, possibly even exponential. – domotorp Nov 20 '14 at 17:12
• 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 Nov 20 '14 at 22:54
• @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 Nov 20 '14 at 23:04

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 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. Note that the precise bounds are still not known for this problem.