Jordan Ellenberg, Richard Oberlin, and I have just uploaded to the arXiv the paper “The Kakeya set and maximal conjectures for algebraic varieties over finite fields“, submitted to Mathematika. This paper builds upon some work of Dvir and later authors on the Kakeya problem in finite fields, which I have discussed in this earlier blog post. Dvir established the following:

Kakeya set conjecture for finite fields.Let F be a finite field, and let E be a subset of that contains a line in every direction. Then E has cardinality at least for some .

The initial argument of Dvir gave . This was improved to for some explicit by Saraf and Sudan, and recently to by Dvir, Kopparty, Saraf, and Sudan, which is within a factor 2 of the optimal result.

In our work we investigate a somewhat different set of improvements to Dvir’s result. The first concerns the *Kakeya maximal function* of a function , defined for all directions in the projective hyperplane at infinity by the formula

where the supremum ranges over all lines in oriented in the direction . Our first result is the endpoint estimate for this operator, namely

Kakeya maximal function conjecture in finite fields.We have for some constant .

This result implies Dvir’s result, since if f is the indicator function of the set E in Dvir’s result, then for every . However, it also gives information on more general sets E which do not necessarily contain a line in every direction, but instead contain a certain fraction of a line in a subset of directions. The exponents here are best possible in the sense that all other mapping properties of the operator can be deduced (with bounds that are optimal up to constants) by interpolating the above estimate with more trivial estimates. This result is the finite field analogue of a long-standing (and still open) conjecture for the Kakeya maximal function in Euclidean spaces; we rely on the polynomial method of Dvir, which thus far has not extended to the Euclidean setting (but note the very interesting variant of this method by Guth that has established the endpoint multilinear Kakeya maximal function estimate in this setting, see this blog post for further discussion).

It turns out that a direct application of the polynomial method is not sufficient to recover the full strength of the maximal function estimate; but by combining the polynomial method with the Nikishin-Maurey-Pisier-Stein “method of random rotations” (as interpreted nowadays by Stein and later by Bourgain, and originally inspired by the factorisation theorems of Nikishin, Maurey, and Pisier), one can already recover a “restricted weak type” version of the above estimate. If one then enhances the polynomial method with the “method of multiplicities” (as introduced by Saraf and Sudan) we can then recover the full “strong type” estimate; a few more details below the fold.

It turns out that one can generalise the above results to more general affine or projective algebraic varieties over finite fields. In particular, we showed

Kakeya maximal function conjecture in algebraic varieties.Suppose that is an (n-1)-dimensional algebraic variety. Let be an integer. Then we havefor some constant , where the supremum is over all irreducible algebraic curves of degree at most d that pass through x but do not lie in W, and W(F) denotes the F-points of W.

The ordinary Kakeya maximal function conjecture corresponds to the case when N=n, W is the hyperplane at infinity, and the degree d is equal to 1. One corollary of this estimate is a Dvir-type result: a subset of which contains, for each x in W, an irreducible algebraic curve of degree d passing through x but not lying in W, has cardinality if . (In particular this implies a lower bound for Nikodym sets worked out by Li.) The dependence of the implied constant on W is only via the degree of W.

The techniques used in the flat case can easily handle curves of higher degree (provided that we allow the implied constants to depend on d), but the method of random rotations does not seem to work directly on the algebraic variety W as there are usually no symmetries of this variety to exploit. Fortunately, we can get around this by using a “random projection trick” to “flatten” W into a hyperplane (after first expressing W as the zero locus of some polynomials, and then composing with the graphing map for such polynomials), reducing the non-flat case to the flat case.

Below the fold, I wish to sketch two of the key ingredients in our arguments, the random rotations method and the random projections trick. (We of course also use some algebraic geometry, but mostly low-tech stuff, on the level of Bezout’s theorem, though we do need one non-trivial result of Kleiman (from SGA6), that asserts that bounded degree varieties can be cut out by a bounded number of polynomials of bounded degree.)

