Idle question: are Kakeya sets winning?

Jayadev Athreya was here last week and reminded me about this notion of “winning sets,” which I learned about from Howie Masur — originally, one of the many contributions of Wolfgang Schmidt.

Here’s a paper by Curt McMullen introducing a somewhat stronger notion, “absolute winning.”

Anyway:  a winning set (or an absolute winning set) in R^n is “big” in some sense.  In particular, it has to have full Hausdorff dimension, but it doesn’t have to have positive measure.

Kakeya sets (subsets of R^n containing a unit line segment in every direction) can have measure zero, by the Besicovitch construction, and are conjectured (when n=2, known) to have Hausdorff dimension n.  So should we expect these sets to be winning?  Are Besicovitch sets winning?

I have no reason to need to know.  I just think these refined classifications of sets which are measure 0 yet still “large” are very interesting.  And for all I know, maybe there are sets where the easiest way to prove they have full Hausdorff dimension is to prove they’re winning!

An incidence conjecture of Bourgain over fields of positive characteristic (with Hablicsek)

Marci Hablicsek (a finishing Ph.D. student at UW) and I recently posted a new preprint, “An incidence conjecture of Bourgain over fields of finite characteristic.”

The theme of the paper is a beautiful theorem of Larry Guth and Nets Katz, one of the early successes of Dvir’s “polynomial method.”  They proved a conjecture of Bourgain:

Given a set S of points in R^3, and a set of N^2 lines such that

• No more than N lines are contained in any plane;
• Each line contains at least N points of S;

then S has at least cN^3 points.

In other words, the only way for a big family of lines to have lots of multiple intersections is for all those lines to be contained in a plane.  (In the worst case where all the lines are in a plane, the incidences between points and lines are governed by the Szemeredi-Trotter theorem.)

I saw Nets speak about this in Wisconsin, and I was puzzled by the fact that the theorem only applied to fields of characteristic 0, when the proof was entirely algebraic.  But you know the proof must fail somehow in characteristic p, because the statement isn’t true in characteristic p.  For example, over the field k with p^2 elements, one can check that the Heisenberg surface

$X: x - x^p + yz^p - zy^p = 0$

has a set of p^4 lines, no more than p lying on any plane, and such that each line contains at least p^2 elements of X(k).  If the Guth-Katz theorem were true over k, we could take N = p^2 and conclude that |X(k)| is at least p^6.  But in fact, it’s around p^5.

It turns out that there is one little nugget in the proof of Guth-Katz which is not purely algebraic.  Namely:  they show that a lot of the lines are contained in some surface S with the following property;  at every smooth point s of S, the tangent plane to S at s intersects S with multiplicity greater than 2.  They express this in the form of an assertion that a certain curvature form vanishes everywhere.  In characteristic 0, this implies that S is a plane.  But not so in characteristic p!  (As always, the fundamental issue is that a function in characteristic p can have zero derivative without being constant — viz., x^p.)  All of us who did the problems in Hartshorne know about the smooth plane curve over F_3 with every point an inflection point.  Well, there are surfaces like that too (the Heisenberg surface is one such) and the point of the new paper is to deal with them.  In fact, we show that the Guth-Katz theorem is true word for word as long as you prevent lines not only from piling up in planes but also from piling up in these “flexy” surfaces.

It turns out that any such surface must have degree at least p, and this enables us to show that the Guth-Katz theorem is actually true, word for word, over the prime field F_p.

If you like, you can think of this as a strengthening of Dvir’s theorem for the case of F_p^3.  Dvir proves that a set of p^2 lines with no two lines in the same direction fills up a positive-density subset of the whole space.  What we prove is that the p^2 lines don’t have to point in distinct directions; it is enough to impose the weaker condition that no more than p of them lie in any plane; this already implies that the union of the lines has positive density.  Again, this strengthening doesn’t hold for larger finite fields, thanks to the Heisenberg surface and its variants.

This is rather satisfying, in that there are other situations in this area (e.g. sum-product problems) where there are qualitatively different bounds depending on whether the field k in question has nontrivial subfields or not.  But it is hard to see how a purely algebraic argument can “see the difference” between F_p and F_{p^2}.  The argument in this paper shows there’s at least one way this can happen.

Satisfying, also, because it represents an unexpected application for some funky characteristic-p algebraic geometry!  I have certainly never needed to remember that particular Hartshorne problem in my life up to now.

