You are currently browsing the monthly archive for February 2008.

In Lecture 11, we studied compact measure-preserving systems – those systems $(X, {\mathcal X}, \mu, T)$ in which every function $f \in L^2(X, {\mathcal X}, \mu)$ was almost periodic, which meant that their orbit $\{ T^n f: n \in {\Bbb Z}\}$ was precompact in the $L^2(X, {\mathcal X}, \mu)$ topology. Among other things, we were able to easily establish the Furstenberg recurrence theorem (Theorem 1 from Lecture 11) for such systems.

In this lecture, we generalise these results to a “relative” or “conditional” setting, in which we study systems which are compact relative to some factor $(Y, {\mathcal Y}, \nu, S)$ of $(X, {\mathcal X}, \mu, T)$. Such systems are to compact systems as isometric extensions are to isometric systems in topological dynamics. The main result we establish here is that the Furstenberg recurrence theorem holds for such compact extensions whenever the theorem holds for the base. The proof is essentially the same as in the compact case; the main new trick is to not to work in the Hilbert spaces $L^2(X,{\mathcal X},\mu)$ over the complex numbers, but rather in the Hilbert module $L^2(X,{\mathcal X},\mu|Y, {\mathcal Y}, \nu)$ over the (commutative) von Neumann algebra $L^\infty(Y,{\mathcal Y},\nu)$. (Modules are to rings as vector spaces are to fields.) Because of the compact nature of the extension, it turns out that results from topological dynamics (and in particular, van der Waerden’s theorem) can be exploited to good effect in this argument.

[Note: this operator-algebraic approach is not the only way to understand these extensions; one can also proceed by disintegrating $\mu$ into fibre measures $\mu_y$ for almost every $y \in Y$ and working fibre by fibre. We will discuss the connection between the two approaches below.]

I’ve just uploaded to the arXiv the short note “A remark on primality testing and the binary expansion“, submitted to the Journal of the Australian Mathematical Society. In this note I establish the following result: for any sufficiently large integer n, there exists an n-bit prime p, such that the numbers $p \pm 2^i$ for $i=0,\ldots,n-1$ are all composite. In particular, if one flips any one of the bits in the binary expansion of the prime p, one obtains a composite number. As a consequence, one obtains the (rather plausible) consequence that in order to (deterministically) test whether an n-bit integer is prime or not, one needs (in the worst-case) to read all n bits of the prime. (This question was posed to me by my colleague here at UCLA, Yiannis Moschovakis.)

Primes p of the form mentioned in the above result are somewhat rare at first; the first some prime is $1973 = 11110110101_2$. But in fact, the argument in my note shows that the set of such primes actually has positive relative density inside the set of all primes. (Amusingly, this means that one can apply a theorem of Ben Green and myself and conclude that there are arbitrarily long arithmetic progressions of such primes, although I doubt that there is any particular significance or application to this conclusion.)

The same remark applies to other bases; thus, for instance, there exist infinitely many prime numbers with the property that if one changes any one of the base 10 digits of that number, one obtains a composite number. (Presumably the first such number can be located by computer search, though I did not attempt to do so.) [Update, Feb 25: see comments.]

In the previous lecture, we studied the recurrence properties of compact systems, which are systems in which all measurable functions exhibit almost periodicity – they almost return completely to themselves after repeated shifting. Now, we consider the opposite extreme of mixing systems – those in which all measurable functions (of mean zero) exhibit mixing – they become orthogonal to themselves after repeated shifting. (Actually, there are two different types of mixing, strong mixing and weak mixing, depending on whether the orthogonality occurs individually or on the average; it is the latter concept which is of more importance to the task of establishing the Furstenberg recurrence theorem.)

We shall see that for weakly mixing systems, averages such as $\frac{1}{N} \sum_{n=0}^{N-1} T^n f \ldots T^{(k-1)n} f$ can be computed very explicitly (in fact, this average converges to the constant $(\int_X f\ d\mu)^{k-1}$). More generally, we shall see that weakly mixing components of a system tend to average themselves out and thus become irrelevant when studying many types of ergodic averages. Our main tool here will be the humble Cauchy-Schwarz inequality, and in particular a certain consequence of it, known as the van der Corput lemma.

As one application of this theory, we will be able to establish Roth’s theorem (the k=3 case of Szemerédi’s theorem).

Last month, at the joint AMS/MAA meeting in San Diego, I spoke at the AMS “Current Events” Bulletin on the topic “Why are solitons stable?“. This talk was supposed to be a survey of many of the developments on the rigorous stability theory of solitary waves in dispersive wave models (e.g. the Kortweg-de Vries equation and its generalisations, nonlinear Schrödinger equations, etc.), although my actual talk (which was the usual 50 minutes in length) only managed to cover about half of the material I had planned.

