Let be the Torus. A function can be described by it’s Fourier series. We can, more generally, consider any Borel complex measure . The Fourier coefficients then look like , where, as usual, denotes the character of associated with . The sequence is called the Fourier transform of . It is not hard to see that if and only if it’s Fourier transform vanishes. In other words, the Fourier transform of a measure describes it. We can actually think of the Fourier transform as being a change of variables. Quite often one has to deal with a measure described by its Fourier transform, so it is important to be able to deduce some properties of the measure by looking only at the Fourier transform. One important property of a measure is being positive (and in particular real). This can be defined as for all Borel set . The Herglotz theorem asserts that is positive if and only if it’s Fourier transform is positive definite:
Definition 1 (Positive Definite Sequence) A sequence of complex numbers is positive definite if for any finite sequence of complex numbers we have
It is not hard to see that a sequence is positive definite if and only if the Toeplitz matrix is positive semi-definite por all (in the sense that all eigenvalues are non-negative).
Using the idea that the Fourier transform is a change of variables, and furthermore that it is unitary, a measure is positive (meaning it’s positive definite on the “space” basis) if and only if when composed by the unitary Fourier transform it is still positive definite (in the “frequency” basis).
It is easy to see that the Fourier transform of a positive measure must be a positive definite function: Let be a positive measure and be any finite sequence of complex numbers. Then
Theorem 2 (Herglotz) Let be a measure on . Then is positive if and only if is a positive definite sequence.
This is quite good but we still need a way to recognize positive definite sequences, or to create them in an easy way. The Polya criterion makes exactly this:
Theorem 3 (Polya criterion) Let be non-negative, non-increasing and convex (meaning that if then the point is bellow the line uniting and , or in other words, ).
Then the sequence is positive definite.
This theorem is apparently well known in probability, but I only very recently came across it. In probability it is stated for probability measures on , but it can be easily adapted to this scenario. To see a proof for the probability case see this paper by Zoltán. It is also to note that not all positive definite sequences fall in the Polya family (as are called the sequences satisfying the criterion).
2. Proof of the Polya Criterion
To prove the theorem we first introduce the Fejér kernel, , the second equality can be obtained multiplying by and rearranging the geometric series thus obtained. We see that is a positive function, and so the measure that has as density is a positive measure. Thus the Fourier transform, must be a positive definite function, by Herglotz theorem. Since the characters are orthogonal, the Fourier transform of is if and otherwise. We note that is in the Polya family. To add some geometric intuition, note that the graph of the sequence is an isosceles triangle with a vertex at and the other two at and .
Now let be a sequence in the Polya family. Assume first that for some (and so for all ). Then we claim that we can write as a positive linear combination of the Fourier transform of Fejér kernels (positive means with positive coefficients). We first try to get some geometric feeling for why this is so: what we claim is that can be obtained as the sum of the triangles (for some positive ).
We prove the claim by induction on . If , then is just positive at and so . For we note that is still in the Polya family and so, by induction hypothesis, is a positive linear combination of Fourier transforms of Fejér kernels, and thus so is .
Now let be an arbitrary sequence in the Polya family and let . Since the measure (this measure gives measure to any set containing and measure to any other set) is positive and is the constant sequence equal to , we just have to prove that is positive definite, or in other words, we can assume that .
Thus for any natural number there is a sequence in the Polya family such that for and for some (we just define . This will eventually reach unless perhaps when , but since is convex, if this happens then is constant from that point on. Since the limit must be we get that is already ). Since the definition of positive definite sequence is local (in the sense that it only uses the sequence over finite sets of indices) we are now done, more explicitly, let be a finite sequence of complex numbers, and let be as just defined. We have that is positive definite by the previous case, so
and thus is positive definite as well.