Proof of DHJ(3) via density-increment - Revision history

Ryanworldwide at 21:58, 20 March 2009

2009-03-20T21:58:03Z

← Older revision		Revision as of 14:58, 20 March 2009
Line 118:		Line 118:

	Written mostly completely [[Line-free_sets_correlate_locally_with_complexity-1_sets\|here]], although some of the "passing between measures" tricks that were done for the uniform distribution should be done for the Pólya distribution instead.		Written mostly completely [[Line-free_sets_correlate_locally_with_complexity-1_sets\|here]], although some of the "passing between measures" tricks that were done for the uniform distribution should be done for the Pólya distribution instead.


	===8. Line-free sets increment on subspaces===		===8. Line-free sets increment on subspaces===

Ryanworldwide: /* 7. Line-free sets increment on intersections of ij-insensitive sets */

2009-03-20T21:57:01Z

7. Line-free sets increment on intersections of ij-insensitive sets

← Older revision		Revision as of 14:57, 20 March 2009
Line 117:		Line 117:
	<b>Proofread By:</b> <i>no one yet</i>		<b>Proofread By:</b> <i>no one yet</i>

	Written mostly completely [[Line-free_sets_correlate_locally_with_complexity-1_sets\|here]].		Written mostly completely [[Line-free_sets_correlate_locally_with_complexity-1_sets\|here]], although some of the "passing between measures" tricks that were done for the uniform distribution should be done for the Pólya distribution instead.


	===8. Line-free sets increment on subspaces===		===8. Line-free sets increment on subspaces===

Ryanworldwide: /* 5. ij-insensitive sets are subspace partitionable */

2009-03-20T21:53:42Z

5. ij-insensitive sets are subspace partitionable

← Older revision		Revision as of 14:53, 20 March 2009
Line 102:		Line 102:
	:'''Definition:''' A set <math>A \subseteq [3]^n</math> is "<math>(\gamma,d)</math>-subspace partitionable" if it can be written as a disjoint union of <math>d</math>-dimensional combinatorial subspaces, along with a single "error" set <math>E</math> satisfying <math>\nu(E)/\nu(A) \leq \gamma</math>.		:'''Definition:''' A set <math>A \subseteq [3]^n</math> is "<math>(\gamma,d)</math>-subspace partitionable" if it can be written as a disjoint union of <math>d</math>-dimensional combinatorial subspaces, along with a single "error" set <math>E</math> satisfying <math>\nu(E)/\nu(A) \leq \gamma</math>.

	:'''Lemma 5:''' Let A \subseteq [3]^n be an <math>ij</math>-insensitive set with <math>\nu</math>-density at least <math>\delta</math>, let <math>d \geq 1</math>, and let <math>\gamma \in (0,1)</math> be a parameter. Assume that <math>n \geq n_5(\delta,\gamma,d) = XXX</math>. Then <math>A</math> is <math>(\gamma,d)</math>-subspace partitionable.		:'''Lemma 5:''' Let <math>A \subseteq [3]^n</math> be an <math>ij</math>-insensitive set with <math>\nu</math>-density at least <math>\delta</math>, let <math>d \geq 1</math>, and let <math>\gamma \in (0,1)</math> be a parameter. Assume that <math>n \geq n_5(\delta,\gamma,d) = XXX</math>. Then <math>A</math> is <math>(\gamma,d)</math>-subspace partitionable.

	This is currently written fairly thoroughly [[A_general_partitioning_principle\|here]], although the parameters need to be worked out to fill in the "XXX" in the statement.		This is currently written fairly thoroughly [[A_general_partitioning_principle\|here]], although the parameters need to be worked out to fill in the "XXX" in the statement.


	===6. Intersections of <math>ij</math>-insensitive sets are subspace partitionable===		===6. Intersections of <math>ij</math>-insensitive sets are subspace partitionable===

Ryanworldwide at 21:53, 20 March 2009

2009-03-20T21:53:08Z

Ryanworldwide at 21:52, 20 March 2009

2009-03-20T21:52:26Z

Ryanworldwide: /* 5. ij-insensitive sets are subspace partitionable */

2009-03-20T21:40:07Z

5. ij-insensitive sets are subspace partitionable

← Older revision		Revision as of 14:40, 20 March 2009
Line 94:		Line 94:

	<b>Proofread By:</b> <i>no one yet</i>		<b>Proofread By:</b> <i>no one yet</i>

			:'''Definition:''' A set <math>A \subseteq [3]^n</math> is "<math>(\gamma,d)</math>-subspace partitionable" if it can be written as a disjoint union of <math>d</math>-dimensional combinatorial subspaces and a single "error" set <math>E</math> satisfying <math>\nu_3(E)/\nu_3(A) \leq \gamma</math>.

			:'''Theorem 5:''' Let A \subseteq [3]^n be an <math>ij</math>XXX-insensitive set with ν-density at least δ, and let d \geq 1. Assume that n \geq n_4(\delta,d) = n_3(\delta/2,d). Then a random d-dimensional subspace drawn from \nu^n_{3+d} is in A with probability at least \eta_4(\delta, d) = \delta/(O(d))^{n_4(\delta,d)}

	This is currently written fairly thoroughly [[A_general_partitioning_principle\|here]], though some of the details of the density/probability calculations are sketched.		This is currently written fairly thoroughly [[A_general_partitioning_principle\|here]], though some of the details of the density/probability calculations are sketched.

Ryanworldwide: /* 4. ij-insensitive sets are subspace rich */

2009-03-20T21:33:56Z

4. ij-insensitive sets are subspace rich

