WOLFRAM|DEMONSTRATIONS PROJECT

Discrepancy Conjecture

​
multiplier
20
discrepancy
2
3
In 2015, Terence Tao proved the Erdős discrepancy conjecture [1]. Consider a sequence like
x={-1,1,1,-1,1,-1,-1,1,1,-1,1,1,-1,1,…}
, where all the terms are
±1
. After that, partition
x
into sections of length
d
, take the first
k
sections, and then total up the last terms in each section. For
d=3
and
k=4
, the sections are
(-1,1,1)
,
(-1,1,-1)
,
(-1,1,1)
, and
(-1,1,1)
; the final terms are
1,-1,1,1
; and their total is 2. The maximum value obtained by any considered
k
or
d
is the discrepancy.
In more formal language, the discrepancy
C=max
k
∑
i=1
x
id

.
The discrepancy conjecture states that for any sequence
x
of
±1
terms and any positive integer
C
, there exists a positive integer
n
such that the finite sequence of the first
n
terms of
x
have discrepancy
C
or greater. Therefore, there is a minimum
N
such that
N
terms of any
±1
sequence has a given discrepancy
C
.
In 2014, Boris Konev and Alexei Lisitsa found a 1160-term sequence with discrepancy 2, and showed that all 1161-term
±1
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
1161
2
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
d
and then an array that highlights the selected terms in red (for
-1
) or blue (for
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.