Fourier-analytic proof of Sperner
We identify 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
and the inversion formula
- . (2)
For any scale 1 < r < n, we consider the bilinear form
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 Br(1A,1A) 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 Br.
We also define the influence Inf(f) as
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
where g ranges over all functions . Functions which are small in the uniform norm are thus "negligible" for the purposes of computing Br 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 U2 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.)
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
- where take values in [-1,1],
- Furthermore, is non-negative and
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 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 / ri + 1) that fU 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).
Now we prove DHJ(2). Let f = 1A 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 fU is uniform at some scale ri and is low-influence at a coarser scale ri + 1.
We then look at . Decomposing into four pieces and using the uniformity of fU, 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 / ri + 1) on the average. Iterating this ri times, we see that . But has density δ, and so the main term is at least δ2. Choosing η small enough and the ri widely separated enough we obtain a nontrivial lower bound on , which gives DHJ(2).