Revisions - MathOverflow

Return to Answer

added 3200 characters in body; added 188 characters in body

view source

edited May 31 2011 at 14:12

Now, forget about the lexiographic ordering I introduced (the one that had $x > y > z > x' > y' > z'$), and introduce a new one, with $y > y' > \text{all other variables}$. With the respect to this new ordering, the left hand side of (6) has leading monomial $yy'$. Thus, the right hand side also must have leading monomial $yy'$. Therefore, none of the homogeneous linear polynomials whose squares appear on the right hand side of (6) can contain the variable $y$ (because the square of any such polynomial would contain $y^2$, and thus the leading monomial of the right hand side (6) would be $y^2$ (here we are using again the fact that the degree of the sum of some positively led polynomials is always equal to the highest of their degrees)). But this means that none of the squares on the right hand side (6) can contain the monomial $yy'$ (because such a monomial could only come from a $y$ inside the square, but we have ruled out this possibility). Therefore, the coefficient of $yy'$ on the right hand side of (6) is $\sum_{j\in J}2a_jb_j\cdot 2A_jB_j$. This is divisible by $4$. The coefficient of $yy'$ on the left hand side of (6) is not divisible by $4$. Contradiction.

Anyway it still keeps the question open whether we are in more luck if we require $R$ to be a $\mathbb Q$-algebra.

EDIT: I think that even if $R$ is supposed to be a $\mathbb Q$-algebra, then your answer is No. Let me try to prove it:

Replace $\mathbb Z$ by $\mathbb Q$, and "integers" by "rationals" throughout the above. We can still get to (6), but we don't get the contradiction through divisibility by $4$ anymore.

Consider (6) again. I have showed that none of the homogeneous linear polynomials whose squares appear on the right hand side of (6) can contain the variable $y$. But the same argument works for any other variable instead of $y$ (just consider the lexicographic order where this variable is higher than all others). This shows that none of the homogeneous linear polynomials whose squares appear on the right hand side of (6) can contain any variables. In other words, these squares are $0$. This simplifies (6) to

(7) $xx'+2yy'+zz' = \sum_{i\in I} \left(a_i^2x+2a_ib_iy+b_i^2z\right)\left(A_i^2x+2A_iB_iy+B_i^2z\right)$

$ + \sum_{j\in J} \left(a_j^2x+2a_jb_jy+b_j^2z\right)\left(A_j^2x'+2A_jB_jy'+B_j^2z'\right)$

$ + \sum_{k\in K} \left(a_k^2x'+2a_kb_ky'+b_k^2z'\right)\left(A_k^2x'+2A_kB_ky'+B_k^2z'\right)$.

Unless the sum $\sum_{i\in I} \left(a_i^2x+2a_ib_iy+b_i^2z\right)\left(A_i^2x+2A_iB_iy+B_i^2z\right)$ on the right hand side of (7) is identically zero, it contributes at least one of the monomials $x^2,xy,xz,y^2,yz,yx,z^2,zx,zy$ with nonzero coefficient to the right hand side of (7), and no other term on the right hand side of (7) can kill this monomial. But this is impossible, as none of these monomials appears on the left hand side of (7) ! Thus, the sum $\sum_{i\in I} \left(a_i^2x+2a_ib_iy+b_i^2z\right)\left(A_i^2x+2A_iB_iy+B_i^2z\right)$ must be identically zero. Similarly, the same holds for the sum $\sum_{k\in K} \left(a_k^2x'+2a_kb_ky'+b_k^2z'\right)\left(A_k^2x'+2A_kB_ky'+B_k^2z'\right)$. Now (7) simplifies to

(8) $xx'+2yy'+zz' = \sum_{j\in J} \left(a_j^2x+2a_jb_jy+b_j^2z\right)\left(A_j^2x'+2A_jB_jy'+B_j^2z'\right)$.

Now, the coefficient of $xz'$ on the right hand side of (8) is $\sum_{j\in J}a_j^2B_j^2$. But the coefficient of $xz'$ on the left hand side of (8) is zero. Thus, $\sum_{j\in J}a_j^2B_j^2=0$. This means that every $j\in J$ satisfies either $a_j=0$ or $B_j=0$. Similarly, every $j\in J$ satisfies either $b_j=0$ or $A_j=0$. Therefore, every $j\in J$ must belong to one of the following pigeonholes:

Pigeonhole 1: $j$'s satisfying $a_j=0\text{ and }b_j=0$.

Pigeonhole 2: $j$'s satisfying $B_j=0\text{ and }b_j=0$.

Pigeonhole 3: $j$'s satisfying $a_j=0\text{ and }A_j=0$.

Pigeonhole 4: $j$'s satisfying $B_j=0\text{ and }A_j=0$.

Any $j$ lying in Pigeonhole 1 can be removed from $J$ without invalidating (8) (because if $j$ lies in Pigeonhole 1, then the addend corresponding to $j$ on the right hand side of (8) is zero and contributes nothing to the sum). Similarly, any $j$ lying in Pigeonhole 4 can be removed from $J$ without invalidating (8). Thus, what remains of (8) is

$xx'+2yy'+zz' = \sum_{j\in \text{Pigeonhole 2}} \left(a_j^2x+2a_jb_jy+b_j^2z\right)\left(A_j^2x'+2A_jB_jy'+B_j^2z'\right)$