“Kakeya sets over non-archimedean local rings,” by Dummit and Hablicsek

A new paper posted this week on the arXiv 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 answer so much!

Recall:  a Kakeya set in an n-dimensional vector space over a field k is a set containing a line (or, in the case k = R, a unit line segment) in every direction.  The “Kakeya problem,” phrased loosely, is to prove that Kakeya sets cannot be too small.

But what does “small” mean?  You might want it to mean “measure 0” but for the small but important fact that in this interpretation the problem has a negative answer:  as Besicovitch discovered in 1919, there are Kakeya sets in R^2 with measure 0!  So Kakeya’s conjecture concerns a stronger notion of “small”  — he conjectures that a Kakeya set in R^n cannot have Hausdorff or Minkowski dimension strictly smaller than n.

(At this point, if you haven’t thought about the Kakeya conjecture before, you might want to read Terry’s long expository post about the Kakeya conjecture and Dvir’s theorem; I cannot do it any better here.)

The big recent news in this area, of course, is Dvir’s theorem that that the Kakeya conjecture is true when k is a finite field.

Of course one hopes that Dvir’s argument will give some ideas for an attack on the original problem in R^n.  And that hasn’t happened yet; though the “polynomial method,” as the main idea of Dvir’s theorem is now called, has found lots of applications to other problems in real combinatorial geometry (e.g. Guth and Katz’s proof of the joints conjecture.)

Why not Kakeya?  Well, here’s one clue.  Dvir actually proves more than the Kakeya conjecture!  He proves that a Kakeya set in F_q^n has positive measure.

(Note:  F_q^n is a finite set, so of course any nonempty subset has positive measure; so “positive measure” here is shorthand for “there’s a lower bound for the measure which is bounded away from 0 as q grows with n fixed.”)

What this tells you is that R really is different from F_q with respect to this problem; if Dvir’s proof “worked” over R, it would prove that a Kakeya set in R^n had positive measure, which is false.

So what’s the difference between R and F_q?  In my view, it’s that R has multiple scales, while F_q only has one.  Two elements in F_q are either the same or distinct, but there is nothing else going on metrically, while distinct real lines can be very close together or very far apart.  The interaction between distances at different scales is your constant companion when working on these problems in the real setting; so maybe it’s not so shocking that a one-scale field like F_q is not a perfect model for the phenomena we’re trying to study.

Which leads us to the ring F_q[[t]] — the “non-archimedean local ring” which Dummit and Hablicsek write about.  This ring is somehow “in between” finite fields and real numbers.  On the one hand, it is “profinite,” which is to say it is approximated by a sequence of larger and larger finite rings F_q[[t]]/t^k.  On the other hand, it has infinitely many scales, like R.  From the point of view of Kakeya sets, is it more like a finite field, or more like the real numbers?  In particular, does it have Kakeya sets of measure 0, making it potentially a good model for the real Kakeya problem?

This is the question Richard, Terry, and I asked, and Evan and Marci show that the answer is yes; they construct explicitly a Kakeya set in F_q[[t]]^2 with measure 0.

Now when we asked this question in our paper, I thought maybe you could do this by imitating Besicovitch’s argument in a straightforward way.  I did not succeed in doing this.  Evan and Marci tried too, and they told me that this just plain doesn’t work.  The construction they came up with is (at least as far as I can see) completely different from anything that makes sense over R.  And the way they prove measure 0 is extremely charming; they define a Markov process such for which the complement of their Kakeya set is the set of points that eventually hit 0, and then show by standard methods that their Markov process goes to 0 with probability 1!

Of course you ask:  does their Kakeya set have Minkowski dimension 2?  Yep — and indeed, they prove that any Kakeya set in F_q[[t]]^2 has Minkowski dimension 2, thus proving the Kakeya conjecture in this setting, up to the distinction between Hausdorff and Minkowski dimension.  (Experts should feel free to weigh in an tell me how much we should worry about this distinction.)  Note that dimension 2 is special:  the Kakeya conjecture in R^2 is known as well.  For every n > 2 we’re in the dark, over F_q[[t]] as well as over R.

To sum up:  what Dummit and Hablicsek prove makes me feel like the Kakeya problem over  F_q[[t]] is, at least potentially, a pretty good model for the Kakeya problem over R!  Not that we know how to solve the Kakeya problem over F_q[[t]]…..

