Ultrafilters, nonstandard analysis, and epsilon management

This post is in some ways an antithesis of my previous postings on hard and soft analysis. In those posts, the emphasis was on taking a result in soft analysis and converting it into a hard analysis statement (making it more “quantitative” or “effective”); here we shall be focusing on the reverse procedure, in which one harnesses the power of infinitary mathematics – in particular, ultrafilters and nonstandard analysis – to facilitate the proof of finitary statements.

Arguments in hard analysis are notorious for their profusion of “epsilons and deltas”. In the more sophisticated arguments of this type, one can end up having an entire army of epsilons that one needs to manage, in particular choosing each epsilon carefully to be sufficiently small compared to other parameters (including other epsilons), while of course avoiding an impossibly circular situation in which a parameter is ultimately required to be small with respect to itself, which is absurd. This art of epsilon management, once mastered, is not terribly difficult – it basically requires one to mentally keep track of which quantities are “small”, “very small”, “very very small”, and so forth – but when these arguments get particularly lengthy, then epsilon management can get rather tedious, and also has the effect of making these arguments unpleasant to read. In particular, any given assertion in hard analysis usually comes with a number of unsightly quantifiers (For every there exists an N…) which can require some thought for a reader to parse. This is in contrast with soft analysis, in which most of the quantifiers (and the epsilons) can be cleanly concealed via the deployment of some very useful terminology; consider for instance how many quantifiers and epsilons are hidden within, say, the Heine-Borel theorem: “a subset of a Euclidean space is compact if and only if it is closed and bounded”.

For those who practice hard analysis for a living (such as myself), it is natural to wonder if one can somehow “clean up” or “automate” all the epsilon management which one is required to do, and attain levels of elegance and conceptual clarity comparable to those in soft analysis, hopefully without sacrificing too much of the “elementary” or “finitary” nature of hard analysis in the process.

A quantitative form of the Besicovitch projection theorem via multiscale analysis

I’ve just uploaded a new paper to the arXiv entitled “A quantitative form of the Besicovitch projection theorem via multiscale analysis“, submitted to the Journal of the London Mathematical Society. In the spirit of my earlier posts on soft and hard analysis, this paper establishes a quantitative version of a well-known theorem in soft analysis, in this case the Besicovitch projection theorem. This theorem asserts that if a subset E of the plane has finite length (in the Hausdorff sense) and is purely unrectifiable (thus its intersection with any Lipschitz graph has zero length), then almost every linear projection E to a line will have zero measure. (In contrast, if E is a rectifiable set of positive length, then it is easy to show that all but at most one linear projection of E will have positive measure, basically thanks to the Rademacher differentiation theorem.)

A concrete special case of this theorem relates to the product Cantor set K, consisting of all points (x,y) in the unit square whose base 4 expansion consists only of 0s and 3s. This is a compact one-dimensional set of finite length, which is purely unrectifiable, and so Besicovitch’s theorem tells us that almost every projection of K has measure zero. (One consequence of this, first observed by Kahane, is that one can construct Kakeya sets in the plane of zero measure by connecting line segments between one Cantor set and another.)

The Lebesgue differentiation theorem and the Szemeredi regularity lemma

This post is a sequel of sorts to my earlier post on hard and soft analysis, and the finite convergence principle. Here, I want to discuss a well-known theorem in infinitary soft analysis – the Lebesgue differentiation theorem – and whether there is any meaningful finitary version of this result. Along the way, it turns out that we will uncover a simple analogue of the Szemerédi regularity lemma, for subsets of the interval rather than for graphs. (Actually, regularity lemmas seem to appear in just about any context in which fine-scaled objects can be approximated by coarse-scaled ones.) The connection between regularity lemmas and results such as the Lebesgue differentiation theorem was recently highlighted by Elek and Szegedy, while the connection between the finite convergence principle and results such as the pointwise ergodic theorem (which is a close cousin of the Lebesgue differentiation theorem) was recently detailed by Avigad, Gerhardy, and Towsner.

The Lebesgue differentiation theorem has many formulations, but we will avoid the strongest versions and just stick to the following model case for simplicity:

