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

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 and be integers, and let . Suppose that is a function supported on such thatThen there exists a filtered nilmanifold of degree and complexity , a polynomial sequence , and a Lipschitz function of Lipschitz constant such that

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 and be integers, and let . Suppose that is a function supported on such thatThen there exists a filtered nilmanifold of degree and complexity , a polynomial sequence , and a Lipschitz function of Lipschitz constant such that

The 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 defined by

that is to say is the digit string base that has digits . This map is a linear map from to a subset of of density . Furthermore it has the following “Freiman isomorphism” property: if lie in with in the image set of for all , then there exist (unique) lifts such that

and

for all . Indeed, the injectivity of on uniquely determines the sum for each , and one can use base arithmetic to verify that the alternating sum of these sums on any -facet of the cube vanishes, which gives the claim. (In the language of additive combinatorics, the point is that is a Freiman isomorphism of order (say) on .)

Now let be the function defined by setting whenever , with vanishing outside of . If obeys (1), then from the above Freiman isomorphism property we have

Applying the one-dimensional inverse theorem (Theorem 1), with reduced by a factor of and replaced by , this implies the existence of a filtered nilmanifold of degree and complexity , a polynomial sequence , and a Lipschitz function of Lipschitz constant such that

which by the Freiman isomorphism property again implies that

