You are currently browsing the monthly archive for September 2007.
While working on my recent paper with Ben Green, I was introduced to the beautiful theorems of Marina Ratner on unipotent flows on homogeneous spaces, and their application to questions in number theory, such as the Oppenheim conjecture (first solved by Margulis, by establishing what can retrospectively be viewed as a special case of Ratner’s theorems). This is a subject that I am still only just beginning to learn, but hope to understand better in the future, especially given that quantitative analogues of Ratner’s theorems should exist, and should have even more applications to number theory (see for instance this recent paper of Einsiedler, Margulis, and Venkatesh). In this post, I will try to describe some of the background for this theorem and its connection with the Oppenheim conjecture; I will not discuss the proof at all, largely because I have not fully understood it myself yet. For a nice introduction to these issues, I recommend Dave Morris’ recent book on the subject (and this post here is drawn in large part from that book).
Ratner’s theorem takes place on a homogeneous space. Informally, a homogeneous space is a space X which looks “the same” when viewed from any point on that space. For instance, a sphere is a homogeneous space, but the surface of a cube is not (the cube looks different when viewed from a corner than from a point on an edge or on a face). More formally, a homogeneous space is a space X equipped with an action of a group G of symmetries which is transitive: given any two points x, y on the space, there is at least one symmetry g that moves x to y, thus y=gx. (For instance the cube has several symmetries, but not enough to be transitive; in contrast, the sphere has the transitive action of the special orthogonal group SO(3) as its symmetry group.) It is not hard to see that a homogeneous space X can always be identified (as a set with an action of G) with a quotient , where is a subgroup of G; indeed, one can take to be the stabiliser of an arbitrarily chosen point x in X, and then identify with . For instance, the sphere has an obvious action of the special orthogonal group SO(3), and the stabiliser of (say) the north pole can be identified with SO(2), so that the sphere can be identified with SO(3)/SO(2). More generally, any Riemannian manifold of constant curvature is a homogeneous space; for instance, an m-dimensional torus can be identified with , while a surface X of constant negative curvature can be identified with for some subgroup of (e.g. the hyperbolic plane is isomorphic to ). Furthermore, the cosphere bundle of X – the space of unit (co)tangent vectors on X – is also a homogeneous space with structure group . (For instance, the cosphere bundle of the hyperbolic plane is isomorphic to .)
For the purposes of Ratner’s theorem, we only consider homogeneous spaces X in which the symmetry group G is a connected finite-dimensional Lie group, and X is finite volume (or more precisely, it has a finite non-trivial G-invariant measure). Every compact homogeneous space is finite volume, but not conversely; for instance the modular curve is finite volume but not compact (it has a cusp). (The modular curve has two real dimensions, but just one complex dimension, hence the term “curve”; rather confusingly, it is also referred to as the “modular surface”. As for the term “modular”, observe that the moduli space of unimodular lattices in has an obvious action of , with the stabiliser of being , and so this moduli space can be identified with the modular curve.)
Ben Green and I have just uploaded our paper “The quantitative behaviour of polynomial orbits on nilmanifolds” to the arXiv (and shortly to be submitted to a journal, once a companion paper is finished). This paper grew out of our efforts to prove the Möbius and Nilsequences conjecture MN(s) from our earlier paper, which has applications to counting various linear patterns in primes (Dickson’s conjecture). These efforts were successful – as the companion paper will reveal – but it turned out that in order to establish this number-theoretic conjecture, we had to first establish a purely dynamical quantitative result about polynomial sequences in nilmanifolds, very much in the spirit of the celebrated theorems of Marina Ratner on unipotent flows; I plan to discuss her theorems in more detail in a followup post to this one.In this post I will not discuss the number-theoretic applications or the connections with Ratner’s theorem, and instead describe our result from a slightly different viewpoint, starting from some very simple examples and gradually moving to the general situation considered in our paper.
To begin with, consider a infinite linear sequence in the unit circle , where . (One can think of this sequence as the orbit of under the action of the shift operator on the unit circle.) This sequence can do one of two things:
- If is rational, then the sequence is periodic and thus only takes on finitely many values.
- If is irrational, then the sequence is dense in . In fact, it is not just dense, it is equidistributed, or equivalently that
for all continuous functions . This statement is known as the equidistribution theorem.
We thus see that infinite linear sequences exhibit a sharp dichotomy in behaviour between periodicity and equidistribution; intermediate scenarios, such as concentration on a fractal set (such as a Cantor set), do not occur with linear sequences. This dichotomy between structure and randomness is in stark contrast to exponential sequences such as , which can exhibit an extremely wide spectrum of behaviours. For instance, the question of whether is equidistributed mod 1 is an old unsolved problem, equivalent to asking whether is normal base 10.
Intermediate between linear sequences and exponential sequences are polynomial sequences , where P is a polynomial with coefficients in . A famous theorem of Weyl asserts that infinite polynomial sequences enjoy the same dichotomy as their linear counterparts, namely that they are either periodic (which occurs when all non-constant coefficients are rational) or equidistributed (which occurs when at least one non-constant coefficient is irrational). Thus for instance the fractional parts of are equidistributed modulo 1. This theorem is proven by Fourier analysis combined with non-trivial bounds on Weyl sums.
For our applications, we are interested in strengthening these results in two directions. Firstly, we wish to generalise from polynomial sequences in the circle to polynomial sequences in other homogeneous spaces, in particular nilmanifolds. Secondly, we need quantitative equidistribution results for finite orbits rather than qualitative equidistribution for infinite orbits .
Today I’d like to discuss a beautiful inequality in graph theory, namely the crossing number inequality. This inequality gives a useful bound on how far a given graph is from being planar, and has a number of applications, for instance to sum-product estimates. Its proof is also an excellent example of the amplification trick in action; here the main source of amplification is the freedom to pass to subobjects, which is a freedom which I didn’t touch upon in the previous post on amplification. The crossing number inequality (and its proof) is well known among graph theorists but perhaps not among the wider mathematical community, so I thought I would publicise it here.
In this post, when I talk about a graph, I mean an abstract collection of vertices V, together with some abstract edges E joining pairs of vertices together. We will assume that the graph is undirected (the edges do not have a preferred orientation), loop-free (an edge cannot begin and start at the same vertex), and multiplicity-free (any pair of vertices is joined by at most one edge). More formally, we can model all this by viewing E as a subset of , the set of 2-element subsets of V, and we view the graph G as an ordered pair G = (V,E). (The notation is set up so that .)
Now one of the great features of graphs, as opposed to some other abstract maths concepts, is that they are easy to draw: the abstract vertices become dots on a plane, while the edges become line segments or curves connecting these dots. [To avoid some technicalities we do not allow these curves to pass through the dots, except if the curve is terminating at that dot.] Let us informally refer to such a concrete representation D of a graph G as a drawing of that graph. Clearly, any non-trivial graph is going to have an infinite number of possible drawings. In some of these drawings, a pair of edges might cross each other; in other drawings, all edges might be disjoint (except of course at the vertices, where edges with a common endpoint are obliged to meet). If G has a drawing D of the latter type, we say that the graph G is planar.
Given an abstract graph G, or a drawing thereof, it is not always obvious as to whether that graph is planar; just because the drawing that you currently possess of G contains crossings, does not necessarily mean that all drawings of G do. The wonderful little web game “Planarity” illustrates this point excellently. Nevertheless, there are definitely graphs which are not planar; in particular the complete graph on five vertices, and the complete bipartite graph on two sets of three vertices, are non-planar.
There is in fact a famous theorem of Kuratowski that says that these two graphs are the only “source” of non-planarity, in the sense that any non-planar graph contains (a subdivision of) one of these graphs as a subgraph. (There is of course the even more famous four-colour theorem that asserts that every planar graphs is four-colourable, but this is not the topic of my post today.)
Intuitively, if we fix the number of vertices |V|, and increase the number of edges |E|, then the graph should become “increasingly non-planar”; conversely, if we keep the same number of edges |E| but spread them amongst a greater number of vertices |V|, then the graph should become “increasingly planar”. Is there a quantitative way to measure the “non-planarity” of a graph, and to formalise the above intuition as some sort of inequality?
Read the rest of this entry »
My colleague Ricardo Pérez-Marco showed me a very cute proof of Pythagoras’ theorem, which I thought I would share here; it’s not particularly earth-shattering, but it is perhaps the most intuitive proof of the theorem that I have seen yet.
In the above diagram, a, b, c are the lengths BC, CA, and AB of the right-angled triangle ACB, while x and y are the areas of the right-angled triangles CDB and ADC respectively. Thus the whole triangle ACB has area x+y.
Now observe that the right-angled triangles CDB, ADC, and ACB are all similar (because of all the common angles), and thus their areas are proportional to the square of their respective hypotenuses. In other words, (x,y,x+y) is proportional to . Pythagoras’ theorem follows.
I’d like to begin today by welcoming Timothy Gowers to the mathematics blogging community; Tim’s blog will also double as the “official” blog for the Princeton Companion to Mathematics, as indicated by his first post
which also contains links to further material (such as sample articles) on the Companion. Tim is already thinking beyond the blog medium, though, as you can see in his second post…
Anyway, this gives me an excuse to continue my own series of PCM articles. Some years back, Tim asked me to write a longer article on harmonic analysis – the quantitative study of oscillation, transforms, and other features of functions and sets on domains. At the time I did not fully understand the theme of the Companion, and wrote a rather detailed and technical survey of the subject, which turned out to be totally unsuitable for the Companion. I then went back and rewrote the article from scratch, leading to this article, which (modulo some further editing) is close to what will actually appear. (These two articles were already available on my web site, but not in a particularly prominent manner.) So, as you can see, the articles in the Companion are not exactly at the same level as the expository survey articles one sees published in journals.
I should also mention that some other authors for the Companion have put their articles on-line. For instance, Alain Connes‘ PCM article “Advice for the beginner“, aimed at graduate students just starting out in research mathematics, was in fact already linked to on one of the pages of this blog. I’ll try to point out links to other PCM articles in future posts in this series.
It occurred to me recently that the mathematical blog medium may be a good venue not just for expository “short stories” on mathematical concepts or results, but also for more technical discussions of individual mathematical “tricks”, which would otherwise not be significant enough to warrant a publication-length (and publication-quality) article. So I thought today that I would discuss the amplification trick in harmonic analysis and combinatorics (and in particular, in the study of estimates); this trick takes an established estimate involving an arbitrary object (such as a function f), and obtains a stronger (or amplified) estimate by transforming the object in a well-chosen manner (often involving some new parameters) into a new object, applying the estimate to that new object, and seeing what that estimate says about the original object (after optimising the parameters or taking a limit). The amplification trick works particularly well for estimates which enjoy some sort of symmetry on one side of the estimate that is not represented on the other side; indeed, it can be viewed as a way to “arbitrage” differing amounts of symmetry between the left- and right-hand sides of an estimate. It can also be used in the contrapositive, amplifying a weak counterexample to an estimate into a strong counterexample. This trick also sheds some light as to why dimensional analysis works; an estimate which is not dimensionally consistent can often be amplified into a stronger estimate which is dimensionally consistent; in many cases, this new estimate is so strong that it cannot in fact be true, and thus dimensionally inconsistent inequalities tend to be either false or inefficient, which is why we rarely see them. (More generally, any inequality on which a group acts on either the left or right-hand side can often be “decomposed” into the “isotypic components” of the group action, either by the amplification trick or by other related tools, such as Fourier analysis.)
The amplification trick is a deceptively simple one, but it can become particularly powerful when one is arbitraging an unintuitive symmetry, such as symmetry under tensor powers. Indeed, the “tensor power trick”, which can eliminate constants and even logarithms in an almost magical manner, can lead to some interesting proofs of sharp inequalities, which are difficult to establish by more direct means.
The most familiar example of the amplification trick in action is probably the textbook proof of the Cauchy-Schwarz inequality
for vectors v, w in a complex Hilbert space. To prove this inequality, one might start by exploiting the obvious inequality
but after expanding everything out, one only gets the weaker inequality
Now (3) is weaker than (1) for two reasons; the left-hand side is smaller, and the right-hand side is larger (thanks to the arithmetic mean-geometric mean inequality). However, we can amplify (3) by arbitraging some symmetry imbalances. Firstly, observe that the phase rotation symmetry preserves the RHS of (3) but not the LHS. We exploit this by replacing v by in (3) for some phase to be chosen later, to obtain
Now we are free to choose at will (as long as it is real, of course), so it is natural to choose to optimise the inequality, which in this case means to make the left-hand side as large as possible. This is achieved by choosing to cancel the phase of , and we obtain
This is closer to (1); we have fixed the left-hand side, but the right-hand side is still too weak. But we can amplify further, by exploiting an imbalance in a different symmetry, namely the homogenisation symmetry for a scalar , which preserves the left-hand side but not the right. Inserting this transform into (4) we conclude that
where is at our disposal to choose. We can optimise in by minimising the right-hand side, and indeed one easily sees that the minimum (or infimum, if one of v and w vanishes) is (which is achieved when when are non-zero, or in an asymptotic limit or in the degenerate cases), and so we have amplified our way to the Cauchy-Schwarz inequality (1). [See also this discussion by Tim Gowers on the Cauchy-Schwarz inequality.]