Kakeya problem - Revision history

132.74.1.4 at 07:35, 5 June 2009

2009-06-05T07:35:31Z

← Older revision		Revision as of 00:35, 5 June 2009
Line 16:		Line 16:

	== Lower Bounds ==		== Lower Bounds ==

	From a paper of [http://arxiv.org/abs/0901.2529 Dvir, Kopparty, Saraf, and Sudan] it follows that <math>k_n\ge (9/5)^n</math> (and for general fields of cardinality q, a lower bound of <math>(q/(2-1/q))^n</math>), but this is superseded by the second estimate 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		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
Line 26:		Line 24:
	<math>\|E\|\gtrsim\sqrt{6N} \approx 3^{(n+1)/2}</math>.		<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,		The better estimate

			:<math>k_n\ge (9/5)^n</math>

			is obtained in [http://arxiv.org/abs/0901.2529 a paper of Dvir, Kopparty, Saraf, and Sudan]. (In general, they show that a Kakeya set in the <math>n</math>-dimensional vector space over the <math>q</math>-element field has at least <math>(q/(2-1/q))^n</math> elements).

			A still 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>		:<math>k_n \ge 3^{6(n-1)/11}.</math>

18.251.7.184 at 03:56, 16 May 2009

2009-05-16T03:56:23Z

← Older revision		Revision as of 20:56, 15 May 2009
Line 17:		Line 17:
	== Lower Bounds ==		== Lower Bounds ==

	From a paper of [http://arxiv.org/abs/0901.2529 Dvir, Kopparty, Saraf, and Sudan] it follows that <math>k_n\ge (3/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\ge (9/5)^n</math> (and for general fields of cardinality q, a lower bound of <math>(q/(2-1/q))^n</math>), but this is superseded by the second estimate 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		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

132.74.1.4 at 09:07, 9 April 2009

2009-04-09T09:07:32Z

← Older revision		Revision as of 02:07, 9 April 2009
Line 3:		Line 3:
	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.		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.

	== ~~Some~~ Basic Estimates ==		== Basic Estimates ==

	Trivially, we have		Trivially, we have
Line 9:		Line 9:
	:<math>k_n\le k_{n+1}\le 3k_n</math>.		:<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~~		Since the Cartesian product of two Kakeya sets is another Kakeya set, the upper bound can be extended to

	:<math>k_{n+m} \leq k_m k_n</math>;		:<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.		this implies that <math>k_n^{1/n}</math> converges to a limit as <math>n</math> goes to infinity.

	== Lower Bounds ==		== Lower Bounds ==

	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\ge (3/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		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>		:<math>k_n\ge 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		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

217.132.31.115 at 16:57, 1 April 2009

2009-04-01T16:57:25Z

← Older revision		Revision as of 09:57, 1 April 2009
Line 1:		Line 1:
	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>.		A '''Kakeya set''' in <math>{\mathbb F}_3^n</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.		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.

	== Basic Estimates ==		== Some Basic Estimates ==

	Trivially, we have		Trivially, we have
Line 15:		Line 15:
	this implies that <math>k_n^{1/n}</math> converges to a limit as <math>n</math> goes to infinity.		this implies that <math>k_n^{1/n}</math> converges to a limit as <math>n</math> goes to infinity.

	== Lower ~~bounds~~ ==		== Lower Bounds ==

	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.
Line 30:		Line 30:
	:<math>k_n \ge 3^{6(n-1)/11}.</math>		:<math>k_n \ge 3^{6(n-1)/11}.</math>

	== Upper ~~bounds~~ ==		== Upper Bounds ==

	We have		We have

132.74.1.4 at 08:30, 31 March 2009

2009-03-31T08:30:40Z

← Older revision		Revision as of 01:30, 31 March 2009
Line 3:		Line 3:
	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.		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~~ ==		== Basic Estimates ==

	Trivially, we have		Trivially, we have
Line 14:		Line 14:

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

			== Lower bounds ==

	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.
Line 28:		Line 30:
	:<math>k_n \ge 3^{6(n-1)/11}.</math>		:<math>k_n \ge 3^{6(n-1)/11}.</math>

	== ~~General upper~~ bounds ==		== Upper bounds ==

	We have		We have

93.173.30.84 at 20:39, 21 March 2009

2009-03-21T20:39:03Z

← Older revision		Revision as of 13:39, 21 March 2009
Line 1:		Line 1:
	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>.		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.		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.

93.173.30.84 at 20:37, 21 March 2009

2009-03-21T20:37:01Z

← Older revision		Revision as of 13:37, 21 March 2009
Line 1:		Line 1:
	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>.		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.		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.

93.173.30.84 at 20:36, 21 March 2009

2009-03-21T20:36:29Z

← Older revision		Revision as of 13:36, 21 March 2009
Line 1:		Line 1:
	~~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>.		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.		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.
Line 5:		Line 5:
	== General lower bounds ==		== General lower bounds ==

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

	Since the Cartesian product of two Kakeya sets is another Kakeya set, we have		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>;		:<math>k_{n+m} \leq k_m k_n</math>;
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\cdot(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, 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>		:<math>k_n\gtrsim 3^{(n+1)/2}.</math>

93.173.30.84 at 20:26, 21 March 2009

2009-03-21T20:26:48Z

← Older revision		Revision as of 13:26, 21 March 2009
Line 24:		Line 24:
	<math>\|E\|\gtrsim\sqrt{6N} \approx 3^{(n+1)/2}</math>.		<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,		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>		:<math>k_n \ge 3^{6(n-1)/11}.</math>
Line 36:		Line 36:
	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.

	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 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>).		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		Putting all this together, we seem to have
Line 44:		Line 44:
	or		or

	:<math>(1.8207~~\ldots~~+o(1))^n \le k_n \le (1.~~88988~~+o(1))^n.</math>		:<math>(1.8207+o(1))^n \le k_n \le (1.8899+o(1))^n.</math>

132.74.1.4 at 11:53, 19 March 2009

2009-03-19T11:53:51Z

← Older revision		Revision as of 04:53, 19 March 2009
Line 36:		Line 36:
	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.

	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 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. 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>).		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 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		Putting all this together, we seem to have