# Symmetric polynomial optimization

Recently I asked a stupid question here (there’s no harm in that, even Fields medalist Terence Tao advises to ask dumb questions once in a while). Here is a variant question that may be more difficult, perhaps even suitable for MathOverflow.

Let $n\geq 3$, and $a,b$ be two positive numbers with $\frac{a}{n} \gt b^{\frac{1}{n}}$ ; then the set

$$K= \bigg\lbrace (x_1,x_2, \ldots ,x_n) \in (0,\infty)^n \bigg| \sum_{k=1}^nx_k=a, \ \prod_{k=1}^nx_k=b \bigg\rbrace$$

is nonempty and compact (it is included in $[0,a]^n$), and its boundary is homeomorphic to $S^{n-2}$ (a nice argument shows this here ). Let $f$ be a symmetric polynomial in $x_1,x_2, \ldots,x_n$. Then $f$ attains a minimum $m$ on $K$. Let us call a point $p=(p_1,p_2, \ldots ,p_n)$ of $K$ extremist if all its coordinates are equal but one (in other words, there is an index $i$ such that the set $\lbrace p_j\rbrace_{j \neq i}$ is a singleton). Also, call it weakly extremist if some two coordinates of $p$ are equal.

Is it true that $m$ is always attained at an extremist point (we are of course not forbidding $f$ from also attaining $m$ at other, non-extremist points, which will certainly happen is $f$ is constant for example) ?

Is it true that $m$ is always attained at a weakly extremist point?

My progress so far on this problem : I can show that the answer is YES to both the questions when $n=3$. Indeed, by the fundamental theorem for symmetric polynomials it suffices to treat the special case $f(x_1,x_2,x_3)=x_1x_2+x_1x_3+x_2x_3$. Then for $(x_1,x_2,x_3) \in K$, $x_1$ varies in an interval $[\alpha,\beta]$ where $\alpha$ and $\beta$ are the two smallest roots of the polynomial $P=x(a-x)^2-4b$. Also,

$$f(x_1,x_2,x_3)=x_1(a-x_1)+\frac{b}{x_1}=g(x_1)$$ On the interval $[\alpha,\beta]$, the derivative $g’$ has two simple zeros, one at $\beta’=\frac{a-\beta}{2}$ and the other at $\alpha’=\frac{a-\alpha}{2}$. If we put $m=g(\beta)$ and $M=g(\alpha)$, then $M=g(\alpha)=g(\alpha’)$ and $m=g(\beta)=g(\beta’)$, so that the original interval $I=[\alpha,\beta]$ can be decomposed as

$$I=I_1 \cup I_2 \cup I_3, \ \ I_1=[\alpha,\beta’], \ I_2=[\beta’,\alpha’], \ I_3=[\alpha’,\beta]$$ and for $i=1,2,3$, we see that $g$ restricts to a bijection $I_i \to [m,M]$. So the minimum $m$ is attained at the extremist point $(\beta,\beta’,\beta’)$ and the maximum $M$ is attained at the extremist point $(\alpha,\alpha’,\alpha’)$.

-

Look at the map $s : K \to \Bbb R^{n-2}$ given by $(x_1,\ldots,x_n) \mapsto (\sigma_2,\ldots,\sigma_{n-1})$ where the $\sigma_i$ are the other elementary symmetric polynomials in the $x_j$.

A symmetric polynomial on $K$ is then equivalent to a polynomial on the $\sigma_i$, and $s$ is a $n!$-fold covering. The image of $s$ is a compact subspace of $\Bbb R^{n-2}$ delimited by the equation $\Delta = 0$ where $\Delta = \prod_{i < j} (x_i-x_j)^2$. (it is not the whole set of solutions to $\Delta \ge 0$ because there are polynomials with positive discriminant and nonreal roots).

Then the image by $s$ of the extremist points are "corners" of this domain, and the weakly extremist points are the boundary.

In the case $n=3$, your polynom $P$ corresponds to the discriminant, and the image of $s$ is $[\alpha ; \beta]$. As you've shown, as you go along the circle, you go back and forth in this interval $3$ times.

Given that the image of $s$ has nonempty interior, you can build a polynomial in the $\sigma_i$ with a minimum in this interior just like in the linked question. For example, with $n=3$, you can pick $g(\sigma_2) = (\sigma_2 - (\alpha+\beta)/2)^2$. Then , $g \circ s$ has $6$ minimums on $K$, and not at extremist points. You can do more and choose a polynomial $g$ on $\sigma_2$ that has its global minimum and maximum in $(\alpha;\beta)$. Then the global extrema of $g \circ s$ are not at extremist points (though there are always local extrema or inflexion points there)

-
I believe your $g$ example is wrong : it is not a symmetric polynomial in $x_1,x_2,x_3$ (because $\alpha+\beta$ is not a polynomial in $x_1,x_2,x_3$). –  Ewan Delanoy Jan 7 '13 at 8:33
$g$ is a polynomial in the elementary symmetric polynomials, so $g \circ s = ((x_1x_2+x_1x_3+x_2x_3)-(\alpha+\beta)/2)^2$ is a symmetric polynomial in $x_1,x_2,x_3$. $\alpha$ and $\beta$ are constants, just like $a$ and $b$. –  mercio Jan 7 '13 at 8:36
Right. What exactly is a “$n$!-fold covering” ? –  Ewan Delanoy Jan 7 '13 at 8:45
A point in the interior of $s(K)$ has $n!$ preimages by $s$ : there are $n!$ ways to order the $n$ distincts roots of $x^n - ax^{n-1} + \sigma_2x^{n-2} - \ldots + (-1)^{n-1}\sigma_{n-1}x + (-1)^n b = 0$. The $6$ minimums of my $g$ are all a different ordering of three distinct real numbers : $(p,q,r), (p,r,q), (q,p,r), \ldots$ are $6$ distinct points in $K$. –  mercio Jan 7 '13 at 8:50