A237695 Maximum length of a +- 1 sequence of discrepancy n.

0, 11, 1160

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

Cf. A181740.

Sequence in context: A358149 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