Schur convexity and positive definiteness of the even degree complete homogeneous symmetric polynomials

6 August, 2017 in expository, math.AC, math.CA | Tags: positive definiteness, symmetric polynomials | by Terence Tao

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.

18 comments

Comments feed for this article

6 August, 2017 at 6:44 pm

unowatblog

There is a typo in the definition of $h_d$: the last index is $i_d$ rather than $i_n$.

Aside, since Schur convexity seems to me a natural solution – would you consider sum of squares type identity a different solution?

7 August, 2017 at 7:43 am

Terence Tao

Thanks for the correction!

One could convert the Schur convexity proof into a (rather artificial looking) sum of squares proof, but if there was a nice looking sum of squares representation analogous to that for $h_2$ then I would consider that to be a different proof.

Here is one small observation that might help towards a different proof: if one already knows the non-negativity of $h_d(x_1,\dots,x_n)$ for even $d$ , then this implies the non-negativity of $h_d(x_1,\dots,x_n,y,-y)$ for any $y$ and even $d$ . This is because the generating function $\sum_{d=0}^\infty h_d(x_1,\dots,x_n,y,-y) t^d$ is equal to the generating function of $\sum_{d=0}^\infty h_d(x_1,\dots,x_n) t^d$ times $\frac{1}{(1-yt)(1+yt)} = 1 + y^2 t^2 + y^4 t^4 + \dots$ ; the latter has only even powers and non-negative coefficients, hence the claim. So one can “cancel” any pair $y,-y$ that occurs in $x_1,\dots,x_n$ , which for instance demonstrates non-negativity of $h_d(x_1,\dots,x_n)$ whenever the $x_1,\dots,x_n$ all have the same magnitude. I wasn’t able to convert this argument into a proof of the general case though.

6 August, 2017 at 7:53 pm

andrescaicedo

At least on my screen the tag (2) is not visible. (I found it by looking at the TeX code of the displayed identity.)

[Corrected, thanks – T.]

6 August, 2017 at 11:23 pm

Orr Shalit

It might be better to start the induction with d=2 (to obtain the condition for strict inequality).

[Suggestion implemented, thanks – T.]

7 August, 2017 at 7:43 am

Anonymous

Maybe this works. Let $Z_1,\dots,Z_n$ be i.i.d exponentially distributed with parameter 1. Let $S=(\sum_{i=1}^n x_i Z_i)^d/d!$ . The coefficient of a monomial $\prod_i x_i^{d_i}$ in $S$ is $\prod_i Z_i^{d_i}/d_i!$ whose expected value is $1$ because the $d_i$ ‘th moment of $Z_i$ is $d_i!$ . So $h_d(x_1,\dots,x_n)$ is the expected value of $S$ , clearly non-negative for even $d$ .

7 August, 2017 at 8:35 am

Synia

Really nice ! Another way of seeing that $h_d(x_1, \dots, x_n) = \mathbb{E}\left( \frac{1}{d!} ( \sum_{j = 1}^n x_j Z_j )^d \right)$ is by writing $h_d(x_1, \dots, x_n) = [t^d] \prod_{j = 1}^n \frac{1}{1 - x_j t} =[t^d] \prod_{j = 1}^n \mathbb{E}\left( e^{t x_j Z_j} \right)$

$= [t^d] \mathbb{E}\left( e^{t \sum_{j = 1}^n x_j Z_j} \right)$ where $[t^d] f(t)$ is the $d$ -th Fourier coefficient (here, we suppose $|t x_j | < 1$ for all $j$ for the convergence).

7 August, 2017 at 9:16 am

Terence Tao

Very nice! I was hunting for a probabilistic interpretation of $h_d$ (this being another major way to prove positivity results, besides sum of squares methods and induction methods) but did not see this very neat moment interpretation. I think this is a good demonstration of the power of the probabilistic method.

(It now makes me wonder more generally if Schur polynomials have a similarly nice probabilistic interpretation. Of course, one can simply plug in the probabilistic interpretation of $h_d$ into the first Jacobi-Trudi formula, but I’m hoping for something more than this…)

15 September, 2021 at 7:10 am

Aditya Guha Roy

