Furstenberg-Katznelson argument - Revision history

Teorth: /* 12-low influence */

2009-02-25T01:43:50Z

12-low influence

← Older revision		Revision as of 18:43, 24 February 2009
Line 27:		Line 27:
	Let us say that a function <math>f: [3]^n \to [-1,1]</math> is ''12-uniform'' if <math>{\Bbb E} g(\ell(1)) f(\ell(2))</math> is small for all <math>g: [3]^n \to [-1,1]</math>, where <math>\ell</math> is again ranging over Lines(n). Assuming Lemma 1, we see that 12-uniform functions are basically orthogonal to 12-low influence functions. In fact any function can essentially be orthogonally decomposed into 12-uniform and 12-low influence components (see the [[Fourier-analytic proof of Sperner]] for some more discussion).		Let us say that a function <math>f: [3]^n \to [-1,1]</math> is ''12-uniform'' if <math>{\Bbb E} g(\ell(1)) f(\ell(2))</math> is small for all <math>g: [3]^n \to [-1,1]</math>, where <math>\ell</math> is again ranging over Lines(n). Assuming Lemma 1, we see that 12-uniform functions are basically orthogonal to 12-low influence functions. In fact any function can essentially be orthogonally decomposed into 12-uniform and 12-low influence components (see the [[Fourier-analytic proof of Sperner]] for some more discussion).

	We can also define 12-uniformity and 12-influence on functions on Lines(n) rather than <math>[3]^n</math>, where now <math>\ell</math> is ranging over lines in Lines(n) (i.e. in elements of Planes(n)).		We can also define 12-uniformity and 12-low influence on functions on Lines(n) rather than <math>[3]^n</math>, where now <math>\ell</math> is ranging over lines in Lines(n) (i.e. in elements of Planes(n)). Similarly for functions on Planes(n), Spaces(n), etc.

	== 01-uniformity relative to 12-low influence ==		== 01-uniformity relative to 12-low influence ==

Teorth: Major rewrite

2009-02-25T01:17:32Z

Major rewrite

Show changes

193.62.203.214: /* Step 1: Random sampling */ Suppose for contradiction that DHJ(3) _is false_

2009-02-17T23:05:58Z

Step 1: Random sampling: Suppose for contradiction that DHJ(3) _is false_

← Older revision		Revision as of 16:05, 17 February 2009
Line 4:		Line 4:
	== Step 1: Random sampling ==		== Step 1: Random sampling ==

	Suppose for contradiction that [[DHJ(3)]]; then there exists <math>\delta > 0</math>, a sequence of n going to infinity, and a sequence <math>A^{(n)} \subset [3]^n</math> of [[line-free]] sets, all with density at least <math>\delta</math>.		Suppose for contradiction that [[DHJ(3)]] is false; then there exists <math>\delta > 0</math>, a sequence of n going to infinity, and a sequence <math>A^{(n)} \subset [3]^n</math> of [[line-free]] sets, all with density at least <math>\delta</math>.

	For any fixed integer m, and with any n larger than m, we can then form a random line-free subset <math>A^{(n)}_m \subset [3]^m</math> by randomly embedding <math>[3]^m</math> inside <math>[3]^n</math>. More precisely,		For any fixed integer m, and with any n larger than m, we can then form a random line-free subset <math>A^{(n)}_m \subset [3]^m</math> by randomly embedding <math>[3]^m</math> inside <math>[3]^n</math>. More precisely,

Teorth at 22:33, 15 February 2009

2009-02-15T22:33:36Z

@@ Line 49: / Line 49: @@
 In fact, we can now extend this groupoid action not just to words, but to any element w of the free group <math>F_3</math> generated by the alphabet 0,1,2 and the formal inverses <math>0^{-1}, 1^{-1}, 2^{-1}</math>, defining <math>\tilde U_{m+|w|}^w: \tilde X_{m+|w|} \to \tilde X_m</math> using the semigroupoid law (1) and the inversion law
-:<math>(\tilde U_{m+|w|}^w)^{-1} := \tilde U_m^{w^{-1}}</math>.
+:<math>(\tilde U_{m+|w|}^w)^{-1} := \tilde U_m^{w^{-1}}</math>. (2)
 Here we adopt the convention that the inverses <math>0^{-1}, 1^{-1}, 2^{-1}</math> have length -1.  Thus for instance <math>\tilde U_5^{012^{-1}1}: \tilde X_5 \to \tilde X_3</math> is the map
 :<math>\tilde U_5^{012^{-1}1} = \tilde U_4^0 \tilde U_5^1 (\tilde U_4^2)^{-1} \tilde U_5^1</math>.
 == Step 3: To be continued... ==

Teorth: /* Step 2. Inverting the translations */

2009-02-14T19:46:52Z

Step 2. Inverting the translations

