Representation of the diagonal - Revision history

Gowers: /* Remarks */

2010-07-03T16:18:33Z

Remarks

← Older revision		Revision as of 09:18, 3 July 2010
Line 15:		Line 15:


	[[Roth's Theorem concerning discrepancy on Arithmetic Progression]] contains a ``representation of ~~the~~ diagonal'' proof in detail.		[[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 ==

OBryant: /* Remarks */

2010-05-16T00:19:24Z

Remarks

← Older revision		Revision as of 17:19, 15 May 2010
Line 13:		Line 13:

	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.		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 the diagonal'' proof in detail.

	== Possible proof strategies ==		== Possible proof strategies ==

Alec: Remark that the matrix need not be diagonal as long as its off-diagonal elements are dominated by its trace.

2010-05-01T09:48:20Z

Remark that the matrix need not be diagonal as long as its off-diagonal elements are dominated by its trace.

← Older revision		Revision as of 02:48, 1 May 2010
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.

	== Possible proof strategies ==		== Possible proof strategies ==

Alec: /* Numerical results */

2010-05-01T09:24:29Z

Numerical results

← Older revision		Revision as of 02:24, 1 May 2010
Line 15:		Line 15:

	== 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.

Alec: We only need the sum of the coefficients to be less than or equal to 1.

2010-05-01T04:32:01Z

We only need the sum of the coefficients to be less than or equal to 1.

← Older revision		Revision as of 21:32, 30 April 2010
Line 3:		Line 3:
	----		----

	For all <math>C > 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 \| = 1</math> and each <math>P_i</math> and <math>Q_i</math> is the characteristic function of a HAP.		For all <math>C > 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 ==		== 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 \| = 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.

	== Possible proof strategies ==		== Possible proof strategies ==

Alec: /* Proof of implication */

2010-04-30T20:23:08Z

Proof of implication

← Older revision		Revision as of 13:23, 30 April 2010
Line 8:		Line 8:

	== 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 \| = 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.

	== Possible proof strategies ==		== Possible proof strategies ==

Alec: New page: 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 ca...

2010-04-30T11:19:02Z

New page: The following conjecture, if true, would imply the Erdos discrepancy conjecture. ---- For all <math>C > 0</math> there exists a diagonal matrix with trace at least <math>C</math> that ca...

New page

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

----

For all <math>C > 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 | = 1</math> and each <math>P_i</math> and <math>Q_i</math> is the characteristic function of a HAP.

----

== Proof of implication ==

== Possible proof strategies ==

== Heuristic arguments ==

== Numerical results ==