# Difference between revisions of "Kakeya problem"

Line 17: | Line 17: | ||

From a paper of [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. | From a paper of [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. | ||

− | To each of the <math>(3^n-1)/2</math> directions in <math>{\mathbb F}_3^n</math> there correspond at least three pairs of elements in a Kakeya set, etermining this direction. Therefore, <math>\binom{k_n}2\ge 3(3^n-1)/2<math>, and hence | + | To each of the <math>(3^n-1)/2</math> directions in <math>{\mathbb F}_3^n</math> there correspond at least three pairs of elements in a Kakeya set, etermining this direction. Therefore, <math>\binom{k_n}{2}\ge 3\cdot(3^n-1)/2</math>, and hence |

− | :<math>k_n\ | + | :<math>k_n\gtrsim 3^{(n+1)/2}.</math> |

− | One can get essentially the same conclusion using 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 | + | One can get essentially the same conclusion using 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 <math>|E|</math>. |

− | + | A better bound follows by using the "slices argument". Let <math>A,B,C\subset{\mathbb F}_3^{n-1}</math> be the three slices of a Kakeya set <math>E</math>. Form a graph <math>G</math> between <math>A</math> and <math>B</math> by connecting <math>a</math> and <math>b</math> by an edge if there is a line in <math>E</math> joining <math>a</math> and <math>b</math>. The restricted sumset <math>\{a+b\colon (a,b)\in G\}</math> is contained in the set <math>-C</math>, while the difference set <math>\{a-b\colon (a-b)\in G\}</math> is all of <math>{\mathbb F}_3^{n-1}</math>. Using an estimate from [http://front.math.ucdavis.edu/math.CO/9906097 a paper of Katz-Tao], we conclude that <math>3^{n-1}\le\max(|A|,|B|,|C|)^{11/6}</math>, leading to <math>|E|\ge 3^{6(n-1)/11}</math>. | |

== General upper bounds == | == General upper bounds == | ||

Line 33: | Line 33: | ||

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

− | ''' | + | 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 <math>E</math>. One can use the random rotations trick to get the rest of the directions in <math>E</math> (losing a polynomial factor in <math>n</math>). | |

− | + | Putting all this together, we seem to have | |

− | + | :<math>(3^{6/11} + o(1))^n \le k_n \le ( (27/4)^{1/3} + o(1))^n</math> | |

− | + | ||

− | :<math>(3^{6/11} + o(1))^n \ | + | |

or | or | ||

− | :<math>(1.8207\ldots+o(1))^n \ | + | :<math>(1.8207\ldots+o(1))^n \le k_n \le (1.88988+o(1))^n.</math> |

## Revision as of 12:07, 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,

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

Since the Cartesian product of two Kakeya sets is another Kakeya set, we have

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

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

From a paper of 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.

To each of the [math](3^n-1)/2[/math] directions in [math]{\mathbb F}_3^n[/math] there correspond at least three pairs of elements in a Kakeya set, etermining this direction. Therefore, [math]\binom{k_n}{2}\ge 3\cdot(3^n-1)/2[/math], and hence

- [math]k_n\gtrsim 3^{(n+1)/2}.[/math]

One can get essentially the same conclusion using 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 [math]|E|[/math].

A better bound follows by using the "slices argument". Let [math]A,B,C\subset{\mathbb F}_3^{n-1}[/math] be the three slices of a Kakeya set [math]E[/math]. Form a graph [math]G[/math] between [math]A[/math] and [math]B[/math] by connecting [math]a[/math] and [math]b[/math] by an edge if there is a line in [math]E[/math] joining [math]a[/math] and [math]b[/math]. The restricted sumset [math]\{a+b\colon (a,b)\in G\}[/math] is contained in the set [math]-C[/math], while the difference set [math]\{a-b\colon (a-b)\in G\}[/math] is all of [math]{\mathbb F}_3^{n-1}[/math]. Using an estimate from a paper of Katz-Tao, we conclude that [math]3^{n-1}\le\max(|A|,|B|,|C|)^{11/6}[/math], leading to [math]|E|\ge 3^{6(n-1)/11}[/math].

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

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 [math]E[/math]. One can use the random rotations trick to get the rest of the directions in [math]E[/math] (losing a polynomial factor in [math]n[/math]).

Putting all this together, we seem to have

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

or

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