Difference between revisions of "Kakeya problem"

From Polymath1Wiki
Jump to: navigation, search
(General upper bounds)
Line 1: Line 1:
 
Define a '''Kakeya set''' to be a subset <math>A</math> of <math>[3]^n\equiv{\mathbb F}_3^n</math> that contains an [[algebraic line]] in every direction; that is, for every <math>d\in{\mathbb F}_3^n</math>, there exists <math>a\in{\mathbb F}_3^n</math> such that <math>a,a+d,a+2d</math> all lie in <math>A</math>.  Let <math>k_n</math> be the smallest size of a Kakeya set in <math>{\mathbb F}_3^n</math>.
 
Define a '''Kakeya set''' to be a subset <math>A</math> of <math>[3]^n\equiv{\mathbb F}_3^n</math> that contains an [[algebraic line]] in every direction; that is, for every <math>d\in{\mathbb F}_3^n</math>, there exists <math>a\in{\mathbb F}_3^n</math> such that <math>a,a+d,a+2d</math> all lie in <math>A</math>.  Let <math>k_n</math> be the smallest size of a Kakeya set in <math>{\mathbb F}_3^n</math>.
  
Clearly, we have <math>k_1=3</math>, and it is easy to see that <math>k_2=7</math>. Using a computer, I also found <math>k_3=13</math> and <math>k_4\le 27</math>. I suspect that, indeed, <math>k_4=27</math> holds (meaning that in <math>{\mathbb F}_3^4</math> one cannot get away with just <math>26</math> elements), and I am very curious to know whether <math>k_5=53</math>: notice the pattern in
+
Clearly, we have <math>k_1=3</math>, and it is easy to see that <math>k_2=7</math>. Using a computer, it is not difficult to find that <math>k_3=13</math> and <math>k_4\le 27</math>. Indeed, it seems likely that <math>k_4=27</math> holds, meaning that in <math>{\mathbb F}_3^4</math> one cannot get away with just <math>26</math> elements.
  
:<math>3,7,13,27,53,\ldots</math>
+
== General lower bounds ==
  
we have the trivial inequalities
+
Trivially, we have
  
:<math>k_n\le k_{n+1}\le 3k_n</math>
+
:<math>k_n\le k_{n+1}\le 3k_n</math>.
  
The Cartesian product of two Kakeya sets is another Kakeya set; this implies that <math>k_{n+m} \leq k_m k_n</math>.  This implies that <math>k_n^{1/n}</math> converges to a limit as n goes to infinity.
+
Next, the Cartesian product of two Kakeya sets is another Kakeya set; hence,
  
== General lower bounds ==
+
:<math>k_{n+m} \leq k_m k_n</math>,
 +
 
 +
implying that <math>k_n^{1/n}</math> converges to a limit as <math>n</math> goes to infinity.
  
