Polymath Wiki - User contributions [en]

Kakeya problem

2009-03-21T20:39:03Z

93.173.30.84:

A '''Kakeya set''' in <math>{\mathbb F}_3^r</math> is a subset <math>E\subset{\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>e\in{\mathbb F}_3^n</math> such that <math>e,e+d,e+2d</math> all lie in <math>E</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>.

Since the Cartesian product of two Kakeya sets is another Kakeya set, we also 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 [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, determining 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 derive essentially the same conclusion using the "bush" argument, as follows. Let <math>E\subset{\mathbb F}_3^n</math> be a Kakeya set, considered as a union of <math>N := (3^n-1)/2</math> lines in all different directions. Let <math>\mu</math> be the largest number of lines that are concurrent at a point of <math>E</math>. The number of point-line incidences is at most <math>|E|\mu</math> and at least <math>3N</math>, whence <math>|E|\ge 3N/\mu</math>. On the other hand, by considering only those points on the "bush" of lines emanating from a point with multiplicity <math>\mu</math>, we see that <math>|E|\ge 2\mu+1</math>. Comparing the two last bounds one obtains
<math>|E|\gtrsim\sqrt{6N} \approx 3^{(n+1)/2}</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\subset{\mathbb F}_3^n</math>. Form a bipartite graph <math>G</math> with the partite sets <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> through <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>. Thus,

:<math>k_n \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.

This estimate can be improved using an idea due to Ruzsa (seems to be unpublished). Namely, let <math>E:=A\cup B</math>, where <math>A</math> is the set of all those vectors with <math>r/3+O(\sqrt r)</math> coordinates equal to <math>1</math> and the rest equal to <math>0</math>, and <math>B</math> is the set of all those vectors with <math>2r/3+O(\sqrt r)</math> coordinates equal to <math>2</math> and the rest equal to <math>0</math>. Then <math>E</math>, being of size just about <math>(27/4)^{r/3}</math> (which is not difficult to verify using [[Stirling's formula]]), contains lines in a positive proportion of directions: for, a typical direction <math>d\in {\mathbb F}_3^n</math> can be represented as <math>d=d_1+2d_2</math> with <math>d_1,d_2\in A</math>, and then <math>d_1,d_1+d,d_1+2d\in E</math>. Now 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+o(1))^n \le k_n \le (1.8899+o(1))^n.</math>

Kakeya problem

2009-03-21T20:37:01Z

93.173.30.84:

A '''Kakeya set''' in <math>{\mathbb F}_3^r</math> is a subset <math>A\subset{\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>.

Since the Cartesian product of two Kakeya sets is another Kakeya set, we also 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 [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, determining 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 derive essentially the same conclusion using the "bush" argument, as follows. Let <math>E\subset{\mathbb F}_3^n</math> be a Kakeya set, considered as a union of <math>N := (3^n-1)/2</math> lines in all different directions. Let <math>\mu</math> be the largest number of lines that are concurrent at a point of <math>E</math>. The number of point-line incidences is at most <math>|E|\mu</math> and at least <math>3N</math>, whence <math>|E|\ge 3N/\mu</math>. On the other hand, by considering only those points on the "bush" of lines emanating from a point with multiplicity <math>\mu</math>, we see that <math>|E|\ge 2\mu+1</math>. Comparing the two last bounds one obtains
<math>|E|\gtrsim\sqrt{6N} \approx 3^{(n+1)/2}</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\subset{\mathbb F}_3^n</math>. Form a bipartite graph <math>G</math> with the partite sets <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> through <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>. Thus,

:<math>k_n \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.

This estimate can be improved using an idea due to Ruzsa (seems to be unpublished). Namely, let <math>E:=A\cup B</math>, where <math>A</math> is the set of all those vectors with <math>r/3+O(\sqrt r)</math> coordinates equal to <math>1</math> and the rest equal to <math>0</math>, and <math>B</math> is the set of all those vectors with <math>2r/3+O(\sqrt r)</math> coordinates equal to <math>2</math> and the rest equal to <math>0</math>. Then <math>E</math>, being of size just about <math>(27/4)^{r/3}</math> (which is not difficult to verify using [[Stirling's formula]]), contains lines in a positive proportion of directions: for, a typical direction <math>d\in {\mathbb F}_3^n</math> can be represented as <math>d=d_1+2d_2</math> with <math>d_1,d_2\in A</math>, and then <math>d_1,d_1+d,d_1+2d\in E</math>. Now 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+o(1))^n \le k_n \le (1.8899+o(1))^n.</math>

Kakeya problem

2009-03-21T20:36:29Z

93.173.30.84:

A '''Kakeya set''' in <math>{\mathbb F}_3^r$ is a subset <math>A\subset{\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>.

Since the Cartesian product of two Kakeya sets is another Kakeya set, we also 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 [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, determining 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 derive essentially the same conclusion using the "bush" argument, as follows. Let <math>E\subset{\mathbb F}_3^n</math> be a Kakeya set, considered as a union of <math>N := (3^n-1)/2</math> lines in all different directions. Let <math>\mu</math> be the largest number of lines that are concurrent at a point of <math>E</math>. The number of point-line incidences is at most <math>|E|\mu</math> and at least <math>3N</math>, whence <math>|E|\ge 3N/\mu</math>. On the other hand, by considering only those points on the "bush" of lines emanating from a point with multiplicity <math>\mu</math>, we see that <math>|E|\ge 2\mu+1</math>. Comparing the two last bounds one obtains
<math>|E|\gtrsim\sqrt{6N} \approx 3^{(n+1)/2}</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\subset{\mathbb F}_3^n</math>. Form a bipartite graph <math>G</math> with the partite sets <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> through <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>. Thus,

:<math>k_n \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.

This estimate can be improved using an idea due to Ruzsa (seems to be unpublished). Namely, let <math>E:=A\cup B</math>, where <math>A</math> is the set of all those vectors with <math>r/3+O(\sqrt r)</math> coordinates equal to <math>1</math> and the rest equal to <math>0</math>, and <math>B</math> is the set of all those vectors with <math>2r/3+O(\sqrt r)</math> coordinates equal to <math>2</math> and the rest equal to <math>0</math>. Then <math>E</math>, being of size just about <math>(27/4)^{r/3}</math> (which is not difficult to verify using [[Stirling's formula]]), contains lines in a positive proportion of directions: for, a typical direction <math>d\in {\mathbb F}_3^n</math> can be represented as <math>d=d_1+2d_2</math> with <math>d_1,d_2\in A</math>, and then <math>d_1,d_1+d,d_1+2d\in E</math>. Now 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+o(1))^n \le k_n \le (1.8899+o(1))^n.</math>

Kakeya problem

2009-03-21T20:26:48Z

93.173.30.84:

Define a '''Kakeya set''' to be a subset <math>A\subset{\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 [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\cdot(3^n-1)/2</math>, and hence

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

One can derive essentially the same conclusion using the "bush" argument, as follows. Let <math>E\subset{\mathbb F}_3^n</math> be a Kakeya set, considered as a union of <math>N := (3^n-1)/2</math> lines in all different directions. Let <math>\mu</math> be the largest number of lines that are concurrent at a point of <math>E</math>. The number of point-line incidences is at most <math>|E|\mu</math> and at least <math>3N</math>, whence <math>|E|\ge 3N/\mu</math>. On the other hand, by considering only those points on the "bush" of lines emanating from a point with multiplicity <math>\mu</math>, we see that <math>|E|\ge 2\mu+1</math>. Comparing the two last bounds one obtains
<math>|E|\gtrsim\sqrt{6N} \approx 3^{(n+1)/2}</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\subset{\mathbb F}_3^n</math>. Form a bipartite graph <math>G</math> with the partite sets <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> through <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>. Thus,

:<math>k_n \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.

This estimate can be improved using an idea due to Ruzsa (seems to be unpublished). Namely, let <math>E:=A\cup B</math>, where <math>A</math> is the set of all those vectors with <math>r/3+O(\sqrt r)</math> coordinates equal to <math>1</math> and the rest equal to <math>0</math>, and <math>B</math> is the set of all those vectors with <math>2r/3+O(\sqrt r)</math> coordinates equal to <math>2</math> and the rest equal to <math>0</math>. Then <math>E</math>, being of size just about <math>(27/4)^{r/3}</math> (which is not difficult to verify using [[Stirling's formula]]), contains lines in a positive proportion of directions: for, a typical direction <math>d\in {\mathbb F}_3^n</math> can be represented as <math>d=d_1+2d_2</math> with <math>d_1,d_2\in A</math>, and then <math>d_1,d_1+d,d_1+2d\in E</math>. Now 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+o(1))^n \le k_n \le (1.8899+o(1))^n.</math>

Talk:Kakeya problem

2009-03-19T04:55:51Z

93.173.30.84: Removing all content from page

Kakeya problem

2009-03-18T19:25:21Z

93.173.30.84:

Define a '''Kakeya set''' to be a subset <math>A\subset{\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 [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\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 [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 ==

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.

This estimate can be improved using an idea due to Ruzsa. Namely, let <math>E:=A\cup B</math>, where <math>A</math> is the set of all those vectors with <math>r/3+O(\sqrt r)</math> coordinates equal <math>1</math> to <math>1</math> and the rest equal to <math>0</math>, and <math>B</math> is the set of all those vectors with <math>2r/3+O(\sqrt r)</math> coordinates equal to <math>2</math> and the rest equal to <math>0</math>. Then <math>E</math>, being of size just about <math>(27/4)^{r/3}</math> (which is not difficult to verify using [[Stirling's formula]]) contains lines in positive proportion of directions. Now 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>

Talk:Kakeya problem

2009-03-18T19:13:18Z

93.173.30.84:

I made some editing, mostly of cosmetical nature (and intend to do a bit more).

Terry (or anybody else), could you explain the <math>2\mu+1</math> in the "bush argument"? We have just <math>\mu</math> lines through a point of musltilicity <math>\mu</math>, by the definition of multiplicity! Where the other <math>\mu+1</math> lines come from?
:: Seva

Talk:Kakeya problem

2009-03-18T19:12:32Z

93.173.30.84: New page: I made some editing, mostly of cosmetical nature (and intend to do a bit more). Terry (or anybody else), could you explain the <math>2\mu+1</math> in the "bush argument"? We have just <ma...

Kakeya problem

2009-03-18T19:09:11Z

93.173.30.84:

Define a '''Kakeya set''' to be a subset <math>A\subset{\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 [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\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 [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 ==

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>

Kakeya problem

2009-03-18T19:07:14Z

93.173.30.84:

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 [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\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 [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 ==

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>

Kakeya problem

2009-03-18T18:25:54Z

93.173.30.84:

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

:<math>k_n\gtsim \sqrt{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 |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 [http://front.math.ucdavis.edu/math.CO/9906097 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>

Kakeya problem

2009-03-18T18:21:00Z

93.173.30.84:

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

:<math>k_n\gtsym \sqrt{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 |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 [http://front.math.ucdavis.edu/math.CO/9906097 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>

Kakeya problem

2009-03-18T18:11:26Z

93.173.30.84:

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

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

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 [http://front.math.ucdavis.edu/math.CO/9906097 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>

Kakeya problem

2009-03-18T18:09:47Z

93.173.30.84:

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

:<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 [http://front.math.ucdavis.edu/math.CO/9906097 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>