OFFSET
0,2
COMMENTS
There is a sequence s_1, s_2, ..., s_a(n) with all terms either 1 or -1 such that abs(s_k + s_2k + ... + s_mk) <= n, but no such sequence with more terms.
The Erdős Discrepancy Conjecture states that a(n) is finite for all n.
Konev & Lisitsa find a(2) = 1160 and a(3) >= 13000. The Polymath5 project had earlier determined that a(2) >= 1124.
Terence Tao solved the Erdős Discrepancy Problem showing that "for any sequence f: N -> {-1,+1} taking values in {-1,+1}, the discrepancy sup_{n,d in N} |Sum_{j=1..n} f(jd)| of f is infinite." (From the abstract of Tao's paper, see the link.) - Peter Luschny, Sep 18 2015
LINKS
P. Erdős, Some unsolved problems, Michigan Math. J. 4 (1957), pp. 291-300.
Timothy Gowers, Erdős and Arithmetic Progressions, arXiv:1509.03421 [math.CO], Sep 11 2015
Timothy Gowers et al., Polymath5: The Erdős discrepancy problem, 2010-2014+.
James Grime, New Wikipedia sized proof explained with a puzzle (2014).
Erica Klarreich, A magical answer to an 80-year-old puzzle, Quanta Magazine, October 2015.
Boris Konev and Alexei Lisitsa, A SAT attack on the Erdős Discrepancy Conjecture, arXiv:1402.2184 [cs.DM], 2014.
Boris Konev and Alexei Lisitsa, Computer-aided proof of Erdős discrepancy properties, arXiv:1405.3097 [cs.DM], 2014; Artificial Intelligence 224 (2015), pp. 103-118.
Terence Tao, The Erdős Discrepancy Problem, arXiv:1509.05363 [math.CO], Sep 2015.
FORMULA
If a(n) exists for some positive n, then a(n) >= 9^(n-1). - Charles R Greathouse IV, Mar 03 2014
a(n) exists for all n (Tao, 2015). - Jeppe Stig Nielsen, Jul 18 2021
EXAMPLE
Writing + for 1 and - for -1, the maximal sequences of maximal discrepancy 1 are +--+-++--+-, +--+-++--++, and their inverses.
PROG
(PARI) mk(n)=apply(k->if(k, 1, -1), binary(n))
ok(n, mx)=my(v=mk(n)); for(k=1, #v\2, my(s); forstep(i=k, #v, k, s+=v[i]; if(abs(s)>mx, return(0)))); 1
a(n)=if(n==0, return(0)); my(k=2^10); while(1, for(i=k+1, 2*k, if(ok(i, n), k=i; next(2))); return(#binary(k)))
CROSSREFS
KEYWORD
nonn,bref,hard,more,nice
AUTHOR
Charles R Greathouse IV, Feb 11 2014
STATUS
approved