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).
— The polynomial Ham Sandwich theorem —
Let us first recall the classical Ham Sandwich theorem:
Ham Sandwich theorem. Let be n bounded open sets in . Then there exists a hyperplane in that divides each of the open sets into two sets of equal volume.
(The name of the theorem derives from the special case when and are two slices of bread and a slice of ham. One can view this theorem as a “thickened” version of the Euclidean geometry axiom that every n points in determine at least one hyperplane.)
There are many proofs of this theorem, but I will focus on the proof that is based on the Borsuk-Ulam theorem:
Borsuk-Ulam theorem: Let be a continuous map from the n-dimensional sphere to the Euclidean space which is antipodal (which means that for all . Then for at least one .
Proof. (Sketch) The set of zeroes of an antipodal map automatically come in antipodal pairs x,-x. To prove the theorem, we shall establish the stronger fact that for an odd number of disjoint antipodal pairs, counting multiplicity (avoiding the degenerate antipodal maps which vanish at an infinite set of points). To see this, first observe that this is true for at least one antipodal map (e.g. one can use the horizontal projection map ). Also, the space of all antipodal maps is a vector space, and thus connected (though it takes some effort to show that the space of non-degenerate antipodal maps is still connected). So one just needs to show that the parity of the number of pairs of antipodal points where f vanishes (counting multiplicity) is unchanged with respect to continuous deformations of f. But some elementary degree theory (or Morse theory) shows that any (non-degenerate) perturbation of f can annihilate two such antipodal pairs by collision, or (by the reverse procedure) spontaneously create two such antipodal pairs from nothing, but cannot otherwise affect the number of pairs; thus the parity of the number of such pairs remains invariant. (It takes some non-trivial effort to make this informal argument rigorous; see for instance this chapter of Matousek’s book on the Borsuk-Ulam theorem, which also contains a number of other proofs of this result. [Thanks to Benny Sudakov for this great reference.] One can also formalise this argument using the language of singular cohomology.)
Remark 1. The Borsuk-Ulam theorem is tied to the more general theory of Lyusternik-Schnirelmann category, which is the viewpoint taken in Guth’s paper, but we will not explicitly use this theory here.
Proof of the Ham-Sandwich theorem using the Borsuk-Ulam theorem. We can identify with the space of affine-linear forms on . Each non-trivial affine-linear form determines a hyperplane that divides into two half-spaces and . We can then define to be the function whose coordinate at P is the volume of minus the volume of ; thus f measures the extent to which the hyperplane fails to bisect all of the . It is easy to see that f is continuous, homogeneous of degree zero, and odd, and so its restriction to is an antipodal map. By the Borsuk-Ulam theorem, there exists P such that , and the claim follows.
Gromov observed the following polynomial generalisation of the Ham Sandwich theorem:
Polynomial Ham Sandwich theorem. Let , and let be bounded open sets in . Then there exists a non-trivial polynomial of degree at most d such that the sets , partition each of the into two sets of equal measure.
Note that the ordinary Ham-Sandwich theorem corresponds to the d=1 case of this theorem. This theorem can be deduced from the Borsuk-Ulam theorem in exactly the same way that the ordinary one is (note that the space of polynomials of degree at most d has dimension ; the continuity of the appropriate antipodal function follows from the dominated convergence theorem and the basic observation that a non-trivial polynomial is non-zero almost everywhere).
Remark 2. One can also deduce the polynomial Ham Sandwich theorem directly from the ordinary Ham Sandwich theorem (in dimensions) by embedding into via the Veronese embedding, and then thickening the images of slightly in an appropriate fashion; we leave the details as an exercise to the reader.
The polynomial Ham Sandwich theorem should be compared with the following finitary counterpart, which morally corresponds to the case when all the are points (but works over arbitrary fields F), and which was a key tool in Dvir’s proof of the Kakeya conjecture in finite fields:
Lemma. Let and let be points in for some field F. Then there exists a non-trivial polynomial of degree at most d which vanishes on all of .
Proof. The evaluation map is a linear map from a -dimensional space to a -dimensional space, and must therefore have a non-trivial kernel.
— Connection with the Kakeya problem —
Now we connect the polynomial Ham Sandwich theorem to the Kakeya problem. We begin by replacing the continuous Kakeya set conjecture with a more quantitative “-discretised” problem:
Kakeya maximal conjecture. Let , and let be a collection of cylindrical tubes pointing in a -separated set of directions (thus the directions of any two of the tubes make an angle of at least ). For each , let be the set of points x which are contained in at least of the tubes . Then the volume of obeys the bound for any .
Here we are using the asymptotic notation that if for some positive constant c (if the is subscripted by parameters, this indicates that c is allowed to depend on those parameters); we always allow constants to depend on the dimension n. This conjecture (which is limiting the extent to which tubes in different directions can overlap) implies the Kakeya set conjecture (for both Minkowski and Hausdorff dimension) by fairly standard arguments from geometric measure theory, see e.g. this paper of Bourgain or these lecture notes of myself. The factor of is natural (and best possible), as can be seen by considering the example in which and all the tubes pass through a common point.
[The name “maximal conjecture” has to do with the formulation of the above conjecture involving the Kakeya maximal function, which I will not discuss here.]
The maximal conjecture (and the set conjecture) is verified in the two-dimensional case (with the one-dimensional case being trivial), but only partial results are known in higher dimensions. However, one can do better if one only considers certain types of overlap. Let us say (somewhat informally) that a point x has non-planar multiplicity with respect to a given collection of tubes if there exist separate families of tubes each passing through x, such that given any tubes from each of these families, the solid angle between the directions is comparable to 1. (Informally, this is a stronger assertion than saying that x has tubes passing through it, because we prohibit these tubes from being essentially contained in a hyperplane). Then, as a special case of Guth’s results, one has
Multilinear Kakeya conjecture (special case): Let be as in the Kakeya maximal conjecture, and let be the set of points with non-planar multiplicity . Then .
Informally, this implies that the only counterexamples to the Kakeya maximal conjecture can come from configurations of tubes such that the tubes that pass through a typical point largely lie in a hyperplane. A previous paper of Bennett, Carbery, and myself established this estimate with an additional loss of by a totally different method (based on heat flow monotonicity formulae). For a precise statement of the full multilinear Kakeya conjecture (which is now proven without any epsilon loss), I refer you to that paper (or the paper of Guth).
Let’s now sketch why the above result is true (details can be found in the paper of Guth). I’ll drop the dependence of implied constants on n. Let be a maximal -net of (i.e. a set of -separated points in that is maximal with respect to set inclusion), then it will suffice to show that
(1).
Let be the cube of sidelength centred at with sides parallel to the axes. Applying the polynomial Ham Sandwich theorem, we can find a non-trivial polynomial P of degree whose zero locus bisects each of the cubes .
For each j, we claim that the hypersurfaces have surface area . Indeed, if instead one of the had surface area , this would imply that the projection of to any (n-1)-dimensional coordinate subspace of has area , in contrast with the projection of itself which has area . Thus for each the complement of V in contains a subset of of relative density that consists entirely of line segments of length in the basis direction . From this it is not hard to see that contains a path-connected component of relative density , which contradicts the claim that bisects .
On the other hand, we know that meets tubes , which are arranged in a non-planar fashion. Because of this, one can show that for a “typical” tube hitting , the projection of to the orthogonal complement of the direction of has area . (Basically, the point is that at any given point of , the normal vector cannot be perpendicular (or close to perpendicular) to all the directions of all the simultaneously, due to non-planarity.) To simplify the exposition, let us assume that in fact all tubes touching are typical.
Each touches tubes (they may touch more than this, but for sake of exposition let us suppose that they touch exactly this number of tubes). By double counting, this means that each tube touches about
(2)
cubes on the average, where the inequality in (2) comes from the -separated directions of the tubes. In particular, we can find a (typical) tube which touches at least such balls. Let be the direction vector of .
Now look at . (Technically, one has to replace by a slight thickening of itself here, but let us ignore this technicality.) This set contains disjoint sets of the form . Each of these sets, when projected to the orthogonal complement of , has measure . On the other hand, itself, when projected to this complement, has a measure of . By the pigeonhole principle, we may thus find a positive measure family of lines in the direction passing through which intersect at of the . In particular, all lines in this family intersect V in different points.
On the other hand, the restriction of P to is a polynomial of degree . If this degree is much less than , this forces P to vanish on each line [cf. Dvir’s argument]; since the set of such lines has positive measure, this forces P to be identically zero, a contradiction. Hence we must have
which when combined with (2), gives (1).
22 comments
Comments feed for this article
27 November, 2008 at 11:12 pm
Anonymous
Errata:
When The Polynomial Ham Sanwich theorem is stated, the subindex of the sets are not well writed. It may be changed by .
Yours,
Jordi-Lluis Figeras Romero
28 November, 2008 at 10:17 am
Anonymous
Why do you call it “Borsak-Ulam theorem” instead of “Borsuk-Ulam theorem”?
28 November, 2008 at 2:34 pm
Terence Tao
Thanks for the corrections!
29 November, 2008 at 7:56 pm
terence tao’s blog « orgtheory.net
[…] simply called “What’s new?” Much of it is research level math (e.g., “The Kakeya Conjecture and the Ham Sandwich Theorem“), but I think any practicing academic might enjoy his career advice. Skip over parts that […]
30 November, 2008 at 12:01 am
Anonymous
I have a related question about theorem naming/attribution. In your additive combinatorics book, on numerous occasions you use a non-lexicographical name for a theorem (such as, say, the “Bob-Alice theorem”). I don’t want to give specific examples as to not make this into a discussion involving specific results/individuals, but a glance through the index will produce several example. Is there a particular significance to these cases?
30 November, 2008 at 5:51 am
bengreen
One I can think of is “Balog-Szemeredi-Gowers theorem”. This result states that if a set inside some ambient abelian group has many additive quadruples then there is a large subset of which has small doubling. The theorem was proved in this qualitative form by Balog and Szemeredi, but some time later Tim Gowers supplied a new proof that gave much more quantitative information concerning the relationship between “many” and “large” in the above statement. In the form that the result is typically used, it should perhaps be called “Gowers’ theorem”, but that would be to ignore the contribution of Balog and Szemeredi in identifying that this was the right kind of question to ask. One might talk, then, of a result of Balog-Szemeredi and Gowers, in which case the standard ordering seems to be the right one. Another factor in this is that Gowers generally talks of “the Balog-Szemeredi theorem” in his lectures and papers, and so to many of us in the subject the words Balog and Szemeredi simply cannot be split in this context.
I’m interested to know how generally well-known it is that pure mathematicians use simple alphabetical ordering on their papers, a practice that does not seem to be the norm in other branches of science, where the ordering conveys all sorts of mysterious information. For example, has Terry himself ever received comment on his being the second, third or fourth author on the great majority of his papers?
30 November, 2008 at 8:02 am
tom
The practice of using strict lexicographical ordering of authors is probably not-well known at all outside pure maths. Now if we look at a list of theorems on wikipedia we see such a rule does suffer regularly some exceptions when one wishes to convey some chronological information (e.g. the theorems called Heine-Borel, Nash-Moser, Poincaré-Hopf… ).
The “mysterious information” Ben alludes to is in fact quite rational, it’s just some folk knowledge one learns along the way, e.g. in biology the last name is that of the big boss, the first one that of the hard-working postdoc, and those in between being other less-involved postdocs/senior guys/lab technicians.
As long as people are aware that other rules may apply outside of their own area, I would imagine no serious confusion would arise.
4 December, 2008 at 7:24 pm
asdf
The mathematics in this post is no doubt very interesting, but I’m unable to think about it because the repeated mention of ham sandwiches has made me hungry. Off to dinner!
6 February, 2009 at 7:23 am
Spencer
Hi everyone,
Perhaps somebody here could shed some light on the following for me:
In Prof. Tao’s 1999 paper “The Bochner Riesz Conjecture implies the Restriction Conjecture” he states a whole collection of conjectures in harmonic analysis/geometric measure and produces a very helpful diagram (on what is page 372 of the journal in which it appears) depicting the relationships between these conjectures (which ones imply which other ones). This diagram seems to show that Bochner Riesz implies the Minkowski dimension part of the Kakeya set Conjecture.
Also, on Izabella Laba’s page about conections between Kakeya and harmonic analysis (http://www.math.ubc.ca/~ilaba/kakeya.html) she states that Fefferman’s counterexample to the ball multiplier conjecture “would provide a counterexample to the Bochner-Riesz conjecture, if one could construct a Besicovitch set in Rn of Hausdorff dimension less than n.” So the claim here is surely that Bochner Riesz implies the Hausdorff dimension part of the Kakeya Set Conjecture.
What has confused me greatly is that there is a paper on the arxiv by Yong Cheol Kim (arXiv:math/0407013v3 [math.CA]) entitled “A proof of the Bochner Riesz Conjecture”.
The details of most of what I’ve referenced are beyond me at present so I have not checked the maths but I was certainly under the impression that Kakeya had not been solved. Could anyone point out to me what’s gone wrong here?
Many Thanks,
Spencer
6 February, 2009 at 7:45 am
Terence Tao
Dear Spencer,
The Kim paper is known to be incorrect, though I do not know why the author (who has acknowledged the error) has not yet withdrawn it from the arXiv.
6 February, 2009 at 2:26 pm
Spencer
Ah right, I thought that that might be the case.
Many Thanks.
12 March, 2009 at 4:25 pm
The Kakeya set and maximal conjectures for algebraic varieties over finite fields « What’s new
[…] that has established the endpoint multilinear Kakeya maximal function estimate in this setting, see this blog post for further […]
11 May, 2009 at 10:49 am
Recent progress on the Kakeya conjecture « What’s new
[…] bisects a ball, then the intersection of that hypersurface with the ball has a large area; see this blog post for further […]
20 November, 2010 at 1:11 pm
The Guth-Katz bound on the Erdős distance problem « What’s new
[…] of cell decomposition. A key new insight is that the polynomial method (and more specifically, the polynomial Ham Sandwich theorem, discussed previously on this blog) can be used to efficiently create […]
17 March, 2011 at 8:00 am
An incidence theorem in higher dimensions « What’s new
[…] Geometry. In this paper we use the polynomial Ham Sandwich method of Guth and Katz (as discussed previously on this blog) to establish higher-dimensional versions of the Szemerédi-Trotter […]
6 October, 2011 at 9:47 am
拓扑学奇趣之Borsuk-Ulam定理 « Fight with Infinity
[…] Tao The Kakeya conjecture and the Ham Sandwich theorem […]
25 September, 2013 at 11:03 pm
El teorema del revuelto de patatas y pimientos | Cifras y Teclas
[…] de la demostración en Mathworld, en inglés. También en inglés, te recomiendo esta entrada de Terence Tao. Si prefieres leer algo en español, puedes hacerlo en esta entrada de Pablo Soberón. El propio […]
19 January, 2014 at 4:23 pm
El teorema del revuelto de patatas y pimientos | cocinaymatematicas
[…] tienes una idea de la demostración en Mathworld, en inglés. También en inglés, te recomiendoesta entrada de Terence Tao. Si prefieres leer algo en español, puedes hacerlo en esta entrada de Pablo Soberón. El propio […]
1 October, 2016 at 7:39 pm
Hu
people have not found counter example with Kakeya set conjecture with any dimension n,do they?
[The Kakeya conjecture is currently open – T.]
5 July, 2019 at 11:04 pm
Anonymous
from each of these three families (why three? typo?)
[Corrected, thanks – T.]
1 January, 2021 at 7:37 pm
Anonymous
Is it possible to show that the extension equivalent version of the restriction conjecture implies Kakeya directly? Without using this very fact, that it’s equivalent to restriction.
4 December, 2021 at 9:30 pm
Kakeya 转针问题 & 何为维度 – 南外数学逻辑与生活社
[…] Kakeya 猜想与拓扑中的 Ham Sandwich Theorem — https://terrytao.wordpress.com/2008/11/27/the-kakeya-conjecture-and-the-ham-sandwich-theorem/ […]