Representation of the diagonal: Difference between revisions
m We only need the sum of the coefficients to be less than or equal to 1. |
|||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 9: | Line 9: | ||
== Proof of implication == | == 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. | 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. | ||
== Remarks == | |||
Moses pointed out [http://gowers.wordpress.com/2010/03/23/edp13-quick-summary/#comment-6971 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. | |||
[[Obtaining the correct bound in Roth's discrepancy theorem|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 == | == Possible proof strategies == | ||
| Line 15: | Line 24: | ||
== Numerical results == | == Numerical results == | ||
Moses has published some experimental data [http://webspace.princeton.edu/users/moses/EDP/try-lp/ here]. See [http://gowers.wordpress.com/2010/03/07/edp11-the-search-continues/#comment-6668 this comment] (and below it) for an explanation. | |||
Latest revision as of 08:18, 3 July 2010
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.
Possible proof strategies
Heuristic arguments
Numerical results
Moses has published some experimental data here. See this comment (and below it) for an explanation.