[http://arxiv.org/abs/0901.2529 Dvir, Kopparty, Saraf, and Sudan] showed that <math>k_n \geq 3^n / 2^n</math>.
+
From [http://arxiv.org/abs/0901.2529 Dvir, Kopparty, Saraf, and Sudan] it follows that <math>k_n \geq 3^n / 2^n</math>, but this is superseded by the estimates given below.
  
 
We have
 
We have

Revision as of 11:09, 18 March 2009

Define a Kakeya set to be a subset [math]A[/math] of [math][3]^n\equiv{\mathbb F}_3^n[/math] that contains an algebraic line in every direction; that is, for every [math]d\in{\mathbb F}_3^n[/math], there exists [math]a\in{\mathbb F}_3^n[/math] such that [math]a,a+d,a+2d[/math] all lie in [math]A[/math]. Let [math]k_n[/math] be the smallest size of a Kakeya set in [math]{\mathbb F}_3^n[/math].

Clearly, we have [math]k_1=3[/math], and it is easy to see that [math]k_2=7[/math]. Using a computer, it is not difficult to find that [math]k_3=13[/math] and [math]k_4\le 27[/math]. Indeed, it seems likely that [math]k_4=27[/math] holds, meaning that in [math]{\mathbb F}_3^4[/math] one cannot get away with just [math]26[/math] elements.

General lower bounds

Trivially, we have

[math]k_n\le k_{n+1}\le 3k_n[/math].

Next, the Cartesian product of two Kakeya sets is another Kakeya set; hence,

[math]k_{n+m} \leq k_m k_n[/math],

implying that [math]k_n^{1/n}[/math] converges to a limit as [math]n[/math] goes to infinity.

From Dvir, Kopparty, Saraf, and Sudan it follows that [math]k_n \geq 3^n / 2^n[/math], but this is superseded by the estimates given below.

We have

[math]k_n(k_n-1)\ge 3(3^n-1)[/math]

since for each [math]d\in {\mathbb F}_3^r\setminus\{0\}[/math] there are at least three ordered pairs of elements of a Kakeya set with difference [math]d[/math]. (I actually can improve the lower bound to something like [math]k_r\gg 3^{0.51r}[/math].)

For instance, we can use the "bush" argument. There are [math]N := (3^n-1)/2[/math] different directions. Take a line in every direction, let E be the union of these lines, and let [math]\mu[/math] be the maximum multiplicity of these lines (i.e. the largest number of lines that are concurrent at a point). On the one hand, from double counting we see that E has cardinality at least [math]3N/\mu[/math]. On the other hand, by considering the "bush" of lines emanating from a point with multiplicity [math]\mu[/math], we see that E has cardinality at least [math]2\mu+1[/math]. If we minimise [math]\max(3N/\mu, 2\mu+1)[/math] over all possible values of [math]\mu[/math] one obtains approximately [math]\sqrt{6N} \approx 3^{(n+1)/2}[/math] as a lower bound of |E|, which is asymptotically better than [math](3/2)^n[/math].

Or, we can use the "slices" argument. Let [math]A, B, C \subset ({\Bbb Z}/3{\Bbb Z})^{n-1}[/math] be the three slices of a Kakeya set E. We can form a graph G between A and B by connecting A and B by an edge if there is a line in E joining A and B. The restricted sumset [math]\{a+b: (a,b) \in G \}[/math] is essentially C, while the difference set [math]\{a-b: (a-b) \in G \}[/math] is all of [math]({\Bbb Z}/3{\Bbb Z})^{n-1}[/math]. Using an estimate from this paper of Katz-Tao, we conclude that [math]3^{n-1} \leq \max(|A|,|B|,|C|)^{11/6}[/math], leading to the bound [math]|E| \geq 3^{6(n-1)/11}[/math], which is asymptotically better still.

General upper bounds

We have

[math]k_n\le 2^{n+1}-1[/math]

since the set of all vectors in [math]{\mathbb F}_3^n[/math] such that at least one of the numbers [math]1[/math] and [math]2[/math] is missing among their coordinates is a Kakeya set.

Question: can the upper bound be strengthened to [math]k_{n+1}\le 2k_n+1[/math]?

Another construction uses the "slices" idea and a construction of Imre Ruzsa. Let [math]A, B \subset [3]^n[/math] be the set of strings with [math]n/3+O(\sqrt{n})[/math] 1's, [math]2n/3+O(\sqrt{n})[/math] 0's, and no 2's; let [math]C \subset [3]^n[/math] be the set of strings with [math]2n/3+O(\sqrt{n})[/math] 2's, [math]n/3+O(\sqrt{n})[/math] 0's, and no 1's, and let [math]E = \{0\} \times A \cup \{1\} \times B \cup \{2\} \times C[/math]. From Stirling's formula we have [math]|E| = (27/4 + o(1))^{n/3}[/math]. Now I claim that for most [math]t \in [3]^{n-1}[/math], there exists an algebraic line in the direction (1,t). Indeed, typically t will have [math]n/3+O(\sqrt{n})[/math] 0s, [math]n/3+O(\sqrt{n})[/math] 1s, and [math]n/3+O(\sqrt{n})[/math] 2s, thus [math]t = e + 2f[/math] where e and f are strings with [math]n/3 + O(\sqrt{n})[/math] 1s and no 2s, with the 1-sets of e and f being disjoint. One then checks that the line [math](0,f), (1,e), (2,2e+2f)[/math] lies in E.

This is already a positive fraction of directions in E. One can use the random rotations trick to get the rest of the directions in E (losing a polynomial factor in n).

Putting all this together, I think we have

[math](3^{6/11} + o(1))^n \leq k_n \leq ( (27/4)^{1/3} + o(1))^n[/math]

or

[math](1.8207\ldots+o(1))^n \leq k_n \leq (1.88988+o(1))^n[/math]