One of the most fundamental principles in Fourier analysis is the uncertainty principle. It does not have a single canonical formulation, but one typical informal description of the principle is that if a function {f} is restricted to a narrow region of physical space, then its Fourier transform {\hat f} must be necessarily “smeared out” over a broad region of frequency space. Some versions of the uncertainty principle are discussed in this previous blog post.

In this post I would like to highlight a useful instance of the uncertainty principle, due to Hugh Montgomery, which is useful in analytic number theory contexts. Specifically, suppose we are given a complex-valued function {f: {\bf Z} \rightarrow {\bf C}} on the integers. To avoid irrelevant issues at spatial infinity, we will assume that the support {\hbox{supp}(f) := \{ n \in {\bf Z}: f(n) \neq 0 \}} of this function is finite (in practice, we will only work with functions that are supported in an interval {[M+1,M+N]} for some natural numbers {M,N}). Then we can define the Fourier transform {\hat f: {\bf R}/{\bf Z} \rightarrow {\bf C}} by the formula

\displaystyle \hat f(\xi) := \sum_{n \in {\bf Z}} f(n) e(-n\xi)

where {e(x) := e^{2\pi i x}}. (In some literature, the sign in the exponential phase is reversed, but this will make no substantial difference to the arguments below.)

The classical uncertainty principle, in this context, asserts that if {f} is localised in an interval of length {N}, then {\hat f} must be “smeared out” at a scale of at least {1/N} (and essentially constant at scales less than {1/N}). For instance, if {f} is supported in {[M+1,M+N]}, then we have the Plancherel identity

\displaystyle \int_{{\bf R}/{\bf Z}} |\hat f(\xi)|^2\ d\xi = \| f \|_{\ell^2({\bf Z})}^2 \ \ \ \ \ (1)

while from the Cauchy-Schwarz inequality we have

\displaystyle |\hat f(\xi)| \leq N^{1/2} \| f \|_{\ell^2({\bf Z})}

for each frequency {\xi}, and in particular that

\displaystyle \int_I |\hat f(\xi)|^2\ d\xi \leq N |I| \| f \|_{\ell^2({\bf Z})}^2

for any arc {I} in the unit circle (with {|I|} denoting the length of {I}). In particular, an interval of length significantly less than {1/N} can only capture a fraction of the {L^2} energy of the Fourier transform of {\hat f}, which is consistent with the above informal statement of the uncertainty principle.

Another manifestation of the classical uncertainty principle is the large sieve inequality. A particularly nice formulation of this inequality is due independently to Montgomery and Vaughan and Selberg: if {f} is supported in {[M+1,M+N]}, and {\xi_1,\ldots,\xi_J} are frequencies in {{\bf R}/{\bf Z}} that are {\delta}-separated for some {\delta>0}, thus {\| \xi_i-\xi_j\|_{{\bf R}/{\bf Z}} \geq \delta} for all {1 \leq i<j \leq J} (where {\|\xi\|_{{\bf R}/{\bf Z}}} denotes the distance of {\xi} to the origin in {{\bf R}/{\bf Z}}), then

\displaystyle \sum_{j=1}^J |\hat f(\xi_j)|^2 \leq (N + \frac{1}{\delta}) \| f \|_{\ell^2({\bf Z})}^2. \ \ \ \ \ (2)

The reader is encouraged to see how this inequality is consistent with the Plancherel identity (1) and the intuition that {\hat f} is essentially constant at scales less than {1/N}. The factor {N + \frac{1}{\delta}} can in fact be amplified a little bit to {N + \frac{1}{\delta} - 1}, which is essentially optimal, by using a neat dilation trick of Paul Cohen, in which one dilates {[M+1,M+N]} to {[MK+K, MK+NK]} (and replaces each frequency {\xi_j} by their {K^{th}} roots), and then sending {K \rightarrow \infty} (cf. the tensor product trick); see this survey of Montgomery for details. But we will not need this refinement here.

