Polymath Wiki - User contributions [en]

Kakeya problem

2009-06-05T07:35:31Z

132.74.1.4:

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.

== Basic Estimates ==

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, the upper bound can be extended to

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

== Lower Bounds ==

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\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
<math>|E|\gtrsim\sqrt{6N} \approx 3^{(n+1)/2}</math>.

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>

== 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-04-09T09:07:32Z

132.74.1.4:

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.

== Basic Estimates ==

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, the upper bound can be extended to

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

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

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

== 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-31T08:30:40Z

132.74.1.4:

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.

== Basic Estimates ==

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.

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

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>

== 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-19T11:53:51Z

132.74.1.4:

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. 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\ldots+o(1))^n \le k_n \le (1.88988+o(1))^n.</math>

Kakeya problem

2009-03-19T11:46:05Z

132.74.1.4:

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

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-19T08:44:35Z

132.74.1.4:

Anybody has a reference to Ruzsa ("General upper bounds" section)?

Kakeya problem

2009-03-19T08:39:38Z

132.74.1.4:

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>. Minimizing <math>\max\{3N/\mu, 2\mu+1\}</math> over all possible values of <math>\mu</math> 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. 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 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>

Kakeya problem

2009-03-19T08:37:27Z

132.74.1.4:

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>. Minimizing <math>\max\{3N/\mu, 2\mu+1\}</math> over all possible values of <math>\mu</math> 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. 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>

Kakeya problem

2009-03-19T08:26:53Z

132.74.1.4:

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

Kakeya problem

2009-03-19T08:23:22Z

132.74.1.4:

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\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> 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>. Thus,

:<math>k_n \ge \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:Fourier-analytic proof of Sperner

2009-02-28T12:34:22Z

132.74.1.4:

In (5), isn't the coefficient 4 in front of the sum missing?

:Er, yeah. Well caught :-) [[User:Teorth|Terry]] 19:51, 26 February 2009 (UTC)

:: I am afraid now the coefficient 16 is missing! ;-)
:: Also, with the illiterates like myself in mind, could you drop several words of motivation for (3) and (6)? Thanks!
:: One more thing. The conclusion of Lemma 1 involves expectation, but there is nothing random in the assumptions! What does the lemma actually say?

Talk:Fourier-analytic proof of Sperner

2009-02-28T12:26:53Z

132.74.1.4:

Talk:Fourier-analytic proof of Sperner

2009-02-26T14:34:58Z

132.74.1.4: New page: In (5), isn't the coefficient 4 in front of the sum missing?

In (5), isn't the coefficient 4 in front of the sum missing?

Sperner's theorem

2009-02-24T13:34:30Z

132.74.1.4:

==Statement of the theorem==

Sperner's theorem as originally stated is a result about set systems. Suppose that you want to find the largest collection of sets <math>\mathcal{A}</math> such that no set in <math>\mathcal{A}</math> is a proper subset of any other. Then the best you can do is choose all the sets of some fixed size---and of course the best size to pick is <math>\lfloor n/2\rfloor</math>, since the binomial coefficient <math>\binom nm</math> is maximized when <math>m=\lfloor n/2\rfloor.</math>

Sperner's theorem is closely related to the density Hales-Jewett theorem: in fact, it is nothing other than DHJ(2) with the best possible bound. To see this, we associate each set <math>A\subset[n]</math> with its characteristic function (that is, the sequence that is 0 outside A and 1 in A). If we have a pair of sets <math>A\subset B,</math> then the two sequences form a [[combinatorial line]] in <math>[2]^n.</math> For example, if n=6 and A and B are the sets <math>\{2,3\}</math> and <math>\{2,3,4,6\}</math>, then we get the combinatorial line that consists of the two points 011000 and 011101, which we can denote by 011*0* (so the wildcard set is <math>\{4,6\}</math>).

==Proof of the theorem==

There are several proofs, but perhaps the most enlightening is a very simple averaging argument that proves a stronger result. Let <math>\mathcal{A}</math> be a collection of subsets of [n]. For each k, let <math>\delta_k</math> denote the density of <math>\mathcal{A}</math> in the kth [[slice|layer]] of the cube: that is, it is the number of sets in <math>\mathcal{A}</math> of size k, divided by <math>\binom nk.</math> The [[equal-slices measure]] of <math>\mathcal{A}</math> is defined to be <math>\delta_0+\dots+\delta_n.</math>

Now the equal-slices measure of <math>\mathcal{A}</math> is easily seen to be equal to the following quantity. Let <math>\pi</math> be a random permutation of [n], let <math>U_0,U_1,U_2\dots,U_n</math> be the sets <math>\emptyset, \{\pi(1)\},\{\pi(1),\pi(2)\},\dots,[n],</math> and let <math>\mu(\mathcal{A})</math> be the expected number of the sets <math>U_i</math> that belong to <math>\mathcal{A}.</math> This is the same by linearity of expectation and the fact that the probability that <math>U_k</math> belongs to <math>\mathcal{A}</math> is <math>\delta_k.</math>

