The complete homogeneous symmetric polynomial ${h_d(x_1,\dots,x_n)}$ of ${n}$ variables ${x_1,\dots,x_n}$ and degree ${d}$ can be defined as

$\displaystyle h_d(x_1,\dots,x_n) := \sum_{1 \leq i_1 \leq \dots \leq i_d \leq n} x_{i_1} \dots x_{i_d},$

thus for instance

$\displaystyle h_0(x_1,\dots,x_n) = 0,$

$\displaystyle h_1(x_1,\dots,x_n) = x_1 + \dots + x_n,$

and

$\displaystyle h_2(x_1,\dots,x_n) = x_1^2 + \dots + x_n^2 + \sum_{1 \leq i < j \leq n} x_i x_j.$

One can also define all the complete homogeneous symmetric polynomials of ${n}$ variables simultaneously by means of the generating function

$\displaystyle \sum_{d=0}^\infty h_d(x_1,\dots,x_n) t^d = \frac{1}{(1-t x_1) \dots (1-tx_n)}. \ \ \ \ \ (1)$

We will think of the variables ${x_1,\dots,x_n}$ as taking values in the real numbers. When one does so, one might observe that the degree two polynomial ${h_2}$ is a positive definite quadratic form, since it has the sum of squares representation

$\displaystyle h_2(x_1,\dots,x_n) = \frac{1}{2} \sum_{i=1}^n x_i^2 + \frac{1}{2} (x_1+\dots+x_n)^2.$

In particular, ${h_2(x_1,\dots,x_n) > 0}$ unless ${x_1=\dots=x_n=0}$. This can be compared against the superficially similar quadratic form

$\displaystyle x_1^2 + \dots + x_n^2 + \sum_{1 \leq i < j \leq n} \epsilon_{ij} x_i x_j$

where ${\epsilon_{ij} = \pm 1}$ are independent randomly chosen signs. The Wigner semicircle law says that for large ${n}$, the eigenvalues of this form will be mostly distributed in the interval ${[-\sqrt{n}, \sqrt{n}]}$ using the semicircle distribution, so in particular the form is quite far from being positive definite despite the presence of the first ${n}$ positive terms. Thus the positive definiteness is coming from the finer algebraic structure of ${h_2}$, and not just from the magnitudes of its coefficients.

One could ask whether the same positivity holds for other degrees ${d}$ than two. For odd degrees, the answer is clearly no, since ${h_d(-x_1,\dots,-x_n) = -h_d(x_1,\dots,x_n)}$ in that case. But one could hope for instance that

$\displaystyle h_4(x_1,\dots,x_n) = \sum_{1 \leq i \leq j \leq k \leq l \leq n} x_i x_j x_k x_l$

also has a sum of squares representation that demonstrates positive definiteness. This turns out to be true, but is remarkably tedious to establish directly. Nevertheless, we have a nice result of Hunter that gives positive definiteness for all even degrees ${d}$. In fact, a modification of his argument gives a little bit more:

Theorem 1 Let ${n \geq 1}$, let ${d \geq 0}$ be even, and let ${x_1,\dots,x_n}$ be reals.

• (i) (Positive definiteness) One has ${h_d(x_1,\dots,x_n) \geq 0}$, with strict inequality unless ${x_1=\dots=x_n=0}$.
• (ii) (Schur convexity) One has ${h_d(x_1,\dots,x_n) \geq h_d(y_1,\dots,y_n)}$ whenever ${(x_1,\dots,x_n)}$ majorises ${(y_1,\dots,y_n)}$, with equality if and only if ${(y_1,\dots,y_n)}$ is a permutation of ${(x_1,\dots,x_n)}$.
• (iii) (Schur-Ostrowski criterion for Schur convexity) For any ${1 \leq i < j \leq n}$, one has ${(x_i - x_j) (\frac{\partial}{\partial x_i} - \frac{\partial}{\partial x_j}) h_d(x_1,\dots,x_n) \geq 0}$, with strict inequality unless ${x_i=x_j}$.

Proof: We induct on ${d}$ (allowing ${n}$ to be arbitrary). The claim is trivially true for ${d=0}$, and easily verified for ${d=2}$, so suppose that ${d \geq 4}$ and the claims (i), (ii), (iii) have already been proven for ${d-2}$ (and for arbitrary ${n}$).

If we apply the differential operator ${(x_i - x_j) (\frac{\partial}{\partial x_i} - \frac{\partial}{\partial x_j})}$ to ${\frac{1}{(1-t x_1) \dots (1-tx_n)}}$ using the product rule, one obtains after a brief calculation

$\displaystyle \frac{(x_i-x_j)^2 t^2}{(1-t x_1) \dots (1-tx_n) (1-t x_i) (1-t x_j)}.$

Using (1) and extracting the ${t^d}$ coefficient, we obtain the identity

$\displaystyle (x_i - x_j) (\frac{\partial}{\partial x_i} - \frac{\partial}{\partial x_j}) h_d(x_1,\dots,x_n)$

$\displaystyle = (x_i-x_j)^2 h_{d-2}( x_1,\dots,x_n,x_i,x_j). \ \ \ \ \ (2)$

The claim (iii) then follows from (i) and the induction hypothesis.

To obtain (ii), we use the more general statement (known as the Schur-Ostrowski criterion) that (ii) is implied from (iii) if we replace ${h_d}$ by an arbitrary symmetric, continuously differentiable function. To establish this criterion, we induct on ${n}$ (this argument can be made independently of the existing induction on ${d}$). If ${(y_1,\dots,y_n)}$ is majorised by ${(x_1,\dots,x_n)}$, it lies in the permutahedron of ${(x_1,\dots,x_n)}$. If ${(y_1,\dots,y_n)}$ lies on a face of this permutahedron, then after permuting both the ${x_i}$ and ${y_j}$ we may assume that ${(y_1,\dots,y_m)}$ is majorised by ${(x_1,\dots,x_m)}$, and ${(y_{m+1},\dots,y_n)}$ is majorised by ${(x_{m+1},\dots,x_n)}$ for some ${1 \leq m < n}$, and the claim then follows from two applications of the induction hypothesis. If instead ${(y_1,\dots,y_n)}$ lies in the interior of the permutahedron, one can follow it to the boundary by using one of the vector fields ${(x_i - x_j) (\frac{\partial}{\partial x_i} - \frac{\partial}{\partial x_j})}$, and the claim follows from the boundary case.

Finally, to obtain (i), we observe that ${(x_1,\dots,x_n)}$ majorises ${(x,\dots,x)}$, where ${x}$ is the arithmetic mean of ${x_1,\dots,x_n}$. But ${h_d(x,\dots,x)}$ is clearly a positive multiple of ${x^d}$, and the claim now follows from (ii). $\Box$

If the variables ${x_1,\dots,x_n}$ are restricted to be nonnegative, the same argument gives Schur convexity for odd degrees also.

The proof in Hunter of positive definiteness is arranged a little differently than the one above, but still relies ultimately on the identity (2). I wonder if there is a genuinely different way to establish positive definiteness that does not go through this identity.