Representation of the diagonal

From Polymath Wiki
Jump to: navigation, search

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

For all [math]C \gt 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.


Moses pointed out 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.

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 here. See this comment (and below it) for an explanation.