Archive for September 6th, 2010

EDP19 — removing some vagueness

September 6, 2010

In the comments on EDP18 we are considering a certain decomposition problem that can be understood in its own right. At various points I have asserted that if we can find a decomposition of a particular kind then we will have a positive solution to EDP. And at various points in the past I have even sketched proofs of this. But I think it would be a good idea to do more than merely sketch a proof. So in this post I shall (I hope) give a completely rigorous derivation of EDP from the existence of an appropriate decomposition. (Well, I may be slightly sketchy in places, but only about details where it is obvious that they can be made precise.) I shall also review some material from earlier posts and comments, rather than giving links.

Representing diagonal matrices

First, let me briefly look again at how the ROD (representation of diagonal) approach works. If P and Q are HAPs, I shall write P\otimes Q for the matrix A such that A_{xy}=1 if (x,y)\in P\times Q and 0 otherwise. The main thing we need to know about P\times Q is that \langle x,(P\otimes Q)x\rangle=(\sum_{i\in P}x_i)(\sum_{j\in Q}x_j) for every x.

Suppose now that D is a diagonal matrix with diagonal entries d_1,\dots,d_n and that we can write it as \sum_r\lambda_rP_r\otimes Q_r, where each P_r and each Q_r is a HAP. Then

\sum_r\lambda_r(\sum_{i\in P_r}x_i)(\sum_{j\in Q_r}x_j)=\sum_kd_kx_k^2.

If \sum_r|\lambda_r|=c\sum_kd_k and x_k=\pm 1 for every k, then it follows that there exists r such that

|\sum_{i\in P_r}x_i||\sum_{j\in Q_r}x_j|\geq c^{-1},

and from that it follows that there is a HAP P such that |\sum_{i\in P}x_i|\geq c^{-1/2}. So if we can make c arbitrarily small, then EDP is proved.