Representation of the diagonal

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

---

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

---

Proof of implication

Suppose [math]\displaystyle{ D }[/math] is a diagonal matrix with entries [math]\displaystyle{ b_j }[/math] on the diagonal, with [math]\displaystyle{ \sum_j b_j }[/math] unbounded, and [math]\displaystyle{ D = \sum_i \lambda_i P_i \otimes Q_i }[/math] where [math]\displaystyle{ \sum_i | \lambda_i | \leq 1 }[/math] and the [math]\displaystyle{ P_i }[/math] and [math]\displaystyle{ Q_i }[/math] are HAPs. Suppose [math]\displaystyle{ x }[/math] is a [math]\displaystyle{ \pm 1 }[/math] sequence with finite discrepancy [math]\displaystyle{ C }[/math]. Then we can write [math]\displaystyle{ | \langle x, Dx \rangle | }[/math] in two ways. On the one hand, [math]\displaystyle{ | \langle x, Dx \rangle | = | \sum_j b_j x_j^2 | = | \sum_j b_j | }[/math], which is unbounded; on the other hand, [math]\displaystyle{ | \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 here that we do not actually need to produce a diagonal matrix [math]\displaystyle{ D }[/math] with unbounded trace. It is enough to produce a matrix [math]\displaystyle{ D }[/math] such that [math]\displaystyle{ \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.

This page contains the LaTeX source code for a write-up of a representation-of-diagonal proof that gives the correct bound.

Numerical results

Moses has published some experimental data here. See this comment (and below it) for an explanation.