login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A237695 Maximum length of a +/- 1 sequence of discrepancy n. 1
0, 11, 1160 (list; graph; refs; listen; history; text; internal format)
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, 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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 22 22:17 EDT 2017. Contains 283901 sequences.