View source for A second Fourier decomposition related to Sperner's theorem

==Introduction==

It seems as though it should be possible to give a clean "purely Fourier" proof of Sperner's theorem that exploits positivity, if one uses [[equal-slices measure]]. Here we present a Fourier decomposition that should achieve this, but we have not yet managed to prove the positivity (which could turn out to be a hard problem---at this stage it is not clear).

We use Ryan's formulation of equal-slices measure on <math>[2]^n</math>: the density of a set <math>\mathcal{A}</math> is <math>\mathbb{E}_p\mu_p(\mathcal{A}),</math> where <math>\mu_p</math> is the standard p-weighted measure on the cube: if A is a subset of [n] then <math>\mu_p(A)=p^{|A|}(1-p)^{n-|A|}.</math> A useful way of thinking about <math>\mu_p</math> is that <math>\mu_p(\mathcal{A})</math> is the probability that <math>(X_1,\dots,X_n)\in\mathcal{A}</math> if the <math>X_i</math> are independent Bernoulli random variables with probability p of equalling 1. 

We also need to define a measure on the space of all [[combinatorial_line|combinatorial lines]]. The natural measure seems to be this. Define two sequences <math>(X_1,\dots,X_n)</math> and <math>(Y_1,\dots,Y_n)</math> of Bernoulli random variables as follows. The joint distribution of <math>(X_i,Y_i)</math> is that it equals (0,0),(0,1) and (1,1) with probabilities 1-q,q-p and p, respectively, and let different pairs  
<math>(X_i,Y_i)</math> be independent. Then the <math>X_i</math> are independent Bernoulli, as are the <math>Y_i,</math> but they depend on each other in a way that guarantees that they form a combinatorial line. 

We shall now be interested in the quantity <math>\mathbb{E}f(X)f(Y),</math> where <math>f</math> is some function and <math>X=(X_1,\dots,X_n), Y=(Y_1,\dots,Y_n).</math> But ultimately what will interest us is the average of this quantity over all pairs <math>0\leq p\leq q\leq 1,</math> which we can write as <math>\mathbb{E}_{p\leq q}\mathbb{E}f(X_{p,q})f(Y_{p,q}).</math>

==A proof in physical space==

Let us first prove positivity in physical space. To do this, we shall define the following equivalent model for the joint distribution of <math>X_{p,q}</math> and <math>Y_{p,q}.</math> We first pick a random variable <math>T=(t_1,\dots,t_n)</math> uniformly from <math>[0,1]^n,</math> and then we let <math>(X_{p,q})_i</math> be <math>0</math> if <math>p\leq t_i</math> and <math>1</math> if <math>p>t_i.</math> Similarly, we let <math>Y_{p,q}</math> be 0 if <math>q\leq t_i</math> and 1 if <math>q>t_i.</math> This gives us the nice property that it makes perfectly good sense even if <math>p>q,</math> and we therefore have the equation <math>\mathbb{E}_{p\leq q}\mathbb{E}f(X_{p,q})f(Y_{p,q})=\mathbb{E}_{t\in T}\mathbb{E}_{p,q}f(X_{p,q})f(Y_{p,q}).</math>

Now <math>X_{p,q}</math> is just a function of p and t, and <math>Y_{p,q}</math> is the same function applied to q and t. Therefore, it makes sense to change our notation. Let <math>(X_{p,t})_i=0</math> if <math>p\leq t</math> and 1 if <math>p>t.</math> Then the right-hand side can be rewritten as <math>\mathbb{E}_{t\in T}\mathbb{E}_{p,q}f(X_{p,t})f(X_{q,t}).</math> Therefore, it is equal to <math>\mathbb{E}_{t\in T}(\mathbb{E}_pf(X_{p,t}))^2,</math> which is positive. 

We can say more. By Cauchy-Schwarz, the expectation is at least <math>(\mathbb{E}_{t\in T}\mathbb{E}_pf(X_{p,t}))^2,</math> which is the square of the equal-slices integral of f. In particular, if f is the characteristic function of a set <math>\mathcal{A},</math> then the combinatorial-line density is at least the square of the density of <math>\mathcal{A}.</math>

==Equal-slices Fourier analysis==

===The equal-slices Fourier transform===