Update on 2-dimensional Kakeya sets over finite fields

A few months ago I wrote about the problem of giving a sharp lower bound for the size of a Kakeya subset of F_q^2; that is, a subset containing a line in every direction. Apparently this problem has now been solved: Simeon Ball, in a comment on Terry’s blog, says that Blokhuis and Mazzocca show that a Kakeya set has have cardinality at least q(q+1)/2 + (q-1)/2. Since there are known examples of Kakeya sets of this size arising from conics, this bound is sharp. The argument appears to be completely combinatorial, not algebro-geometric a la Dvir.

I’m a bit confused about attribution; Ball calls it a result of Blokhuis and Mazzocca, but links to a preprint of his own which apparently proves the theorem, and which doesn’t mention Blokhuis and Mazzocca. So who actually proved this nice result? Anyone with first-hand knowledge should enlighten me in comments.

Give the people (who like the Kakeya problem) what they want

Wow — make one comment on Terry’s blog and you get a ton of traffic.

Terry encouraged me in the comments to experiment with posting math. So I’m going to experiment!

The background: Zeev Dvir this week presented a beautiful and simple proof of the Kakeya conjecture over finite fields. A Kakeya set in F_q^n is a subset containing a line 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 paper!)

In the special case n=2, Dvir’s method shows that a Kakeya set has at least 1/2 q(q+1) elements. In fact (as I learned from Terry’s blog) the best known lower bound is

1/2 q(q+1) + (5/14)q + O(1)

due to Cooper.

Question: Can Dvir’s method be refined to give a better lower bound?

(Note that there are examples of 2-dimensional Kakeya sets, due to Mockenhaupt and Tao, of size 1/2 q(q+1) + (1/2) q + O(1), so Cooper’s bound can’t be improved very much!)

One might naturally start out as follows. The main idea of Dvir’s proof is to show that a Kakeya set can’t be contained in an affine plane curve of degree q-1.

What if S is a Kakeya set contained in an affine plane curve of degree q? That is, what if F in F_q[x,y] is a polynomial of degree q vanishing on S? This places rather strong conditions on F. In each direction m we have a line L_m (say y = mx+b) such that F vanishes on L_m(F_q); since deg F = q, this implies that

F(x,mx + b) = L_m G + c (x^q – x)

for m = 0,1, … q-1. (Of course, there is one more direction, the infinite one, which you can deal with separately.)

Let V be the space of degree-q polynomials vanishing on S. One might like to bound the dimension of V above; because the dimension of the space of degree-q polynomials vanishing on S is at least (1/2)(q+1)(q+2) – |S|, so

|S| <= (1/2)(q+1)(q+2) – dim V.

We note that V is contained in the intersection of q spaces V_0, … V_{q-1}, where

V_m = span of multiples of L_m and x^q-x.

(Note that if not for the x^q – x, we would be looking for polynomials which were multiples of q different linear forms, which indeed makes V very small! This is what happens in Dvir’s case, where the degree is q-1.)

So far, I’m actually not sure whether any of this does more than restate the problem. But one might try to make an argument along the following lines: we can think of V+[x^q-x] as a linear system of degree-q curves in P^2. Now the Kakeya condition on S shows that a whole lot of these curves have one of the lines L_0, … , L_{q-1} as an irreducible component; in particular, the locus R of reducible curves in this linear system contains q+1 hyperplanes.Does this give an upper bound on dim V? One might, for example, observe that if R contains q+1 hyperplanes, then a general pencil of curves in V + [x^q -x] has q+1 reducible fibers; there is a substantial literature about reducible fibers in pencils of hypersurfaces — particularly relevant here seem to be theorems of Lorenzini (1993) and Vistoli (1993). (Beware: these theorems are usually stated in characteristic 0!)

Evening update:  I spent a few hours thinking about this and don’t immediately see how to push it through — the hard upper bound on the number of reducible fibers from Lorenzini or Vistoli is q^2 – 1, and it’s not clear to me how you could ensure that some pencil in V + [x^q – x] satisfies the more delicate conditions necessary to get that number down below q.  It may be that cutting down to pencils is the wrong thing to do, and one should instead try to show directly that the reducible locus in V + [x^q – x] doesn’t contain q hyperplanes.