## 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.

## 12 thoughts on “Give the people (who like the Kakeya problem) what they want”

1. […] [Update, Mar 25: See also these posts by Izabella Laba and Jordan Ellenberg.] […]

2. Terence Tao says:

Nice post!

Just for reference, I thought I should detail the example of Gerd Mockenhaupt and I. Suppose |F|=q is odd, and consider the set $E := \{ (x, y) \in F^2: x+y^2 \hbox{ is a square} \}$. Because there are exactly (q+1)/2 squares in F, this set has cardinality q(q+1)/2. On the other hand, for any non-horizontal direction (v,1), E contains the line $\{ (yv + v^2/4, y): y \in F \}$, thanks to the high-school trick of completing the square. So this is almost a Kakeya set already, but one has to add a horizontal line somewhere, which costs an additional (q-1)/2 = q/2 + O(1) points.

The original set E is cut out by the polynomial $(x+y^2)^{(q-1)/2} - 1$. Once one adds a horizontal line, say the line y=0, presumably the lowest degree polynomial that still vanishes on E is $y( (x+y^2)^{(q-1)/2} - 1 )$. Perhaps these polynomials would be a good test case for your above analysis?

3. Terence Tao says:

p.s. also, as far as I know, I don’t know any non-trivial upper bound for the size of a Kakeya set in characteristic 2; for all I know, such sets could actually have size $q^2 - O(q)$. It could be that a Dvir-type analysis would be helpful here…

4. JSE says:

I think your polynomial doesn’t vanish when x+y^2 = 0, right? So maybe multiply by x+y^2 and get a polynomial of degree q+2 vanishing on your set E. In fact, a very reducible one; it’s the product of a line and (q+1)/2 conics.

But yes — what’s interesting is that just by dimension count there should be a (1/2)q + O(1) dimensional family of degree-q polynomials vanishing on your E, and it’s not clear to me what’s special about them.

5. Terence Tao says:

Oops, you’re right, of course.

The Kakeya set $E' := E \cup \{ y=0 \}$ is invariant under the parabolic scaling $(x,y) \mapsto (t^2 x, t y)$, so there is a nice action of $F^\times$ on the degree $\leq q$ polynomials that vanish on E’. Now that there is a group action, it significantly raises the odds that these polynomials are “special”. (There is also a reflection symmetry $(x,y) \mapsto (x,-y)$ which should presumably be useful in working out exactly what these polynomials are.)

Can one say anything about a degree q polynomial P(x,y) that vanishes on a conic such as $x+y^2=0$? By the Euclidean algorithm, I of course have $P(x,y) = Q(x,y) (x+y^2) + a(x) y + b(x)$ for some polynomials Q, a, b of degree at most q-2, q-1, q respectively. The symmetry $y \mapsto -y$ then tells me that a(x) and b(x) vanish whenever x is non-zero, and b(0) also vanishes, so it looks like $a(x) = c (x^{q-1} - 1)$ and $b(x) = d (x^q - x)$ for some constants c, d.

So, more generally, a polynomial P of degree at most d that vanishes on E’ must have the factorisations

$P(x,y) = Q_t(x,y) (x+y^2-t^2) + c_t ((x-t^2)^{q-1} - 1) + d_t (x^q - x)$

for every t, as well as another factorisation

$P(x,y) = y Q(x,y) + e (x^q - x)$.

Not sure what the next step should be, though… (finding a good Groebner basis, perhaps?)

6. Terence Tao says:

Hmm. For what it’s worth, the polynomial $(x+y^2)^{(q+1)/2} - (x+y^{q+1})$ vanishes on E and has degree q; with respect to the scaling $(x, y) \to (\lambda^2 x, \lambda y)$, it’s basically homogeneous of degree 2. From linear algebra I know that there is one such polynomial like this for each homogeneity, but they seem to look kind of ugly. The polynomials that vanish on E’ are some subspace of this, but they don’t seem to be very pretty either; I can’t write down a short formula for any of them.

