Extremal rays in families of inequalities (II)

-

(This is Yan Sheng.)

Last time we studied a family of inequalities involving absolute values on linear polynomials, and asked the question of how lazy we can be to prove inequalities of that form. This week, we will be applying the same approach to a different family: 3-variable homogeneous symmetric inequalities of low degree.

A polynomial $P(x,y,z)$ in 3 variables is called homogeneous of degree $d$ if each of its terms is of degree $d$, and symmetric if $P(x,y,z)=P(x',y',z')$ for all permutations $x',y',z'$ of $x,y,z$. Inequalities involving homogeneous symmetric polynomials include the AM-GM inequality$$\left(\frac{x+y+z}3\right)^3\ge xyz,$$and the Schur inequality$$x^r(x-y)(x-z)+y^r(y-x)(y-z)+z^r(z-x)(z-y)\ge0$$for integers $r\ge0$.

For the rest of this post, write $\mathcal P^+_d$ for the family of all homogeneous symmetric polynomials $P(x,y,z)$ of degree $d$ such that $P(x,y,z)\ge0$ holds for all $x,y,z\ge0$. Our Main Problem is to describe $\mathcal P^+_d$.

Exercise: Determine $\mathcal P^+_d$ for $d\le2$. (The most interesting inequality here is $x^2+y^2+z^2\ge xy+yz+zx$.)

Warmup: degree 3

From here on, we will use the symmetric sum notation$$[a,b,c]=\frac16(x^ay^bz^c+\cdots),$$where there are 6 terms in the sum, one for each permutation of $x,y,z$. For instance, we have$$\begin{align*}[3,0,0]&=\frac13(x^3+y^3+z^3),\\ [2,1,0]&=\frac16(x^2y+y^2z+z^2x+xy^2+yz^2+zx^2),\\ [1,1,1]&=xyz.\end{align*}$$By AM-GM (or Muirhead, iykyk), we have $[3,0,0]\ge[2,1,0]\ge[1,1,1]$.

Let's start by considering our Main Problem in degree 3. It should be clear that every homogeneous symmetric polynomial of degree 3 can be written as$$P(x,y,z)=K[3,0,0]+A[2,1,0]+B[1,1,1],$$for some constants $K,A,B\in\mathbb R$, so the Main Problem becomes: "for which triples $(K,A,B)$ do we have $P\ge0$ for all $x,y,z\ge0$?"

It seems sensible as a first step to plug in specific points $(x,y,z)$ to get some conditions that $K,A,B$ have to satisfy: $$\begin{matrix} (x,y,z)&3[3,0,0]&3[2,1,0]&3[1,1,1]\\\hline (1,0,0)&1&0&0\\ (1,1,0)&2&1&0\\ (1,1,1)&3&3&3 \end{matrix}$$ Hence if $P\ge0$ at these points, then we must have$$\begin{align*}K&\ge0,\\2K+A&\ge0,\\K+A+B&\ge0.\end{align*}$$Geometrically, this is a region in $\mathbb R^3$ cut out by 3 planes; the pairwise intersections of the planes give us 3 vectors in the directions of the edges, whose nonnegative linear combinations generate the whole region. Hence we have$$\begin{pmatrix}K\\A\\B\end{pmatrix}=c_1\begin{pmatrix}1\\-2\\1\end{pmatrix}+c_2\begin{pmatrix}0\\1\\-1\end{pmatrix}+c_3\begin{pmatrix}0\\0\\1\end{pmatrix}$$for some $c_1,c_2,c_3\ge0$.

But now note that$$\begin{align*}[3,0,0]-2[2,1,0]+[1,1,1]&\ge0,&&(\text{Schur})\\ [2,1,0]-[1,1,1]&\ge0,&&(\text{AM-GM})\\ [1,1,1]&\ge0,&&(\text{trivial})\end{align*}$$so every $(K,A,B)$ in this region does in fact yield a nonnegative $P$! Hence we have proved:

Theorem: Let $P(x,y,z)$ be a homogeneous symmetric polynomial of degree 3. Then the following are equivalent:

  1. $P(x,y,z)\ge0$ holds for all $x,y,z\ge0$ (i.e., $P\in\mathcal P^+_3$);
  2. $P(x,y,z)\ge0$ holds at $(x,y,z)=(1,0,0),(1,1,0),(1,1,1)$; and
  3. $P$ is a nonnegative linear combination of the three polynomials:
    • $[3,0,0]-2[2,1,0]+[1,1,1]$;
    • $[2,1,0]-[1,1,1]$; and
    • $[1,1,1]$. $\square$

The slogan here is "every 3-variable homogeneous symmetric inequality of degree 3 can be proved by checking 3 points/can be proved with AM-GM and Schur". I first noticed and posted about this fact in 2011, but it has been known since at least Stolarsky (1971) and van Albada (1971), in the context of triangle inequalities.

I'd say that this theorem a pretty satisfactory, complete solution of our Main Problem in degree 3. In fact we see that there are actually two different aspects of the Main Problem:

  1. The Decision Problem: Find a minimal set of points $X_d$ such that $P(x,y,z)\ge0$ for all $(x,y,z)\in X_d$ implies that $P(x,y,z)\ge0$ for all $x,y,z\ge0$.
  2. The Generation Problem: Find a minimal set $\mathcal S_d$ of homogeneous symmetric polynomials of degree $d$, whose nonnegative linear combinations form exactly $\mathcal P^+_d$.

By the discussion above and the preceding exercise, we may take for example$$\begin{align*}\mathcal S_1&=\{x+y+z\},\\\mathcal S_2&=\{x^2+y^2+z^2-xy-yz-zx,\\&\phantom{{}=\{}xy+yz+zx\},\\\mathcal S_3&=\{[3,0,0]-2[2,1,0]+[1,1,1],\\&\phantom{{}=\{}[2,1,0]-[1,1,1],\\&\phantom{{}=\{}[1,1,1]\},\end{align*}$$and$$\begin{align*}X_1&=\{\text{any nonzero point}\},\\X_2&=\{(1,0,0),(1,1,1)\},\\X_3&=\{(1,0,0),(1,1,0),(1,1,1)\}.\end{align*}$$

It turns out that the decision problem is easier, thanks to a powerful theory developed in the late-2000's.

The pqr/uvw method

Recall that every symmetric polynomial $P(x,y,z)$ can be written in terms of the elementary symmetric polynomials, given by $$\begin{align*}p&=x+y+z,\\q&=xy+yz+zx,\\r&=xyz.\end{align*}$$Some people like to write $p,q,r$ as $u,v^2,w^3$ instead, presumably to track degrees, but of course this is purely an aesthetic choice.

Much of the power of rewriting symmetric inequalities in terms of $p,q,r$ lies in the following result, which gives simple conditions on the range of one of these variables in terms of the other two:

"Tejs's Theorem": Suppose that $x,y,z\ge0$.

  1. ($r$-lemma) For fixed $p,q$, the value of $r$ attains its maximum only when two of $x,y,z$ are equal, and its minimum only when two of $x,y,z$ are equal or one of $x,y,z$ is 0.
  2. ($q$-lemma) For fixed $p,r$, the value of $q$ attains its maximum or minimum only when two of $x,y,z$ are equal.
  3. ($p$-lemma) For fixed $q,r$, the value of $p$ attains its maximum or minimum only when two of $x,y,z$ are equal.

Proof sketch: Consider the cubic polynomial $f(t)=t^3-pt^2+qt-r$, which has three nonnegative real roots. If we fix $p,q$, the question of "what is the maximum possible value of $r$?" is equivalent to "how far can we push the graph of $f$ down such that it still has 3 nonnegative real roots?"; the answer is clearly "until we reach the local maximum of $f$", at which point two of the roots become equal:

On the other hand, "what is the minimum possible value of $r$?" is equivalent to "how far can we push the graph of $f$ up such that it still has 3 nonnegative real roots?", and the answer is "until either (a) we reach the local minimum of $f$ (at which point two of the roots become equal), or (b) one of the roots becomes 0":

This proves the $r$-lemma.

For the $q$-lemma and the $p$-lemma, if $r=0$ then one of $x,y,z$ is 0, and it's easy to handle this case separately. Otherwise, we apply the same argument to $f(t)=\dfrac{t^3-pt^2+qt-r}t$ and $f(t)=\dfrac{t^3-pt^2+qt-r}{t^2}$, respectively: now we have $r>0$ implies $f(0)=-\infty$, so case (b) doesn't happen, and we are done. $\square$

Exercise: Make the above argument rigorous. Hint: if a cubic polynomial $f$ has 3 real roots, then its derivative has two real roots $\alpha\le\beta$ by Rolle's theorem; hence $f$ is increasing on $(-\infty,\alpha)$, decreasing on $(\alpha,\beta)$, and increasing on $(\beta,\infty)$. Now consider $f^{-1}$ on each of these intervals.

For sufficiently low degree, this restricts where homogeneous symmetric polynomials can attain their extrema:

Corollary: Let $P(x,y,z)$ be a homogeneous symmetric polynomial of degree $\le5$. Then $P(x,y,z)\ge0$ holds for all $x,y,z\ge0$ if and only if it holds at $(x,y,z)=(t,1,1)$ and $(t,1,0)$ for all $t\ge0$.

Proof: By the $r$-lemma, for fixed values of $p,q$ the extrema of $r$ is attained at points of the form $(x,y,y)$ or $(x,y,0)$. But by the degree condition, we see that $P$ written as a polynomial in $p,q,r$ must be linear in $r$, so the same is true for the extrema of $P$; hence to check that $P$ is nonnegative it suffices to check points of those two forms. By homogeneity we can divide these points by $y$, so it suffices to check points of the form $(t,1,1)$ or $(t,1,0)$, as desired. $\square$

This corollary solves the decision problem for homogeneous symmetric inequalities in 3 nonnegative real variables of degree up to 5: any such inequality can be proven by checking two inequalities in a single variable $t\ge0$, which is easy with calculus. (This is why you don't see such problems in olympiads any more.)

Aside: History of pqr/uvw

The uvw method has probably been independently rediscovered multiple times.

Convex cones in finite dimensions

We now turn to the generation problem, which asks for a minimal set of polynomials in $\mathcal P^+_d$ which generates all the other ones by nonnegative linear combinations. First, we recall some helpful results from convex analysis.

A closed set $C\subseteq\mathbb R^n$ is called a convex cone if any nonnegative linear combination of elements of $C$ is also in $C$; in other words, for all $v_i\in C$ and $a_i\ge0$ we have $\sum_ia_iv_i\in C$. Examples in $\mathbb R^3$ include the circular cone $\{x^2+y^2\le z^2\}$ and the first octant $\{x,y,z\ge0\}$.

Exercise: Verify that $\mathcal P^+_d$ is a convex cone inside some finite-dimensional real vector space.

Given a convex cone $C$, we're interested in its "outermost" points, namely those that are not nonnegative linear combinations of other points in $C$ (except trivially in terms of multiples of itself). For any nonzero $v\in\mathbb R^n$, we write $\langle v\rangle$ for the ray $\{\lambda v\,:\,\lambda\ge0\}$; a ray $\langle v\rangle\subseteq C$ is called an extremal ray if any line segment in $C$ which intersects $\langle v\rangle$ actually lies entirely inside $\langle v\rangle$. For example, every ray $\langle(\cos\theta,\sin\theta,1)\rangle$ contained in the boundary of the circular cone is an extremal ray; on the other hand, the first octant only has 3 extremal rays, namely the nonnegative $x$-, $y$- and $z$-axes.

It is almost a true statement that convex cones are the convex hulls of their extremal rays. (The key idea we used in the previous post was morally equivalent to this statement, for the cone of convex functions.)

Exercises:

  1. Verify that the circular cone and the first octant are each equal to the convex hull of their respective extremal rays.
  2. Determine the set of extremal rays of the following sets in $\mathbb R^3$: (a) the half-space $\{x\ge0\}$; (b) the quadrant $\{x,y\ge0\}$. Verify that neither set is the convex hull of their extremal rays.

Actually, we only need one more mild condition for the statement to be true. We only briefly sketch the idea of the proof here; the interested reader can find details in Rockafellar's Convex Analysis text.

Theorem (Rockafellar, Corollary 18.5.2): Let $C\ne\{0\}$ be a convex cone in $\mathbb R^n$ which contains no lines. Then $C$ is the convex hull of its extremal rays.

Proof sketch: If $\dim C\le1$ then $C$ is a ray, and the result is obvious, so assume that $\dim C\ge2$. Then $C$ contains no lines implies that $C$ is not all of a subspace of $\mathbb R^n$, so its relative boundary $D$ is nonempty. (Here "relative" means "relative to the minimal affine space containing $C$".) Similarly, $C$ is not a half-space of a subspace, which implies that $D$ is not convex. Thus there is some line $\ell$ which intersects $C$ in a compact interval, which implies that every line parallel to $\ell$ intersects $C$ in a compact (possibly empty) interval. Hence every point in the relative interior of $C$ is a convex combination of two points in $D$, and we finish by induction on dimension. $\square$

Exercise: Verify that $\mathcal P^+_d$ contains no lines.

Hence for the generation problem, it suffices to determine the extremal rays of the convex cone $\mathcal P^+_d$, and take $\mathcal S_d$ to consist of one nonzero polynomial taken from each extremal ray. Which polynomials lie on the extremal rays of this cone?

Characterising extremal rays of $\mathcal P^+_d$

Recall that $\langle P\rangle$ is an extremal ray of $\mathcal P^+_d$ if there are no nontrivial line segments in $\mathcal P^+_d$ which contain $P$ in its interior (the trivial line segments being the ones contained in $\langle P\rangle$). As such, we should really try to understand line segments in $\mathcal P^+_d$: given polynomials $P_0,P_1\in\mathcal P^+_d$ which are not multiples of each other, what can we say about the polynomials in the family $P_\lambda=(1-\lambda)P_0+\lambda P_1$ for $\lambda\in(0,1)$?

Well, the most natural thing to do is to fix a point $(x,y,z)$ and look at the values $P_\lambda(x,y,z)=(1-\lambda)a+\lambda b$, where $a=P_0(x,y,z)$, $b=P_1(x,y,z)$, with $a,b\ge0$. There's not much we can say about this value, except if $a=b=0$ then $P_\lambda(x,y,z)=0$ for all $\lambda$. In fact, the converse also holds: if $(1-\lambda)a+\lambda b=0$ for some $\lambda\in(0,1)$, then $a=b=0$. So all polynomials in the interior of a line segment have the same set of roots, which is the intersection of the set of roots of the polynomials at the two endpoints.

Thus if $\langle P\rangle$ is an extremal ray of $\mathcal P^+_d$, what that means is something like "the only polynomials in $\mathcal P^+_d$ with all the roots of $P$ are multiples of $P$", i.e., the set of roots of $P$ is maximal among nonzero polynomials in $\mathcal P^+_d$.

There is a technical issue with formalising the above intuitive argument: we need to keep track of the multiplicities of the roots, and for polynomials of more than one variable I'd have to say words I don't understand, like "divisors" and "projective". Fortunately, recall that for $d\le5$ we can restrict to polynomials of one variable to determine membership in $\mathcal P^+_d$, and those are much easier to deal with.

Lemma: Let $P_0,P_1:[a,b]\to\mathbb R$ be polynomials such that $P_0,P_1\ge0$ on $[a,b]$, and write $P_\lambda=(1-\lambda)P_0+\lambda P_1$. Let $Z(\cdot)$ denote the set of roots of a polynomial on $[a,b]$, counting multiplicity. Then:

  1. $Z(P_\lambda)=Z(P_0)\cap Z(P_1)$ for all $0<\lambda<1$; and
  2. If $Z(P_0)\subseteq Z(P_1)$, then there exists $\varepsilon>0$ such that $P_{-\varepsilon}\ge0$ on $[a,b]$.

Exercise: Prove the above lemma. Hint: all roots in $(a,b)$ must appear with even multiplicity; hence $R=\gcd(P_0,P_1)$ doesn't change sign in $[a,b]$. Now we may divide $P_0$ and $P_1$ by $R$, and assume that $Z(P_0)\cap Z(P_1)=\emptyset$; the rest is easy. $\square$

For $d\le5$, we know by pqr/uvw that any homogeneous symmetric $P$ of degree $d$ lies in $\mathcal P^+_d$ if and only if the two polynomials$$\begin{align*}f(t)&\coloneqq3P(t,1,1),\\g(t)&\coloneqq3P(t,1,0),\end{align*}$$are nonnegative on $[0,\infty)$. (The factor of 3 is just to get rid of some annoying constants later.) Now we can almost give a characterisation of the extremal rays of $\mathcal P^+_d$ in terms of the roots of $f$ and $g$ by using the previous lemma, but $[0,\infty)$ is not a compact interval. This isn't a big issue, since$$\begin{align*}f(t)=0&\iff P(1,t^{-1},t^{-1})=0,\\g(t)=0&\iff P(t^{-1},1,0)=0.\end{align*}$$So just for the sake of the next result, define$$\begin{align*}\mathcal L=\{(t,1,1)\,&:\,0\le t\le1\}\\{}\cup\{(1,t,t)\,&:\,0\le t\le1\}\\{}\cup\{(t,1,0)\,&:\,0\le t\le1\}.\end{align*}$$Then $P\in\mathcal P^+_d$ if and only if $P\ge0$ on $\mathcal L$. Let $Z_{\mathcal L}(P)$ be the set of roots of $P$ viewed as a 1-variable polynomial when restricted to each of the three line segments in $\mathcal L$, counted with multiplicity.

Proposition: Let $d\le5$. For any $P\in\mathcal P^+_d\setminus\{0\}$, we have that $\langle P\rangle$ is an extremal ray of $\mathcal P^+_d$ if and only if $Z_{\mathcal L}(P)$ is maximal among polynomials in $\mathcal P^+_d\setminus\{0\}$.

Proof: $(\Leftarrow)$ If $\langle P\rangle$ is not an extremal ray, then $P$ is contained in some line segment $[Q,R]\subseteq\mathcal P^+_d$ which is not contained in $\langle P\rangle$; in particular, $Q\ne0$. Now since $\mathcal P^+_d$ contains no lines, this line segment when extended must leave $\mathcal P^+_d$; without loss of generality we may assume that this happens at $Q$, i.e., there does not exist $\varepsilon>0$ such that $(1+\varepsilon)Q-\varepsilon R\in\mathcal P^+_d$.

By (1) of the previous lemma, we have $Z_{\mathcal L}(P)\subseteq Z_{\mathcal L}(Q)$; by (2) of the lemma, we have $Z_{\mathcal L}(P)\ne Z_{\mathcal L}(Q)$. Hence $Z_{\mathcal L}(P)$ is not maximal in $\mathcal P^+_d\setminus\{0\}$.

$(\Rightarrow)$ If $Z_{\mathcal L}(P)$ is not maximal in $\mathcal P^+_d\setminus\{0\}$, then there exists $Q\in\mathcal P^+_d\setminus\{0\}$ such that $Z_{\mathcal L}(P)\varsubsetneq Z_{\mathcal L}(Q)$; in particular, $Q$ is not a multiple of $P$. Now by (2) of the lemma, there exists $\varepsilon>0$ such that $R=(1+\varepsilon)P-\varepsilon Q\ge0$ on $[a,b]$. Hence $P$ lies on the line segment $[Q,R]$ which is not contained in $\langle P\rangle$, so $\langle P\rangle$ is not an extremal ray. $\square$

Finally, let's translate $Z_{\mathcal L}(P)$ back in terms of the roots of $f$ and $g$. For example, since $P(1,t,t)=t^dP(t^{-1},1,1)=t^df(t^{-1})$, we have:

  • For $0<\rho<1$, the multiplicity of $\rho$ as a root of $P(1,t,t)$ is equal to the multiplicity of $\rho^{-1}$ as a root of $f$;
  • For $\rho=0$, the multiplicity of 0 as a root of $P(1,t,t)$ is equal to $d-\deg f$. In other words, the "degree deficit" of $f$ can be viewed as "roots of $f$ at $\infty$".

Hence we will define $Z_f=Z_{f,P}$ to be the set of roots of $f$ counted with multiplicity, together with $\infty$ with multiplicity $d-\deg f$; define $Z_g$ similarly. Now we have the characterisation of the extremal rays of $\mathcal P^+_d$ in terms of $f$ and $g$ like we wanted:

Theorem: For $d\le5$ and $P\in\mathcal P^+_d\setminus\{0\}$, we have $\langle P\rangle$ is an extremal ray of $\mathcal P^+_d$ if and only if $(Z_{f,P},Z_{g,P})$ is inclusion-maximal among polynomials in $\mathcal P^+_d\setminus\{0\}$. $\square$

In other words, for any $Q\in\mathcal P^+_d\setminus\{0\}$, if $(Z_{f,P},Z_{g,P})\subseteq(Z_{f,Q},Z_{g,Q})$ then $(Z_{f,P},Z_{g,P})=(Z_{f,Q},Z_{g,Q})$. (Here we're abusing notation and writing $(A,B)\subseteq(C,D)$ to mean the pair of inclusions $A\subseteq C$ and $B\subseteq D$.)

Remark: It's possible a priori that $f\equiv0$ even if $P\not\equiv0$; in this case, we should consider every point in $[0,\infty]$ as a root of $f$ with infinite multiplicity, and we write $Z_f=🙏$ in this case; similarly for $g$.

Almost maximal subsets of roots

We can think of the above theorem as saying: if we restrict $\mathcal P^+_d$ by specifying some roots, until we're left with a 1-dimensional subset, then what we're left with is an extremal ray of $\mathcal P^+_d$, and the set of roots that we have specified is maximal.

What happens if the set of roots is almost maximal, and we're left with a 2-dimensional subset instead? Geometrically, any convex cone in 2 dimensions which contains no lines must be a sector in the plane, generated by nonnegative linear combinations of the two rays which bound it; so we should expect that these are precisely the two extremal rays of $\mathcal P^+_d$ in this subset.

As such, we will conclude this section with the following result, which will help us in our quest to do as little work as possible when we go back to actually solving the generation problem.

Theorem: For $d\le5$, let $S,T$ be multisets with elements in $[0,\infty]$, and let$$\Omega=\{P\in\mathcal P^+_d\,:\,(S,T)\subseteq(Z_{f,P},Z_{g,P})\}.$$

  1. If $\dim\Omega=1$, then $\Omega=\langle P\rangle$ is an extremal ray of $\mathcal P^+_d$.
  2. If $\dim\Omega=2$, and $P,Q\in\Omega$ are given such that neither of $(Z_{f,P},Z_{g,P})$ and $(Z_{f,Q},Z_{g,Q})$ contains the other, then $\langle P\rangle$ and $\langle Q\rangle$ are exactly the extremal rays of $\mathcal P^+_d$ which are contained in $\Omega$.

Proof: (1): Clear from the definition of extremal rays, and the fact that $\mathcal P^+_d$ contains no lines.

(2): Note that $P,Q$ are not multiples of each other, so every element of $\Omega$ is some linear combination $\lambda P+\mu Q$. By the given condition, there exists $(x,y,z)$ which is a root of $P$ but not of $Q$, so $(\lambda P+\mu Q)(x,y,z)\ge0$ implies that $\mu\ge0$. Similarly, we have $\lambda\ge0$. Hence$$\Omega=\{\lambda P+\mu Q\,:\,\lambda,\mu\ge0\}.$$Now any element of $\Omega$ not in either $\langle P\rangle$ or $\langle Q\rangle$ must have $\lambda,\mu>0$, so that$$(Z_{f,\lambda P+\mu Q},Z_{g,\lambda P+\mu Q})=(Z_{f,P},Z_{g,P})\cap(Z_{f,Q},Z_{g,Q}),$$which is strictly smaller than either $(Z_{f,P},Z_{g,P})$ or $(Z_{f,Q},Z_{g,Q})$. Hence both $P$ and $Q$ have maximal zero sets, so $\langle P\rangle$ and $\langle Q\rangle$ are both extremal rays of $\mathcal P^+_d$. $\square$

Determining extremal rays of $\mathcal P^+_d$

To summarise: $\mathcal P^+_d$ is generated by nonnegative linear combinations of its extremal rays, which are in turn the polynomials with maximal zero sets $(Z_f,Z_g)$. The game plan now is:

  1. Specify enough roots until the space of possible polynomials has dimension $\le2$;
  2. Construct examples in that space with maximal zero sets;
  3. Repeat until we exhaust all possibilities.

First, let's check that we get the same answer as before in the degree 3 case.

Degree 3

Recall that that every homogeneous symmetric polynomial of degree 3 can be written as$$P(x,y,z)=K[3,0,0]+A[2,1,0]+B[1,1,1].$$Now we compute $f(t)=3P(t,1,1)$ and $g(t)=3P(t,1,0)$:$$\begin{align*}f(t)&=K(t^3+2)+A(t^2+t+1)+B(3t),\\g(t)&=K(t^3+1)+A\frac{t^2+t}2.\end{align*}$$ Exercise:

  • Show that $f\equiv0\iff K=A=B=0$ (i.e., $P\equiv0$). (Hence $f$ completely determines $K,A,B$, and therefore $P$.)
  • Show that $g\equiv0\iff K=A=0$ (i.e., $\langle P\rangle=\langle[1,1,1]\rangle$).

To prove facts about $Z_f$ and $Z_g$, we should first think about characterising what cubic polynomials can appear as $f$ or $g$. Characterising $g$ is easier: we have$$g(t)=P(t,1,0)=t^dP(1,t^{-1},0)=t^dg(t^{-1}),$$so $g$ is a reciprocal polynomial.

To characterise $f$, first notice that $f$ can't be an arbitrary cubic: the space of cubics is 4-dimensional, while the space of possible $f$'s is 3-dimensional. Hence we should find a constraint that $f$ must satisfy; after staring for a bit (for example by plotting the graphs of $t^3+2$, $t^2+t+1$ and $3t$) we come up with the following.

Exercise: Show that $f'(1)=f(1)$. (We could verify this explicitly on $t^3+2$, $t^2+t+1$ and $3t$, or observe that this is a consequence of Euler's theorem on homogeneous functions.)

Hence we can collect some basic properties of $Z_f$ and $Z_g$:

Proposition:

  1. For $0<\rho<\infty$, we have that $\rho$ has even multiplicity in $Z_f$ and $Z_g$;
  2. $0\in Z_f\iff\{1,1\}\subseteq Z_g$;
  3. $\infty\in Z_f\iff\{0,\infty\}\subseteq Z_g$;
  4. For $0\le\rho\le\infty$, we have that $\rho$ and $\rho^{-1}$ have the same multiplicity in $Z_g$;
  5. If $f\not\equiv0$, then $\#Z_f\le d$; similarly for $g$.

Proof:

  1. This follows from the fact that $f$ and $g$ do not change sign at $\rho$.
  2. Both $0\in Z_f$ and $1\in Z_g$ are equivalent to $P(1,1,0)=0$; now 1 must appear with even multiplicity in $Z_g$, so $1\in Z_g\iff\{1,1\}\subseteq Z_g$.
  3. Both conditions are equivalent to $P(1,0,0)=0$.
  4. This follows from $g(t)=t^dg(t^{-1})$.
  5. Note that $f$ has $\le\deg f$ roots on $[0,\infty)$, and $d-\deg f$ roots at $\infty$; similarly for $g$. $\square$

Now there are many different ways of finding maximal zero sets with the above facts (I have typed out 4 different arguments while drafting this post), but let's stick to the game plan. Suppose that $\langle P\rangle$ is an extremal ray of $\mathcal P^+_3$, with corresponding zero sets $(Z_f,Z_g)$. We split into the following cases, calculating the dimension of the set $\Omega$ of remaining polynomials for each case.

  • Case 1: $\rho\in Z_g$, where $\rho\ne0,1,\infty$. Note that this implies $\{\rho,\rho,\rho^{-1},\rho^{-1}\}\subseteq Z_g$, which contradicts $\#Z_g\le d=3$ unless $g\equiv0$. Hence $\dim\Omega=1$, and $\Omega=\langle P\rangle=\langle[1,1,1]\rangle$ is an extremal ray.
  • Case 2: $0\in Z_g\iff\infty\in Z_g\iff\infty\in Z_f$. From the formula for $g$ we get $K=0$, so $\dim\Omega=2$.
  • Case 3: $1\in Z_g\iff0\in Z_f$. From the formula for $g$ we get $2K+A=0$, so $\dim\Omega=2$.
  • Case 4: $\rho\in Z_f$, where $\rho\ne0,1,\infty$. Now $P\not\equiv0$ implies that $f\not\equiv0$, so we may assume that $f$ is monic. Note that $\rho$ must appear with even multiplicity in $Z_f$, so $f$ has one of the following forms:$$\begin{align*}f(t)&=(t-\rho)^2(t-\sigma),\quad\text{or}\\f(t)&=(t-\rho)^2.\end{align*}$$In the second case, $f'(1)=f(1)$ implies $\rho=1$, contradiction. In the first case, we must have $\sigma\le0$ (since $f$ changes sign at $\sigma$), and now taking the logarithmic derivative at 1 gives$$\frac2{1-\rho}+\frac1{1-\sigma}=\frac{f'(1)}{f(1)}=1.$$Hence $\dfrac2{1-\rho}\in[0,1)$, so $\rho<-1$, contradiction. Hence $\dim\Omega=0$, i.e., $\Omega=\{0\}$.
  • Case 5: $1\in Z_f$. From the formula of $f$ we get $K+A+B=0$, so $\dim\Omega=2$.
  • Case 6: None of the above. Then $(Z_f,Z_g)=(\emptyset,\emptyset)$, which any of our constructions later will show is not maximal.

Now to find all extremal rays of $\mathcal P^+_3$, it suffices to construct two elements with neither zero set containing the other in each of Cases 2, 3 and 5! (Also notice that the significance of the points $(1,1,1)$, $(1,1,0)$ and $(1,0,0)$ naturally falls out of this case analysis.)

To finish, we list some members of $\mathcal P^+_3$ that we already know:

  • $S_3\coloneqq[3,0,0]-2[2,1,0]+[1,1,1]$, by Schur;
  • $[3,0,0]-[2,1,0]$, by AM-GM;
  • $[2,1,0]-[1,1,1]$, by AM-GM;
  • $[1,1,1]$ (trivial).

We compute $Z_f$ and $Z_g$ for each of these:$$\begin{matrix} P&f&g&Z_f&Z_g\\\hline S_3&t(t-1)^2&(t-1)^2(t+1)&\{0,1,1\}&\{1,1\}\\ [3,0,0]-[2,1,0]&(t-1)^2(t+1)&(t^2-\frac12t+1)(t+1)&\{1,1\}&\emptyset\\ [2,1,0]-[1,1,1]&(t-1)^2&\frac12t(t+1)&\{1,1,\infty\}&\{0,\infty\}\\ [1,1,1]&3t&0&\{0,\infty,\infty\}&🙏 \end{matrix}$$Clearly the second example doesn't have maximal zero set, so we can safely remove it from consideration (even if we hadn't noticed before that it's the sum of the first and third rows).

Now the relevant constructions for each case is:

  • Case 2: $[2,1,0]-[1,1,1]$ and $[1,1,1]$;
  • Case 3: $S_3$ and $[1,1,1]$;
  • Case 5: $S_3$ and $[2,1,0]-[1,1,1]$.

Thus our three examples are exactly the extremal rays in $\mathcal P^+_3$.

Degree 4

We're now ready to march bravely onward to tackle the problem in degree 4. The general homogeneous symmetric polynomial of degree 4 is$$P(x,y,z)=K[4,0,0]+A[3,1,0]+B[2,2,0]+C[2,1,1],$$where again we have $[4,0,0]\ge[3,1,0]\ge[2,2,0]\ge[2,1,1]$ by AM-GM. Now we evaluate $f$ and $g$:$$\begin{align*}f(t)&=K(t^4+2)+A(t^3+t+1)+B(2t^2+1)+C(t^2+2t),\\g(t)&=K(t^4+1)+A\frac{t^3+t}2+Bt^2.\end{align*}$$ Exercise:

  • Show that $f\equiv0\iff K=A=B=C=0$ (i.e., $P\equiv0$). (Hence $f$ completely determines $K,A,B,C$, and therefore $P$.)
  • Prove that $f'(1)=\frac43f(1)$.
  • Show that $g\equiv0\iff K=A=B=0$ (i.e., $\langle P\rangle=\langle[2,1,1]\rangle$).

As before, suppose that $\langle P\rangle$ is an extremal ray of $\mathcal P^+_4$, with corresponding zero sets $(Z_f,Z_g)$. We split into the following cases, where $\Omega$ in each case denotes the set of remaining polynomials. (This time, we start with the cases avoiding the special points $(1,1,1)$, $(1,1,0)$ and $(1,0,0)$.)

  • Case 1: $\rho\in Z_g$, where $\rho\ne0,1,\infty$. Note that this implies $\{\rho,\rho,\rho^{-1},\rho^{-1}\}\subseteq Z_g$, so $g(t)$ is a multiple of $(t-\rho)^2(t-\rho^{-1})^2$. Since the map from $P$ to $g$ has 1-dimensional kernel, and the space of possible $g$ is 1-dimensional, we have $\dim\Omega=1+1=2$.
  • Case 2: $\rho\in Z_f$, where $\rho\ne0,1,\infty$. We expect that the space of quartic polynomials satisfying the constraints $f'(1)=\frac43f(1)$ and $f(\rho)=f'(\rho)=0$ has dimension $5-3=2$; indeed, writing $f(t)=(t-\rho)^2\tilde f(t)$, we see that $\tilde f$ is a polynomial of degree $\le2$ satisfying$$\frac{f'(1)}{f(1)}=\frac2{1-\rho}+\frac{\tilde f'(1)}{\tilde f(1)},$$i.e., $\tilde f'(1)=\left(\frac43-\frac2{1-\rho}\right)\tilde f(1)$. Clearly the space of such $\tilde f$, and hence the space of $f$, has dimension 2; since the map from $P$ to $f$ is invertible, we also have $\dim\Omega=2$.

Now it turns out that the remaining conditions, namely

  • $0\in Z_g\iff\infty\in Z_g\iff\infty\in Z_f$;
  • $1\in Z_g\iff0\in Z_f$; and
  • $1\in Z_f$,

each yield only one nontrivial condition on $P$, so that $\dim\Omega=3$ in each case. To overcome this, we have to impose them together pairwise, or with higher multiplicity:

  • Case 3: $\{0,1\}\subseteq Z_f$. We have $f(t)=t(t-1)^2\tilde f(t)$ for some $\tilde f$ with degree $\le1$; hence $\dim\Omega=2$.
  • Case 4: $\{0,\infty\}\subseteq Z_f$. We have $f(t)=t\tilde f(t)$ for some $\tilde f$ with degree $\le2$, and$$\frac{f'(1)}{f(1)}=\frac11+\frac{\tilde f'(1)}{\tilde f(1)}$$implies $\tilde f'(1)=\frac13\tilde f(1)$; hence $\dim\Omega=2$.
  • Case 5: $\{1,\infty\}\subseteq Z_f$. We have $f(t)=(t-1)^2\tilde f(t)$ for some $\tilde f$ with degree $\le1$; hence $\dim\Omega=2$.
  • Case 6: $\{0,0\}\subseteq Z_f$. We have $f(t)=t^2\tilde f(t)$ for some $\tilde f$ with degree $\le2$, and$$\frac{f'(1)}{f(1)}=\frac21+\frac{\tilde f'(1)}{\tilde f(1)}$$implies $\tilde f'(1)=-\frac23\tilde f(1)$; hence $\dim\Omega=2$.
  • Case 7: $\{1,1,1,1\}\subseteq Z_f$. Then $f(t)$ is a multiple of $(t-1)^4$, so $\dim\Omega=1$.
  • Case 8: $\{\infty,\infty\}\subseteq Z_f$. Then $f$ has degree $\le2$ and satisfies $f'(1)=\frac43f(1)$, so $\dim\Omega=2$.
  • Case 9: None of the above. Then $(Z_f,Z_g)$ is one of $(\{0\},\{1\})$, $(\{1,1\},\emptyset)$, $(\{\infty\},\{0,\infty\})$, or $(\emptyset,\emptyset)$, each of which our constructions later will show is not maximal.

Okay, that's a lot of construction to do. We list down some members of $\mathcal P^+_4$ that we already know; just like in the degree 3 case, one of the AM-GM ones is redundant (and is omitted from this table): $$\begin{matrix} P&f&g&Z_f&Z_g\\\hline S_4&t^2(t-1)^2&(t-1)^2(t^2+t+1)&\{0,0,1,1\}&\{1,1\}\\ [3,1,0]-[2,2,0]&t(t-1)^2&\frac12t(t-1)^2&\{0,1,1,\infty\}&\{0,1,1,\infty\}\\ [2,2,0]-[2,1,1]&(t-1)^2&t^2&\{1,1,\infty,\infty\}&\{0,0,\infty,\infty\}\\ [2,1,1]&t(t+2)&0&\{0,\infty,\infty\}&🙏 \end{matrix}$$

Let's keep track of which cases these constructions work for:$$\begin{matrix} \text{Case}&\text{Condition}&\text{Constructions}\\\hline 1&\rho\in Z_g,\,\rho\ne0,1,\infty&[2,1,1],\,?\\ 2&\rho\in Z_f,\,\rho\ne0,1,\infty&?,\,?\\ 3&\{0,1\}\subseteq Z_f&S_4,\,[3,1,0]-[2,2,0]\\ 4&\{0,\infty\}\subseteq Z_f&[3,1,0]-[2,2,0],\,[2,1,1]\\ 5&\{1,\infty\}\subseteq Z_f&[3,1,0]-[2,2,0],\,[2,2,0]-[2,1,1]\\ 6&\{0,0\}\subseteq Z_f&S_4,\,?\\ 7&\{1,1,1,1\}\subseteq Z_f&?\\ 8&\{\infty,\infty\}\subseteq Z_f&[2,2,0]-[2,1,1],\,[2,1,1] \end{matrix}$$

Looks like we'll need some families of polynomials in $\mathcal P^+_4$ such that $f$ and $g$ can have general roots $\rho\ne0,1,\infty$. Are there any other easy constructions for polynomials in $\mathcal P^+_4$?

One idea is to just square some quadratic polynomial, say$$P^{4A}_\lambda(x,y,z)\coloneqq\frac13(x^2+y^2+z^2-\lambda(xy+yz+zx))^2.$$For this polynomial, we have$$\begin{align*}f(t)&=(t^2+2-\lambda (2t+1))^2,\\g(t)&=(t^2+1-\lambda t)^2.\end{align*}$$Can $f$ and $g$ have any root $\rho\ne0,1,\infty$ for an appropriate choice of $\lambda$? Sure: just take $\lambda=\dfrac{\rho^2+2}{2\rho+1}$ and $\lambda=\dfrac{\rho^2+1}\rho$, respectively.

Sketching these two curves, we see that $P^{4A}_\lambda$ has the following zero sets for various values of $\lambda$:$$\begin{matrix} &Z_f&Z_g\\\hline \lambda=1&\{1,1,1,1\}&\emptyset\\ 1<\lambda<2&\begin{gathered}\{\rho,\rho,\rho',\rho'\}\\[-0.5em]{\small(0<\rho'<1<\rho<4)}\end{gathered}&\emptyset\\ \lambda=2&\{0,0,4,4\}&\{1,1,1,1\}\\ \lambda>2&\begin{gathered}\{\rho,\rho\}\\[-0.5em]{\small(\rho>4)}\end{gathered}&\begin{gathered}\{\rho,\rho,\rho^{-1},\rho^{-1}\}\\[-0.5em]{\small(\rho>1)}\end{gathered} \end{matrix}$$So these constructions are good for many of our incomplete cases:$$\begin{matrix} \text{Case}&\text{Condition}&\text{Constructions}\\\hline 1&\rho\in Z_g,\,\rho\ne0,1,\infty&[2,1,1],\,P^{4A}_\lambda\ {\small(\lambda>2)}\\ 2&\rho\in Z_f,\,\rho\ne0,1,\infty&P^{4A}_\lambda\ {\small(\lambda>1)},\,?\\ 6&\{0,0\}\subseteq Z_f&S_4,\,P^{4A}_2\\ 7&\{1,1,1,1\}\subseteq Z_f&P^{4A}_1 \end{matrix}$$

We're now left to construct a polynomial in $\mathcal P^+_4$ which has roots at the point $(\rho,1,1)$ (and thus also at $(1,\rho,1)$ and $(1,1,\rho)$, by symmetry), and also at some point that isn't a root of the corresponding $P^{4A}_\lambda$; let's choose $(1,1,1)$ here. (Of course, the correct thing to do is a dimension count to make sure that there is indeed a nonzero solution.) Again, maybe we want to construct this as the square of a quadratic to ensure positivity; what quadratic polynomial has roots at those 4 points?

This is easy if we take the quadratic as the product of two linear factors: note that the 4 points lie on the union of $y=z$ and $y+z=(\rho+1)x$; this suggests the polynomial $(y-z)^2(y+z-(\rho+1)x)^2$, which is homogeneous of degree 4 but not symmetric. No worries, we can just take the cyclic sum: define$$P^{4B}_\mu(x,y,z)\coloneqq\frac13\sum_{\text{cyc}}(y-z)^2(y+z-\mu x)^2,$$which will have the 4 roots as desired. Finally it is easy to check that $f(t)=(t-1)^2(t-(\mu-1))^2$ in this case, so that $Z_f=\{1,1,\mu-1,\mu-1\}$, which completes our list of required constructions:$$\begin{matrix} \text{Case}&\text{Condition}&\text{Constructions}\\\hline 2&\rho\in Z_f,\,\rho\ne0,1,\infty&P^{4A}_\lambda\ {\small(\lambda>1)},\,P^{4B}_{\rho+1} \end{matrix}$$

Remark: Note that taking $\rho=0,1$ (i.e., $\mu=1,2$) will overlap with some of our previous constructions; by comparing root sets and leading coefficients, it is easy to check that $P^{4B}_1=S_4$ and $P^{4B}_2=P^{4A}_1$. Also, it's possible to make sense of $\rho=\infty$ (i.e., $\mu=\infty$) if we normalise correctly, say$$P^{4B}_\infty\coloneqq\lim_{\mu\to\infty}\mu^{-2}P^{4B}_\mu,$$and by considering the root set and leading coefficient in this case we see that in fact $P^{4B}_\infty=[2,2,0]-[2,1,1]$.

Hence we have our solution to the generation problem for degree 4:

Theorem: The extremal rays of $\mathcal P^+_4$ are:$$\begin{matrix} &\langle P^{4A}_\lambda\rangle\ {\small(1<\lambda<\infty)},\\ &\langle P^{4B}_\mu\rangle\ {\small(1<\mu<\infty)},\\ &\langle[3,1,0]-[2,2,0]\rangle,\\ &\langle[2,2,0]-[2,1,1]\rangle,\\ &\langle[2,1,1]\rangle. \end{matrix}$$Any $P\in\mathcal P^+_4$ is a nonnegative linear combination of the polynomials listed above. $\square$

The only place in the literature where I could find this statement is in Ando (2022), Proposition 1.3, where it is deduced as a consequence of the (much harder) classification of extremal rays for nonnegative homogeneous cyclic polynomials of degree 4. (Coincidentally, Tetsuya Ando is the chair of the Problem Selection Committee for IMO 2023.) As far as I know, the proof in this post is original.

Exercises

Because there are so many more things to say that these deserve their own section.

Like, an actual inequality

  1. Solve in 30 seconds: Find the largest value of $M>0$ such that the inequality$$(x+y+z)^3\ge M(x+y-z)(y+z-x)(z+x-y)$$holds for all $x,y,z\ge0$.

Extremal rays of $\mathcal P^+_d$

  1. For each extremal ray $\langle P\rangle$ of $\mathcal P^+_3$, express $(x+y+z)P$ as a nonnegative linear combination of extremal rays of $\mathcal P^+_4$.
  2. Consider the following attempted construction of an extremal ray in $\mathcal P^+_4$: we check that for $\rho>4$, the polynomial $f(t)=t(t-\rho)^2(t-\sigma)$ with $$\frac2{1-\rho}+\frac1{1-\sigma}=\frac13$$satisfies $\sigma<0$ (so that $f\ge0$ on $[0,\infty)$) and $f'(1)=\frac43f(1)$. Recovering $P$ from $f$, we must have $(\{0,\rho,\rho\},\{1,1\})\subseteq(Z_f,Z_g)$. So this is a third construction for Case 2, where we should have $\dim\Omega=2$. What went wrong?
  3. Prove that if $P\in\mathcal P^+_d$ and $g(t)=P(t,1,0)\equiv0$, then $xyz\mid P$.
    (Hint: we can assume that $P$ is a linear combination of polynomials of the form $[k,d-k,0]$.)
    Hence show that the following are extremal rays of $\mathcal P^+_d$:
    1. $\langle[k,k,k]\rangle$, if $d=3k$;
    2. $\langle[k+1,k,k]\rangle$, if $d=3k+1$;
    3. $\langle[k+1,k+1,k]\rangle$ and $\langle[k+2,k,k]-[k+1,k+1,k]\rangle$, if $d=3k+2$.
  4. Let $S_6$ be the degree 6 Schur polynomial,$$\begin{align*}S_6&\coloneqq\frac13\sum x^4(x-y)(x-z)\\&=[6,0,0]-2[5,1,0]+[4,1,1].\end{align*}$$Show that $\langle S_6\rangle$ is not an extremal ray of $\mathcal P^+_6$.
    (Hint: we have $f_{S_6}(t)=S_6(t,1,1)=t^4(t-1)^2$; show that set of polynomials in $\mathcal P^+_6$ satisfying the constraint $\{0,0,0,0,1,1\}\subseteq Z_f$ has dimension 2, and find the two rays bounding this region. Note that since we no longer have $d\le5$, we can't immediately conclude that these rays are extremal rays of $\mathcal P^+_6$.)

Root diagrams

It turns out that we can actually do even less work in degree 4, by drawing the correct diagrams.

  1. Show that the roots of any $P\in\mathcal P^+_4\setminus\{0\}$ can be represented by a symmetric subset of the following region:

    (Hint: take the normalisation $x+y+z=1$; this is basically the same as the soil triangle.)

Note that:

  • The points $(t,1,1)$ are projected down to the $y=z$ line, which is a median/altitude/angle bisector of the triangle, with $t=0,1,\infty$ at the foot, centre, and vertex, respectively;

  • The points $(t,1,0)$ are projected down to the $z=0$ line, which is a side of the triangle, with $t=0,1,\infty$ at the vertex, midpoint, and other vertex, respectively.

  1. Recall that $P^{4A}_\lambda(x,y,z)\coloneqq\frac13(x^2+y^2+z^2-\lambda(xy+yz+zx))^2$. Without using coordinate geometry, show that the roots of $P^{4A}_\lambda$ are given by the following diagrams.

    (Hint: which conics have the same symmetries as the equilateral triangle?)
    Hence recover the table of the zero sets of $P^{4A}_\lambda$ in each case (reproduced here):$$\begin{matrix} &Z_f&Z_g\\\hline \lambda=1&\{1,1,1,1\}&\emptyset\\ 1<\lambda<2&\begin{gathered}\{\rho,\rho,\rho',\rho'\}\\[-0.5em]{\small(0<\rho'<1<\rho<4)}\end{gathered}&\emptyset\\ \lambda=2&\{0,0,4,4\}&\{1,1,1,1\}\\ \lambda>2&\begin{gathered}\{\rho,\rho\}\\[-0.5em]{\small(\rho>4)}\end{gathered}&\begin{gathered}\{\rho,\rho,\rho^{-1},\rho^{-1}\}\\[-0.5em]{\small(\rho>1)}\end{gathered} \end{matrix}$$

  2. Explain how the following diagram gives the construction for $P^{4B}_\lambda$:

Test sets

The following result is due to Timofte (2003); notice that this exactly recovers our previous results for $n=3$ and $d=3,4,5$.

Theorem (Half-degree principle): Let $F(x_1,\ldots,x_n)$ be a homogeneous symmetric polynomial of degree $d\ge2$ in $n$ variables. Then $F\ge0$ for all $x_i\ge0$ if and only if $F\ge0$ on all points $(x_1,\ldots,x_n)$ with $x_i\ge0$ and at most $\lfloor d/2\rfloor$ distinct nonzero coordinates.

Here we present the simplified approach by Reiner (2012).

  1. Let $\varphi(T)$ be a degree $n$ polynomial with $n$ distinct positive real roots. Show that there exists $\varepsilon>0$ such that for all $c\in[-\varepsilon,\varepsilon$], the polynomial $\varphi(T)+c$ also has $n$ distinct nonnegative real roots.
  2. Let $\varphi(T)$ be a degree $n$ polynomial with $n$ nonnegative real roots, of which there are $m$ distinct positive roots. Show that there exists $\varepsilon>0$ and a polynomial $\psi$ of degree $n-m$ such that for all $c\in[-\varepsilon,\varepsilon$], the polynomial $\varphi(T)+c\psi(T)$ also has $n$ nonnegative real roots, of which there are $>m$ distinct positive roots.
    (Hint: apply the previous result to $\varphi/\psi$ for an appropriately chosen factor $\psi$ of $\varphi$.)
  3. Let $e_k(x_1,\ldots,x_n)$ denote the elementary symmetric polynomial of degree $k$. Recall that $F$ can be uniquely written as a polynomial in $e_1,\ldots,e_n$; show that this polynomial is linear in the variables $e_k$ ($\lfloor d/2\rfloor<k\le n$) jointly.
  4. Show that the locus $\Omega$ of points $(x_1,\ldots,x_n)$ with $x_i\ge0$ determined by fixing the values of $e_1,\ldots,e_{\lfloor d/2\rfloor}$ is compact.
  5. Suppose that the point $(x_1,\ldots,x_n)$ with $x_i\ge0$ is chosen in $\Omega$ minimising $F$, with the maximal number $m$ of distinct positive components. By considering the polynomial$$\varphi(T)=\prod_i(T-x_i)=\sum_{k=0}^n(-1)^ke_kT^{n-k}$$and applying (2), show that $m\le\lfloor d/2\rfloor$. Conclude.

The decision problem

Recall that the decision problem requires us to find a minimal set $X_d$ such that $P\ge0$ on $X_d$ implies that $P\ge0$ for all $x,y,z\ge0$. This is not quite the right definition: for example, for $d=4,5$, we can't actually take $X_d$ to be $\mathcal L$, since by continuity we only need to check points in $\mathcal L$ with rational coordinates.

Let's fix the definition: set$$\Sigma=\{(x,y,z)\,:\,x\ge y\ge z\ge0,\,x+y+z=1\}.$$We now aim to find a minimal closed set $\mathcal X_d\subseteq\Sigma$ such that all homogeneous symmetric polynomials $P$ of degree $d$ which are nonnegative on $\mathcal X_d$ must also be nonnegative on all of $\Sigma$ (and hence for all $x,y,z\ge0$).

  1. Suppose that $P\in\mathcal P^+_d\setminus\{0\}$ has a unique root $(x_0,y_0,z_0)\in\Sigma$. Show that any choice of $\mathcal X_d$ must contain $(x_0,y_0,z_0)$.
    (Hint: Take $Q=[d,0,0]$, so that $Q>0$ on $\Sigma$; for any neighbourhood $U\subseteq\Sigma$ of $(x_0,y_0,z_0)$, show that there exists $\varepsilon>0$ such that $P-\varepsilon Q$ is only negative inside of $U$.)
  2. For each point $(x_0,y_0,z_0)$ on the relative boundary of $\Sigma$, construct $P\in\mathcal P^+_4\setminus\{0\}$ such that $P=0$ only on multiples of $(x_0,y_0,z_0)$. (This shows that $\mathcal X_4$ is essentially $\mathcal L$; taking $(x+y+z)P$ shows the same for $\mathcal X_5$.)
  3. For each point $(x_0,y_0,z_0)$ in the relative interior of $\Sigma$, construct $P\in\mathcal P^+_6\setminus\{0\}$ such that $P=0$ only on multiples of $(x_0,y_0,z_0)$.
    (Hint: consider the polynomial$$\left(\frac{x+y}{x_0+y_0}-\frac z{z_0}\right)\left(\frac{x+y}{y_0+z_0}-\frac z{x_0}\right)\left(\frac{x+y}{z_0+x_0}-\frac z{y_0}\right).)$$This shows that $\mathcal X_d$ has to be all of $\Sigma$ for $d\ge6$.

Degree 5

The approach described in this post can also be applied to classify the extremal rays of $\mathcal P^+_5$, with enough determination. Here we outline the most important cases.

The general homogeneous symmetric polynomial of degree 5 is$$P(x,y,z)=K[5,0,0]+A[4,1,0]+B[3,2,0]+C[3,1,1]+D[2,2,1].$$

  1. Prove the usual preliminary results about $f$ and $g$:
    • the map from $P$ to $f$ is injective;
    • the map from $P$ to $g$ has kernel of dimension 2 (generated by $[3,1,1]$ and $[2,2,1]$);
    • $f'(1)=\frac53f(1)$.
  2. For distinct $\rho,\rho'\ne0,1,\infty$, show that the set $\Omega$ of polynomials in $\mathcal P^+_5$ with $\{\rho,\rho'\}\subseteq Z_f$ has dimension$$\dim\Omega=\begin{cases}1,&\rho'\in\left[\max\left(0,\frac{5-2\rho}{\rho+2}\right),\frac{7-\rho}{5\rho+1}\right],\\0,&\text{otherwise}.\end{cases}$$(Hint: $f(t)=(t-\rho)^2(t-\rho')^2\tilde f(t)$ for some $\tilde f$ of degree $\le1$; take the logarithmic derivative at 1 to restrict the possible values of $\dfrac1{1-\rho}+\dfrac1{1-\rho'}$.)
  3. For $\rho\ne0,1,\infty$, show that the set of polynomials in $\mathcal P^+_5$ with $\rho\in Z_f$ has dimension 3, parametrised by $(K,A,B)$. Determine the set of these triples such that $\sigma\in Z_g$ for some $1<\sigma<\infty$. Hence determine the pairs $(\rho,\sigma)$ such that the set $\Omega$ of polynomials in $\mathcal P^+_5$ with $(\rho,\sigma)\in(Z_f,Z_g)$ has dimension 1.
    (Hint: show that $g(t)=(t+1)t^2h(t+t^{-1})$ for some polynomial $h$ of degree $\le2$, and express the coefficients of $h$ as linear functions of $K,A,B$.)
  4. For $\rho\ne0,1,\infty$, show that the set $\Omega$ of polynomials in $\mathcal P^+_5$ under each of the following constraints has dimension 1:
    • $\{\rho,0,1\}\subseteq Z_f$;
    • $\{\rho,0,\infty\}\subseteq Z_f$;
    • $\{\rho,1,\infty\}\subseteq Z_f$.

In each of the above cases, we can get some expression for $P$ by recovering it from $f$, though it would be less interpretable than our constructions in degree 4.

  1. Finish the classification of the extremal rays of $\mathcal P^+_5$. Check against Ando (2022), Theorem 1.4.

The dual cone

This was the original approach that I was going to write about when I first started on this post.

Degree 3

Recall the expressions $$\begin{align*}P(x,y,z)&=K[3,0,0]+A[2,1,0]+B[1,1,1],\\f(t)&=K(t^3+2)+A(t^2+t+1)+B(3t),\\g(t)&=K(t^3+1)+A\frac{t^2+t}2.\end{align*}$$Instead of analysing the cone of possible triples $(K,A,B)$ (which we identify with $\mathcal P^+_3$ by abuse of notation), we can instead look at the dual cone $\mathcal P^*_3$ of triples $(\kappa,\alpha,\beta)$ for which$$\kappa K+\alpha A+\beta B\ge0$$for all $(K,A,B)\in\mathcal P^+_3$. Geometrically, every point in $\mathcal P^*_3$ represents a supporting plane to $\mathcal P^+_3$.

Since the only restrictions defining $\mathcal P^+_3$ are given by $f(t)\ge0$ and $g(t)\ge0$ for all $t\ge0$, it should be clear that $\mathcal P^*_3$ is simply the cone generated by nonnegative linear combinations of the points $(t^3+2,t^2+t+1,3t)$ and $(t^3+1,\frac12(t^2+t),0)$ for $t\ge0$.

  1. Show that the $\kappa=1$ cross-section of $\mathcal P^*_3$ is given by the convex hull $\mathcal C_3$ of the union of the two parametric curves$$\begin{align*}\varphi(t)&\coloneqq\left(\frac{t^2+t+1}{t^3+2},\frac{3t}{t^3+2}\right),\\\psi(t)&\coloneqq\left(\frac{t^2+t}{2(t^3+1)},0\right),\end{align*}$$for $t\ge0$.
  2. Show that $\mathcal C_3$ is a triangle with vertices at $(\frac12,0)$, $(1,1)$, $(0,0)$, corresponding to the points $(x,y,z)=(1,1,0)$, $(1,1,1)$, $(1,0,0)$ respectively.

Now we have to figure out what extremal rays correspond to in the picture for the dual cone $\mathcal P^*_3$.

  1. Show that each point $(K,A,B)\in\mathcal P^+_3$ represents a supporting plane to $\mathcal P^*_3$; in the $\kappa=1$ cross-section, these are supporting lines to $\mathcal C_3$.
  2. Show that each line segment in $\mathcal P^+_3$ corresponds to a family of planes in $\mathcal P^*_3$ passing through a fixed line; in the $\kappa=1$ cross-section, these are families of supporting lines to $\mathcal C_3$ passing through a common point.
  3. Hence show that each extremal ray of $\mathcal P^+_3$ corresponds to a supporting line $\ell$ of $\mathcal P^+_3$ which must intersect $\mathcal C_3$ if you wiggle it while pivoting about any point on $\ell$.
  4. Show that the only such $\ell$ are the three sides of $\mathcal C_3$.

Degree 4

We set up the dual cone $\mathcal P^*_4$ and its $\kappa=1$ cross-section $\mathcal C_4$ analogously.$$\begin{align*}f(t)&=K(t^4+2)+A(t^3+t+1)+B(2t^2+1)+C(t^2+2t),\\g(t)&=K(t^4+1)+A\frac{t^3+t}2+Bt^2.\end{align*}$$

  1. Show that the $\kappa=1$ cross-section of $\mathcal P^*_4$ is given by the convex hull $\mathcal C_4$ of the union of the two parametric curves$$\begin{align*}\varphi(t)&\coloneqq\left(\frac{t^3+t+1}{t^4+2},\frac{2t^2+1}{t^4+2},\frac{t^2+2t}{t^4+2}\right),\\\psi(t)&\coloneqq\left(\frac{t^3+t}{2(t^4+1)},\frac{t^2}{t^4+1},0\right),\end{align*}$$for $t\ge0$.
  2. Show that the boundary of $\mathcal C_4$ consists of finitely many ruled surfaces.
  3. Show that extremal rays of $\mathcal P^+_4$ correspond to segments lying on the boundary of $\mathcal C_4$, joining two points on the parametric curves.
  4. Complete the classification of extremal rays of $\mathcal P^+_4$.

Open questions

  1. Using the method in this post, determine the extremal rays in the following families of polynomials which are nonnegative on nonnegative arguments:
    • Homogeneous cyclic polynomials of degree 3 in 3 variables (check against);
    • Homogeneous symmetric polynomials of degree 3 in 4 variables;
    • Any other family.
    Check against results in the literature, in particular the work of Tetsuya Ando, Vasile Cirtoaje, Mariyan and Nedelcho Milev, ...
  2. Determine the extremal rays of $\mathcal P^+_6$.

Comments

Post a Comment

Popular posts from this blog

SMO Open 2024 ??% Speedrun

-
Image
 Hi! It's Glen again. So I was supposed to write a post for next weekend, but I woke up this morning to pictures of this year's SMO Open Round 2 in my messages, and I figured I might as well give them a go. And then I figured that I should just release my solutions to beat everyone else to the chase. Hence, this blog post is a week early.
Read more

Musings about the IMO

-
Image
 (Dylan here.) With the IMO drawing near, I thought I'd stray from maths to do some rambling.  What is the IMO? What is tested at the IMO? Do I know enough maths? Why do people care about the IMO? Should I care about the IMO? How do I get to/train for the IMO? How do I know if I'm improving? What happens after the IMO?
Read more