0
$\begingroup$

Related to the thread Nonnegativity conditions for a polynomial in two variables? but on more than two variables.

Suppose a probability vector $p$ belongs to a compact polytope where for each entry $p_i^{upperBound}\leq p_i\leq p_i^{lowerBound}$. We want to find all non-negative polynomials $f(p)$ from a polynomial ideal.

The polynomial ideal is determined by two-terminal connectivity in graphs which can be understood such that each polynomial has monomials $i\backslash j=\{x^{cut_{ij}}\mid i\in V(G),j\not\in V(G)\}$ in positive monomials while $j\backslash i=\{x^ {cut_{ji}}\mid i\in V(G),j\not\in V(G)\}$ in negative monomials. The polynomials are multivariate, determined by the number of vertices.

For example, the polynomial ideals for a series graph and a parallel graph are

\begin{eqnarray*} \mathcal{P}{}_{st}(G_{series}) & = & \langle p_{1}-p_{2},p_{1}-p_{3},\ldots,p_{2}-p_{3},p_{3}-p_{4},\ldots,p_{n}-p_{1},\ldots,p_{n}-p_{n-1}\rangle\\ \mathcal{P}{}_{st}(G_{parallel}) & = & \langle0\rangle \end{eqnarray*}

and the compact polytope could be $P$ where each $0 \leq p_i\leq 1 \forall i=1\ldots |V(G)|$, affinely equivalent to product of 1-dimensional hypercubes, so no non-negative polynomial in $\mathcal P_{st}(G_{series})$. Suppose the lower bounds and the upper bounds for $p$ are arbitrary; the question here in Math.SE with examples.

What are sufficient and necessary conditions for the non-negative polynomial to exist in the polynomial ideal? And how can you find them, with something like here?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ If the polytope is affinely equivalent to a product of simplices (this of course includes cubes, and other stuff, but restricts to simple polytopes---or do I mean simplicial (I forget which is which)), then the ideal theorem converts to the positivity result quoted (for which by the way, a simpler proof can be given, without using Gröbner bases). This refers to positivity wrt the multiplicative cone generated by the outward normals; in the product of simplices case, this converts to positivity of coefficients in products of polynomials. $\endgroup$
    – David Handelman
    Commented Jul 26, 2016 at 2:06
  • 1
    $\begingroup$ If the polytope is not so equivalent, then the positivity condition is much more difficult; the paper, In praise of order units Journal of Algebra and Its Applications 11 (06), 1250120, discusses this. $\endgroup$
    – David Handelman
    Commented Jul 26, 2016 at 2:10
  • $\begingroup$ @DavidHandelman you mean that if $p_{lowerBound}\leq p_i\leq p_{upperBound}$ for each $i$, we can find non-negative polynomials $f(p)$ without using Gröbner bases -- the polytope $P$ is affinely equivalent to some product of simplicial complexes. Then again if $P$ is not affinely equivalent to some product of simplicial complexes, the problem of finding non-negative polynomials is harder and done with Gröbner basis? How can you know whether $P$ does not correspond to some product of simplicial complexes? And how is the positivity results used for the non-negativity? $\endgroup$
    – hhh
    Commented Jul 26, 2016 at 14:38
  • $\begingroup$ @DavidHandelman I asked here without graph theory focus to find out non-negative polynomials $f(p),p\in P$ where $P$ is a compact polytope for clarification with enumerate list, hopefully easier to answer. $\endgroup$
    – hhh
    Commented Jul 26, 2016 at 14:58

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .