The Kakeya conjecture and the Ham Sandwich theorem

One of my favourite family of conjectures (and one that has preoccupied a significant fraction of my own research) is the family of Kakeya conjectures in geometric measure theory and harmonic analysis.  There are many (not quite equivalent) conjectures in this family.  The cleanest one to state is the set conjecture:

Kakeya set conjecture: Let , and let contain a unit line segment in every direction (such sets are known as Kakeya sets or Besicovitch sets).  Then E has Hausdorff dimension and Minkowski dimension equal to n.

One reason why I find these conjectures fascinating is the sheer variety of mathematical fields that arise both in the partial results towards this conjecture, and in the applications of those results to other problems.  See for instance this survey of Wolff, my Notices article and this article of Łaba on the connections between this problem and other problems in Fourier analysis, PDE, and additive combinatorics; there have even been some connections to number theory and to cryptography.  At the other end of the pipeline, the mathematical tools that have gone into the proofs of various partial results have included:

• Maximal functions, covering lemmas, methods (Cordoba, Strömberg, Cordoba-Fefferman);
• Fourier analysis (Nagel-Stein-Wainger);
• Multilinear integration (Drury, Christ)
• Paraproducts (Katz);
• Combinatorial incidence geometry (Bourgain, Wolff);
• Multi-scale analysis (Barrionuevo, Katz-Łaba-Tao, Łaba-Tao, Alfonseca-Soria-Vargas);
• Probabilistic constructions (Bateman-Katz, Bateman);
• Additive combinatorics and graph theory (Bourgain, Katz-Łaba-Tao, Katz-Tao, Katz-Tao);
• Sum-product theorems (Bourgain-Katz-Tao);
• Bilinear estimates (Tao-Vargas-Vega);
• Perron trees (Perron, Schoenberg, Keich);
• Group theory (Katz);
• Low-degree algebraic geometry (Schlag, Tao, Mockenhaupt-Tao);
• High-degree algebraic geometry (Dvir, Saraf-Sudan);
• Heat flow monotonicity formulae (Bennett-Carbery-Tao)

[This list is not exhaustive.]

Very recently, I was pleasantly surprised to see yet another mathematical tool used to obtain new progress on the Kakeya conjecture, namely (a generalisation of) the famous Ham Sandwich theorem from algebraic topology.  This was recently used by Guth to establish a certain endpoint multilinear Kakeya estimate left open by the work of Bennett, Carbery, and myself.  With regards to the Kakeya set conjecture, Guth’s arguments assert, roughly speaking, that the only Kakeya sets that can fail to have full dimension are those which obey a certain “planiness” property, which informally means that the line segments that pass through a typical point in the set must be essentially coplanar. (This property first surfaced in my paper with Katz and Łaba.)  Guth’s arguments can be viewed as a partial analogue of Dvir’s arguments in the finite field setting (which I discussed in this blog post) to the Euclidean setting; in particular, both arguments rely crucially on the ability to create a polynomial of controlled degree that vanishes at or near a large number of points.  Unfortunately, while these arguments fully settle the Kakeya conjecture in the finite field setting, it appears that some new ideas are still needed to finish off the problem in the Euclidean setting.  Nevertheless this is an interesting new development in the long history of this conjecture, in particular demonstrating that the polynomial method can be successfully applied to continuous Euclidean problems (i.e. it is not confined to the finite field setting).

In this post I would like to sketch some of the key ideas in Guth’s paper, in particular the role of the Ham Sandwich theorem (or more precisely, a polynomial generalisation of this theorem first observed by Gromov).

Structure and Randomness: pages from year one of mathematical blog

The AMS has just notified me that the book version of the first year of my blog, now retitled “Structure and Randomness: pages from year one of a mathematical blog“, is now available.  An official web page for this book has also been set up here, though it is fairly empty at present.  A (2MB) high-resolution PDF file of the cover can be found here.

I plan to start on converting this year’s blog posts to book form in January, and hopefully the process should be a little faster this time.  Given that my lecture notes on ergodic theory and on the Poincaré conjecture will form the bulk of that book, I have chosen the working title for that book to be “Poincaré’s legacies: pages from year two of a mathematical blog“.

Marker lecture IV: “Sieving for almost primes and expanders”

In this final lecture in the Marker lecture series, I discuss the recent work of Bourgain, Gamburd, and Sarnak on how arithmetic combinatorics and expander graphs were used to sieve for almost primes in various algebraic sets.

Marker lecture III: “Small gaps between primes”

In the third Marker lecture, I would like to discuss the recent progress, particularly by Goldston, Pintz, and Yıldırım, on finding small gaps between consecutive primes.  (See also the surveys by Goldston-Pintz-Yıldırım, by Green, and by Soundararajan on the subject; the material here is based to some extent on these prior surveys.)

Marker lectures II, “Linear equations in primes”