Therefore, if the equal-slices measure of <math>\mathcal{A}</math> is greater than 1, then the expected number of sets <math>U_k</math> in <math>\mathcal{A}</math> is greater than 1, so there must exist a permutation for which it is at least 2, and that gives us a pair of sets with one contained in the other.

To see that this implies Sperner's theorem, one just has to make the simple observation that a set with equal-slices measure at most 1 must have cardinality at most <math>\binom n{\lfloor n/2\rfloor}.</math> (If n is odd, so that there are two middle layers, then it is not quite so obvious that to have an extremal set you must pick one or other of the layers, but this is the case.) This stronger version of the statement is called the <em>LYM inequality</em>

==Multidimensional versions==

===Basic version===

Sperner's theorem allows us to find a combinatorial line in any dense subset of <math>[2]^n.</math> What if we want to find a higher-dimensional subspace? Here we briefly sketch a proof that this can be done. We make no attempt to optimize any bounds.

The proof uses the argument for the one-dimensional version together with one extra ingredient, which is the following lemma.

'''Lemma.''' Let X be a set of size N and let <math>A_1,\dots,A_m</math> be subsets of X of average size <math>\delta N.</math> Then the average size of the intersections <math>A_i\cap A_j</math> with <math>i\ne j</math> is at least <math>(\delta^2-\delta/m)N.</math>

'''Proof.''' For each <math>x\in X</math> let f(x) be defined to be the number of i such that <math>x\in A_i.</math> Then the average of f(x) is <math>\delta m,</math> so the average of <math>f(x)^2</math> is at least <math>\delta^2m^2.</math> But the sum over all <math>f(x)^2</math> is the sum over all i and j of <math>|A_i\cap A_j|.</math> If we define <math>g(A_i,A_j)</math> to be <math>|A_i\cap A_j|</math> when <math>i\ne j</math> and 0 when <math>i=j,</math> then we find that the sum of all <math>g(A_i,A_j)</math> is at least <math>\delta^2m^2N-\delta mN.</math> Therefore the average of <math>g(A_i,A_j),</math> and hence the average over all <math>i\ne j,</math> is at least <math>(\delta^2-\delta/m)N,</math> as stated.

Now let us suppose that <math>\mathcal{A}</math> is a subset of <math>[2]^n</math> of density <math>\delta.</math> Let n=p+q (where p and q are to be chosen at the stage where one actually tries to optimize what this argument gives) and think of <math>[2]^n</math> as <math>[2]^p\times[2]^q.</math> For each <math>y\in[2]^p</math> let <math>\mathcal{A}_y</math> be the set of <math>z\in[2]^q</math> such that <math>(y,z)\in\mathcal{A}.</math> Then the density of y such that <math>\mathcal{A}_y</math> has density at least <math>\delta/2</math> is at least <math>\delta/2.</math> From this it is easy to derive that for a random permutation <math>\pi</math> of [p], there are at least <math>8/\delta</math> sequences x corresponding to the initial segments of <math>\pi</math> such that the density of <math>\mathcal{A}_x</math> is at least <math>\delta/2.</math> But that, by the lemma, implies that there are two such sequences, x and x', say, such that <math>\mathcal{A}_x\cap\mathcal{A}_{x'}</math> has density at least <math>\delta^2/8.</math> Now we fix such a pair x and x' and use induction to say that <math>\mathcal{A}_x\cap\mathcal{A}_{x'}</math> contains a (k-1)-dimensional combinatorial subspace, which implies that <math>\mathcal{A}</math> contains a k-dimensional combinatorial subspace.

===Strong version===

An alternative argument deduces the multidimensional Sperner theorem from the density Hales-Jewett theorem. We can think of <math>[2]^n</math> as <math>[2^k]^{n/k}.</math> If we do so and apply DHJ(2^k) and translate back to <math>[2]^n,</math> then we find that we have produced a k-dimensional combinatorial subspace. This is obviously a much more sophisticated proof, since DHJ(2^k) is a very hard result, but it gives more information, since the wildcard sets turn out to have the same size. A sign that this strong version is genuinely strong is that it implies Szemerédi's theorem. For instance, suppose you take as your set <math>\mathcal{A}</math> the set of all sequences such that the number of 0s plus the number of 1s in even places plus twice the number of 1s in odd places belongs to some dense set in <math>[3n].</math> Then if you have a 2D subspace with both wildcard sets of size d, one wildcard set consisting of odd numbers and the other of even numbers (which this proof gives), then this implies that in your dense set of integers you can find four integers of the form a, a+d, a+2d, a+d+2d, which is an arithmetic progression of length 4.

==Further remarks==

The k=3 generalisation of the LYM inequality is the [[hyper-optimistic conjecture]].

Sperner's theorem is also related to the [[Kruskal-Katona theorem]].

* [http://en.wikipedia.org/wiki/Sperner%27s_theorem The Wikipedia entry for Sperner's theorem]
* [http://en.wikipedia.org/wiki/Lubell-Yamamoto-Meshalkin_inequality The Wikipedia entry for the LYM inequality]