The previous post showed how to connect sets with ergodic theory, namely a measure-preserving system , where is the symbolic space and is the shift map. As the reader can check in ERT5, the measure is an accumulation point of Dirac probability measures along increasing intervals of orbits of the point associated to . For this reason, is supported in the orbit of . Then we could take as the orbit closure

instead of the whole space . The set , in addition of composing the mps , has the natural metric induced by . More precisely, endow with the discrete metric and with the product topology. By Tychonoff Theorem, is a compact topological space, and the distance defined as

generates the topology of (to see this, just note that the cylinders – sets of elements with fixed entries in a finite number of positions – form a basis of topology of and each of them is a ball with respect to the metric ). Also, is homeomorphism. In fact, we leave as exercise to the reader to prove that

It is natural to wonder how general results of topological dynamics can be obtained and applied to this setting. This is what we are going to do in this post. The first section consists of the relations between arithmetic properties of and topological properties of . The second section is deeper and we prove van der Waerden theorem assuming a topological multiple recurrence theorem, which will be proved in ERT7. The main result of this post is, then,

Theorem 1 (van der Waerden) If , then some contains arbitrarily long arithmetic progressions.

1. Combinatorics of vs Topology of

The set is always a compact, totally disconnected set (because is) and transitive with respect to (the orbit of is dense in ).

Proposition 2 Let and its associated set.

(i) is finite if and only if there exist a finite set and an integer such that is the disjoint union

(ii) is thick if and only if .

(iii) if and only if .

Proof: (i) is finite if and only if is periodic for , that is, if and only if there exists such that . Considering , we obtain the desired conclusion.

(ii) If is thick, there are intervals , , such that . Then

which converges to if . For the opposite implication, the same argument works: if then, for every , there exists such that

that is, . As is arbitrary, is thick.

(iii) If , there exist intervals , , such that

Fix an integer and decompose as the union of intervals of length (except, at most, the last one). That is, write , , and into intervals of lenght and one of lenght ( is possibly empty). If is large, and then some is contained in , so that

Again, as is arbitrary, . Reciprocally, if , there exists, for each , an integer such that

that is, . This proves that .

The situation (i) happens if , where . These sets have low complexity and are highly structured sets formed by infinite arithmetic progressions.

Proposition 3 If is minimal, then is syndetic.

Proof: Take any and consider the clopen cylinder

By minimality, the set of return times of to is syndetic. But

and so , implying that is syndetic.

The converse is false. For example,

is syndetic, but contains the fixed point (this follows from Proposition 2, because ). This means we have to look for more conditions about to characterize minimality of .

Question. What are these conditions?

Given , consider the -limit of , defined as

We say that is recurrent if .

Definition 4 A set is called IP-set if it there exists an increasing sequence such that contains the set

Theorem 5 If is recurrent, then contains the translate of an IP-set.

Proof: Construct inductively an increasing sequence as follows: is any element of and, for every , is a positive integer greater than such that the first entries of and are equal, that is

This last condition means that

We’ll prove that . This is equivalent to , for every . The case is obvious:

Suppose for some . Then

which concludes the proof.

Corollary 6 Choose ramdomly, that is, each is in with probability . Then almost surely contains the translate of an IP-set.

Proof: Consider the probability in induced by the vector . By Poincaré Recurrence Theorem (see ERT1), almost-every is recurrent.

2. Proof of van der Waerden theorem

We know how to translate the notion of subsets of to symbolic spaces. How to encode a partition

to topology? Well, instead if considering , we take and, for the partition given in (1), associate the element defined as

Such association follows the same philosophy of the previous section: to , there is a natural partition . By the same reasons described in Section 1, is a compact metric space and the same happens to the orbit closure of with respect to the shift . In this encoding, by definition of the distance ,

Therefore, the existence of a monochromatic arithmetic progression is equivalent to , that is,

This condition is guaranteed by the

Theorem 7 (Furstenberg-Weiss topological multiple recurrence) Let be a continuous map of the compact metric space . Then, for any and , there exist and such that

Moreover, given any dense subset , we can take .

Consider the transformation . By Theorem 7, we can fix such that, for some , the element satisfies

which is exactly (2). This concludes the proof of Theorem 1.

Previous posts: ERT0, ERT1, ERT2, ERT3, ERT4, ERT5.

From the CERN English website:

CERN’s Visits Service organises tours of its experimental areas and facilities, which are free of charge. Tours in several languages are organised on Mondays to Saturdays starting at 9 a.m. and 2 p.m. It is essential to book in advance.
Please note that the tours are not suitable for children under 14 years of age.

(emphasis mine, as people say in history books).

Now from the French version:

Le service des visites du CERN organise des visites gratuites de sites d’expériences et d’infrastructures. Ces visites sont proposées en plusieurs langues, du lundi au samedi, à 9h ou à 14h. La réservation est obligatoire.
Veuillez noter que le niveau des visites n’est pas adapté aux enfants de moins de 10 ans.

