# Representation of the diagonal

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

For all $C \gt 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 $P_i$ and $Q_i$ is the characteristic function of a HAP.

## Proof of implication

Suppose $D$ is a diagonal matrix with entries $b_j$ on the diagonal, with $\sum_j b_j$ unbounded, and $D = \sum_i \lambda_i P_i \otimes Q_i$ where $\sum_i | \lambda_i | \leq 1$ and the $P_i$ and $Q_i$ 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.