Representation of the diagonal

From Polymath1Wiki

Jump to: navigation, search

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.

Contents

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.

Possible proof strategies

Heuristic arguments

Numerical results

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

Retrieved from "http://michaelnielsen.org/polymath1/index.php?title=Representation_of_the_diagonal"
Personal tools