One question that we investigate in this paper is, how can we build log-concave polynomials using sparse polynomials as building blocks? More precisely, let f = Σ_(i=0)~d a_i X~i ∈ R~+ [X] be a polynomial satisfying the log-concavity condition a_i~2 ＞ Ta_(i-1)a_(i+1) for every i ∈ {1, ..., d - 1}, where T ＞ 0. Whenever / can be written under the form f = Σ_(i=1)~k Π_(j=1)~m f_(i, j) where the polynomials f_(i, j) have at most t monomials, it is clear that d ≤ kt~m. Assuming that the f_(i, j) have only non-negative coefficients, we improve this degree bound to d = O(km~(2/3)t~(2m/3)log~(2/3)(kt)) if T ＞ 1, and to d ≤ kmt if T = d~(2d). This investigation has a complexity-theoretic motivation: we show that a suitable strengthening of the above results would imply a separation of the algebraic complexity classes VP and VNP. As they currently stand, these results are strong enough to provide a new example of a family of polynomials in VNP which cannot be computed by monotone arithmetic circuits of polynomial size.
展开▼
