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 F^n that contains a line in every direction.  Then E has cardinality at least c_n |F|^n for some c_n > 0.

The initial argument of Dvir gave c_n = 1/n!.  This was improved to c_n = c^n for some explicit 0 < c < 1 by Saraf and Sudan, and recently to c_n =1/2^n 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 f^*: {\Bbb P}^{n-1}(F) \to {\Bbb R} of a function f: F^n \to {\Bbb R}, defined for all directions \xi \in {\Bbb P}^{n-1}(F) in the projective hyperplane at infinity by the formula

f^*(\xi) = \sup_{\ell // \xi} \sum_{x \in \ell} |f(x)|

where the supremum ranges over all lines \ell in F^n oriented in the direction \xi.  Our first result is the endpoint L^p estimate for this operator, namely

Kakeya maximal function conjecture in finite fields. We have \| f^* \|_{\ell^n({\Bbb P}^{n-1}(F))} \leq C_n |F|^{(n-1)/n} \|f\|_{\ell^n(F^n)} for some constant C_n > 0.

This result implies Dvir’s result, since if f is the indicator function of the set E in Dvir’s result, then f^*(\xi) = |F| for every \xi \in {\Bbb P}^{n-1}(F).  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 \ell^p \to \ell^q 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 W \subset {\Bbb P}^N is an (n-1)-dimensional algebraic variety.  Let d \geq 1 be an integer. Then we have

\| \sup_{\gamma \ni x; \gamma \not \subset W} \sum_{y \in \gamma} f(y) \|_{\ell^n_x(W(F))} \leq C_{n,d,N,W} |F|^{(n-1)/n} \|f\|_{\ell^n({\Bbb P}^N(F))}

for some constant C_{n,d,N,W} > 0, where the supremum is over all irreducible algebraic curves \gamma 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 {\Bbb P}^N(F) which contains, for each x in W, an irreducible algebraic curve of degree d passing through x but not lying in W, has cardinality \gg |F|^n if |W| \gg |F|^{n-1}.  (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 \gamma 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 F^n which contains lines in J different directions.  If |J| \sim |F|^{n-1}, then |E| \gtrsim |F|^n.  (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 F^n which contains lines in J different directions.  Then |E| \gtrsim |J| |F|.

Proof. If |J| \sim |F|^{n-1} then we are done by Proposition 1 already, so suppose that J is much smaller than |F|^{n-1}.  (There are only O(|F|^{n-1}) directions available in F^n.)  Let m be an integer such that Jm \sim |F|^{n-1}.

We use the probabilistic method (and more precisely, the first moment method).  Now let R_1, R_2, \ldots, R_m: F^n \to F^n be m randomly chosen “rotations”, or more precisely invertible linear transformations, and consider the set E' := \bigcup_{i=1}^m R_i(E).  Clearly, |E'| \leq m |E|.  On the other hand, we expect E' to contain lines in about |F|^{n-1} different directions.  Indeed, pick any direction \xi.  Then R_i^{-1}(\xi) has a probability about J/|F|^{n-1} of being one of the J directions of the lines that E contains; this is also the probability that R_i(E) contains a line in the direction \xi.  If we choose each of the R_i independently at random, then basic probability then tells us that for each direction \xi, that E’ will contain a line in the direction \xi with probability about 1 - (1 - J/|F|^{n-1})^m \sim 1.  From linearity of expectation we thus see that the expected number of directions along which E’ contains a line is \sim |F|^{n-1}, so in particular we will have \gtrsim |F|^{n-1} such lines for at least one choice of E’.  Applying Proposition 1 to that choice we obtain m|E| \geq |E'| \gtrsim |F|^n, and so |E| \gtrsim J |F| 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 F^n, and let T: F^n \to F^m be a random linear transformation.  If |E| \lesssim |F|^m, then |T(E)| \sim |E| with high probability.

Proof. Consider the number of “collisions”,

X := | \{ (x,y) \in E: T(x) = T(y) \} |.

On the one hand, each pair (x,y) has a probability of |F|^{-m} of contributing a collision if x and y are distinct, and a probability 1 of contributing a collision if they are equal.  Thus

{\Bbb E} X \sim |E| + |F|^{-m} |E|^2 \sim |E|.

From Markov’s inequality we conclude that X = O(|E|) with high probability.

On the other hand, we can write X := \sum_{z \in T(E)} |T^{-1}(z) \cap E|^2.  Since |E| = \sum_{z \in T(E)} |T^{-1}(z) \cap E|, we conclude from the Cauchy-Schwarz inequality that

|X| \geq |E|^2 / |T(E)|,

and the claim follows. \Box

Remark. While T is “mostly injective” once |E| \lesssim |F|^m (in the sense that |T(E)| \sim |E|), T will not be completely injective with high probability until |E| \lesssim |F|^{m/2}, thanks to the birthday paradox. \diamond

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 F^n of size |E| \sim |F|^n, and let G be another set in F^n such that for every point x in E, there exists a line \ell_x passing through x such that G contains \ell_x \backslash \{x\}.  Then |G| \sim |F|^n.

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 N \geq n.  Let E be a subset of F^N of size |E| \sim |F|^n, and let G be another set in F^N such that for every point x in E, there exists a line \ell_x passing through x such that G contains \ell_x \backslash \{x\}.  Then |G| \gtrsim |F|^n.

Proof. By  Lemma 1, we can find a linear map T: F^N \to F^n such that |T(E)| \sim |F|^n.  Then observe that T(G) obeys the same hypotheses as G, but with E replaced by T(E).  By Proposition 2, |T(G)| \sim |F|^n, and the claim follows. \Box

–

About these ads