This week I am at Penn State University, giving this year’s Marker lectures.  My chosen theme for my four lectures here is “recent developments in additive prime number theory”.  My first lecture, “Long arithmetic progressions in primes”, is similar to my AMS lecture on the same topic and so I am not reposting it here.  The second lecture, the notes for which begin after the fold, is on “Linear equations in primes”.  These two lectures focus primarily on work of myself and Ben Green.  The third and fourth lectures, entitled “Small gaps between primes” and “Sieving for almost primes and expander graphs”, will instead be focused on the work of Goldston-Yildirim-Pintz and Bourgain-Gamburd-Sarnak respectively.

Some notes on “non-classical” polynomials in finite characteristic

Let be an integer.  The concept of a polynomial of one variable of degree (or ) can be defined in one of two equivalent ways:

• (Global definition) is a polynomial of degree iff it can be written in the form for some coefficients .
• (Local definition) is a polynomial of degree if it is k-times continuously differentiable and .

From single variable calculus we know that if P is a polynomial in the global sense, then it is a polynomial in the local sense; conversely, if P is a polynomial in the local sense, then from the Taylor series expansion

we see that P is a polynomial in the global sense. We make the trivial remark that we have no difficulty dividing by here, because the field is of characteristic zero.

The above equivalence carries over to higher dimensions:

• (Global definition) is a polynomial of degree iff it can be written in the form for some coefficients .
• (Local definition) is a polynomial of degree if it is k-times continuously differentiable and for all .

Again, it is not difficult to use several variable calculus to show that these two definitions of a polynomial are equivalent.

The purpose of this (somewhat technical) post here is to record some basic analogues of the above facts in finite characteristic, in which the underlying domain of the polynomial P is F or for some finite field F.  In the “classical” case when the range of P is also the field F, it is a well-known fact (which we reproduce here) that the local and global definitions of polynomial are equivalent.  But in the “non-classical” case, when P ranges in a more general group (and in particular in the unit circle ), the global definition needs to be corrected somewhat by adding some new monomials to the classical ones .  Once one does this, one can recover the equivalence between the local and global definitions.

(The results here are derived from forthcoming work with Vitaly Bergelson and Tamar Ziegler.)

A counterexample to a strong polynomial Freiman-Ruzsa conjecture

One of my favourite open problems in additive combinatorics is the polynomial Freiman-Ruzsa conjecture, which Ben Green guest blogged about here some time ago.  It has many equivalent formulations (which is always a healthy sign when considering a conjecture), but here is one involving “approximate homomorphisms”:

Polynomial Freiman-Ruzsa conjecture. Let be a function which is an approximate homomorphism in the sense that for all and some set .  Then there exists a genuine homomorphism such that takes at most values.

Remark 1. The key point here is that the bound on the range of is at most polynomial in |S|.  An exponential bound of can be trivially established by splitting into the subspace spanned by S (which has size at most ) and some complementary subspace, and then letting g be the projection of f to that complementary subspace.

Recently, Ben Green and I have shown that this conjecture is equivalent to a certain polynomially quantitative strengthening of the inverse conjecture for the Gowers norm ; I hope to talk about this in a future post.  For this (somewhat technical) post, I want to comment on a possible further strengthening of this conjecture, namely

Strong Polynomial Freiman-Ruzsa conjecture. Let be a function which is an approximate homomorphism in the sense that for all and some set .  Then there exists a genuine homomorphism such that takes values in the sumset for some fixed .

This conjecture is known to be true for certain types of set S (e.g. for Hamming balls, this is a result of Farah).  Unfortunately, it is false in general; the purpose of this post is to describe one counterexample (related to the failure of the inverse conjecture for the Gowers norm for for classical polynomials; in particular, the arguments here have several features in common with those in the papers of Lovett-Meshulam-Samorodnitsky and Green-Tao).  [A somewhat different counterexample also appears in the paper of Farah.]  The verification of the counterexample is surprisingly involved, ultimately relying on the multidimensional Szemerédi theorem of Furstenberg and Katznelson.

(The results here are derived from forthcoming joint work with Ben Green.)

Concentration compactness and the profile decomposition

One of the most important topological concepts in analysis is that of compactness (as discussed for instance in my Companion article on this topic).  There are various flavours of this concept, but let us focus on sequential compactness: a subset E of a topological space X is sequentially compact if every sequence in E has a convergent subsequence whose limit is also in E.  This property allows one to do many things with the set E.  For instance, it allows one to maximise a functional on E:

Proposition 1. (Existence of extremisers)  Let E be a non-empty sequentially compact subset of a topological space X, and let be a continuous function.  Then the supremum is attained at at least one point , thus for all .  (In particular, this supremum is finite.)  Similarly for the infimum.

Proof. Let be the supremum .  By the definition of supremum (and the axiom of (countable) choice), one can find a sequence in E such that .  By compactness, we can refine this sequence to a subsequence (which, by abuse of notation, we shall continue to call ) such that converges to a limit x in E.  Since we still have , and f is continuous at x, we conclude that f(x)=L, and the claim for the supremum follows.  The claim for the infimum is similar. 

Remark 1. An inspection of the argument shows that one can relax the continuity hypothesis on F somewhat: to attain the supremum, it suffices that F be upper semicontinuous, and to attain the infimum, it suffices that F be lower semicontinuous.

