Kakeya problem: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
Define a '''Kakeya set''' to be a subset A of <math>[3]^ | Define a '''Kakeya set''' to be a subset <math>A</math> of <math>[3]^r\equiv{\mathbb F}_3^r</math> that contains an [[algebraic line]] in every direction; that is, for every <math>d\in{\mathbb F}_3^r</math>, there exists <math>a\in{\mathbb F}_3^r</math> such that <math>a,a+d,a+2d</math> all lie in <math>A</math>. Let <math>k_r</math> be the smallest size of a Kakeya set in <math>{\mathbb F}_3^r</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 26 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, 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 | ||
:<math>3,7,13,27,53,\ldots</math> | :<math>3,7,13,27,53,\ldots</math> | ||
| Line 14: | Line 14: | ||
:<math>k_r\le 2^{r+1}-1</math>: | :<math>k_r\le 2^{r+1}-1</math>: | ||
the former 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 d, the latter due to the fact that the set of all vectors in <math>{\mathbb F}_3^r</math> such that at least one of the numbers 1 and 2 is missing among their coordinates is a Kakeya set. (I actually can improve the lower bound to something like <math>k_r\gg 3^{0.51r}</math>.) Also, we have the trivial inequalities | the former 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>, the latter due to the fact that the set of all vectors in <math>{\mathbb F}_3^r</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. (I actually can improve the lower bound to something like <math>k_r\gg 3^{0.51r}</math>.) Also, we have the trivial inequalities | ||
:<math>k_r\le k_{r+1}\le 3k_r</math>; | :<math>k_r\le k_{r+1}\le 3k_r</math>; | ||
Revision as of 12:45, 14 March 2009
Define a Kakeya set to be a subset [math]\displaystyle{ A }[/math] of [math]\displaystyle{ [3]^r\equiv{\mathbb F}_3^r }[/math] that contains an algebraic line in every direction; that is, for every [math]\displaystyle{ d\in{\mathbb F}_3^r }[/math], there exists [math]\displaystyle{ a\in{\mathbb F}_3^r }[/math] such that [math]\displaystyle{ a,a+d,a+2d }[/math] all lie in [math]\displaystyle{ A }[/math]. Let [math]\displaystyle{ k_r }[/math] be the smallest size of a Kakeya set in [math]\displaystyle{ {\mathbb F}_3^r }[/math].
Clearly, we have [math]\displaystyle{ k_1=3 }[/math], and it is easy to see that [math]\displaystyle{ k_2=7 }[/math]. Using a computer, I also found [math]\displaystyle{ k_3=13 }[/math] and [math]\displaystyle{ k_4\le 27 }[/math]. I suspect that, indeed, [math]\displaystyle{ k_4=27 }[/math] holds (meaning that in [math]\displaystyle{ {\mathbb F}_3^4 }[/math] one cannot get away with just [math]\displaystyle{ 26 }[/math] elements), and I am very curious to know whether [math]\displaystyle{ k_5=53 }[/math]: notice the pattern in
- [math]\displaystyle{ 3,7,13,27,53,\ldots }[/math]
As to the general estimates, we have
- [math]\displaystyle{ k_r(k_r-1)\ge 3(3^r-1) }[/math]
and, on the other hand,
- [math]\displaystyle{ k_r\le 2^{r+1}-1 }[/math]:
the former since for each [math]\displaystyle{ 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]\displaystyle{ d }[/math], the latter due to the fact that the set of all vectors in [math]\displaystyle{ {\mathbb F}_3^r }[/math] such that at least one of the numbers [math]\displaystyle{ 1 }[/math] and [math]\displaystyle{ 2 }[/math] is missing among their coordinates is a Kakeya set. (I actually can improve the lower bound to something like [math]\displaystyle{ k_r\gg 3^{0.51r} }[/math].) Also, we have the trivial inequalities
- [math]\displaystyle{ k_r\le k_{r+1}\le 3k_r }[/math];
can the upper bound be strengthened to [math]\displaystyle{ k_{r+1}\le 2k_r+1 }[/math]?
Dvir, Kopparty, Saraf, and Sudan showed that [math]\displaystyle{ k_r \geq 3^r / 2^r }[/math].
The Cartesian product of two Kakeya sets is another Kakeya set; this implies that [math]\displaystyle{ k_{r+s} \leq k_r k_s }[/math].