More recently, I completed the article that accompanies the talk, and which will be submitted to the Bulletin of the American Mathematical Society. In this paper I describe the key conflict in these wave models between dispersion (the tendency of waves of differing frequency to move at different speeds, thus causing any localised wave to disperse in space over time) and nonlinearity (which can cause any concentrated portion of the wave to self-amplify). Solitons seem to lie at the exact balancing point between these two forces, neither dispersing nor amplifying, but instead simply traveling at a constant velocity or oscillating in phase at a constant rate. In some cases, this balancing point is unstable; remove even a tiny amount of mass from the soliton and it eventually disperses completely into radiation, or one can add a tiny amount and cause the soliton to concentrate into a point and thence exhibit blowup in finite time. In other cases, the balancing point is stable; small perturbations to a soliton may end up changing the amplitude, position, and/or velocity of the soliton slightly, but the bulk of the solution still closely resembles a soliton in size, shape, and behaviour. Stability is sometimes enforced by linear properties, such as dispersive estimates or spectral properties of the linearised dynamics, but is also often enforced by nonlinear properties, such as nonlinear conservation laws, monotonicity formulae, and local propagation estimates for mass and energy (such as those provided by virial identities). The interplay between all these properties can be remarkably subtle, especially in the critical case when a key conserved quantity is scale-invariant (thus leading to an additional degeneracy in the soliton manifold). This is particularly evident in the remarkable series of papers by Martel and Merle establishing various stability and blowup properties near the ground state soliton of the critical generalised KdV equation, which I spend some time discussing (without going into too many of the (quite numerous) technical details). The focus in my paper is primarily on the non-integrable case, in which the techniques are primarily analytic rather than algebraic or geometric.

[This post is authored by Luca Trevisan. – T.]

Notions of “quasirandomness” for graphs and hypergraphs have many applications in combinatorics and computer science. Several past posts by Terry have addressed the role of quasirandom structures in additive combinatorics. A recurring theme is that if an object (a graph, a hypergraph, a subset of integers, …) is quasirandom, then several useful properties can be immediately deduced, but, also, if an object is not quasirandom then it possesses some “structure” than can be usefully exploited in an inductive argument. The contrapositive statements of such randomness-structure dichotomies are that certain simple properties imply quasirandomness. One can view such results as algorithms that can be used to “certify” quasirandomness, and the existence (or, in some cases, conjectural non-existence) of such algorithms has implications in computer science, as I shall discuss in this post.
Read the rest of this entry »

This week there is a conference here at IPAM on expanders in pure and applied mathematics. I was an invited speaker, but I don’t actually work in expanders per se (though I am certainly interested in them). So I spoke instead about the recent simplified proof by Kleiner of the celebrated theorem of Gromov on groups of polynomial growth. (This proof does not directly mention expanders, but the argument nevertheless hinges on the absence of expansion in the Cayley graph of a group of polynomial growth, which is exhibited through the smoothness properties of harmonic functions on such graphs.)

The newly elected Australian Prime Minister, Kevin Rudd, apologises to the “Stolen Generation” of indigenous Australians for past government policies.

The primary objective of this lecture and the next few will be to give a proof of the Furstenberg recurrence theorem (Theorem 2 from the previous lecture). Along the way we will develop a structural theory for measure-preserving systems.

The basic strategy of Furstenberg’s proof is to first prove the recurrence theorems for very simple systems – either those with “almost periodic” (or compact) dynamics or with “weakly mixing” dynamics. These cases are quite easy, but don’t manage to cover all the cases. To go further, we need to consider various combinations of these systems. For instance, by viewing a general system as an extension of the maximal compact factor, we will be able to prove Roth’s theorem (which is equivalent to the k=3 form of the Furstenberg recurrence theorem). To handle the general case, we need to consider compact extensions of compact factors, compact extensions of compact extensions of compact factors, etc., as well as weakly mixing extensions of all the previously mentioned factors.

In this lecture, we will consider those measure-preserving systems $(X, {\mathcal X}, \mu, T)$ which are compact or almost periodic. These systems are analogous to the equicontinuous or isometric systems in topological dynamics discussed in Lecture 6, and as with those systems, we will be able to characterise such systems (or more precisely, the ergodic ones) algebraically as Kronecker systems, though this is not strictly necessary for the proof of the recurrence theorem.

In this lecture, we describe the simple but fundamental Furstenberg correspondence principle which connects the “soft analysis” subject of ergodic theory (in particular, recurrence theorems) with the “hard analysis” subject of combinatorial number theory (or more generally with results of “density Ramsey theory” type). Rather than try to set up the most general and abstract version of this principle, we shall instead study the canonical example of this principle in action, namely the equating of the Furstenberg multiple recurrence theorem with Szemerédi’s theorem on arithmetic progressions.
Read the rest of this entry »

This Thursday I was at the University of Sydney, Australia, giving a public lecture on a favourite topic of mine, “Structure and randomness in the prime numbers“. My slides here are a merge between my slides for a Royal Society meeting and the slides I gave for the UCLA Science Colloquium; now that I figured out to use Powerpoint a little bit better, I was able to make the latter a bit more colourful (and the former less abridged).