Discrepancy Conjecture

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

In 2015, Terence Tao proved the Erdős discrepancy conjecture [1]. Consider a sequence like , where all the terms are . After that, partition into sections of length , take the first sections, and then total up the last terms in each section. For and , the sections are , , , and ; the final terms are ; and their total is 2. The maximum value obtained by any considered or is the discrepancy.

[more]

In more formal language, the discrepancy .

The discrepancy conjecture states that for any sequence of terms and any positive integer , there exists a positive integer such that the finite sequence of the first terms of have discrepancy or greater. Therefore, there is a minimum such that terms of any sequence has a given discrepancy .

In 2014, Boris Konev and Alexei Lisitsa found a 1160-term sequence with discrepancy 2, and showed that all 1161-term sequences have discrepancy 3 [2]. They showed that all known elegant methods for constructing a sequence of that length fail; but one might yet be discovered by brute forcing through all possible sequences, which isn't possible at the moment. They later found a 130000-term sequence with discrepancy 3 [3]. This Demonstration examines those two sequences by providing a plot of the ongoing total for a given multiplier and then an array that highlights the selected terms in red (for ) or blue (for ).

The proof in [1] is an existence proof, and not a constructive proof. The minimum size sequence for forcing discrepancies 3, 4, and up is still unknown.

[less]

Contributed by: Ed Pegg Jr (October 2015)
Open content licensed under CC BY-NC-SA


Snapshots


Details

References

[1] T. Tao, "The Erdős Discrepancy Problem," 2015. arXiv:1509.05363.

[2] B. Konev and A. Lisitsa, "A SAT Attack on the Erdős Discrepancy Conjecture," in Theory and Applications of Satisfiability Testing—SAT 2014, 8561, 2014 pp. 219–226.

[3] B. Konev and A. Lisitsa, "Computer-Aided Proof of Erdős Discrepancy Properties," Artificial Intelligence, 224, 2015 pp. 103–118. Data.

[4] "The Erdős Discrepancy Problem." Polymath. (Sep 21, 2015) michaelnielsen.org/polymath1/index.php?title=The_Erdős _discrepancy _problem.

[5] Wikipedia. "±1 Sequence." (Sep 30, 2015) en.wikipedia.org/wiki/%C2 % B11-sequence.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send