In fact Hunter’s result says that $h_{2r}(x_1,....,x_n) \ge \frac{||x||^{2r}}{2^rr!};$ I strongly believe that this probabilistic argument can be amplified to deduce Hunter’s original inequality too.

8 August, 2017 at 4:54 am

David Speyer

Very nice indeed!

I would say that this is morally a “sum of squares” argument; you have expressed $h_d$ as an integral of a $d$-th power. I imagine that, by replacing the integral by a suitable average over finitely many values, you could obtain a literal sum of squares expression.

8 August, 2017 at 7:46 am

Terence Tao

True; indeed it looks like all one needs to do is to replace the exponential random variable $Z$ by a discrete random variable which matches moments with the continuous one up to $d^{th}$ order and one would get a discrete representation. (The existence of such a discrete random variable follows from Caratheodory’s theorem.)

8 August, 2017 at 6:10 am

Arash B

“To establish this criterion, we again induct on $d$ “; Isn’t it induction on $n$?

[Corrected, thanks – T.]

8 August, 2017 at 3:58 pm

David Speyer

You might already know this, but there is a positivity property for Schur polynomials: If $\lambda$ is a partition with all even parts, then $s_{\lambda}(x_1, \ldots, x_n)$ is nonnegative for any real inputs. (And, I think, positive unless the inputs are all zero, but I’m not sure.)

By symmetry and continuity, it is enough to show that $s_{\lambda}(x_1, \ldots, x_n) > 0$ when $x_1 > x_2 > \cdots x_n$ . We recall the ratio of alternants formula: $s_{\lambda}(x_1, \ldots, x_n) = \det(x_i^{\lambda_j + n -j})/\det(x_i^{n-j})$ . So it is enough to show that $\det(x_i^{\lambda_j + n -j}) > 0$ when $x_1 > x_2 > \cdots x_n$ and all the $\lambda_i$ are even. By continuity, it is enough to show that $\det(x_i^{\lambda_j + n -j}) \neq 0$ under these conditions.

Suppose to the contrary that $\det(x_i^{\lambda_j + n -j}) = 0$ . Then there is a linear relation $\sum_j c_j x_i^{\lambda_j+n-j} = 0$ . In other words, the polynomial $\sum c_j x^{\lambda_j+n-j}$ has $n$ distinct real roots. But the condition that the parts of $\lambda$ are even means that that the exponents $\lambda_j+n-j$ alternate in parity, which means Descartes’ Rule of Signs will permit only $n-1$ real roots, a contradiction. $\square$

If we wanted to show strict positivity, we’d need to show that $x_i-x_j$ only divided $\det(x_i^{\lambda_j + n -j}) \neq 0$ once; we’ve shown strict positivity off the locus where two of the $x_i$ are equal already.

I believe this was an exercise in Barvinok’s convexity textbook, but I don’t have it at hand to check.

9 August, 2017 at 6:24 am

Synia

This gives an alternative proof for the positivity of $h_{2n}$ since $h_n = s_{(n)}$ .

9 August, 2017 at 12:24 pm

Terence Tao

Nice! (I knew one could use the rule of signs to prove that the Schur polynomials were positive when the inputs $x_1,\dots,x_n$ were positive, but this was already obvious from the Young tableau expansion.)

Unfortunately most Schor polynomials can vanish outside of the origin; indeed, by testing a Schur polynomial $s_\lambda$ on a basis vector $(1,0,\dots,0)$ using the Young tableau expansion, one gets zero unless $\lambda$ has only one non-zero part. So the only strictly positive definite Schur polynomials are the $h_{2n}$ . (Apoorva Khare and I have an upcoming paper where we had a theorem that worked for all strictly positive definite Schur polynomials, so it was a bit disappointing to realise how few of them there were.)

10 August, 2017 at 7:34 am

David Speyer

Oh wow, I should have noticed that about $s_{\lambda}(1,0,0,\ldots,0)=0$ . Huh, I wonder what the real points where $s_{\lambda}$ vanishes, when all parts of $\lambda$ are even, look like.

21 August, 2017 at 8:34 pm

Anonymous

Theorem 1(i) is easy if all the reals have the same sign. Otherwise, without loss of generality, $x_1$ is positive and $x_2$ is negative. The identity

