# Fourier-analytic proof of Sperner

### From Polymath1Wiki

## Contents |

## Fourier analysis

We identify [2]^{n} with the power set 2^{[n]} of [n]. Given any function , we define the Fourier transform by the formula

- ;

we have the Plancherel formula

- (1)

and the inversion formula

- . (2)

For any scale 1 < *r* < *n*, we consider the bilinear form

- (3)

where X is drawn randomly from 2^{[n]}, and Y is formed from X by setting whenever , and when , setting with probability *r* / *n*. To avoid significant distortion in the measure, we will be working in the regime . Note that if *B*_{r}(1_{A},1_{A}) is large, and r is not too small, then A will contain many combinatorial lines (since Y will be strictly larger than X with high probability); thus it is of interest to get lower bounds on *B*_{r}.

We also define the influence Inf(f) as

- (4)

where X' is formed from X by randomly flipping one bit (from 0 to 1, or vice versa). In Fourier space, we have

- . (5)

## Dichotomy between structure and randomness

For any , define the *uniformity norm at scale r* by the formula

- (6)

where g ranges over all functions . Functions which are small in the uniform norm are thus "negligible" for the purposes of computing *B*_{r} and can be discarded. (This is analogous to the theory of counting arithmetic progressions of length three, in which functions with small Fourier coefficients (or small Gowers *U*^{2} norm) can be discarded.)

**Lemma 1**Let be such that , where and η > 0. Then there exists a function of influence such that

It seems that this is more or less proven in Ryan's notes. (May be worth redoing it here on the wiki. Note that the scale r here basically corresponds to ε*n* in Ryan's notes.)

## Structure theorem

Now we use the general "energy increment" argument (see e.g. Terry's paper on this) to obtain a structural theorem.

**Corollary 2**(Koopman-von Neumann type theorem) Let and 0 < η < 1. Then there exists*k*=*k*(η) such that whenever be a sequence of scales. Then there exists and a decomposition- (7)

- where take values in [-1,1],
- (8)

- and
- (9)

- Furthermore, is non-negative and
- (10)

**Proof** (sketch) It's likely that there is now a slick proof of this type of thing using the duality arguments of Gowers or of Reingold-Trevisan-Tulsiani-Vadhan. But here is the "old school" approach from my long AP paper with Ben, running the energy increment algorithm:

- Initialise i=1, and let be the trivial partition of [2]
^{n}. - Let be the conditional expectation of f with respect to the partition; initially, this is just the constant function , but becomes more complicated as the partition gets finer. Set
- If then STOP.
- Otherwise, we apply Lemma 1 to find a function F of influence
*O*_{η}(1 /*r*_{i + 1}) that*f*_{U}correlates with. Partition F into level sets (discretising in multiples of η or so, randomly shifting the cut-points to avoid edge effects) and use this to augment the partition . In doing so, the energy increases by some non-negligible amount*c*(η) > 0, thanks to Pythagoras' theorem: this is why this process will stop before k steps. - Now return to Step 1.

A certain tedious amount of verification is needed to show that all the hypotheses are satisfied. One technical step is that one needs to use the Weierstrass approximation theorem to approximate by a polynomial combination of low-influence functions, and one needs to show that polynomial combinations of low-influence functions are low-influence. The complexity of the polynomial is controlled by some function of η and this explains the losses in that parameter in (8).

## DHJ(2)

Now we prove DHJ(2). Let *f* = 1_{A} have density δ. We let η be a small number depending on δ. Now we pick some scales between 1 and (the exact choices are not so important, so long as the scales are widely separated), and apply the above corollary, to decompose , where *f*_{U} is uniform at some scale *r*_{i} and is low-influence at a coarser scale *r*_{i + 1}.

We then look at . Decomposing into four pieces and using the uniformity of *f*_{U}, this expression is equal to . But the low influence of means that when one randomly flips a bit from a 0 to a 1, changes by *O*_{η}(1 / *r*_{i + 1}) on the average. Iterating this *r*_{i} times, we see that . But has density δ, and so the main term is at least δ^{2}. Choosing η small enough and the *r*_{i} widely separated enough we obtain a nontrivial lower bound on , which gives DHJ(2).