← Older revision		Revision as of 12:46, 14 February 2009
Line 31:		Line 31:
	== Step 2. Inverting the translations ==		== Step 2. Inverting the translations ==

	This is all very well and good, but there is one minor technical problem which will cause difficulty in later parts of the argument: the slicing maps <math>U_{m+\|w\|}^w: X_{m+r} \to X_m</math> are not invertible. We would like to (artificially) upgrade them to be invertible (thus upgrading the semigroupoid of transformations <math>U_{m+r}^w</math> to a groupoid). This can be done, but requires extending the measure spaces ~~$latex~~ X_m$ a bit (or in probabilistic language, by adding random number generators).		This is all very well and good, but there is one minor technical problem which will cause difficulty in later parts of the argument: the slicing maps <math>U_{m+\|w\|}^w: X_{m+r} \to X_m</math> are not invertible. We would like to (artificially) upgrade them to be invertible (thus upgrading the semigroupoid of transformations <math>U_{m+r}^w</math> to a groupoid). This can be done, but requires extending the measure spaces <math>X_m</math> a bit (or in probabilistic language, by adding random number generators).

	Let's turn to the details. It suffices to understand what is going on with the hyperplane slicing maps <math>U_{m+1}^i: X_{m+1} \to X_m</math> for <math>i=0,1,2</math>, since the more general maps can be expressed as compositions of these maps by (1). The key lemma is		Let's turn to the details. It suffices to understand what is going on with the hyperplane slicing maps <math>U_{m+1}^i: X_{m+1} \to X_m</math> for <math>i=0,1,2</math>, since the more general maps can be expressed as compositions of these maps by (1). The key lemma is

Teorth: /* Step 2. Inverting the translations */

2009-02-14T19:46:30Z

Step 2. Inverting the translations

← Older revision		Revision as of 12:46, 14 February 2009
Line 54:		Line 54:

	:<math>\tilde U_5^{012^{-1}1} = \tilde U_4^0 \tilde U_5^1 (\tilde U_4^2)^{-1} \tilde U_5^1</math>.		:<math>\tilde U_5^{012^{-1}1} = \tilde U_4^0 \tilde U_5^1 (\tilde U_4^2)^{-1} \tilde U_5^1</math>.
	~~--[[User~~:~~Ryanworldwide\|Ryanworldwide]] 19:44, 14 February 2009 (UTC)~~
			== Step 3: To be continued... ==

Teorth: /* Step 1: Random sampling */

2009-02-14T19:44:24Z

Step 1: Random sampling

← Older revision		Revision as of 12:44, 14 February 2009
Line 9:		Line 9:

	# Pick m distinct positions <math>a_1,\ldots,a_m \in [n]</math> uniformly at random.		# Pick m distinct positions <math>a_1,\ldots,a_m \in [n]</math> uniformly at random.
	# Outside of these m positions, pick a random word x in <math>[3]^{[n] \backslash \{a_1,\ldots,a_m\}</math> uniformly at random.		# Outside of these m positions, pick a random word x in <math>[3]^{[n] \backslash \{a_1,\ldots,a_m\}}</math> uniformly at random.
	# Define the random sampling map <math>\phi_m^{(n)}: [3]^m \to [3]^n</math> by mapping <math>w_1 \ldots w_m</math> to the string that is equal to x outside of the positions <math>a_1,\ldots,a_m</math>, and then setting the position at <math>a_i</math> equal to <math>w_i</math>.		# Define the random sampling map <math>\phi_m^{(n)}: [3]^m \to [3]^n</math> by mapping <math>w_1 \ldots w_m</math> to the string that is equal to x outside of the positions <math>a_1,\ldots,a_m</math>, and then setting the position at <math>a_i</math> equal to <math>w_i</math>.
	# Define <math>A^{(n)}_m := (\phi_m^{(n)})^{-1}(A^{(n)})</math>.		# Define <math>A^{(n)}_m := (\phi_m^{(n)})^{-1}(A^{(n)})</math>.

Ryanworldwide at 19:44, 14 February 2009

2009-02-14T19:44:10Z