We thus see that sequential compactness is useful, among other things, for ensuring the existence of extremisers.  In finite-dimensional spaces (such as vector spaces), compact sets are plentiful; indeed, the Heine-Borel theorem asserts that every closed and bounded set is compact.  However, once one moves to infinite-dimensional spaces, such as function spaces, then the Heine-Borel theorem fails quite dramatically; most of the closed and bounded sets one encounters in a topological vector space are non-compact, if one insists on using a reasonably “strong” topology.  This causes a difficulty in (among other things) calculus of variations, which is often concerned to finding extremisers to a functional on a subset E of an infinite-dimensional function space X.

In recent decades, mathematicians have found a number of ways to get around this difficulty.  One of them is to weaken the topology to recover compactness, taking advantage of such results as the Banach-Alaoglu theorem (or its sequential counterpart).  Of course, there is a tradeoff: weakening the topology makes compactness easier to attain, but makes the continuity of F harder to establish.  Nevertheless, if F enjoys enough “smoothing” or “cancellation” properties, one can hope to obtain continuity in the weak topology, allowing one to do things such as locate extremisers.  (The phenomenon that cancellation can lead to continuity in the weak topology is sometimes referred to as compensated compactness.)

Another option is to abandon trying to make all sequences have convergent subsequences, and settle just for extremising sequences to have convergent subsequences, as this would still be enough to retain Theorem 1.  Pursuing this line of thought leads to the Palais-Smale condition, which is a substitute for compactness in some calculus of variations situations.

But in many situations, one cannot weaken the topology to the point where the domain E becomes compact, without destroying the continuity (or semi-continuity) of F, though one can often at least find an intermediate topology (or metric) in which F is continuous, but for which E is still not quite compact.  Thus one can find sequences in E which do not have any subsequences that converge to a constant element , even in this intermediate metric.  (As we shall see shortly, one major cause of this failure of compactness is the existence of a non-trivial action of a non-compact group G on E; such a group action can cause compensated compactness or the Palais-Smale condition to fail also.)  Because of this, it is a priori conceivable that a continuous function F need not attain its supremum or infimum.

Nevertheless, even though a sequence does not have any subsequences that converge to a constant x, it may have a subsequence (which we also call ) which converges to some non-constant sequence (in the sense that the distance between the subsequence and the new sequence in a this intermediate metric), where the approximating sequence is of a very structured form (e.g. “concentrating” to a point, or “travelling” off to infinity, or a superposition of several concentrating or travelling profiles of this form).  This weaker form of compactness, in which superpositions of a certain type of profile completely describe all the failures (or defects) of compactness, is known as concentration compactness, and the decomposition of the subsequence is known as the profile decomposition.  In many applications, it is a sufficiently good substitute for compactness that one can still do things like locate extremisers for functionals F –  though one often has to make some additional assumptions of F to compensate for the more complicated nature of the compactness.  This phenomenon was systematically studied by P.L. Lions in the 80s, and found great application in calculus of variations and nonlinear elliptic PDE.  More recently, concentration compactness has been a crucial and powerful tool in the non-perturbative analysis of nonlinear dispersive PDE, in particular being used to locate “minimal energy blowup solutions” or “minimal mass blowup solutions” for such a PDE (analogously to how one can use calculus of variations to find minimal energy solutions to a nonlinear elliptic equation); see for instance this recent survey by Killip and Visan.

In typical applications, the concentration compactness phenomenon is exploited in moderately sophisticated function spaces (such as Sobolev spaces or Strichartz spaces), with the failure of traditional compactness being connected to a moderately complicated group G of symmetries (e.g. the group generated by translations and dilations).  Because of this, concentration compactness can appear to be a rather complicated and technical concept when it is first encountered.  In this note, I would like to illustrate concentration compactness in a simple toy setting, namely in the space of absolutely summable sequences, with the uniform () metric playing the role of the intermediate metric, and the translation group playing the role of the symmetry group G.  This toy setting is significantly simpler than any model that one would actually use in practice [for instance, in most applications X is a Hilbert space], but hopefully it serves to illuminate this useful concept in a less technical fashion.

The inverse conjecture for the Gowers norm over finite fields via the correspondence principle

Tamar Ziegler and I have just uploaded to the arXiv our paper, “The inverse conjecture for the Gowers norm over finite fields via the correspondence principle“, submitted to Analysis & PDE.  As announced a few months ago in this blog post, this paper establishes (most of) the inverse conjecture for the Gowers norm from an ergodic theory analogue of this conjecture (in a forthcoming paper by Vitaly Bergelson, Tamar Ziegler, and myself, which should be ready shortly), using a variant of the Furstenberg correspondence principle.  Our papers were held up for a while due to some unexpected technical difficulties arising in the low characteristic case; as a consequence, our paper only establishes the full inverse conjecture in the high characteristic case , and gives a partial result in the low characteristic case .

In the rest of this post, I would like to describe the inverse conjecture (in both combinatorial and ergodic forms), and sketch how one deduces one from the other via the correspondence principle (together with two additional ingredients, namely a statistical sampling lemma and a local testability result for polynomials).