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