I thought it might be good to have a post where I tried to take stock and assess the chances that Polymath5 will actually result in a solution to the Erdős discrepancy problem. But before I talk about that, I want to make the point, which I have made before, that solving the problem one sets out to solve is not a necessary condition for the attempt to count as worthwhile. There is easily enough material on the blog now for it to be possible to base a publishable paper on it, even if quite a lot of that paper ends up being a combination of a survey about the problem and a report on the interesting phenomena that have become apparent as a result of computations, some of which we understand reasonably well and some of which are still rather mysterious.

I am not saying this in order to hint that I think that it might be time to give up. At the moment it feels to me as though we still have momentum, so my enthusiasm is not flagging. What is mathematical momentum? I might define it as follows: an assault on an open problem has momentum if one’s understanding of the problem is continuing to develop. Right now I feel as though with each passing day I understand things about EDP that I did not understand before — and I presume that applies to everyone else too. And for as long as that is the case, one can never quite be sure that the problem won’t suddenly yield.

After Terry’s reduction of the problem to one about multiplicative functions, we have devoted almost all our attention to them. (Almost, but not quite: Klas and Alec are still trying to find a sequence of discrepancy 2 and length greater than 1124. It looks as though 1124 may be the upper bound though.) At this stage, I think it is fair to say that the main thing we are doing is playing around in multiplicative-function space, trying to get a feel for what it looks like. But this playing around has a serious purpose, as I shall now explain.

In my EDP4 post, I wrote about how there seem to be some very different kinds of multiplicative functions, which have unbounded partial sums for very different kinds of reasons. On the one hand you have functions like the Liouville function , which behaves fairly like a random function and therefore has partial sums that grow like (if you believe the Riemann hypothesis, and at least that fast unconditionally). On the other, there are functions like and , which have a great deal of additive structure (as well as their multiplicative structure) and give rise to logarithmic growth. Because of this, it felt as though one might be forced to classify multiplicative sequences to some extent. Some of them would be “similar to character-like functions” and would have unbounded partial sums for similar reasons to the reasons that apply to and , while others would be “not similar to character-like functions”, which would cause them to behave sufficiently randomly to have unbounded partial sums for that reason.

It is still conceivable that some kind of strategy like that could work, but certain difficulties with it have come to light. At one point, I had the following serious anxiety about the approach. The only proof I knew of that the partial sums of the Liouville function were unbounded went via the Riemann zeta function and some very special properties of . Therefore, in order to prove EDP it looked as though it would be necessary to find an entirely new, and highly generalizable, argument that applied to . And this looked as though it might be a known hard problem in number theory.

Fortunately, Terence Tao was able to supply a much simpler proof that these partial sums were unbounded. His proof relies on the fact that the Dirichlet convolution of with the constant function 1 is the characteristic function of the squares, which is a very special property of , so Terry’s proof does not look like the massively generalizable argument that one would need, but at least it is reassuringly elementary. It might still be worth trying to find new ways of understanding this fact, though.

However, I have another worry about the strategy of splitting multiplicative functions into those that are character-like and those that are not. It is that I now believe that there are probably multiplicative functions that have no obvious additive structure but that still have slow-growing partial sums. (For now let me say that the partial sums are slow-growing if they are bounded above by , but I think one might be able to get a small power of .) The evidence for this comes from thinking about algorithms for choosing the values at primes in a way that is designed to keep the partial sums small. The obvious algorithm is a greedy one: if the partial sum up to is positive then let , and if it is negative then let , and do what you like if it is zero. However, computations suggest that this fails spectacularly. I don’t know if anyone has a clear understanding of why this should be — I certainly don’t.

Equally mysterious is a fascinating discovery of Johan de Jong: that if you change your criterion slightly and choose if and only if the partial sum up to is less than -10, you do far better. I would love to have an explanation for this. I don’t care whether it is rigorous as long as it is convincing.

Those two links are part of a sub-conversation that starts here. I think that by this point is fairly safe to say that the experiments are telling us that multiplicative functions with slow-growing partial sums do not have to be all that structured. It is still possible that if you insist that the growth is at most logarithmic then your function is forced to be similar to a character-like function, but it also seems clear that we are not going to be able to prove big growth when the function is not similar to a character-like function.

To me this suggests that we may have to look for a unified proof after all. I do not feel 100% confident about this, but it is where my own energies are concentrated for the time being.

I’m still thinking aloud (or the bloggerly equivalent thereof) about the topic of my last post, and I’m at this delightful stage of guessing there may well be interesting questions there, and yet not knowing too precisely which ones are easy, which are impossible, or even which are already hidden in the maze of MathSciNet under cleverly disguised search terms.

So consider the case of G=SL(2,Z) again, and assume given a subgroup H. In broadest terms, we’re trying to identify which conjugacy classes in G have representatives in H. We can’t exclude that all of them do; if that happens, we know that (1) H is of infinite index (see the first comment by D. Speyer to the earlier post); (2) but H surjects, by reduction modulo p, to SL(2,Fp) for every p. The latter condition implies in particular that H be Zariski-dense in SL(2) (otherwise, its reduction would be in G(Fp) for some proper algebraic subgroup, and this would be strictly contained in SL(2,Fp) if p is large enough). Nicely enough, such subgroups (especially when finitely generated) are currently the topic of much work in terms of spectral theory, expansion and the like (see for instance these recent preprints by Bourgain, Gamburd and Sarnak, and by Bourgain and Kantorovich).

