11
$\begingroup$

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?

$\endgroup$

2 Answers 2

13
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.