You are currently browsing the tag archive for the ‘symmetric polynomials’ tag.

The complete homogeneous symmetric polynomial of variables and degree can be defined as

thus for instance

and

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

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

In particular, unless . This can be compared against the superficially similar quadratic form

where are independent randomly chosen signs. The *Wigner semicircle law* says that for large , the eigenvalues of this form will be mostly distributed in the interval using the semicircle distribution, so in particular the form is quite far from being positive definite despite the presence of the first positive terms. Thus the positive definiteness is coming from the finer algebraic structure of , and not just from the magnitudes of its coefficients.

One could ask whether the same positivity holds for other degrees than two. For odd degrees, the answer is clearly no, since in that case. But one could hope for instance that

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 . In fact, a modification of his argument gives a little bit more:

Theorem 1Let , let be even, and let be reals.

- (i) (Positive definiteness) One has , with strict inequality unless .
- (ii) (Schur convexity) One has whenever majorises , with equality if and only if is a permutation of .
- (iii) (Schur-Ostrowski criterion for Schur convexity) For any , one has , with strict inequality unless .

*Proof:* We induct on (allowing to be arbitrary). The claim is trivially true for , and easily verified for , so suppose that and the claims (i), (ii), (iii) have already been proven for (and for arbitrary ).

If we apply the differential operator to using the product rule, one obtains after a brief calculation

Using (1) and extracting the coefficient, we obtain the identity

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 by an arbitrary symmetric, continuously differentiable function. To establish this criterion, we induct on (this argument can be made independently of the existing induction on ). If is majorised by , it lies in the permutahedron of . If lies on a face of this permutahedron, then after permuting both the and we may assume that is majorised by , and is majorised by for some , and the claim then follows from two applications of the induction hypothesis. If instead lies in the interior of the permutahedron, one can follow it to the boundary by using one of the vector fields , and the claim follows from the boundary case.

Finally, to obtain (i), we observe that majorises , where is the arithmetic mean of . But is clearly a positive multiple of , and the claim now follows from (ii).

If the variables 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.

Recently, I had tentatively announced a forthcoming result with Ben Green establishing the “Gowers inverse conjecture” (or more accurately, the “inverse conjecture for the Gowers uniformity norm”) for vector spaces over a finite field , in the special case when p=2 and when the function for which the inverse conjecture is to be applied is assumed to be a polynomial phase of bounded degree (thus , where is a polynomial of some degree ). See my FOCS article for some further discussion of this conjecture, which has applications to both polynomiality testing and to various structural decompositions involving the Gowers norm.

This conjecture can be informally stated as follows. By iterating the obvious fact that the derivative of a polynomial of degree at most d is a polynomial of degree at most d-1, we see that a function is a polynomial of degree at most d if and only if

for all . From this one can deduce that a function bounded in magnitude by 1 is a polynomial phase of degree at most d if and only if the *Gowers norm*

is equal to its maximal value of 1. The inverse conjecture for the Gowers norm, in its usual formulation, says that, more generally, if a function bounded in magnitude by 1 has large Gowers norm (e.g. ) then f has some non-trivial correlation with some polynomial phase g (e.g. for some ). Informally, this conjecture asserts that if a function has biased derivatives, then one should be able to “integrate” this bias and conclude that the function is biased relative to a polynomial of degree d. The conjecture has already been proven for . There are analogues of this conjecture for cyclic groups which are of relevance to Szemerédi’s theorem and to counting linear patterns in primes, but I will not discuss those here.

At the time of the announcement, our paper had not quite been fully written up. This turned out to be a little unfortunate, because soon afterwards we discovered that our arguments at one point had to go through a version of Newton’s interpolation formula, which involves a factor of d! in the denominator and so is only valid when the characteristic p of the field exceeds the degree. So our arguments in fact are only valid in the range , and in particular are rather trivial in the important case ; my previous announcement should thus be amended accordingly.

## Recent Comments