# Furstenberg-Katznelson argument

This proof of DHJ(3) is being pursued in our reading seminar. Below is an ongoing "combinatorial" translation of the argument. [Very informal!]

We write $[3] = \{0,1,2\}$ for our alphabet. We let $Lines(n)$ be the space of all combinatorial lines $\ell: [3] \to [3]^n$ with "few" wildcards, where we will be vague about what "few" means. We also have $Planes(n)$, the space of combinatorial planes $\pi: [3]^2 \to [3]^n$, and $Spaces(n)$, the space of combinatorial 3-spaces $\sigma: [3]^3 \to [3]^n$. Note that one can think of a combinatorial plane in $[3]^n$ as a combinatorial line in Lines(n), etc.

DHJ(3) is then the claim that if $f: [3]^n \to [0,1]$ has large mean, then

${\Bbb E} f(\ell(0)) f(\ell(1)) f(\ell(2))$ is large,

where $\ell$ ranges over Lines(n).

## 12-low influence

We say that a function $f: [3]^n \to [-1,1]$ is 12-low influence if

${\Bbb E} |f(x)-f(y)|^2$ is small,

where x is drawn uniformly from $[3]^n$ and y is formed from x by randomly flipping a 1 to a 2 or vice versa. Equivalently, f is 12-low influence if

${\Bbb E} |f(\ell(1)) - f(\ell(2))|^2$ is small,

where $\ell$ is drawn randomly from Lines(n).

The following claim is, technically, not true, but is a useful first approximation to the truth:

Lemma 1 (A lie) Let $f: [3]^n \to [-1,1]$. Then the function $F(x) := {\Bbb E}_{\ell: \ell(1)=x} f(\ell(2))$ has 12-low influence, as does the function $G(x) := {\Bbb E}_{\ell: \ell(2) = x} f(\ell(1))$.

Let us say that a function $f: [3]^n \to [-1,1]$ is 12-uniform if ${\Bbb E} g(\ell(1)) f(\ell(2))$ is small for all $g: [3]^n \to [-1,1]$, where $\ell$ 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-low influence on functions on Lines(n) rather than $[3]^n$, where now $\ell$ 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

We can define 01-uniformity in exact analogy to 12-uniformity; a function f is 01-uniform if ${\Bbb E} g(\ell(0)) f(\ell(1))$ is small for all $g: [3]^n \to [-1,1]$. We need a more sophisticated notion (analogous to $U^2({\Bbb Z}/N{\Bbb Z})$ Gowers uniformity): a function f is 01-uniform relative to 12-low influence if ${\Bbb E} g(\ell(0)) f(\ell(1)) h(\ell)$ is small for all $g: [3]^n \to [-1,1]$ and all 12-low influence $h: Lines(n) \to [-1,1]$.

Example Random functions are 01-uniform relative to 12-low influence.

Lemma 2 (von Neumann theorem) If $f: [3]^n \to [-1,1]$ is 01-uniform relative to 12-low influence and $g, h: [3]^n \to [-1,1]$, then ${\Bbb E} h(\ell(0)) f(\ell(1)) g(\ell(2))$ is small.

Proof: An "IP van der Corput lemma" allows one to ensure that ${\Bbb E} h(\ell(0)) f(\ell(1)) g(\ell(2))$ is small if we can show that

${\Bbb E} f(\pi(01)) g(\pi(02)) f(\pi(11)) g(\pi(22))$ (1)

is small, where $\pi$ ranges over Planes(n). (Rough sketch of proof: we can rearrange ${\Bbb E} h(\ell(0)) f(\ell(1)) g(\ell(2))$ as

${\Bbb E}_{\phi,i} h(\phi(0^r)) f(\phi(1^i 0^{r-i})) g(2^i 0^{r-i})$

where r is a medium size number, $\phi: [3]^r \to [3]^n$ ranges over r-dimensional subspaces with few wildcards, and i ranges from 1 to r. Using Cauchy-Schwarz in i, we reduce to bounding

${\Bbb E}_{\phi,i,j} f(\phi(1^i 0^{r-i})) g(2^i 0^{r-i}) f(\phi(1^j 0^{r-j})) g(2^j 0^{r-j})$

which can be rearranged to give (1)).

We can rearrange (1) further as

${\Bbb E} F(\pi(1)) G(\pi(2))$

where $\pi(1), \pi(2)$ are thought of as lines and $F(\ell) := f(\ell(0)) f(\ell(1))$ and $G(\ell) := g(\ell(0)) g(\ell(2))$. But by Lemma 1, we can rewrite this as

