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

The lonely runner conjecture is the following open problem:

Conjecture 1Suppose one has runners on the unit circle , all starting at the origin and moving at different speeds. Then for each runner, there is at least one time for which that runner is “lonely” in the sense that it is separated by a distance at least 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 by ) as follows:

Conjecture 2Let be non-zero real numbers for some . Then there exists a real number such that the numbers are all a distance at least from the integers, thus where denotes the distance of to the nearest integer.

This conjecture has been proven for , but remains open for larger . The bound is optimal, as can be seen by looking at the case and applying the Dirichlet approximation theorem. Note that for each non-zero , the set has (Banach) density for any , and from this and the union bound we can easily find for which

for any , but it has proven to be quite challenging to remove the factor of to increase to . (As far as I know, even improving to for some absolute constant and sufficiently large remains open.)

The speeds 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 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 are integers of *bounded size*, where the bound depends on . More precisely:

Proposition 3In order to prove the lonely runner conjecture, it suffices to do so under the additional assumption that the are integers of size at most , where is an (explicitly computable) absolute constant. (More precisely: if this restricted version of the lonely runner conjecture is true for all , then the original version of the conjecture is also true for all .)

In principle, this proposition allows one to verify the lonely runner conjecture for a given in finite time; however the number of cases to check with this proposition grows faster than exponentially in , and so this is unfortunately not a feasible approach to verifying the lonely runner conjecture for more values of 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 ) in the reals is a set of the form

for some and ; the quantity is called the *rank* of the progression. If , the progression is said to be *-proper* if the sums with for are all distinct. We have

Lemma 4 (Progressions lie inside proper progressions)Let be a GAP of rank in the reals, and let . Then is contained in a -proper GAP of rank at most , with

*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.)

Now let , and assume inductively that the lonely runner conjecture has been proven for all smaller values of , as well as for the current value of in the case that are integers of size at most for some sufficiently large . We will show that the lonely runner conjecture holds in general for this choice of .

let be non-zero real numbers. Let be a large absolute constant to be chosen later. From the above lemma applied to the GAP , one can find a -proper GAP of rank at most containing such that

in particular if is large enough depending on .

We write

for some , , and . We thus have for , where is the linear map and are non-zero and lie in the box .

We now need an elementary lemma that allows us to create a “collision” between two of the via a linear projection, without making any of the collide with the origin:

Lemma 5Let be non-zero vectors that are not all collinear with the origin. Then, after replacing one or more of the with their negatives if necessary, there exists a pair such that , and such that none of the is a scalar multiple of .

*Proof:* We may assume that , since the case is vacuous. Applying a generic linear projection to (which does not affect collinearity, or the property that a given is a scalar multiple of ), we may then reduce to the case .

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

We now return to the proof of the proposition. If the are all collinear with the origin, then lie in a one-dimensional arithmetic progression , and then by rescaling we may take the to be integers of magnitude at most , at which point we are done by hypothesis. Thus, we may assume that the are not all collinear with the origin, and so by the above lemma and relabeling we may assume that is non-zero, and that none of the are scalar multiples of .

with for ; by relabeling we may assume without loss of generality that is non-zero, and furthermore that

where is a natural number and have no common factor.

We now define a variant of by the map

where the are real numbers that are linearly independent over , whose precise value will not be of importance in our argument. This is a linear map with the property that , so that consists of at most distinct real numbers, which are non-zero since none of the are scalar multiples of , and the are linearly independent over . As we are assuming inductively that the lonely runner conjecture holds for , we conclude (after deleting duplicates) that there exists at least one real number such that

We would like to “approximate” by to then conclude that there is at least one real number such that

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

for a set of reals of (Banach) density . Thus, by the triangle inequality, we have

for a set of reals of density .

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

which takes values in , is for , and is no larger than for . We then have

where denotes the mean value of a quasiperiodic function on the reals . We expand the left-hand side out as

From the genericity of , we see that the constraint

occurs if and only if is a scalar multiple of , or equivalently (by (1), (2)) an integer multiple of . Thus

By Fourier expansion and writing , we may write (4) as

The support of the implies that . Because of the -properness of , we see (for large enough) that the equation

and conversely that (7) implies that (6) holds for some with . From (3) we thus have

In particular, there exists a such that

Since is bounded in magnitude by , and is bounded by , we thus have

for each , which by the size properties of implies that for all , giving the lonely runner conjecture for .

Because of Euler’s identity , the complex exponential is not injective: for any complex and integer . As such, the complex logarithm is not well-defined as a single-valued function from to . 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 , one has the *standard branch* of the logarithm, with defined as the unique choice of the complex logarithm of whose imaginary part has magnitude strictly less than . This particular branch has a number of useful additional properties:

- The standard branch is holomorphic on its domain .
- One has for all in the domain . In particular, if is real, then is real.
- One has for all in the domain .

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 of the square root function. We caution however that the identity can fail for the standard branch (or indeed for any branch of the logarithm).

One can extend this standard branch of the logarithm to complex matrices, or (equivalently) to linear transformations on an -dimensional complex vector space , provided that the spectrum of that matrix or transformation avoids the branch cut . Indeed, from the spectral theorem one can decompose any such as the direct sum of operators on the non-trivial generalised eigenspaces of , where ranges in the spectrum of . For each component of , we define

where is the Taylor expansion of at ; as is nilpotent, only finitely many terms in this Taylor expansion are required. The logarithm is then defined as the direct sum of the .

The matrix standard branch of the logarithm has many pleasant and easily verified properties (often inherited from their scalar counterparts), whenever has no spectrum in :

- (i) We have .
- (ii) If and have no spectrum in , then .
- (iii) If has spectrum in a closed disk in , then , where is the Taylor series of around (which is absolutely convergent in ).
- (iv) depends holomorphically on . (Easily established from (ii), (iii), after covering the spectrum of by disjoint disks; alternatively, one can use the Cauchy integral representation for a contour in the domain enclosing the spectrum of .) In particular, the standard branch of the matrix logarithm is smooth.
- (v) If is any invertible linear or antilinear map, then . In particular, the standard branch of the logarithm commutes with matrix conjugations; and if is real with respect to a complex conjugation operation on (that is to say, an antilinear involution), then is real also.
- (vi) If denotes the transpose of (with the complex dual of ), then . Similarly, if denotes the adjoint of (with the complex conjugate of , i.e. with the conjugated multiplication map ), then .
- (vii) One has .
- (viii) If denotes the spectrum of , then .

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

