View source for Representation of the diagonal

The following conjecture, if true, would imply the Erdos discrepancy conjecture.

----

For all <math>C > 0</math> there exists a diagonal matrix with trace at least <math>C</math> that can be expressed as <math>\sum_i \lambda_i P_i \otimes Q_i</math>, where <math>\sum_i | \lambda_i | \leq 1</math> and each <math>P_i</math> and <math>Q_i</math> is the characteristic function of a HAP.

----

== Proof of implication ==
Suppose <math>D</math> is a diagonal matrix with entries <math>b_j</math> on the diagonal, with <math>\sum_j b_j</math> unbounded, and <math>D = \sum_i \lambda_i P_i \otimes Q_i</math> where <math>\sum_i | \lambda_i | \leq 1</math> and the <math>P_i</math> and <math>Q_i</math> are HAPs. Suppose <math>x</math> is a <math>\pm 1</math> sequence with finite discrepancy <math>C</math>. Then we can write <math>| \langle x, Dx \rangle |</math> in two ways. On the one hand, <math>| \langle x, Dx \rangle | = | \sum_j b_j x_j^2 | = | \sum_j b_j |</math>, which is unbounded; on the other hand, <math>| \langle x, Dx \rangle | = | \langle x, \sum_i \lambda_i (P_i \otimes Q_i) x \rangle | = | \sum_i \lambda_i \langle x, P_i \rangle \langle x, Q_i \rangle | \leq \sum_i | \lambda_i | | \langle x, P_i \rangle | | \langle x, Q_i \rangle | \leq C^2</math>, a contradiction.

== Remarks ==

Moses pointed out [http://gowers.wordpress.com/2010/03/23/edp13-quick-summary/#comment-6971 here] that we do not actually need to produce a ''diagonal'' matrix <math>D</math> with unbounded trace. It is enough to produce a matrix <math>D</math> such that <math>\sum_i d_{ii} - \sum_{i \neq j} | d_{ij} |</math> is unbounded.


[[Roth's Theorem concerning discrepancy on Arithmetic Progression]] contains a representation-of-diagonal proof in detail.

[[Obtaining the correct bound in Roth's discrepancy theorem|This page]] contains the LaTeX source code for a write-up of a representation-of-diagonal proof that gives the correct bound.

== Possible proof strategies ==

== Heuristic arguments ==

== Numerical results ==
Moses has published some experimental data [http://webspace.princeton.edu/users/moses/EDP/try-lp/ here]. See [http://gowers.wordpress.com/2010/03/07/edp11-the-search-continues/#comment-6668 this comment] (and below it) for an explanation.