The conjugacy classes of G have been classified for a long time (for instance, this is needed for the Selberg Trace Formula). The most interesting, or at least those I’m going to look at first, are the so-called hyperbolic ones, which are characterized by the fact that, for some (unique) a>1, they contain a representative which is conjugate in SL(2,R) to

which acts as a dilation

on the Poincaré upper half-plane. A more direct characterization, in terms of an arbitrary representative g of the conjugacy class, is that

So, for instance, we can take the conjugacy class of

In the case of a conjugacy class in G, the dilation a is a real quadratic integer (it is the largest eigenvalue of the matrix, and the determinant, which gives the constant term of the minimal polynomial, is 1). In the example above, we get

In SL(2,R), the dilation is the unique invariant of a hyperbolic conjugacy class (and visibly any a>1 occurs as a dilation). In G, things get a bit more arithmetic (which means more complicated, though the two words are maybe not quite synonyms). Essentially (I am here forgetting or glossing over some important semi-technical issues), for a given discriminant

there are only finitely many G-conjugacy classes, and the number of them is the class number of the associated real quadratic field. (Precise details are given in this old paper of Sarnak).

From my point of view of conjugacy classes, the following seems the obvious salient features:

(1) to have a chance to find a given hyperbolic conjugacy class in a subgroup H, a necessary condition is that H contains a matrix with a certain trace (up to sign; if we assume that minus the identity is in H, the sign ambiguity disappears); this condition, in turn, is obviously susceptible to local congruence obstructions — but we know that for a Zariski-dense (finitely generated) subgroup of G, all but finitely many of these congruence obstructions modulo primes will vanish by Strong Approximation.

(2) if we have a subgroup where all local obstructions disappear (for instance, all reductions modulo primes are surjective; not I don’t actually have an example of a proper subgroup of infinite index where this holds…), we are led to wonder whether all ideal classes associated with hyperbolic elements of G have representatives in H; this question is reminiscent of the representation problem for integers by ternary definite quadratic forms (where there are fairly simple necessary conditions for this to happen, and those are fairly classically also sufficient for an integer to be representation by some form in the same genus as the given one, which means by some form everywhere locally equivalent to it, while the representability by the given form holds for sufficiently large integers by much deeper work involving Fourier coefficients of half-integral modular forms — a very beautiful story, where crucial work is due to Iwaniec and Duke and Schulze-Pillot).

As before, hopefully more to come…

I wasn’t expecting to have to write another post quite this soon, so this is another one where I don’t have much to say. Here are a few bits and bobs from the last lot of comments, but there’s plenty more in the comments themselves, and actually I think that it’s not that hard to browse through them now that we have depth-1 threading and quite a lot of the comments are very short.

Johan de Jong came up with a very interesting variant of the problem, in which is replaced by the space of polynomials over . I confess to being a little sad when the problem was solved negatively soon afterwards, as it had looked as though it might be a rather good model problem. However, the solution was nice.

One of the general aims at the moment is to try to show that a multiplicative function of bounded discrepancy must have some kind of character-like behaviour. Terence Tao has come up with an intriguing argument that shows not that but at least something in the right ball park.

Work has continued on a human proof that completely multiplicative sequences must have discrepancy greater than 2. It looks as though the proof will be complete before too long, and not too painful. Some nice tricks of Jason Dyer have come in helpful in reducing the amount of case analysis that is needed.

Theorem of the Day has a 'new acquisition': Haken;s Unknot Theorem

Theorem of the Day has a 'new acquisition': Lin McMullin's Theorem

Theorem of the Day has two 'new acquisitions': The Friendship Theorem and the Diaconis-Holmes-Montgomery Coin Tossing Theorem

The 2010 Theorem of the Day calendar is now available as a free download.

Theorem of the Day has a 'new acquisition': Heath's Finitely Discontinuous Function Theorem

Theorem of the Day has a 'new acquisition': Quadratic Nonresidue is Zero-Knowledge Provable

A preliminary download version of the 2010 Theorem of the Day calendar is now available.

Theorem of the Day has a 'new acquisition': the Classification of the Archimedean 4-Polytopes

Theorem of the Day has a 'new acquisition': the McIver-Neumann 1/2-n Bound

A colour-free version of Theorem no. 49, Netto's Conjecture, has been added.

Theorem of the Day has two 'new acquisitions': the Transversal Matroid Theorem and The Albert-Brauer-Hasse-Noether Main Theorem

Theorem of the Day has a 'new acquisition': The Lecture Hall Partition Theorem

Theorem of the Day has a 'new acquisition': a Tripartite Turán Theorem

Theorem of the Day has a 'new acquisition': The Remainder Theorem

Theorem of the Day has a 'new acquisition': Lamé's Theorem