Proposition 1Let be one of the following matrix groups: , , , , , or , where is a non-degenerate real quadratic form (so is isomorphic to a (possibly indefinite) orthogonal group for some . Then any element of whose spectrum avoids is exponential, that is to say for some in the Lie algebra of .

*Proof:* We just prove this for , as the other cases are similar (or a bit simpler). If , then (viewing as a complex-linear map on , and using the complex bilinear form associated to to identify with its complex dual , then is real and . By the properties (v), (vi), (vii) of the standard branch of the matrix logarithm, we conclude that is real and , and so lies in the Lie algebra , and the claim now follows from (i).

Exercise 2Show that is not exponential in if . 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 3Let be an element of the split orthogonal group which lies in the connected component of the identity. Then .

The requirement that lie in the identity component is necessary, as the counterexample for shows.

*Proof:* We think of as a (real) linear transformation on , and write for the quadratic form associated to , so that . We can split , where is the sum of all the generalised eigenspaces corresponding to eigenvalues in , and is the sum of all the remaining eigenspaces. Since and are real, are real (i.e. complex-conjugation invariant) also. For , the restriction of to then lies in , where is the restriction of to , and

The spectrum of consists of positive reals, as well as complex pairs (with equal multiplicity), so . From the preceding proposition we have for some ; this will be important later.

It remains to show that . If has spectrum at then we are done, so we may assume that has spectrum only at (being invertible, has no spectrum at ). We split , where correspond to the portions of the spectrum in , ; these are real, -invariant spaces. We observe that if are generalised eigenspaces of with , then are orthogonal with respect to the (complex-bilinear) inner product associated with ; this is easiest to see first for the actual eigenspaces (since for all ), and the extension to generalised eigenvectors then follows from a routine induction. From this we see that is orthogonal to , and and are null spaces, which by the non-degeneracy of (and hence of the restriction of to ) forces to have the same dimension as , indeed now gives an identification of with . If we let be the restrictions of to , we thus identify with , since lies in ; in particular is invertible. Thus

and so it suffices to show that .

At this point we need to use the hypothesis that lies in the identity component of . This implies (by a continuity argument) that the restriction of to any maximal-dimensional positive subspace has positive determinant (since such a restriction cannot be singular, as this would mean that positive norm vector would map to a non-positive norm vector). Now, as have equal dimension, has a balanced signature, so does also. Since , already lies in the identity component of , and so has positive determinant on any maximal-dimensional positive subspace of . We conclude that has positive determinant on any maximal-dimensional positive subspace of .

We choose a complex basis of , to identify with , which has already been identified with . (In coordinates, are now both of the form , and for .) Then becomes a maximal positive subspace of , and the restriction of to this subspace is conjugate to , so that

But since and is positive definite, so as required.

The Euler equations for three-dimensional incompressible inviscid fluid flow are

where is the velocity field, and is the pressure field. For the purposes of this post, we will ignore all issues of decay or regularity of the fields in question, assuming that they are as smooth and rapidly decreasing as needed to justify all the formal calculations here; in particular, we will apply inverse operators such as or formally, assuming that these inverses are well defined on the functions they are applied to.

Meanwhile, the surface quasi-geostrophic (SQG) equation is given by

where is the active scalar, and is the velocity field. The SQG equations are often used as a toy model for the 3D Euler equations, as they share many of the same features (e.g. vortex stretching); see this paper of Constantin, Majda, and Tabak for more discussion (or this previous blog post).

I recently found a more direct way to connect the two equations. We first recall that the Euler equations can be placed in *vorticity-stream* form by focusing on the vorticity . Indeed, taking the curl of (1), we obtain the vorticity equation

while the velocity can be recovered from the vorticity via the Biot-Savart law

The system (4), (5) has some features in common with the system (2), (3); in (2) it is a scalar field that is being transported by a divergence-free vector field , which is a linear function of the scalar field as per (3), whereas in (4) it is a vector field that is being transported (in the Lie derivative sense) by a divergence-free vector field , which is a linear function of the vector field as per (5). However, the system (4), (5) is in three dimensions whilst (2), (3) is in two spatial dimensions, the dynamical field is a scalar field for SQG and a vector field for Euler, and the relationship between the velocity field and the dynamical field is given by a zeroth order Fourier multiplier in (3) and a order operator in (5).

However, we can make the two equations more closely resemble each other as follows. We first consider the generalisation

where is an invertible, self-adjoint, positive-definite zeroth order Fourier multiplier that maps divergence-free vector fields to divergence-free vector fields. The Euler equations then correspond to the case when is the identity operator. As discussed in this previous blog post (which used to denote the inverse of the operator denoted here as ), this generalised Euler system has many of the same features as the original Euler equation, such as a conserved Hamiltonian

the Kelvin circulation theorem, and conservation of helicity

Also, if we require to be divergence-free at time zero, it remains divergence-free at all later times.

Let us consider “two-and-a-half-dimensional” solutions to the system (6), (7), in which do not depend on the vertical coordinate , thus

and

but we allow the vertical components to be non-zero. For this to be consistent, we also require to commute with translations in the direction. As all derivatives in the direction now vanish, we can simplify (6) to

where is the two-dimensional material derivative

Also, divergence-free nature of then becomes

In particular, we may (formally, at least) write

for some scalar field , so that (7) becomes

The first two components of (8) become

which rearranges using (9) to

Formally, we may integrate this system to obtain the transport equation

Finally, the last component of (8) is

At this point, we make the following choice for :

where is a real constant and is the Leray projection onto divergence-free vector fields. One can verify that for large enough , is a self-adjoint positive definite zeroth order Fourier multiplier from divergence free vector fields to divergence-free vector fields. With this choice, we see from (10) that

so that (12) simplifies to

This implies (formally at least) that if vanishes at time zero, then it vanishes for all time. Setting , we then have from (10) that

and from (11) we then recover the SQG system (2), (3). To put it another way, if and solve the SQG system, then by setting

then solve the modified Euler system (6), (7) with given by (13).

We have , so the Hamiltonian for the modified Euler system in this case is formally a scalar multiple of the conserved quantity . The momentum for the modified Euler system is formally a scalar multiple of the conserved quantity , while the vortex stream lines that are preserved by the modified Euler flow become the level sets of the active scalar that are preserved by the SQG flow. On the other hand, the helicity vanishes, and other conserved quantities for SQG (such as the Hamiltonian ) do not seem to correspond to conserved quantities of the modified Euler system. This is not terribly surprising; a low-dimensional flow may well have a richer family of conservation laws than the higher-dimensional system that it is embedded in.

An extremely large portion of mathematics is concerned with locating solutions to equations such as

for in some suitable domain space (either finite-dimensional or infinite-dimensional), and various maps or . To solve the fixed point iteration equation (1), the simplest general method available is the fixed point iteration method: one starts with an initial *approximate solution* to (1), so that , and then recursively constructs the sequence by . If behaves enough like a “contraction”, and the domain is complete, then one can expect the to converge to a limit , which should then be a solution to (1). For instance, if is a map from a metric space to itself, which is a contraction in the sense that

for all and some , then with as above we have

for any , and so the distances between successive elements of the sequence decay at at least a geometric rate. This leads to the contraction mapping theorem, which has many important consequences, such as the inverse function theorem and the Picard existence theorem.

A slightly more complicated instance of this strategy arises when trying to *linearise* a complex map defined in a neighbourhood of a fixed point. For simplicity we normalise the fixed point to be the origin, thus and . When studying the complex dynamics , , of such a map, it can be useful to try to conjugate to another function , where is a holomorphic function defined and invertible near with , since the dynamics of will be conjguate to that of . Note that if and , then from the chain rule any conjugate of will also have and . Thus, the “simplest” function one can hope to conjugate to is the linear function . Let us say that is *linearisable* (around ) if it is conjugate to in some neighbourhood of . Equivalently, is linearisable if there is a solution to the Schröder equation

for some defined and invertible in a neighbourhood of with , and all sufficiently close to . (The Schröder equation is normalised somewhat differently in the literature, but this form is equivalent to the usual form, at least when is non-zero.) Note that if solves the above equation, then so does for any non-zero , so we may normalise in addition to , which also ensures local invertibility from the inverse function theorem. (Note from winding number considerations that cannot be invertible near zero if vanishes.)

We have the following basic result of Koenigs:

Theorem 1 (Koenig’s linearisation theorem)Let be a holomorphic function defined near with and . If (attracting case) or (repelling case), then is linearisable near zero.

*Proof:* Observe that if solve (2), then solve (2) also (in a sufficiently small neighbourhood of zero). Thus we may reduce to the attractive case .

Let be a sufficiently small radius, and let denote the space of holomorphic functions on the complex disk with and . We can view the Schröder equation (2) as a fixed point equation

where is the partially defined function on that maps a function to the function defined by

assuming that is well-defined on the range of (this is why is only partially defined).

We can solve this equation by the fixed point iteration method, if is small enough. Namely, we start with being the identity map, and set , etc. We equip with the uniform metric . Observe that if , and is small enough, then takes values in , and are well-defined and lie in . Also, since is smooth and has derivative at , we have

if , and is sufficiently small depending on . This is not yet enough to establish the required contraction (thanks to Mario Bonk for pointing this out); but observe that the function is holomorphic on and bounded by on the boundary of this ball (or slightly within this boundary), so by the maximum principle we see that

on all of , and in particular

on . Putting all this together, we see that

since , we thus obtain a contraction on the ball if is small enough (and sufficiently small depending on ). From this (and the completeness of , which follows from Morera’s theorem) we see that the iteration converges (exponentially fast) to a limit which is a fixed point of , and thus solves Schröder’s equation, as required.

Koenig’s linearisation theorem leaves open the *indifferent case* when . In the *rationally indifferent* case when for some natural number , there is an obvious obstruction to linearisability, namely that (in particular, linearisation is not possible in this case when is a non-trivial rational function). An obstruction is also present in some *irrationally indifferent* cases (where but for any natural number ), if is sufficiently close to various roots of unity; the first result of this form is due to Cremer, and the optimal result of this type for quadratic maps was established by Yoccoz. In the other direction, we have the following result of Siegel:

Theorem 2 (Siegel’s linearisation theorem)Let be a holomorphic function defined near with and . If and one has the Diophantine condition for all natural numbers and some constant , then is linearisable at .

The Diophantine condition can be relaxed to a more general condition involving the rational exponents of the phase of ; this was worked out by Brjuno, with the condition matching the one later obtained by Yoccoz. Amusingly, while the set of Diophantine numbers (and hence the set of linearisable ) has full measure on the unit circle, the set of non-linearisable is generic (the complement of countably many nowhere dense sets) due to the above-mentioned work of Cremer, leading to a striking disparity between the measure-theoretic and category notions of “largeness”.

Siegel’s theorem does not seem to be provable using a fixed point iteration method. However, it can be established by modifying another basic method to solve equations, namely Newton’s method. Let us first review how this method works to solve the equation for some smooth function defined on an interval . We suppose we have some initial approximant to this equation, with small but not necessarily zero. To make the analysis more quantitative, let us suppose that the interval lies in for some , and we have the estimates

for some and and all (the factors of are present to make “dimensionless”).

Lemma 3Under the above hypotheses, we can find with such thatIn particular, setting , , and , we have , and

for all .

The crucial point here is that the new error is roughly the square of the previous error . This leads to extremely fast (double-exponential) improvement in the error upon iteration, which is more than enough to absorb the exponential losses coming from the factor.

*Proof:* If for some absolute constants then we may simply take , so we may assume that for some small and large . Using the Newton approximation we are led to the choice

for . From the hypotheses on and the smallness hypothesis on we certainly have . From Taylor’s theorem with remainder we have

and the claim follows.

We can iterate this procedure; starting with as above, we obtain a sequence of nested intervals with , and with evolving by the recursive equations and estimates

If is sufficiently small depending on , we see that converges rapidly to zero (indeed, we can inductively obtain a bound of the form for some large absolute constant if is small enough), and converges to a limit which then solves the equation by the continuity of .

As I recently learned from Zhiqiang Li, a similar scheme works to prove Siegel’s theorem, as can be found for instance in this text of Carleson and Gamelin. The key is the following analogue of Lemma 3.

Lemma 4Let be a complex number with and for all natural numbers . Let , and let be a holomorphic function with , , andfor all and some . Let , and set . Then there exists an injective holomorphic function and a holomorphic function such that

and

for all and some .

*Proof:* By scaling we may normalise . If for some constants , then we can simply take to be the identity and , so we may assume that for some small and large .

To motivate the choice of , we write and , with and viewed as small. We would like to have , which expands as

As and are both small, we can heuristically approximate up to quadratic errors (compare with the Newton approximation ), and arrive at the equation

This equation can be solved by Taylor series; the function vanishes to second order at the origin and thus has a Taylor expansion

and then has a Taylor expansion

We take this as our definition of , define , and then define implicitly via (4).

Let us now justify that this choice works. By (3) and the generalised Cauchy integral formula, we have for all ; by the Diophantine assumption on , we thus have . In particular, converges on , and on the disk (say) we have the bounds

In particular, as is so small, we see that maps injectively to and to , and the inverse maps to . From (3) we see that maps to , and so if we set to be the function , then is a holomorphic function obeying (4). Expanding (4) in terms of and as before, and also writing , we have

for , which by (5) simplifies to

From (6), the fundamental theorem of calculus, and the smallness of we have

and thus

From (3) and the Cauchy integral formula we have on (say) , and so from (6) and the fundamental theorem of calculus we conclude that

on , and the claim follows.

If we set , , and to be sufficiently small, then (since vanishes to second order at the origin), the hypotheses of this lemma will be obeyed for some sufficiently small . Iterating the lemma (and halving repeatedly), we can then find sequences , injective holomorphic functions and holomorphic functions such that one has the recursive identities and estimates

for all and . By construction, decreases to a positive radius that is a constant multiple of , while (for small enough) converges double-exponentially to zero, so in particular converges uniformly to on . Also, is close enough to the identity, the compositions are uniformly convergent on with and . From this we have

on , and on taking limits using Morera’s theorem we obtain a holomorphic function defined near with , , and

obtaining the required linearisation.

Remark 5The idea of using a Newton-type method to obtain error terms that decay double-exponentially, and can therefore absorb exponential losses in the iteration, also occurs in KAM theory and in Nash-Moser iteration, presumably due to Siegel’s influence on Moser. (I discuss Nash-Moser iteration in this note that I wrote back in 2006.)

The von Neumann ergodic theorem (the Hilbert space version of the mean ergodic theorem) asserts that if is a unitary operator on a Hilbert space , and is a vector in that Hilbert space, then one has

in the strong topology, where is the -invariant subspace of , and is the orthogonal projection to . (See e.g. these previous lecture notes for a proof.) The same proof extends to more general amenable groups: if is a countable amenable group acting on a Hilbert space by unitary transformations for , and is a vector in that Hilbert space, then one has

for any Folner sequence of , where is the -invariant subspace, and is the average of on . Thus one can interpret as a certain average of elements of the orbit of .

In a previous blog post, I noted a variant of this ergodic theorem (due to Alaoglu and Birkhoff) that holds even when the group is not amenable (or not discrete), using a more abstract notion of averaging:

Theorem 1 (Abstract ergodic theorem)Let be an arbitrary group acting unitarily on a Hilbert space , and let be a vector in . Then is the element in the closed convex hull of of minimal norm, and is also the unique element of in this closed convex hull.

I recently stumbled upon a different way to think about this theorem, in the additive case when is abelian, which has a closer resemblance to the classical mean ergodic theorem. Given an arbitrary additive group (not necessarily discrete, or countable), let denote the collection of finite non-empty multisets in – that is to say, unordered collections of elements of , not necessarily distinct, for some positive integer . Given two multisets , in , we can form the sum set . Note that the sum set can contain multiplicity even when do not; for instance, . Given a multiset in , and a function from to a vector space , we define the average as

Note that the multiplicity function of the set affects the average; for instance, we have , but .

We can define a directed set on as follows: given two multisets , we write if we have for some . Thus for instance we have . It is easy to verify that this operation is transitive and reflexive, and is directed because any two elements of have a common upper bound, namely . (This is where we need to be abelian.) The notion of convergence along a net, now allows us to define the notion of convergence along ; given a family of points in a topological space indexed by elements of , and a point in , we say that *converges* to along if, for every open neighbourhood of in , one has for sufficiently large , that is to say there exists such that for all . If the topological space is Hausdorff, then the limit is unique (if it exists), and we then write

When takes values in the reals, one can also define the limit superior or limit inferior along such nets in the obvious fashion.

We can then give an alternate formulation of the abstract ergodic theorem in the abelian case:

Theorem 2 (Abelian abstract ergodic theorem)Let be an arbitrary additive group acting unitarily on a Hilbert space , and let be a vector in . Then we havein the strong topology of .

*Proof:* Suppose that , so that for some , then

so by unitarity and the triangle inequality we have

thus is monotone non-increasing in . Since this quantity is bounded between and , we conclude that the limit exists. Thus, for any , we have for sufficiently large that

for all . In particular, for any , we have

We can write

and so from the parallelogram law and unitarity we have

for all , and hence by the triangle inequality (averaging over a finite multiset )

for any . This shows that is a Cauchy sequence in (in the strong topology), and hence (by the completeness of ) tends to a limit. Shifting by a group element , we have

and hence is invariant under shifts, and thus lies in . On the other hand, for any and , we have

and thus on taking strong limits

and so is orthogonal to . Combining these two facts we see that is equal to as claimed.

To relate this result to the classical ergodic theorem, we observe

Lemma 3Let be a countable additive group, with a F{\o}lner sequence , and let be a bounded sequence in a normed vector space indexed by . If exists, then exists, and the two limits are equal.

*Proof:* From the F{\o}lner property, we see that for any and any , the averages and differ by at most in norm if is sufficiently large depending on , (and the ). On the other hand, by the existence of the limit , the averages and differ by at most in norm if is sufficiently large depending on (regardless of how large is). The claim follows.

It turns out that this approach can also be used as an alternate way to construct the Gowers–Host-Kra seminorms in ergodic theory, which has the feature that it does not explicitly require any amenability on the group (or separability on the underlying measure space), though, as pointed out to me in comments, even uncountable abelian groups are amenable in the sense of possessing an invariant mean, even if they do not have a F{\o}lner sequence.

Given an arbitrary additive group , define a *-system* to be a probability space (not necessarily separable or standard Borel), together with a collection of invertible, measure-preserving maps, such that is the identity and (modulo null sets) for all . This then gives isomorphisms for by setting . From the above abstract ergodic theorem, we see that

in the strong topology of for any , where is the collection of measurable sets that are essentially -invariant in the sense that modulo null sets for all , and is the conditional expectation of with respect to .

In a similar spirit, we have

Theorem 4 (Convergence of Gowers-Host-Kra seminorms)Let be a -system for some additive group . Let be a natural number, and for every , let , which for simplicity we take to be real-valued. Then the expressionconverges, where we write , and we are using the product direct set on to define the convergence . In particular, for , the limit

converges.

We prove this theorem below the fold. It implies a number of other known descriptions of the Gowers-Host-Kra seminorms , for instance that

for , while from the ergodic theorem we have

This definition also manifestly demonstrates the cube symmetries of the Host-Kra measures on , defined via duality by requiring that

In a subsequent blog post I hope to present a more detailed study of the norm and its relationship with eigenfunctions and the Kronecker factor, without assuming any amenability on or any separability or topological structure on .

In 1946, Ulam, in response to a theorem of Anning and Erdös, posed the following problem:

Problem 1 (Erdös-Ulam problem)Let be a set such that the distance between any two points in is rational. Is it true that cannot be (topologically) dense in ?

The paper of Anning and Erdös addressed the case that all the distances between two points in were integer rather than rational in the affirmative.

The Erdös-Ulam problem remains open; it was discussed recently over at Gödel’s lost letter. It is in fact likely (as we shall see below) that the set in the above problem is not only forbidden to be topologically dense, but also cannot be Zariski dense either. If so, then the structure of is quite restricted; it was shown by Solymosi and de Zeeuw that if fails to be Zariski dense, then all but finitely many of the points of must lie on a single line, or a single circle. (Conversely, it is easy to construct examples of dense subsets of a line or circle in which all distances are rational, though in the latter case the square of the radius of the circle must also be rational.)

The main tool of the Solymosi-de Zeeuw analysis was Faltings’ celebrated theorem that every algebraic curve of genus at least two contains only finitely many rational points. The purpose of this post is to observe that an affirmative answer to the full Erdös-Ulam problem similarly follows from the conjectured analogue of Falting’s theorem for surfaces, namely the following conjecture of Bombieri and Lang:

Conjecture 2 (Bombieri-Lang conjecture)Let be a smooth projective irreducible algebraic surface defined over the rationals which is of general type. Then the set of rational points of is not Zariski dense in .

In fact, the Bombieri-Lang conjecture has been made for varieties of arbitrary dimension, and for more general number fields than the rationals, but the above special case of the conjecture is the only one needed for this application. We will review what “general type” means (for smooth projective complex varieties, at least) below the fold.

The Bombieri-Lang conjecture is considered to be extremely difficult, in particular being substantially harder than Faltings’ theorem, which is itself a highly non-trivial result. So this implication should not be viewed as a practical route to resolving the Erdös-Ulam problem unconditionally; rather, it is a demonstration of the power of the Bombieri-Lang conjecture. Still, it was an instructive algebraic geometry exercise for me to carry out the details of this implication, which quickly boils down to verifying that a certain quite explicit algebraic surface is of general type (Theorem 4 below). As I am not an expert in the subject, my computations here will be rather tedious and pedestrian; it is likely that they could be made much slicker by exploiting more of the machinery of modern algebraic geometry, and I would welcome any such streamlining by actual experts in this area. (For similar reasons, there may be more typos and errors than usual in this post; corrections are welcome as always.) My calculations here are based on a similar calculation of van Luijk, who used analogous arguments to show (assuming Bombieri-Lang) that the set of perfect cuboids is not Zariski-dense in its projective parameter space.

We also remark that in a recent paper of Makhul and Shaffaf, the Bombieri-Lang conjecture (or more precisely, a weaker consequence of that conjecture) was used to show that if is a subset of with rational distances which intersects any line in only finitely many points, then there is a uniform bound on the cardinality of the intersection of with any line. I have also recently learned (private communication) that an unpublished work of Shaffaf has obtained a result similar to the one in this post, namely that the Erdös-Ulam conjecture follows from the Bombieri-Lang conjecture, plus an additional conjecture about the rational curves in a specific surface.

Let us now give the elementary reductions to the claim that a certain variety is of general type. For sake of contradiction, let be a dense set such that the distance between any two points is rational. Then certainly contains two points that are a rational distance apart. By applying a translation, rotation, and a (rational) dilation, we may assume that these two points are and . As is dense, there is a third point of not on the axis, which after a reflection we can place in the upper half-plane; we will write it as with .

Given any two points in , the quantities are rational, and so by the cosine rule the dot product is rational as well. Since , this implies that the -component of every point in is rational; this in turn implies that the product of the -coordinates of any two points in is rational as well (since this differs from by a rational number). In particular, and are rational, and all of the points in now lie in the lattice . (This fact appears to have first been observed in the 1988 habilitationschrift of Kemnitz.)

Now take four points , in in general position (so that the octuplet avoids any pre-specified hypersurface in ); this can be done if is dense. (If one wished, one could re-use the three previous points to be three of these four points, although this ultimately makes little difference to the analysis.) If is any point in , then the distances from to are rationals that obey the equations

for , and thus determine a rational point in the affine complex variety defined as

By inspecting the projection from to , we see that is a branched cover of , with the generic cover having points (coming from the different ways to form the square roots ); in particular, is a complex affine algebraic surface, defined over the rationals. By inspecting the monodromy around the four singular base points (which switch the sign of one of the roots , while keeping the other three roots unchanged), we see that the variety is connected away from its singular set, and thus irreducible. As is topologically dense in , it is Zariski-dense in , and so generates a Zariski-dense set of rational points in . To solve the Erdös-Ulam problem, it thus suffices to show that

Claim 3For any non-zero rational and for rationals in general position, the rational points of the affine surface is not Zariski dense in .

This is already very close to a claim that can be directly resolved by the Bombieri-Lang conjecture, but is affine rather than projective, and also contains some singularities. The first issue is easy to deal with, by working with the projectivisation

of , where is the homogeneous quadratic polynomial

with

and the projective complex space is the space of all equivalence classes of tuples up to projective equivalence . By identifying the affine point with the projective point , we see that consists of the affine variety together with the set , which is the union of eight curves, each of which lies in the closure of . Thus is the projective closure of , and is thus a complex irreducible projective surface, defined over the rationals. As is cut out by four quadric equations in and has degree sixteen (as can be seen for instance by inspecting the intersection of with a generic perturbation of a fibre over the generically defined projection ), it is also a complete intersection. To show (3), it then suffices to show that the rational points in are not Zariski dense in .

Heuristically, the reason why we expect few rational points in is as follows. First observe from the projective nature of (1) that every rational point is equivalent to an integer point. But for a septuple of integers of size , the quantity is an integer point of of size , and so should only vanish about of the time. Hence the number of integer points of height comparable to should be about

this is a convergent sum if ranges over (say) powers of two, and so from standard probabilistic heuristics (see this previous post) we in fact expect only finitely many solutions, in the absence of any special algebraic structure (e.g. the structure of an abelian variety, or a birational reduction to a simpler variety) that could produce an unusually large number of solutions.

The Bombieri-Lang conjecture, Conjecture 2, can be viewed as a formalisation of the above heuristics (roughly speaking, it is one of the most optimistic natural conjectures one could make that is compatible with these heuristics while also being invariant under birational equivalence).

Unfortunately, contains some singular points. Being a complete intersection, this occurs when the Jacobian matrix of the map has less than full rank, or equivalently that the gradient vectors

for are linearly dependent, where the is in the coordinate position associated to . One way in which this can occur is if one of the gradient vectors vanish identically. This occurs at precisely points, when is equal to for some , and one has for all (so in particular ). Let us refer to these as the *obvious* singularities; they arise from the geometrically evident fact that the distance function is singular at .

The other way in which could occur is if a non-trivial linear combination of at least two of the gradient vectors vanishes. From (2), this can only occur if for some distinct , which from (1) implies that

for two choices of sign . If the signs are equal, then (as are in general position) this implies that , and then we have the singular point

If the non-trivial linear combination involved three or more gradient vectors, then by the pigeonhole principle at least two of the signs involved must be equal, and so the only singular points are (5). So the only remaining possibility is when we have two gradient vectors that are parallel but non-zero, with the signs in (3), (4) opposing. But then (as are in general position) the vectors are non-zero and non-parallel to each other, a contradiction. Thus, outside of the obvious singular points mentioned earlier, the only other singular points are the two points (5).

We will shortly show that the obvious singularities are *ordinary double points*; the surface near any of these points is analytically equivalent to an ordinary cone near the origin, which is a cone over a smooth conic curve . The two non-obvious singularities (5) are slightly more complicated than ordinary double points, they are *elliptic singularities*, which approximately resemble a cone over an elliptic curve. (As far as I can tell, this resemblance is exact in the category of real smooth manifolds, but not in the category of algebraic varieties.) If one blows up each of the point singularities of separately, no further singularities are created, and one obtains a smooth projective surface (using the Segre embedding as necessary to embed back into projective space, rather than in a product of projective spaces). Away from the singularities, the rational points of lift up to rational points of . Assuming the Bombieri-Lang conjecture, we thus are able to answer the Erdös-Ulam problem in the affirmative once we establish

This will be done below the fold, by the pedestrian device of explicitly constructing global differential forms on ; I will also be working from a complex analysis viewpoint rather than an algebraic geometry viewpoint as I am more comfortable with the former approach. (As mentioned above, though, there may well be a quicker way to establish this result by using more sophisticated machinery.)

I thank Mark Green and David Gieseker for helpful conversations (and a crash course in varieties of general type!).

Remark 5The above argument shows in fact (assuming Bombieri-Lang) that sets with all distances rational cannot be Zariski-dense, and thus (by Solymosi-de Zeeuw) must lie on a single line or circle with only finitely many exceptions. Assuming a stronger version of Bombieri-Lang involving a general number field , we obtain a similar conclusion with “rational” replaced by “lying in ” (one has to extend the Solymosi-de Zeeuw analysis to more general number fields, but this should be routine, using the analogue of Faltings’ theorem for such number fields).

Many problems and results in analytic prime number theory can be formulated in the following general form: given a collection of (affine-)linear forms , none of which is a multiple of any other, find a number such that a certain property of the linear forms are true. For instance:

- For the twin prime conjecture, one can use the linear forms , , and the property in question is the assertion that and are both prime.
- For the even Goldbach conjecture, the claim is similar but one uses the linear forms , for some even integer .
- For Chen’s theorem, we use the same linear forms as in the previous two cases, but now is the assertion that is prime and is an almost prime (in the sense that there are at most two prime factors).
- In the recent results establishing bounded gaps between primes, we use the linear forms for some admissible tuple , and take to be the assertion that at least two of are prime.

For these sorts of results, one can try a sieve-theoretic approach, which can broadly be formulated as follows:

- First, one chooses a carefully selected
*sieve weight*, which could for instance be a non-negative function having a divisor sum formfor some coefficients , where is a natural scale parameter. The precise choice of sieve weight is often quite a delicate matter, but will not be discussed here. (In some cases, one may work with multiple sieve weights .)

- Next, one uses tools from analytic number theory (such as the Bombieri-Vinogradov theorem) to obtain upper and lower bounds for sums such as
where is some “arithmetic” function involving the prime factorisation of (we will be a bit vague about what this means precisely, but a typical choice of might be a Dirichlet convolution of two other arithmetic functions ).

- Using some combinatorial arguments, one manipulates these upper and lower bounds, together with the non-negative nature of , to conclude the existence of an in the support of (or of at least one of the sieve weights being considered) for which holds

For instance, in the recent results on bounded gaps between primes, one selects a sieve weight for which one has upper bounds on

and lower bounds on

so that one can show that the expression

is strictly positive, which implies the existence of an in the support of such that at least two of are prime. As another example, to prove Chen’s theorem to find such that is prime and is almost prime, one uses a variety of sieve weights to produce a lower bound for

and an upper bound for

and

where is some parameter between and , and “rough” means that all prime factors are at least . One can observe that if , then there must be at least one for which is prime and is almost prime, since for any rough number , the quantity

is only positive when is an almost prime (if has three or more factors, then either it has at least two factors less than , or it is of the form for some ). The upper and lower bounds on are ultimately produced via asymptotics for expressions of the form (1), (2), (3) for various divisor sums and various arithmetic functions .

Unfortunately, there is an obstruction to sieve-theoretic techniques working for certain types of properties , which Zeb Brady and I recently formalised at an AIM workshop this week. To state the result, we recall the Liouville function , defined by setting whenever is the product of exactly primes (counting multiplicity). Define a *sign pattern* to be an element of the discrete cube . Given a property of natural numbers , we say that a sign pattern is *forbidden* by if there does not exist any natural numbers obeying for which

Example 1Let be the property that at least two of are prime. Then the sign patterns , , , are forbidden, because prime numbers have a Liouville function of , so that can only occur when at least two of are equal to .

Example 2Let be the property that is prime and is almost prime. Then the only forbidden sign patterns are and .

Example 3Let be the property that and are both prime. Then are all forbidden sign patterns.

We then have a parity obstruction as soon as has “too many” forbidden sign patterns, in the following (slightly informal) sense:

Claim 1 (Parity obstruction)Suppose is such that that the convex hull of the forbidden sign patterns of contains the origin. Then one cannot use the above sieve-theoretic approach to establish the existence of an such that holds.

Thus for instance, the property in Example 3 is subject to the parity obstruction since is a convex combination of and , whereas the properties in Examples 1, 2 are not. One can also check that the property “at least of the numbers is prime” is subject to the parity obstruction as soon as . Thus, the largest number of elements of a -tuple that one can force to be prime by purely sieve-theoretic methods is , rounded up.

This claim is not precisely a theorem, because it presumes a certain “Liouville pseudorandomness conjecture” (a very close cousin of the more well known “Möbius pseudorandomness conjecture”) which is a bit difficult to formalise precisely. However, this conjecture is widely believed by analytic number theorists, see e.g. this blog post for a discussion. (Note though that there are scenarios, most notably the “Siegel zero” scenario, in which there is a severe breakdown of this pseudorandomness conjecture, and the parity obstruction then disappears. A typical instance of this is Heath-Brown’s proof of the twin prime conjecture (which would ordinarily be subject to the parity obstruction) under the hypothesis of a Siegel zero.) The obstruction also does not prevent the establishment of an such that holds by introducing additional sieve axioms beyond upper and lower bounds on quantities such as (1), (2), (3). The proof of the Friedlander-Iwaniec theorem is a good example of this latter scenario.

Now we give a (slightly nonrigorous) proof of the claim.

*Proof:* (Nonrigorous) Suppose that the convex hull of the forbidden sign patterns contain the origin. Then we can find non-negative numbers for sign patterns , which sum to , are non-zero only for forbidden sign patterns, and which have mean zero in the sense that

for all . By Fourier expansion (or Lagrange interpolation), one can then write as a polynomial

where is a polynomial in variables that is a linear combination of monomials with and (thus has no constant or linear terms, and no monomials with repeated terms). The point is that the mean zero condition allows one to eliminate the linear terms. If we now consider the weight function

then is non-negative, is supported solely on for which is a forbidden pattern, and is equal to plus a linear combination of monomials with .

The Liouville pseudorandomness principle then predicts that sums of the form

and

or more generally

should be asymptotically negligible; intuitively, the point here is that the prime factorisation of should not influence the Liouville function of , even on the short arithmetic progressions that the divisor sum is built out of, and so any monomial occurring in should exhibit strong cancellation for any of the above sums. If one accepts this principle, then all the expressions (1), (2), (3) should be essentially unchanged when is replaced by .

Suppose now for sake of contradiction that one could use sieve-theoretic methods to locate an in the support of some sieve weight obeying . Then, by reweighting all sieve weights by the additional multiplicative factor of , the same arguments should also be able to locate in the support of for which holds. But is only supported on those whose Liouville sign pattern is forbidden, a contradiction.

Claim 1 is sharp in the following sense: if the convex hull of the forbidden sign patterns of do *not* contain the origin, then by the Hahn-Banach theorem (in the hyperplane separation form), there exist real coefficients such that

for all forbidden sign patterns and some . On the other hand, from Liouville pseudorandomness one expects that

is negligible (as compared against for any reasonable sieve weight . We conclude that for some in the support of , that

and hence is not a forbidden sign pattern. This does not actually imply that holds, but it does not prevent from holding purely from parity considerations. Thus, we do not expect a parity obstruction of the type in Claim 1 to hold when the convex hull of forbidden sign patterns does not contain the origin.

Example 4Let be a graph on vertices , and let be the property that one can find an edge of with both prime. We claim that this property is subject to the parity problem precisely when is two-colourable. Indeed, if is two-colourable, then we can colour into two colours (say, red and green) such that all edges in connect a red vertex to a green vertex. If we then consider the two sign patterns in which all the red vertices have one sign and the green vertices have the opposite sign, these are two forbidden sign patterns which contain the origin in the convex hull, and so the parity problem applies. Conversely, suppose that is not two-colourable, then it contains an odd cycle. Any forbidden sign pattern then must contain more s on this odd cycle than s (since otherwise two of the s are adjacent on this cycle by the pigeonhole principle, and this is not forbidden), and so by convexity any tuple in the convex hull of this sign pattern has a positive sum on this odd cycle. Hence the origin is not in the convex hull, and the parity obstruction does not apply. (See also this previous post for a similar obstruction ultimately coming from two-colourability).

Example 5An example of a parity-obstructed property (supplied by Zeb Brady) that does not come from two-colourability: we let be the property that are prime for some collection of pair sets that cover . For instance, this property holds if are both prime, or if are all prime, but not if are the only primes. An example of a forbidden sign pattern is the pattern where are given the sign , and the other three pairs are given . Averaging over permutations of we see that zero lies in the convex hull, and so this example is blocked by parity. However, there is no sign pattern such that it and its negation are both forbidden, which is another formulation of two-colourability.

Of course, the absence of a parity obstruction does not automatically mean that the desired claim is true. For instance, given an admissible -tuple , parity obstructions do not prevent one from establishing the existence of infinitely many such that at least three of are prime, however we are not yet able to actually establish this, even assuming strong sieve-theoretic hypotheses such as the generalised Elliott-Halberstam hypothesis. (However, the argument giving (4) does easily give the far weaker claim that there exist infinitely many such that at least three of have a Liouville function of .)

Remark 1Another way to get past the parity problem in some cases is to take advantage of linear forms that are constant multiples of each other (which correlates the Liouville functions to each other). For instance, on GEH we can find two numbers (products of exactly three primes) that differ by exactly ; a direct sieve approach using the linear forms fails due to the parity obstruction, but instead one can first find such that two of are prime, and then among the pairs of linear forms , , one can find a pair of numbers that differ by exactly . See this paper of Goldston, Graham, Pintz, and Yildirim for more examples of this type.

I thank John Friedlander and Sid Graham for helpful discussions and encouragement.

The wave equation is usually expressed in the form

where is a function of both time and space , with being the Laplacian operator. One can generalise this equation in a number of ways, for instance by replacing the spatial domain with some other manifold and replacing the Laplacian with the Laplace-Beltrami operator or adding lower order terms (such as a potential, or a coupling with a magnetic field). But for sake of discussion let us work with the classical wave equation on . We will work formally in this post, being unconcerned with issues of convergence, justifying interchange of integrals, derivatives, or limits, etc.. One then has a conserved energy

which we can rewrite using integration by parts and the inner product on as

A key feature of the wave equation is *finite speed of propagation*: if, at time (say), the initial position and initial velocity are both supported in a ball , then at any later time , the position and velocity are supported in the larger ball . This can be seen for instance (formally, at least) by inspecting the exterior energy

and observing (after some integration by parts and differentiation under the integral sign) that it is non-increasing in time, non-negative, and vanishing at time .

The wave equation is second order in time, but one can turn it into a first order system by working with the pair rather than just the single field , where is the velocity field. The system is then

and the conserved energy is now

Finite speed of propagation then tells us that if are both supported on , then are supported on for all . One also has time reversal symmetry: if is a solution, then is a solution also, thus for instance one can establish an analogue of finite speed of propagation for negative times using this symmetry.

If one has an eigenfunction

of the Laplacian, then we have the explicit solutions

of the wave equation, which formally can be used to construct all other solutions via the principle of superposition.

When one has vanishing initial velocity , the solution is given via functional calculus by

and the propagator can be expressed as the average of half-wave operators:

One can view as a minor of the full wave propagator

which is unitary with respect to the energy form (1), and is the fundamental solution to the wave equation in the sense that

Viewing the contraction as a minor of a unitary operator is an instance of the “dilation trick“.

It turns out (as I learned from Yuval Peres) that there is a useful discrete analogue of the wave equation (and of all of the above facts), in which the time variable now lives on the integers rather than on , and the spatial domain can be replaced by discrete domains also (such as graphs). Formally, the system is now of the form

where is now an integer, take values in some Hilbert space (e.g. functions on a graph ), and is some operator on that Hilbert space (which in applications will usually be a self-adjoint contraction). To connect this with the classical wave equation, let us first consider a rescaling of this system

where is a small parameter (representing the discretised time step), now takes values in the integer multiples of , and is the wave propagator operator or the heat propagator (the two operators are different, but agree to fourth order in ). One can then formally verify that the wave equation emerges from this rescaled system in the limit . (Thus, is not exactly the direct analogue of the Laplacian , but can be viewed as something like in the case of small , or if we are not rescaling to the small case. The operator is sometimes known as the *diffusion operator*)

Assuming is self-adjoint, solutions to the system (3) formally conserve the energy

This energy is positive semi-definite if is a contraction. We have the same time reversal symmetry as before: if solves the system (3), then so does . If one has an eigenfunction

to the operator , then one has an explicit solution

to (3), and (in principle at least) this generates all other solutions via the principle of superposition.

Finite speed of propagation is a lot easier in the discrete setting, though one has to offset the support of the “velocity” field by one unit. Suppose we know that has unit speed in the sense that whenever is supported in a ball , then is supported in the ball . Then an easy induction shows that if are supported in respectively, then are supported in .

The fundamental solution to the discretised wave equation (3), in the sense of (2), is given by the formula

where and are the Chebyshev polynomials of the first and second kind, thus

and

In particular, is now a minor of , and can also be viewed as an average of with its inverse :

As before, is unitary with respect to the energy form (4), so this is another instance of the dilation trick in action. The powers and are discrete analogues of the heat propagators and wave propagators respectively.

One nice application of all this formalism, which I learned from Yuval Peres, is the Varopoulos-Carne inequality:

Theorem 1 (Varopoulos-Carne inequality)Let be a (possibly infinite) regular graph, let , and let be vertices in . Then the probability that the simple random walk at lands at at time is at most , where is the graph distance.

This general inequality is quite sharp, as one can see using the standard Cayley graph on the integers . Very roughly speaking, it asserts that on a regular graph of reasonably controlled growth (e.g. polynomial growth), random walks of length concentrate on the ball of radius or so centred at the origin of the random walk.

*Proof:* Let be the graph Laplacian, thus

for any , where is the degree of the regular graph and sum is over the vertices that are adjacent to . This is a contraction of unit speed, and the probability that the random walk at lands at at time is

where are the Dirac deltas at . Using (5), we can rewrite this as

where we are now using the energy form (4). We can write

where is the simple random walk of length on the integers, that is to say where are independent uniform Bernoulli signs. Thus we wish to show that

By finite speed of propagation, the inner product here vanishes if . For we can use Cauchy-Schwarz and the unitary nature of to bound the inner product by . Thus the left-hand side may be upper bounded by

and the claim now follows from the Chernoff inequality.

This inequality has many applications, particularly with regards to relating the entropy, mixing time, and concentration of random walks with volume growth of balls; see this text of Lyons and Peres for some examples.

For sake of comparison, here is a continuous counterpart to the Varopoulos-Carne inequality:

Theorem 2 (Continuous Varopoulos-Carne inequality)Let , and let be supported on compact sets respectively. Thenwhere is the Euclidean distance between and .

*Proof:* By Fourier inversion one has

for any real , and thus

By finite speed of propagation, the inner product vanishes when ; otherwise, we can use Cauchy-Schwarz and the contractive nature of to bound this inner product by . Thus

Bounding by , we obtain the claim.

Observe that the argument is quite general and can be applied for instance to other Riemannian manifolds than .

The prime number theorem can be expressed as the assertion

is the von Mangoldt function. It is a basic result in analytic number theory, but requires a bit of effort to prove. One “elementary” proof of this theorem proceeds through the Selberg symmetry formula

where the second von Mangoldt function is defined by the formula

(We are avoiding the use of the symbol here to denote Dirichlet convolution, as we will need this symbol to denote ordinary convolution shortly.) For the convenience of the reader, we give a proof of the Selberg symmetry formula below the fold. Actually, for the purposes of proving the prime number theorem, the weaker estimate

In this post I would like to record a somewhat “soft analysis” reformulation of the elementary proof of the prime number theorem in terms of Banach algebras, and specifically in Banach algebra structures on (completions of) the space of compactly supported continuous functions equipped with the convolution operation

This soft argument does not easily give any quantitative decay rate in the prime number theorem, but by the same token it avoids many of the quantitative calculations in the traditional proofs of this theorem. Ultimately, the key “soft analysis” fact used is the spectral radius formula

for any element of a unital commutative Banach algebra , where is the space of characters (i.e., continuous unital algebra homomorphisms from to ) of . This formula is due to Gelfand and may be found in any text on Banach algebras; for sake of completeness we prove it below the fold.

The connection between prime numbers and Banach algebras is given by the following consequence of the Selberg symmetry formula.

Theorem 1 (Construction of a Banach algebra norm)For any , let denote the quantityThen is a seminorm on with the bound

for all . Furthermore, we have the Banach algebra bound

We prove this theorem below the fold. The prime number theorem then follows from Theorem 1 and the following two assertions. The first is an application of the spectral radius formula (6) and some basic Fourier analysis (in particular, the observation that contains a plentiful supply of local units:

Theorem 2 (Non-trivial Banach algebras with many local units have non-trivial spectrum)Let be a seminorm on obeying (7), (8). Suppose that is not identically zero. Then there exists such thatfor all . In particular, by (7), one has

whenever is a non-negative function.

The second is a consequence of the Selberg symmetry formula and the fact that is real (as well as Mertens’ theorem, in the case), and is closely related to the non-vanishing of the Riemann zeta function on the line :

Theorem 3 (Breaking the parity barrier)Let . Then there exists such that is non-negative, and

Assuming Theorems 1, 2, 3, we may now quickly establish the prime number theorem as follows. Theorem 2 and Theorem 3 imply that the seminorm constructed in Theorem 1 is trivial, and thus

as for any Schwartz function (the decay rate in may depend on ). Specialising to functions of the form for some smooth compactly supported on , we conclude that

as ; by the smooth Urysohn lemma this implies that

as for any fixed , and the prime number theorem then follows by a telescoping series argument.

The same argument also yields the prime number theorem in arithmetic progressions, or equivalently that

for any fixed Dirichlet character ; the one difference is that the use of Mertens’ theorem is replaced by the basic fact that the quantity is non-vanishing.

In graph theory, the recently developed theory of *graph limits* has proven to be a useful tool for analysing large dense graphs, being a convenient reformulation of the Szemerédi regularity lemma. Roughly speaking, the theory asserts that given any sequence of finite graphs, one can extract a subsequence which converges (in a specific sense) to a continuous object known as a “graphon” – a symmetric measurable function . What “converges” means in this context is that subgraph densities converge to the associated integrals of the graphon . For instance, the edge density

converge to the integral

the triangle density

converges to the integral

the four-cycle density

converges to the integral

and so forth. One can use graph limits to prove many results in graph theory that were traditionally proven using the regularity lemma, such as the triangle removal lemma, and can also reduce many asymptotic graph theory problems to continuous problems involving multilinear integrals (although the latter problems are not necessarily easy to solve!). See this text of Lovasz for a detailed study of graph limits and their applications.

One can also express graph limits (and more generally hypergraph limits) in the language of nonstandard analysis (or of ultraproducts); see for instance this paper of Elek and Szegedy, Section 6 of this previous blog post, or this paper of Towsner. (In this post we assume some familiarity with nonstandard analysis, as reviewed for instance in the previous blog post.) Here, one starts as before with a sequence of finite graphs, and then takes an ultraproduct (with respect to some arbitrarily chosen non-principal ultrafilter ) to obtain a nonstandard graph , where is the ultraproduct of the , and similarly for the . The set can then be viewed as a symmetric subset of which is measurable with respect to the Loeb -algebra of the product (see this previous blog post for the construction of Loeb measure). A crucial point is that this -algebra is larger than the product of the Loeb -algebra of the individual vertex set . This leads to a decomposition

where the “graphon” is the orthogonal projection of onto , and the “regular error” is orthogonal to all product sets for . The graphon then captures the statistics of the nonstandard graph , in exact analogy with the more traditional graph limits: for instance, the edge density

(or equivalently, the limit of the along the ultrafilter ) is equal to the integral

where denotes Loeb measure on a nonstandard finite set ; the triangle density

(or equivalently, the limit along of the triangle densities of ) is equal to the integral

and so forth. Note that with this construction, the graphon is living on the Cartesian square of an abstract probability space , which is likely to be inseparable; but it is possible to cut down the Loeb -algebra on to minimal countable -algebra for which remains measurable (up to null sets), and then one can identify with , bringing this construction of a graphon in line with the traditional notion of a graphon. (See Remark 5 of this previous blog post for more discussion of this point.)

Additive combinatorics, which studies things like the additive structure of finite subsets of an abelian group , has many analogies and connections with asymptotic graph theory; in particular, there is the arithmetic regularity lemma of Green which is analogous to the graph regularity lemma of Szemerédi. (There is also a higher order arithmetic regularity lemma analogous to hypergraph regularity lemmas, but this is not the focus of the discussion here.) Given this, it is natural to suspect that there is a theory of “additive limits” for large additive sets of bounded doubling, analogous to the theory of graph limits for large dense graphs. The purpose of this post is to record a candidate for such an additive limit. This limit can be used as a substitute for the arithmetic regularity lemma in certain results in additive combinatorics, at least if one is willing to settle for qualitative results rather than quantitative ones; I give a few examples of this below the fold.

It seems that to allow for the most flexible and powerful manifestation of this theory, it is convenient to use the nonstandard formulation (among other things, it allows for full use of the transfer principle, whereas a more traditional limit formulation would only allow for a transfer of those quantities continuous with respect to the notion of convergence). Here, the analogue of a nonstandard graph is an *ultra approximate group* in a nonstandard group , defined as the ultraproduct of finite -approximate groups for some standard . (A -approximate group is a symmetric set containing the origin such that can be covered by or fewer translates of .) We then let be the external subgroup of generated by ; equivalently, is the union of over all standard . This space has a Loeb measure , defined by setting

whenever is an internal subset of for any standard , and extended to a countably additive measure; the arguments in Section 6 of this previous blog post can be easily modified to give a construction of this measure.

The Loeb measure is a translation invariant measure on , normalised so that has Loeb measure one. As such, one should think of as being analogous to a locally compact abelian group equipped with a Haar measure. It should be noted though that is not *actually* a locally compact group with Haar measure, for two reasons:

- There is not an obvious topology on that makes it simultaneously locally compact, Hausdorff, and -compact. (One can get one or two out of three without difficulty, though.)
- The addition operation is not measurable from the product Loeb algebra to . Instead, it is measurable from the coarser Loeb algebra to (compare with the analogous situation for nonstandard graphs).

Nevertheless, the analogy is a useful guide for the arguments that follow.

Let denote the space of bounded Loeb measurable functions (modulo almost everywhere equivalence) that are supported on for some standard ; this is a complex algebra with respect to pointwise multiplication. There is also a convolution operation , defined by setting

whenever , are bounded nonstandard functions (extended by zero to all of ), and then extending to arbitrary elements of by density. Equivalently, is the pushforward of the -measurable function under the map .

The basic structural theorem is then as follows.

Theorem 1 (Kronecker factor)Let be an ultra approximate group. Then there exists a (standard) locally compact abelian group of the formfor some standard and some compact abelian group , equipped with a Haar measure and a measurable homomorphism (using the Loeb -algebra on and the Baire -algebra on ), with the following properties:

- (i) has dense image, and is the pushforward of Loeb measure by .
- (ii) There exists sets with open and compact, such that
- (iii) Whenever with compact and open, there exists a nonstandard finite set such that
- (iv) If , then we have the convolution formula
where are the pushforwards of to , the convolution on the right-hand side is convolution using , and is the pullback map from to . In particular, if , then for all .

One can view the locally compact abelian group as a “model “or “Kronecker factor” for the ultra approximate group (in close analogy with the Kronecker factor from ergodic theory). In the case that is a genuine nonstandard finite group rather than an ultra approximate group, the non-compact components of the Kronecker group are trivial, and this theorem was implicitly established by Szegedy. The compact group is quite large, and in particular is likely to be inseparable; but as with the case of graphons, when one is only studying at most countably many functions , one can cut down the size of this group to be separable (or equivalently, second countable or metrisable) if desired, so one often works with a “reduced Kronecker factor” which is a quotient of the full Kronecker factor . Once one is in the separable case, the Baire sigma algebra is identical with the more familiar Borel sigma algebra.

Given any sequence of uniformly bounded functions for some fixed , we can view the function defined by

as an “additive limit” of the , in much the same way that graphons are limits of the indicator functions . The additive limits capture some of the statistics of the , for instance the normalised means

converge (along the ultrafilter ) to the mean

and for three sequences of functions, the normalised correlation

converges along to the correlation

the normalised Gowers norm

converges along to the Gowers norm

and so forth. We caution however that some correlations that involve evaluating more than one function at the same point will not necessarily be preserved in the additive limit; for instance the normalised norm

does not necessarily converge to the norm

but can converge instead to a larger quantity, due to the presence of the orthogonal projection in the definition (4) of .

An important special case of an additive limit occurs when the functions involved are indicator functions of some subsets of . The additive limit does not necessarily remain an indicator function, but instead takes values in (much as a graphon takes values in even though the original indicators take values in ). The convolution is then the ultralimit of the normalised convolutions ; in particular, the measure of the support of provides a lower bound on the limiting normalised cardinality of a sumset. In many situations this lower bound is an equality, but this is not necessarily the case, because the sumset could contain a large number of elements which have very few () representations as the sum of two elements of , and in the limit these portions of the sumset fall outside of the support of . (One can think of the support of as describing the “essential” sumset of , discarding those elements that have only very few representations.) Similarly for higher convolutions of . Thus one can use additive limits to partially control the growth of iterated sumsets of subsets of approximate groups , in the regime where stays bounded and goes to infinity.

Theorem 1 can be proven by Fourier-analytic means (combined with Freiman’s theorem from additive combinatorics), and we will do so below the fold. For now, we give some illustrative examples of additive limits.

Example 2 (Bohr sets)We take to be the intervals , where is a sequence going to infinity; these are -approximate groups for all . Let be an irrational real number, let be an interval in , and for each natural number let be the Bohr setIn this case, the (reduced) Kronecker factor can be taken to be the infinite cylinder with the usual Lebesgue measure . The additive limits of and end up being and , where is the finite cylinder

and is the rectangle

Geometrically, one should think of and as being wrapped around the cylinder via the homomorphism , and then one sees that is converging in some normalised weak sense to , and similarly for and . In particular, the additive limit predicts the growth rate of the iterated sumsets to be quadratic in until becomes comparable to , at which point the growth transitions to linear growth, in the regime where is bounded and is large.

If were rational instead of irrational, then one would need to replace by the finite subgroup here.

Example 3 (Structured subsets of progressions)We take be the rank two progressionwhere is a sequence going to infinity; these are -approximate groups for all . Let be the subset

Then the (reduced) Kronecker factor can be taken to be with Lebesgue measure , and the additive limits of the and are then and , where is the square

and is the circle

Geometrically, the picture is similar to the Bohr set one, except now one uses a Freiman homomorphism for to embed the original sets into the plane . In particular, one now expects the growth rate of the iterated sumsets and to be quadratic in , in the regime where is bounded and is large.

Example 4 (Dissociated sets)Let be a fixed natural number, and takewhere are randomly chosen elements of a large cyclic group , where is a sequence of primes going to infinity. These are -approximate groups. The (reduced) Kronecker factor can (almost surely) then be taken to be with counting measure, and the additive limit of is , where and is the standard basis of . In particular, the growth rates of should grow approximately like for bounded and large.

Example 5 (Random subsets of groups)Let be a sequence of finite additive groups whose order is going to infinity. Let be a random subset of of some fixed density . Then (almost surely) the Kronecker factor here can be reduced all the way to the trivial group , and the additive limit of the is the constant function . The convolutions then converge in the ultralimit (modulo almost everywhere equivalence) to the pullback of ; this reflects the fact that of the elements of can be represented as the sum of two elements of in ways. In particular, occupies a proportion of .

Example 6 (Trigonometric series)Take for a sequence of primes going to infinity, and for each let be an infinite sequence of frequencies chosen uniformly and independently from . Let denote the random trigonometric seriesThen (almost surely) we can take the reduced Kronecker factor to be the infinite torus (with the Haar probability measure ), and the additive limit of the then becomes the function defined by the formula

In fact, the pullback is the ultralimit of the . As such, for any standard exponent , the normalised norm

can be seen to converge to the limit

The reader is invited to consider combinations of the above examples, e.g. random subsets of Bohr sets, to get a sense of the general case of Theorem 1.

It is likely that this theorem can be extended to the noncommutative setting, using the noncommutative Freiman theorem of Emmanuel Breuillard, Ben Green, and myself, but I have not attempted to do so here (see though this recent preprint of Anush Tserunyan for some related explorations); in a separate direction, there should be extensions that can control higher Gowers norms, in the spirit of the work of Szegedy.

Note: the arguments below will presume some familiarity with additive combinatorics and with nonstandard analysis, and will be a little sketchy in places.

## Recent Comments