Discrepancy assumption

The discrepancy conjecture is a mathematical conjecture established by Paul Erdős and proven by Terence Tao in 2015 .

Clear presentation of the problem

The following illustration is from James Grime :

A person is trapped on a ledge. Two steps to his left is an abyss, two steps to the right is a snake pit. To torture him, an evil guard forced his victim to keep moving left and right. The prisoner has to find a sequence of steps to avoid the dangers on both sides. If he first moves to the right, he must immediately return to the left, otherwise the crash is inevitable.

Going alternately in both directions seems to be the solution - but here's the catch: The prisoner must determine his sequence of steps in advance, and the guard can determine that he only takes every second step, starting with the second. Or he only allows every third, fourth, ... The question is: does a tactic exist to keep the prisoner alive regardless of the strategy his tormentor chooses?

The discrepancy conjecture says that such a tactic does not exist - and not only for , but also for any other distance to the abyss. ${\ displaystyle C = 1}$

Mathematical formulation

For every sequence with for all and for every whole number there are whole numbers and with ${\ displaystyle (x_ {n}) _ {n \ in \ mathbb {N}}}$ ${\ displaystyle x_ {n} \ in \ left \ {+ 1, -1 \ right \}}$ ${\ displaystyle n}$ ${\ displaystyle C}$ ${\ displaystyle k}$ ${\ displaystyle d}$

{\ displaystyle \ left | \ sum _ {i = 1} ^ {k} x_ {d \ cdot i} \ right |> C}

.

History of the problem

Paul Erdös and Terence Tao (1985)

The assumption was made by Erdős around 1932.

In 2010 the question became one of the first Polymath projects .

In 2014 Lisitsa and Konev proved the conjecture for . In this case you can always choose . At 13 gigabytes, your computer proof was the most elaborate proof of mathematics to date. ${\ displaystyle C \ leq 2}$ ${\ displaystyle k <1161}$

In 2015, Tao proved the assumption based on the preliminary work of the Polymath project. His work was published in 2016 as the first article in the newly founded journal Discrete Analysis .

literature

W. Timothy Gowers: Erdős and Arithmetic Progressions . In: László Lovász, Imre Z. Ruzsa, Vera T. Sós (eds.): Erdős Centennial (= Bolyai Society Mathematical Studies . Volume 25 ). Springer, 2013, ISBN 978-3-642-39285-6 , ISSN 1217-4696 , p. 265-287 , doi : 10.1007 / 978-3-642-39286-3 (English).
Boris Konev, Alexei Lisitsa: Computer-Aided Proof of Erdős Discrepancy Properties . In: Artificial Intelligence . tape 224 , 2015, ISSN 0004-3702 , p. 102-118 (English).
Kaisa Matomäki, Maksym Radziwiłł: Multiplicative functions in short intervals . In: Annals of Mathematics . tape 183 , no. 3 , 2016, ISSN 0003-486X , p. 1015-1056 , doi : 10.4007 / annals.2016.183.3.6 , JSTOR : 24735181 (English).
Terence Tao: The Erdős discrepancy problem . In: Discrete Analysis . tape 1 , 2016, ISSN 2397-3129 , doi : 10.19086 / da.609 , arxiv : 1509.05363 (English).

Individual evidence

↑ Erica Klarreich: No rescue from the abyss. In: Spektrum.de . December 16, 2015, accessed March 23, 2020 .
^ Polymath: The Erdős discrepancy problem.
↑ see example 1.7 in Terence Tao: The Erdős discrepancy problem . In: Discrete Analysis . tape 1 , 2016, ISSN 2397-3129 , p. 4 , example 1.7 , doi : 10.19086 / da.609 , arxiv : 1509.05363 (English).

[1] Erica Klarreich: No rescue from the abyss. In: Spektrum.de . December 16, 2015, accessed March 23, 2020 .

[2] Polymath: The Erdős discrepancy problem.

[3] see example 1.7 in Terence Tao: The Erdős discrepancy problem . In: Discrete Analysis . tape 1 , 2016, ISSN 2397-3129 , p. 4 , example 1.7 , doi : 10.19086 / da.609 , arxiv : 1509.05363 (English).