$+ \sum_{j\in \text{Pigeonhole 3}} \left(a_j^2x+2a_jb_jy+b_j^2z\right)\left(A_j^2x'+2A_jB_jy'+B_j^2z'\right)$

$= \sum_{j\in \text{Pigeonhole 2}} \left(a_j^2x\right)\left(A_j^2x'\right) + \sum_{j\in \text{Pigeonhole 3}} \left(b_j^2z\right)\left(B_j^2z'\right)$.

This is absurd.

added 6 characters in body; added 1 characters in body

view source

edited May 31 2011 at 13:50

darij grinberg
12.8k●1●24●75

I tend to believe that the answer to your question, in the generality you want, is negative. Since I am not sure of the proof (and have not written it up in detail), I am making this answer community wiki. Feel free to edit.

We will consider the case $n=2$, and let $R$ be the polynomial ring $\mathbb Z\left[x,y,z,x',y',z'\right]$. Define the nonnegative cone on $R$ to consist of all polynomials which can be written as sums of products of squares and polynomials of the form $a^2x+2aby+b^2z$ with $a,b\in R$ or of the form $a^2x'+2aby'+b^2z'$ with $a,b\in R$.

Let $A$ be the matrix $\left(\begin{array}{cc}x&y\\ y& z\end{array}\right)$ , and let $B$ be the matrix $\left(\begin{array}{cc}x'& y'\\ y'& z'\end{array}\right)$ . Then, $A$ and $B$ are nonnegative definite (meaning that your condition is satisfied), but I claim that $\mathrm{Tr}\left(AB\right)$ does not lie in the nonnegative cone. Why?

A polynomial in $\mathbb Z\left[x,y,z,x',y',z'\right]$ is said to be positively led if its leading monomial with respect to the lexicographic ordering ($x > y > z > x' > y' > z'$) is a positive integer. The positively led polynomials form a cone, which contains our nonnegative cone because:

(1) the sum and the product of two positively led polynomials are positively led (this is trivial);

(2) squares of polynomials are positively led (this is very easy);

(3) polynomials of the form $a^2x+2aby+b^2z$ with $a,b\in R$ or of the form $a^2x'+2aby'+b^2z'$ with $a,b\in R$ are positively led. (Proving this requires some work. For $a^2x+2aby+b^2z$, we wlog assume that $a$ and $b$ are monomials (because we can always restrict our concentration to the leading monomials of $a$ and $b$; all the other monomials don't contribute anything to the leading monomial of $a^2x+2aby+b^2z$), then show that the monomial $aby$ cannot be $\geq$ to each of the monomials $a^2x$ and $b^2z$ at the same time. Similarly for $a^2x'+2aby'+b^2z'$.)

Now, assume that $\mathrm{Tr}\left(AB\right)$ is nonnegative. Then, $\mathrm{Tr}\left(AB\right) = xx'+2yy'+zz'$ can be written as a sum of products of squares and polynomials of the form $a^2x+2aby+b^2z$ with $a,b\in R$ or of the form $a^2x'+2aby'+b^2z'$ with $a,b\in R$. Now, each of the addends in this sum must have degree $\leq 2$ (where "degree" means "total degree"). This is because the degree of the sum of some positively led polynomials is always equal to the highest of their degrees (and not just smaller or equal to it!), so if we had some terms of degree $\geq 3$, they could not cancel out, contradicting to $\deg\left(xx'+2yy'+zz'\right)=2$.

Now another minor lemma:

(4) If a polynomial of the form $a^2x+2aby+b^2z$ with $a,b\in R$ has degree $\leq 2$, then $a$ and $b$ must be integers (and the polynomial has degree $1$).

This is easy to see by the method we used to prove (3): We assume WLOG that $a$ and $b$ are just monomials (because otherwise, we just replace the polynomials $a$ and $b$ by their leading monomials; this does not change the degree of $a^2x+2aby+b^2z$). Now as in (3) we show that the monomial $aby$ cannot be $\geq$ to each of the monomials $a^2x$ and $b^2z$ at the same time. Hence, the leading monomial in $a^2x+2aby+b^2z$ must be either $a^2x$ or $b^2z$ or $a^2x+b^2z$. In each of these cases, we conclude that at least one of $a$ and $b$ must be an integer (i. e., a monomial of degree $0$), let's say that it's $a$. Now this yields that the leading monomial in $a^2x+2aby+b^2z$ must be $b^2z$, so that $b$ too is an integer. This proves (4).

Similarly:

(5) If a polynomial of the form $a^2x'+2aby'+b^2z'$ with $a,b\in R$ has degree $\leq 2$, then $a$ and $b$ must be integers (and the polynomial has degree $1$).

So let us conclude:

We know that $xx'+2yy'+zz'$ can be written as a sum of products of squares and polynomials of the form $a^2x+2aby+b^2z$ with $a,b\in R$ or of the form $a^2x'+2aby'+b^2z'$ with $a,b\in R$.

But we know that each of the addends has degree $\leq 2$. Thus each of these addends is either a square or the product of two polynomials of the form $a^2x+2aby+b^2z$ with $a,b\in \mathbb Z$ or of the form $a^2x'+2aby'+b^2z'$ with $a,b\in \mathbb Z$. (In fact, any other combination would make the degree too high; in particular, multiplying with a square increases the degree by $\geq 2$ unless the square is just an integer square, and multiplying by a polynomial of the form $a^2x+2aby+b^2z$ with $a,b\in R$ or of the form $a^2x'+2aby'+b^2z'$ with $a,b\in R$ increases the degree by $1$ if $a,b\in\mathbb Z$ or by $\geq 3$ otherwise (due to (4) and (5)).)

We can WLOG assume that all squares occuring in the sum are squares of homogeneous linear polynomials (because we can simply remove the constant terms; here we use that $xx'+2yy'+zz'$ is homogeneous of degree $2$). So we have

(6) $xx'+2yy'+zz' = \left(\text{sum of squares of some homogeneous linear polynomials}\right)$

$ + \sum_{i\in I} \left(a_i^2x+2a_ib_iy+b_i^2z\right)\left(A_i^2x+2A_iB_iy+B_i^2z\right)$

$ + \sum_{j\in J} \left(a_j^2x+2a_jb_jy+b_j^2z\right)\left(A_j^2x'+2A_jB_jy'+B_j^2z'\right)$

$ + \sum_{k\in K} \left(a_k^2x'+2a_kb_ky'+b_k^2z'\right)\left(A_k^2x'+2A_kB_ky'+B_k^2z'\right)$,

where $I$, $J$, $K$ are three disjoint finite sets, and $a_i$, $b_i$, $A_i$, $B_i$, $a_j$, $b_j$, ... are integers.

Now, forget about the lexiographic ordering I introduced (the one that had $x > y > z > x' > y' > z'$), and introduce a new one, with $y > y' > \text{all other variables}$. With the respect to this new ordering, the left hand side of (6) has leading monomial $yy'$. Thus, the right hand side also must have leading monomial $yy'$. Therefore, none of the homgeneous homogeneous linear polynomials whose squares appear on the right hand side of (6) can contain the variable $y$ (because the square of any such polynomial would contain $y^2$, and thus the leading monomial of the right hand side (6) would be $y^2$ (here we are using again the fact that the degree of the sum of some positively led polynomials is always equal to the highest of their degrees)). But this means that none of the squares on the right hand side (6) can contain the monomial $yy'$ (because such a monomial could only come from a $y$ inside the square, but we have ruled out this possibility). Therefore, the coefficient of $yy'$ on the right hand side of (6) is $\sum_{k\in K}2a_kb_k2A_kB_k$\sum_{j\in J}2a_jb_j\cdot 2A_jB_j$. This is divisible by $4$. The coefficient of $yy'$ on the left hand side of (6) is not divisible by $4$. Contradiction.

At least if I didn't mess anything up. Given the length of the proof, this is rather improbable.

Anyway it still keeps the question open whether we are in more luck if we require $R$ to be a $\mathbb Q$-algebra.

[made Community Wiki]

view source

answered May 31 2011 at 13:44

darij grinberg
12.8k●1●24●75

(1) the sum and the product of two positively led polynomials are positively led (this is trivial);

(2) squares of polynomials are positively led (this is very easy);

Now another minor lemma:

(4) If a polynomial of the form $a^2x+2aby+b^2z$ with $a,b\in R$ has degree $\leq 2$, then $a$ and $b$ must be integers (and the polynomial has degree $1$).

Similarly:

(5) If a polynomial of the form $a^2x'+2aby'+b^2z'$ with $a,b\in R$ has degree $\leq 2$, then $a$ and $b$ must be integers (and the polynomial has degree $1$).

So let us conclude:

We know that $xx'+2yy'+zz'$ can be written as a sum of products of squares and polynomials of the form $a^2x+2aby+b^2z$ with $a,b\in R$ or of the form $a^2x'+2aby'+b^2z'$ with $a,b\in R$.

(6) $xx'+2yy'+zz' = \left(\text{sum of squares of some homogeneous linear polynomials}\right)$

$ + \sum_{i\in I} \left(a_i^2x+2a_ib_iy+b_i^2z\right)\left(A_i^2x+2A_iB_iy+B_i^2z\right)$

$ + \sum_{j\in J} \left(a_j^2x+2a_jb_jy+b_j^2z\right)\left(A_j^2x'+2A_jB_jy'+B_j^2z'\right)$

$ + \sum_{k\in K} \left(a_k^2x'+2a_kb_ky'+b_k^2z'\right)\left(A_k^2x'+2A_kB_ky'+B_k^2z'\right)$,

where $I$, $J$, $K$ are three disjoint finite sets, and $a_i$, $b_i$, $A_i$, $B_i$, $a_j$, $b_j$, ... are integers.

Now, forget about the lexiographic ordering I introduced (the one that had $x > y > z > x' > y' > z'$), and introduce a new one, with $y > y' > \text{all other variables}$. With the respect to this new ordering, the left hand side of (6) has leading monomial $yy'$. Thus, the right hand side also must have leading monomial $yy'$. Therefore, none of the homgeneous linear polynomials whose squares appear on the right hand side of (6) can contain the variable $y$ (because the square of any such polynomial would contain $y^2$, and thus the leading monomial of the right hand side (6) would be $y^2$ (here we are using again the fact that the degree of the sum of some positively led polynomials is always equal to the highest of their degrees)). But this means that none of the squares on the right hand side (6) can contain the monomial $yy'$ (because such a monomial could only come from a $y$ inside the square, but we have ruled out this possibility). Therefore, the coefficient of $yy'$ on the right hand side of (6) is $\sum_{k\in K}2a_kb_k2A_kB_k$. This is divisible by $4$. The coefficient of $yy'$ on the left hand side of (6) is not divisible by $4$. Contradiction.

At least if I didn't mess anything up. Given the length of the proof, this is rather improbable.

Anyway it still keeps the question open whether we are in more luck if we require $R$ to be a $\mathbb Q$-algebra.