You are using a browser not supported by the Wolfram Cloud
Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.
I understand and wish to continue anyway »
WOLFRAM NOTEBOOK
Discrepancy Conjecture
Discrepancy Conjecture
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.
x={-1,1,1,-1,1,-1,-1,1,1,-1,1,1,-1,1,…}
±1
x
d
k
d=3
k=4
(-1,1,1)
(-1,1,-1)
(-1,1,1)
(-1,1,1)
1,-1,1,1
k
d
In more formal language, the discrepancy .
C=max
k
∑
i=1
x
id
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 .
x
±1
C
n
n
x
C
N
N
±1
C
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 ).
±1
1161
2
d
-1
1
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.