A second Fourier decomposition related to Sperner's theorem

From Polymath1Wiki
Revision as of 04:50, 26 February 2009 by (Talk)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


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 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). 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 \ltmath\gt\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\gtt_i.[/math] Similarly, we let [math]Y_{p,q}[/math] be 0 if [math]q\leq t_i[/math] and 1 if [math]q\gtt_i.[/math] This gives us the nice property that it makes perfectly good sense even if [math]p\gtq,[/math] and we therefore have the equation [math]\mathbb{E}_{p\leq q}\mathbb{E}f(X_{p,q})f(Y_{p,q})=(1/2)\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, the right-hand side is equal to [math]\mathbb{E}_{t\in T}(\mathbb{E}_pf(X_{p,q}))^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,q}))^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]

A Fourier translation of the problem

To be continued.