You are currently browsing the category archive for the ‘expository’ category.

The Poincaré upper half-plane ${{\mathbf H} := \{ z: \hbox{Im}(z) > 0 \}}$ (with a boundary consisting of the real line ${{\bf R}}$ together with the point at infinity ${\infty}$) carries an action of the projective special linear group

$\displaystyle \hbox{PSL}_2({\bf R}) := \{ \begin{pmatrix} a & b \\ c & d \end{pmatrix}: a,b,c,d \in {\bf R}: ad-bc = 1 \} / \{\pm 1\}$

via fractional linear transformations:

$\displaystyle \begin{pmatrix} a & b \\ c & d \end{pmatrix} z := \frac{az+b}{cz+d}. \ \ \ \ \ (1)$

Here and in the rest of the post we will abuse notation by identifying elements ${\begin{pmatrix} a & b \\ c & d \end{pmatrix}}$ of the special linear group ${\hbox{SL}_2({\bf R})}$ with their equivalence class ${\{ \pm \begin{pmatrix} a & b \\ c & d \end{pmatrix} \}}$ in ${\hbox{PSL}_2({\bf R})}$; this will occasionally create or remove a factor of two in our formulae, but otherwise has very little effect, though one has to check that various definitions and expressions (such as (1)) are unaffected if one replaces a matrix ${\begin{pmatrix} a & b \\ c & d \end{pmatrix}}$ by its negation ${\begin{pmatrix} -a & -b \\ -c & -d \end{pmatrix}}$. In particular, we recommend that the reader ignore the signs ${\pm}$ that appear from time to time in the discussion below.

As the action of ${\hbox{PSL}_2({\bf R})}$ on ${{\mathbf H}}$ is transitive, and any given point in ${{\mathbf H}}$ (e.g. ${i}$) has a stabiliser isomorphic to the projective rotation group ${\hbox{PSO}_2({\bf R})}$, we can view the Poincaré upper half-plane ${{\mathbf H}}$ as a homogeneous space for ${\hbox{PSL}_2({\bf R})}$, and more specifically the quotient space of ${\hbox{PSL}_2({\bf R})}$ of a maximal compact subgroup ${\hbox{PSO}_2({\bf R})}$. In fact, we can make the half-plane a symmetric space for ${\hbox{PSL}_2({\bf R})}$, by endowing ${{\mathbf H}}$ with the Riemannian metric

$\displaystyle dg^2 := \frac{dx^2 + dy^2}{y^2}$

(using Cartesian coordinates ${z=x+iy}$), which is invariant with respect to the ${\hbox{PSL}_2({\bf R})}$ action. Like any other Riemannian metric, the metric on ${{\mathbf H}}$ generates a number of other important geometric objects on ${{\mathbf H}}$, such as the distance function ${d(z,w)}$ which can be computed to be given by the formula

$\displaystyle 2(\cosh(d(z_1,z_2))-1) = \frac{|z_1-z_2|^2}{\hbox{Im}(z_1) \hbox{Im}(z_2)}, \ \ \ \ \ (2)$

the volume measure ${\mu = \mu_{\mathbf H}}$, which can be computed to be

$\displaystyle d\mu = \frac{dx dy}{y^2},$

and the Laplace-Beltrami operator, which can be computed to be ${\Delta = y^2 (\frac{\partial^2}{\partial x^2} + \frac{\partial^2}{\partial y^2})}$ (here we use the negative definite sign convention for ${\Delta}$). As the metric ${dg}$ was ${\hbox{PSL}_2({\bf R})}$-invariant, all of these quantities arising from the metric are similarly ${\hbox{PSL}_2({\bf R})}$-invariant in the appropriate sense.

The Gauss curvature of the Poincaré half-plane can be computed to be the constant ${-1}$, thus ${{\mathbf H}}$ is a model for two-dimensional hyperbolic geometry, in much the same way that the unit sphere ${S^2}$ in ${{\bf R}^3}$ is a model for two-dimensional spherical geometry (or ${{\bf R}^2}$ is a model for two-dimensional Euclidean geometry). (Indeed, ${{\mathbf H}}$ is isomorphic (via projection to a null hyperplane) to the upper unit hyperboloid ${\{ (x,t) \in {\bf R}^{2+1}: t = \sqrt{1+|x|^2}\}}$ in the Minkowski spacetime ${{\bf R}^{2+1}}$, which is the direct analogue of the unit sphere in Euclidean spacetime ${{\bf R}^3}$ or the plane ${{\bf R}^2}$ in Galilean spacetime ${{\bf R}^2 \times {\bf R}}$.)

One can inject arithmetic into this geometric structure by passing from the Lie group ${\hbox{PSL}_2({\bf R})}$ to the full modular group

$\displaystyle \hbox{PSL}_2({\bf Z}) := \{ \begin{pmatrix} a & b \\ c & d \end{pmatrix}: a,b,c,d \in {\bf Z}: ad-bc = 1 \} / \{\pm 1\}$

or congruence subgroups such as

$\displaystyle \Gamma_0(q) := \{ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \in \hbox{PSL}_2({\bf Z}): c = 0\ (q) \} / \{ \pm 1 \} \ \ \ \ \ (3)$

for natural number ${q}$, or to the discrete stabiliser ${\Gamma_\infty}$ of the point at infinity:

$\displaystyle \Gamma_\infty := \{ \pm \begin{pmatrix} 1 & b \\ 0 & 1 \end{pmatrix}: b \in {\bf Z} \} / \{\pm 1\}. \ \ \ \ \ (4)$

These are discrete subgroups of ${\hbox{PSL}_2({\bf R})}$, nested by the subgroup inclusions

$\displaystyle \Gamma_\infty \leq \Gamma_0(q) \leq \Gamma_0(1)=\hbox{PSL}_2({\bf Z}) \leq \hbox{PSL}_2({\bf R}).$

There are many further discrete subgroups of ${\hbox{PSL}_2({\bf R})}$ (known collectively as Fuchsian groups) that one could consider, but we will focus attention on these three groups in this post.

Any discrete subgroup ${\Gamma}$ of ${\hbox{PSL}_2({\bf R})}$ generates a quotient space ${\Gamma \backslash {\mathbf H}}$, which in general will be a non-compact two-dimensional orbifold. One can understand such a quotient space by working with a fundamental domain ${\hbox{Fund}( \Gamma \backslash {\mathbf H})}$ – a set consisting of a single representative of each of the orbits ${\Gamma z}$ of ${\Gamma}$ in ${{\mathbf H}}$. This fundamental domain is by no means uniquely defined, but if the fundamental domain is chosen with some reasonable amount of regularity, one can view ${\Gamma \backslash {\mathbf H}}$ as the fundamental domain with the boundaries glued together in an appropriate sense. Among other things, fundamental domains can be used to induce a volume measure ${\mu = \mu_{\Gamma \backslash {\mathbf H}}}$ on ${\Gamma \backslash {\mathbf H}}$ from the volume measure ${\mu = \mu_{\mathbf H}}$ on ${{\mathbf H}}$ (restricted to a fundamental domain). By abuse of notation we will refer to both measures simply as ${\mu}$ when there is no chance of confusion.

For instance, a fundamental domain for ${\Gamma_\infty \backslash {\mathbf H}}$ is given (up to null sets) by the strip ${\{ z \in {\mathbf H}: |\hbox{Re}(z)| < \frac{1}{2} \}}$, with ${\Gamma_\infty \backslash {\mathbf H}}$ identifiable with the cylinder formed by gluing together the two sides of the strip. A fundamental domain for ${\hbox{PSL}_2({\bf Z}) \backslash {\mathbf H}}$ is famously given (again up to null sets) by an upper portion ${\{ z \in {\mathbf H}: |\hbox{Re}(z)| < \frac{1}{2}; |z| > 1 \}}$, with the left and right sides again glued to each other, and the left and right halves of the circular boundary glued to itself. A fundamental domain for ${\Gamma_0(q) \backslash {\mathbf H}}$ can be formed by gluing together

$\displaystyle [\hbox{PSL}_2({\bf Z}) : \Gamma_0(q)] = q \prod_{p|q} (1 + \frac{1}{p}) = q^{1+o(1)}$

copies of a fundamental domain for ${\hbox{PSL}_2({\bf Z}) \backslash {\mathbf H}}$ in a rather complicated but interesting fashion.

While fundamental domains can be a convenient choice of coordinates to work with for some computations (as well as for drawing appropriate pictures), it is geometrically more natural to avoid working explicitly on such domains, and instead work directly on the quotient spaces ${\Gamma \backslash {\mathbf H}}$. In order to analyse functions ${f: \Gamma \backslash {\mathbf H} \rightarrow {\bf C}}$ on such orbifolds, it is convenient to lift such functions back up to ${{\mathbf H}}$ and identify them with functions ${f: {\mathbf H} \rightarrow {\bf C}}$ which are ${\Gamma}$-automorphic in the sense that ${f( \gamma z ) = f(z)}$ for all ${z \in {\mathbf H}}$ and ${\gamma \in \Gamma}$. Such functions will be referred to as ${\Gamma}$-automorphic forms, or automorphic forms for short (we always implicitly assume all such functions to be measurable). (Strictly speaking, these are the automorphic forms with trivial factor of automorphy; one can certainly consider other factors of automorphy, particularly when working with holomorphic modular forms, which corresponds to sections of a more non-trivial line bundle over ${\Gamma \backslash {\mathbf H}}$ than the trivial bundle ${(\Gamma \backslash {\mathbf H}) \times {\bf C}}$ that is implicitly present when analysing scalar functions ${f: {\mathbf H} \rightarrow {\bf C}}$. However, we will not discuss this (important) more general situation here.)

An important way to create a ${\Gamma}$-automorphic form is to start with a non-automorphic function ${f: {\mathbf H} \rightarrow {\bf C}}$ obeying suitable decay conditions (e.g. bounded with compact support will suffice) and form the Poincaré series ${P_\Gamma[f]: {\mathbf H} \rightarrow {\bf C}}$ defined by

$\displaystyle P_{\Gamma}[f](z) = \sum_{\gamma \in \Gamma} f(\gamma z),$

which is clearly ${\Gamma}$-automorphic. (One could equivalently write ${f(\gamma^{-1} z)}$ in place of ${f(\gamma z)}$ here; there are good argument for both conventions, but I have ultimately decided to use the ${f(\gamma z)}$ convention, which makes explicit computations a little neater at the cost of making the group actions work in the opposite order.) Thus we naturally see sums over ${\Gamma}$ associated with ${\Gamma}$-automorphic forms. A little more generally, given a subgroup ${\Gamma_\infty}$ of ${\Gamma}$ and a ${\Gamma_\infty}$-automorphic function ${f: {\mathbf H} \rightarrow {\bf C}}$ of suitable decay, we can form a relative Poincaré series ${P_{\Gamma_\infty \backslash \Gamma}[f]: {\mathbf H} \rightarrow {\bf C}}$ by

$\displaystyle P_{\Gamma_\infty \backslash \Gamma}[f](z) = \sum_{\gamma \in \hbox{Fund}(\Gamma_\infty \backslash \Gamma)} f(\gamma z)$

where ${\hbox{Fund}(\Gamma_\infty \backslash \Gamma)}$ is any fundamental domain for ${\Gamma_\infty \backslash \Gamma}$, that is to say a subset of ${\Gamma}$ consisting of exactly one representative for each right coset of ${\Gamma_\infty}$. As ${f}$ is ${\Gamma_\infty}$-automorphic, we see (if ${f}$ has suitable decay) that ${P_{\Gamma_\infty \backslash \Gamma}[f]}$ does not depend on the precise choice of fundamental domain, and is ${\Gamma}$-automorphic. These operations are all compatible with each other, for instance ${P_\Gamma = P_{\Gamma_\infty \backslash \Gamma} \circ P_{\Gamma_\infty}}$. A key example of Poincaré series are the Eisenstein series, although there are of course many other Poincaré series one can consider by varying the test function ${f}$.

For future reference we record the basic but fundamental unfolding identities

$\displaystyle \int_{\Gamma \backslash {\mathbf H}} P_\Gamma[f] g\ d\mu_{\Gamma \backslash {\mathbf H}} = \int_{\mathbf H} f g\ d\mu_{\mathbf H} \ \ \ \ \ (5)$

for any function ${f: {\mathbf H} \rightarrow {\bf C}}$ with sufficient decay, and any ${\Gamma}$-automorphic function ${g}$ of reasonable growth (e.g. ${f}$ bounded and compact support, and ${g}$ bounded, will suffice). Note that ${g}$ is viewed as a function on ${\Gamma \backslash {\mathbf H}}$ on the left-hand side, and as a ${\Gamma}$-automorphic function on ${{\mathbf H}}$ on the right-hand side. More generally, one has

$\displaystyle \int_{\Gamma \backslash {\mathbf H}} P_{\Gamma_\infty \backslash \Gamma}[f] g\ d\mu_{\Gamma \backslash {\mathbf H}} = \int_{\Gamma_\infty \backslash {\mathbf H}} f g\ d\mu_{\Gamma_\infty \backslash {\mathbf H}} \ \ \ \ \ (6)$

whenever ${\Gamma_\infty \leq \Gamma}$ are discrete subgroups of ${\hbox{PSL}_2({\bf R})}$, ${f}$ is a ${\Gamma_\infty}$-automorphic function with sufficient decay on ${\Gamma_\infty \backslash {\mathbf H}}$, and ${g}$ is a ${\Gamma}$-automorphic (and thus also ${\Gamma_\infty}$-automorphic) function of reasonable growth. These identities will allow us to move fairly freely between the three domains ${{\mathbf H}}$, ${\Gamma_\infty \backslash {\mathbf H}}$, and ${\Gamma \backslash {\mathbf H}}$ in our analysis.

When computing various statistics of a Poincaré series ${P_\Gamma[f]}$, such as its values ${P_\Gamma[f](z)}$ at special points ${z}$, or the ${L^2}$ quantity ${\int_{\Gamma \backslash {\mathbf H}} |P_\Gamma[f]|^2\ d\mu}$, expressions of interest to analytic number theory naturally emerge. We list three basic examples of this below, discussed somewhat informally in order to highlight the main ideas rather than the technical details.

The first example we will give concerns the problem of estimating the sum

$\displaystyle \sum_{n \leq x} \tau(n) \tau(n+1), \ \ \ \ \ (7)$

where ${\tau(n) := \sum_{d|n} 1}$ is the divisor function. This can be rewritten (by factoring ${n=bc}$ and ${n+1=ad}$) as

$\displaystyle \sum_{ a,b,c,d \in {\bf N}: ad-bc = 1} 1_{bc \leq x} \ \ \ \ \ (8)$

which is basically a sum over the full modular group ${\hbox{PSL}_2({\bf Z})}$. At this point we will “cheat” a little by moving to the related, but different, sum

$\displaystyle \sum_{a,b,c,d \in {\bf Z}: ad-bc = 1} 1_{a^2+b^2+c^2+d^2 \leq x}. \ \ \ \ \ (9)$

This sum is not exactly the same as (8), but will be a little easier to handle, and it is plausible that the methods used to handle this sum can be modified to handle (8). Observe from (2) and some calculation that the distance between ${i}$ and ${\begin{pmatrix} a & b \\ c & d \end{pmatrix} i = \frac{ai+b}{ci+d}}$ is given by the formula

$\displaystyle 2(\cosh(d(i,\begin{pmatrix} a & b \\ c & d \end{pmatrix} i))-1) = a^2+b^2+c^2+d^2 - 2$

and so one can express the above sum as

$\displaystyle 2 \sum_{\gamma \in \hbox{PSL}_2({\bf Z})} 1_{d(i,\gamma i) \leq \hbox{cosh}^{-1}(x/2)}$

(the factor of ${2}$ coming from the quotient by ${\{\pm 1\}}$ in the projective special linear group); one can express this as ${P_\Gamma[f](i)}$, where ${\Gamma = \hbox{PSL}_2({\bf Z})}$ and ${f}$ is the indicator function of the ball ${B(i, \hbox{cosh}^{-1}(x/2))}$. Thus we see that expressions such as (7) are related to evaluations of Poincaré series. (In practice, it is much better to use smoothed out versions of indicator functions in order to obtain good control on sums such as (7) or (9), but we gloss over this technical detail here.)

The second example concerns the relative

$\displaystyle \sum_{n \leq x} \tau(n^2+1) \ \ \ \ \ (10)$

of the sum (7). Note from multiplicativity that (7) can be written as ${\sum_{n \leq x} \tau(n^2+n)}$, which is superficially very similar to (10), but with the key difference that the polynomial ${n^2+1}$ is irreducible over the integers.

As with (7), we may expand (10) as

$\displaystyle \sum_{A,B,C \in {\bf N}: B^2 - AC = -1} 1_{B \leq x}.$