But the map is clearly a polynomial map from to (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 3This trick appears to be largely restricted to the case of boundedly generated groups such as ; I do not see any easy way to deduce an inverse theorem for, say, from the -inverse theorem by this method.

Remark 4By combining this argument with the one in the previous post, one can obtain a weak ergodic inverse theorem for -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 actions (a result first obtained in the PhD thesis of Griesmer) from the counterpart for 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 and be integers, and let . Suppose that is a function supported on such thatThen there exists a filtered nilmanifold of degree and complexity , a polynomial sequence , and a Lipschitz function of Lipschitz constant such that

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 be an integer, and let be an ergodic, countably generated measure-preserving system. Suppose that one hasfor all non-zero (all spaces are real-valued in this post). Then is an inverse limit (in the category of measure-preserving systems, up to almost everywhere equivalence) of ergodic degree nilsystems, that is to say systems of the form for some degree filtered nilmanifold and a group element that acts ergodically on .

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 -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 be an integer, and let be an ergodic, countably generated measure-preserving system. Suppose that one hasfor all non-zero , where . Then is a

factorof an inverse limit of ergodic degree nilsystems.

Theorem 4 (Pro-nilsystems closed under factors)Let be an integer. Then any factor of an inverse limit of ergodic degree nilsystems, is again an inverse limit of ergodic degree 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:

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 and be integers, and let . Suppose that is a function supported on such that

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 be an integer, and let . Suppose that is a measurable function supported on such thatThen there exists a filtered nilmanifold of degree and complexity , a (smooth) polynomial sequence , and a Lipschitz function of Lipschitz constant such that

The interval 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 . Note though that the coefficients of can be arbitrarily large (and this is necessary, as can be seen just by considering functions of the form for some arbitrarily large frequency ).

It is likely that one could prove Theorem 2 by carefully going through the proof of Theorem 1 and replacing all instances of with (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 as a limit of the discrete interval as . 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 produced by Theorem 1, after normalising these coefficients by . Fortunately, a factorisation theorem from a paper of Ben Green and myself resolves this problem by splitting 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 .

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 be a positive integer, and let be a function with for some , where we use the averaging notation , , etc.. Then for we havefor some depending only on .

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 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 has a prime factorisation
into (not necessarily distinct) primes , which is unique up to rearrangement. Taking logarithms, we obtain a partition

of .

- (Prime number theorem) A randomly selected integer of size will be prime with probability when is large.
- If is a randomly selected large integer of size , and is a randomly selected prime factor of (with each index being chosen with probability ), then is approximately uniformly distributed between and . (See Proposition 9 of this previous blog post.)
- The set of real numbers arising from the prime factorisation of a large random number converges (away from the origin, and in a suitable weak sense) to the Poisson-Dirichlet process in the limit . (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 has a cycle decomposition
into disjoint cycles , which is unique up to rearrangement, and where we count each fixed point of as a cycle of length . If is the length of the cycle , we obtain a partition

of .

- (Prime number theorem for permutations) A randomly selected permutation of will be an -cycle with probability exactly . (This was noted in this previous blog post.)
- If is a random permutation in , and is a randomly selected cycle of (with each being selected with probability ), then is exactly uniformly distributed on . (See Proposition 8 of this blog post.)
- The set of real numbers arising from the cycle decomposition of a random permutation converges (in a suitable sense) to the Poisson-Dirichlet process in the limit . (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 over a finite field , 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 . We then have another analogous list of facts, proven very similarly to the corresponding list of facts for the integers:

- Every monic polynomial has a factorisation
into irreducible monic polynomials , which is unique up to rearrangement. Taking degrees, we obtain a partition

of .

- (Prime number theorem for polynomials) A randomly selected monic polynomial of degree will be irreducible with probability when is fixed and is large.
- If is a random monic polynomial of degree , and is a random irreducible factor of (with each selected with probability ), then is approximately uniformly distributed in when is fixed and is large.
- The set of real numbers arising from the factorisation of a randomly selected polynomial of degree converges (in a suitable sense) to the Poisson-Dirichlet process when is fixed and is large.

The above list of facts addressed the *large limit* of the polynomial ring , where the order 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 . However, there is another interesting asymptotic limit of polynomial rings to consider, namely the *large limit* where it is now the *degree* that is held fixed, but the order of the field goes to infinity. Actually to simplify the exposition we will use the slightly more restrictive limit where the *characteristic* of the field goes to infinity (again keeping the degree fixed), although all of the results proven below for the large limit turn out to be true as well in the large limit.

The large (or large ) limit is technically a different limit than the large 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 limit:

Theorem 1 (Prime number theorem)The probability that a random monic polynomial of degree is irreducible is in the limit where is fixed and the characteristic goes to infinity.

*Proof:* There are monic polynomials of degree . If is irreducible, then the zeroes of are distinct and lie in the finite field , but do not lie in any proper subfield of that field. Conversely, every element of that does not lie in a proper subfield is the root of a unique monic polynomial in of degree (the minimal polynomial of ). Since the union of all the proper subfields of has size , the total number of irreducible polynomials of degree is thus , and the claim follows.

Remark 2The above argument and inclusion-exclusion in fact gives the well known exact formula for the number of irreducible monic polynomials of degree .

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

Theorem 3The partition of a random monic polynomial of degree converges in distribution to the partition of a random permutation of length , in the limit where is fixed and the characteristic 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 limit)A random monic polynomial of degree will be square-free with probability when is fixed and (or ) goes to infinity. In a similar spirit, two randomly selected monic polynomials of degree will be coprime with probability if are fixed and or goes to infinity.

*Proof:* For any polynomial of degree , the probability that is divisible by is at most . Summing over all polynomials of degree , and using the union bound, we see that the probability that is *not* squarefree is at most , giving the first claim. For the second, observe from the first claim (and the fact that has only a bounded number of factors) that is squarefree with probability , giving the claim.

Now we can prove the theorem. Elementary combinatorics tells us that the probability of a random permutation consisting of cycles of length for , where are nonnegative integers with , is precisely

since there are ways to write a given tuple of cycles in cycle notation in nondecreasing order of length, and 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 that are the product of irreducible polynomials of degree is

which simplifies to

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 of permutations and the factorisation of a polynomial. One immediate thought might be to try to link the multiplication structure of permutations in 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 is (extremely) non-abelian but invertible. Also, the multiplication of a degree and a degree polynomial is a degree polynomial, whereas the group multiplication law on permutations does not take a permutation in and a permutation in and return a permutation in .

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 are two subgroups of some ambient group , with the index of in being finite. Then is the union of left cosets of , thus for some set of cardinality . The elements of are not entirely arbitrary with regards to . For instance, if is a *normal* subgroup of , then for each , the conjugation map preserves . In particular, if we write for the conjugate of by , then

Even if is not normal in , it turns out that the conjugation map *approximately* preserves , if is bounded. To quantify this, let us call two subgroups *-commensurate* for some if one has

Proposition 1Let be groups, with finite index . Then for every , the groups and are -commensurate, in fact

*Proof:* One can partition into left translates of , as well as left translates of . Combining the partitions, we see that can be partitioned into at most non-empty sets of the form . Each of these sets is easily seen to be a left translate of the subgroup , thus . Since

and , we obtain the claim.

One can replace the inclusion by commensurability, at the cost of some worsening of the constants:

Corollary 2Let be -commensurate subgroups of . Then for every , the groups and are -commensurate.

*Proof:* Applying the previous proposition with replaced by , we see that for every , and are -commensurate. Since and have index at most in and respectively, the claim follows.

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 containing a given approximate group as a “bounded index approximate subgroup”. Recall that a -approximate group in a group for some is a symmetric subset of containing the identity, such that the product set can be covered by at most left translates of (and thus also right translates, by the symmetry of ). For simplicity we will restrict attention to finite approximate groups so that we can use their cardinality as a measure of size. We call finite two approximate groups *-commensurate* if one has

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

Theorem 3Let be a group, and let be real numbers. Let be a finite -approximate group, and let be a symmetric subset of that contains .

- (i) If is a -approximate group with , then one has for some set of cardinality at most . Furthermore, for each , the approximate groups and are -commensurate.
- (ii) Conversely, if for some set of cardinality at most , and and are -commensurate for all , then , and is a -approximate group.

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

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 and are finite non-empty subsets of , then one has for some set with cardinality .

*Proof:* We take to be a subset of with the property that the translates are disjoint in , and such that is maximal with respect to set inclusion. The required properties of are then easily verified.

Lemma 5 (Ruzsa triangle inequality)If are finite non-empty subsets of , then

*Proof:* If is an element of with and , then from the identity we see that can be written as the product of an element of and an element of in at least distinct ways. The claim follows.

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

left-translates of , and hence by at most left-translates of , thus for some . Since only intersects if , we may assume that

and hence for any

By the Ruzsa covering lemma again, this implies that can be covered by at most left-translates of , and hence by at most left-translates of . By the pigeonhole principle, there thus exists a group element with

Since

and

the claim follows.

Now we prove (ii). Clearly

Now we control the size of . We have

From the Ruzsa triangle inequality and symmetry we have

and thus

By the Ruzsa covering lemma, this implies that is covered by at most left-translates of , hence by at most left-translates of . Since , the claim follows.

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

Proposition 6Let be a -approximate group, be a -approximate group, and be a -approximate group. If and are -commensurate, and and are -commensurate, then and are -commensurate.

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

By the Ruzsa covering lemma, we may thus cover by at most left-translates of , and hence by left-translates of . By the pigeonhole principle, there thus exists a group element such that

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

and similarly

and the claim follows.

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

Proposition 7Let be a -approximate group, be a -approximate group, and suppose that and are -commensurate. Then is a -approximate subgroup, and is a -approximate subgroup.

Using this proposition, one may obtain a variant of the previous theorem where the containment is replaced by commensurability; we leave the details to the interested reader.

*Proof:* We begin with . Clearly is symmetric and contains the identity. We have . The set is already covered by left translates of , and hence of ; similarly is covered by left translates of . As for , we observe from the Ruzsa triangle inequality that

and hence by the Ruzsa covering lemma, is covered by at most left translates of , and hence by left translates of , and hence of . Similarly is covered by at most left translates of . The claim follows.

Now we consider . Again, this is clearly symmetric and contains the identity. Repeating the previous arguments, we see that is covered by at most left-translates of , and hence there exists a group element with

Now observe that

and so by the Ruzsa covering lemma, can be covered by at most left-translates of . But this latter set is (as observed previously) contained in , and the claim follows.

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

## Recent Comments