Recall that the [http://en.wikipedia.org/wiki/Walsh_function Walsh functions] on the set <math>[2]^n</math> are defined as follows. For each subset <math>A\subset[n]</math> we define <math>w_A(B)</math> to be <math>(-1)^{|A\cap B|}.</math> They can also be conveniently defined in sequence terms: for each A and each <math>x\in\{0,1\}^n</math> we define <math>w_A(x)=\prod_{i\in A}(-1)^{x_i}.</math>

It can easily be checked that the Walsh functions form an orthonormal basis of the <math>2^n</math>-dimensional Euclidean space of all functions from <math>\{0,1\}^n</math> to <math>\mathbb{R},</math> if we take as our inner product the expression  <math>\langle f,g\rangle =\mathbb{E}_xf(x)g(x).</math> However, we shall not always be taking the uniform measure on <math>\{0,1\}^n.</math> If we take the measure <math>\mu_p,</math> then the natural inner product is <math>\langle f,g\rangle_p=\sum_x\mu_p(x)f(x)g(x),</math> which we shall write as <math>\mathbb{E}_pf(x)g(x).</math> (This can be read as the expectation of <math>f(x)g(x)</math> if the coordinates of x are independent Bernoulli variables with mean p.) 

With respect to this inner product, the Walsh functions are no longer orthonormal, but we can define very similar functions that are orthonormal, as follows. First, choose numbers  <math>a_p</math> and <math>b_p</math> such that <math>(1-p)a_p+pb_p=0,</math> <math>(1-p)a_p^2+pb_p^2=1,</math> and <math>a_p\geq 0.</math> This turns out to imply that <math>a_p=(p/(1-p))^{1/2}</math> and <math>b_p=-((1-p)/p)^{1/2},</math> though for now it is the equations they satisfy that we really care about. Next, define <math>w_{i,p}(x)</math> to be <math>a_p</math> if <math>x_i=0</math> and <math>b_p</math> if <math>x_i=1.</math> Finally, define <math>w_{A,p}(x)</math> to be <math>\prod_{i\in A}w_{i,p}(x).</math> Note that if <math>p=1/2,</math> then <math>a_p=1, b_p=-1, w_{i,p}(x)=(-1)^{x_i}</math> and <math>w_{A,p}(x)=w_A(x).</math> 

We now define the p-''Fourier transform'' of a function f to be the function <math>\hat{f}_p</math> given by the formula <math>\hat{f}_p(A)=\langle f,w_{A,p}\rangle.</math> We then define the ''equal-slices Fourier coefficient'' of f at A to be the function <math>p\mapsto\hat{f}_p(A).</math> This is unlike a normal Fourier coefficient in that its value is a function rather than a real number, but this turns out to be surprisingly unproblematic for many purposes.

===An inversion formula===

Obviously one can recover f from its equal-slices Fourier coefficients, since one can recover f from its Walsh coefficients, or indeed its p-Walsh coefficients for any p other than 0 or 1. However, it is more natural to average the results. In other words, since for each p we know that <math>f(x)=\sum_A\hat{f}_p(A)w_{A,p}(x),</math> we obtain the formula <math>f=\mathbb{E}_{p\in[0,1]}\sum_A\hat{f}_p(A)w_{A,p}.</math> Reversing the order of summation/integration, we can also split up according to the contribution from each set A, obtaining the formula <math>f=\sum_A\int_0^1\hat{f}_p(A)w_{A,p}dp.</math>

===A Parseval identity===

Next, let us prove a Parseval identity. First, we define the ''equal-slices inner product'' of f and g to be <math>\mathbb{E}_{p\in[0,1]}\langle f,g\rangle_p.</math> It is easy to see that this is indeed an inner product. More generally, if <math>f_p</math> and <math>g_p</math> are functions that depend on p, then we define the equal-slices inner product to be <math>\mathbb{E}_{p\in[0,1]}\langle f_p,g_p\rangle_p.</math> Let us now calculate the equal-slices inner product of <math>w_{A,p}</math> and <math>w_{B,p}.</math> 

This, like the inversion formula, follows trivially from the corresponding facts for fixed p, which is an easy exercise, but we will do it anyway, just to get used to the kinds of arguments used later. That is, we shall prove that for fixed p the functions <math>w_{A,p}</math> form an orthonormal basis with respect to the measure <math>\mu_p.</math> To do this, let <math>x</math> be chosen randomly according to this measure and recall that <math>w_{A,p}(x)=\prod_{i\in A}w_{i,p}(x),</math>, and similarly for <math>w_{B,p}(x)</math>. Therefore, <math>w_{A,p}(x)w_{B,p}(x)</math> is a product of independent random variables, each of which is either 1, <math>w_{i,p}(x)</math> or <math>w_{i,p}(x)^2,</math> according as i belongs to zero, one or two of the sets A and B. Since the expectation of a product of independent random variables equals the product of the expectations, and the expectation of <math>w_{i,p}(x)</math> is zero (this is the true meaning of the condition <math>(1-p)a_p+pb_p=0</math>), the entire expectation is zero unless A=B. And since the expectation of <math>w_{i,p}(x)^2</math> is 1 (this is the meaning of the condition <math>(1-p)a_p^2+pb_p^2=1</math>), the entire expectation is 1 when A=B.

This proves that <math>\langle w_{A,p},w_{B,p}\rangle=\delta_{AB},</math> from which it follows that <math>\mathbb{E}_{p\in[0,1]}\langle w_{A,p},w_{B,p}\rangle_p=\delta_{AB}.</math>

If we now use the inversion formula to write <math>f=\sum_A\hat{f}_pw_{A,p}</math> and <math>g=\sum_B\hat{g}_pw_{B,p},</math> then we find that <math>\langle f,g\rangle_p=\sum_{A,B}\delta_{A,B}\hat{f}_p(A)\hat{g}_p(B)=\sum_A\hat{f}_p(A)\hat{g}_p(A).</math> Therefore, the equal-slices inner product of f and g is equal to <math>\sum_A\int_0^1\hat{f}_p(A)\hat{g}_p(A)dp.</math> In particular, if f=g then we find that the square of the equal-slices <math>L_2</math>-norm of f is equal to <math>\sum_A\int_0^1\hat{f}_p(A)^2dp.</math>

==A Fourier expression for the density of subset pairs==

We would now like to examine the quantity <math>\mathbb{E}_{t\in T}\mathbb{E}_{p,q}f(X_{p,t})f(X_{q,t})</math> on the Fourier side. To do this, we write <math>f(X_{p,t})</math> as <math>\sum_A\hat{f}_p(A)w_{A,p}(X_{p,t})</math> and we write <math>f(X_{q,t})</math> as <math>\sum_B\hat{f}_q(B)w_{B,q}(X_{q,t}).</math> So for each fixed p and q our problem reduces to calculating <math>\mathbb{E}_{t\in T}w_{A,p}(X_{p,t})w_{B,q}(X_{q,t}).</math> 

This calculation is very similar to the calculations in the proof of Parseval's identity. The random variable <math>w_{A,p}(X_{p,t})w_{B,q}(X_{q,t})</math> splits up as a product of functions of the various <math>t_i,</math> which are independent. If i belongs to A but not to B, then the expectation of <math>w_{i,p}(X_{p,t})w_{i,q}(X_{q,t})</math> is the expectation of <math>w_{i,p}(X_{p,t}),</math> which is zero. So the contribution from pairs (A,B) with <math>A\ne B</math> is zero. If A=B then we need to calculate the expectation <math>\lambda_{p,q}</math> of <math>w_{i,p}(X_{p,t})w_{i,q}(X_{q,t}).</math> 

This depends on which of p and q is larger. If <math>p<q</math>, then we get <math>a_pa_q</math> with probability 1-q, <math>a_pb_q</math> with probability q-p, and <math>b_pb_q</math> with probability p. This gives an expectation of <math>(1-q)(\frac{p}{1-p})^{1/2}(\frac{q}{1-q})^{1/2}-(q-p)(\frac{p}{1-p})^{1/2}(\frac{1-q}{q})^{1/2}+p(\frac{1-p}{p})^{1/2}(\frac{1-q}{q})^{1/2},</math> which works out to be <math>(\frac{p}{1-p})^{1/2}(\frac{1-q}{q})^{1/2}.</math> By symmetry, if <math>p\geq q</math> then <math>\lambda_{p,q}=(\frac{1-p}{p})^{1/2}(\frac{q}{1-q})^{1/2}.</math> Therefore, if A=B, then the expectation of <math>w_{A,p}(X_{p,t})w_{B,q}(X_{q,t})</math> is <math>\lambda_{p,q}^{|A|},</math> byt the independence of the <math>t_i.</math>

Putting all this together, we obtain the formula <math>\mathbb{E}_{t\in T}\mathbb{E}_{p,q}f(X_{p,t})f(X_{q,t})</math><math>=\mathbb{E}_{p,q}\sum_A\lambda_{p,q}^{|A|}\hat{f}_p(A)\hat{f}_q(A).</math> This is the Fourier translation we were seeking.

==Positivity==

It would be very nice to be able to see easily that this Fourier expression is positive. As a first step in that direction, let us change the order of summation/integration and write it as <math>\sum_A\lambda_{p,q}^{|A|}\mathbb{E}_{p,q}\hat{f}_p(A)\hat{f}_q(A).</math> In an ideal world, one might hope that every term in this sum was positive. That would follow if we knew that for each k the "continuous matrix" <math>(\lambda_{p,q}^k)_{p,q=0}^1</math> was positive definite. And in fact it is, though at the moment the only proof I have takes an inverse Fourier transform and so doesn't count as a proper Fourier proof.

Here is a sketch of the argument anyway. Consider the expression <math>\mathbb{E}_{p,q}\lambda_{p,q}^{|A|}F(p)F(q).</math> For each p we can form the function <math>F(p)w_{A,p}</math> and call it <math>f_p.</math> Then <math>\mathbb{E}_{p,q}\lambda_{p,q}^{|A|}F(p)F(q)</math> is equal to <math>\mathbb{E}_{t\in T}\mathbb{E}_{p,q}f_p(X_{p,t})f_q(X_{q,t}),</math> which equals <math>\mathbb{E}_{t\in T}(\mathbb{E}_pf_p(X_{p,t}))^2,</math> which is non-negative. (This last statement can be thought of as a generalized Sperner theorem where your function is allowed to vary as p varies.)