Posted by: Izabella Laba | March 23, 2008

The Kakeya problem in finite fields

The Kakeya problem, in its best known formulation, is the following. Let E \subset {\bf R}^n be a set which contains a translate of every unit line segment; equivalently, for every direction e\in S^{n-1}, E contains a unit line segment parallel to e. An n-dimensional ball of radius 1/2 is a simple example of a set with this property, but there are many other such sets, some of which have n-dimensional measure 0 (an old construction of Besicovitch). Can E be even smaller than that and have Hausdorff dimension strictly smaller than n? The conjectured answer is no. This is known in dimension 2 (due to Davies), but open otherwise.

This is one of the “big” problems in harmonic analysis, with an interesting history, relations to several major conjectures in the field, and intriguing connections to other areas of mathematics. There are many expositions available; here is the link to my latest one, in case you are interested.

There is a variant of the problem set in a vector space over a finite field, rather than in the Euclidean space. Let q be a large prime, and let {\bf F}_q^n be the n-dimensional vector space over the q-element field {\bf F}_q. A line in {\bf F}_q^n is the q-element set \{a, a+v, a+2v,\dots, a+(q-1)v\}, where a,v\in {\bf F}_q^n are fixed vectors and v\neq 0. Note that if v' is a multiple of v, then the lines defined by a,v and a,v' coincide.

A Kakeya set is a set E\subset {\bf F}_q^n which contains a translate of every line. Is it true that every Kakeya set must have cardinality at least C_n q^n, where C_n is a constant depending only on the dimension n, but not on q? This question was first formulated in an expository paper by Tom Wolff in the late 1990s, and addressed in several subsequent papers (Mockenhaupt-Tao 2004, Tao 2005, Bourgain-Katz-Tao 2004).

The reason for this post is that this problem appears to have just been solved! Only a few days ago, Zeev Dvir posted a paper on the arXiv where he proves that Kakeya sets in {\bf F}_q^n must have cardinality at least C_\epsilon q^{n-\epsilon} for any \epsilon>o, with the constant independent of q. This is best possible except for the endpoint.

The idea of the proof is quite beautiful and genuinely new in this context. Consider the space of all homogeneous polynomials over {\bf F}_q of degree d in n variables x_1,\dots,x_n, where d=q-2; this space has dimension d+n-1\choose n-1. If the Kakeya set E has cardinality smaller than that, then there is a polynomial, say g, which vanishes on E. But because E is Kakeya set, this implies via some simple algebraic manipulations that g must in fact have at least q^n zeros, which contradicts a theorem of Schwartz and Zippel bounding the number of such zeros. A well-known product set argument completes the proof of the bound stated above.

There is, of course, a verification process that has to take place. However, Dvir’s argument is very short (only about two pages) and easy to check. I’m not familiar with the Schwartz-Zippel theorem, which plays a key role in the proof, but I’m sure that it is receiving a lot of renewed scrutiny right now.

Is this how the “real” Euclidean problem will be solved? First of all, I don’t expect any 2-page proofs in the Euclidean case. There are just too many technicalities to deal with. That said, Dvir’s idea could be the most significant new contribution to the subject in years. It has been suspected, now and then, that further improvements in Kakeya bounds might involve some sort of algebraic structure - except that of course we didn’t know how to do it. While Dvir’s argument is specific to finite fields, there is a very good chance that it will inspire further work in the Euclidean setting. I have no idea whether this might actually resolve the problem, but I’m pretty sure that we should at least see further developments in this direction.

Update, March 25: Dvir’s paper has now been updated to include an additional argument (due to Alon and Tao) that proves the endpoint estimate. This resolves completely the finite field Kakeya conjecture.

Posted in research math

« Housekeeping notes
Andrzej Hulanicki, 1933-2008 »

Responses

[...] Mar 25: See also these posts by Izabella Laba and Jordan [...]

By: Dvir’s proof of the finite field Kakeya conjecture « What’s new on March 25, 2008
at 7:53 am

[...] in every direction. Dvir proved that every Kakeya set has at least c_n q^n elements. (Hat tip to The Accidental Mathematician for alerting me to Dvir’s [...]

By: Give the people (who like the Kakeya problem) what they want « Quomodocumque on March 25, 2008
at 6:41 pm

Are you familiar with the fundamental theorem of algebra? Do you think it might be carefully reexamined soon, too?

By: anonymous on March 26, 2008
at 3:55 pm

Anonymous aka Snarky Snark:

I was under the impression that the results of Schwartz and Zippel go a little bit beyond the fundamental theorem of algebra. Otherwise they wouldn’t have been published as research papers not so long ago, would they? And no, not everybody has to be familiar with them.

If those results do get carefully reexamined, then what would be wrong with that? That’s what should happen, as far as I’m concerned. In fact I’d be reading those papers right now if I weren’t sick. Because that’s what many of us do when a big result in our area gets proved. We examine the proof, including the results that it relies on where possible - not just to check for correctness, but also to understand the argument better.

A new application of an old theorem can put that theorem in a new light and lead to questions that wouldn’t have been thought of otherwise. We will want to know how far the argument extends, or whether similar ideas can be used in other settings, and for that we will need to know how the Schwartz-Zippel theorem works. Even if there turn out to be no such extensions, at least we will have learned something that we didn’t know before. Which is always a good thing.

By: Izabella Laba on March 26, 2008
at 8:14 pm

Leave a response






Your response:

Categories