

A237695


Maximum length of a +/ 1 sequence of discrepancy n.


1




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

Table of n, a(n) for n=0..2.
P. Erdős, Some unsolved problems, Michigan Math. J. 4 (1957), pp. 291300.
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, 20102014+.
James Grime, New Wikipedia sized proof explained with a puzzle (2014)
Erica Klarreich, A magical answer to an 80yearold 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, Computeraided proof of Erdős discrepancy properties, Artificial Intelligence 224 (2015), pp. 103118.
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^(n1).  Charles R Greathouse IV, Mar 03 2014


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

Sequence in context: A177068 A222827 A067105 * A180581 A233012 A019524
Adjacent sequences: A237692 A237693 A237694 * A237696 A237697 A237698


KEYWORD

nonn,bref,hard,more,nice


AUTHOR

Charles R Greathouse IV, Feb 11 2014


STATUS

approved



