Uncertainty principles in Fourier analysis

Uncertainty principles in Fourier analysis are formalizations of the following principle: A function $f$ and its Fourier transform $\hat{f}$ cannot both be sharply ''localized''. This of course allows many interpretations, and by interpreting localization in various ways, we get theorems (usually inequalities) about the simultaneous behavior of $f$ and $\hat{f}$. We will formalize and prove the following uncertainty principles.

• $|f|^2$ and $|\hat{f}|^2$ cannot both have small variance (Heisenberg uncertainty principle)
•  Two self-adjoint operators cannot both have small norms compared to the norm of their commutator (Heisenberg uncertainty principle for operators)
•  $f$ and $\hat{f}$ cannot both decay faster than gaussian functions (Hardy's uncertainty principle)
• Not both $f$ and $\hat{f}$ can be nonzero only in a set of finite measure (Benedick's inequality)
• The entropy of $f$ and $\hat{f}$ cannot both be positive (Hirschman's inequality)

The first hint that such principles might be true is that the Fourier transform ''spreads out'' a function the more it is concentrated: $\mathcal{F}(f(tx))=\frac{1}{t}\hat{f}(\frac{\xi}{t})$. We now proceed to formalize and prove the principles.

Character sums and Pólya-Vinogradov inequality

In this post, we consider character sums, which are one of the central objects in the discrete Fourier analysis of the integers modulo $q$. We will prove the Pólya-Vinogradov estimate, which we will observe to be the best possible estimate up to a logarithmic factor, despite being easy to prove. Character sums arise in many problems in number theory, and we utilize them to prove classical bounds for the least quadratic nonresidue and primitive root modulo $q$. We also show that the generalized Riemann hypothesis reduces the bounds for the least quadratic nonresidue and primitive root considerably.

Fourier transform and its mapping properties

We present some classical results about the Fourier transform in $\mathbb{R}^n$ in this post, and some of them will be applied in later posts to partial differential equations, additive number theory, and other topics. In particular, we consider the validity of the Fourier inversion theorem in various forms, the $L^2$ theory of the Fourier transform and the mapping properties of the Fourier transform in many spaces.

Roth's theorem on arithmetic progressions

In this post, we give an application of Fourier analysis to combinatorics, more precisely to Ramsey theory. In Ramsey theory, a typical result tells that certain large but otherwise arbitrary objects (sets of integers, graphs, collections of points, etc.) are forced to contain some structure in them, thus implying intuitively that there is no complete randomness. The desired structure in these objects could mean for example large cliques or independent sets of vertices in the case of graphs, or some arithmetic structure in the case of sets of integers. One of the most basic arithmetic structures is of course an arithmetic progression, and there are several Ramsey theoretic results about their occurrence. We mention the following two theorems.

Theorem 1 (van der Waerden). Let $k$ and $\ell$ be positive integers. Then there exists a number $W(k,\ell)$ such that whenever the numbers in $\{1,2,...,N\}$ with $N\geq W(k,\ell)$ are colored using $\ell$ colors, there is a monochromatic arithmetic progression of length $k$ .

Theorem 2 (Szemerédi). Let $\delta>0$, and let $k$ be a positive integer. Then, if $A$ is any subset of $\{1,2,...,N\}$ with $N\geq N(k,\delta)$ and having density at least $\delta$ (that is, $|A|\geq \delta N$), the set $A$ contains an arithmetic progression of length $k$.

The first result was proved by van der Waerden in 1927 (back then, the result was an open problem that many famous mathematicians attempted to resolve, but it was the young van der Waerden who solved it). The latter result is a very deep and important result of Szemerédi from 1975 (the proof was so complicated that Szemerédi refused to write it down himself). Szemerédi's proof was based on his graph regularity lemma, and virtually every proof of the theorem has started a fruitful new research direction. For instance, Furstenberg proved the theorem using ergodic theory in 1977, and Gowers using Fourier analytic methods and his uniformity norms in 2001, and the latter proof also improved bounds on $W(k,\ell)$ enormously.

It is easy to see that van der Waerden's theorem is a special case of Szemerédi's; indeed, if $\{1,2,...,N\}$ is colored with $\ell$ colors, there is at least one monochromatic subset of density at least $\frac{1}{\ell}$. In addition, both theorems allow immediately an infinite version. For Szemerédi's theorem, the infinite version is that any subset of the natural numbers with a positive lower density contains arbitrarily long arithmetic progressions. In fact, there is a nice compactness argument that can be used to deduce the finite versions of the theorems from their infinite versions, but that is a different story.

We will not try to prove Szemerédi's theorem in this post, but we will prove its special case $k=3$ due to Roth from 1953. This case is an elegant and relatively short application of Fourier analysis into combinatorics. For convenience, we also formulate this claim.

Quadratic reciprocity via discrete Fourier analysis

In this post, we give a proof of the law of quadratic reciprocity based on discrete Fourier analysis and more precisely Gauss sums. This celebrated theorem has numerous proofs, but the most elementary ones usually boil down to some tedious combinatorial computations. In particular, after one has derived Gauss' lemma or some similar statement that is usually used in the proof, the big picture may become unclear, and one is left with some combinatorial counting problem. On the other hand, if one uses discrete Fourier analysis to prove the reciprocity law, the structure of the proof is simple, and one works in the context of trigonometric sums instead of solving an isolated combinatorial problem. Moreover, this method generalizes to higher reciprocity laws as well, and similar ideas as in what follows can be applied for example in proving the functional equation of the $L$-functions, the class number formula or the Pólya-Vinogradov inequality. Some of these results will be discussed in later posts.

A very short introduction to Fourier analysis

In later posts, we consider properties of Fourier series (for instance, convergence and divergence results), as well as lacunary trigonometric series and applications of Fourier series to sum identities, combinatorics and number theory. After that, we discuss the Fourier transform in $\mathbb{R}^d$ and phenomena related to it (uncertainty principles, $L^2$ theory, tempered distributions), and applications to the central limit theorem and PDE.

In this post, we say a a bit about Fourier analysis in general. In classical Fourier analysis, we have a function $f:G\to \mathbb{C}$, where $G$ is is usually the integers modulo $N$, that is $\mathbb{Z}_N$, or the real numbers $\pmod 1$, that is $\mathbb{R}/ \mathbb{Z}$, or the whole Euclidean space $\mathbb{R}^d$ ($G$ can also be the integers $\mathbb{Z}$, but that situation is just dual to $G=\mathbb{R}/\mathbb{Z}$). More generally, in harmonic analysis, $G$ could be any locally compact abelian group, and then the analogue of an exponential function would be a homomorphism from $G$ to $\mathbb{C}$. We want to represent the function $f:G\to \mathbb{C}$ as a sum or integral (depending on the domain) of combinations of trigonometric functions. It turns out that a general function, with some mild regularity properties, has such a representation, so many ''linear'' problems concerning arbitrary functions can be reduced to corresponding problems for trigonometric functions (a ''linear'' problem could for instance be a linear PDE, such as the heat equation, which was Joseph Fourier's original motivation, or a problem about arithmetic progressions). We use the trigonometric exponentials $e^{2\pi in x}$ instead of sines and cosines, since otherwise we would have to do everything separately for them. Besides, cosines and sines can be recovered from trigonometric exponentials by taking real and imaginary parts. The representations we are looking for are

$\begin{eqnarray}f(n)&=&\sum_{k\in \mathbb{Z}_N}\hat{f}(k)e^{\frac{2\pi i k}{N}},\quad\quad\,\,\,\,\, \,f:\mathbb{Z}_N\to \mathbb{C}\\f(x)&=&\sum_{n=-\infty}^{\infty}\hat{f}(n)e^{2\pi i n x},\quad \quad f:\mathbb{R}/\mathbb{Z}\to \mathbb{C}\\f(x)&=&\int_{\mathbb{R}^d}\hat{f}(\xi)e^{2\pi i x\cdot\xi}d\xi,\quad \quad f:\mathbb{R}^d\to \mathbb{C},\end{eqnarray}$
where $x\cdot \xi$ is the inner product of two vectors from $\mathbb{R}^d$.

The functions $\hat{f}$ are some coefficient functions, but not just any functions, as these are called the Fourier transform in the continuous case and Fourier coefficients in the discrete case. From the orthogonality relation

$\begin{eqnarray}\int_{0}^{1}e^{2\pi i (m-n)x}dx=\begin{cases} 0, \quad m \neq n\\ 1,\quad m=n,\end{cases}\end{eqnarray}$

(the name comes from the fact that this relation says that the pairwise inner products of distinct functions $e^{2\pi in x}$ are $0$) or from its equivalent for sums it follows, by multiplying both sides of the three equations above by exponentials and integrating (or summing) both sides, that if we formally change the order of integration (or summation), we arrive at

$\begin{eqnarray}\hat{f}(n)&=&\frac{1}{N}\sum_{k\in \mathbb{Z}_N}f(k)e^{-\frac{2\pi i k}{N}},\quad \quad n \in \mathbb{Z}_N\\\hat{f}(n)&=&\int_{0}^1 f(x)e^{-2\pi i n x}dx,\quad\,\,\,\,\,\, n \in \mathbb{Z}\\ \hat{f}(\xi)&=&\int_{\mathbb{R}^d}f(x)e^{-2\pi i x \cdot\xi}dx,\quad \,\,\,\xi \in \mathbb{R}^d\end{eqnarray}$

(in the first case, there is no problem in changing the order of summations). By definition, this is called a Fourier coefficient of $f$ (or the Fourier transform of $f$ in the third case). Notice that these three formulas resemble very much the three representation formulas given above, so the Fourier transform is essentially its own dual operation, and this is of course an important fact. Next we say a few words about the properties of these transforms.