In the above instances of the uncertainty principle, the concept of narrow support in physical space was formalised in the Archimedean sense, using the standard Archimedean metric {d_\infty(n,m) := |n-m|} on the integers {{\bf Z}} (in particular, the parameter {N} is essentially the Archimedean diameter of the support of {f}). However, in number theory, the Archimedean metric is not the only metric of importance on the integers; the {p}-adic metrics play an equally important role; indeed, it is common to unify the Archimedean and {p}-adic perspectives together into a unified adelic perspective. In the {p}-adic world, the metric balls are no longer intervals, but are instead residue classes modulo some power of {p}. Intersecting these balls from different {p}-adic metrics together, we obtain residue classes with respect to various moduli {q} (which may be either prime or composite). As such, another natural manifestation of the concept of “narrow support in physical space” is “vanishes on many residue classes modulo {q}“. This notion of narrowness is particularly common in sieve theory, when one deals with functions supported on thin sets such as the primes, which naturally tend to avoid many residue classes (particularly if one throws away the first few primes).

In this context, the uncertainty principle is this: the more residue classes modulo {q} that {f} avoids, the more the Fourier transform {\hat f} must spread out along multiples of {1/q}. To illustrate a very simple example of this principle, let us take {q=2}, and suppose that {f} is supported only on odd numbers (thus it completely avoids the residue class {0 \mod 2}). We write out the formulae for {\hat f(\xi)} and {\hat f(\xi+1/2)}:

\displaystyle \hat f(\xi) = \sum_n f(n) e(-n\xi)

\displaystyle \hat f(\xi+1/2) = \sum_n f(n) e(-n\xi) e(-n/2).

If {f} is supported on the odd numbers, then {e(-n/2)} is always equal to {-1} on the support of {f}, and so we have {\hat f(\xi+1/2)=-\hat f(\xi)}. Thus, whenever {\hat f} has a significant presence at a frequency {\xi}, it also must have an equally significant presence at the frequency {\xi+1/2}; there is a spreading out across multiples of {1/2}. Note that one has a similar effect if {f} was supported instead on the even integers instead of the odd integers.

A little more generally, suppose now that {f} avoids a single residue class modulo a prime {p}; for sake of argument let us say that it avoids the zero residue class {0 \mod p}, although the situation for the other residue classes is similar. For any frequency {\xi} and any {j=0,\ldots,p-1}, one has

\displaystyle \hat f(\xi+j/p) = \sum_n f(n) e(-n\xi) e(-jn/p).

From basic Fourier analysis, we know that the phases {e(-jn/p)} sum to zero as {j} ranges from {0} to {p-1} whenever {n} is not a multiple of {p}. We thus have

\displaystyle \sum_{j=0}^{p-1} \hat f(\xi+j/p) = 0.

In particular, if {\hat f(\xi)} is large, then one of the other {\hat f(\xi+j/p)} has to be somewhat large as well; using the Cauchy-Schwarz inequality, we can quantify this assertion in an {\ell^2} sense via the inequality

\displaystyle \sum_{j=1}^{p-1} |\hat f(\xi+j/p)|^2 \geq \frac{1}{p-1} |\hat f(\xi)|^2. \ \ \ \ \ (3)

Let us continue this analysis a bit further. Now suppose that {f} avoids {\omega(p)} residue classes modulo a prime {p}, for some {0 \leq \omega(p) < p}. (We exclude the case {\omega(p)=p} as it is clearly degenerates by forcing {f} to be identically zero.) Let {\nu(n)} be the function that equals {1} on these residue classes and zero away from these residue classes, then

\displaystyle \sum_n f(n) e(-n\xi) \nu(n) = 0.

Using the periodic Fourier transform, we can write

\displaystyle \nu(n) = \sum_{j=0}^{p-1} c(j) e(-jn/p)

for some coefficients {c(j)}, thus

\displaystyle \sum_{j=0}^{p-1} \hat f(\xi+j/p) c(j) = 0.

Some Fourier-analytic computations reveal that

\displaystyle c(0) = \frac{\omega(p)}{p}

and

\displaystyle \sum_{j=0}^{p-1} |c(j)|^2 = \frac{\omega(p)}{p}

