User amir ali ahmadi - MathOverflow

Answer by Amir Ali Ahmadi for Criteria to determine whether a real-coefficient polynomial has real root?

2010-07-04T17:14:06Z

There is indeed an easy way to check if a univariate poly with real coefficients has a real root, without computing the roots.

Note that the answer for odd degree polynomials is always yes. For an even degree polynomial $p(x)$ do the following:

1) Compute the Hermite form of the polynomial. This is a symmetric matrix defined e.g. here: (on page 4, near the bottom denoted by $H_1(p)$). The entries of this matrix can be filled using Newton identities.

2) The number of real roots of $p(x)$ is equal to the signature of the Hermite matrix $H_1(p)$, i.e., the number of positive eigenvalues minus the number of negative eigenvalues.

3) Since the Hermite form is symmetric, its characteristic poly has only real roots. Therefore, we can apply Descartes' rule of signs to its char. polynomial, which would give us exactly the number of positive and negative eigenvalues of the Hermite form.

This process gives you the exact number of real roots of $p(x)$ without computing the roots, and in particular you can see if the polynomial has a real root.

Hope this helps.

-Amirali Ahmadi

Answer by Amir Ali Ahmadi for When does 'positive' imply 'sum of squares'?

2011-05-09T18:01:13Z

One other case that seems to be missing from the comments above (but most likely not from the references in there) is the 1888 result of Hilbert that all nonnegative ternary quartic forms (and bivariate quartic polynomials) are sums of squares of polynomials.

Of the same flavor of the type of questions you have raised, it is an open problem to determine if a polynomial with rational coefficients that is a sum of squares of polynomials (with possibly real coefficients) can also be written as a sum of squares of polynomials with rational coefficients. See e.g. Section 3 of http://www.msri.org/people/members/chillar/files/rationallmisos.pdf

Answer by Amir Ali Ahmadi for Convex polynomial homogenization and convexity

2011-05-09T17:30:11Z

It is definitely not true that the homogenization of a convex polynomial is convex. In fact, any convex polynomial that is not nonnegative will no longer be convex after homogenization. (This is because homogenization preserves lack of nonnegativity and convex homogeneous polynomials are always nonnegative.)

But even if the polynomial is nonnegative, the statement is still not true. Take e.g. the univariate polynomial $10x_1^4-5x_1+2$, which is convex and nonnegative, but its homogenization $10x_1^4-5x_1x_2^3+2x_2^4$ is not convex.

(Of course, for your specific polynomial the statement can be true, but I'm answering the general question that you raised.)

What is true generally is that the homogenization of a polynomial of degree d is convex if and only if the d-th root of the polynomial is convex. See Proposition 4.4 on p. 13 of the following nice paper of Reznick for the precise statement and a proof: http://www.math.uiuc.edu/~reznick/blenders2.pdf