${\Bbb E} F(\ell) \overline{G}(\ell)$

where $\overline{G}$ is 12-low influence. But as f is 01-uniform relative to 12-low influence, this expression is small. $\Box$

Thus, when dealing with expressions of the form

${\Bbb E} h(\ell(0)) f(\ell(1)) g(\ell(2))$,

functions which are 01-uniform relative to 12-low influence can be discarded from the second factor. For similar reasons, functions which are 20-uniform relative to 12-low influence (defined in the obvious manner) can be discarded from the third factor).

## Obstructions to uniformity

To continue, we need to understand what the obstructions are to 01-uniformity relative to 12-low influence. The answer turns out to be 01-almost periodicity relative to 12-low influence. Roughly speaking, a function f is 01-periodic relative to 12-low influence if any shift from 0s to 1s distorts f in a manner which can be described by 12-low influence functions. More precisely, there exists a bounded number of functions $g_h: [3]^n \to [-1,1]$ and 12-low influence functions $c_h: Lines(n) \to [-1,1]$ for $h = 1,\ldots,H$ such that the equation

$f(\ell(1)) = {\Bbb E}_h c_h(\ell) g_h(\ell(0))$

is approximately true for most lines $\ell$ in Lines(n).

Example 1 If f is 01-low influence, then $f(\ell(1)) \approx f(\ell(0))$, so f is certainly 01-almost periodic relative to 12-low influence.

Example 2 Let $f(x) \in \{-1,+1\}$ be the parity of the number of 1s in x, then $f(\ell(1)) = c(\ell) f(\ell(0))$ where $c(\ell)$ depends only on the number of wildcards in $\ell$, and is in particular 12-low influence. Thus this function is also 01-almost periodic relative to 12-low influence.

Example 3 If $f: [3]^n \to [-1,1]$ is 12-low influence, then trivially $f(\ell(1)) = c(\ell)$ where $c(\ell) := f(\ell(1))$. Since c is 12-low influence, we conclude that f is 01-almost periodic relative to 12-low influence.

Example 4 Any bounded linear combination of 01-almost periodic functions relative to 12-low influence is also 01-almost periodic relative to 12-low influence; also, any product of 01-almost periodic functions relative to 12-low influence is also 01-almost periodic relative to 12-low influence.

These almost periodic functions obstruct uniformity:

Lemma 2: If $f: [3]^n \to [-1,1]$ is 01-uniform relative to 12-low influence, and $g: [3]^n \to [-1,1]$ is 01-almost periodic relative to 12-low influence, then f and g have small inner product.

Proof: The inner product of f and g can be expressed as

${\Bbb E} f(\ell(1)) g(\ell(1))$

where $\ell$ ranges over Lines(n). On the other hand, from the almost periodicity of g we can write

$g(\ell(1)) = {\Bbb E}_h c_h(\ell) G_h(\ell(0))$

for some 12-low influence $c_h$ and some bounded $G_h$. So we can reexpress the inner product as

${\Bbb E}_h {\Bbb E} f(\ell(1)) G_h(\ell(0)) c_h(\ell).$

But as f is 01-uniform relative to 12-low influence, the inner expectation is small, and the claim follows. $\Box$

Conversely, these are the only obstructions to uniformity:

Lemma 3: If $f: [3]^n \to [-1,1]$ is not 01-uniform relative to 12-low influence, then there exists a $g: [3]^n \to [-1,1]$ is 01-almost periodic relative to 12-low influence, such that f and g have large inner product.

Proof: By hypothesis, we can find a 12-low influence c and a bounded G such that

${\Bbb E} f(\ell(1)) G(\ell(0)) c(\ell)$

is large. We then take

$g(x) := {\Bbb E}_{\ell: \ell(1) = x} G(\ell(0)) c(\ell)$.

Clearly f correlates with g.

If the expression inside the expectation was constant, then we would have

$g(\ell(1)) = G(\ell(0)) c(\ell)$

and g would be 01-almost periodic relative to 12-low influence. Of course, the expression here is not necessarily constant, but if it oscillates too much, then g would be very small and the claim would be easy. I think we can use some sort of statistical sampling argument to handle the general case (I did this in my finitisation of Furstenberg's proof of Szemeredi's theorem); I'll come back to this point later. $\Box$

In view of this lemma, I believe we have