At first glance this does not look like a sum over a modular group, but one can manipulate this expression into such a form in one of two (closely related) ways. First, observe that any factorisation ${B + i = (a-bi) (c+di)}$ of ${B+i}$ into Gaussian integers ${a-bi, c+di}$ gives rise (upon taking norms) to an identity of the form ${B^2 - AC = -1}$, where ${A = a^2+b^2}$ and ${C = c^2+d^2}$. Conversely, by using the unique factorisation of the Gaussian integers, every identity of the form ${B^2-AC=-1}$ gives rise to a factorisation of the form ${B+i = (a-bi) (c+di)}$, essentially uniquely up to units. Now note that ${(a-bi)(c+di)}$ is of the form ${B+i}$ if and only if ${ad-bc=1}$, in which case ${B = ac+bd}$. Thus we can essentially write the above sum as something like

$\displaystyle \sum_{a,b,c,d: ad-bc = 1} 1_{|ac+bd| \leq x} \ \ \ \ \ (11)$

and one the modular group ${\hbox{PSL}_2({\bf Z})}$ is now manifest. An equivalent way to see these manipulations is as follows. A triple ${A,B,C}$ of natural numbers with ${B^2-AC=1}$ gives rise to a positive quadratic form ${Ax^2+2Bxy+Cy^2}$ of normalised discriminant ${B^2-AC}$ equal to ${-1}$ with integer coefficients (it is natural here to allow ${B}$ to take integer values rather than just natural number values by essentially doubling the sum). The group ${\hbox{PSL}_2({\bf Z})}$ acts on the space of such quadratic forms in a natural fashion (by composing the quadratic form with the inverse ${\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}}$ of an element ${\begin{pmatrix} a & b \\ c & d \end{pmatrix}}$ of ${\hbox{SL}_2({\bf Z})}$). Because the discriminant ${-1}$ has class number one (this fact is equivalent to the unique factorisation of the gaussian integers, as discussed in this previous post), every form ${Ax^2 + 2Bxy + Cy^2}$ in this space is equivalent (under the action of some element of ${\hbox{PSL}_2({\bf Z})}$) with the standard quadratic form ${x^2+y^2}$. In other words, one has

$\displaystyle Ax^2 + 2Bxy + Cy^2 = (dx-by)^2 + (-cx+ay)^2$

which (up to a harmless sign) is exactly the representation ${B = ac+bd}$, ${A = c^2+d^2}$, ${C = a^2+b^2}$ introduced earlier, and leads to the same reformulation of the sum (10) in terms of expressions like (11). Similar considerations also apply if the quadratic polynomial ${n^2+1}$ is replaced by another quadratic, although one has to account for the fact that the class number may now exceed one (so that unique factorisation in the associated quadratic ring of integers breaks down), and in the positive discriminant case the fact that the group of units might be infinite presents another significant technical problem.

Note that ${\begin{pmatrix} a & b \\ c & d \end{pmatrix} i = \frac{ai+b}{ci+d}}$ has real part ${\frac{ac+bd}{c^2+d^2}}$ and imaginary part ${\frac{1}{c^2+d^2}}$. Thus (11) is (up to a factor of two) the Poincaré series ${P_\Gamma[f](i)}$ as in the preceding example, except that ${f}$ is now the indicator of the sector ${\{ z: |\hbox{Re} z| \leq x |\hbox{Im} z| \}}$.

Sums involving subgroups of the full modular group, such as ${\Gamma_0(q)}$, often arise when imposing congruence conditions on sums such as (10), for instance when trying to estimate the expression ${\sum_{n \leq x: q|n} \tau(n^2+1)}$ when ${q}$ and ${x}$ are large. As before, one then soon arrives at the problem of evaluating a Poincaré series at one or more special points, where the series is now over ${\Gamma_0(q)}$ rather than ${\hbox{PSL}_2({\bf Z})}$.

The third and final example concerns averages of Kloosterman sums

$\displaystyle S(m,n;c) := \sum_{x \in ({\bf Z}/c{\bf Z})^\times} e( \frac{mx + n\overline{x}}{c} ) \ \ \ \ \ (12)$

where ${e(\theta) := e^{2p\i i\theta}}$ and ${\overline{x}}$ is the inverse of ${x}$ in the multiplicative group ${({\bf Z}/c{\bf Z})^\times}$. It turns out that the ${L^2}$ norms of Poincaré series ${P_\Gamma[f]}$ or ${P_{\Gamma_\infty \backslash \Gamma}[f]}$ are closely tied to such averages. Consider for instance the quantity

$\displaystyle \int_{\Gamma_0(q) \backslash {\mathbf H}} |P_{\Gamma_\infty \backslash \Gamma_0(q)}[f]|^2\ d\mu_{\Gamma \backslash {\mathbf H}} \ \ \ \ \ (13)$

where ${q}$ is a natural number and ${f}$ is a ${\Gamma_\infty}$-automorphic form that is of the form

$\displaystyle f(x+iy) = F(my) e(m x)$

for some integer ${m}$ and some test function ${f: (0,+\infty) \rightarrow {\bf C}}$, which for sake of discussion we will take to be smooth and compactly supported. Using the unfolding formula (6), we may rewrite (13) as

$\displaystyle \int_{\Gamma_\infty \backslash {\mathbf H}} \overline{f} P_{\Gamma_\infty \backslash \Gamma_0(q)}[f]\ d\mu_{\Gamma_\infty \backslash {\mathbf H}}.$

To compute this, we use the double coset decomposition

$\displaystyle \Gamma_0(q) = \Gamma_\infty \cup \bigcup_{c \in {\mathbf N}: q|c} \bigcup_{1 \leq d \leq c: (d,c)=1} \Gamma_\infty \begin{pmatrix} a & b \\ c & d \end{pmatrix} \Gamma_\infty,$

where for each ${c,d}$, ${a,b}$ are arbitrarily chosen integers such that ${ad-bc=1}$. To see this decomposition, observe that every element ${\begin{pmatrix} a & b \\ c & d \end{pmatrix}}$ in ${\Gamma_0(q)}$ outside of ${\Gamma_\infty}$ can be assumed to have ${c>0}$ by applying a sign ${\pm}$, and then using the row and column operations coming from left and right multiplication by ${\Gamma_\infty}$ (that is, shifting the top row by an integer multiple of the bottom row, and shifting the right column by an integer multiple of the left column) one can place ${d}$ in the interval ${[1,c]}$ and ${(a,b)}$ to be any specified integer pair with ${ad-bc=1}$. From this we see that

$\displaystyle P_{\Gamma_\infty \backslash \Gamma_0(q)}[f] = f + \sum_{c \in {\mathbf N}: q|c} \sum_{1 \leq d \leq c: (d,c)=1} P_{\Gamma_\infty}[ f( \begin{pmatrix} a & b \\ c & d \end{pmatrix} \cdot ) ]$

and so from further use of the unfolding formula (5) we may expand (13) as

$\displaystyle \int_{\Gamma_\infty \backslash {\mathbf H}} |f|^2\ d\mu_{\Gamma_\infty \backslash {\mathbf H}}$

$\displaystyle + \sum_{c \in {\mathbf N}} \sum_{1 \leq d \leq c: (d,c)=1} \int_{\mathbf H} \overline{f}(z) f( \begin{pmatrix} a & b \\ c & d \end{pmatrix} z)\ d\mu_{\mathbf H}.$

The first integral is just ${m \int_0^\infty |F(y)|^2 \frac{dy}{y^2}}$. The second expression is more interesting. We have

$\displaystyle \begin{pmatrix} a & b \\ c & d \end{pmatrix} z = \frac{az+b}{cz+d} = \frac{a}{c} - \frac{1}{c(cz+d)}$

$\displaystyle = \frac{a}{c} - \frac{cx+d}{c((cx+d)^2+c^2y^2)} + \frac{iy}{(cx+d)^2 + c^2y^2}$

so we can write

$\displaystyle \int_{\mathbf H} \overline{f}(z) f( \begin{pmatrix} a & b \\ c & d \end{pmatrix} z)\ d\mu_{\mathbf H}$

as

$\displaystyle \int_0^\infty \int_{\bf R} \overline{F}(my) F(\frac{imy}{(cx+d)^2 + c^2y^2}) e( -mx + \frac{ma}{c} - m \frac{cx+d}{c((cx+d)^2+c^2y^2)} )$

$\displaystyle \frac{dx dy}{y^2}$

which on shifting ${x}$ by ${d/c}$ simplifies a little to

$\displaystyle e( \frac{ma}{c} + \frac{md}{c} ) \int_0^\infty \int_{\bf R} F(my) \bar{F}(\frac{imy}{c^2(x^2 + y^2)}) e(- mx - m \frac{x}{c^2(x^2+y^2)} )$

$\displaystyle \frac{dx dy}{y^2}$

and then on scaling ${x,y}$ by ${m}$ simplifies a little further to

$\displaystyle e( \frac{ma}{c} + \frac{md}{c} ) \int_0^\infty \int_{\bf R} F(y) \bar{F}(\frac{m^2}{c^2} \frac{iy}{x^2 + y^2}) e(- x - \frac{m^2}{c^2} \frac{x}{x^2+y^2} )\ \frac{dx dy}{y^2}.$

Note that as ${ad-bc=1}$, we have ${a = \overline{d}}$ modulo ${c}$. Comparing the above calculations with (12), we can thus write (13) as

$\displaystyle m (\int_0^\infty |F(y)|^2 \frac{dy}{y^2} + \sum_{q|c} \frac{S(m,m;c)}{c} V(\frac{m}{c})) \ \ \ \ \ (14)$

where

$\displaystyle V(u) := \frac{1}{u} \int_0^\infty \int_{\bf R} F(y) \bar{F}(u^2 \frac{y}{x^2 + y^2}) e(- x - u^2 \frac{x}{x^2+y^2} )\ \frac{dx dy}{y^2}$

is a certain integral involving ${F}$ and a parameter ${u}$, but which does not depend explicitly on parameters such as ${m,c,d}$. Thus we have indeed expressed the ${L^2}$ expression (13) in terms of Kloosterman sums. It is possible to invert this analysis and express varius weighted sums of Kloosterman sums in terms of ${L^2}$ expressions (possibly involving inner products instead of norms) of Poincaré series, but we will not do so here; see Chapter 16 of Iwaniec and Kowalski for further details.

Traditionally, automorphic forms have been analysed using the spectral theory of the Laplace-Beltrami operator ${-\Delta}$ on spaces such as ${\Gamma\backslash {\mathbf H}}$ or ${\Gamma_\infty \backslash {\mathbf H}}$, so that a Poincaré series such as ${P_\Gamma[f]}$ might be expanded out using inner products of ${P_\Gamma[f]}$ (or, by the unfolding identities, ${f}$) with various generalised eigenfunctions of ${-\Delta}$ (such as cuspidal eigenforms, or Eisenstein series). With this approach, special functions, and specifically the modified Bessel functions ${K_{it}}$ of the second kind, play a prominent role, basically because the ${\Gamma_\infty}$-automorphic functions

$\displaystyle x+iy \mapsto y^{1/2} K_{it}(2\pi |m| y) e(mx)$

for ${t \in {\bf R}}$ and ${m \in {\bf Z}}$ non-zero are generalised eigenfunctions of ${-\Delta}$ (with eigenvalue ${\frac{1}{4}+t^2}$), and are almost square-integrable on ${\Gamma_\infty \backslash {\mathbf H}}$ (the ${L^2}$ norm diverges only logarithmically at one end ${y \rightarrow 0^+}$ of the cylinder ${\Gamma_\infty \backslash {\mathbf H}}$, while decaying exponentially fast at the other end ${y \rightarrow +\infty}$).

However, as discussed in this previous post, the spectral theory of an essentially self-adjoint operator such as ${-\Delta}$ is basically equivalent to the theory of various solution operators associated to partial differential equations involving that operator, such as the Helmholtz equation ${(-\Delta + k^2) u = f}$, the heat equation ${\partial_t u = \Delta u}$, the Schrödinger equation ${i\partial_t u + \Delta u = 0}$, or the wave equation ${\partial_{tt} u = \Delta u}$. Thus, one can hope to rephrase many arguments that involve spectral data of ${-\Delta}$ into arguments that instead involve resolvents ${(-\Delta + k^2)^{-1}}$, heat kernels ${e^{t\Delta}}$, Schrödinger propagators ${e^{it\Delta}}$, or wave propagators ${e^{\pm it\sqrt{-\Delta}}}$, or involve the PDE more directly (e.g. applying integration by parts and energy methods to solutions of such PDE). This is certainly done to some extent in the existing literature; resolvents and heat kernels, for instance, are often utilised. In this post, I would like to explore the possibility of reformulating spectral arguments instead using the inhomogeneous wave equation

$\displaystyle \partial_{tt} u - \Delta u = F.$

Actually it will be a bit more convenient to normalise the Laplacian by ${\frac{1}{4}}$, and look instead at the automorphic wave equation

$\displaystyle \partial_{tt} u + (-\Delta - \frac{1}{4}) u = F. \ \ \ \ \ (15)$

This equation somewhat resembles a “Klein-Gordon” type equation, except that the mass is imaginary! This would lead to pathological behaviour were it not for the negative curvature, which in principle creates a spectral gap of ${\frac{1}{4}}$ that cancels out this factor.

The point is that the wave equation approach gives access to some nice PDE techniques, such as energy methods, Sobolev inequalities and finite speed of propagation, which are somewhat submerged in the spectral framework. The wave equation also interacts well with Poincaré series; if for instance ${u}$ and ${F}$ are ${\Gamma_\infty}$-automorphic solutions to (15) obeying suitable decay conditions, then their Poincaré series ${P_{\Gamma_\infty \backslash \Gamma}[u]}$ and ${P_{\Gamma_\infty \backslash \Gamma}[F]}$ will be ${\Gamma}$-automorphic solutions to the same equation (15), basically because the Laplace-Beltrami operator commutes with translations. Because of these facts, it is possible to replicate several standard spectral theory arguments in the wave equation framework, without having to deal directly with things like the asymptotics of modified Bessel functions. The wave equation approach to automorphic theory was introduced by Faddeev and Pavlov (using the Lax-Phillips scattering theory), and developed further by by Lax and Phillips, to recover many spectral facts about the Laplacian on modular curves, such as the Weyl law and the Selberg trace formula. Here, I will illustrate this by deriving three basic applications of automorphic methods in a wave equation framework, namely

• Using the Weil bound on Kloosterman sums to derive Selberg’s 3/16 theorem on the least non-trivial eigenvalue for ${-\Delta}$ on ${\Gamma_0(q) \backslash {\mathbf H}}$ (discussed previously here);
• Conversely, showing that Selberg’s eigenvalue conjecture (improving Selberg’s ${3/16}$ bound to the optimal ${1/4}$) implies an optimal bound on (smoothed) sums of Kloosterman sums; and
• Using the same bound to obtain pointwise bounds on Poincaré series similar to the ones discussed above. (Actually, the argument here does not use the wave equation, instead it just uses the Sobolev inequality.)

This post originated from an attempt to finally learn this part of analytic number theory properly, and to see if I could use a PDE-based perspective to understand it better. Ultimately, this is not that dramatic a depature from the standard approach to this subject, but I found it useful to think of things in this fashion, probably due to my existing background in PDE.

I thank Bill Duke and Ben Green for helpful discussions. My primary reference for this theory was Chapters 15, 16, and 21 of Iwaniec and Kowalski.

The equidistribution theorem asserts that if ${\alpha \in {\bf R}/{\bf Z}}$ is an irrational phase, then the sequence ${(n\alpha)_{n=1}^\infty}$ is equidistributed on the unit circle, or equivalently that

$\displaystyle \frac{1}{N} \sum_{n=1}^N F(n\alpha) \rightarrow \int_{{\bf R}/{\bf Z}} F(x)\ dx$

for any continuous (or equivalently, for any smooth) function ${F: {\bf R}/{\bf Z} \rightarrow {\bf C}}$. By approximating ${F}$ uniformly by a Fourier series, this claim is equivalent to that of showing that

$\displaystyle \frac{1}{N} \sum_{n=1}^N e(hn\alpha) \rightarrow 0$

for any non-zero integer ${h}$ (where ${e(x) := e^{2\pi i x}}$), which is easily verified from the irrationality of ${\alpha}$ and the geometric series formula. Conversely, if ${\alpha}$ is rational, then clearly ${\frac{1}{N} \sum_{n=1}^N e(hn\alpha)}$ fails to go to zero when ${h}$ is a multiple of the denominator of ${\alpha}$.

One can then ask for more quantitative information about the decay of exponential sums of ${\frac{1}{N} \sum_{n=1}^N e(n \alpha)}$, or more generally on exponential sums of the form ${\frac{1}{|Q|} \sum_{n \in Q} e(P(n))}$ for an arithmetic progression ${Q}$ (in this post all progressions are understood to be finite) and a polynomial ${P: Q \rightarrow \/{\bf Z}}$. It will be convenient to phrase such information in the form of an inverse theorem, describing those phases for which the exponential sum is large. Indeed, we have

Lemma 1 (Geometric series formula, inverse form) Let ${Q \subset {\bf Z}}$ be an arithmetic progression of length at most ${N}$ for some ${N \geq 1}$, and let ${P(n) = n \alpha + \beta}$ be a linear polynomial for some ${\alpha,\beta \in {\bf R}/{\bf Z}}$. If

$\displaystyle \frac{1}{N} |\sum_{n \in Q} e(P(n))| \geq \delta$