and so after some routine algebra and the Cauchy-Schwarz inequality, we obtain a generalisation of (3):

\displaystyle \sum_{j=1}^{p-1} |\hat f(\xi+j/p)|^2 \geq \frac{\omega(p)}{p-\omega(p)} |\hat f(\xi)|^2.

Thus we see that the more residue classes mod {p} we exclude, the more Fourier energy has to disperse along multiples of {1/p}. It is also instructive to consider the extreme case {\omega(p)=p-1}, in which {f} is supported on just a single residue class {a \mod p}; in this case, one clearly has {\hat f(\xi+j/p) = e(-aj/p) \hat f(\xi)}, and so {\hat f} spreads its energy completely evenly along multiples of {1/p}.

In 1968, Montgomery observed the following useful generalisation of the above calculation to arbitrary modulus:

Proposition 1 (Montgomery’s uncertainty principle) Let {f: {\bf Z} \rightarrow{\bf C}} be a finitely supported function which, for each prime {p}, avoids {\omega(p)} residue classes modulo {p} for some {0 \leq \omega(p) < p}. Then for each natural number {q}, one has

\displaystyle \sum_{1 \leq a \leq q: (a,q)=1} |\hat f(\xi+\frac{a}{q})|^2 \geq h(q) |\hat f(\xi)|^2

where {h(q)} is the quantity

\displaystyle h(q) := \mu(q)^2 \prod_{p|q} \frac{\omega(p)}{p-\omega(p)} \ \ \ \ \ (4)

where {\mu} is the Möbius function.

We give a proof of this proposition below the fold.

Following the “adelic” philosophy, it is natural to combine this uncertainty principle with the large sieve inequality to take simultaneous advantage of localisation both in the Archimedean sense and in the {p}-adic senses. This leads to the following corollary:

Corollary 2 (Arithmetic large sieve inequality) Let {f: {\bf Z} \rightarrow {\bf C}} be a function supported on an interval {[M+1,M+N]} which, for each prime {p}, avoids {\omega(p)} residue classes modulo {p} for some {0 \leq \omega(p) < p}. Let {\xi_1,\ldots,\xi_J \in {\bf R}/{\bf Z}}, and let {{\mathcal Q}} be a finite set of natural numbers. Suppose that the frequencies {\xi_j + \frac{a}{q}} with {1 \leq j \leq J}, {q \in {\mathcal Q}}, and {(a,q)=1} are {\delta}-separated. Then one has

\displaystyle \sum_{j=1}^J |\hat f(\xi_j)|^2 \leq \frac{N + \frac{1}{\delta}}{\sum_{q \in {\mathcal Q}} h(q)} \| f \|_{\ell^2({\bf Z})}^2

where {h(q)} was defined in (4).

Indeed, from the large sieve inequality one has

\displaystyle \sum_{j=1}^J \sum_{q \in {\mathcal Q}} \sum_{1 \leq a \leq q: (a,q)=1} |\hat f(\xi_j+\frac{a}{q})|^2 \leq (N + \frac{1}{\delta}) \| f \|_{\ell^2({\bf Z})}^2

while from Proposition 1 one has

\displaystyle \sum_{q \in {\mathcal Q}} \sum_{1 \leq a \leq q: (a,q)=1} |\hat f(\xi_j+\frac{a}{q})|^2 \geq (\sum_{q \in {\mathcal Q}} h(q)) |\hat f(\xi_j)|^2

whence the claim.

There is a great deal of flexibility in the above inequality, due to the ability to select the set {{\mathcal Q}}, the frequencies {\xi_1,\ldots,\xi_J}, the omitted classes {\omega(p)}, and the separation parameter {\delta}. Here is a typical application concerning the original motivation for the large sieve inequality, namely in bounding the size of sets which avoid many residue classes:

Corollary 3 (Large sieve) Let {A} be a set of integers contained in {[M+1,M+N]} which avoids {\omega(p)} residue classes modulo {p} for each prime {p}, and let {R>0}. Then

\displaystyle |A| \leq \frac{N+R^2}{G(R)}

