# Application of polynomials with non-negative coefficients

Question 1: Are there any deeper applications (in any field of mathematics) of polynomials (with possibly more than one variable) over the real numbers whose coefficients are non-negative? So far I have found only some vague mentions of control theory and maybe some approximations of functions, but don't know the details (e.g. www.math.ttu.edu/~barnard/poly.pdf).

Question 2: There is a similar notion, namely "positive polynomials", but they are defined as "polynomial functions that are non-negative". Does anybody know some connection between these two kinds of polynomials? Thanks.

All comments and suggested answers here (thanks for them:)) have certainly something to do with the mentioned type of polynomials. To specify more what was my intention - a desired answer (to Question 1) should fullfil the following: "Is the application in you proposed area of such a kind that it forces an (independent) research of polynomials with non-negative coefficients on themselves?"

-
Proof of Cauchy Kovaleskaya in PDE theory as done in Evans' book. – Helge Nov 9 '12 at 4:26

One answer to question 2 is Polya's theorem on forms positive on an orthant: Let a form (i.e. homogeneous polynomial) in several variables be given which is (strictly) positive whenever evaluated on non zero tuples of nonnegative reals. Then you can multiply it with a high power of the sum of the variables such that you obtain a form with all coefficients nonnegative (actually all coefficients of the "right" degree are positive).

You can also prove a lower bound on the exponent required, see: Powers, Reznick: A new bound for Polya’s Theorem with applications to polynomials positive on polyhedra