Lebesgue differentiation theorem. If is Lebesgue measurable, then for almost every we have . Equivalently, the fundamental theorem of calculus is true for almost every x in [0,1].

Here we use the oriented definite integral, thus . Specialising to the case where is an indicator function, we obtain the Lebesgue density theorem as a corollary:

Lebesgue density theorem. Let be Lebesgue measurable. Then for almost every , we have as , where |A| denotes the Lebesgue measure of A.

In other words, almost all the points x of A are points of density of A, which roughly speaking means that as one passes to finer and finer scales, the immediate vicinity of x becomes increasingly saturated with A. (Points of density are like robust versions of interior points, thus the Lebesgue density theorem is an assertion that measurable sets are almost like open sets. This is Littlewood’s first principle.) One can also deduce the Lebesgue differentiation theorem back from the Lebesgue density theorem by approximating f by a finite linear combination of indicator functions; we leave this as an exercise.

STOC talk: The condition number of a randomly perturbed matrix

This week I am in San Diego for the 39th ACM Symposium for the Theory of Computing (STOC). Today I presented my work with Van Vu on the condition number of randomly perturbed matrices, which was the subject of an earlier post on this blog. For this short talk (20 minutes), Van and I prepared some slides; of course, in such a short time frame one cannot hope to discuss many of the details of the result, but one can at least convey the statement of the result and a brief sketch of the main ideas in the proof.

One late update (which didn’t make it onto the slides): last week, an alternate proof of some cases of our main result (together with some further generalisations and other results, in particular a circular law for the eigenvalues of discrete random matrices) was obtained by Pan and Zhou, using earlier arguments by Rudelson and Vershynin.

[Update, June 16: It was pointed out to me that the Pan-Zhou result only recovers our result in the case when the unperturbed matrix has a spectral norm of (our result assumes that the unperturbed matrix has polynomial size). Slides also updated.]

Advice on mathematical careers, and mathematical writing

For the last year or so, I’ve maintained two advice pages on my web site: one for career advice to students in mathematics, and another for authors wishing to write and submit papers (for instance, to one of the journals I am editor of). It occurred to me, though, that an advice page is particularly well suited to the blog medium, due to the opportunities for feedback that this medium affords (and especially given that many of my readers have more mathematical experience than I do).

I have thus moved these pages to my blog; my career advice page is now here, and my advice for writing and submitting papers is now here. I also took the opportunity to split up these rather lengthy pages into lots of individual subpages, which allowed for easier hyperlinking, and also to expand each separate topic somewhat (for instance, each topic is now framed by an appropriate quotation). Each subpage is also open to comments, as I am hoping to get some feedback to improve each of them.

[Update, June 10: Of course, the comments page for this post, and for the pages mentioned above, are also a good place to post your own tips on mathematical writing or careers. :-) ]

Open question: The parity problem in sieve theory

The parity problem is a notorious problem in sieve theory: this theory was invented in order to count prime patterns of various types (e.g. twin primes), but despite superb success in obtaining upper bounds on the number of such patterns, it has proven to be somewhat disappointing in obtaining lower bounds. [Sieves can also be used to study many other things than primes, of course, but we shall focus only on primes in this post.] Even the task of reproving Euclid’s theorem – that there are infinitely many primes – seems to be extremely difficult to do by sieve theoretic means, unless one of course injects into the theory an estimate at least as strong as Euclid’s theorem (e.g. the prime number theorem). The main obstruction is the parity problem: even assuming such strong hypotheses as the Elliott-Halberstam conjecture (a sort of “super-generalised Riemann Hypothesis” for sieves), sieve theory is largely (but not completely) unable to distinguish numbers with an odd number of prime factors from numbers with an even number of prime factors. This “parity barrier” has been broken for some select patterns of primes by injecting some powerful non-sieve theory methods into the subject, but remains a formidable obstacle in general.

I’ll discuss the parity problem in more detail later in this post, but I want to first discuss how sieves work [drawing in part on some excellent unpublished lecture notes of Iwaniec]; the basic ideas are elementary and conceptually simple, but there are many details and technicalities involved in actually executing these ideas, and which I will try to suppress for sake of exposition.