for some ${\delta > 0}$, then there exists a subprogression ${Q'}$ of ${Q}$ of size ${|Q'| \gg \delta^2 N}$ such that ${P(n)}$ varies by at most ${\delta}$ on ${Q'}$ (that is to say, ${P(n)}$ lies in a subinterval of ${{\bf R}/{\bf Z}}$ of length at most ${\delta}$).

Proof: By a linear change of variable we may assume that ${Q}$ is of the form ${\{0,\dots,N'-1\}}$ for some ${N' \geq 1}$. We may of course assume that ${\alpha}$ is non-zero in ${{\bf R}/{\bf Z}}$, so that ${\|\alpha\|_{{\bf R}/{\bf Z}} > 0}$ (${\|x\|_{{\bf R}/{\bf Z}}}$ denotes the distance from ${x}$ to the nearest integer). From the geometric series formula we see that

$\displaystyle |\sum_{n \in Q} e(P(n))| \leq \frac{2}{|e(\alpha) - 1|} \ll \frac{1}{\|\alpha\|_{{\bf R}/{\bf Z}}},$

and so ${\|\alpha\|_{{\bf R}/{\bf Z}} \ll \frac{1}{\delta N}}$. Setting ${Q' := \{ n \in Q: n \leq c \delta^2 N \}}$ for some sufficiently small absolute constant ${c}$, we obtain the claim. $\Box$

Thus, in order for a linear phase ${P(n)}$ to fail to be equidistributed on some long progression ${Q}$, ${P}$ must in fact be almost constant on large piece of ${Q}$.

As is well known, this phenomenon generalises to higher order polynomials. To achieve this, we need two elementary additional lemmas. The first relates the exponential sums of ${P}$ to the exponential sums of its “first derivatives” ${n \mapsto P(n+h)-P(n)}$.

Lemma 2 (Van der Corput lemma, inverse form) Let ${Q \subset {\bf Z}}$ be an arithmetic progression of length at most ${N}$, and let ${P: Q \rightarrow {\bf R}/{\bf Z}}$ be an arbitrary function such that

$\displaystyle \frac{1}{N} |\sum_{n \in Q} e(P(n))| \geq \delta \ \ \ \ \ (1)$

for some ${\delta > 0}$. Then, for ${\gg \delta^2 N}$ integers ${h \in Q-Q}$, there exists a subprogression ${Q_h}$ of ${Q}$, of the same spacing as ${Q}$, such that

$\displaystyle \frac{1}{N} |\sum_{n \in Q_h} e(P(n+h)-P(n))| \gg \delta^2. \ \ \ \ \ (2)$

Proof: Squaring (1), we see that

$\displaystyle \sum_{n,n' \in Q} e(P(n') - P(n)) \geq \delta^2 N^2.$

We write ${n' = n+h}$ and conclude that

$\displaystyle \sum_{h \in Q-Q} \sum_{n \in Q_h} e( P(n+h)-P(n) ) \geq \delta^2 N^2$

where ${Q_h := Q \cap (Q-h)}$ is a subprogression of ${Q}$ of the same spacing. Since ${\sum_{n \in Q_h} e( P(n+h)-P(n) ) = O(N)}$, we conclude that

$\displaystyle |\sum_{n \in Q_h} e( P(n+h)-P(n) )| \gg \delta^2 N$

for ${\gg \delta^2 N}$ values of ${h}$ (this can be seen, much like the pigeonhole principle, by arguing via contradiction for a suitable choice of implied constants). The claim follows. $\Box$

The second lemma (which we recycle from this previous blog post) is a variant of the equidistribution theorem.

Lemma 3 (Vinogradov lemma) Let ${I \subset [-N,N] \cap {\bf Z}}$ be an interval for some ${N \geq 1}$, and let ${\theta \in{\bf R}/{\bf Z}}$ be such that ${\|n\theta\|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ for at least ${\delta N}$ values of ${n \in I}$, for some ${0 < \varepsilon, \delta < 1}$. Then either

$\displaystyle N < \frac{2}{\delta}$

or

$\displaystyle \varepsilon > 10^{-2} \delta$

or else there is a natural number ${q \leq 2/\delta}$ such that

$\displaystyle \| q \theta \|_{{\bf R}/{\bf Z}} \ll \frac{\varepsilon}{\delta N}.$

Proof: We may assume that ${N \geq \frac{2}{\delta}}$ and ${\varepsilon \leq 10^{-2} \delta}$, since we are done otherwise. Then there are at least two ${n \in I}$ with ${\|n \theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$, and by the pigeonhole principle we can find ${n_1 < n_2}$ in ${Q}$ with ${\|n_1 \theta \|_{{\bf R}/{\bf Z}}, \|n_2 \theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ and ${n_2-n_1 \leq \frac{2}{\delta}}$. By the triangle inequality, we conclude that there exists at least one natural number ${q \leq \frac{2}{\delta}}$ for which

$\displaystyle \| q \theta \|_{{\bf R}/{\bf Z}} \leq 2\varepsilon.$

We take ${q}$ to be minimal amongst all such natural numbers, then we see that there exists ${a}$ coprime to ${q}$ and ${|\kappa| \leq 2\varepsilon}$ such that

$\displaystyle \theta = \frac{a}{q} + \frac{\kappa}{q}. \ \ \ \ \ (3)$

If ${\kappa=0}$ then we are done, so suppose that ${\kappa \neq 0}$. Suppose that ${n < m}$ are elements of ${I}$ such that ${\|n\theta \|_{{\bf R}/{\bf Z}}, \|m\theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ and ${m-n \leq \frac{1}{10 \kappa}}$. Writing ${m-n = qk + r}$ for some ${0 \leq r < q}$, we have

$\displaystyle \| (m-n) \theta \|_{{\bf R}/{\bf Z}} = \| \frac{ra}{q} + (m-n) \frac{\kappa}{q} \|_{{\bf R}/{\bf Z}} \leq 2\varepsilon.$

By hypothesis, ${(m-n) \frac{\kappa}{q} \leq \frac{1}{10 q}}$; note that as ${q \leq 2/\delta}$ and ${\varepsilon \leq 10^{-2} \delta}$ we also have ${\varepsilon \leq \frac{1}{10q}}$. This implies that ${\| \frac{ra}{q} \|_{{\bf R}/{\bf Z}} < \frac{1}{q}}$ and thus ${r=0}$. We then have

$\displaystyle |k \kappa| \leq 2 \varepsilon.$

We conclude that for fixed ${n \in I}$ with ${\|n\theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$, there are at most ${\frac{2\varepsilon}{|\kappa|}}$ elements ${m}$ of ${[n, n + \frac{1}{10 |\kappa|}]}$ such that ${\|m\theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$. Iterating this with a greedy algorithm, we see that the number of ${n \in I}$ with ${\|n\theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ is at most ${(\frac{N}{1/10|\kappa|} + 1) 2\varepsilon/|\kappa|}$; since ${\varepsilon < 10^{-2} \delta}$, this implies that

$\displaystyle \delta N \ll 2 \varepsilon / \kappa$

and the claim follows. $\Box$

Now we can quickly obtain a higher degree version of Lemma 1:

Proposition 4 (Weyl exponential sum estimate, inverse form) Let ${Q \subset {\bf Z}}$ be an arithmetic progression of length at most ${N}$ for some ${N \geq 1}$, and let ${P: {\bf Z} \rightarrow {\bf R}/{\bf Z}}$ be a polynomial of some degree at most ${d \geq 0}$. If

$\displaystyle \frac{1}{N} |\sum_{n \in Q} e(P(n))| \geq \delta$

for some ${\delta > 0}$, then there exists a subprogression ${Q'}$ of ${Q}$ with ${|Q'| \gg_d \delta^{O_d(1)} N}$ such that ${P}$ varies by at most ${\delta}$ on ${Q'}$.

Proof: We induct on ${d}$. The cases ${d=0,1}$ are immediate from Lemma 1. Now suppose that ${d \geq 2}$, and that the claim had already been proven for ${d-1}$. To simplify the notation we allow implied constants to depend on ${d}$. Let the hypotheses be as in the proposition. Clearly ${\delta}$ cannot exceed ${1}$. By shrinking ${\delta}$ as necessary we may assume that ${\delta \leq c}$ for some sufficiently small constant ${c}$ depending on ${d}$.

By rescaling we may assume ${Q \subset [0,N] \cap {\bf Z}}$. By Lemma 3, we see that for ${\gg \delta^2 N}$ choices of ${h \in [-N,N] \cap {\bf Z}}$ such that

$\displaystyle \frac{1}{N} |\sum_{n \in I_h} e(P(n+h) - P(n))| \gg \delta^2$

for some interval ${I_h \subset [0,N] \cap {\bf Z}}$. We write ${P(n) = \sum_{i \leq d} \alpha_i n^i}$, then ${P(n+h)-P(n)}$ is a polynomial of degree at most ${d-1}$ with leading coefficient ${h \alpha_d n^{d-1}}$. We conclude from induction hypothesis that for each such ${h}$, there exists a natural number ${q_h \ll \delta^{-O(1)}}$ such that ${\|q_h h \alpha_d \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N^{d-1}}$, by double-counting, this implies that there are ${\gg \delta^{O(1)} N}$ integers ${n}$ in the interval ${[-\delta^{-O(1)} N, \delta^{-O(1)} N] \cap {\bf Z}}$ such that ${\|n \alpha_d \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N^{d-1}}$. Applying Lemma 3, we conclude that either ${N \ll \delta^{-O(1)}}$, or that

$\displaystyle \| q \alpha_d \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N^d. \ \ \ \ \ (4)$

In the former case the claim is trivial (just take ${Q'}$ to be a point), so we may assume that we are in the latter case.

We partition ${Q}$ into arithmetic progressions ${Q'}$ of spacing ${q}$ and length comparable to ${\delta^{-C} N}$ for some large ${C}$ depending on ${d}$ to be chosen later. By hypothesis, we have

$\displaystyle \frac{1}{|Q|} |\sum_{n \in Q} e(P(n))| \geq \delta$

so by the pigeonhole principle, we have

$\displaystyle \frac{1}{|Q'|} |\sum_{n \in Q'} e(P(n))| \geq \delta$

for at least one such progression ${Q'}$. On this progression, we may use the binomial theorem and (4) to write ${\alpha_d n^d}$ as a polynomial in ${n}$ of degree at most ${d-1}$, plus an error of size ${O(\delta^{C - O(1)})}$. We thus can write ${P(n) = P'(n) + O(\delta^{C-O(1)})}$ for ${n \in Q'}$ for some polynomial ${P'}$ of degree at most ${d-1}$. By the triangle inequality, we thus have (for ${C}$ large enough) that

$\displaystyle \frac{1}{|Q'|} |\sum_{n \in Q'} e(P'(n))| \gg \delta$

and hence by induction hypothesis we may find a subprogression ${Q''}$ of ${Q'}$ of size ${|Q''| \gg \delta^{O(1)} N}$ such that ${P'}$ varies by most ${\delta/2}$ on ${Q''}$, and thus (for ${C}$ large enough again) that ${P}$ varies by at most ${\delta}$ on ${Q''}$, and the claim follows. $\Box$

This gives the following corollary (also given as Exercise 16 in this previous blog post):

Corollary 5 (Weyl exponential sum estimate, inverse form II) Let ${I \subset [-N,N] \cap {\bf Z}}$ be a discrete interval for some ${N \geq 1}$, and let ${P(n) = \sum_{i \leq d} \alpha_i n^i}$ polynomial of some degree at most ${d \geq 0}$ for some ${\alpha_0,\dots,\alpha_d \in {\bf R}/{\bf Z}}$. If

$\displaystyle \frac{1}{N} |\sum_{n \in I} e(P(n))| \geq \delta$

for some ${\delta > 0}$, then there is a natural number ${q \ll_d \delta^{-O_d(1)}}$ such that ${\| q\alpha_i \|_{{\bf R}/{\bf Z}} \ll_d \delta^{-O_d(1)} N^{-i}}$ for all ${i=0,\dots,d}$.

One can obtain much better exponents here using Vinogradov’s mean value theorem; see Theorem 1.6 this paper of Wooley. (Thanks to Mariusz Mirek for this reference.) However, this weaker result already suffices for many applications, and does not need any result as deep as the mean value theorem.

Proof: To simplify notation we allow implied constants to depend on ${d}$. As before, we may assume that ${\delta \leq c}$ for some small constant ${c>0}$ depending only on ${d}$. We may also assume that ${N \geq \delta^{-C}}$ for some large ${C}$, as the claim is trivial otherwise (set ${q=1}$).

Applying Proposition 4, we can find a natural number ${q \ll \delta^{-O(1)}}$ and an arithmetic subprogression ${Q}$ of ${I}$ such that ${|Q| \gg \delta^{O(1)}}$ and such that ${P}$ varies by at most ${\delta}$ on ${Q}$. Writing ${Q = \{ qn+r: n \in I'\}}$ for some interval ${I' \subset [0,N] \cap {\bf Z}}$ of length ${\gg \delta^{O(1)}}$ and some ${0 \leq r < q}$, we conclude that the polynomial ${n \mapsto P(qn+r)}$ varies by at most ${\delta}$ on ${I'}$. Taking ${d^{th}}$ order differences, we conclude that the ${d^{th}}$ coefficient of this polynomial is ${O(\delta^{-O(1)} / N^d)}$; by the binomial theorem, this implies that ${n \mapsto P(qn+r)}$ differs by at most ${O(\delta)}$ on ${I'}$ from a polynomial of degree at most ${d-1}$. Iterating this, we conclude that the ${i^{th}}$ coefficient of ${n \mapsto P(qn+r)}$ is ${O(\delta N^{-i})}$ for ${i=0,\dots,d}$, and the claim then follows by inverting the change of variables ${n \mapsto qn+r}$ (and replacing ${q}$ with a larger quantity such as ${q^d}$ as necessary). $\Box$

For future reference we also record a higher degree version of the Vinogradov lemma.

Lemma 6 (Polynomial Vinogradov lemma) Let ${I \subset [-N,N] \cap {\bf Z}}$ be a discrete interval for some ${N \geq 1}$, and let ${P: {\bf Z} \rightarrow {\bf R}/{\bf Z}}$ be a polynomial ${P(n) = \sum_{i \leq d} \alpha_i n^i}$ of degree at most ${d}$ for some ${d \geq 1}$ such that ${\|P(n)\|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ for at least ${\delta N}$ values of ${n \in I}$, for some ${0 < \varepsilon, \delta < 1}$. Then either

$\displaystyle N \ll_d \delta^{-O_d(1)} \ \ \ \ \ (5)$

or

$\displaystyle \varepsilon \gg_d \delta^{O_d(1)} \ \ \ \ \ (6)$

or else there is a natural number ${q \ll_d \delta^{-O_d(1)}}$ such that

$\displaystyle \| q \alpha_i \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^i}$

for all ${i=0,\dots,d}$.

Proof: We induct on ${d}$. For ${d=1}$ this follows from Lemma 3 (noting that if ${\|P(n)\|_{{\bf R}/{\bf Z}}, \|P(n_0)\|_{{\bf R}/Z} \leq \varepsilon}$ then ${\|P(n)-P(n_0)\|_{{\bf R}/{\bf Z}} \leq 2\varepsilon}$), so suppose that ${d \geq 2}$ and that the claim is already proven for ${d-1}$. We now allow all implied constants to depend on ${d}$.

For each ${h \in [-2N,2N] \cap {\bf Z}}$, let ${N_h}$ denote the number of ${n \in [-N,N] \cap {\bf Z}}$ such that ${\| P(n+h)\|_{{\bf R}/{\bf Z}}, \|P(n)\|_{{\bf R}/{\bf Z}} \leq \varepsilon}$. By hypothesis, ${\sum_{h \in [-2N,2N] \cap {\bf Z}} N_h \gg \delta^2 N^2}$, and clearly ${N_h = O(N)}$, so we must have ${N_h \gg \delta^2 N}$ for ${\gg \delta^2 N}$ choices of ${h}$. For each such ${h}$, we then have ${\|P(n+h)-P(n)\|_{{\bf R}/{\bf Z}} \leq 2\varepsilon}$ for ${\gg \delta^2 N}$ choices of ${n \in [-N,N] \cap {\bf Z}}$, so by induction hypothesis, either (5) or (6) holds, or else for ${\gg \delta^{O(1)} N}$ choices of ${h \in [-2N,2N] \cap {\bf Z}}$, there is a natural number ${q_h \ll \delta^{-O(1)}}$ such that

$\displaystyle \| q_h \alpha_{i,h} \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^i}$

for ${i=1,\dots,d-1}$, where ${\alpha_{i,h}}$ are the coefficients of the degree ${d-1}$ polynomial ${n \mapsto P(n+h)-P(n)}$. We may of course assume it is the latter which holds. By the pigeonhole principle we may take ${q_h= q}$ to be independent of ${h}$.

Since ${\alpha_{d-1,h} = dh \alpha_d}$, we have

$\displaystyle \| qd h \alpha_d \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^{d-1}}$

for ${\gg \delta^{O(1)} N}$ choices of ${h}$, so by Lemma 3, either (5) or (6) holds, or else (after increasing ${q}$ as necessary) we have

$\displaystyle \| q \alpha_d \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^d}.$

We can again assume it is the latter that holds. This implies that ${q \alpha_{d-2,h} = (d-1) h \alpha_{d-1} + O( \delta^{-O(1)} \varepsilon / N^{d-2} )}$ modulo ${1}$, so that

$\displaystyle \| q(d-1) h \alpha_{d-1} \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^{d-2}}$

for ${\gg \delta^{O(1)} N}$ choices of ${h}$. Arguing as before and iterating, we obtain the claim. $\Box$

The above results also extend to higher dimensions. Here is the higher dimensional version of Proposition 4:

Proposition 7 (Multidimensional Weyl exponential sum estimate, inverse form) Let ${k \geq 1}$ and ${N_1,\dots,N_k \geq 1}$, and let ${Q_i \subset {\bf Z}}$ be arithmetic progressions of length at most ${N_i}$ for each ${i=1,\dots,k}$. Let ${P: {\bf Z}^k \rightarrow {\bf R}/{\bf Z}}$ be a polynomial of degrees at most ${d_1,\dots,d_k}$ in each of the ${k}$ variables ${n_1,\dots,n_k}$ separately. If

$\displaystyle \frac{1}{N_1 \dots N_k} |\sum_{n \in Q_1 \times \dots \times Q_k} e(P(n))| \geq \delta$

for some ${\delta > 0}$, then there exists a subprogression ${Q'_i}$ of ${Q_i}$ with ${|Q'_i| \gg_{k,d_1,\dots,d_k} \delta^{O_{k,d_1,\dots,d_k}(1)} N_i}$ for each ${i=1,\dots,k}$ such that ${P}$ varies by at most ${\delta}$ on ${Q'_1 \times \dots \times Q'_k}$.

A much more general statement, in which the polynomial phase ${n \mapsto e(P(n))}$ is replaced by a nilsequence, and in which one does not necessarily assume the exponential sum is small, is given in Theorem 8.6 of this paper of Ben Green and myself, but it involves far more notation to even state properly.

Proof: We induct on ${k}$. The case ${k=1}$ was established in Proposition 5, so we assume that ${k \geq 2}$ and that the claim has already been proven for ${k-1}$. To simplify notation we allow all implied constants to depend on ${k,d_1,\dots,d_k}$. We may assume that ${\delta \leq c}$ for some small ${c>0}$ depending only on ${k,d_1,\dots,d_k}$.

By a linear change of variables, we may assume that ${Q_i \subset [0,N_i] \cap {\bf Z}}$ for all ${i=1,\dots,k}$.

We write ${n' := (n_1,\dots,n_{k-1})}$. First suppose that ${N_k = O(\delta^{-O(1)})}$. Then by the pigeonhole principle we can find ${n_k \in I_k}$ such that

$\displaystyle \frac{1}{N_1 \dots N_{k-1}} |\sum_{n' \in Q_1 \times \dots \times Q_{k-1}} e(P(n',n_k))| \geq \delta$

and the claim then follows from the induction hypothesis. Thus we may assume that ${N_k \geq \delta^{-C}}$ for some large ${C}$ depending only on ${k,d_1,\dots,d_k}$. Similarly we may assume that ${N_i \geq \delta^{-C}}$ for all ${i=1,\dots,k}$.

By the triangle inequality, we have

$\displaystyle \frac{1}{N_1 \dots N_k} \sum_{n_k \in Q_k} |\sum_{n' \in Q_1 \times \dots \times Q_{k-1}} e(P(n',n_k))| \geq \delta.$

The inner sum is ${O(N_k)}$, and the outer sum has ${O(N_1 \dots N_{k-1})}$ terms. Thus, for ${\gg \delta N_1 \dots N_{k-1}}$ choices of ${n' \in Q_1 \times \dots \times Q_{k-1}}$, one has

$\displaystyle \frac{1}{N_k} |\sum_{n_k \in Q_k} e(P(n',n_k))| \gg \delta. \ \ \ \ \ (7)$

We write

$\displaystyle P(n',n_k) = \sum_{i_k \leq d_k} P_{i_k}(n') n_k^i$

for some polynomials ${P_{i_k}: {\bf Z}^{k-1} \rightarrow {\bf R}/{\bf Z}}$ of degrees at most ${d_1,\dots,d_{k-1}}$ in the variables ${n_1,\dots,n_{k-1}}$. For each ${n'}$ obeying (7), we apply Corollary 5 to conclude that there exists a natural number ${q_{n'} \ll \delta^{-O(1)}}$ such that

$\displaystyle \| q_{n'} P_{i_k}(n') \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N_k^{i_k}$

for ${i_k=1,\dots,d_k}$ (the claim also holds for ${i_k=0}$ but we discard it as being trivial). By the pigeonhole principle, there thus exists a natural number ${q \ll \delta^{-O(1)}}$ such that

$\displaystyle \| q P_{i_k}(n') \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N_k^{i_k}$

for all ${i_k=1,\dots,d_k}$ and for ${\gg \delta^{O(1)} N_1 \dots N_{k-1}}$ choices of ${n' \in Q_1 \times \dots \times Q_{k-1}}$. If we write

$\displaystyle P_{i_k}(n') = \sum_{i_{k-1} \leq d_{k-1}} P_{i_{k-1},i_k}(n_1,\dots,n_{k-2}) n_{k-1}^{i_{k-1}},$

where ${P_{i_{k-1},i_k}: {\bf Z}^{k-2} \rightarrow {\bf R}/{\bf Z}}$ is a polynomial of degrees at most ${d_1,\dots,d_{k-2}}$, then for ${\gg \delta^{O(1)} N_1 \dots N_{k-2}}$ choices of ${(n_1,\dots,n_{k-2}) \in Q_1 \times \dots \times Q_{k-2}}$ we then have

$\displaystyle \| \sum_{i_{k-1} \leq d_{k-1}} q P_{i_{k-1},i_k}(n_1,\dots,n_{k-2}) n_{k-1}^{i_{k-1}} \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N_k^{i_k}.$

Applying Lemma 6 in the ${n_{k-1}}$ and the largeness hypotheses on the ${N_i}$ (and also the assumption that ${i_k \geq 1}$) we conclude (after enlarging ${q}$ as necessary, and pigeonholing to keep ${q}$ independent of ${n_1,\dots,n_{k-2}}$) that

$\displaystyle \| q P_{i_{k-1},i_k}(n_1,\dots,n_{k-2}) \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)}}{N_{k-1}^{i_{k-1}} N_k^{i_k}}$

for all ${i_{k-1}=0,\dots,d_{k-1}}$ (note that we now include that ${i_{k-1}=0}$ case, which is no longer trivial) and for ${\gg \delta^{O(1)} N_1 \dots N_{k-2}}$ choices of ${(n_1,\dots,n_{k-2}) \in Q_1 \times \dots \times Q_{k-2}}$. Iterating this, we eventually conclude (after enlarging ${q}$ as necessary) that

$\displaystyle \| q \alpha_{i_1,\dots,i_k} \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)}}{N_1^{i_1} \dots N_k^{i_k}} \ \ \ \ \ (8)$

whenever ${i_j \in \{0,\dots,d_j\}}$ for ${j=1,\dots,k}$, with ${i_k}$ nonzero. Permuting the indices, and observing that the claim is trivial for ${(i_1,\dots,i_k) = (0,\dots,0)}$, we in fact obtain (8) for all ${(i_1,\dots,i_k) \in \{0,\dots,d_1\} \times \dots \times \{0,\dots,d_k\}}$, at which point the claim easily follows by taking ${Q'_j := \{ qn_j: n_j \leq \delta^C N_j\}}$ for each ${j=1,\dots,k}$. $\Box$

An inspection of the proof of the above result (or alternatively, by combining the above result again with many applications of Lemma 6) reveals the following general form of Proposition 4, which was posed as Exercise 17 in this previous blog post, but had a slight misprint in it (it did not properly treat the possibility that some of the ${N_j}$ could be small) and was a bit trickier to prove than anticipated (in fact, the reason for this post was that I was asked to supply a more detailed solution for this exercise):

Proposition 8 (Multidimensional Weyl exponential sum estimate, inverse form, II) Let ${k \geq 1}$ be an natural number, and for each ${j=1,\dots,k}$, let ${I_j \subset [0,N_j]_{\bf Z}}$ be a discrete interval for some ${N_j \geq 1}$. Let

$\displaystyle P(n_1,\dots,n_k) = \sum_{i_1 \leq d_1, \dots, i_k \leq d_k} \alpha_{i_1,\dots,i_k} n_1^{i_1} \dots n_k^{i_k}$

be a polynomial in ${k}$ variables of multidegrees ${d_1,\dots,d_k \geq 0}$ for some ${\alpha_{i_1,\dots,i_k} \in {\bf R}/{\bf Z}}$. If

$\displaystyle \frac{1}{N_1 \dots N_k} |\sum_{n \in I_1 \times \dots \times I_k} e(P(n))| \geq \delta \ \ \ \ \ (9)$

for some ${\delta > 0}$, then either

$\displaystyle N_j \ll_{k,d_1,\dots,d_k} \delta^{-O_{k,d_1,\dots,d_k}(1)} \ \ \ \ \ (10)$

for some ${1 \leq j \leq d_k}$, or else there is a natural number ${q \ll_{k,d_1,\dots,d_k} \delta^{-O_{k,d_1,\dots,d_k}(1)}}$ such that

$\displaystyle \| q\alpha_{i_1,\dots,i_k} \|_{{\bf R}/{\bf Z}} \ll_{k,d_1,\dots,d_k} \delta^{-O_d(1)} N_1^{-i_1} \dots N_k^{-i_k} \ \ \ \ \ (11)$

whenever ${i_j \leq d_j}$ for ${j=1,\dots,k}$.

Again, the factor of ${N_1^{-i_1} \dots N_k^{-i_k}}$ is natural in this bound. In the ${k=1}$ case, the option (10) may be deleted since (11) trivially holds in this case, but this simplification is no longer available for ${k>1}$ since one needs (10) to hold for all ${j}$ (not just one ${j}$) to make (11) completely trivial. Indeed, the above proposition fails for ${k \geq 2}$ if one removes (10) completely, as can be seen for instance by inspecting the exponential sum ${\sum_{n_1 \in \{0,1\}} \sum_{n_2 \in [1,N] \cap {\bf Z}} e( \alpha n_1 n_2)}$, which has size comparable to ${N}$ regardless of how irrational ${\alpha}$ is.

This week I have been at a Banff workshop “Combinatorics meets Ergodic theory“, focused on the combinatorics surrounding Szemerédi’s theorem and the Gowers uniformity norms on one hand, and the ergodic theory surrounding Furstenberg’s multiple recurrence theorem and the Host-Kra structure theory on the other. This was quite a fruitful workshop, and directly inspired the various posts this week on this blog. Incidentally, BIRS being as efficient as it is, videos for this week’s talks are already online.

As mentioned in the previous two posts, Ben Green, Tamar Ziegler, and myself proved the following inverse theorem for the Gowers norms:

Theorem 1 (Inverse theorem for Gowers norms) Let ${N \geq 1}$ and ${s \geq 1}$ be integers, and let ${\delta > 0}$. Suppose that ${f: {\bf Z} \rightarrow [-1,1]}$ is a function supported on ${[N] := \{1,\dots,N\}}$ such that

$\displaystyle \frac{1}{N^{s+2}} \sum_{n,h_1,\dots,h_{s+1} \in {\bf Z}} \prod_{\omega \in \{0,1\}^{s+1}} f(n+\omega_1 h_1 + \dots + \omega_{s+1} h_{s+1}) \geq \delta.$

Then there exists a filtered nilmanifold ${G/\Gamma}$ of degree ${\leq s}$ and complexity ${O_{s,\delta}(1)}$, a polynomial sequence ${g: {\bf Z} \rightarrow G}$, and a Lipschitz function ${F: G/\Gamma \rightarrow {\bf R}}$ of Lipschitz constant ${O_{s,\delta}(1)}$ such that

$\displaystyle \frac{1}{N} \sum_n f(n) F(g(n) \Gamma) \gg_{s,\delta} 1.$

There is a higher dimensional generalisation, which first appeared explicitly (in a more general form) in this preprint of Szegedy (which used a slightly different argument than the one of Ben, Tammy, and myself; see also this previous preprint of Szegedy with related results):

Theorem 2 (Inverse theorem for multidimensional Gowers norms) Let ${N \geq 1}$ and ${s,d \geq 1}$ be integers, and let ${\delta > 0}$. Suppose that ${f: {\bf Z}^d \rightarrow [-1,1]}$ is a function supported on ${[N]^d}$ such that

$\displaystyle \frac{1}{N^{d(s+2)}} \sum_{n,h_1,\dots,h_{s+1} \in {\bf Z}^d} \prod_{\omega \in \{0,1\}^{s+1}} f(n+\omega_1 h_1 + \dots + \omega_{s+1} h_{s+1}) \geq \delta. \ \ \ \ \ (1)$

Then there exists a filtered nilmanifold ${G/\Gamma}$ of degree ${\leq s}$ and complexity ${O_{s,\delta,d}(1)}$, a polynomial sequence ${g: {\bf Z}^d \rightarrow G}$, and a Lipschitz function ${F: G/\Gamma \rightarrow {\bf R}}$ of Lipschitz constant ${O_{s,\delta,d}(1)}$ such that

$\displaystyle \frac{1}{N^d} \sum_{n \in {\bf Z}^d} f(n) F(g(n) \Gamma) \gg_{s,\delta,d} 1.$

The ${d=2}$ case of this theorem was recently used by Wenbo Sun. One can replace the polynomial sequence with a linear sequence if desired by using a lifting trick (essentially due to Furstenberg, but which appears explicitly in Appendix C of my paper with Ben and Tammy).

In this post I would like to record a very neat and simple observation of Ben Green and Nikos Frantzikinakis, that uses the tool of Freiman isomorphisms to derive Theorem 2 as a corollary of the one-dimensional theorem. Namely, consider the linear map ${\phi: {\bf Z}^d \rightarrow {\bf Z}}$ defined by

$\displaystyle \phi( n_1,\dots,n_d ) := \sum_{i=1}^d (10 N)^{i-1} n_i,$

that is to say ${\phi}$ is the digit string base ${10N}$ that has digits ${n_d \dots n_1}$. This map is a linear map from ${[N]^d}$ to a subset of ${[d 10^d N^d]}$ of density ${1/(d10^d)}$. Furthermore it has the following “Freiman isomorphism” property: if ${n, h_1,\dots,h_{s+1}}$ lie in ${{\bf Z}}$ with ${n + \omega_1 h_1 + \dots + \omega_{s+1} h_{s+1}}$ in the image set ${\phi( [N]^d )}$ of ${[N]^d}$ for all ${\omega}$, then there exist (unique) lifts ${\tilde n \in {\bf Z}^d, \tilde h_1,\dots,\tilde h_{s+1} \in {\bf Z}}$ such that

$\displaystyle \tilde n + \omega_1 \tilde h_1 + \dots + \omega_{s+1} \tilde h_{s+1} \in [N]^d$

and

$\displaystyle \phi( \tilde n + \omega_1 \tilde h_1 + \dots + \omega_{s+1} \tilde h_{s+1} ) = n + \omega_1 h_1 + \dots + \omega_{s+1} h_{s+1}$

for all ${\omega}$. Indeed, the injectivity of ${\phi}$ on ${[N]^d}$ uniquely determines the sum ${\tilde n + \omega_1 \tilde h_1 + \dots + \omega_{s+1} \tilde h_{s+1}}$ for each ${\omega}$, and one can use base ${10N}$ arithmetic to verify that the alternating sum of these sums on any ${2}$-facet of the cube ${\{0,1\}^{s+1}}$ vanishes, which gives the claim. (In the language of additive combinatorics, the point is that ${\phi}$ is a Freiman isomorphism of order (say) ${8}$ on ${[N]^d}$.)

Now let ${\tilde f: {\bf Z} \rightarrow [-1,1]}$ be the function defined by setting ${\tilde f( \phi(n) ) := f(n)}$ whenever ${n \in [N]^d}$, with ${\tilde f}$ vanishing outside of ${\phi([N]^d)}$. If ${f}$ obeys (1), then from the above Freiman isomorphism property we have

$\displaystyle \frac{1}{N^{d(s+2)}} \sum_{n, h_1,\dots,h_{s+1} \in {\bf Z}} \prod_{\omega \in \{0,1\}^{s+1}} \tilde f(n+\omega_1 h_1 + \dots + \omega_{s+1} h_{s+1}) \geq \delta.$

Applying the one-dimensional inverse theorem (Theorem 1), with ${\delta}$ reduced by a factor of ${d 10^d}$ and ${N}$ replaced by ${d 10^d N^d}$, this implies the existence of a filtered nilmanifold ${G/\Gamma}$ of degree ${\leq s}$ and complexity ${O_{s,\delta,d}(1)}$, a polynomial sequence ${g: {\bf Z} \rightarrow G}$, and a Lipschitz function ${F: G/\Gamma \rightarrow {\bf R}}$ of Lipschitz constant ${O_{s,\delta,d}(1)}$ such that

$\displaystyle \frac{1}{N^{d(s+2)}} \sum_{n \in {\bf Z}} \tilde f(n) F(g(n) \Gamma) \gg_{s,\delta,d} 1$

which by the Freiman isomorphism property again implies that

$\displaystyle \frac{1}{N^{d(s+2)}} \sum_{n \in {\bf Z}^d} f(n) F(g(\phi(n)) \Gamma) \gg_{s,\delta,d} 1.$

But the map ${n \mapsto g(\phi(n))}$ is clearly a polynomial map from ${{\bf Z}^d}$ to ${G}$ (the composition of two polynomial maps is polynomial, see e.g. Appendix B of my paper with Ben and Tammy), and the claim follows.

Remark 3 This trick appears to be largely restricted to the case of boundedly generated groups such as ${{\bf Z}^d}$; I do not see any easy way to deduce an inverse theorem for, say, ${\bigcup_{n=1}^\infty {\mathbb F}_p^n}$ from the ${{\bf Z}}$-inverse theorem by this method.

Remark 4 By combining this argument with the one in the previous post, one can obtain a weak ergodic inverse theorem for ${{\bf Z}^d}$-actions. Interestingly, the Freiman isomorphism argument appears to be difficult to implement directly in the ergodic category; in particular, there does not appear to be an obvious direct way to derive the Host-Kra inverse theorem for ${{\bf Z}^d}$ actions (a result first obtained in the PhD thesis of Griesmer) from the counterpart for ${{\bf Z}}$ actions.

Note: this post is of a particularly technical nature, in particular presuming familiarity with nilsequences, nilsystems, characteristic factors, etc., and is primarily intended for experts.

As mentioned in the previous post, Ben Green, Tamar Ziegler, and myself proved the following inverse theorem for the Gowers norms:

Theorem 1 (Inverse theorem for Gowers norms) Let ${N \geq 1}$ and ${s \geq 1}$ be integers, and let ${\delta > 0}$. Suppose that ${f: {\bf Z} \rightarrow [-1,1]}$ is a function supported on ${[N] := \{1,\dots,N\}}$ such that

$\displaystyle \frac{1}{N^{s+2}} \sum_{n,h_1,\dots,h_{s+1}} \prod_{\omega \in \{0,1\}^{s+1}} f(n+\omega_1 h_1 + \dots + \omega_{s+1} h_{s+1}) \geq \delta.$

Then there exists a filtered nilmanifold ${G/\Gamma}$ of degree ${\leq s}$ and complexity ${O_{s,\delta}(1)}$, a polynomial sequence ${g: {\bf Z} \rightarrow G}$, and a Lipschitz function ${F: G/\Gamma \rightarrow {\bf R}}$ of Lipschitz constant ${O_{s,\delta}(1)}$ such that

$\displaystyle \frac{1}{N} \sum_n f(n) F(g(n) \Gamma) \gg_{s,\delta} 1.$

This result was conjectured earlier by Ben Green and myself; this conjecture was strongly motivated by an analogous inverse theorem in ergodic theory by Host and Kra, which we formulate here in a form designed to resemble Theorem 1 as closely as possible:

Theorem 2 (Inverse theorem for Gowers-Host-Kra seminorms) Let ${s \geq 1}$ be an integer, and let ${(X, T)}$ be an ergodic, countably generated measure-preserving system. Suppose that one has

$\displaystyle \lim_{N \rightarrow \infty} \frac{1}{N^{s+1}} \sum_{h_1,\dots,h_{s+1} \in [N]} \int_X \prod_{\omega \in \{0,1\}^{s+1}} f(T^{\omega_1 h_1 + \dots + \omega_{s+1} h_{s+1}}x)\ d\mu(x)$

$\displaystyle > 0$

for all non-zero ${f \in L^\infty(X)}$ (all ${L^p}$ spaces are real-valued in this post). Then ${(X,T)}$ is an inverse limit (in the category of measure-preserving systems, up to almost everywhere equivalence) of ergodic degree ${\leq s}$ nilsystems, that is to say systems of the form ${(G/\Gamma, x \mapsto gx)}$ for some degree ${\leq s}$ filtered nilmanifold ${G/\Gamma}$ and a group element ${g \in G}$ that acts ergodically on ${G/\Gamma}$.

It is a natural question to ask if there is any logical relationship between the two theorems. In the finite field category, one can deduce the combinatorial inverse theorem from the ergodic inverse theorem by a variant of the Furstenberg correspondence principle, as worked out by Tamar Ziegler and myself, however in the current context of ${{\bf Z}}$-actions, the connection is less clear.

One can split Theorem 2 into two components:

Theorem 3 (Weak inverse theorem for Gowers-Host-Kra seminorms) Let ${s \geq 1}$ be an integer, and let ${(X, T)}$ be an ergodic, countably generated measure-preserving system. Suppose that one has

$\displaystyle \lim_{N \rightarrow \infty} \frac{1}{N^{s+1}} \sum_{h_1,\dots,h_{s+1} \in [N]} \int_X \prod_{\omega \in \{0,1\}^{s+1}} T^{\omega_1 h_1 + \dots + \omega_{s+1} h_{s+1}} f\ d\mu$

$\displaystyle > 0$

for all non-zero ${f \in L^\infty(X)}$, where ${T^h f := f \circ T^h}$. Then ${(X,T)}$ is a factor of an inverse limit of ergodic degree ${\leq s}$ nilsystems.

Theorem 4 (Pro-nilsystems closed under factors) Let ${s \geq 1}$ be an integer. Then any factor of an inverse limit of ergodic degree ${\leq s}$ nilsystems, is again an inverse limit of ergodic degree ${\leq s}$ nilsystems.

Indeed, it is clear that Theorem 2 implies both Theorem 3 and Theorem 4, and conversely that the two latter theorems jointly imply the former. Theorem 4 is, in principle, purely a fact about nilsystems, and should have an independent proof, but this is not known; the only known proofs go through the full machinery needed to prove Theorem 2 (or the closely related theorem of Ziegler). (However, the fact that a factor of a nilsystem is again a nilsystem was established previously by Parry.)

The purpose of this post is to record a partial implication in reverse direction to the correspondence principle:

Proposition 5 Theorem 1 implies Theorem 3.

As mentioned at the start of the post, a fair amount of familiarity with the area is presumed here, and some routine steps will be presented with only a fairly brief explanation.

A few years ago, Ben Green, Tamar Ziegler, and myself proved the following (rather technical-looking) inverse theorem for the Gowers norms:

Theorem 1 (Discrete inverse theorem for Gowers norms) Let ${N \geq 1}$ and ${s \geq 1}$ be integers, and let ${\delta > 0}$. Suppose that ${f: {\bf Z} \rightarrow [-1,1]}$ is a function supported on ${[N] := \{1,\dots,N\}}$ such that

$\displaystyle \frac{1}{N^{s+2}} \sum_{n,h_1,\dots,h_{s+1}} \prod_{\omega \in \{0,1\}^{s+1}} f(n+\omega_1 h_1 + \dots + \omega_{s+1} h_{s+1}) \geq \delta.$

Then there exists a filtered nilmanifold ${G/\Gamma}$ of degree ${\leq s}$ and complexity ${O_{s,\delta}(1)}$, a polynomial sequence ${g: {\bf Z} \rightarrow G}$, and a Lipschitz function ${F: G/\Gamma \rightarrow {\bf R}}$ of Lipschitz constant ${O_{s,\delta}(1)}$ such that

$\displaystyle \frac{1}{N} \sum_n f(n) F(g(n) \Gamma) \gg_{s,\delta} 1.$

For the definitions of “filtered nilmanifold”, “degree”, “complexity”, and “polynomial sequence”, see the paper of Ben, Tammy, and myself. (I should caution the reader that this blog post will presume a fair amount of familiarity with this subfield of additive combinatorics.) This result has a number of applications, for instance to establishing asymptotics for linear equations in the primes, but this will not be the focus of discussion here.

The purpose of this post is to record the observation that this “discrete” inverse theorem, together with an equidistribution theorem for nilsequences that Ben and I worked out in a separate paper, implies a continuous version:

Theorem 2 (Continuous inverse theorem for Gowers norms) Let ${s \geq 1}$ be an integer, and let ${\delta>0}$. Suppose that ${f: {\bf R} \rightarrow [-1,1]}$ is a measurable function supported on ${[0,1]}$ such that

$\displaystyle \int_{{\bf R}^{s+1}} \prod_{\omega \in \{0,1\}^{s+1}} f(t+\omega_1 h_1 + \dots + \omega_{s+1} h_{s+1})\ dt dh_1 \dots dh_{s+1} \geq \delta. \ \ \ \ \ (1)$

Then there exists a filtered nilmanifold ${G/\Gamma}$ of degree ${\leq s}$ and complexity ${O_{s,\delta}(1)}$, a (smooth) polynomial sequence ${g: {\bf R} \rightarrow G}$, and a Lipschitz function ${F: G/\Gamma \rightarrow {\bf R}}$ of Lipschitz constant ${O_{s,\delta}(1)}$ such that

$\displaystyle \int_{\bf R} f(t) F(g(t) \Gamma)\ dt \gg_{s,\delta} 1.$

The interval ${[0,1]}$ can be easily replaced with any other fixed interval by a change of variables. A key point here is that the bounds are completely uniform in the choice of ${f}$. Note though that the coefficients of ${g}$ can be arbitrarily large (and this is necessary, as can be seen just by considering functions of the form ${f(t) = \cos( \xi t)}$ for some arbitrarily large frequency ${\xi}$).

It is likely that one could prove Theorem 2 by carefully going through the proof of Theorem 1 and replacing all instances of ${{\bf Z}}$ with ${{\bf R}}$ (and making appropriate modifications to the argument to accommodate this). However, the proof of Theorem 1 is quite lengthy. Here, we shall proceed by the usual limiting process of viewing the continuous interval ${[0,1]}$ as a limit of the discrete interval ${\frac{1}{N} \cdot [N]}$ as ${N \rightarrow \infty}$. However there will be some problems taking the limit due to a failure of compactness, and specifically with regards to the coefficients of the polynomial sequence ${g: {\bf N} \rightarrow G}$ produced by Theorem 1, after normalising these coefficients by ${N}$. Fortunately, a factorisation theorem from a paper of Ben Green and myself resolves this problem by splitting ${g}$ into a “smooth” part which does enjoy good compactness properties, as well as “totally equidistributed” and “periodic” parts which can be eliminated using the measurability (and thus, approximate smoothness), of ${f}$.

Szemerédi’s theorem asserts that any subset of the integers of positive upper density contains arbitrarily large arithmetic progressions. Here is an equivalent quantitative form of this theorem:

Theorem 1 (Szemerédi’s theorem) Let ${N}$ be a positive integer, and let ${f: {\bf Z}/N{\bf Z} \rightarrow [0,1]}$ be a function with ${{\bf E}_{x \in {\bf Z}/N{\bf Z}} f(x) \geq \delta}$ for some ${\delta>0}$, where we use the averaging notation ${{\bf E}_{x \in A} f(x) := \frac{1}{|A|} \sum_{x \in A} f(x)}$, ${{\bf E}_{x,r \in A} f(x) := \frac{1}{|A|^2} \sum_{x, r \in A} f(x)}$, etc.. Then for ${k \geq 3}$ we have

$\displaystyle {\bf E}_{x,r \in {\bf Z}/N{\bf Z}} f(x) f(x+r) \dots f(x+(k-1)r) \geq c(k,\delta)$

for some ${c(k,\delta)>0}$ depending only on ${k,\delta}$.

The equivalence is basically thanks to an averaging argument of Varnavides; see for instance Chapter 11 of my book with Van Vu or this previous blog post for a discussion. We have removed the cases ${k=1,2}$ as they are trivial and somewhat degenerate.

There are now many proofs of this theorem. Some time ago, I took an ergodic-theoretic proof of Furstenberg and converted it to a purely finitary proof of the theorem. The argument used some simplifying innovations that had been developed since the original work of Furstenberg (in particular, deployment of the Gowers uniformity norms, as well as a “dual” norm that I called the uniformly almost periodic norm, and an emphasis on van der Waerden’s theorem for handling the “compact extension” component of the argument). But the proof was still quite messy. However, as discussed in this previous blog post, messy finitary proofs can often be cleaned up using nonstandard analysis. Thus, there should be a nonstandard version of the Furstenberg ergodic theory argument that is relatively clean. I decided (after some encouragement from Ben Green and Isaac Goldbring) to write down most of the details of this argument in this blog post, though for sake of brevity I will skim rather quickly over arguments that were already discussed at length in other blog posts. In particular, I will presume familiarity with nonstandard analysis (in particular, the notion of a standard part of a bounded real number, and the Loeb measure construction), see for instance this previous blog post for a discussion.

In analytic number theory, there is a well known analogy between the prime factorisation of a large integer, and the cycle decomposition of a large permutation; this analogy is central to the topic of “anatomy of the integers”, as discussed for instance in this survey article of Granville. Consider for instance the following two parallel lists of facts (stated somewhat informally). Firstly, some facts about the prime factorisation of large integers:

• Every positive integer ${m}$ has a prime factorisation

$\displaystyle m = p_1 p_2 \dots p_r$

into (not necessarily distinct) primes ${p_1,\dots,p_r}$, which is unique up to rearrangement. Taking logarithms, we obtain a partition

$\displaystyle \log m = \log p_1 + \log p_2 + \dots + \log p_r$

of ${\log m}$.

• (Prime number theorem) A randomly selected integer ${m}$ of size ${m \sim N}$ will be prime with probability ${\approx \frac{1}{\log N}}$ when ${N}$ is large.
• If ${m \sim N}$ is a randomly selected large integer of size ${N}$, and ${p = p_i}$ is a randomly selected prime factor of ${m = p_1 \dots p_r}$ (with each index ${i}$ being chosen with probability ${\frac{\log p_i}{\log m}}$), then ${\log p_i}$ is approximately uniformly distributed between ${0}$ and ${\log N}$. (See Proposition 9 of this previous blog post.)
• The set of real numbers ${\{ \frac{\log p_i}{\log m}: i=1,\dots,r \}}$ arising from the prime factorisation ${m = p_1 \dots p_r}$ of a large random number ${m \sim N}$ converges (away from the origin, and in a suitable weak sense) to the Poisson-Dirichlet process in the limit ${N \rightarrow \infty}$. (See the previously mentioned blog post for a definition of the Poisson-Dirichlet process, and a proof of this claim.)

Now for the facts about the cycle decomposition of large permutations:

• Every permutation ${\sigma \in S_n}$ has a cycle decomposition

$\displaystyle \sigma = C_1 \dots C_r$

into disjoint cycles ${C_1,\dots,C_r}$, which is unique up to rearrangement, and where we count each fixed point of ${\sigma}$ as a cycle of length ${1}$. If ${|C_i|}$ is the length of the cycle ${C_i}$, we obtain a partition

$\displaystyle n = |C_1| + \dots + |C_r|$

of ${n}$.

• (Prime number theorem for permutations) A randomly selected permutation of ${S_n}$ will be an ${n}$-cycle with probability exactly ${1/n}$. (This was noted in this previous blog post.)
• If ${\sigma}$ is a random permutation in ${S_n}$, and ${C_i}$ is a randomly selected cycle of ${\sigma}$ (with each ${i}$ being selected with probability ${|C_i|/n}$), then ${|C_i|}$ is exactly uniformly distributed on ${\{1,\dots,n\}}$. (See Proposition 8 of this blog post.)
• The set of real numbers ${\{ \frac{|C_i|}{n} \}}$ arising from the cycle decomposition ${\sigma = C_1 \dots C_r}$ of a random permutation ${\sigma \in S_n}$ converges (in a suitable sense) to the Poisson-Dirichlet process in the limit ${n \rightarrow \infty}$. (Again, see this previous blog post for details.)

See this previous blog post (or the aforementioned article of Granville, or the Notices article of Arratia, Barbour, and Tavaré) for further exploration of the analogy between prime factorisation of integers and cycle decomposition of permutations.

There is however something unsatisfying about the analogy, in that it is not clear why there should be such a kinship between integer prime factorisation and permutation cycle decomposition. It turns out that the situation is clarified if one uses another fundamental analogy in number theory, namely the analogy between integers and polynomials ${P \in {\mathbf F}_q[T]}$ over a finite field ${{\mathbf F}_q}$, discussed for instance in this previous post; this is the simplest case of the more general function field analogy between number fields and function fields. Just as we restrict attention to positive integers when talking about prime factorisation, it will be reasonable to restrict attention to monic polynomials ${P}$. We then have another analogous list of facts, proven very similarly to the corresponding list of facts for the integers:

• Every monic polynomial ${f \in {\mathbf F}_q[T]}$ has a factorisation

$\displaystyle f = P_1 \dots P_r$

into irreducible monic polynomials ${P_1,\dots,P_r \in {\mathbf F}_q[T]}$, which is unique up to rearrangement. Taking degrees, we obtain a partition

$\displaystyle \hbox{deg} f = \hbox{deg} P_1 + \dots + \hbox{deg} P_r$

of ${\hbox{deg} f}$.

• (Prime number theorem for polynomials) A randomly selected monic polynomial ${f \in {\mathbf F}_q[T]}$ of degree ${n}$ will be irreducible with probability ${\approx \frac{1}{n}}$ when ${q}$ is fixed and ${n}$ is large.
• If ${f \in {\mathbf F}_q[T]}$ is a random monic polynomial of degree ${n}$, and ${P_i}$ is a random irreducible factor of ${f = P_1 \dots P_r}$ (with each ${i}$ selected with probability ${\hbox{deg} P_i / n}$), then ${\hbox{deg} P_i}$ is approximately uniformly distributed in ${\{1,\dots,n\}}$ when ${q}$ is fixed and ${n}$ is large.
• The set of real numbers ${\{ \hbox{deg} P_i / n \}}$ arising from the factorisation ${f = P_1 \dots P_r}$ of a randomly selected polynomial ${f \in {\mathbf F}_q[T]}$ of degree ${n}$ converges (in a suitable sense) to the Poisson-Dirichlet process when ${q}$ is fixed and ${n}$ is large.

The above list of facts addressed the large ${n}$ limit of the polynomial ring ${{\mathbf F}_q[T]}$, where the order ${q}$ of the field is held fixed, but the degrees of the polynomials go to infinity. This is the limit that is most closely analogous to the integers ${{\bf Z}}$. However, there is another interesting asymptotic limit of polynomial rings to consider, namely the large ${q}$ limit where it is now the degree ${n}$ that is held fixed, but the order ${q}$ of the field goes to infinity. Actually to simplify the exposition we will use the slightly more restrictive limit where the characteristic ${p}$ of the field goes to infinity (again keeping the degree ${n}$ fixed), although all of the results proven below for the large ${p}$ limit turn out to be true as well in the large ${q}$ limit.

The large ${q}$ (or large ${p}$) limit is technically a different limit than the large ${n}$ limit, but in practice the asymptotic statistics of the two limits often agree quite closely. For instance, here is the prime number theorem in the large ${q}$ limit:

Theorem 1 (Prime number theorem) The probability that a random monic polynomial ${f \in {\mathbf F}_q[T]}$ of degree ${n}$ is irreducible is ${\frac{1}{n}+o(1)}$ in the limit where ${n}$ is fixed and the characteristic ${p}$ goes to infinity.

Proof: There are ${q^n}$ monic polynomials ${f \in {\mathbf F}_q[T]}$ of degree ${n}$. If ${f}$ is irreducible, then the ${n}$ zeroes of ${f}$ are distinct and lie in the finite field ${{\mathbf F}_{q^n}}$, but do not lie in any proper subfield of that field. Conversely, every element ${\alpha}$ of ${{\mathbf F}_{q^n}}$ that does not lie in a proper subfield is the root of a unique monic polynomial in ${{\mathbf F}_q[T]}$ of degree ${f}$ (the minimal polynomial of ${\alpha}$). Since the union of all the proper subfields of ${{\mathbf F}_{q^n}}$ has size ${o(q^n)}$, the total number of irreducible polynomials of degree ${n}$ is thus ${\frac{q^n - o(q^n)}{n}}$, and the claim follows. $\Box$

Remark 2 The above argument and inclusion-exclusion in fact gives the well known exact formula ${\frac{1}{n} \sum_{d|n} \mu(\frac{n}{d}) q^d}$ for the number of irreducible monic polynomials of degree ${n}$.

Now we can give a precise connection between the cycle distribution of a random permutation, and (the large ${p}$ limit of) the irreducible factorisation of a polynomial, giving a (somewhat indirect, but still connected) link between permutation cycle decomposition and integer factorisation:

Theorem 3 The partition ${\{ \hbox{deg}(P_1), \dots, \hbox{deg}(P_r) \}}$ of a random monic polynomial ${f= P_1 \dots P_r\in {\mathbf F}_q[T]}$ of degree ${n}$ converges in distribution to the partition ${\{ |C_1|, \dots, |C_r|\}}$ of a random permutation ${\sigma = C_1 \dots C_r \in S_n}$ of length ${n}$, in the limit where ${n}$ is fixed and the characteristic ${p}$ goes to infinity.

We can quickly prove this theorem as follows. We first need a basic fact:

Lemma 4 (Most polynomials square-free in large ${q}$ limit) A random monic polynomial ${f \in {\mathbf F}_q[T]}$ of degree ${n}$ will be square-free with probability ${1-o(1)}$ when ${n}$ is fixed and ${q}$ (or ${p}$) goes to infinity. In a similar spirit, two randomly selected monic polynomials ${f,g}$ of degree ${n,m}$ will be coprime with probability ${1-o(1)}$ if ${n,m}$ are fixed and ${q}$ or ${p}$ goes to infinity.

Proof: For any polynomial ${g}$ of degree ${m}$, the probability that ${f}$ is divisible by ${g^2}$ is at most ${1/q^{2m}}$. Summing over all polynomials of degree ${1 \leq m \leq n/2}$, and using the union bound, we see that the probability that ${f}$ is not squarefree is at most ${\sum_{1 \leq m \leq n/2} \frac{q^m}{q^{2m}} = o(1)}$, giving the first claim. For the second, observe from the first claim (and the fact that ${fg}$ has only a bounded number of factors) that ${fg}$ is squarefree with probability ${1-o(1)}$, giving the claim. $\Box$

Now we can prove the theorem. Elementary combinatorics tells us that the probability of a random permutation ${\sigma \in S_n}$ consisting of ${c_k}$ cycles of length ${k}$ for ${k=1,\dots,r}$, where ${c_k}$ are nonnegative integers with ${\sum_{k=1}^r k c_k = n}$, is precisely

$\displaystyle \frac{1}{\prod_{k=1}^r c_k! k^{c_k}},$

since there are ${\prod_{k=1}^r c_k! k^{c_k}}$ ways to write a given tuple of cycles ${C_1,\dots,C_r}$ in cycle notation in nondecreasing order of length, and ${n!}$ ways to select the labels for the cycle notation. On the other hand, by Theorem 1 (and using Lemma 4 to isolate the small number of cases involving repeated factors) the number of monic polynomials of degree ${n}$ that are the product of ${c_k}$ irreducible polynomials of degree ${k}$ is

$\displaystyle \frac{1}{\prod_{k=1}^r c_k!} \prod_{k=1}^r ( (\frac{1}{k}+o(1)) q^k )^{c_k} + o( q^n )$

which simplifies to

$\displaystyle \frac{1+o(1)}{\prod_{k=1}^r c_k! k^{c_k}} q^n,$

and the claim follows.

This was a fairly short calculation, but it still doesn’t quite explain why there is such a link between the cycle decomposition ${\sigma = C_1 \dots C_r}$ of permutations and the factorisation ${f = P_1 \dots P_r}$ of a polynomial. One immediate thought might be to try to link the multiplication structure of permutations in ${S_n}$ with the multiplication structure of polynomials; however, these structures are too dissimilar to set up a convincing analogy. For instance, the multiplication law on polynomials is abelian and non-invertible, whilst the multiplication law on ${S_n}$ is (extremely) non-abelian but invertible. Also, the multiplication of a degree ${n}$ and a degree ${m}$ polynomial is a degree ${n+m}$ polynomial, whereas the group multiplication law on permutations does not take a permutation in ${S_n}$ and a permutation in ${S_m}$ and return a permutation in ${S_{n+m}}$.

I recently found (after some discussions with Ben Green) what I feel to be a satisfying conceptual (as opposed to computational) explanation of this link, which I will place below the fold.

Suppose that ${A \subset B}$ are two subgroups of some ambient group ${G}$, with the index ${K := [B:A]}$ of ${A}$ in ${B}$ being finite. Then ${B}$ is the union of ${K}$ left cosets of ${A}$, thus ${B = SA}$ for some set ${S \subset B}$ of cardinality ${K}$. The elements ${s}$ of ${S}$ are not entirely arbitrary with regards to ${A}$. For instance, if ${A}$ is a normal subgroup of ${B}$, then for each ${s \in S}$, the conjugation map ${g \mapsto s^{-1} g s}$ preserves ${A}$. In particular, if we write ${A^s := s^{-1} A s}$ for the conjugate of ${A}$ by ${s}$, then

$\displaystyle A = A^s.$

Even if ${A}$ is not normal in ${B}$, it turns out that the conjugation map ${g \mapsto s^{-1} g s}$ approximately preserves ${A}$, if ${K}$ is bounded. To quantify this, let us call two subgroups ${A,B}$ ${K}$-commensurate for some ${K \geq 1}$ if one has

$\displaystyle [A : A \cap B], [B : A \cap B] \leq K.$

Proposition 1 Let ${A \subset B}$ be groups, with finite index ${K = [B:A]}$. Then for every ${s \in B}$, the groups ${A}$ and ${A^s}$ are ${K}$-commensurate, in fact

$\displaystyle [A : A \cap A^s ] = [A^s : A \cap A^s ] \leq K.$

Proof: One can partition ${B}$ into ${K}$ left translates ${xA}$ of ${A}$, as well as ${K}$ left translates ${yA^s}$ of ${A^s}$. Combining the partitions, we see that ${B}$ can be partitioned into at most ${K^2}$ non-empty sets of the form ${xA \cap yA^s}$. Each of these sets is easily seen to be a left translate of the subgroup ${A \cap A^s}$, thus ${[B: A \cap A^s] \leq K^2}$. Since

$\displaystyle [B: A \cap A^s] = [B:A] [A: A \cap A^s] = [B:A^s] [A^s: A \cap A^s]$

and ${[B:A] = [B:A^s]=K}$, we obtain the claim. $\Box$

One can replace the inclusion ${A \subset B}$ by commensurability, at the cost of some worsening of the constants:

Corollary 2 Let ${A, B}$ be ${K}$-commensurate subgroups of ${G}$. Then for every ${s \in B}$, the groups ${A}$ and ${A^s}$ are ${K^2}$-commensurate.

Proof: Applying the previous proposition with ${A}$ replaced by ${A \cap B}$, we see that for every ${s \in B}$, ${A \cap B}$ and ${(A \cap B)^s}$ are ${K}$-commensurate. Since ${A \cap B}$ and ${(A \cap B)^s}$ have index at most ${K}$ in ${A}$ and ${A^s}$ respectively, the claim follows. $\Box$

It turns out that a similar phenomenon holds for the more general concept of an approximate group, and gives a “classification” of all the approximate groups ${B}$ containing a given approximate group ${A}$ as a “bounded index approximate subgroup”. Recall that a ${K}$-approximate group ${A}$ in a group ${G}$ for some ${K \geq 1}$ is a symmetric subset of ${G}$ containing the identity, such that the product set ${A^2 := \{ a_1 a_2: a_1,a_2 \in A\}}$ can be covered by at most ${K}$ left translates of ${A}$ (and thus also ${K}$ right translates, by the symmetry of ${A}$). For simplicity we will restrict attention to finite approximate groups ${A}$ so that we can use their cardinality ${A}$ as a measure of size. We call finite two approximate groups ${A,B}$ ${K}$-commensurate if one has

$\displaystyle |A^2 \cap B^2| \geq \frac{1}{K} |A|, \frac{1}{K} |B|;$

note that this is consistent with the previous notion of commensurability for genuine groups.

Theorem 3 Let ${G}$ be a group, and let ${K_1,K_2,K_3 \geq 1}$ be real numbers. Let ${A}$ be a finite ${K_1}$-approximate group, and let ${B}$ be a symmetric subset of ${G}$ that contains ${A}$.

• (i) If ${B}$ is a ${K_2}$-approximate group with ${|B| \leq K_3 |A|}$, then one has ${B \subset SA}$ for some set ${S}$ of cardinality at most ${K_1 K_2 K_3}$. Furthermore, for each ${s \in S}$, the approximate groups ${A}$ and ${A^s}$ are ${K_1 K_2^5 K_3}$-commensurate.
• (ii) Conversely, if ${B \subset SA}$ for some set ${S}$ of cardinality at most ${K_3}$, and ${A}$ and ${A^s}$ are ${K_2}$-commensurate for all ${s \in S}$, then ${|B| \leq K_3 |A|}$, and ${B}$ is a ${K_1^6 K_2 K_3^2}$-approximate group.

Informally, the assertion that ${B}$ is an approximate group containing ${A}$ as a “bounded index approximate subgroup” is equivalent to ${B}$ being covered by a bounded number of shifts ${sA}$ of ${A}$, where ${s}$ approximately normalises ${A^2}$ in the sense that ${A^2}$ and ${(A^2)^s}$ have large intersection. Thus, to classify all such ${B}$, the problem essentially reduces to that of classifying those ${s}$ that approximately normalise ${A^2}$.

To prove the theorem, we recall some standard lemmas from arithmetic combinatorics, which are the foundation stones of the “Ruzsa calculus” that we will use to establish our results:

Lemma 4 (Ruzsa covering lemma) If ${A}$ and ${B}$ are finite non-empty subsets of ${G}$, then one has ${B \subset SAA^{-1}}$ for some set ${S \subset B}$ with cardinality ${|S| \leq \frac{|BA|}{|A|}}$.

Proof: We take ${S}$ to be a subset of ${B}$ with the property that the translates ${sA, s \in S}$ are disjoint in ${BA}$, and such that ${S}$ is maximal with respect to set inclusion. The required properties of ${S}$ are then easily verified. $\Box$

Lemma 5 (Ruzsa triangle inequality) If ${A,B,C}$ are finite non-empty subsets of ${G}$, then

$\displaystyle |A C^{-1}| \leq |A B^{-1}| |B C^{-1}| / |B|.$

Proof: If ${ac^{-1}}$ is an element of ${AC^{-1}}$ with ${a \in A}$ and ${c \in C}$, then from the identity ${ac^{-1} = (ab^{-1}) (bc^{-1})}$ we see that ${ac^{-1}}$ can be written as the product of an element of ${AB^{-1}}$ and an element of ${BC^{-1}}$ in at least ${|B|}$ distinct ways. The claim follows. $\Box$

Now we can prove (i). By the Ruzsa covering lemma, ${B}$ can be covered by at most

$\displaystyle \frac{|BA|}{|A|} \leq \frac{|B^2|}{|A|} \leq \frac{K_2 |B|}{|A|} \leq K_2 K_3$

left-translates of ${A^2}$, and hence by at most ${K_1 K_2 K_3}$ left-translates of ${A}$, thus ${B \subset SA}$ for some ${|S| \leq K_1 K_2 K_3}$. Since ${sA}$ only intersects ${B}$ if ${s \in BA}$, we may assume that

$\displaystyle S \subset BA \subset B^2$

and hence for any ${s \in S}$

$\displaystyle |A^s A| \leq |B^2 A B^2 A| \leq |B^6|$

$\displaystyle \leq K_2^5 |B| \leq K_2^5 K_3 |A|.$

By the Ruzsa covering lemma again, this implies that ${A^s}$ can be covered by at most ${K_2^5 K_3}$ left-translates of ${A^2}$, and hence by at most ${K_1 K_2^5 K_3}$ left-translates of ${A}$. By the pigeonhole principle, there thus exists a group element ${g}$ with

$\displaystyle |A^s \cap gA| \geq \frac{1}{K_1 K_2^5 K_3} |A|.$

Since

$\displaystyle |A^s \cap gA| \leq | (A^s \cap gA)^{-1} (A^s \cap gA)|$

and

$\displaystyle (A^s \cap gA)^{-1} (A^s \cap gA) \subset A^2 \cap (A^s)^2$

the claim follows.

Now we prove (ii). Clearly

$\displaystyle |B| \leq |S| |A| \leq K_3 |A|.$

Now we control the size of ${B^2 A}$. We have

$\displaystyle |B^2 A| \leq |SA SA^2| \leq K_3^2 \sup_{s \in S} |A s A^2| = K_3^2 \sup_{s \in S} |A^s A^2|.$

From the Ruzsa triangle inequality and symmetry we have

$\displaystyle |A^s A^2| \leq \frac{ |A^s (A^2 \cap (A^2)^s)| |(A^2 \cap (A^2)^s) A^2|}{|A^2 \cap (A^2)^s|}$

$\displaystyle \leq \frac{ |(A^3)^s| |A^4| }{|A|/K_2}$

$\displaystyle \leq K_2 \frac{ |A^3| |A^4| }{|A|}$

$\displaystyle \leq K_1^5 K_2 |A|$

and thus

$\displaystyle |B^2 A| \leq K_1^5 K_2 K_3^2 |A|.$

By the Ruzsa covering lemma, this implies that ${B^2}$ is covered by at most ${K_1^5 K_2 K_3^2}$ left-translates of ${A^2}$, hence by at most ${K_1^6 K_2 K_3^2}$ left-translates of ${A}$. Since ${A \subset B}$, the claim follows.

We now establish some auxiliary propositions about commensurability of approximate groups. The first claim is that commensurability is approximately transitive:

Proposition 6 Let ${A}$ be a ${K_1}$-approximate group, ${B}$ be a ${K_2}$-approximate group, and ${C}$ be a ${K_3}$-approximate group. If ${A}$ and ${B}$ are ${K_4}$-commensurate, and ${B}$ and ${C}$ are ${K_5}$-commensurate, then ${A}$ and ${C}$ are ${K_1^2 K_2^3 K_2^3 K_4 K_5 \max(K_1,K_3)}$-commensurate.

Proof: From two applications of the Ruzsa triangle inequality we have

$\displaystyle |AC| \leq \frac{|A (A^2 \cap B^2)| |(A^2 \cap B^2) (B^2 \cap C^2)| |(B^2 \cap C^2) C|}{|A^2 \cap B^2| |B^2 \cap C^2|}$

$\displaystyle \leq \frac{|A^3| |B^4| |C^3|}{ (|A|/K_4) (|B|/K_5)}$

$\displaystyle \leq K_4 K_5 \frac{K_1^2 |A| K_2^3 |B| K_3^2 |C|}{ |A| |B| }$

$\displaystyle = K_1^2 K_2^3 K_3^2 K_4 K_5 |C|.$

By the Ruzsa covering lemma, we may thus cover ${A}$ by at most ${K_1^2 K_2^3 K_3^2 K_4 K_5}$ left-translates of ${C^2}$, and hence by ${K_1^2 K_2^3 K_3^3 K_4 K_5}$ left-translates of ${C}$. By the pigeonhole principle, there thus exists a group element ${g}$ such that

$\displaystyle |A \cap gC| \geq \frac{1}{K_1^2 K_2^3 K_3^3 K_4 K_5} |A|,$

and so by arguing as in the proof of part (i) of the theorem we have

$\displaystyle |A^2 \cap C^2| \geq \frac{1}{K_1^2 K_2^3 K_3^3 K_4 K_5} |A|$

and similarly

$\displaystyle |A^2 \cap C^2| \geq \frac{1}{K_1^3 K_2^3 K_3^2 K_4 K_5} |C|$

and the claim follows. $\Box$

The next proposition asserts that the union and (modified) intersection of two commensurate approximate groups is again an approximate group:

Proposition 7 Let ${A}$ be a ${K_1}$-approximate group, ${B}$ be a ${K_2}$-approximate group, and suppose that ${A}$ and ${B}$ are ${K_3}$-commensurate. Then ${A \cup B}$ is a ${K_1 + K_2 + K_1^2 K_2^4 K_3 + K_1^4 K_2^2 K_3}$-approximate subgroup, and ${A^2 \cap B^2}$ is a ${K_1^6 K_2^3 K_3}$-approximate subgroup.

Using this proposition, one may obtain a variant of the previous theorem where the containment ${A \subset B}$ is replaced by commensurability; we leave the details to the interested reader.

Proof: We begin with ${A \cup B}$. Clearly ${A \cup B}$ is symmetric and contains the identity. We have ${(A \cup B)^2 = A^2 \cup AB \cup BA \cup B^2}$. The set ${A^2}$ is already covered by ${K_1}$ left translates of ${A}$, and hence of ${A \cup B}$; similarly ${B^2}$ is covered by ${K_2}$ left translates of ${A \cup B}$. As for ${AB}$, we observe from the Ruzsa triangle inequality that

$\displaystyle |AB^2| \leq \frac{|A (A^2 \cap B^2)| |(A^2 \cap B^2) B^2|}{|A^2 \cap B^2|}$

$\displaystyle \leq \frac{|A^3| |B^4|}{|A|/K_3}$

$\displaystyle \leq K_1^2 K_2^3 K_3 |B|$

and hence by the Ruzsa covering lemma, ${AB}$ is covered by at most ${K_1^2 K_2^3 K_3}$ left translates of ${B^2}$, and hence by ${K_1^2 K_2^4 K_3}$ left translates of ${B}$, and hence of ${A \cup B}$. Similarly ${BA}$ is covered by at most ${K_1^4 K_2^2 K_3}$ left translates of ${B}$. The claim follows.

Now we consider ${A^2 \cap B^2}$. Again, this is clearly symmetric and contains the identity. Repeating the previous arguments, we see that ${A}$ is covered by at most ${K_1^2 K_2^3 K_3}$ left-translates of ${B}$, and hence there exists a group element ${g}$ with

$\displaystyle |A \cap gB| \geq \frac{1}{K_1^2 K_2^3 K_3} |A|.$

Now observe that

$\displaystyle |(A^2 \cap B^2)^2 (A \cap gB)| \leq |A^5| \leq K_1^4 |A|$

and so by the Ruzsa covering lemma, ${(A^2 \cap B^2)^2}$ can be covered by at most ${K_1^6 K_2^3 K_3}$ left-translates of ${(A \cap gB) (A \cap gB)^{-1}}$. But this latter set is (as observed previously) contained in ${A^2 \cap B^2}$, and the claim follows. $\Box$

The lonely runner conjecture is the following open problem:

Conjecture 1 Suppose one has ${n \geq 1}$ runners on the unit circle ${{\bf R}/{\bf Z}}$, all starting at the origin and moving at different speeds. Then for each runner, there is at least one time ${t}$ for which that runner is “lonely” in the sense that it is separated by a distance at least ${1/n}$ from all other runners.

One can normalise the speed of the lonely runner to be zero, at which point the conjecture can be reformulated (after replacing ${n}$ by ${n+1}$) as follows:

Conjecture 2 Let ${v_1,\dots,v_n}$ be non-zero real numbers for some ${n \geq 1}$. Then there exists a real number ${t}$ such that the numbers ${tv_1,\dots,tv_n}$ are all a distance at least ${\frac{1}{n+1}}$ from the integers, thus ${\|tv_1\|_{{\bf R}/{\bf Z}},\dots,\|tv_n\|_{{\bf R}/{\bf Z}} \geq \frac{1}{n+1}}$ where ${\|x\|_{{\bf R}/{\bf Z}}}$ denotes the distance of ${x}$ to the nearest integer.

This conjecture has been proven for ${n \leq 7}$, but remains open for larger ${n}$. The bound ${\frac{1}{n+1}}$ is optimal, as can be seen by looking at the case ${v_i=i}$ and applying the Dirichlet approximation theorem. Note that for each non-zero ${v}$, the set ${\{ t \in {\bf R}: \|vt\|_{{\bf R}/{\bf Z}} \leq r \}}$ has (Banach) density ${2r}$ for any ${0 < r < 1/2}$, and from this and the union bound we can easily find ${t \in {\bf R}}$ for which

$\displaystyle \|tv_1\|_{{\bf R}/{\bf Z}},\dots,\|tv_n\|_{{\bf R}/{\bf Z}} \geq \frac{1}{2n}-\varepsilon$

for any ${\varepsilon>0}$, but it has proven to be quite challenging to remove the factor of ${2}$ to increase ${\frac{1}{2n}}$ to ${\frac{1}{n+1}}$. (As far as I know, even improving ${\frac{1}{2n}}$ to ${\frac{1+c}{2n}}$ for some absolute constant ${c>0}$ and sufficiently large ${n}$ remains open.)

The speeds ${v_1,\dots,v_n}$ in the above conjecture are arbitrary non-zero reals, but it has been known for some time that one can reduce without loss of generality to the case when the ${v_1,\dots,v_n}$ are rationals, or equivalently (by scaling) to the case where they are integers; see e.g. Section 4 of this paper of Bohman, Holzman, and Kleitman.

In this post I would like to remark on a slight refinement of this reduction, in which the speeds ${v_1,\dots,v_n}$ are integers of bounded size, where the bound depends on ${n}$. More precisely:

Proposition 3 In order to prove the lonely runner conjecture, it suffices to do so under the additional assumption that the ${v_1,\dots,v_n}$ are integers of size at most ${n^{Cn^2}}$, where ${C}$ is an (explicitly computable) absolute constant. (More precisely: if this restricted version of the lonely runner conjecture is true for all ${n \leq n_0}$, then the original version of the conjecture is also true for all ${n \leq n_0}$.)

In principle, this proposition allows one to verify the lonely runner conjecture for a given ${n}$ in finite time; however the number of cases to check with this proposition grows faster than exponentially in ${n}$, and so this is unfortunately not a feasible approach to verifying the lonely runner conjecture for more values of ${n}$ than currently known.

One of the key tools needed to prove this proposition is the following additive combinatorics result. Recall that a generalised arithmetic progression (or ${GAP}$) in the reals ${{\bf R}}$ is a set of the form

$\displaystyle P = \{ n_1 v_1 + \dots + n_d v_d: n_1,\dots,n_d \in {\bf Z}; |n_1| \leq N_1, \dots, |n_d| \leq N_d \}$

for some ${v_1,\dots,v_d \in {\bf R}}$ and ${N_1,\dots,N_d > 0}$; the quantity ${d}$ is called the rank of the progression. If ${t>0}$, the progression ${P}$ is said to be ${t}$-proper if the sums ${n_1 v_1 + \dots + n_d v_d}$ with ${|n_i| \leq t N_i}$ for ${i=1,\dots,d}$ are all distinct. We have

Lemma 4 (Progressions lie inside proper progressions) Let ${P}$ be a GAP of rank ${d}$ in the reals, and let ${t \geq 1}$. Then ${P}$ is contained in a ${t}$-proper GAP ${Q}$ of rank at most ${d}$, with

$\displaystyle |Q| \leq (2t)^d d^{6d^2} \prod_{i=1}^d (2N_i+1).$

Proof: See Theorem 2.1 of this paper of Bilu. (Very similar results can also be found in Theorem 3.40 of my book with Van Vu, or Theorem 1.10 of this paper of mine with Van Vu.) $\Box$

Now let ${n \geq 1}$, and assume inductively that the lonely runner conjecture has been proven for all smaller values of ${n}$, as well as for the current value of ${n}$ in the case that ${v_1,\dots,v_n}$ are integers of size at most ${n^{Cn^2}}$ for some sufficiently large ${C}$. We will show that the lonely runner conjecture holds in general for this choice of ${n}$.

let ${v_1,\dots,v_n}$ be non-zero real numbers. Let ${C_0}$ be a large absolute constant to be chosen later. From the above lemma applied to the GAP ${\{ n_1 v_1 + \dots + n_d v_d: n_1,\dots,n_d \in \{-1,0,1\}\}}$, one can find a ${n^{C_0n}}$-proper GAP ${Q}$ of rank at most ${n}$ containing ${\{v_1,\dots,v_n\}}$ such that

$\displaystyle |Q| \leq (6n^{C_0 n})^n n^{6n^2};$

in particular ${|Q| \leq n^{Cn^2}}$ if ${C}$ is large enough depending on ${C_0}$.

We write

$\displaystyle Q = \{ n_1 w_1 + \dots + n_d w_d: n_1,\dots,n_d \in {\bf Z}; |n_1| \leq N_1,\dots,|n_d| \leq N_d \}$

for some ${d \leq n}$, ${w_1,\dots,w_d}$, and ${N_1,\dots,N_d \geq 0}$. We thus have ${v_i = \phi(a_i)}$ for ${i=1,\dots,n}$, where ${\phi: {\bf R}^d \rightarrow {\bf R}}$ is the linear map ${\phi(n_1,\dots,n_d) := n_1 w_1 + \dots + n_d w_d}$ and ${a_1,\dots,a_n \in {\bf Z}^d}$ are non-zero and lie in the box ${\{ (n_1,\dots,n_d) \in {\bf R}^d: |n_1| \leq N_1,\dots,|n_d| \leq N_d \}}$.

We now need an elementary lemma that allows us to create a “collision” between two of the ${a_1,\dots,a_n}$ via a linear projection, without making any of the ${a_i}$ collide with the origin:

Lemma 5 Let ${a_1,\dots,a_n \in {\bf R}^d}$ be non-zero vectors that are not all collinear with the origin. Then, after replacing one or more of the ${a_i}$ with their negatives ${-a_i}$ if necessary, there exists a pair ${a_i,a_j}$ such that ${a_i-a_j \neq 0}$, and such that none of the ${a_1,\dots,a_n}$ is a scalar multiple of ${a_i-a_j}$.

Proof: We may assume that ${d \geq 2}$, since the ${d \leq 1}$ case is vacuous. Applying a generic linear projection to ${{\bf R}^2}$ (which does not affect collinearity, or the property that a given ${a_k}$ is a scalar multiple of ${a_i-a_j}$), we may then reduce to the case ${d=2}$.

By a rotation and relabeling, we may assume that ${a_1}$ lies on the negative ${x}$-axis; by flipping signs as necessary we may then assume that all of the ${a_2,\dots,a_n}$ lie in the closed right half-plane. As the ${a_i}$ are not all collinear with the origin, one of the ${a_i}$ lies off of the ${x}$-axis, by relabeling, we may assume that ${a_2}$ lies off of the ${x}$ axis and makes a minimal angle with the ${x}$-axis. Then the angle of ${a_2-a_1}$ with the ${x}$-axis is non-zero but smaller than any non-zero angle that any of the ${a_i}$ make with this axis, and so none of the ${a_i}$ are a scalar multiple of ${a_2-a_1}$, and the claim follows. $\Box$

We now return to the proof of the proposition. If the ${a_1,\dots,a_n}$ are all collinear with the origin, then ${\phi(a_1),\dots,\phi(a_n)}$ lie in a one-dimensional arithmetic progression ${\{ mv: |m| \leq |Q| \}}$, and then by rescaling we may take the ${v_1,\dots,v_n}$ to be integers of magnitude at most ${|Q| \leq n^{Cn}}$, at which point we are done by hypothesis. Thus, we may assume that the ${a_1,\dots,a_n}$ are not all collinear with the origin, and so by the above lemma and relabeling we may assume that ${a_n-a_1}$ is non-zero, and that none of the ${a_i}$ are scalar multiples of ${a_n-a_1}$.

We write

$\displaystyle a_n-a_1 = (c_1,\dots,c_d) \ \ \ \ \ (1)$

with ${|c_i| \leq 2 N_i}$ for ${i=1,\dots,d}$; by relabeling we may assume without loss of generality that ${c_d}$ is non-zero, and furthermore that

$\displaystyle \frac{|c_i|}{N_i} \leq \frac{|c_d|}{N_d}$

for ${i=1,\dots,d}$. We can also factor

$\displaystyle (c_1,\dots,c_d) = q (c'_1,\dots,c'_d) \ \ \ \ \ (2)$

where ${q}$ is a natural number and ${c'_1,\dots,c'_d}$ have no common factor.

We now define a variant ${\tilde \phi: {\bf R}^d \rightarrow {\bf R}}$ of ${\phi: {\bf R}^d \rightarrow {\bf R}}$ by the map

$\displaystyle \tilde \phi(n_1,\dots,n_d) := n_1 \tilde w_1 + \dots + n_{d-1} \tilde w_{d-1} - \frac{n_d}{c_d} (c_1 \tilde w_1 + \dots + c_{d-1} \tilde w_{d-1}),$

where the ${\tilde w_1,\dots,\tilde w_{d-1}}$ are real numbers that are linearly independent over ${{\bf Q}}$, whose precise value will not be of importance in our argument. This is a linear map with the property that ${\tilde \phi(a_n-a_1)=0}$, so that ${\tilde \phi(a_1),\dots,\tilde \phi(a_n)}$ consists of at most ${n-1}$ distinct real numbers, which are non-zero since none of the ${a_i}$ are scalar multiples of ${a_n-a_1}$, and the ${\tilde w_i}$ are linearly independent over ${{\bf Q}}$. As we are assuming inductively that the lonely runner conjecture holds for ${n-1}$, we conclude (after deleting duplicates) that there exists at least one real number ${\tilde t}$ such that

$\displaystyle \| \tilde t \tilde \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| \tilde t \tilde \phi(a_n) \|_{{\bf R}/{\bf Z}} \geq \frac{1}{n}.$

We would like to “approximate” ${\phi}$ by ${\tilde \phi}$ to then conclude that there is at least one real number ${t}$ such that

$\displaystyle \| t \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| t \phi(a_n) \|_{{\bf R}/{\bf Z}} \geq \frac{1}{n+1}.$

It turns out that we can do this by a Fourier-analytic argument taking advantage of the ${n^{C_0 n}}$-proper nature of ${Q}$. Firstly, we see from the Dirichlet approximation theorem that one has

$\displaystyle \| \tilde t \tilde \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| \tilde t \tilde \phi(a_n) \|_{{\bf R}/{\bf Z}} \leq \frac{1}{10 n^2}$

for a set ${\tilde t}$ of reals of (Banach) density ${\gg n^{-O(n)}}$. Thus, by the triangle inequality, we have

$\displaystyle \| \tilde t \tilde \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| \tilde t \tilde \phi(a_n) \|_{{\bf R}/{\bf Z}} \geq \frac{1}{n} - \frac{1}{10n^2}$

for a set ${\tilde t}$ of reals of density ${\gg n^{-O(n)}}$.

Applying a smooth Fourier multiplier of Littlewood-Paley type, one can find a trigonometric polynomial

$\displaystyle \eta(x) = \sum_{m: |m| \leq n^{C_0 n/10}} b_m e^{2\pi i mx}$

which takes values in ${[0,1]}$, is ${\gg 1}$ for ${\|x\|_{{\bf R}/{\bf Z}} \geq \frac{1}{n} - \frac{1}{10n^2}}$, and is no larger than ${O( n^{-100 C_0n} )}$ for ${\|x\|_{{\bf R}/{\bf Z}} \leq \frac{1}{n+1}}$. We then have

$\displaystyle \mathop{\bf E}_t \prod_{j=1}^n \eta( t \tilde \phi(a_j) ) \gg n^{-O(n)}$

where ${\mathop{\bf E}_t f(t)}$ denotes the mean value of a quasiperiodic function ${f}$ on the reals ${{\bf R}}$. We expand the left-hand side out as

$\displaystyle \sum_{m_1,\dots,m_n: m_1 \tilde \phi(a_1) + \dots + m_n \tilde \phi(a_n) = 0} b_{m_1} \dots b_{m_n}.$

From the genericity of ${\tilde w_1,\dots,\tilde w_n}$, we see that the constraint

$\displaystyle m_1 \tilde \phi(a_1) + \dots + m_n \tilde \phi(a_n) = 0$

occurs if and only if ${m_1 a_1 + \dots + m_n a_n}$ is a scalar multiple of ${a_n-a_1}$, or equivalently (by (1), (2)) an integer multiple of ${(c'_1,\dots,c'_d)}$. Thus

$\displaystyle \sum_{m_1,\dots,m_n: m_1 a_1 + \dots + m_n a_n \in {\bf Z} (c'_1,\dots,c'_d)} b_{m_1} \dots b_{m_n} \gg n^{-O(n)}. \ \ \ \ \ (3)$

Next, we consider the average

$\displaystyle \mathop{\bf E}_t \varphi( t \xi ) \prod_{j=1}^n \eta( t v_j ) \ \ \ \ \ (4)$

where

$\displaystyle \xi := c'_1 w_1 + \dots + c'_d w_d. \ \ \ \ \ (5)$

and ${\varphi}$ is the Dirichlet series

$\displaystyle \varphi(x) := \sum_{m: |m| \leq n^{C_0 n/2}} e^{2\pi i mx}.$

By Fourier expansion and writing ${v_j = \phi(a_j)}$, we may write (4) as

$\displaystyle \sum_{m,m_1,\dots,m_n: |m| \leq n^{C_0n/2}; m_1 \phi(a_1) + \dots + m_n \phi(a_n) = m \xi} b_{m_1} \dots b_{m_n}.$

The support of the ${b_{m_i}}$ implies that ${|m_i| \leq n^{C_0n/10}}$. Because of the ${n^{C_0 n}}$-properness of ${Q}$, we see (for ${n}$ large enough) that the equation

$\displaystyle m_1 \phi(a_1) + \dots + m_n \phi(a_n) = m \xi \ \ \ \ \ (6)$

implies that

$\displaystyle m_1 a_1 + \dots + m_n a_n \in {\bf Z} (c'_1,\dots,c'_d) \ \ \ \ \ (7)$

and conversely that (7) implies that (6) holds for some ${m}$ with ${|m| \leq n^{C_0 n/2}}$. From (3) we thus have

$\displaystyle \mathop{\bf E}_t \varphi( t \xi ) \prod_{j=1}^n \eta( t v_j ) \gg n^{-O(1)}.$

In particular, there exists a ${t}$ such that

$\displaystyle \varphi( t \xi ) \prod_{j=1}^n \eta( t v_j ) \gg n^{-O(1)}.$

Since ${\varphi}$ is bounded in magnitude by ${n^{C_0n/2}}$, and ${\eta}$ is bounded by ${1}$, we thus have

$\displaystyle \eta(t v_j) \gg n^{-C_0 n/2 - O(1)}$

for each ${1 \leq j \leq n}$, which by the size properties of ${\eta}$ implies that ${\|tv_j\|_{{\bf R}/{\bf Z}} \geq \frac{1}{n+1}}$ for all ${1 \leq j \leq n}$, giving the lonely runner conjecture for ${n}$.

Because of Euler’s identity ${e^{\pi i} + 1 = 0}$, the complex exponential is not injective: ${e^{z + 2\pi i k} = e^z}$ for any complex ${z}$ and integer ${k}$. As such, the complex logarithm ${z \mapsto \log z}$ is not well-defined as a single-valued function from ${{\bf C} \backslash \{0\}}$ to ${{\bf C}}$. However, after making a branch cut, one can create a branch of the logarithm which is single-valued. For instance, after removing the negative real axis ${(-\infty,0]}$, one has the standard branch ${\hbox{Log}: {\bf C} \backslash (-\infty,0] \rightarrow \{ z \in {\bf C}: |\hbox{Im} z| < \pi \}}$ of the logarithm, with ${\hbox{Log}(z)}$ defined as the unique choice of the complex logarithm of ${z}$ whose imaginary part has magnitude strictly less than ${\pi}$. This particular branch has a number of useful additional properties:

• The standard branch ${\hbox{Log}}$ is holomorphic on its domain ${{\bf C} \backslash (-\infty,0]}$.
• One has ${\hbox{Log}( \overline{z} ) = \overline{ \hbox{Log}(z) }}$ for all ${z}$ in the domain ${{\bf C} \backslash (-\infty,0]}$. In particular, if ${z \in {\bf C} \backslash (-\infty,0]}$ is real, then ${\hbox{Log} z}$ is real.
• One has ${\hbox{Log}( z^{-1} ) = - \hbox{Log}(z)}$ for all ${z}$ in the domain ${{\bf C} \backslash (-\infty,0]}$.

One can then also use the standard branch of the logarithm to create standard branches of other multi-valued functions, for instance creating a standard branch ${z \mapsto \exp( \frac{1}{2} \hbox{Log} z )}$ of the square root function. We caution however that the identity ${\hbox{Log}(zw) = \hbox{Log}(z) + \hbox{Log}(w)}$ can fail for the standard branch (or indeed for any branch of the logarithm).

One can extend this standard branch of the logarithm to ${n \times n}$ complex matrices, or (equivalently) to linear transformations ${T: V \rightarrow V}$ on an ${n}$-dimensional complex vector space ${V}$, provided that the spectrum of that matrix or transformation avoids the branch cut ${(-\infty,0]}$. Indeed, from the spectral theorem one can decompose any such ${T: V \rightarrow V}$ as the direct sum of operators ${T_\lambda: V_\lambda \rightarrow V_\lambda}$ on the non-trivial generalised eigenspaces ${V_\lambda}$ of ${T}$, where ${\lambda \in {\bf C} \backslash (-\infty,0]}$ ranges in the spectrum of ${T}$. For each component ${T_\lambda}$ of ${T}$, we define

$\displaystyle \hbox{Log}( T_\lambda ) = P_\lambda( T_\lambda )$

where ${P_\lambda}$ is the Taylor expansion of ${\hbox{Log}}$ at ${\lambda}$; as ${T_\lambda-\lambda}$ is nilpotent, only finitely many terms in this Taylor expansion are required. The logarithm ${\hbox{Log} T}$ is then defined as the direct sum of the ${\hbox{Log} T_\lambda}$.

The matrix standard branch of the logarithm has many pleasant and easily verified properties (often inherited from their scalar counterparts), whenever ${T: V \rightarrow V}$ has no spectrum in ${(-\infty,0]}$:

• (i) We have ${\exp( \hbox{Log} T ) = T}$.
• (ii) If ${T_1: V_1 \rightarrow V_1}$ and ${T_2: V_2 \rightarrow V_2}$ have no spectrum in ${(-\infty,0]}$, then ${\hbox{Log}( T_1 \oplus T_2 ) = \hbox{Log}(T_1) \oplus \hbox{Log}(T_2)}$.
• (iii) If ${T}$ has spectrum in a closed disk ${B(z,r)}$ in ${{\bf C} \backslash (-\infty,0]}$, then ${\hbox{Log}(T) = P_z(T)}$, where ${P_z}$ is the Taylor series of ${\hbox{Log}}$ around ${z}$ (which is absolutely convergent in ${B(z,r)}$).
• (iv) ${\hbox{Log}(T)}$ depends holomorphically on ${T}$. (Easily established from (ii), (iii), after covering the spectrum of ${T}$ by disjoint disks; alternatively, one can use the Cauchy integral representation ${\hbox{Log}(T) = \frac{1}{2\pi i} \int_\gamma \hbox{Log}(z)(z-T)^{-1}\ dz}$ for a contour ${\gamma}$ in the domain enclosing the spectrum of ${T}$.) In particular, the standard branch of the matrix logarithm is smooth.
• (v) If ${S: V \rightarrow W}$ is any invertible linear or antilinear map, then ${\hbox{Log}( STS^{-1} ) = S \hbox{Log}(T) S^{-1}}$. In particular, the standard branch of the logarithm commutes with matrix conjugations; and if ${T}$ is real with respect to a complex conjugation operation on ${V}$ (that is to say, an antilinear involution), then ${\hbox{Log}(T)}$ is real also.
• (vi) If ${T^*: V^* \rightarrow V^*}$ denotes the transpose of ${T}$ (with ${V^*}$ the complex dual of ${V}$), then ${\hbox{Log}(T^*) = \hbox{Log}(T)^*}$. Similarly, if ${T^\dagger: V^\dagger \rightarrow V^\dagger}$ denotes the adjoint of ${T}$ (with ${V^\dagger}$ the complex conjugate of ${V^*}$, i.e. ${V^*}$ with the conjugated multiplication map ${(c,z) \mapsto \overline{c} z}$), then ${\hbox{Log}(T^\dagger) = \hbox{Log}(T)^\dagger}$.
• (vii) One has ${\hbox{Log}(T^{-1}) = - \hbox{Log}( T )}$.
• (viii) If ${\sigma(T)}$ denotes the spectrum of ${T}$, then ${\sigma(\hbox{Log} T) = \hbox{Log} \sigma(T)}$.

As a quick application of the standard branch of the matrix logarithm, we have

Proposition 1 Let ${G}$ be one of the following matrix groups: ${GL_n({\bf C})}$, ${GL_n({\bf R})}$, ${U_n({\bf C})}$, ${O(Q)}$, ${Sp_{2n}({\bf C})}$, or ${Sp_{2n}({\bf R})}$, where ${Q: {\bf R}^n \rightarrow {\bf R}}$ is a non-degenerate real quadratic form (so ${O(Q)}$ is isomorphic to a (possibly indefinite) orthogonal group ${O(k,n-k)}$ for some ${0 \leq k \leq n}$. Then any element ${T}$ of ${G}$ whose spectrum avoids ${(-\infty,0]}$ is exponential, that is to say ${T = \exp(X)}$ for some ${X}$ in the Lie algebra ${{\mathfrak g}}$ of ${G}$.

Proof: We just prove this for ${G=O(Q)}$, as the other cases are similar (or a bit simpler). If ${T \in O(Q)}$, then (viewing ${T}$ as a complex-linear map on ${{\bf C}^n}$, and using the complex bilinear form associated to ${Q}$ to identify ${{\bf C}^n}$ with its complex dual ${({\bf C}^n)^*}$, then ${T}$ is real and ${T^{*-1} = T}$. By the properties (v), (vi), (vii) of the standard branch of the matrix logarithm, we conclude that ${\hbox{Log} T}$ is real and ${- \hbox{Log}(T)^* = \hbox{Log}(T)}$, and so ${\hbox{Log}(T)}$ lies in the Lie algebra ${{\mathfrak g} = {\mathfrak o}(Q)}$, and the claim now follows from (i). $\Box$

Exercise 2 Show that ${\hbox{diag}(-\lambda, -1/\lambda)}$ is not exponential in ${GL_2({\bf R})}$ if ${-\lambda \in (-\infty,0) \backslash \{-1\}}$. Thus we see that the branch cut in the above proposition is largely necessary. See this paper of Djokovic for a more complete description of the image of the exponential map in classical groups, as well as this previous blog post for some more discussion of the surjectivity (or lack thereof) of the exponential map in Lie groups.

For a slightly less quick application of the standard branch, we have the following result (recently worked out in the answers to this MathOverflow question):

Proposition 3 Let ${T}$ be an element of the split orthogonal group ${O(n,n)}$ which lies in the connected component of the identity. Then ${\hbox{det}(1+T) \geq 0}$.

The requirement that ${T}$ lie in the identity component is necessary, as the counterexample ${T = \hbox{diag}(-\lambda, -1/\lambda )}$ for ${\lambda \in (-\infty,-1) \cup (-1,0)}$ shows.

Proof: We think of ${T}$ as a (real) linear transformation on ${{\bf C}^{2n}}$, and write ${Q}$ for the quadratic form associated to ${O(n,n)}$, so that ${O(n,n) \equiv O(Q)}$. We can split ${{\bf C}^{2n} = V_1 \oplus V_2}$, where ${V_1}$ is the sum of all the generalised eigenspaces corresponding to eigenvalues in ${(-\infty,0]}$, and ${V_2}$ is the sum of all the remaining eigenspaces. Since ${T}$ and ${(-\infty,0]}$ are real, ${V_1,V_2}$ are real (i.e. complex-conjugation invariant) also. For ${i=1,2}$, the restriction ${T_i: V_i \rightarrow V_i}$ of ${T}$ to ${V_i}$ then lies in ${O(Q_i)}$, where ${Q_i}$ is the restriction of ${Q}$ to ${V_i}$, and

$\displaystyle \hbox{det}(1+T) = \hbox{det}(1+T_1) \hbox{det}(1+T_2).$

The spectrum of ${T_2}$ consists of positive reals, as well as complex pairs ${\lambda, \overline{\lambda}}$ (with equal multiplicity), so ${\hbox{det}(1+T_2) > 0}$. From the preceding proposition we have ${T_2 = \exp( X_2 )}$ for some ${X_2 \in {\mathfrak o}(Q_2)}$; this will be important later.

It remains to show that ${\hbox{det}(1+T_1) \geq 0}$. If ${T_1}$ has spectrum at ${-1}$ then we are done, so we may assume that ${T_1}$ has spectrum only at ${(-\infty,-1) \cup (-1,0)}$ (being invertible, ${T}$ has no spectrum at ${0}$). We split ${V_1 = V_3 \oplus V_4}$, where ${V_3,V_4}$ correspond to the portions of the spectrum in ${(-\infty,-1)}$, ${(-1,0)}$; these are real, ${T}$-invariant spaces. We observe that if ${V_\lambda, V_\mu}$ are generalised eigenspaces of ${T}$ with ${\lambda \mu \neq 1}$, then ${V_\lambda, V_\mu}$ are orthogonal with respect to the (complex-bilinear) inner product ${\cdot}$ associated with ${Q}$; this is easiest to see first for the actual eigenspaces (since ${ \lambda \mu u \cdot v = Tu \cdot Tv = u \cdot v}$ for all ${u \in V_\lambda, v \in V_\mu}$), and the extension to generalised eigenvectors then follows from a routine induction. From this we see that ${V_1}$ is orthogonal to ${V_2}$, and ${V_3}$ and ${V_4}$ are null spaces, which by the non-degeneracy of ${Q}$ (and hence of the restriction ${Q_1}$ of ${Q}$ to ${V_1}$) forces ${V_3}$ to have the same dimension as ${V_4}$, indeed ${Q}$ now gives an identification of ${V_3^*}$ with ${V_4}$. If we let ${T_3, T_4}$ be the restrictions of ${T}$ to ${V_3,V_4}$, we thus identify ${T_4}$ with ${T_3^{*-1}}$, since ${T}$ lies in ${O(Q)}$; in particular ${T_3}$ is invertible. Thus

$\displaystyle \hbox{det}(1+T_1) = \hbox{det}(1 + T_3) \hbox{det}( 1 + T_3^{*-1} ) = \hbox{det}(T_3)^{-1} \hbox{det}(1+T_3)^2$

and so it suffices to show that ${\hbox{det}(T_3) > 0}$.

At this point we need to use the hypothesis that ${T}$ lies in the identity component of ${O(n,n)}$. This implies (by a continuity argument) that the restriction of ${T}$ to any maximal-dimensional positive subspace has positive determinant (since such a restriction cannot be singular, as this would mean that ${T}$ positive norm vector would map to a non-positive norm vector). Now, as ${V_3,V_4}$ have equal dimension, ${Q_1}$ has a balanced signature, so ${Q_2}$ does also. Since ${T_2 = \exp(X_2)}$, ${T_2}$ already lies in the identity component of ${O(Q_2)}$, and so has positive determinant on any maximal-dimensional positive subspace of ${V_2}$. We conclude that ${T_1}$ has positive determinant on any maximal-dimensional positive subspace of ${V_1}$.

We choose a complex basis of ${V_3}$, to identify ${V_3}$ with ${V_3^*}$, which has already been identified with ${V_4}$. (In coordinates, ${V_3,V_4}$ are now both of the form ${{\bf C}^m}$, and ${Q( v \oplus w ) = v \cdot w}$ for ${v,w \in {\bf C}^m}$.) Then ${\{ v \oplus v: v \in V_3 \}}$ becomes a maximal positive subspace of ${V_1}$, and the restriction of ${T_1}$ to this subspace is conjugate to ${T_3 + T_3^{*-1}}$, so that

$\displaystyle \hbox{det}( T_3 + T_3^{*-1} ) > 0.$

But since ${\hbox{det}( T_3 + T_3^{*-1} ) = \hbox{det}(T_3) \hbox{det}( 1 + T_3^{-1} T_3^{*-1} )}$ and ${ 1 + T_3^{-1} T_3^{*-1}}$ is positive definite, so ${\hbox{det}(T_3)>0}$ as required. $\Box$