## Polya’s criterion for positive definite sequences.

1. Introduction

Let ${{\mathbb T}={\mathbb R}/{\mathbb Z}}$ be the Torus. A function ${f\in L^2({\mathbb T})}$ can be described by it’s Fourier series. We can, more generally, consider any Borel complex measure ${\mu}$. The Fourier coefficients then look like ${\hat\mu(n)=\int_{\mathbb T} e_nd\mu}$, where, as usual, ${e_n:=e^{2\pi i nx}}$ denotes the character of ${\mathbb T}$ associated with ${n}$. The sequence ${\{\hat\mu(n)\}_n}$ is called the Fourier transform of ${\mu}$. It is not hard to see that ${\mu=0}$ if and only if it’s Fourier transform ${\hat\mu}$ 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 ${\mu(A)\geq0}$ for all Borel set ${A\subset {\mathbb T}}$. The Herglotz theorem asserts that ${\mu}$ is positive if and only if it’s Fourier transform ${\hat \mu}$ is positive definite:

Definition 1 (Positive Definite Sequence) A sequence ${\{a_n\}_{n\in {\mathbb Z}}}$ of complex numbers is positive definite if for any finite sequence ${\{z_j\}_{j=1}^m}$ of complex numbers we have

$\displaystyle \sum_{j,l=1}^ma_{j-l}z_j\overline{z_l}\geq0$

It is not hard to see that a sequence is positive definite if and only if the ${n\times n}$ Toeplitz matrix ${A:=[a_{i-j}]_{i,j=1}^n}$ is positive semi-definite por all ${n}$ (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 ${\mu}$ be a positive measure and ${\{z_j\}_{j=1}^m}$ be any finite sequence of complex numbers. Then

$\displaystyle \begin{array}{rcl} \displaystyle\sum_{j,l=1}^m\hat\mu(j-l)z_j\overline{z_l}&=& \displaystyle\sum_{j,l=1}^m\int_{\mathbb T} e^{2\pi i (j-l)x}d\mu(x) z_j\overline{z_l}=\sum_{j,l=1}^m\int_{\mathbb T} e^{2\pi i jx}z_j\overline{e^{2\pi i lx}z_l}d\mu(x) \\ &=&\displaystyle\int_{\mathbb T}\left|\sum_{j=1}^me^{2\pi i jx}z_j\right|^2d\mu(x)\geq0 \end{array}$

Theorem 2 (Herglotz) Let ${\mu}$ be a measure on ${\mathbb T}$. Then ${\mu}$ is positive if and only if ${\hat\mu}$ 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 ${f:{\mathbb N}\rightarrow {\mathbb R}}$ be non-negative, non-increasing and convex (meaning that if ${a\leq b\leq c}$ then the point $(b,f(b))$ is bellow the line uniting $(a,f(a))$ and $(c,f(c))$, or in other words, $f(b)\leq \frac{b-a}{c-a}f(c)+\frac{c-b}{c-a}(a)$).
Then the sequence $a_n=f(|n|)$ 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 ${{\mathbb R}}$, 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, $\displaystyle{F_n:=\sum_{|k|\leq n}\frac{n-|k|}ne_k=\frac1n\left(\frac{\sin(nx/2)}{\sin(x/2)}\right)^2}$, the second equality can be obtained multiplying ${F_n}$ by ${e_n}$ and rearranging the geometric series thus obtained. We see that ${F_n}$ is a positive function, and so the measure that has ${F_n}$ as density is a positive measure. Thus the Fourier transform, ${\hat F_n}$ must be a positive definite function, by Herglotz theorem. Since the characters ${e_n}$ are orthogonal, the Fourier transform of ${F_n}$ is ${\hat F_n(k)=\frac{n-|k|}n}$ if ${|k|\leq n}$ and ${\hat F_n(k)=0}$ otherwise. We note that ${\hat F_n}$ is in the Polya family. To add some geometric intuition, note that the graph of the sequence ${\hat F_n}$ is an isosceles triangle with a vertex at ${(0,1)}$ and the other two at ${(n,0)}$ and ${(-n,0)}$.

Now let ${a=\{a_n\}_{n\in {\mathbb Z}}}$ be a sequence in the Polya family. Assume first that ${a_m=0}$ for some ${m}$ (and so ${a_n=0}$ for all ${|n|>m}$). Then we claim that we can write ${a}$ 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 ${a}$ can be obtained as the sum of the triangles ${c_n\hat F_n}$ (for some positive ${c_n}$).

We prove the claim by induction on ${m}$. If ${m=1}$, then ${a}$ is just positive at ${n=0}$ and so ${a=a_0\hat F_1}$. For ${m>1}$ we note that ${b=a-ma_{m-1}F_m}$ is still in the Polya family and ${b_m=0}$ so, by induction hypothesis, ${b}$ is a positive linear combination of Fourier transforms of Fejér kernels, and thus so is ${a}$.

Now let ${a}$ be an arbitrary sequence in the Polya family and let ${l=\lim a_n}$. Since the measure ${l\delta_0}$ (this measure gives measure ${l}$ to any set containing ${0}$ and ${0}$ measure to any other set) is positive and ${\widehat{l\delta_0}}$ is the constant sequence equal to ${l}$, we just have to prove that ${a-l}$ is positive definite, or in other words, we can assume that ${\lim a_n=0}$.

Thus for any natural number ${m}$ there is a sequence ${b}$ in the Polya family such that ${a_n=b_n}$ for ${|n|\leq m}$ and ${b_k=0}$ for some ${k\geq m}$ (we just define ${b_{m+j}=\max(0,a_m-j(a_m-a_{m-1}))}$. This will eventually reach ${0}$ unless perhaps when ${a_m=a_{m-1}}$, but since ${a}$ is convex, if this happens then ${a}$ is constant from that point on. Since the limit must be ${0}$ we get that ${a_m}$ is already ${0}$). 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 ${\{z_j\}_{j=1}^m}$ be a finite sequence of complex numbers, and let ${b}$ be as just defined. We have that ${b}$ is positive definite by the previous case, so

$\displaystyle 0\leq\sum_{j,l=1}^mb_{j-l}z_j\overline{z_l}=\sum_{j,l=1}^ma_{j-l}z_j\overline{z_l}$

and thus ${a}$ is positive definite as well.