[Update, March 14: See also Jordan's own blog post on our paper.]

– The random rotations method –

The random rotations method allows one to amplify a result about large sets into an estimate about small sets, by observing that large sets can be created by taking many random rotations (or translations, etc.) of a given small set; it is useful in any situation which enjoys symmetries that one can push small sets around this way (e.g. a homogeneous space will do nicely). Let’s see how it works in this context. Dvir’s argument lets us give the following conclusion (stated somewhat informally):

Proposition 1.Let E be a subset of which contains lines in J different directions. If , then . (Implied constants here are allowed to depend on n.)

We now amplify this by the random rotations method to extend from the large J case to the small J case:

Proposition 2.Let E be a subset of which contains lines in J different directions. Then .

**Proof. **If then we are done by Proposition 1 already, so suppose that J is much smaller than . (There are only directions available in .) Let m be an integer such that .

We use the probabilistic method (and more precisely, the first moment method). Now let be m randomly chosen “rotations”, or more precisely invertible linear transformations, and consider the set . Clearly, . On the other hand, we expect to contain lines in about different directions. Indeed, pick any direction . Then has a probability about of being one of the J directions of the lines that E contains; this is also the probability that contains a line in the direction . If we choose each of the independently at random, then basic probability then tells us that for each direction , that E’ will contain a line in the direction with probability about . From linearity of expectation we thus see that the expected number of directions along which E’ contains a line is , so in particular we will have such lines for at least one choice of E’. Applying Proposition 1 to that choice we obtain , and so as required.

– The random projection trick –

The random projection trick is a different application of the probabilistic method. It uses the fact that random maps tend to be “mostly injective” whenever the range is larger than the domain (and, dually, are “mostly surjective” when the domain is larger than the range); this often allows one to cut either the domain or range down in size until they are roughly equal. It is used in a number of places in the literature, for instance in Ruzsa’s proof of Freiman’s theorem.

For instance, we have the following statement (stated a bit informally to simplify the formulation):

Lemma 1.Let E be a subset of , and let be a random linear transformation. If , then with high probability.

**Proof. **Consider the number of “collisions”,

.

On the one hand, each pair has a probability of of contributing a collision if x and y are distinct, and a probability 1 of contributing a collision if they are equal. Thus

.

From Markov’s inequality we conclude that with high probability.

On the other hand, we can write . Since , we conclude from the Cauchy-Schwarz inequality that

,

and the claim follows.

**Remark. ** While T is “mostly injective” once (in the sense that ), T will not be *completely* injective with high probability until , thanks to the birthday paradox.

Here is a typical way in which one can hope to use this trick for Kakeya-type problems. A simple modification of Dvir’s original argument (as done in this paper of Li) gives

Proposition 3.(Nikodym-type estimate) Let E be a subset of of size , and let be another set in such that for every point x in E, there exists a line passing through x such that G contains . Then .

The random rotations trick (or more precisely, the random translations trick) from the preceding section lets us extend this result to smaller values of |E| (shrinking |G| proportionally). But here I wish to discuss a different extension, using the random projections trick instead:

Proposition 3.(Nikodym-type estimate) Let . Let E be a subset of of size , and let be another set in such that for every point x in E, there exists a line passing through x such that G contains . Then .

**Proof. **By Lemma 1, we can find a linear map such that . Then observe that T(G) obeys the same hypotheses as G, but with E replaced by T(E). By Proposition 2, , and the claim follows.

–

## 23 comments

Comments feed for this article

13 March, 2009 at 4:53 pm

Liangpan LiWhat is the exact meaning of the notation “~” in Proposition 3 and many other places? Thanks.

13 March, 2009 at 6:32 pm

Liangpan LiNow let us talk about sets in the Euclidean spaces Rn. A Kakeya set is any set of points in Euclidean space which contains a unit line segment in every direction. In your 1999 Duke Math J. paper, you called a set E to be Nikodym if for every x belongs to Rn, there is a line L passing through x such that the intersection of L and E contains a unit line segment. This definition is different from the original definition of the Nikodym set by the Polish mathematician Otton M. Nikodym. OK, let us follow your definition. The famous Kakeya/Nikodym conjecture asserts that the Kakeya/Nikodym set has full (Hausdorff, Minkowski) dimension.

Given a COMPACT Nikodym set E in Rn, it is easy to see that E is also a Kakeya set. (Why? Choosing a direction e, let a person standing at the origin walk through the direction e, then …, then by the standard compactness argument, E contains a unit line segment in the direction e.) So a compact Nikodym set has both the properties of a Nikodym set and a Kakeya set. A compact Kakeya set need not to be a Nikodym set. Maybe people could first solve the Euclidean Nikoym set conjecture under the requirement that the set is also compact .

14 March, 2009 at 11:46 am

PeterThis might be a dumb question, but could it be easier to work with Kakeya sets in instead of in the reals?

14 March, 2009 at 1:57 pm

Terence TaoDear Liangpan: as stated in the post, the notation is an informal one; I use it to mean equivalence up to constants. One can of course reconstruct a formalised version of these propositions by going through the proofs (and more precise results of this type are in my paper with Jordan and Richard).

Dear Peter: Certainly all of the results over carry over to without difficulty; there is for instance a thesis of David Alvarez that works out some of this. One new feature in is the presence of subfields of index 2, which can cause some near-counterexamples to the Kakeya conjecture in this setting. For instance, in one has the Heisenberg group , which has five real dimensions (and thus has complex dimension 5/2, in some sense), and yet contains a four real dimensional (thus two complex dimensional, in some sense) family of complex lines. These lines are not all contained inside a complex plane, but they do contain many parallel lines and so this does not directly contradict the Kakeya conjecture in this setting; however it does indicate that in the presence of subfields, one does need to exploit the hypothesis that lines point in different directions. (Dvir’s argument, for instance, does this, and indeed his argument is insensitive to the presence of subfields.)

15 March, 2009 at 12:33 am

Scott McKuenCan any of the finite field results be carried over to the complex numbers by using the ideas from the earlier post on Serre’s paper and the Ax-Grothendieck theorem? Also, is anything known about the Kakeya problem in pseudofinite fields?

15 March, 2009 at 8:04 am

Terence TaoDear Scott,

It is of course a tantalising suggestion. The Kakeya problem in R or C is not of the “finitary algebraic” nature to which the type of transference principle mentioned in the Serre post applies directly, but there have been more indirect ways to transfer the _ideas_ from the finite field world to the continuous setting, as discussed for instance in my earlier post

http://terrytao.wordpress.com/2008/11/27/the-kakeya-conjecture-and-the-ham-sandwich-theorem/

Similarly, the Kakeya conjecture does not seem to be of the “first-order” type needed to easily move from finite fields to pseudofinite fields. In our paper with Jordan and Richard, we discuss briefly the possibility of extending the results to other fields and rings (and perhaps even to schemes) but it seems that some additional ideas are needed in order to get satisfactory results.

15 March, 2009 at 8:16 am

JSEScott, somebody else just asked me that last week! I agree with TT that it’s a very interesting question. Of course, the polynomial method relies crucially on the fact that the finite field is finite — the order of the field is used as a bound for degrees of polynomials throughout. (Where the polynomial method is used in a Euclidean setting, as in the work of Guth and Guth-Katz, you usually start by discretizing your problem in some way so that “a line has about N points,” and N then plays the role of |F|.)

Here’s a prequel to your question: is it clear what the right _statement_ of the Kakeya set and Kakeya maximal conjectures should be over a pseudo-finite field? For instance, are there examples of such fields which have nice enough metric structure for the desired bound on Hausdorff dimension to make sense? Or is there some other way in this setting that one should be able to say “Kakeya sets are big”?

16 March, 2009 at 11:08 pm

isotropyJSE – I believe pseudofinite fields come with model-theoretic notions of dimension and measure on definable sets that look somewhat like Hausdorff dimension and Hausdorff measure – I don’t know if they coincide (I don’t know anything about metric spaces over pseudofinite fields).

Ax showed any pseudofinite field is elementarily equivalent to an ultraproduct of finite fields. The underlying ultrafilter is on the set of prime powers, so it picks out certain orders of finite fields for the components of the ultraproduct – let be a component, of order , and let a ring formula defining a subset of .

Consider for each natural number the quantity:

If you look at this over all in the ultraproduct, and for some this quantity has a limit in the ultrafilter sense, then we say is the dimension of and is its measure. Like with Hausdorff dimension, is only nonzero and finite for at most one .

This might be a substitute notion of dimension for Kakeya sets in pseudofinite fields. I think this all comes from a 1992 paper of Chatzidakis, van den Dries, and Macintyre – “Definable Sets over Finite Fields” in Crelle’s.

16 March, 2009 at 11:11 pm

Scott McKuenSorry! That comment by “isotropy” was my response to JSE. Somehow my email got partly dumped into the name field.

6 April, 2009 at 3:57 am

oyunlarGreat news, thanks Scott!

11 May, 2009 at 10:49 am

Recent progress on the Kakeya conjecture « What’s new[...] and also generalises to other families of curves in algebraic varieties, as was done recently by Ellenberg, Oberlin, and myself (see this blog post for further discussion). There are even some tentative indications that these [...]

15 May, 2009 at 12:53 pm

The two-ends reduction for the Kakeya maximal conjecture « What’s new[...] Indeed, to deduce (2) from Conjecture 2 one can perform another dyadic decomposition, this time based on the dyadic range of the densities . Conversely, (2) implies Conjecture 2 in the case , and the remaining case can then be deduced by the random rotations trick (discussed in this earlier post). [...]

20 June, 2009 at 9:56 am

An equivalence between inverse sumset theorems and inverse conjectures for the U^3 norm « What’s new[...] Conjecture 3 was observed by Ruzsa; basically, the idea is to use the random projection trick (cf. this post) to view the set A in Conjecture 1 as a graph of a function over a base of cardinality roughly [...]

14 July, 2009 at 6:58 am

AnonymousDear Terry,

Concerning the paper mentioned at the very beginning of the post: could you kindly explain Remark 4.19? Either I don’t understand the construction, or I don’t see why it works; that is, why the set in question is a k-plane Kakeya set.

Thanks!

14 July, 2009 at 8:39 am

Terence TaoDear anonymous,

Given a n-k+1-dimensional Kakeya set E in , the set is a k-plane Kakeya set in . This is because given every orientation of a k-plane in , one can find a k-plane with that orientation whose intersection with is contained in a line (it may be a point or empty if the orientation is sufficiently “parallel” to ). Translating this plane around, one can eventually fit it inside E’.

4 May, 2010 at 2:47 am

ilyarazIt might be a silly question but nevertheless.

Suppose we have linearly independent -dimensional vectors over . We project them on a random -dimensional subspace. How can we estimate a probability that images will be linearly independent?

4 May, 2010 at 7:46 am

Terence TaoAs stated, your question is ambiguous because there is more than one way to project a vector space onto a subspace (this is not a Hilbert space, and one does not have a canonical orthogonal projection). But in general, when asking whether n vectors are linearly independent, a common way to proceed is to first compute the conditional probabilities that, for any fixed , that does not lie in the span of ; the final probability can then be obtained by integrating together all these conditional probabilities. In many situations one has enough independence or martingale structure that one can in fact just multiply together all the conditional probabilities rather than perform a complicated integral.

4 May, 2010 at 8:54 am

ilyarazTerm ‘projection’ is used incorrectly, I agree.

What I am trying to say is the following. Suppose we have matrix with a maximum rank (over ). We multiply it by a random matrix B. How can we estimate a probability that will have maximum rank?

4 May, 2010 at 10:42 am

Kenneth MaplesHi ilyaraz,

I’m assuming by random matrix you mean one chosen uniformly from the space of matrices over . Other distributions require a little more care.

Following Terry’s suggestion, we can observe that the columns of the product are independent random variables, so it suffices to study the probability that the th column of lies in the span of the previous columns, conditioning on the dimension of that span.

Each column of the product is of the form where is the th column of . The mapping is linear and surjective, so in particular the cardinalities of the fibres over each point are equal. In particular, our probability distribution (uniform) on the columns of pushes forward to the uniform probability distribution on the columns of . You can then calculate the chance that has full rank by direct counting, where the probability gets arbitrarily close to as you send ; the rate of convergence should be exponential in .

6 May, 2010 at 9:49 pm

AnonymousProf. Tao:

In the proof in the section “random projection method”, at the very end it says

and should be

Also, it seems that already stands for a number, not a set , so there is no need to use

[Corrected, thanks - T.]17 March, 2011 at 8:00 am

An incidence theorem in higher dimensions « What’s new[...] this strategy (and also a generic projection argument to cut down the ambient dimension, as used in this previous paper with Ellenberg and Oberlin, and an induction on dimension), we obtain in our paper a higher-dimensional incidence theorem: [...]

12 May, 2011 at 9:44 pm

Stein’s maximal principle « What’s new[...] been used repeatedly in harmonic analysis. For instance, I used the random rotations trick in a recent paper with Jordan Ellenberg and Richard Oberlin on Kakeya-type estimates in finite fields. The random sums trick is by now a standard tool to build [...]

18 December, 2011 at 7:09 pm

“Kakeya sets over non-archimedean local rings,” by Dummit and Hablicsek « Quomodocumque[...] this week by UW grad students Evan Dummit and Márton Hablicsek answers a question left open in a paper of mine with Richard Oberlin and Terry Tao. Let me explain why I was interested in this question and why I like Evan and Marci’s [...]