$\displaystyle \frac{1}{1-tx_1} \frac{1}{1-tx_2} = \frac{x_1}{x_1+(-x_2)} \frac{1}{1-tx_1} + \frac{(-x_2)}{x_1+(-x_2)} \frac{1}{1-tx_2},$

shows that $h_d(x_1,x_2,\dots,x_n)$ is a convex combination of $h_d(x_1,0,\dots,x_n)$ and $h_d(0,x_2,\dots,x_n)$ . These are each strictly positive for even $d$ by induction on the number of non-zero components.

23 August, 2017 at 1:14 pm

Anonymous

Here is a proof of strict positivity, using log-convexity.
This approach gives Hunter’s bound
$h_{2r}\geq (\sum x_i^2)^r/2^r r!$ , which I don’t see a way to get just using moment generating functions.

Define $\mathcal C$ to be the set of exponential generating functions of log-convex sequences.
The Davenport-Pólya theorem says that $\mathcal C$ is closed under products.

I will use the following lemma. If $f,g\in\mathcal C$ then the even coefficients of $f(t)g(-t)$ are non-negative.
Proof: the coefficient of $t^n$ is $\sum_{i} \binom{n}{i} (-1)^i f_i g_{n-i}$ .
The sequence $f_0g_n,f_1g_{n-1},\dots,f_ng_0$ is log-convex, which implies it is convex.
But a sum of the form $\sum_{i} \binom{n}{i} (-1)^i c_i$ is non-negative if $n$ is even and $c_0,\dots,c_n$ is convex. QED.

Assume $x_1,\dots,x_m > 0$ and $0 > x_{m+1},\dots,x_n$ . By abuse of notation, write $h_d=h_d(x_1,\dots,x_n)$ , and $h_d^+=h_d(x_1,\dots,x_m)$ , and $h_d^-=h_d(-x_{m+1},\dots,-x_n)$ . We have the identity $\sum_{d\geq 0} h_d t^d = (\sum_{d\geq 0} h_d^+ t^d) (\sum_{d\geq 0} h_d^- (-t)^d).$ Note $\mathcal C$ contains all functions of the form $1/(1-tx)$ for $x>0$ , and so contains $\sum_{d\geq 0} h_d^+ t^d$ and $\sum_{d\geq 0} h_d^- t^d$ by the formula (1) in the main post. By the lemma above, $h_d\geq 0$ for even $d$ .

To get a bound in terms of $\sum x_i^2$ , note that $\exp(-x^2t^2)/(1-tx)$ is
in $\mathcal C$ for $x>0$ :
the first few coefficients of $(tx)^k/k!$ are
[A000266](https://oeis.org/A000266), and they tend quickly to $k!e^{-1/2}(1+o(1))$ which is log-convex.
By the same argument as before, the even coefficients of
$\exp(-\sum x_i^2t^2/2)\sum_{d\geq 0} h_d t^d$
are non-negative. Multiplying by $\exp(\sum x_i^2t^2/2)$
gives the bound $h_{2r}\geq (\sum x_i^2)^r/2^r r!$ .

23 August, 2017 at 3:00 pm

Anonymous

Sorry, I realised that proof doesn’t work – convexity by itself isn’t strong enough to guarantee those even coefficients are non-negative in general.

	Anonymous on Erratum for “An inverse…
	Anonymous on Pointwise ergodic theorems for…
	Anonymous on 275A, Notes 3: The weak and st…
	Terence Tao on Pointwise ergodic theorems for…
	Terence Tao on Erratum for “An inverse…
	Anonymous on Notes on the B+B+t theore…
	Anonymous on Pointwise ergodic theorems for…
	Anonymous on Erratum for “An inverse…
	Erratum for “A… on An inverse theorem for the Gow…
	Anonymous on Analysis II
	Anonymous on Notes on the B+B+t theore…
	Anonymous on Twisted convolution and the se…
	Anonymous on A generalized Cauchy-Schwarz i…
	Notes on the B+B+t t… on Ultrafilters, nonstandard anal…
	Notes on the B+B+t t… on Soft analysis, hard analysis,…

Schur convexity and positive definiteness of the even degree complete homogeneous symmetric polynomials

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

18 comments

Leave a comment Cancel reply

For commenters

Schur convexity and positive definiteness of the even degree complete homogeneous symmetric polynomials

Share this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

18 comments

Leave a comment Cancel reply

For commenters