This theorem can be used in representation theorems involving sums of squares (cf. Patricia's answer), see my article: An algorithmic approach to Schmüdgen’s Positivstellensatz

-

If you know that the coefficients are non-negative and also integral, then the polynomial can be completely determined by the values of $p(1)$ and $p(p(1))$. There might be a way to extend this to rational coefficients, but I'm not sure.

-
Why is this statement true? – Igor Rivin Mar 22 '12 at 1:57
@Igor: $q=p(1)$ gives the sum of the coefficients. Now think of $p(p(1))=p(q)$ written in base $q$; one sees that the "digits" are exactly the coefficients of $p$. The only possible ambiguity comes if $p(q)=q^n$ for some $n$, but since the coefficients sum to $q$, one sees that $p=qx^{n−1}$ in this case. – ARupinski Mar 22 '12 at 2:33
The previous proof works if $p(1)\neq 1$ (i.e. $p(x)=x^n$). But one can just take $p(2)$ and $p(p(2))$ for instance. – Miroslav Korbelar Mar 22 '12 at 14:49
@Miroslav One could also take the maximum of the coefficient, say $m$ and evaluate $p(m+1)$ in base $m+1$. – user11000 Mar 29 '12 at 6:56
@Marvis: you have to know $m$ in advance for that trick to work. If you know nothing about the polynomial, I think that the best you can do is asking for $q=p(1)$, and then for either $p(p(1))$ if $q\neq 1$ or $p(2)$ instead. This way you can always reconstruct the polynomial by asking for two evaluations. – Federico Poloni Nov 9 '12 at 8:49

Regarding question 1: An example from combinatorics (or conceivably topology, depending on how one classifies these things): if a finite simplicial complex is Cohen-Macaulay (defined below), then its $h$-polynomial (also defined below) has nonnegative coefficients. So this is one example of a situation where you can detect that an object of some sort lacks some nice property by observing that an associated polynomial does not have nonnegative coefficients.

Terminology review, as promised above: given a finite $(d-1)$-dimensional simplicial complex $\Delta$, let $f_i(\Delta )$ be the number of $i$-dimensional faces in $\Delta$, making the convention that the empty set is a $(-1)$-dimensional face. The vector $(f_{-1}(\Delta ),f_0(\Delta ),\dots )$ is called the $f$-vector of $\Delta$. One may encode the same data with another vector called the $h$-vector of $\Delta$ given by $h_k(\Delta ) = \sum_{i=0}^k (-1)^{k-i}{d-i\choose k-i}f_{i-1}(\Delta )$ for each $0\le k\le d$, so for instance $h_d(\Delta )$ is the reduced Euler characteristic of $\Delta$. The $h$-polynomial of $\Delta$ is the polynomial $h(x) = h_0 x^d + h_1 x^{d-1} + \cdots + h_d$, while the $f$-polynomial of $\Delta$ is $f(x) = f_{-1}x^d + f_0x^{d-1} + \cdots + f_{d-1}$. Now an equivalent way (to above) of describing the relationship between $h$-vectors and $f$-vectors is via $\sum_{i=0}^d f_{i-1}(t-1)^{d-i} = \sum_{i=0}^d h_it^{d-i}$, or in other words as $h(x)=f(x-1)$. Now a finite $d$-dimensional simplicial complex $\Delta$ is said to be Cohen-Macaulay over the integers if all its reduced homology groups satisfy $\tilde{H_i}(\Delta ,\mathbf{Z})=0$ for $i < d$ and likewise the link $lk_{\Delta }(\sigma )$ of any face $\sigma \in \Delta$ has reduced homology groups satisfying $\tilde{H_i}(lk_{\Delta }(\sigma )) = 0$ for $i < dim (lk_{\Delta }(\sigma ))$. Cohen-Macaulay complexes have the property that their $h$-vector is nonnegative, hence $h$-polynomial has nonnegative coefficients. A good reference for this and related topological combinatorics is the book "Combinatorics and commutative algebra" by Richard Stanley.

Regarding question 2: An important way of constructing positive polynomials is as sums of squares. Many examples of positive polynomials with nonnegative coefficients may be constructed this way -- if the smaller polynomials being squared have nonnegative coefficients too. However, not all positive polynomials are sums of squares by any means, let alone these special ones. A good reference on this is the paper:

G. Blekherman, Nonnegative polynomials and sums of squares, Jour. Amer. Math. Soc. 25 (2012), 617-635

which proves that there are many more nonnegative polynomials than sums of squares asymptotically by showing that the volumes of cross sections of the cone of nonnegative polynomials grow much faster as total degree is increased than the corresponding cross sections of the cone of sums of squares.

-
People who haven't seen $h$-vectors before might find the definition somewhat unnatural. Since you're interested in the polynomials, not just the vectors, it might be worth mentioning the nice relationship between the $h$- and $f$-polynomials, shifting the argument by 1. – Andreas Blass Nov 9 '12 at 0:43
@Andreas: That's a good idea! I will add that some time soon. – Patricia Hersh Nov 9 '12 at 1:12
@Patricia: Sums of squares don't necessarily have all coefficients nonnegative. – Markus Schweighofer Nov 9 '12 at 7:13
@Markus: I got mixed up and was using the wrong (too restrictive) definition. Thanks for catching that. – Patricia Hersh Nov 9 '12 at 7:59

How about Rook polynomials? http://en.wikipedia.org/wiki/Rook_polynomial Or if you like examples in several variables, Schur polynomials, http://en.wikipedia.org/wiki/Schur_polynomial

Or a plentiful of other polynomials with combinatorial connections. The Schur polynomials have for example applications in representation theory.

-
In fact I had some more systematic usage in mind, not only the fact that some polynomials are just of this kind. Or does one really use this property in the examples you mentioned? – Miroslav Korbelar Mar 22 '12 at 9:18
Well, each coefficient counts something, so if it was negative (or non-integer), it would make no sense. – Per Alexandersson Mar 22 '12 at 11:58

Thanks to all for your comments and suggestions. The original motivation for this question was a connection between polynomials with non-negative coefficients and commutative semirings. After some search we found some papers asking for determining the least degree of a polynomial with non-negative coefficients that is divisible by a given (general) polynomial. Suprisingly similar questions were investigated repeatedly and independetly but without any deeper motivation. We deceided hence to make an overview, improvements of some results and suggested a few conjectures. The result (made before the latest updates of this webpage) can be found here http://arxiv.org/abs/1210.6868. (Suggestions and comments are welcome.)

-