A237695 - OEIS

%I #53 Sep 07 2023 04:29:23

%S 0,11,1160

%N Maximum length of a +- 1 sequence of discrepancy n.

%C 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.

%C The Erdős Discrepancy Conjecture states that a(n) is finite for all n.

%C Konev & Lisitsa find a(2) = 1160 and a(3) >= 13000. The Polymath5 project had earlier determined that a(2) >= 1124.

%C 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

%H P. Erdős, <a href="http://www.renyi.hu/~p_erdos/1957-13.pdf">Some unsolved problems</a>, Michigan Math. J. 4 (1957), pp. 291-300.

%H Timothy Gowers, <a href="http://arxiv.org/abs/1509.03421">Erdős and Arithmetic Progressions</a>, arXiv:1509.03421 [math.CO], Sep 11 2015

%H Timothy Gowers et al., <a href="http://michaelnielsen.org/polymath1/index.php?title=The_Erd%C5%91s_discrepancy_problem">Polymath5: The Erdős discrepancy problem</a>, 2010-2014+.

%H James Grime, <a href="http://www.youtube.com/watch?v=pFHsrCNtJu4">New Wikipedia sized proof explained with a puzzle</a> (2014).

%H Erica Klarreich, <a href="https://www.quantamagazine.org/20151001-tao-erdos-discrepancy-problem/">A magical answer to an 80-year-old puzzle</a>, Quanta Magazine, October 2015.

%H Boris Konev and Alexei Lisitsa, <a href="http://arxiv.org/abs/1402.2184">A SAT attack on the Erdős Discrepancy Conjecture</a>, arXiv:1402.2184 [cs.DM], 2014.

%H Boris Konev and Alexei Lisitsa, <a href="http://arxiv.org/abs/1405.3097">Computer-aided proof of Erdős discrepancy properties</a>, arXiv:1405.3097 [cs.DM], 2014; Artificial Intelligence 224 (2015), pp. 103-118.

%H Terence Tao, <a href="http://arxiv.org/abs/1509.05363">The Erdős Discrepancy Problem</a>, arXiv:1509.05363 [math.CO], Sep 2015.

%F If a(n) exists for some positive n, then a(n) >= 9^(n-1). - _Charles R Greathouse IV_, Mar 03 2014

%F a(n) exists for all n (Tao, 2015). - _Jeppe Stig Nielsen_, Jul 18 2021

%e Writing + for 1 and - for -1, the maximal sequences of maximal discrepancy 1 are +--+-++--+-, +--+-++--++, and their inverses.

%o (PARI) mk(n)=apply(k->if(k,1,-1),binary(n))

%o 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

%o 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)))

%Y Cf. A181740.

%K nonn,bref,hard,more,nice

%O 0,2

%A _Charles R Greathouse IV_, Feb 11 2014