← Older revision		Revision as of 12:44, 14 February 2009
Line 35:		Line 35:
	Let's turn to the details. It suffices to understand what is going on with the hyperplane slicing maps <math>U_{m+1}^i: X_{m+1} \to X_m</math> for <math>i=0,1,2</math>, since the more general maps can be expressed as compositions of these maps by (1). The key lemma is		Let's turn to the details. It suffices to understand what is going on with the hyperplane slicing maps <math>U_{m+1}^i: X_{m+1} \to X_m</math> for <math>i=0,1,2</math>, since the more general maps can be expressed as compositions of these maps by (1). The key lemma is

	'''Lemma 1''' Let <math>(X,\mu_X)</math> and <math>(Y,\mu_Y)</math> be finite probability spaces, and let <math>U: X \to Y</math> be a surjective map which is probability-preserving (thus <math>U_* \mu_X = \mu_Y</math>, or equivalently that <math>\mu_X(U^{-1}(E)) = \mu_Y(E)</math> for every <math>E \subset Y). Then one can lift U to an (almost surely) invertible map <math>\tilde U: X \times [0,1] \to Y \times [0,1]</math> on the product probability spaces which forms a commuting square with the projections <math>\pi_X: X \times [0,1] \to X</math>, <math>\pi_Y: Y \times [0,1] \to Y</math>, such that <math>\tilde U, \tilde U^{-1}</math> are measure-preserving.		'''Lemma 1''' Let <math>(X,\mu_X)</math> and <math>(Y,\mu_Y)</math> be finite probability spaces, and let <math>U: X \to Y</math> be a surjective map which is probability-preserving (thus <math>U_* \mu_X = \mu_Y</math>, or equivalently that <math>\mu_X(U^{-1}(E)) = \mu_Y(E)</math> for every <math>E \subset Y</math>). Then one can lift U to an (almost surely) invertible map <math>\tilde U: X \times [0,1] \to Y \times [0,1]</math> on the product probability spaces which forms a commuting square with the projections <math>\pi_X: X \times [0,1] \to X</math>, <math>\pi_Y: Y \times [0,1] \to Y</math>, such that <math>\tilde U, \tilde U^{-1}</math> are measure-preserving.

	'''Proof''': By working one fibre of U at a time, one can reduce to the case when Y is a point (so that U is trivial). Order X as <math>x_1,\ldots,x_k</math>, with probabilities <math>p_1,\ldots,p_k</math>. One can then take		'''Proof''': By working one fibre of U at a time, one can reduce to the case when Y is a point (so that U is trivial). Order X as <math>x_1,\ldots,x_k</math>, with probabilities <math>p_1,\ldots,p_k</math>. One can then take
Line 54:		Line 54:

	:<math>\tilde U_5^{012^{-1}1} = \tilde U_4^0 \tilde U_5^1 (\tilde U_4^2)^{-1} \tilde U_5^1</math>.		:<math>\tilde U_5^{012^{-1}1} = \tilde U_4^0 \tilde U_5^1 (\tilde U_4^2)^{-1} \tilde U_5^1</math>.
			--[[User:Ryanworldwide\|Ryanworldwide]] 19:44, 14 February 2009 (UTC)

Teorth: /* Step 1: Random sampling */

2009-02-14T19:43:44Z

Step 1: Random sampling

← Older revision		Revision as of 12:43, 14 February 2009
Line 9:		Line 9:

	# Pick m distinct positions <math>a_1,\ldots,a_m \in [n]</math> uniformly at random.		# Pick m distinct positions <math>a_1,\ldots,a_m \in [n]</math> uniformly at random.
	# Outside of these m positions, pick a random word x in <math>[3]^{[n] \backslash \{a_1,\ldots,a_m\}}</math> uniformly at random.		# Outside of these m positions, pick a random word x in <math>[3]^{[n] \backslash \{a_1,\ldots,a_m\}</math> uniformly at random.
	# Define the random sampling map <math>\phi_m^{(n)}: [3]^m \to [3]^n</math> by mapping <math>w_1 \ldots w_m</math> to the string that is equal to x outside of the positions <math>a_1,\ldots,a_m</math>, and then setting the position at <math>a_i</math> equal to <math>w_i</math>.		# Define the random sampling map <math>\phi_m^{(n)}: [3]^m \to [3]^n</math> by mapping <math>w_1 \ldots w_m</math> to the string that is equal to x outside of the positions <math>a_1,\ldots,a_m</math>, and then setting the position at <math>a_i</math> equal to <math>w_i</math>.
	# Define <math>A^{(n)}_m := (\phi_m^{(n)})^{-1}(A^{(n)})</math>.		# Define <math>A^{(n)}_m := (\phi_m^{(n)})^{-1}(A^{(n)})</math>.

Ryanworldwide at 19:42, 14 February 2009

2009-02-14T19:42:23Z

← Older revision		Revision as of 12:42, 14 February 2009
Line 10:		Line 10:
	# Pick m distinct positions <math>a_1,\ldots,a_m \in [n]</math> uniformly at random.		# Pick m distinct positions <math>a_1,\ldots,a_m \in [n]</math> uniformly at random.
	# Outside of these m positions, pick a random word x in <math>[3]^{[n] \backslash \{a_1,\ldots,a_m\}}</math> uniformly at random.		# Outside of these m positions, pick a random word x in <math>[3]^{[n] \backslash \{a_1,\ldots,a_m\}}</math> uniformly at random.
	# Define the random sampling map <math>\phi_m^{(n)}: [3]^m \to [3]^n$ by mapping <math>w_1 \ldots w_m</math> to the string that is equal to x outside of the positions <math>a_1,\ldots,a_m</math>, and then setting the position at <math>a_i</math> equal to <math>w_i</math>.		# Define the random sampling map <math>\phi_m^{(n)}: [3]^m \to [3]^n</math> by mapping <math>w_1 \ldots w_m</math> to the string that is equal to x outside of the positions <math>a_1,\ldots,a_m</math>, and then setting the position at <math>a_i</math> equal to <math>w_i</math>.
	# Define <math>A^{(n)}_m := (\phi_m^{(n)})^{-1}(A^{(n)})</math>.		# Define <math>A^{(n)}_m := (\phi_m^{(n)})^{-1}(A^{(n)})</math>.