Corollary 4: Any function $f: [3]^n \to [0,1]$ can be decomposed into a function $f_{01}: [3]^n \to [0,1]$ with the same mean as f which is 01-almost periodic relative to 12-low influence, plus an error $f-f_{01}$ which is 01-uniform relative to 12-low influence.

We have a similar decomposition $f = f_{20} + (f-f_{20})$ into a function $f_{20}: [3]^n \to [0,1]$ with the same mean as f which is 20-almost periodic relative to 12-low influence, plus an error $f-f_{20}$ which is 01-uniform relative to 12-low influence. Using the von Neumann theorem, we can thus replace

${\Bbb E} f(\ell(0)) f(\ell(1)) f(\ell(2))$

by

${\Bbb E} f(\ell(0)) f_{01}(\ell(1)) f_{20}(\ell(2))$. (2)

## Conclusion of proof

Let $f_{12}$ be the 12-low influence component of f, then $f_{12}$ is non-negative, has large density, and correlates with f. If we then let E be the set where $f_{12}$ is large, then E is also 12-low influence, and f is large on E.

By DHJ(2.5), the 12-low influence set E contains large combinatorial subspaces. Passing to such a subspace, we may assume that E is everything, i.e. $f_{12}$ is large everywhere. To put it another way, this implies that f has large density inside any 12-low influence set.

Having done this, we now perform the reductions in the previous section to get to the expression (2). From the almost periodicity of $f_{01}, f_{20}$, we have

$f_{01}(\ell(1)) = {\Bbb E}_h c_h(\ell) g_{01,h}(\ell(0))$ (3)

where $c_h$ is 12-low influence, and similarly

$f_{20}(\ell(2)) = {\Bbb E}_h c'_h(\ell) g_{20,h}(\ell(0))$ (4)

where $c'_h$ is 12-low influence.

Direct substitution of (3) and (4) into (2) does not quite work; we have to do something a bit sneakier. Let r be a medium size number and consider an r-dimensional subspace $\phi: [3]^r \to [3]^n$. By the Graham-Rothschild theorem, if r is large enough, one can find a three-dimensional subspace $\sigma: [3]^3 \to [3]^n$ of $\phi$ on which $c_h, c'_h$ are essentially constant. Call such a subspace monochromatic; thus the collection of monochromatic 3-dimensional subspaces has positive density in Spaces(n). Furthermore, since this collection is defined using the 12-low influence functions $c_h, c'_h$, the collection of 3-dimensional monochromatic spaces is itself 12-low influence.

We now rewrite (2) as

${\Bbb E} f(\sigma(012)) f_{01}(\sigma(112)) f_{20}(\sigma(212))$

where $\sigma$ ranges over Spaces(n).

Suppose that $\sigma$ is monochromatic. Then from (3) we have

$f_{01}(\sigma(112)) = {\Bbb E}_h c_h(\sigma(**2)) g_{01,h}(\sigma(002))$

and

$f_{01}(\sigma(012)) = {\Bbb E}_h c_h(\sigma(0*2)) g_{01,h}(\sigma(002))$

and hence by monochromaticity

$f_{01}(\sigma(112)) = f_{01}(\sigma(012))$

and similarly

$f_{20}(\sigma(212)) = f_{20}(\sigma(012))$.

Thus we can bound (2) from below by

${\Bbb E} 1_{mono}(\sigma) [f f_{01} f_{20}](\sigma(012))$

where $1_{mono}$ is the indicator function on the class of monochromatic spaces.

Now, we claim that $f_{01}$ is large on almost all of the support of f. Indeed, if there was a large set in the support of f on which $f_{01}$ was small, then denoting f' by the restriction of f to that set, ${\Bbb E} f'$ would be large but ${\Bbb E} f' f_{01}$ would be small. But if $f'_{01}$ denotes the component of f' which is 01-almost periodic relative to 12-low influence, then $f'_{01}$ is dominated by $f_{01}$ (since f' is dominated by f), and so ${\Bbb E} f' f'_{01}$ would be small. But by orthogonality of f' and $f'-f'_{01}$, this is equal to ${\Bbb E} (f'_{01})^2$. Since $f'_{01}$ has the same mean as f', which is large, this is a contradiction. Thus $f_{01}$ is large on almost all the support of f, and similarly for $f_{20}$. Thus we can bound (2) from below by some multiple of

${\Bbb E} 1_{mono}(\sigma) 1_{supp(f)}(\sigma(012))$.

But because f has positive density inside any 12-low influence set, this expression is large, and we are done.