# Representation of the diagonal

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

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

## Proof of implication

Suppose D is a diagonal matrix with entries bj on the diagonal, with

 ∑ bj j

unbounded, and $D = \sum_i \lambda_i P_i \otimes Q_i$ where $\sum_i | \lambda_i | \leq 1$ and the Pi and Qi are HAPs. Suppose x is a $\pm 1$ sequence with finite discrepancy C. Then we can write $| \langle x, Dx \rangle |$ in two ways. On the one hand, $| \langle x, Dx \rangle | = | \sum_j b_j x_j^2 | = | \sum_j b_j |$, which is unbounded; on the other hand, $| \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$, a contradiction.

## Remarks

Moses pointed out here that we do not actually need to produce a diagonal matrix D with unbounded trace. It is enough to produce a matrix D such that $\sum_i d_{ii} - \sum_{i \neq j} | d_{ij} |$ 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.