← Older revision		Revision as of 14:33, 20 March 2009
Line 79:		Line 79:
	<b>Proofread By:</b> <i>no one yet</i>		<b>Proofread By:</b> <i>no one yet</i>

	: '''Lemma 4:''' Let <math>A \subseteq [3]^n</math> be an <math>ij</math>-insensitive set with <math>\nu</math>-density at least <math>\delta</math>, and let <math>d \geq 1</math>. Assume that <math>n \geq n_4(\delta,d) = n_3(\delta/2,d)</math>. Then a random <math>d</math>-dimensional subspace drawn from <math>\~~nu_~~{3+d}</math> is in <math>A</math> with probability at least <math>\eta_4(\delta, d) = \delta/(O(d))^{n_4(\delta,d)}</math>.		: '''Lemma 4:''' Let <math>A \subseteq [3]^n</math> be an <math>ij</math>-insensitive set with <math>\nu</math>-density at least <math>\delta</math>, and let <math>d \geq 1</math>. Assume that <math>n \geq n_4(\delta,d) = n_3(\delta/2,d)</math>. Then a random <math>d</math>-dimensional subspace drawn from <math>\nu^n_{3+d}</math> is in <math>A</math> with probability at least <math>\eta_4(\delta, d) = \delta/(O(d))^{n_4(\delta,d)}</math>.

	This is sketched originally [[A_second_outline_of_a_density-increment_argument#Step_1:_a_dense_1-set_contains_an_abundance_of_combinatorial_subspaces\|here]]. Here is a more complete argument:		This is sketched originally [[A_second_outline_of_a_density-increment_argument#Step_1:_a_dense_1-set_contains_an_abundance_of_combinatorial_subspaces\|here]]. Here is a more complete argument:

Ryanworldwide at 21:33, 20 March 2009

2009-03-20T21:33:01Z

← Older revision		Revision as of 14:33, 20 March 2009
Line 68:		Line 68:

	: '''Lemma 3:''' Let <math>A \subseteq [3]^n</math> be an <math>ij</math>-insensitive set with <math>\nu_3</math>-density at least <math>\delta</math>, and let <math>d \geq 1</math>. Assume that <math>n \geq n_3(\delta,d) = \sqrt{2/\delta} \cdot n_2(\delta/2, d)</math>. Then <math>A</math> contains a <math>d</math>-dimensional combinatorial subspace.		: '''Lemma 3:''' Let <math>A \subseteq [3]^n</math> be an <math>ij</math>-insensitive set with <math>\nu_3</math>-density at least <math>\delta</math>, and let <math>d \geq 1</math>. Assume that <math>n \geq n_3(\delta,d) = \sqrt{2/\delta} \cdot n_2(\delta/2, d)</math>. Then <math>A</math> contains a <math>d</math>-dimensional combinatorial subspace.


	We sketch the proof here, for now.		We sketch the proof here, for now.


	: '''Proof:''' (Sketch.) Assume without loss of generality that <math>i = 2</math>, <math>j = 3</math>. We can think of a draw <math>x \sim \nu_3^n</math> by first conditioning on the set of coordinates <math>S</math> where <math>x</math> has its <math>3</math>'s, and then drawing the remainder of the string as <math>y \sim \nu_2^{\|\overline{S}\|}</math>, where <math>\overline{S} = [n] \setminus S</math>. (This requires a quick justification.) Inventing some notation, we have <math>\mathbf{E}_S[\nu_2(A_S)] = \delta</math>. Further, it should be easy to check that <math>\mathbf{Pr}[\|\overline{S}\| <\gamma n] \leq \gamma^2</math> (or perhaps only a tiny bit higher). Hence <math>\mathbf{E}_S[\nu_2(A_S) \mid \|\overline{S}\| \geq \gamma n] \geq \delta - \gamma^2.</math> We set <math>\gamma = \sqrt{\delta/2}</math> and conclude that there exists a particular set of <math>3</math>-coordinates <math>S_0</math> such that <math>\nu_2(A_{S_0}) \geq \delta/2</math> and <math>\|\overline{S_0}\| \geq \sqrt{\delta/2} n</math>. By choice of <math>n_2</math>, this lets us apply Theorem 2 to conclude that <math>A_{S_0} \subseteq [2]^{S_0}</math> contains a <math>d</math>-dimensional combinatorial subspace; call it <math>\sigma</math>.		: '''Proof:''' (Sketch.) Assume without loss of generality that <math>i = 2</math>, <math>j = 3</math>. We can think of a draw <math>x \sim \nu_3^n</math> by first conditioning on the set of coordinates <math>S</math> where <math>x</math> has its <math>3</math>'s, and then drawing the remainder of the string as <math>y \sim \nu_2^{\|\overline{S}\|}</math>, where <math>\overline{S} = [n] \setminus S</math>. (This requires a quick justification.) Inventing some notation, we have <math>\mathbf{E}_S[\nu_2(A_S)] = \delta</math>. Further, it should be easy to check that <math>\mathbf{Pr}[\|\overline{S}\| <\gamma n] \leq \gamma^2</math> (or perhaps only a tiny bit higher). Hence <math>\mathbf{E}_S[\nu_2(A_S) \mid \|\overline{S}\| \geq \gamma n] \geq \delta - \gamma^2.</math> We set <math>\gamma = \sqrt{\delta/2}</math> and conclude that there exists a particular set of <math>3</math>-coordinates <math>S_0</math> such that <math>\nu_2(A_{S_0}) \geq \delta/2</math> and <math>\|\overline{S_0}\| \geq \sqrt{\delta/2} n</math>. By choice of <math>n_2</math>, this lets us apply Theorem 2 to conclude that <math>A_{S_0} \subseteq [2]^{S_0}</math> contains a <math>d</math>-dimensional combinatorial subspace; call it <math>\sigma</math>.
Line 81:		Line 79:
	<b>Proofread By:</b> <i>no one yet</i>		<b>Proofread By:</b> <i>no one yet</i>

	: '''Lemma 4:''' Let <math>A \subseteq [3]^n</math> be an <math>ij</math>-insensitive set with <math>\nu</math>-density at least <math>\delta</math>, and let <math>d \geq 1</math>. Assume that <math>n \geq n_4(\delta,d) = n_3(\delta/2,d)</math>. Then a random <math>d</math>-dimensional subspace drawn from <math>\nu_{3+d}</math> is in <math>A</math> with probability at least <math>\eta_4(\delta, d) = ~~XXX~~</math>.		: '''Lemma 4:''' Let <math>A \subseteq [3]^n</math> be an <math>ij</math>-insensitive set with <math>\nu</math>-density at least <math>\delta</math>, and let <math>d \geq 1</math>. Assume that <math>n \geq n_4(\delta,d) = n_3(\delta/2,d)</math>. Then a random <math>d</math>-dimensional subspace drawn from <math>\nu_{3+d}</math> is in <math>A</math> with probability at least <math>\eta_4(\delta, d) = \delta/(O(d))^{n_4(\delta,d)}</math>.

	This is sketched originally [[A_second_outline_of_a_density-increment_argument#Step_1:_a_dense_1-set_contains_an_abundance_of_combinatorial_subspaces\|here]]. Here is a more complete argument:		This is sketched originally [[A_second_outline_of_a_density-increment_argument#Step_1:_a_dense_1-set_contains_an_abundance_of_combinatorial_subspaces\|here]]. Here is a more complete argument:

	: '''Proof:''' For any <math>3 \leq m \leq n</math> one can draw a string <math>h \sim \nu_3^n</math> as follows: First, draw <math>f \sim \nu_m^n</math>; then independently draw <math>g \sim \nu_3^m</math>; finally, set <math>h = g \circ f</math>. This notation means that <math>h_i = g_{f_i}</math>. The fact that this indeed gives the distribution <math>\nu_3^n</math> is justified in [[http://www.cs.cmu.edu/~odonnell/more-ordered-partitions.pdf\|this document]], but should be simplified and ported to the wiki.		: '''Proof:''' (Sketch.) For any <math>3 \leq m \leq n</math> one can draw a string <math>h \sim \nu_3^n</math> as follows: First, draw <math>f \sim \nu_m^n</math>; then independently draw <math>g \sim \nu_3^m</math>; finally, set <math>h = g \circ f</math>. This notation means that <math>h_i = g_{f_i}</math>. The fact that this indeed gives the distribution <math>\nu_3^n</math> is justified in [[http://www.cs.cmu.edu/~odonnell/more-ordered-partitions.pdf\|this document]], but should be simplified and ported to the wiki.

	: By assumption, <math>\mathbf{Pr}[h \in A] \geq \delta</math>; hence with probability at least <math>\delta/2</math> over the choice of <math>f</math> we get that <math>A_f \subseteq [3]^m</math> has <math>\nu_3</math>-density at least <math>\delta/2</math>. Here <math>A_f</math> of course denotes <math>\{g \in [3]^m : g \circ f \in A</math>. Crucially, <math>A_f</math> is an <math>ij</math>-insensitive set because <math>A</math>. (This takes a slight bit of reflection but is, I think, easily confirmed.) Call an <math>f</math> "good" if indeed <math>\nu_3(A_f) \geq \delta/2</math>.		: By assumption, <math>\mathbf{Pr}[h \in A] \geq \delta</math>; hence with probability at least <math>\delta/2</math> over the choice of <math>f</math> we get that <math>A_f \subseteq [3]^m</math> has <math>\nu_3</math>-density at least <math>\delta/2</math>. Here <math>A_f</math> of course denotes <math>\{g \in [3]^m : g \circ f \in A</math>. Crucially, <math>A_f</math> is an <math>ij</math>-insensitive set because <math>A</math>. (This takes a slight bit of reflection but is, I think, easily confirmed.) Call an <math>f</math> "good" if indeed <math>\nu_3(A_f) \geq \delta/2</math>.

	: We therefore select <math>m = n_3(\delta/2,d)</math> (which is allowable as <math>n \geq n_3(\delta/2,d)</math>) and use Lemma 3 to conclude that for each good <math>f</math>, the set <math>A_f</math> contains some <math>d</math>-dimensional subspace. In these cases, a <i>randomly</i> chosen subspace <math>\sigma \sim [3+d]^m</math> is in <math>A_f</math> with some positive probability. ~~To be continued~~...		: We therefore select <math>m = n_3(\delta/2,d)</math> (which is allowable as <math>n \geq n_3(\delta/2,d)</math>) and use Lemma 3 to conclude that for each good <math>f</math>, the set <math>A_f</math> contains some <math>d</math>-dimensional subspace. In these cases, a <i>randomly</i> chosen subspace <math>\sigma \sim [3+d]^m</math> is in <math>A_f</math> with some positive probability. At this point, we should calculate the least probability of any outcome under <math>\nu_k^n</math>; I believe it is <math>\frac{\Theta(1/k)^{k/2}}{n^{(k-1)/2} \cdot k^n}</math>. Lower-bounding this crudely, we have that <math>\sigma \sim [3+d]^m</math> is in <math>A_f</math> with probability at least <math>(O(d))^{-m}</math>.

			: So overall we have that for <math>f \sim \nu_3^m</math> and <math>\sigma \sim [3+d]^m</math>, the probability of <math>\sigma \circ f</math> being entirely in <math>A</math> is at least <math>\delta/(O(d))^m = \delta/(O(d))^{n_3(\delta/2,d)}</math>. But <math>\sigma \circ f</math> is distributed as <math>\nu_{3+d}^n</math>, completing the proof. <math>\Box</math>

	===5. <math>ij</math>-insensitive sets are subspace partitionable===		===5. <math>ij</math>-insensitive sets are subspace partitionable===

91.85.186.58 at 18:44, 20 March 2009

2009-03-20T18:44:54Z

← Older revision		Revision as of 11:44, 20 March 2009
Line 63:		Line 63:
	Let <math>i,j \in [k]</math> be distinct characters. We define <math>A \subseteq [k]^n</math> to be an "<math>ij</math>-insensitive set" if for all strings <math>x</math>, changing <math>i</math>'s to <math>j</math>'s in <math>x</math> or vice versa does not change whether or not <math>x \in A</math>.		Let <math>i,j \in [k]</math> be distinct characters. We define <math>A \subseteq [k]^n</math> to be an "<math>ij</math>-insensitive set" if for all strings <math>x</math>, changing <math>i</math>'s to <math>j</math>'s in <math>x</math> or vice versa does not change whether or not <math>x \in A</math>.

	An <math>ij</math>-insensitive in <math>[k]^n</math> is elsewhere on the blog called a "<math>1</math>-set", ~~being~~ a special case of a [[Complexity_of_a_set\|special set of complexity <math>1</math>]]. See also this article discussing [[Line_free_sets_correlate_locally_with_dense_sets_of_complexity_k-2\|the complexity of sets]].		An <math>23</math>-insensitive in <math>[3]^n</math> is elsewhere on the blog called a "<math>1</math>-set", since it depends only on the set of coordinates where the value 1 is taken. It is a special case of a [[Complexity_of_a_set\|special set of complexity <math>1</math>]]. See also this article discussing [[Line_free_sets_correlate_locally_with_dense_sets_of_complexity_k-2\|the complexity of sets]].

	The statement we prove here is:		The statement we prove here is:

Ryanworldwide at 17:54, 20 March 2009

2009-03-20T17:54:45Z

← Older revision		Revision as of 10:54, 20 March 2009
Line 1:		Line 1:
	==Introduction==		==Introduction==

	This article is intended to contain a proof outline of DHJ(<math>3</math>) via the [[Density_increment_method\|density-increment method]]. The proofs of each step in the outline will appear in separate articles. The goal is to rigorously codify the [[A_second_outline_of_a_density-increment_argument\|"second outline"]] proof. A secondary goal is to write the proof in such a way that it becomes "easy" to see the generalization to DHJ(<math>k</math>).		This article is intended to contain a proof outline of DHJ(<math>3</math>) via the [[Density_increment_method\|density-increment method]]. The proofs of each step in the outline will appear in separate articles. The goal is to rigorously codify the [[A_second_outline_of_a_density-increment_argument\|"second outline"]] proof. A secondary goal is to write the proof in such a way that it becomes "easy" to see the generalization to DHJ(<math>k</math>). Each step of the outline has a "Proofread By" section to which people can add their names.


Line 37:		Line 37:

	===1. Sets in <math>[2]^n</math> have lines===		===1. Sets in <math>[2]^n</math> have lines===

			<b>Proofread By:</b> <i>no one yet</i>

	This is simply Sperner's Theorem. Our version, with the Pólya Urn distribution, is:		This is simply Sperner's Theorem. Our version, with the Pólya Urn distribution, is:
Line 43:		Line 45:

	: '''[[Proof of Sperner's Theorem]]'''. For now, the proof more or less appears in the article on [[Sperner%27s_theorem#Proof_of_the_theorem\|Sperner's Theorem]]; we might want to use the writeup ideas in the current article on [[Equal-slices_distribution_for_DHJ(k)\|Equal Slices]]. The easiest proof involves first passing from Pólya to Equal Slices. I think you only need <math>n_1(\delta) > 1/\delta^2 + 1</math> or something.		: '''[[Proof of Sperner's Theorem]]'''. For now, the proof more or less appears in the article on [[Sperner%27s_theorem#Proof_of_the_theorem\|Sperner's Theorem]]; we might want to use the writeup ideas in the current article on [[Equal-slices_distribution_for_DHJ(k)\|Equal Slices]]. The easiest proof involves first passing from Pólya to Equal Slices. I think you only need <math>n_1(\delta) > 1/\delta^2 + 1</math> or something.


	===2. Sets in <math>[2]^n</math> have subspaces===		===2. Sets in <math>[2]^n</math> have subspaces===

			<b>Proofread By:</b> <i>no one yet</i>

	The next step is to extend DHJ(<math>2</math>) from lines to subspaces of arbitrary dimension.		The next step is to extend DHJ(<math>2</math>) from lines to subspaces of arbitrary dimension.
Line 50:		Line 55:
	: '''Theorem 2:''' Let <math>A \subseteq [2]^n</math> have <math>\nu_2</math>-density at least <math>\delta</math>, and let <math>d \geq 1</math>. Assume that <math>n \geq n_2(\delta,d)</math>. Then <math>A</math> contains a <math>d</math>-dimensional combinatorial subspace. Here <math>n_2(\delta,d)</math> probably only needs to be <math>O(1/\delta)^{2^{d+1}}</math>		: '''Theorem 2:''' Let <math>A \subseteq [2]^n</math> have <math>\nu_2</math>-density at least <math>\delta</math>, and let <math>d \geq 1</math>. Assume that <math>n \geq n_2(\delta,d)</math>. Then <math>A</math> contains a <math>d</math>-dimensional combinatorial subspace. Here <math>n_2(\delta,d)</math> probably only needs to be <math>O(1/\delta)^{2^{d+1}}</math>

	This sort of result has been shown for the uniform distribution case by Gunderson-Rödl-Sidorenko, from which one can easily conclude the Pólya distribution case by [[passing between measures]]. Alternatively, one can prove the result with a (much) worse bound on <math>n_2</math> using an [[DHJ(k)_implies_multidimensional_DHJ(k)\|argument which generalizes to <math>[k]^n</math>]]. A few technical bits need to be filled into this argument; namely, showing that if one does Pólya on some small random subset <math>S \subseteq [n]</math>, and then combines this with an independent Pólya draw on <math>[n] \setminus S</math>, the overall draw is very close in total variation distance to a normal Pólya draw. This is proved rather explicitly in the [[Passing_between_measures\|passing between measures]] article. (Presumably there is also literature from the Pólya Urn studiers on this, too.)		This sort of result has been shown for the uniform distribution case by [[http://home.cc.umanitoba.ca/~gunderso/published_work/paper7.pdf\|Gunderson-Rödl-Sidorenko]], from which one can easily conclude the Pólya distribution case by [[passing between measures]]. Alternatively, one can prove the result with a (much) worse bound on <math>n_2</math> using an [[DHJ(k)_implies_multidimensional_DHJ(k)\|argument which generalizes to <math>[k]^n</math>]]. A few technical bits need to be filled into this argument; namely, showing that if one does Pólya on some small random subset <math>S \subseteq [n]</math>, and then combines this with an independent Pólya draw on <math>[n] \setminus S</math>, the overall draw is very close in total variation distance to a normal Pólya draw. This is proved rather explicitly in the [[Passing_between_measures\|passing between measures]] article. (Presumably there is also literature from the Pólya Urn studiers on this, too.)

	===3. <math>ij</math>-insensitive sets in <math>[3]^n</math> have subspaces===		===3. <math>ij</math>-insensitive sets in <math>[3]^n</math> have subspaces===

			<b>Proofread By:</b> <i>no one yet</i>

	Let <math>i,j \in [k]</math> be distinct characters. We define <math>A \subseteq [k]^n</math> to be an "<math>ij</math>-insensitive set" if for all strings <math>x</math>, changing <math>i</math>'s to <math>j</math>'s in <math>x</math> or vice versa does not change whether or not <math>x \in A</math>.		Let <math>i,j \in [k]</math> be distinct characters. We define <math>A \subseteq [k]^n</math> to be an "<math>ij</math>-insensitive set" if for all strings <math>x</math>, changing <math>i</math>'s to <math>j</math>'s in <math>x</math> or vice versa does not change whether or not <math>x \in A</math>.
Line 60:		Line 67:
	The statement we prove here is:		The statement we prove here is:

	: '''Lemma 3:''' Let <math>A \subseteq [3]^n</math> be an <math>ij</math>-insensitive set with <math>\~~nu_2~~</math>-density at least <math>\delta</math>. Assume that <math>n \geq n_3(\delta) = \sqrt{2/\delta} \cdot n_2(\delta/2, d)</math>. Then <math>A</math> contains a <math>d</math>-dimensional combinatorial subspace.		: '''Lemma 3:''' Let <math>A \subseteq [3]^n</math> be an <math>ij</math>-insensitive set with <math>\nu_3</math>-density at least <math>\delta</math>, and let <math>d \geq 1</math>. Assume that <math>n \geq n_3(\delta,d) = \sqrt{2/\delta} \cdot n_2(\delta/2, d)</math>. Then <math>A</math> contains a <math>d</math>-dimensional combinatorial subspace.


Line 72:		Line 79:
	===4. <math>ij</math>-insensitive sets are subspace rich===		===4. <math>ij</math>-insensitive sets are subspace rich===

	This is sketched originally [[A_second_outline_of_a_density-increment_argument#Step_1:_a_dense_1-set_contains_an_abundance_of_combinatorial_subspaces\|here]], ~~and should be provable rather nicely using~~ the ~~ideas~~ in ~~the last paragraph of~~ [[http://www.cs.cmu.edu/~odonnell/more-ordered-partitions.pdf\|this document]].		<b>Proofread By:</b> <i>no one yet</i>

			: '''Lemma 4:''' Let <math>A \subseteq [3]^n</math> be an <math>ij</math>-insensitive set with <math>\nu</math>-density at least <math>\delta</math>, and let <math>d \geq 1</math>. Assume that <math>n \geq n_4(\delta,d) = n_3(\delta/2,d)</math>. Then a random <math>d</math>-dimensional subspace drawn from <math>\nu_{3+d}</math> is in <math>A</math> with probability at least <math>\eta_4(\delta, d) = XXX</math>.

			This is sketched originally [[A_second_outline_of_a_density-increment_argument#Step_1:_a_dense_1-set_contains_an_abundance_of_combinatorial_subspaces\|here]]. Here is a more complete argument:

			: '''Proof:''' For any <math>3 \leq m \leq n</math> one can draw a string <math>h \sim \nu_3^n</math> as follows: First, draw <math>f \sim \nu_m^n</math>; then independently draw <math>g \sim \nu_3^m</math>; finally, set <math>h = g \circ f</math>. This notation means that <math>h_i = g_{f_i}</math>. The fact that this indeed gives the distribution <math>\nu_3^n</math> is justified in [[http://www.cs.cmu.edu/~odonnell/more-ordered-partitions.pdf\|this document]], but should be simplified and ported to the wiki.

			: By assumption, <math>\mathbf{Pr}[h \in A] \geq \delta</math>; hence with probability at least <math>\delta/2</math> over the choice of <math>f</math> we get that <math>A_f \subseteq [3]^m</math> has <math>\nu_3</math>-density at least <math>\delta/2</math>. Here <math>A_f</math> of course denotes <math>\{g \in [3]^m : g \circ f \in A</math>. Crucially, <math>A_f</math> is an <math>ij</math>-insensitive set because <math>A</math>. (This takes a slight bit of reflection but is, I think, easily confirmed.) Call an <math>f</math> "good" if indeed <math>\nu_3(A_f) \geq \delta/2</math>.

			: We therefore select <math>m = n_3(\delta/2,d)</math> (which is allowable as <math>n \geq n_3(\delta/2,d)</math>) and use Lemma 3 to conclude that for each good <math>f</math>, the set <math>A_f</math> contains some <math>d</math>-dimensional subspace. In these cases, a <i>randomly</i> chosen subspace <math>\sigma \sim [3+d]^m</math> is in <math>A_f</math> with some positive probability. To be continued...

	===5. <math>ij</math>-insensitive sets are subspace partitionable===		===5. <math>ij</math>-insensitive sets are subspace partitionable===

			<b>Proofread By:</b> <i>no one yet</i>

	This is currently written fairly thoroughly [[A_general_partitioning_principle\|here]], though some of the details of the density/probability calculations are sketched.		This is currently written fairly thoroughly [[A_general_partitioning_principle\|here]], though some of the details of the density/probability calculations are sketched.

	===6. Intersections of <math>ij</math>-insensitive sets are subspace partitionable===		===6. Intersections of <math>ij</math>-insensitive sets are subspace partitionable===

			<b>Proofread By:</b> <i>no one yet</i>

	Currently written [[A_second_outline_of_a_density-increment_argument#Step_3:_a_dense_12-set_can_be_almost_entirely_partitioned_into_large_subspaces\|here]].		Currently written [[A_second_outline_of_a_density-increment_argument#Step_3:_a_dense_12-set_can_be_almost_entirely_partitioned_into_large_subspaces\|here]].

	===7. Line-free sets increment on intersections of <math>ij</math>-insensitive sets===		===7. Line-free sets increment on intersections of <math>ij</math>-insensitive sets===

			<b>Proofread By:</b> <i>no one yet</i>

	Written mostly completely [[Line-free_sets_correlate_locally_with_complexity-1_sets\|here]].		Written mostly completely [[Line-free_sets_correlate_locally_with_complexity-1_sets\|here]].

	===8. Line-free sets increment on subspaces===		===8. Line-free sets increment on subspaces===

			<b>Proofread By:</b> <i>no one yet</i>

	Sketch [[A_second_outline_of_a_density-increment_argument#How_the_proof_works\|here]].		Sketch [[A_second_outline_of_a_density-increment_argument#How_the_proof_works\|here]].

	===9. Sets in <math>[3]^n</math> have lines===		===9. Sets in <math>[3]^n</math> have lines===

			<b>Proofread By:</b> <i>no one yet</i>

	The basic idea is described in the article on the [[density increment method]].		The basic idea is described in the article on the [[density increment method]].

← Older revision		Revision as of 14:53, 20 March 2009
Line 13:		Line 13:

	Although we will prove DHJ(<math>3</math>) for sets that are dense under <math>\nu_3</math>, this also proves it for sets that are dense under the usual uniform distribution; this should be explicated in the article on [[passing between measures]].		Although we will prove DHJ(<math>3</math>) for sets that are dense under <math>\nu_3</math>, this also proves it for sets that are dense under the usual uniform distribution; this should be explicated in the article on [[passing between measures]].


	==Proof Outline==		==Proof Outline==
Line 35:		Line 36:

	9. Dense sets in <math>[3]^n</math> contain lines (i.e., DHJ(<math>3</math>)).		9. Dense sets in <math>[3]^n</math> contain lines (i.e., DHJ(<math>3</math>)).


	===1. Sets in <math>[2]^n</math> have lines===		===1. Sets in <math>[2]^n</math> have lines===
Line 56:		Line 58:

	This sort of result has been shown for the uniform distribution case by [[http://home.cc.umanitoba.ca/~gunderso/published_work/paper7.pdf\|Gunderson-Rödl-Sidorenko]], from which one can easily conclude the Pólya distribution case by [[passing between measures]]. Alternatively, one can prove the result with a (much) worse bound on <math>n_2</math> using an [[DHJ(k)_implies_multidimensional_DHJ(k)\|argument which generalizes to <math>[k]^n</math>]]. A few technical bits need to be filled into this argument; namely, showing that if one does Pólya on some small random subset <math>S \subseteq [n]</math>, and then combines this with an independent Pólya draw on <math>[n] \setminus S</math>, the overall draw is very close in total variation distance to a normal Pólya draw. This is proved rather explicitly in the [[Passing_between_measures\|passing between measures]] article. (Presumably there is also literature from the Pólya Urn studiers on this, too.)		This sort of result has been shown for the uniform distribution case by [[http://home.cc.umanitoba.ca/~gunderso/published_work/paper7.pdf\|Gunderson-Rödl-Sidorenko]], from which one can easily conclude the Pólya distribution case by [[passing between measures]]. Alternatively, one can prove the result with a (much) worse bound on <math>n_2</math> using an [[DHJ(k)_implies_multidimensional_DHJ(k)\|argument which generalizes to <math>[k]^n</math>]]. A few technical bits need to be filled into this argument; namely, showing that if one does Pólya on some small random subset <math>S \subseteq [n]</math>, and then combines this with an independent Pólya draw on <math>[n] \setminus S</math>, the overall draw is very close in total variation distance to a normal Pólya draw. This is proved rather explicitly in the [[Passing_between_measures\|passing between measures]] article. (Presumably there is also literature from the Pólya Urn studiers on this, too.)


	===3. <math>ij</math>-insensitive sets in <math>[3]^n</math> have subspaces===		===3. <math>ij</math>-insensitive sets in <math>[3]^n</math> have subspaces===
Line 74:		Line 77:

	: Pulling <math>\sigma</math> back into <math>[3]^n</math> by putting <math>3</math>'s into the <math>S</math> coordinates, we get a <math>d</math>-dimensional "<math>2</math>-subspace" in <math>A \subseteq [3]^n</math>. But in fact, all of the strings necessary to fill this out into a complete <math>d</math>-dimensional subspace in <math>[3]^n</math> must also be present in <math>A</math>, because <math>A</math> is <math>23</math>-insensitive. <math>\Box</math> (somewhat poorly explained)		: Pulling <math>\sigma</math> back into <math>[3]^n</math> by putting <math>3</math>'s into the <math>S</math> coordinates, we get a <math>d</math>-dimensional "<math>2</math>-subspace" in <math>A \subseteq [3]^n</math>. But in fact, all of the strings necessary to fill this out into a complete <math>d</math>-dimensional subspace in <math>[3]^n</math> must also be present in <math>A</math>, because <math>A</math> is <math>23</math>-insensitive. <math>\Box</math> (somewhat poorly explained)


	===4. <math>ij</math>-insensitive sets are subspace rich===		===4. <math>ij</math>-insensitive sets are subspace rich===
Line 90:		Line 94:

	: So overall we have that for <math>f \sim \nu_3^m</math> and <math>\sigma \sim [3+d]^m</math>, the probability of <math>\sigma \circ f</math> being entirely in <math>A</math> is at least <math>\delta/(O(d))^m = \delta/(O(d))^{n_3(\delta/2,d)}</math>. But <math>\sigma \circ f</math> is distributed as <math>\nu_{3+d}^n</math>, completing the proof. <math>\Box</math>		: So overall we have that for <math>f \sim \nu_3^m</math> and <math>\sigma \sim [3+d]^m</math>, the probability of <math>\sigma \circ f</math> being entirely in <math>A</math> is at least <math>\delta/(O(d))^m = \delta/(O(d))^{n_3(\delta/2,d)}</math>. But <math>\sigma \circ f</math> is distributed as <math>\nu_{3+d}^n</math>, completing the proof. <math>\Box</math>


	===5. <math>ij</math>-insensitive sets are subspace partitionable===		===5. <math>ij</math>-insensitive sets are subspace partitionable===
Line 100:		Line 105:

	This is currently written fairly thoroughly [[A_general_partitioning_principle\|here]], although the parameters need to be worked out to fill in the "XXX" in the statement.		This is currently written fairly thoroughly [[A_general_partitioning_principle\|here]], although the parameters need to be worked out to fill in the "XXX" in the statement.


	===6. Intersections of <math>ij</math>-insensitive sets are subspace partitionable===		===6. Intersections of <math>ij</math>-insensitive sets are subspace partitionable===
Line 106:		Line 112:

	Currently written [[A_second_outline_of_a_density-increment_argument#Step_3:_a_dense_12-set_can_be_almost_entirely_partitioned_into_large_subspaces\|here]].		Currently written [[A_second_outline_of_a_density-increment_argument#Step_3:_a_dense_12-set_can_be_almost_entirely_partitioned_into_large_subspaces\|here]].


	===7. Line-free sets increment on intersections of <math>ij</math>-insensitive sets===		===7. Line-free sets increment on intersections of <math>ij</math>-insensitive sets===
Line 112:		Line 119:

	Written mostly completely [[Line-free_sets_correlate_locally_with_complexity-1_sets\|here]].		Written mostly completely [[Line-free_sets_correlate_locally_with_complexity-1_sets\|here]].


	===8. Line-free sets increment on subspaces===		===8. Line-free sets increment on subspaces===
Line 118:		Line 126:

	Sketch [[A_second_outline_of_a_density-increment_argument#How_the_proof_works\|here]].		Sketch [[A_second_outline_of_a_density-increment_argument#How_the_proof_works\|here]].


	===9. Sets in <math>[3]^n</math> have lines===		===9. Sets in <math>[3]^n</math> have lines===

← Older revision		Revision as of 14:52, 20 March 2009
Line 53:		Line 53:
	The next step is to extend DHJ(<math>2</math>) from lines to subspaces of arbitrary dimension.		The next step is to extend DHJ(<math>2</math>) from lines to subspaces of arbitrary dimension.

	: '''~~Theorem~~ 2:''' Let <math>A \subseteq [2]^n</math> have <math>\nu_2</math>-density at least <math>\delta</math>, and let <math>d \geq 1</math>. Assume that <math>n \geq n_2(\delta,d)</math>. Then <math>A</math> contains a <math>d</math>-dimensional combinatorial subspace. Here <math>n_2(\delta,d)</math> probably only needs to be <math>O(1/\delta)^{2^{d+1}}</math>		: '''Lemma 2:''' Let <math>A \subseteq [2]^n</math> have <math>\nu_2</math>-density at least <math>\delta</math>, and let <math>d \geq 1</math>. Assume that <math>n \geq n_2(\delta,d)</math>. Then <math>A</math> contains a <math>d</math>-dimensional combinatorial subspace. Here <math>n_2(\delta,d)</math> probably only needs to be <math>O(1/\delta)^{2^{d+1}}</math>

	This sort of result has been shown for the uniform distribution case by [[http://home.cc.umanitoba.ca/~gunderso/published_work/paper7.pdf\|Gunderson-Rödl-Sidorenko]], from which one can easily conclude the Pólya distribution case by [[passing between measures]]. Alternatively, one can prove the result with a (much) worse bound on <math>n_2</math> using an [[DHJ(k)_implies_multidimensional_DHJ(k)\|argument which generalizes to <math>[k]^n</math>]]. A few technical bits need to be filled into this argument; namely, showing that if one does Pólya on some small random subset <math>S \subseteq [n]</math>, and then combines this with an independent Pólya draw on <math>[n] \setminus S</math>, the overall draw is very close in total variation distance to a normal Pólya draw. This is proved rather explicitly in the [[Passing_between_measures\|passing between measures]] article. (Presumably there is also literature from the Pólya Urn studiers on this, too.)		This sort of result has been shown for the uniform distribution case by [[http://home.cc.umanitoba.ca/~gunderso/published_work/paper7.pdf\|Gunderson-Rödl-Sidorenko]], from which one can easily conclude the Pólya distribution case by [[passing between measures]]. Alternatively, one can prove the result with a (much) worse bound on <math>n_2</math> using an [[DHJ(k)_implies_multidimensional_DHJ(k)\|argument which generalizes to <math>[k]^n</math>]]. A few technical bits need to be filled into this argument; namely, showing that if one does Pólya on some small random subset <math>S \subseteq [n]</math>, and then combines this with an independent Pólya draw on <math>[n] \setminus S</math>, the overall draw is very close in total variation distance to a normal Pólya draw. This is proved rather explicitly in the [[Passing_between_measures\|passing between measures]] article. (Presumably there is also literature from the Pólya Urn studiers on this, too.)
Line 71:		Line 71:
	We sketch the proof here, for now.		We sketch the proof here, for now.

	: '''Proof:''' (Sketch.) Assume without loss of generality that <math>i = 2</math>, <math>j = 3</math>. We can think of a draw <math>x \sim \nu_3^n</math> by first conditioning on the set of coordinates <math>S</math> where <math>x</math> has its <math>3</math>'s, and then drawing the remainder of the string as <math>y \sim \nu_2^{\|\overline{S}\|}</math>, where <math>\overline{S} = [n] \setminus S</math>. (This requires a quick justification.) Inventing some notation, we have <math>\mathbf{E}_S[\nu_2(A_S)] = \delta</math>. Further, it should be easy to check that <math>\mathbf{Pr}[\|\overline{S}\| <\gamma n] \leq \gamma^2</math> (or perhaps only a tiny bit higher). Hence <math>\mathbf{E}_S[\nu_2(A_S) \mid \|\overline{S}\| \geq \gamma n] \geq \delta - \gamma^2.</math> We set <math>\gamma = \sqrt{\delta/2}</math> and conclude that there exists a particular set of <math>3</math>-coordinates <math>S_0</math> such that <math>\nu_2(A_{S_0}) \geq \delta/2</math> and <math>\|\overline{S_0}\| \geq \sqrt{\delta/2} n</math>. By choice of <math>n_2</math>, this lets us apply ~~Theorem~~ 2 to conclude that <math>A_{S_0} \subseteq [2]^{S_0}</math> contains a <math>d</math>-dimensional combinatorial subspace; call it <math>\sigma</math>.		: '''Proof:''' (Sketch.) Assume without loss of generality that <math>i = 2</math>, <math>j = 3</math>. We can think of a draw <math>x \sim \nu_3^n</math> by first conditioning on the set of coordinates <math>S</math> where <math>x</math> has its <math>3</math>'s, and then drawing the remainder of the string as <math>y \sim \nu_2^{\|\overline{S}\|}</math>, where <math>\overline{S} = [n] \setminus S</math>. (This requires a quick justification.) Inventing some notation, we have <math>\mathbf{E}_S[\nu_2(A_S)] = \delta</math>. Further, it should be easy to check that <math>\mathbf{Pr}[\|\overline{S}\| <\gamma n] \leq \gamma^2</math> (or perhaps only a tiny bit higher). Hence <math>\mathbf{E}_S[\nu_2(A_S) \mid \|\overline{S}\| \geq \gamma n] \geq \delta - \gamma^2.</math> We set <math>\gamma = \sqrt{\delta/2}</math> and conclude that there exists a particular set of <math>3</math>-coordinates <math>S_0</math> such that <math>\nu_2(A_{S_0}) \geq \delta/2</math> and <math>\|\overline{S_0}\| \geq \sqrt{\delta/2} n</math>. By choice of <math>n_2</math>, this lets us apply Lemma 2 to conclude that <math>A_{S_0} \subseteq [2]^{S_0}</math> contains a <math>d</math>-dimensional combinatorial subspace; call it <math>\sigma</math>.

	: Pulling <math>\sigma</math> back into <math>[3]^n</math> by putting <math>3</math>'s into the <math>S</math> coordinates, we get a <math>d</math>-dimensional "<math>2</math>-subspace" in <math>A \subseteq [3]^n</math>. But in fact, all of the strings necessary to fill this out into a complete <math>d</math>-dimensional subspace in <math>[3]^n</math> must also be present in <math>A</math>, because <math>A</math> is <math>23</math>-insensitive. <math>\Box</math> (somewhat poorly explained)		: Pulling <math>\sigma</math> back into <math>[3]^n</math> by putting <math>3</math>'s into the <math>S</math> coordinates, we get a <math>d</math>-dimensional "<math>2</math>-subspace" in <math>A \subseteq [3]^n</math>. But in fact, all of the strings necessary to fill this out into a complete <math>d</math>-dimensional subspace in <math>[3]^n</math> must also be present in <math>A</math>, because <math>A</math> is <math>23</math>-insensitive. <math>\Box</math> (somewhat poorly explained)
Line 95:		Line 95:
	<b>Proofread By:</b> <i>no one yet</i>		<b>Proofread By:</b> <i>no one yet</i>

	:'''Definition:''' A set <math>A \subseteq [3]^n</math> is "<math>(\gamma,d)</math>-subspace partitionable" if it can be written as a disjoint union of <math>d</math>-dimensional combinatorial subspaces ~~and~~ a single "error" set <math>E</math> satisfying <math>\~~nu_3~~(E)/\~~nu_3~~(A) \leq \gamma</math>.		:'''Definition:''' A set <math>A \subseteq [3]^n</math> is "<math>(\gamma,d)</math>-subspace partitionable" if it can be written as a disjoint union of <math>d</math>-dimensional combinatorial subspaces, along with a single "error" set <math>E</math> satisfying <math>\nu(E)/\nu(A) \leq \gamma</math>.

	:'''~~Theorem~~ 5:''' Let A \subseteq [3]^n be an <math>ij</math>~~XXX~~-insensitive set with ν-density at least δ, ~~and~~ let d \geq 1. Assume that n \geq ~~n_4~~(\delta,d) = ~~n_3(\delta~~/~~2,d)~~. Then ~~a random d-dimensional subspace drawn from \nu^n_{3+d}~~ is ~~in A with probability at least \eta_4~~(\~~delta~~, d) ~~= \delta~~/~~(O(d))^{n_4(\delta,d)}~~		:'''Lemma 5:''' Let A \subseteq [3]^n be an <math>ij</math>-insensitive set with <math>\nu</math>-density at least <math>\delta</math>, let <math>d \geq 1</math>, and let <math>\gamma \in (0,1)</math> be a parameter. Assume that <math>n \geq n_5(\delta,\gamma,d) = XXX</math>. Then <math>A</math> is <math>(\gamma,d)</math>-subspace partitionable.

	This is currently written fairly thoroughly [[A_general_partitioning_principle\|here]], ~~though some of~~ the ~~details of~~ the ~~density/probability calculations are sketched~~.		This is currently written fairly thoroughly [[A_general_partitioning_principle\|here]], although the parameters need to be worked out to fill in the "XXX" in the statement.

	===6. Intersections of <math>ij</math>-insensitive sets are subspace partitionable===		===6. Intersections of <math>ij</math>-insensitive sets are subspace partitionable===