7. Xander Faber says:

I had no idea until this morning that so many people had gotten so excited about Dvir’s proof of the finite Kakeya conjecture! For the last several days I’ve been toying with exactly the idea you’ve described here on bounding the size of a finite Kakeya set in dimension 2 (i.e., by bounding the kernel of the polynomial evaluation map on points of Kakeya sets).

Personally, I think it’s a useful reformulation of the problem of finding a sharp lower bound for 2-dimensional Kakeya sets. If nothing else, it gives a much clearer means of quantifying the obstruction to being a small Kakeya set.

I don’t quite understand Terence’s comment on a non-trivial upper bound for Kakeya sets in characteristic 2, though. Taking $(q + 1)$ lines in distinct directions through a single point gives a Kakeya set of size $q^2$. The Tao/Mockenhaupt example gives a Kakeya set of exactly the minimum size $(q^2 + q) / 2$ when $q$ is even. So the characteristic 2 case is completely done in dimension 2. Unfortunately, the picture isn’t so simple in higher dimensions. Even for q=2 and dimension 3, the smallest Kakeya set has size 5, while Dvir’s proof gives a lower bound of size 4.

8. JSE says:

The Mockenhaupt-Tao example is only in odd characteristic — it relies on completing the square, which doesn’t work so well in characteristic 2!

9. Xander Faber says:

Ahhh … thanks for the clarification. That makes more sense now.

Here is an extension of the MT example to even characteristic that I discovered a few years ago. Define a Kakeya set in $F_q$ given by the union of the vertical line $\{x=0\}$ and the lines $\{y = ix - i^2 \}$ as $i$ ranges over all elements of $F_q$. The non-vertical lines have the property that no three of them meet in a common point. So they contribute $(q^2 + q)/2$ to the size of the set. The non-vertical lines meet the vertical line at the points $(0,0)$ and $(0, -i^2)$, so the vertical line contributes $q$ minus the number of squares in $F_q$.

In characteristic 2 every element is a square, and so the vertical line contributes nothing new; i.e., the size of this Kakeya set is $(q^2 + q)/2$. For odd characteristic, there are $(q+1)/2$ square elements, and so this Kakeya set has size $(q^2 + q)/2 + (q-1)/2$.

This appears to give the smallest 2-dimensional Kakeya set in odd characteristic, although it’s only been verified in special cases so far. Experimentally, it’s true for all odd $q \leq 13$.

10. JSE says:

Xander — this is a nice example!

Let me frame it another way: you are looking at the set of (x,y) such that there exists i in F_q with

i^2 + ix + y = 0

Now forgetting about x=0 and substituting j = i/x I get

j^2 + j + (y/x^2) = 0

So this should have a solution exactly when y/x^2 lies in the image of (Frob+1). But Frob+1 is a linear map whose kernel consists only of F_2, so its image is of size q/2; in other words, the Kakeya set has size on order of q^2/2.

11. Xander Faber says:

Thanks! Dotting the i’s and lower case j’s in your approach gives exactly (q^2 + q) / 2, just as one would hope. The real difficulty seems to be in improving the lower bound for q odd. A few years ago I managed to prove

$|K| \geq \frac{q^2 + q}{2} + \frac{q}{3}$

Josh Cooper (who currently holds the record) squeezed a little bit more out of my method with some really clever combinatorics to get

$|K| \geq \frac{q^2 + q}{2} + \frac{q}{3} + \frac{q}{42} - \frac{1}{14}$.

Given Dvir’s proof of the order of magnitude of a general Kakeya set, I can’t help but feel that there’s an elementary proof of the correct lower bound lurking here somewhere. But what is it? Besides the fact that only half of the elements in F_q are squares when q is odd, what else is different from characteristic 2?

12. […] on 2-dimensional Kakeya sets over finite fields 05Jun08 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 […]