where

\displaystyle G(R) := \sum_{q \leq R} h(q).

Proof: We apply Corollary 2 with {f = 1_A}, {J=1}, {\delta=1/R^2}, {\xi_1=0}, and {{\mathcal Q} := \{ q: q \leq R\}}. The key point is that the Farey sequence of fractions {a/q} with {q \leq R} and {(a,q)=1} is {1/R^2}-separated, since

\displaystyle \| \frac{a}{q}-\frac{a'}{q'} \|_{{\bf R}/{\bf Z}} \geq \frac{1}{qq'} \geq \frac{1}{R^2}

whenever {a/q, a'/q'} are distinct fractions in this sequence. \Box

If, for instance, {A} is the set of all primes in {[M+1,M+N]} larger than {R}, then one can set {\omega(p)=1} for all {p \leq R}, which makes {h(q) = \frac{\mu^2(q)}{\phi(q)}}, where {\phi} is the Euler totient function. It is a classical estimate that

\displaystyle G(R) = \log R + O(1).

Using this fact and optimising in {R}, we obtain (a special case of) the Brun-Titchmarsh inequality

\displaystyle \pi(M+N)-\pi(M) \leq (2+o_{N \rightarrow \infty}(1)) \frac{N}{\log N}

where {\pi(x)} is the prime counting function; a variant of the same argument gives the more general Brun-Titchmarsh inequality

\displaystyle \pi(M+N;a,q)-\pi(M;a,q) \leq (2+o_{N \rightarrow \infty;q}(1)) \frac{q}{\phi(q)} \frac{N}{\log N}

for any primitive residue class {a \mod q}, where {\pi(M;a,q)} is the number of primes less than or equal to {M} that are congruent to {a \mod q}. By performing a more careful optimisation using a slightly sharper version of the large sieve inequality (2) that exploits the irregular spacing of the Farey sequence, Montgomery and Vaughan were able to delete the error term in the Brun-Titchmarsh inequality, thus establishing the very nice inequality

\displaystyle \pi(M+N;a,q)-\pi(M;a,q) \leq 2 \frac{q}{\phi(q)} \frac{N}{\log N}

for any natural numbers {M,N,a,q} with {N>1}. This is a particularly useful inequality in non-asymptotic analytic number theory (when one wishes to study number theory at explicit orders of magnitude, rather than the number theory of sufficiently large numbers), due to the absence of asymptotic notation.

I recently realised that Corollary 2 also establishes a stronger version of the “restriction theorem for the Selberg sieve” that Ben Green and I proved some years ago (indeed, one can view Corollary 2 as a “restriction theorem for the large sieve”). I’m placing the details below the fold.

— 1. Proof of uncertainty principle —

We now prove Proposition 1. As with the case when {q} is prime, the idea is to work by duality, testing {f} against a suitably chosen test function {\nu} and using the Cauchy-Schwarz inequality.

By replacing {f(n)} with the modulated function {f(n) e(n\xi)}, we may assume without loss of generality that {\xi=0}. We may of course assume that {q} is square-free, and that {\omega(p) > 0} for all {p|q}, since otherwise {h(q)=0} and the claim is vacuously true. Let us abbreviate the summation {\sum_{1 \leq a \leq q: (a,q)=1}} as {\sum_{a}^*}, thus our task is to show that

\displaystyle \sum_{a}^* |\hat f(\frac{a}{q})|^2 \geq |\hat f(0)|^2 h(q). \ \ \ \ \ (5)

For each prime {p} dividing {q}, let {S_p} be the union of the {\omega(p)} residue classes modulo {p} which avoid {A}. It turns out that the optimal choice for {\nu} is the function

\displaystyle \nu(n) := \prod_{p|q} (\omega(p) - p 1_{S_p}).

On the one hand, we see that {\nu(n)} is equal to {\omega(q) := \prod_{p|q} \omega(p)} on the support of {f}, and thus

\displaystyle \sum_{n \in {\bf Z}} \nu(n) f(n) = \omega(q) \hat f(0).

On the other hand, each {\omega(p)-p 1_{S_p}} is mean zero and periodic of period {p}, and thus a linear combination of phases {e(an/p)} with {a} coprime to {p}. Multiplying together, we conclude that

\displaystyle \nu(n) = \sum_{a \in {\bf Z}/q{\bf Z}: (a,q)=1} c(a) e(an/q)

for some coefficients {c(n)}. Taking the inner product against {f}, we conclude that

\displaystyle \sum_{n \in {\bf Z}} \nu(n) f(n) = \sum_{a}^* \overline{c(a)} \hat f(a/q).

By Cauchy-Schwarz, we conclude that

\displaystyle |\sum_{n \in {\bf Z}} \nu(n) f(n)| \leq (\sum_{a}^* |\hat f(a/q)|^2)^{1/2} (\sum_{a}^* |c(a)|^2)^{1/2}.

But by the Plancherel identity we have

\displaystyle \sum_{a}^* |c(a)|^2 = \mathop{\bf E}_{n \in {\bf Z}/q{\bf Z}} \nu(n)^2.

Note that {(\omega(p)-p1_{S_p})^2} has mean {(p-\omega(p)) \omega(p)}, and so

\displaystyle \mathop{\bf E}_{n \in {\bf Z}/q{\bf Z}} \nu(n)^2 = \prod_{p|q} (p-\omega(p)) \omega(p).

Putting everything together, we obtain (5) as required.

Remark 1 The factor of {h(q)} in the uncertainty principle is sharp, as can be seen by computing what happens when {f := \prod_{p|q} (1-1_{S_p})}.

— 2. Restriction theory of the large sieve —

The hypotheses of Corollary 2 are somewhat inconvenient to work with. We can specialise Corollary 2 to a more tractable version:

Theorem 4 (Special case of large sieve inequality) Let {f: {\bf Z} \rightarrow {\bf C}} be a function supported on an interval {[M+1,M+N]} which, for each prime {p}, avoids {\omega(p)} residue classes modulo {p} for some {0 \leq \omega(p) < p}. Let {\xi_1,\ldots,\xi_J \in {\bf R}/{\bf Z}}, and {R := (2\delta)^{-1/4}}. Then one has

\displaystyle \sum_{j=1}^J |\hat f(\xi_j)|^2 \leq (\prod_{p \in {\mathcal P}} (1-\frac{\omega(p)}{p}))^{-1} \frac{N + \frac{1}{\delta}}{G(R)} \| f \|_{\ell^2({\bf Z})}^2, \ \ \ \ \ (6)

where {{\mathcal P}} is a set of at most {\binom{J}{2}} primes.

Proof: Observe that for each {1 \leq i < j \leq J}, there is at most one fraction {\frac{a}{q}} with {q < R^2} such that {\| \xi_i - \xi_j - \frac{a}{q} \|_{{\bf R}/{\bf Z}} \leq \delta}. Indeed, if there were two such fractions {\frac{a}{q}, \frac{a'}{q'}}, then we would have

\displaystyle \| \frac{a}{q} - \frac{a'}{q'} \| \leq 2\delta

by the triangle inequality. On the other hand, the left-hand side is at least {1/qq' > R^{-4}}, contradicting the definition of {R}.

By selecting at most one prime for each of the {\binom{J}{2}} pairs {(i,j)} with {1 \leq i < j \leq J}, we may thus find a natural number {k} that is the product of at most {\binom{J}{2}} primes, and with the property that

\displaystyle \| \xi_i - \xi_j - \frac{a}{q} \| > \delta

whenever {q < R^2}, {1 \leq i < j \leq J}, and {(q,k)=1}. From this (and (2)) we see that

\displaystyle \| (\xi_i + \frac{a}{q}) - (\xi_j + \frac{a'}{q'}) \| > \delta

whenever {1 \leq i,j \leq J} and {q, q' \leq R} with {(q,k) = (q',k)=1}, with either {i \neq j} or {a/q \neq a'/q'}. Applying Corollary 2, we conclude that

\displaystyle \sum_{j=1}^J |\hat f(\xi_j)|^2 \leq \frac{N + \frac{1}{\delta}}{\sum_{q \leq R; (q,k)=1} h(q)} \| f \|_{\ell^2({\bf Z})}^2.

On the other hand, from the multiplicative (and non-negative) nature of {h} we have

\displaystyle (\sum_{q \leq R; (q,k)=1} h(q)) (\sum_{q|k} h(q)) \geq \sum_{q \leq R} h(q) = G(R).

Writing {{\mathcal P}} as the primes dividing {k}, we see that

\displaystyle \sum_{q|k} h(q) = (\prod_{p \in {\mathcal P}} (1-\frac{\omega(p)}{p}))^{-1}.

The claim follows. \Box

Suppose that {\omega(p) \leq k} for all primes {p} and some fixed {k}. Then from Mertens’ theorem, we have

\displaystyle (\prod_{p \in {\mathcal P}} (1-\frac{\omega(p)}{p}))^{-1} \ll_k \log^k |{\mathcal P}| \ll_k 1+\log^k J.

Also, one has the standard sieve theory bound

\displaystyle G(R) \gg_k \frac{1}{{\mathfrak G}} \log^k R

where {{\mathfrak G}} is the singular series

\displaystyle {\mathfrak G} = \prod_{p \leq R} \frac{1-\frac{\omega}{p}}{(1-\frac{1}{p})^k}.

This bound can be established by a variety of techniques (e.g. by estimating the Dirichlet series {\sum_n \frac{h(n)}{n^\epsilon}} for small values of {\epsilon}), and can for instance be found in Lemma 4.1 of this text of Halberstam and Richert. Putting this together, we conclude that

\displaystyle \sum_{j=1}^J |\hat f(\xi_j)|^2 \ll_k {\mathfrak G} (1+\log^k J) \frac{N + \frac{1}{\delta}}{\log^k R} \| f \|_{\ell^2({\bf Z})}^2.

Setting {\delta := 1/N}, we can simplify this a bit to

\displaystyle \sum_{j=1}^J |\hat f(\xi_j)|^2 \ll_k {\mathfrak G} (1+\log^k J) \frac{N}{\log^k N} \| f \|_{\ell^2({\bf Z})}^2.

Note the very slow growth in {J}. It is not difficult to use this bound to obtain the {\ell^p} variant

\displaystyle (\sum_{j=1}^J |\hat f(\xi_j)|^p)^{1/p} \ll_{k,p} {\mathfrak G}^{1/2} (\frac{N}{\log^k N})^{1/2} \| f \|_{\ell^2({\bf Z})}

for any {2 < p \leq \infty} and any {1/N}-separated {\xi_1,\ldots,\xi_J}. Averaging, we obtain a restriction theorem

\displaystyle \| \hat f \|_{L^p({\bf R}/{\bf Z})} \ll_{k,p} {\mathfrak G}^{1/2} \frac{N^{1/2-1/p}}{\log^{k/2} N} \| f \|_{\ell^2({\bf Z})}

which is essentially Proposition 4.2 of my paper with Ben Green (but with the Selberg sieve replaced by the large sieve). As such, it can be used to deduce many of the other results in that paper. For instance, one has the following strengthening of Theorem 1.1 in that paper: if {A} is a subset of {[M+1,M+N]} that avoids {\omega(p)} residue classes mod {p} for each {p} and some {0 \leq \omega(p) \leq k}, then

\displaystyle \| \hat 1_A \|_{L^p({\bf R}/{\bf Z})} \ll_{k,p} {\mathfrak G} N^{1-1/p} \log^{-k} N

for all {2 < p \leq \infty}. If {|A| \geq \delta N / \log^k N} for some {\delta>0}, and {N} is sufficiently large depending on {\delta,k,{\mathfrak G}}, one can then show that {A} contains arithmetic progressions of length three by repeating the arguments in Section 6 of that paper; among other things, this reproves our result that there are infinitely many progressions of length three among the Chen primes (which arises from the two-dimensional case {k=2} of the above assertion).