Difference between revisions of "Kakeya problem"

From Polymath1Wiki
Jump to: navigation, search
(New page: Define a '''Kakeya set''' to be a subset A of <math>[3]^n \equiv ({\Bbb Z}/3{\Bbb Z})^n</math> that contains an algebraic line in every direction. Thus, for every <math>r \in ({\Bbb Z...)
 
Line 19: Line 19:
  
 
can the upper bound be strengthened to <math>k_{r+1}\le 2k_r+1</math>?
 
can the upper bound be strengthened to <math>k_{r+1}\le 2k_r+1</math>?
 +
 +
[http://arxiv.org/abs/0901.2529 Dvir, Kopparty, Saraf, and Sudan] showed that <math>k_r \geq 3^r / 2^r</math>.
 +
 +
The Cartesian product of two Kakeya sets is another Kakeya set; this implies that <math>k_{r+s} \leq k_r k_s</math>.

Revision as of 10:42, 14 March 2009

Define a Kakeya set to be a subset A of [math][3]^n \equiv ({\Bbb Z}/3{\Bbb Z})^n[/math] that contains an algebraic line in every direction. Thus, for every [math]r \in ({\Bbb Z}/3{\Bbb Z})^n[/math], there exists [math]a \in ({\Bbb Z}/3{\Bbb Z})^n[/math] such that a, a+r, a+2r all lie in A. Let [math]k_n[/math] be the smallest size of a Kakeya set in n dimensions.


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

[math]3,7,13,27,53,\ldots[/math]

As to the general estimates, we have

[math]k_r(k_r-1)\ge 3(3^r-1)[/math]

and, on the other hand,

[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

[math]k_r\le k_{r+1}\le 3k_r[/math];

can the upper bound be strengthened to [math]k_{r+1}\le 2k_r+1[/math]?

Dvir, Kopparty, Saraf, and Sudan showed that [math]k_r \geq 3^r / 2^r[/math].

The Cartesian product of two Kakeya sets is another Kakeya set; this implies that [math]k_{r+s} \leq k_r k_s[/math].