User:SuneJ

2010-02-02T05:26:04Z

SuneJ: New page: My name is Sune Kristian Jakobsen and I'm a second year undergraduate student of mathematics at University of Copenhagen. If you want to send me an email, you can use the "Email this user...

My name is Sune Kristian Jakobsen and I'm a second year undergraduate student of mathematics at University of Copenhagen.

If you want to send me an email, you can use the "Email this user" link in the toolbox to the left, or send it to my first name followed by my last name (no middle name or dot or anything) at hotmail dot com.

Algorithm for finding multiplicative sequences with bounded discrepancy

2010-01-28T14:24:10Z

SuneJ: New page: To return to the main Polymath5 page, click here. This is an algorithm for finding long multiplicative sequences over a finite set of complex number...

[[The Erdős discrepancy problem|To return to the main Polymath5 page, click here]].

This is an algorithm for finding long multiplicative sequences over a finite set of complex numbers (eg. {-1,1}), or showing that they don't exist.
The algorithm consists of 3 types of operations: Using multiplicativity, using bounded discrepancy, and guessing.

*Using multiplicity is:
** Setting <math>x_1=1</math>.
** Determining one of <math>x_a,x_b,x_{ab}</math> from the two others using <math>x_ax_b=x_{ab}</math>.
** Determining one of <math>x_a, x_{an^2}</math> from the other using <math>x_a=x_{an^2}</math>.

*Using bounded discrepancy is:
** For any positive integer n, write down all numbers between -C and C with the same parity as n. This is the "possible partial sums at n". If there is only one possible partial sum at n, call it "the partial sum at n".
** Set 0 to be the partial sum a 0.
** If we know the partial sum at n-1 and <math>x_n</math>, you may set the partial sum at n to be the sum of these two.
** If we know the partial sum at n and <math>x_n</math> you may set the partial sum at n-1 to be the sum a n minus <math>x_n</math>.
** If neither c-1 or c+1 is a possible partial sum at n, you may delete c as a partial sum at n-1 and n+1.
** If you know the partial sum at n and at n-1,you may set <math>x_n</math> to be the sum at n minus the sum at n-1.

*Guessing is:
** If you can assign a value to <math>x_n</math> and reach a contradiction (that is one of the formulas in "using multiplicity" is not fulfilled or for some n there is no possible sum at n) using multiplicity, bounded discrepancy, and guessing you may conclude that this is not a possible value for <math>x_n</math>.
** If there is only one possible value for <math>x_n</math> you may assign this value to <math>x_n</math>.

The Erdős discrepancy problem

2010-01-28T14:23:24Z

SuneJ: /* Simple observations */

If you want to you can [http://michaelnielsen.org/polymath1/index.php?title=Experimental_results jump straight to the main experimental results page].

==Introduction and statement of problem==

Let <math>(x_n)</math> be a <math>\scriptstyle \pm 1</math> sequence and let <math>C</math> be a constant. Must there exist positive integers <math> d,k </math> such that

:<math> \left| \sum_{i=1}^k x_{id} \right| > C </math>?

Known colloquially as "The Erdős discrepancy problem", this question has remained unanswered since the 1930s (Erdős, 1957) and Erdős offered $500 for an answer. It was also asked by Chudakov (1956). It is extremely easy to state, and a very appealing problem, so perhaps Polymath can succeed where individual mathematicians have failed. If so, then, given the notoriety of the problem, it would be a significant coup for the multiply collaborative approach to mathematics. But even if a full solution is not reached, preliminary investigations have already thrown up some interesting ideas which could perhaps be developed into publishable results.

It seems likely that the answer to Erdős's question is yes. If it is, then an easy compactness argument tells us that for every <math>C</math> there exists <math>n</math> such that for every <math>\scriptstyle \pm 1</math> sequence of length <math>n</math> there exist <math>d,k</math> with <math>dk\leq n</math> such that <math> \left| \sum_{i=1}^k x_{id} \right| > C </math>. In view of this, we make some definitions that allow one to talk about the dependence between <math>C</math> and <math>n</math>. For any finite set <math>A</math> of integers, we define the error on <math>A</math> by
:<math> E(A) := \sum_{a\in A} x_a </math>,
and for a set <math>\mathcal{A}</math> of finite sets of integers, we define the discrepancy
:<math> \delta(\mathcal{A},x) := \sup_{A\in \mathcal{A}} |E(A)|. </math>
We can think of the values taken by the sequence <math>(x_n)</math> as a red/blue colouring of the integers that tries to make the number of reds and blues in each <math>\scriptstyle A\in\mathcal{A}</math> as equal as possible. The discrepancy measures the extent to which the sequence fails in this attempt. Taking <math>\scriptstyle \mathcal{HAP}(N)</math> to be the set of homogeneous arithmetic progressions <math>\{d, 2d, 3d, ..., nd\}</math> contained in <math>\{1, 2, ..., N\}</math>, we can restate the question as whether <math>\scriptstyle \delta(\mathcal{HAP}(N),x) \to \infty</math> for every sequence <math>x</math>.

Two related questions have already been solved in the literature. Letting <math>\scriptstyle \mathcal{AP}(N) </math> be the collection of all (not necessarily homogeneous) arithmetic progressions in <math>\{1, 2, ..., N\}</math>, Roth (1964) proved that <math> \scriptstyle \delta(\mathcal{AP}(N),x) \geq c n^{1/4}</math>, independent of the sequence <math>x</math>. Letting <math> \scriptstyle \mathcal{HQAP}(N) </math> be the collection of all homogeneous quasi-arithmetic progressions <math>\scriptstyle\{\lfloor \alpha \rfloor,\lfloor 2\alpha \rfloor,\dots,\lfloor k\alpha \rfloor\}</math> contained in <math>\{1, 2, ..., N\}</math>, Vijay (2008) proved that <math>\scriptstyle \delta(\mathcal{HQAP}(N),x) \geq 0.02 n^{1/6}</math>, independent of the sequence <math>x</math>.

==Some definitions and notational conventions==

A homogeneous arithmetic progression, or HAP, is an arithmetic progression of the form <math> \{d,2d,3d,...,nd\}</math>.

When <math> x</math> is clear from context, we write <math> \delta(N) </math> in place of <math> \delta(\mathcal{HAP}(N),x) </math>.

The discrepancy of a sequence <math>(x_n)</math> is the supremum of <math>|\sum_{n\in P}x_n|</math> over all homogeneous arithmetic progressions P. (Strictly speaking, we should call this something like the HAP-discrepancy, but since we will almost always be talking about HAPs, we adopt the convention that "discrepancy" always means "HAP-discrepancy" unless it is stated otherwise.)
<math>Insert formula here</math>
A sequence <math>(x_n)</math> has discrepancy at most φ(n) if for every natural number N the maximum value of <math>|\sum_{n\in P}x_n|</math> over all homogeneous arithmetic progressions P that are subsets of {1,2,...,N} is at most φ(N).

The EDP is the Erdős discrepancy problem. (This may conceivably be changed if enough people don't like it.)

A sequence <math>(x_n)</math> is completely multiplicative if <math>x_{mn}=x_mx_n</math> for any two positive integers m and n. We shall sometimes abbreviate this to "multiplicative", but the reader should be aware that the word "multiplicative" normally refers to the more general class of sequences such that <math>x_{mn}=x_mx_n</math> whenever m and n are coprime. A completely multiplicative function is determined by the values it takes at primes. The Liouville function λ is the unique completely multiplicative function that takes the value -1 at every prime: if the prime factorization of n is <math>\prod p_i^{a_i}</math> then λ(n) equals <math>(-1)^{\sum a_i}</math>.

A HAP-subsequence of a sequence <math>(x_n)</math> is a subsequence of the form <math>x_d,x_{2d},x_{3d},...</math> for some d. If <math>(x_n)</math> is a multiplicative <math>\pm 1</math> sequence, then every HAP-subsequence is equal to either <math>(x_n)</math> or <math>(-x_n)</math>. We shall call a sequence weakly multiplicative if it has only finitely many distinct HAP-subsequences. Let us also call a <math>\pm 1</math> sequence quasi-multiplicative if it is a composition of a completely multiplicative function from <math>\mathbb{N}</math> to an Abelian group G with a function from G to {-1,1} (This definition is too general. See [http://gowers.wordpress.com/2010/01/09/erds-discrepancy-problem-continued/#comment-4843 this and the next comment]). [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4705 It can be shown] that if <math>(x_n)</math> is a weakly multiplicative sequence, then it has an HAP-subsequence that is quasi-multiplicative.

It is convenient to define the maps <math>T_k</math> for <math>k \geq 1</math> by <math>T_k(x)_n = x_{kn}</math>, where <math>x = (x_1, x_2, ...)</math> is a sequence.

==Simple observations==

*To answer the problem negatively, it is sufficient to find a completely multiplicative sequence (that is, a sequence <math>(x_n)</math> such that <math>x_{mn}=x_mx_n</math> for every m,n) such that its partial sums <math>x_1+\dots+x_n</math> are bounded. First mentioned in the proof of the theorem in [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/ this] post.

*The function that takes n to 1 if the last non-zero digit of n in its ternary representation is 1 and -1 if the last non-zero digit is 2 is completely multiplicative and the partial sum up to n is easily shown to be at most <math>\log_3n +1</math>. Therefore, the rate at which the worst discrepancy grows, as a function of the length of the homogeneous progression, can be as slow as logarithmic. [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/] <s>[http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4553 It turns out] that the base can be made significantly higher than 3, so this example is not best possible.</s> [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4757 Correction]

*To answer the problem negatively, it is also sufficient to find a completely multiplicative function f from <math>\mathbb{N}</math> to a finite Abelian group G (meaning that f(mn)=f(m)+f(n) for every m,n) and a function h from G to {-1,1} such that for each g in G there exists d with f(d)=g and with the partial sums hf(d)+hf(2d)+...+hf(nd) bounded. In that case, one can set <math>x_n=hf(n)</math>. (Though this observation is simple with the benefit of hindsight, it might not have been made had it not been for the fact that this sort of structure was identified in a long sequence that had been produced experimentally). First mentioned [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4696 here]. Se also [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/ this post] and [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4717 this comment].

*[http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4705 It can be shown] that if a <math>\pm 1</math> sequence <math>(x_n)</math> starts with 1 and has only finitely many distinct subsequences of the form <math>(x_d,x_{2d},x_{3d},\dots)</math>, then it must have a subsequence that arises in the above way. (This was mentioned just above in the terminology section.)

*The problem for the positive integers is equivalent to the problem for the positive rationals. [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4676](Sketch proof: if you have a function f from the positive integers to {-1,1} that works, then define <math>f_q(x)</math> to be f(q!x) whenever q!x is an integer. Then take a pointwise limit of a subsequence of the functions <math>f_q</math>. [[Limits with better properties|Click here for a more detailed discussion of this construction and what it is good for]].

*Define the [[drift]] of a sequence to be the maximal value of |f(md)+...+f(nd)|. The discrepancy problem is equivalent to showing that the drift is always infinite. It is obvious that it is at least 2 (because |f(2)+f(4)|, |f(2)+f(3)|, |f(3)+f(4)| cannot all be at most 1); one can show that [[drift|it is at least 3]] (which implies as a corollary that the discrepancy is at least 2). One can also show that the [[upper and lower discrepancy]] are each at least 2.

*One can [[topological dynamics formulation|formulate the problem using topological dynamics]].

*Using Fourier analysis, one can [[Fourier reduction|reduce the problem to one about completely multiplicative functions]].

*Here is an [[algorithm for finding multiplicative sequences with bounded discrepancy]].

==Experimental evidence==

''Main page: [[Experimental results]]''

A nice feature of the problem is that it lends itself well to investigation on a computer. Although the number of <math>\pm 1</math> sequences grows exponentially, the constraints on these sequences are such that depth-first searches can lead quite quickly to interesting examples. For instance, at the time of writing they have yielded several examples of sequences of length 1124 with discrepancy 2. (This is the current record.) See [[Experimental results|this page]] for more details and further links.

Another sort of evidence is to bound the discrepancy for specific sequences. For example, setting <math>x_1=-x_2=1</math> and <math> x_n=-x_{n/3}</math> or <math>x_n=x_{n-3}</math> according to whether <math>n</math> is a multiple of 3 or not, yields a sequence with

:<math> \delta(N) \leq \log_9(N)+1 </math>

for sufficiently large <math> N </math>. Currently, this is the record-holder for slow growing discrepancy.

The Thue-Morse sequence has discrepancy <math> \delta(N) \gg \sqrt{N} </math>. (See the discussion following [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4775 this comment] and the next one.)

A random sequence (each <math> x_i </math> chosen independently) has discrepancy at least (asymptotically) <math> \sqrt{2N \log\log N} </math> by the law of the iterated logarithm.

Determining if the discrepancy of [http://en.wikipedia.org/wiki/Liouville_function Liouville's lambda function] is <math> O(n^{1/2+\epsilon})</math> is equivalent to solving the Riemann hypothesis. However, this growth cannot be bounded above by <math>n^{1/2-\epsilon}</math> for any positive ε.

==Interesting subquestions==

Given the length of time that the Erdős discrepancy problem has been open, the chances that it will be solved by Polymath5 are necessarily small. However, there are a number of interesting questions that we do not know the answers to, several of which have arisen naturally from the experimental evidence. Good answers to some of these would certainly constitute publishable results. Here is a partial list -- further additions are very welcome. (When the more theoretical part of the project starts, this section will probably grow substantially and become a separate page.)

*Is there an infinite sequence of discrepancy 2? (Given how long a finite sequence can be, it seems unlikely that we could answer this question just by a clever search of all possibilities on a computer.)

*The long sequences of low discrepancy discovered by computer all have some kind of approximate weak multiplicativity. If we take a hypothetical counterexample <math>(x_n)</math> (which we could even assume has discrepancy 2), can we prove that it, or some other counterexample derived from it by passing to HAP-subsequences and taking pointwise limits, has some kind of interesting multiplicative structure?

*Closely related to the previous question. If <math>(x_n)</math> is a hypothetical counterexample, must it satisfy a compactness property of the following kind: for every positive c there exists M such that if you take any M HAP-subsequences, then there must be two of them, <math>(y_n)</math> and <math>(z_n)</math>, such that <math>\lim\inf N^{-1}\sum_{n=1}^Ny_nz_n\geq 1-c</math>?

*An even weaker question. If <math>(x_n)</math> is a hypothetical counterexample, must it have two HAP-subsequences <math>(y_n)</math> and <math>(z_n)</math> such that the lim inf of <math>N^{-1}\sum_{n=1}^N y_nz_n</math> is greater than 0?

*A similar question, perhaps equivalent to the previous one (this should be fairly easy to check). Given a sequence <math>(x_n)</math> define f(N) to be the average of <math>x_ax_bx_cx_d</math> over all quadruples (a,b,c,d) such that ab=cd and <math>a,b,c,d\leq N</math>. If <math>(x_n)</math> is a counterexample, does that imply that <math>\lim\inf f(N)</math> is greater than 0? [http://thomas1111.wordpress.com/2010/01/15/average-over-quadruples-of-the-first-1124-sequence/ See here for a computation of this average for the first 1124 sequence].

*Is there any completely multiplicative counterexample? (This may turn out to be a very hard question. If so, then answering the previous questions could turn out to be the best we can hope for without making a substantial breakthrough in analytic number theory.)

*Does there exist a <math>\pm 1</math> sequence such that the corresponding discrepancy function grows at a rate that is slower than <math>c\log n</math> for any positive c?

*Does the number of sequences of length n and discrepancy at most C grow exponentially with n or more slowly than exponentially? (Obviously if the conjecture is true then it must be zero for large enough n, but the hope is that this question is a more realistic initial target.)

==General proof strategies==

This section contains links to other pages in which potential approaches to solving the problem are described.

[[First obtain multiplicative structure and then obtain a contradiction]]

[[Find a different parameter, show that it tends to infinity, and show that that implies that the discrepancy tends to infinity]]

[[Prove the result for shifted HAPs instead of HAPs]]

==Annotated Bibliography==

*Blog Discussion on Gowers's Weblog
**[http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/ Zeroth Post] (Dec 17 - Jan 6).
**[http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/ First Post] (Jan 6 - Jan 12).
**[http://gowers.wordpress.com/2010/01/09/erds-discrepancy-problem-continued/ Second Post] (Jan 9 - Jan 11).
**[http://gowers.wordpress.com/2010/01/11/the-erds-discrepancy-problem-iii/ Third Post] (Jan 11 - Jan 14).
**[http://gowers.wordpress.com/2010/01/14/the-erds-discrepancy-problem-iv/ Fourth Post] (Jan 14 - 16).
**[http://gowers.wordpress.com/2010/01/16/the-erds-discrepancy-problem-v/ Fifth Post] (Jan 16-19).
**[http://gowers.wordpress.com/2010/01/19/edp1-the-official-start-of-polymath5/ First Theoretical Post] (Jan 19-21)
**[http://gowers.wordpress.com/2010/01/21/edp2-a-few-lessons-from-edp1/ Second Theoretical Post] (Jan 21-26)
**[http://gowers.wordpress.com/2010/01/26/edp3-a-very-brief-report-on-where-we-are/ Third Theoretical Post] (Jan 26 -?)

*Mathias, A. R. D. [http://www.dpmms.cam.ac.uk/~ardm/erdoschu.pdf On a conjecture of Erdős and Čudakov]. Combinatorics, geometry and probability (Cambridge, 1993).

This one page paper establishes that the maximal length of sequence for the case where C=1 is 11, and is the starting point for our experimental studies.

*Tchudakoff, N. G. Theory of the characters of number semigroups. J. Indian Math. Soc. (N.S.) 20 (1956), 11--15. MR0083515 (18,719e)

The Mathias paper states that one of Erdős's problem lists states that this paper "studies related questions". The Math Review for this paper states that it summarizes results from seven other papers that are in Russian. The Math Review leaves the impression that the topic concerns characters of modulus 1.

*Borwein, Peter, and Choi, Stephen. [http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P204.pdf A variant of Liouville's lambda function: some surprizing formulae].

Explicit formulas for the discrepancy of some completely multiplicative functions whose discrepancy is logarithmic. A typical example is: Let <math>\lambda_3(n) = (-1)^{\omega_3(n)}</math> where <math>\omega_3(n)</math> is the number of distinct prime factors congruent to <math>-1 \bmod 3</math> in <math>n</math> (with multiple factors counted multiply). Then the discrepancy of the <math>\lambda_3</math> sequence up to <math>N</math> is exactly the number of 1's in the base three expansion of <math>N</math>. (This turns out not to be so surprising after all, since <math>\lambda_3(n)</math> is precisely the same as the ternary function defined in the second item of the Simple Observations section.)

*Borwein, Peter, Choi, Stephen and Coons, Michael. [http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P225.pdf Completely multiplicative functions taking values in {-1,1}]. The published version of the above paper, which explains the results and proofs more clearly than the preprint, and is more explicit about the relationship with Erdős's question.

*Granville and Soundararajan. [http://arxiv.org/abs/math/0702389 Multiplicative functions in arithmetic progressions]

In this [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4729 blog post] Terry Tao wrote: "Granville and Soundararajan have made some study of the discrepancy of bounded multiplicative functions. The situation is remarkably delicate and number-theoretical (and is closely tied with the Granville-Soundararajan theory of pretentious characters)."

=== Problem lists on which this problem appears ===

*Erdős, P. and Graham, R. [http://www.math.ucsd.edu/~fan/ron/papers/79_09_combinatorial_number_theory.pdf Old and New Problems and Results in Combinatorial Number Theory: van der Waerden's Theorem and Related Topics], L'Enseignement Math. 25 (1979), 325-344.

Our problem is mentioned at the bottom of page 331, where they indicate knowledge of a coloring with logarithmic discrepancy. On pages 330-1, they review work on the non-homogeneous problem.

*As [http://www.math.niu.edu/~rusin/known-math/93_back/prizes.erd this web page] reveals, the Erdős discrepancy problem was a $500-dollar problem of Erdős, so it is clear that he regarded it as pretty hard.

*P. Erdős. [http://www.renyi.hu/~p_erdos/1957-13.pdf Some unsolved problems], Michigan Math. J. 4 (1957), 291--300 MR20 #5157; Zentralblatt 81,1.

Problem 9 of this paper is ours. Erdős dates the problem to around 1932, and notes what we know about Liouville's function (lower and upper bound).

*Finch, S. [http://algo.inria.fr/csolve/ec.pdf Two-colorings of positive integers]. Dated May 27, 2008.

Summarizes knowledge of discrepancy of two colorings when the discrepancy is restricted to homogeneous progressions, nonhomogeneous progressions, and homogeneous quasi-progressions. Contains bibliography with 17 entries, including most of those above.

=== non-homogeneous AP, quasi-AP, and other related discrepancy papers ===

*Hochberg, Robert. [http://www.springerlink.com/content/q02424284373qw45/ Large Discrepancy In Homogenous Quasi-Arithmetic Progressions]. Combinatorica, Volume 26 (2006), Number 1.

Roth's method for the <math> n^{1/4}</math> lower bound on nonhomogeneous AP discrepancy is adapted to give a lower bound for homogeneous quasi-AP discrepancy. This result is weaker than the Vijay result, but uses a different method.

*Vijay, Sujith. [http://www.combinatorics.org/Volume_15/PDF/v15i1r104.pdf On the discrepancy of quasi-progressions]. Electronic Journal of Combinatorics, R104 of Volume 15(1), 2008.

A quasi-progression is a sequence of the form <math>\lfloor k \alpha \rfloor </math>, with <math>1\leq k \leq K</math> for some K. The main theorem of interest is: If the integers from 0 to n are 2-coloured, there exists a quasi-progression that has discrepancy at least <math> (1/50)n^{1/6}</math>.

* Doerr, Benjamin; Srivastav, Anand; Wehr, Petra. [http://www.combinatorics.org/Volume_11/Abstracts/v11i1r5.html Discrepancy of Cartesian products of arithmetic progressions]. Electron. J. Combin. 11 (2004), no. 1, Research Paper 5, 16 pp. (electronic).

Abstract: We determine the combinatorial discrepancy of the hypergraph H of cartesian
products of d arithmetic progressions in the <math> [N]^d</math> –lattice.
The study of such higher dimensional arithmetic progressions is motivated by a
multi-dimensional version of van derWaerden’s theorem, namely the Gallai-theorem
(1933). We solve the discrepancy problem for d–dimensional arithmetic progressions
by proving <math>disc(H) = \Theta�(N^{d/4})</math> for every fixed positive integer d. This extends the famous
lower bound of <math> \Omega(N^{1/4})</math> of Roth (1964) and the matching upper bound <math> O(N^{1/4})</math>
of Matouˇsek and Spencer (1996) from d = 1 to arbitrary, fixed d. To establish
the lower bound we use harmonic analysis on locally compact abelian groups. For
the upper bound a product coloring arising from the theorem of Matouˇsek and
Spencer is sufficient. We also regard some special cases, e.g., symmetric arithmetic
progressions and infinite arithmetic progressions.

*Cilleruelo, Javier; Hebbinghaus, Nils [http://www.ams.org/mathscinet-getitem?mr=2547932 Discrepancy in generalized arithmetic progressions]. European J. Combin. 30 (2009), no. 7, 1607--1611. MR 2547932

*Valkó, Benedek. [Discrepancy of arithmetic progressions in higher dimensions]. (English summary)
J. Number Theory 92 (2002), no. 1, 117--130. MR1880588 (2003b:11071)

Abstract:
K. F. Roth (1964, Acta. Arith.9, 257–260) proved that the discrepancy of arithmetic progressions contained in [N] is at least <math> cN^{1/4} </math>, and later it was proved that this result is sharp. We consider the d-dimensional version of this problem. We give a lower estimate for the discrepancy of arithmetic progressions on <math> [N]^d </math> and prove that this result is nearly sharp. We use our results to give an upper estimate for the discrepancy of lines on an N×N lattice, and we also give an estimate for the discrepancy of a related random hypergraph.

*Roth, K. F., Remark concerning integer sequences. Acta Arith. 9 1964 257--260. MR0168545 (29 #5806)

Shows that the discrepancy on APs is at least <math>cN^{1/4}</math>.

Fourier reduction

2010-01-27T22:01:55Z

SuneJ: S^1: text --> TeX

Let f be an arbitrary function from <math>{\Bbb Z}</math> to {-1,+1} of discrepancy at most C. Let N be a moderately large integer, let <math>p_1,\ldots,p_d</math> be the primes in [N], and let M be a huge integer (much larger than N). Then we can define a function <math>F: ({\Bbb Z}/M{\Bbb Z})^d \to \{-1,+1\}</math> by the formula

:<math>F(a_1,\ldots,a_d) := f( p_1^{a_1} \ldots p_d^{a_d} ).</math>
whenever <math>a_1,\ldots,a_d \in [M]</math>. Note that F has a normalised L^2 norm of 1, so by the Plancherel identity

:<math>\sum_{\xi \in ({\Bbb Z}/M{\Bbb Z})^d} |\hat F(\xi)|^2 = 1.</math> (1)

Let <math>\pi: [N] \to {\Bbb Z}^d</math> be the map

:<math>\pi(p_1^{a_1} \ldots p_d^{a_d}) := (a_1,\ldots,a_d)</math>

then by hypothesis one has

:<math>|F(x+\pi(1)) + \ldots + F(x+\pi(n))| \leq C</math>

for all (1-O_N(1/M)) of the x in <math>({\Bbb Z}/M{\Bbb Z})^d</math>, and all <math>1 \leq n \leq N</math>. Applying Plancherel to this, we obtain

:<math> \sum_{\xi \in ({\Bbb Z}/M{\Bbb Z})^d} |\hat F(\xi)|^2 |\sum_{j=1}^n e( \xi \cdot \pi(j) / M ) |^2 \ll C</math>

for each such n, and so on averaging in n we have

:<math> \sum_{\xi \in ({\Bbb Z}/M{\Bbb Z})^d} |\hat F(\xi)|^2 \frac{1}{N} \sum_{n=1}^N |\sum_{j=1}^n e( \xi \cdot \pi(j) / M )|^2 \ll C.</math>

Comparing this with (1) and using the pigeonhole principle, we conclude that there exists <math>\xi</math> such that

:<math>\frac{1}{N} \sum_{n=1}^N |\sum_{j=1}^n e( \xi \cdot \pi(j) / M )|^2 \ll C</math>.

If we let <math>g: {\Bbb N} \to S^1</math> be a completely multiplicative function such that <math>g(p_i) = e(\xi_i/M)</math> for all i=1,...,d, we have

:<math> e( \xi \cdot \pi(j) / M ) = g(j)</math>

for all j=1,...,N, and thus

:<math>\frac{1}{N} \sum_{n=1}^N |\sum_{j=1}^n g(j)|^2 \ll C</math>.

So, if one can show a uniform bound

:<math>\frac{1}{N} \sum_{n=1}^N |\sum_{j=1}^n g(j)|^2 \geq \omega(N)</math>

where <math>\omega(N)</math> goes to infinity as <math>N \to \infty</math>, for arbitrary <math>S^1</math>-valued multiplicative functions, one is done!

Actually, one can do a little better than this. From (1) we see that <math>|\hat F(\xi)|^2</math> induces a probability measure (depending on N,M) on completely multiplicative functions <math>g: {\Bbb Q} \to S^1</math> (strictly speaking, this function is only defined on rationals that involve the primes <math>p_1,\ldots,p_d</math>, but one can extend to the rationals by setting g to equal 1 on all other primes), and for g drawn from this probability measure the above arguments in fact show that

:<math> {\Bbb E} |g(1)+\ldots+g(n)|^2 \ll C</math>

for all n up to N. Taking a weak limit of these probability measures (using Prokhorov's theorem) we can in fact get this for all n. So to solve EDP, it in fact suffices to show that

:<math> \sup_n {\Bbb E} |g(1)+\ldots+g(n)|^2 = \infty</math>

for all probabilistic completely multiplicative functions taking values in <math>S^1</math>. This should be compared to the completely multiplicative special case of EDP, in which g takes values in {-1,+1} and is deterministic.

If one is interested in square-invariant functions only (so <math>f(q^2 x) = f(x)</math> for all rational q) then we can restrict g to be {-1,+1} valued (basically because <math>({\Bbb Z}/M{\Bbb Z})^d</math> can now be replaced with <math>({\Bbb Z}/2{\Bbb Z})^d</math> in the above analysis.

Limits with better properties

2010-01-12T21:14:59Z

SuneJ: /* Dichotomies */

[[The Erdős discrepancy problem|Click here to return to the main Polymath5 page]]

===From an integer sequence to a function defined on the rationals===

Let <math>(x_n)</math> be an infinite <math>\pm 1</math> sequence of discrepancy at most C. Using this sequence, we can define a "rational sequence" <math>(y_a)_{a\in\mathbb{Q}}</math> in one or other of the following two ways (which look different but are essentially the same).

====Method 1====

For each positive rational number a and each positive integer n, let <math>f_n(a)=x_{n!a}</math> if n!a is an integer and let it be undefined (or arbitrarily defined) otherwise. Pick a subsequence of the functions <math>f_n</math> that converges pointwise and define <math>y_a</math> to be the limit of the values of <math>f_n(a)</math> along this subsequence.

====Method 2====

Define the functions <math>f_n</math> as above, but this time define <math>y_a</math> to be the limit of <math>f_n(a)</math> along a non-principal ultrafilter U. It is simple to check that the result will again be a pointwise limit of a subsequence of the functions <math>f_n</math>.

===Properties of the resulting function===

Let us begin by proving that every sequence of the form <math>y_a,y_{2a},y_{3a},\dots</math> (which we shall call an HAP-subsequence) has discrepancy at most C.

This is trivial. Let <math>g_1,g_2,g_3,\dots</math> be a subsequence of the <math>f_n</math> such that <math>f_n(a)</math> converges to <math>y_a</math> for every rational number a. Let m be any positive integer. Then there exists some n such that <math>g_n(ka)=y_{ka}</math> for every k between 1 and m. We may also pick n large enough so that n!a is an integer. If we do so, then the numbers n!a, 2n!a,...,mn!a form an HAP, which implies that the partial sum <math>g_n(a)+\dots+g_n(ma)</math> has absolute value at most C, since it equals the sum <math>x_d+\dots+x_{md}</math>, where d=n!a.

Thus, this construction gives us a way of passing from an example that works over the integers to an example that works over the rationals. However, it does more than that, as the following argument shows. Let us suppose that the r-sequence and the s-sequence of <math>(x_n)</math> are equal: that is, <math>x_{rn}=x_{sn}</math> for every positive integer n. What does this tell us about the function <math>y_a</math>? Obviously, it implies immediately that <math>y_{ra}=y_{sa}</math> for every rational number a. From that we deduce that <math>y_a=y_{sa/r}</math> for every rational number a (applying the previous result to a/r) and also that <math>y_a=y_{ar/s}</math>. In other words, once we have passed to the rational limit, we find that the function is invariant under dilation by r/s, which implies that it is also invariant under dilation by s/r.

===Further investigation===

====Improved properties in the limit====

If we know only that two HAP-subsequences of the sequence <math>(x_n)</math> are approximately equal, then it is still possible that we might be able to choose the pointwise limit carefully so as to ensure that in the limit we have exact invariance. It would be very interesting to reach a clear understanding of when this is possible and when it isn't. (If the two sequences differ everywhere on some further HAP-subsequence, for example, then it probably isn't possible. But then we might not be inclined to say that the two sequences are approximately equal.)

====Dichotomies====

Suppose, as we may, that we have a rational example <math>(y_a)</math> with discrepancy at most C. That instantly gives us a whole host of other examples, since for every rational b the function <math>y_{ba}</math> is an example, and any pointwise limit of a subsequence of these further examples (which is the same as an element of the closure of the set of those examples in the product topology) is again an example. We have already seen that we can get improved properties in the limit. What happens if we try to force the limit to take certain values in certain places by choosing an appropriate sequence of dilations?

To get some handle on this question, let us look at a couple of simple examples. Suppose, for instance, that I want to find an example <math>(z_a)</math> such that <math>z_1=z_2</math>. If I can find any r such that <math>y_r=y_{2r}</math> then I am done, since I can simply set <math>z_a=y_{ra}</math>. So if I cannot find an example with <math>z_1=z_2</math> then I know that <math>y_a=-y_{2a}</math> for every a, which is a very strong multiplicativity property.

This is not particularly interesting, because the property <math>z_1=z_2</math> will rapidly be lost if one dilates the function <math>z_a</math> and passes to limits. So let us try to do something more infinitary.

Suppose that I want to pass to an example that is multiplicative. I can do this if for every finite multiset A of rationals there exists some rational r such that <math>y_ry_{rab}=y_{ra}y_{rb}</math> for every a,b in A. The reason is that if I have such an r for a given set A and I set <math>z_a=y_{ar}/y_r</math>, then <math>z_{ab}=z_az_b</math> for every a,b in A. Taking a increasing sequence of sets A whose union is all of <math>\mathbb{Q}</math> and passing to the limit of the corresponding z-sequences, we obtain an example that is multiplicative everywhere.

This is basically just a simple compactness argument that says either there is a multiplicative example or there is some finite set A such that for every r we find a "failure of A-multiplicativity at r". For example, if A is the multiset {2,2,3}, then it tells us that there is no r such that both the equalities <math>y_ry_{4r}=y_{2r}^2</math> and <math>y_ry_{6r}=y_{2r}y_{3r}</math> hold.

This is quite a strong non-multiplicativity property. It would be interesting to investigate experimentally whether insisting on non-multiplicativity of this kind forces the discrepancy to become large.

====Limiting behaviour of some concrete sequences or classes of sequences====

As well as beginning with a hypothetical counterexample to the Erdős discrepancy problem, one can begin with concrete sequences and see what happens. For example, if you start with the Liouville sequence, then the only two HAP-subsequences are the sequence itself and minus the sequence. More generally, if a sequence is weakly multiplicative, then there will be only finitely many HAP-subsequences, so any pointwise limit of them is automatically one of these subsequences (and similar remarks apply to any rational extension).

It might be interesting to see what happens to the Morse sequence. It is <math>T_2</math>-invariant, so the interest would come with dilations by odd factors. Can one characterize all functions on the rationals that are pointwise limits of sequences of the form <math>T_kx</math>, where x is the Morse sequence? [http://gowers.wordpress.com/2010/01/11/the-erds-discrepancy-problem-iii/#comment-4985 I think it is done here]

If x is a random sequence, then I'm pretty sure that every sequence is a pointwise limit of dilations of x. This, interestingly, would give an infinitary proof that random sequences have unbounded discrepancy. (When you unpack it, however, the argument is less interesting: it is essentially using the fact that a random sequence will have arbitrarily long strings of 1s, which trivially rules out bounded discrepancy.)

====Possible definitions of essential sameness====

We could place various equivalence relations on sequences. One particularly generous one would be to say that two sequences x and y are equivalent if you can find pointwise limits of dilations of x and y that were equal. A more restricted one would be as above, but to insist that the same sequence of dilations is chosen for each. A yet more restricted one would be to insist that all pointwise limits of dilations (perhaps with the added property that every positive integer is eventually a factor of all the amounts by which you are dilating) are the same.

Limits with better properties

2010-01-12T19:03:53Z

SuneJ: /* Limiting behaviour of some concrete sequences or classes of sequences */

[[The Erdős discrepancy problem|Click here to return to the main Polymath5 page]]

===From an integer sequence to a function defined on the rationals===

Let <math>(x_n)</math> be an infinite <math>\pm 1</math> sequence of discrepancy at most C. Using this sequence, we can define a "rational sequence" <math>(y_a)_{a\in\mathbb{Q}}</math> in one or other of the following two ways (which look different but are essentially the same).

====Method 1====

For each positive rational number a and each positive integer n, let <math>f_n(a)=x_{n!a}</math> if n!a is an integer and let it be undefined (or arbitrarily defined) otherwise. Pick a subsequence of the functions <math>f_n</math> that converges pointwise and define <math>y_a</math> to be the limit of the values of <math>f_n(a)</math> along this subsequence.

====Method 2====

Define the functions <math>f_n</math> as above, but this time define <math>y_a</math> to be the limit of <math>f_n(a)</math> along a non-principal ultrafilter U. It is simple to check that the result will again be a pointwise limit of a subsequence of the functions <math>f_n</math>.

===Properties of the resulting function===

Let us begin by proving that every sequence of the form <math>y_a,y_{2a},y_{3a},\dots</math> (which we shall call an HAP-subsequence) has discrepancy at most C.

This is trivial. Let <math>g_1,g_2,g_3,\dots</math> be a subsequence of the <math>f_n</math> such that <math>f_n(a)</math> converges to <math>y_a</math> for every rational number a. Let m be any positive integer. Then there exists some n such that <math>g_n(ka)=y_{ka}</math> for every k between 1 and m. We may also pick n large enough so that n!a is an integer. If we do so, then the numbers n!a, 2n!a,...,mn!a form an HAP, which implies that the partial sum <math>g_n(a)+\dots+g_n(ma)</math> has absolute value at most C, since it equals the sum <math>x_d+\dots+x_{md}</math>, where d=n!a.

Thus, this construction gives us a way of passing from an example that works over the integers to an example that works over the rationals. However, it does more than that, as the following argument shows. Let us suppose that the r-sequence and the s-sequence of <math>(x_n)</math> are equal: that is, <math>x_{rn}=x_{sn}</math> for every positive integer n. What does this tell us about the function <math>y_a</math>? Obviously, it implies immediately that <math>y_{ra}=y_{sa}</math> for every rational number a. From that we deduce that <math>y_a=y_{sa/r}</math> for every rational number a (applying the previous result to a/r) and also that <math>y_a=y_{ar/s}</math>. In other words, once we have passed to the rational limit, we find that the function is invariant under dilation by r/s, which implies that it is also invariant under dilation by s/r.

===Further investigation===

====Improved properties in the limit====

If we know only that two HAP-subsequences of the sequence <math>(x_n)</math> are approximately equal, then it is still possible that we might be able to choose the pointwise limit carefully so as to ensure that in the limit we have exact invariance. It would be very interesting to reach a clear understanding of when this is possible and when it isn't. (If the two sequences differ everywhere on some further HAP-subsequence, for example, then it probably isn't possible. But then we might not be inclined to say that the two sequences are approximately equal.)

====Dichotomies====

Suppose, as we may, that we have a rational example <math>(y_a)</math> with discrepancy at most C. That instantly gives us a whole host of other examples, since for every rational b the function <math>y_{ba}</math> is an example, and any pointwise limit of a subsequence of these further examples (which is the same as an element of the closure of the set of those examples in the product topology) is again an example. We have already seen that we can get improved properties in the limit. What happens if we try to force the limit to take certain values in certain places by choosing an appropriate sequence of dilations?

To get some handle on this question, let us look at a couple of simple examples. Suppose, for instance, that I want to find an example <math>(z_a)</math> such that <math>z_1=z_2</math>. If I can find any r such that <math>y_r=y_{2r}</math> then I am done, since I can simply set <math>z_a=y_{ra}</math>. So if I cannot find an example with <math>z_1=z_2</math> then I know that <math>y_a=-y_{2a}</math> for every a, which is a very strong multiplicativity property.

This is not particularly interesting, because the property <math>z_1=z_2</math> will rapidly be lost if one dilates the function <math>z_a</math> and passes to limits. So let us try to do something more infinitary.

Suppose that I want to pass to an example that is multiplicative. I can do this if for every finite multiset A of rationals there exists some rational r such that <math>y_ry_{rab}=y_{ra}y_{rb}</math> for every a,b in A. The reason is that if I have such an r for a given set A and I set <math>z_a=y_{ar}/y_r</math>, then <math>z_{ab}=z_az_b</math> for every a,b in A. Taking a collection of sets A whose union is all of <math>\mathbb{Q}</math> and passing to the limit of the corresponding z-sequences, we obtain an example that is multiplicative everywhere.

This is basically just a simple compactness argument that says either there is a multiplicative example or there is some finite set A such that for every r we find a "failure of A-multiplicativity at r". For example, if A is the multiset {2,2,3}, then it tells us that there is no r such that both the equalities <math>y_ry_{4r}=y_{2r}^2</math> and <math>y_ry_{6r}=y_{2r}y_{3r}</math> hold.

This is quite a strong non-multiplicativity property. It would be interesting to investigate experimentally whether insisting on non-multiplicativity of this kind forces the discrepancy to become large.

====Limiting behaviour of some concrete sequences or classes of sequences====

As well as beginning with a hypothetical counterexample to the Erdős discrepancy problem, one can begin with concrete sequences and see what happens. For example, if you start with the Liouville sequence, then the only two HAP-subsequences are the sequence itself and minus the sequence. More generally, if a sequence is weakly multiplicative, then there will be only finitely many HAP-subsequences, so any pointwise limit of them is automatically one of these subsequences (and similar remarks apply to any rational extension).

It might be interesting to see what happens to the Morse sequence. It is <math>T_2</math>-invariant, so the interest would come with dilations by odd factors. Can one characterize all functions on the rationals that are pointwise limits of sequences of the form <math>T_kx</math>, where x is the Morse sequence? [http://gowers.wordpress.com/2010/01/11/the-erds-discrepancy-problem-iii/#comment-4985 I think it is done here]

If x is a random sequence, then I'm pretty sure that every sequence is a pointwise limit of dilations of x. This, interestingly, would give an infinitary proof that random sequences have unbounded discrepancy. (When you unpack it, however, the argument is less interesting: it is essentially using the fact that a random sequence will have arbitrarily long strings of 1s, which trivially rules out bounded discrepancy.)

====Possible definitions of essential sameness====

We could place various equivalence relations on sequences. One particularly generous one would be to say that two sequences x and y are equivalent if you can find pointwise limits of dilations of x and y that were equal. A more restricted one would be as above, but to insist that the same sequence of dilations is chosen for each. A yet more restricted one would be to insist that all pointwise limits of dilations (perhaps with the added property that every positive integer is eventually a factor of all the amounts by which you are dilating) are the same.

Talk:Limits with better properties

2010-01-12T10:39:26Z

SuneJ: Question

== Question ==

"Taking a collection of sets A whose union is all of <math>\mathbb{Q}</math> and passing to the limit of the corresponding z-sequences, we obtain an example that is multiplicative everywhere."

Do you mean an ''increasing sequence'' of sets A, whose union is Q? --[[User:SuneJ|SuneJ]] 10:39, 12 January 2010 (UTC)

Experimental results

2010-01-10T19:04:52Z

SuneJ: /* Experimental data */

To return to the main Polymath5 page, click [[The Erdős discrepancy problem|here]].

Perhaps we should have two kinds of subpages to this page: Pages about finding examples, and pages about analyzing them?

== Experimental data==
* [[The first 1124-sequence]] with discrepancy 2. ''Some more description''
* Other [[length 1124 sequences]] with discrepancy 2. ''Some more description''
* Some data about the problem with [[different upper and lower bound]]. ''Some more description''
* Sequences taking values in <math>\mathbb{T}</math>:
** [[4th roots of unity]]
** [[6th roots of unity]]
* [http://thomas1111.wordpress.com/2010/01/10/tables-for-a-c10-candidate/ A sequence of length 407] with discrepancy 2 such that <math>x_n=x_{32 n}</math> for every n. [[The HAP-subsequence structure of that sequence]].
* More [[T32-invariant sequences]].
* Long [[multiplicative sequences]].
* Long sequences satisfying [[T2(x) = -x]].

==Wish list==

* Find long/longest quasi-multiplicative sequences with some fixed group G, function <math>G\to \{-1,1\}</math> and maximal discrepancy C
** <math>G=C_6</math> and the function that sends 0,1 and 2 to 1 (because this seems to be a good choice)
* Do a "Mark-Bennet-style analysis" of one of the new 1124-sequences. [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4827] Also [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4842 done] (by Mark Bennet).
*. Take a moderately large k and search for the longest sequence of discrepancy 2 that's constructed as follows. First, pick a completely multiplicative function f to the group <math>C_{2k}</math>. Then set <math>x_n</math> to be 1 if f(n) lies between 0 and k-1, and -1 if f(n) lies between k and 2k-1. Alec has already [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4563 done this for k=1] and [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4734 partially done it for k=3].
*Search for the longest sequence of discrepancy 2 with the property that <math>x_n=x_{32n}</math> for every n. The motivation for this is to produce a fundamentally different class of examples (different because their group structure would include an element of order 5). It's not clear that it will work, since 32 is a fairly large number. However, if you've chosen <math>x_{32n}</math> then that will have some influence on several other choices, such as <math>x_{4n},x_{8n}</math> and <math>x_{16n}</math>, so maybe it will lead to something interesting. Alec [http://gowers.wordpress.com/2010/01/09/erds-discrepancy-problem-continued/#comment-4873 has made a start on this] and an [http://gowers.wordpress.com/2010/01/09/erds-discrepancy-problem-continued/#comment-4874 initial investigation] suggests that the sequence he has found does indeed have some <math>C_{10}</math>-related structure.
*Here's another experiment that should be pretty easy to program and might yield something interesting. It's to look at the how the discrepancy appears to grow when you define a sequence using a greedy algorithm. I say "a" greedy algorithm because there are various algorithms that could reasonably be described as greedy. Here are a few.

<blockquote>
1. For each n let <math>x_n</math> be chosen so as to minimize the discrepancy so far, given the choices already made for <math>x_1,\dots,x_{n-1}</math>. (If this does not uniquely determine <math>x_n</math> then choose it arbitrarily, or randomly, or according to some simple rule like always equalling 1.)
</blockquote>

<blockquote>
2. Same as 1 but with additional constraints, in the hope that these make the sequence more likely to be good. For instance, one might insist that <math>x_{2k}=x_{3k}</math> for every k. Here, when choosing <math>x_n</math> one would probably want to minimize the discrepancy up to <math>x_{n+k}</math> if <math>x_{n+1},\dots,x_{n+k}</math> had already been chosen. Another obvious constraint to try is complete multiplicativity.
</blockquote>

<blockquote>
3. A greedy algorithm of sorts, but this time trying to minimize a different parameter. The first algorithm will do this: when you pick <math>x_n</math> you look, for each factor d of n, at the partial sum along the multiples of d up to but not including n. This will give you a set A of numbers (the possible partial sums). If max(A) is greater than max(-A) then you set <math>x_n=-1</math>, if max(-A) is greater than max(A) then you let <math>x_n=1</math>, and if they are equal then you make the decision according to some rule that seems sensible. But it might be that you would end up with a slower-growing discrepancy if you regarded A as a multiset and made the decision on some other basis. For instance, you could take the sum of <math>2^k</math> over all positive elements <math>k\in A</math> (with multiplicity) and the sum of <math>2^{-k}</math> over all negative elements and choose <math>x_n</math> according to which was bigger. Although that wouldn't minimize the discrepancy at each stage, it might make the sequence better for future development because it wouldn't sacrifice the needs of an overwhelming majority to those of a few rogue elements.

The motivation for these experiments is to see whether they, or some variants, appear to lead to sublogarithmic growth. If they do, then we could start trying to prove rigorously that sublogarithmic growth is possible. I still think that a function that arises in nature and satisfies f(1124)=2 ought to be sublogarithmic.
</blockquote>

*What happens if one applies a backtracking algorithm to try to extend the following discrepancy-2 sequence, which satisfies <math>x_{2n}=-x_n</math> for every n, to a much longer discrepancy-2 sequence: + - - + - + + - - + + - + - + + - + - - + - - + + - - + + - + - - + - - + + + + - - - + + + - - + - + + - + - - + - ?

* Investigate what happens if our HAPs are restricted to allow differences divisible only by 2 or 3 [and then other sets of primes including 2] - {2,3,5,7} would be interesting - is there an infinite sequence of discrepancy 2 in these simple cases - is it easy to find an infinite sequence with finite discrepancy in these cases? [for sets of odd primes, take a sequence which is 1 on odd numbers, -1 on even numbers, including 2 is the non-trivial case]

* ... you are welcome to add more.

T2(x) = -T(x)

2010-01-10T19:04:16Z

SuneJ: T2(x) = -T(x) moved to T2(x) = -x

#REDIRECT [[T2(x) = -x]]

T2(x) = -x

2010-01-10T19:04:16Z

SuneJ: T2(x) = -T(x) moved to T2(x) = -x

This sequence, of length <math>594</math>, satisfies <math>x_{2n} = -x_n</math> for all <math>n</math>:

0+--+-++--+--+-++-++--+-++--+--+-++
--+-++-+--++--+-++-++--+-++--+--+-+
+-++--+--+-++--++++--+--+-++-++----
+++-+--+-++--+--+-++-++--+-++-++--+
-++--+--+-++--+-++-++--+--+-++-+-+-
+--+++---+-++-++--+--+--+-++-+++-+-
---+-+++-++-+---+--+-++-++--+++---+
--+-+++-+--+-++-++--+-++--+--+-++-+
+----++-++--+-++--+--+-++-++--++-+-
++--+--+-++-++-+---+--+-++--++--++-
-++-++---+-++-+-++-++--+-++--+--+-+
+--+-++--+-++-++--+--+--+-+-++--++-
+-+-++--++-+-+--+--+-++--++++-+---+
-++-++--+-++--+--+++--+---++-+++--+
+-+---++-+-+--++--+++---++-+-++--+-
-+-++--++---++-++--+-+--+++-+-++---
-++++-+-+--+--++---++++--++--+-++-+

Here's one of length <math>584</math>, which held the record for about ten minutes:

0+--+-++--++---++-+--+-++++-+--+-++---+-++--+
+-+-+-+-++---+-++--++---++-+++---++-+--+++---
-++--+++-++---+--+-++++-+---+--+-++-++---++-+
++--+--+--+-+-++-+++----+++--+-++-+-+--+++-+-
+----++-+--+-+-+++-+-++-+-+---+-+--+++-+-+-+-
-++--+++-+---+++--++--+-++--+--+-+-++-+--++-+
-+--+++---+++---+++--++--++----+++-+---++-+-+
++--+---++-+--+++-+--++--++--+++--+-+--++--++
-++-+-+-+--+--++--+++--++---++---+-+++-++--+-
-++--++--+-+++--++--++-+--+-+-++---++-++---++
+----++-++-+-+-++--++-+-+--+-+--+-+--+-++-++-
++--+--+-+--++-++--++--++-+-++---+++--+--++-+
+---+++--+-+--+-+-++-+-+-++-+-+--+-+--+-++---

A more colourful display of this sequence can be found [http://thomas1111.wordpress.com/2010/01/10/a-sequence-of-584-elements-with-t2x-tx/ on this page].

The Erdős discrepancy problem

2010-01-09T21:44:33Z

SuneJ: /* Some definitions and notational conventions */

==Introduction and statement of problem==

The Erdős discrepancy problem is a problem that has been around since the 1930s and has resisted attack ever since. It is extremely easy to state, and a very appealing problem, so perhaps Polymath can succeed where individual mathematicians have failed. If so, then, given the notoriety of the problem, it would be a significant coup for the multiply collaborative approach to mathematics. But even if a full solution is not reached, preliminary investigations have already thrown up some interesting ideas, which could perhaps be developed into publishable results.

To state the problem, we first define a homogeneous arithmetic progression to be a set of positive integers of the form {d,2d,3d,...,nd}. (It is also reasonable to define it to be a set of non-negative integers of the form {0,d,2d,3d,...,nd}: at the time of writing it is not clear what the "official" definition should be.) Suppose that we have a sequence <math>x_1,x_2,x_3,\dots</math> of elements of the set <math>\{-1,1\}</math> (henceforth to be referred to as a <math>\pm 1</math> sequence). We say that the discrepancy of the sequence <math>(x_n)</math> with respect to a set A of positive integers is <math>|\sum_{n\in A}x_n|</math>. The reason for this name is that we can think of the sequence as a red/blue-colouring of the positive integers, and the discrepancy with respect to A is then the difference between the number of red elements of A and the number of blue elements of A. The Erdős discrepancy problem is the following question.

Problem. Let <math>(x_n)</math> be a <math>\pm 1</math> sequence. Must it be the case that for every constant C there exists a homogeneous arithmetic progression P such that the discrepancy of the sequence <math>(x_n)</math> with respect to P is at least C?

==Some definitions and notational conventions==

A homogeneous arithmetic progression, or HAP, is an arithmetic progression of the form {d,2d,3d,...,nd}.

The discrepancy of a sequence <math>(x_n)</math> is the supremum of <math>|\sum_{n\in P}x_n|</math> over all homogeneous arithmetic progressions P.

A sequence <math>(x_n)</math> has discrepancy at most φ(n) if for every natural number N the maximum value of <math>|\sum_{n\in P}x_n|</math> over all homogeneous arithmetic progressions P that are subsets of {1,2,...,N} is at most φ(N).

The EDP is the Erdős discrepancy problem. (This may conceivably be changed if enough people don't like it.)

A sequence <math>(x_n)</math> is completely multiplicative if <math>x_{mn}=x_mx_n</math> for any two positive integers m and n. We shall sometimes abbreviate this to "multiplicative", but the reader should be aware that the word "multiplicative" normally refers to the more general class of sequences such that <math>x_{mn}=x_mx_n</math> whenever m and n are coprime.

A HAP-subsequence of a sequence <math>(x_n)</math> is a subsequence of the form <math>x_d,x_{2d},x_{3d},\dots</math> for some d. If <math>(x_n)</math> is a multiplicative sequence, then every HAP-subsequence is equal to either <math>(x_n)</math> or <math>(-x_n)</math>. We shall call a sequence weakly multiplicative if it has only finitely many distinct HAP-subsequences. Let us also call a <math>\pm 1</math> sequence quasi-multiplicative if it is a composition of a completely multiplicative function from <math>\mathbb{N}</math> to an Abelian group G with a function from G to {-1,1} (This definition is too general. See [http://gowers.wordpress.com/2010/01/09/erds-discrepancy-problem-continued/#comment-4843 this and the next comment]). [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4705 It can be shown] that if <math>(x_n)</math> is a weakly multiplicative sequence, then it has an HAP-subsequence that is quasi-multiplicative.

==Simple observations==

*To answer the problem negatively, it is sufficient to find a completely multiplicative sequence (that is, a sequence <math>(x_n)</math> such that <math>x_{mn}=x_mx_n</math> for every m,n) such that its partial sums <math>x_1+\dots+x_n</math> are bounded. First mentioned in the proof of the theorem in [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/ this] post.

*The function that takes n to 1 if the last non-zero digit of n in its ternary representation is 1 and -1 if the last non-zero digit is 2 is completely multiplicative and the partial sum up to n is easily shown to be at most <math>\log_3n +1</math>. Therefore, the rate at which the worst discrepancy grows, as a function of the length of the homogeneous progression, can be as slow as logarithmic. [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/] <s>[http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4553 It turns out] that the base can be made significantly higher than 3, so this example is not best possible.</s> [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4757 Correction]

*To answer the problem negatively, it is also sufficient to find a completely multiplicative function f from <math>\mathbb{N}</math> to a finite Abelian group G (meaning that f(mn)=f(m)+f(n) for every m,n) and a function h from G to {-1,1} such that for each g in G there exists d with f(d)=g and with the partial sums hf(d)+hf(2d)+...+hf(nd) bounded. In that case, one can set <math>x_n=hf(n)</math>. (Though this observation is simple with the benefit of hindsight, it might not have been made had it not been for the fact that this sort of structure was identified in a long sequence that had been produced experimentally). First mentioned [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4696 here]. Se also [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/ this post] and [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4717 this comment].

*[http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4705 It can be shown] that if a <math>\pm 1</math> sequence <math>(x_n)</math> starts with 1 and has only finitely many distinct subsequences of the form <math>(x_d,x_{2d},x_{3d},\dots)</math>, then it must have a subsequence that arises in the above way. (This was mentioned just above in the terminology section.)

*The problem for the positive integers is equivalent to the problem for the positive rationals. [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4676](Sketch proof: if you have a function f from the positive integers to {-1,1} that works, then define <math>f_q(x)</math> to be f(q!x) whenever q!x is an integer. Then take a pointwise limit of a subsequence of the functions <math>f_q</math>.)

==Experimental evidence==

A nice feature of the problem is that it lends itself well to investigation on a computer. Although the number of <math>\pm 1</math> sequences grows exponentially, the constraints on these sequences are such that depth-first searches can lead quite quickly to interesting examples. For instance, at the time of writing they have yielded a sequence of length 1124 with discrepancy 2. See [[Experimental results|this page]] for more details about this and for further links.

==Annoted Bibliography==

*Mathias, A. R. D. [http://www.dpmms.cam.ac.uk/~ardm/erdoschu.pdf On a conjecture of Erdős and Čudakov]. Combinatorics, geometry and probability (Cambridge, 1993).

This is a short paper establishing the maximal length of sequence for the case where C=1 is 11, and is the starting point for our experimental studies.

*Borwein, Peter, and Choi, Stephen. [http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P204.pdf A variant of Liouville's lambda function: some surprizing formulae].

Explicit formulas for the discrepancy of some completely multiplicative functions whose discrepancy is logarithmic. A typical example is: Let <math>\lambda_3(n) = (-1)^{\omega_3(n)}</math> where <math>\omega_3(n)</math> is the number of distinct prime factors congruent to <math>-1 \bmod 3</math> in <math>n</math> (with multiple factors counted multiply). Then the discrepancy of the <math>\lambda_3</math> sequence up to <math>N</math> is exactly the number of 1's in the base three expansion of <math>N</math>.

*Vijay, Sujith. [http://www.combinatorics.org/Volume_15/PDF/v15i1r104.pdf On the discrepancy of quasi-progressions]. Electronic Journal of Combinatorics, R104 of Volume 15(1), 2008.

A quasi-progression is a sequence of the form <math>\lfloor k \alpha \rfloor </math>, with <math>1\leq k \leq K</math> for some K. The main theorem of interest is: If the integers from 0 to n are 2-coloured, there exists a quasi-progression that has discrepancy at least <math> (1/50)n^{1/6}</math>.

*Granville and Soundararajan. [http://arxiv.org/abs/math/0702389 Multiplicative functions in arithmetic progressions]

In this [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4729 blog post] Terry Tao wrote: "Granville and Soundararajan have made some study of the discrepancy of bounded multiplicative functions. The situation is remarkably delicate and number-theoretical (and is closely tied with the Granville-Soundararajan theory of pretentious characters)."

*[http://www.math.niu.edu/~rusin/known-math/93_back/prizes.erd As this web page reveals], the Erdős discrepancy problem was a $500-dollar problem of Erdős, so it is clear that he regarded it as pretty hard.

Length 1124 sequences

2010-01-09T21:40:38Z

2010-01-09T19:15:15Z

SuneJ:

I think the method used to find it was the same as for the first one. A I understand it, Klas has a program that searches for sequences of length over <math>100n</math> extended from a list of sequences of length <math>25</math> that he already knows are extendable to length <math>100(n-1)</math>. So far he's posted three sequences of length over <math>1000</math> generated in this way, of which two have yielded sequences of length <math>1124</math> by using them as initial nodes in a depth-first search.

Ok, I thought you used a (p,q) trick that you didn't use the first time? I no one minds, I will keep two pages about 1124 sequences: One about the first (since we have lot about that one), and one about all of them. Perhaps they will turn into one page about our analyses of the sequences and one page about how we found them. --[[User:SuneJ|SuneJ]] 19:15, 9 January 2010 (UTC)

Experimental results

2010-01-09T19:09:29Z

SuneJ:

To return to the main Polymath5 page, click [[The Erdős discrepancy problem|here]].

* [[The first 1124-sequence]] with discrepancy 2. ''Some more description''
* Other [[length 1124 sequences]] with discrepancy 2. ''Some more description''
* Some data about the problem with [[different upper and lower bound]]. ''Some more description''
* Sequences taking values in <math>\mathbb{T}</math>:
** [[4th roots of unity]]
** [[6th roots of unity]]

4th roots of unity

2010-01-09T19:06:38Z

SuneJ: New page: This page is about sequences that takes 4th root of unity as values. The longest ''known'' sequence with discrepancy <math>\sqrt{2}</math> has length 314. ==Method== Here should be a s...

This page is about sequences that takes 4th root of unity as values.

The longest ''known'' sequence with discrepancy <math>\sqrt{2}</math> has length 314.

==Method==

Here should be a short description of the way the sequence was found. (The code(s) used should be further down this page.)

== Status ==

Is the data still relevant (e.g. longest know)? Is the method still relevant, or have we found a better method? Is the program still running on a computer somewhere?

== The data==

If the <math>x_n</math> are allowed to be any of the four points <math>(\pm 1, 0)</math> and <math>(0, \pm 1)</math>, and one requires all sums along HAPs to belong to one of the nine points at unit spacing centred on the origin, the maximum length of a sequence is ''at least'' <math>314</math>. The following sequence achieves this:

(1, 0), (0, 1), (-1, 0), (1, 0), (-1, 0), (0, -1), (0, 1), (-1, 0), (1, 0), (1, 0), (0, -1), (-1, 0), (-1, 0), (0, -1), (1, 0), (1, 0), (-1, 0), (0, 1), (1, 0), (-1, 0), (0, -1), (-1, 0), (0, 1), (1, 0), (0, -1), (1, 0), (-1, 0), (0, 1), (1, 0), (-1, 0), (0, -1), (-1, 0), (0, 1), (0, -1), (1, 0), (1, 0), (-1, 0), (-1, 0), (1, 0), (1, 0), (0, 1), (0, 1), (-1, 0), (0, -1), (-1, 0), (1, 0), (1, 0), (-1, 0), (0, -1), (0, 1), (1, 0), (-1, 0), (1, 0), (0, -1), (0, 1), (0, -1), (-1, 0), (0, 1), (-1, 0), (1, 0), (0, -1), (-1, 0), (0, 1), (1, 0), (0, -1), (1, 0), (0, 1), (0, 1), (0, -1), (-1, 0), (1, 0), (-1, 0), (-1, 0), (1, 0), (0, 1), (1, 0), (-1, 0), (-1, 0), (1, 0), (-1, 0), (1, 0), (0, -1), (0, 1), (0, -1), (0, -1), (0, 1), (-1, 0), (0, 1), (0, -1), (1, 0), (1, 0), (-1, 0), (0, 1), (0, -1), (0, 1), (1, 0), (0, -1), (0, 1), (0, -1), (0, -1), (0, 1), (0, 1), (-1, 0), (1, 0), (-1, 0), (0, -1), (1, 0), (-1, 0), (-1, 0), (0, -1), (1, 0), (0, 1), (-1, 0), (1, 0), (1, 0), (0, -1), (-1, 0), (0, 1), (1, 0), (-1, 0), (1, 0), (-1, 0), (0, -1), (1, 0), (0, 1), (0, -1), (-1, 0), (-1, 0), (1, 0), (0, 1), (0, -1), (0, 1), (-1, 0), (1, 0), (1, 0), (0, -1), (0, 1), (-1, 0), (0, -1), (1, 0), (-1, 0), (0, 1), (0, 1), (1, 0), (-1, 0), (0, -1), (0, 1), (-1, 0), (1, 0), (0, -1), (1, 0), (-1, 0), (-1, 0), (1, 0), (0, 1), (1, 0), (0, -1), (-1, 0), (-1, 0), (1, 0), (0, -1), (0, 1), (0, 1), (-1, 0), (0, -1), (0, -1), (0, 1), (0, 1), (0, -1), (0, 1), (1, 0), (1, 0), (-1, 0), (0, -1), (-1, 0), (0, -1), (1, 0), (0, 1), (1, 0), (-1, 0), (0, -1), (-1, 0), (0, 1), (1, 0), (0, -1), (1, 0), (0, 1), (0, 1), (0, -1), (0, -1), (0, 1), (-1, 0), (-1, 0), (1, 0), (0, 1), (0, -1), (1, 0), (-1, 0), (0, -1), (0, 1), (0, -1), (-1, 0), (0, 1), (0, -1), (1, 0), (1, 0), (0, 1), (-1, 0), (0, -1), (1, 0), (0, 1), (0, 1), (-1, 0), (-1, 0), (0, -1), (1, 0), (-1, 0), (1, 0), (1, 0), (0, 1), (0, -1), (-1, 0), (0, 1), (0, -1), (0, -1), (1, 0), (0, 1), (-1, 0), (1, 0), (-1, 0), (1, 0), (0, 1), (-1, 0), (1, 0), (-1, 0), (1, 0), (-1, 0), (-1, 0), (1, 0), (1, 0), (0, -1), (-1, 0), (-1, 0), (0, -1), (1, 0), (0, 1), (0, 1), (-1, 0), (0, -1), (0, -1), (1, 0), (0, 1), (-1, 0), (1, 0), (0, 1), (1, 0), (-1, 0), (-1, 0), (1, 0), (-1, 0), (1, 0), (1, 0), (-1, 0), (0, -1), (0, -1), (0, 1), (0, 1), (0, -1), (1, 0), (-1, 0), (-1, 0), (0, 1), (0, -1), (1, 0), (0, 1), (1, 0), (-1, 0), (-1, 0), (0, -1), (0, -1), (1, 0), (0, 1), (0, -1), (-1, 0), (1, 0), (1, 0), (0, 1), (-1, 0), (0, -1), (1, 0), (-1, 0), (1, 0), (0, 1), (0, -1), (-1, 0), (0, 1), (0, 1), (0, -1), (1, 0), (0, 1), (-1, 0), (-1, 0), (1, 0), (0, -1), (0, 1), (1, 0), (-1, 0), (-1, 0), (0, -1), (1, 0), (1, 0), (0, -1), (0, 1), (0, 1)

--[[User:Alec|Alec]] 14:42, 9 January 2010 (UTC)

== Relevant code ==
The code(s) (or a link to the code(s)) used to find this sequence should be posted here.

6th unity roots

2010-01-09T19:01:18Z

SuneJ: 6th unity roots moved to 6th roots of unity

#REDIRECT [[6th roots of unity]]

6th roots of unity

2010-01-09T19:01:18Z

SuneJ: 6th unity roots moved to 6th roots of unity

This page is about sequences that takes 6th root of unity as values.

The longest sequence with discrepancy 1 has length 116.

==Method==

Here should be a short description of the way the sequence was found. (The code(s) used should be further down this page.)

== Status ==

Is the data still relevant (e.g. longest know)? Is the method still relevant, or have we found a better method? Is the program still running on a computer somewhere?

== The data==

If the <math>x_n</math> are allowed to be any of the six points of a regular hexagon, and one requires all sums along HAPs to be zero or one of those same points, the maximum length of a sequence is <math>116</math>. The following sequence achieves this, where the numbers index the points in order around the hexagon:

-, 0, 3, 3, 0, 3, 0, 2, 4, 0, 1, 4, 3,
1, 5, 0, 2, 4, 3, 1, 5, 5, 1, 4, 1, 2,
5, 3, 2, 5, 4, 1, 4, 1, 2, 5, 0, 2, 4,
4, 1, 5, 2, 1, 4, 3, 1, 5, 5, 2, 4, 1,
2, 4, 0, 1, 5, 4, 1, 4, 2, 2, 4, 0, 1,
5, 4, 2, 5, 1, 2, 4, 3, 1, 5, 5, 1, 4,
1, 3, 4, 2, 1, 0, 4, 1, 4, 3, 1, 5, 0,
2, 4, 5, 2, 4, 1, 1, 5, 3, 2, 0, 3, 4,
5, 1, 1, 3, 4, 1, 5, 0, 2, 4, 1, 3, 5

Here are some of its HAP subseqences, which seem to show the presence of some kind of multiplicative structure, though the structure seems to degenerate as the sequences progress.

====The 2-sequence====

3, 0, 0, 4, 1, 3, 5, 2, 3, 5, 1, 1, 5, 2, 4, 4, 2, 0, 4, 1, 2, 4, 1, 5, 4, 2, 0, 5, 1, 2, 4, 1, 4, 5, 2, 3, 5, 1, 1, 4, 1, 4, 4, 1, 0, 4, 2, 1, 5, 2, 3, 5, 1, 4, 5, 2, 1, 5

====The 3-sequence====

3, 0, 0, 3, 0, 3, 5, 1, 3, 4, 1, 0, 4, 2, 3, 5, 1, 0, 4, 2, 0, 4, 1, 3, 5, 1, 2, 4, 3, 0, 5, 1, 3, 3, 1, 4, 0, 1

====The 4-sequence====

0, 4, 3, 2, 5, 1, 2, 4, 0, 1, 4, 5, 2, 5, 2, 1, 5, 3, 1, 4, 4, 1, 4, 1, 2, 5, 4, 2, 5

====The 5-sequence====

3, 1, 0, 5, 2, 4, 5, 1, 3, 4, 1, 2, 5, 2, 5, 4, 1, 0, 4, 2, 1, 5, 3

====The 6-sequence====

0, 3, 3, 1, 4, 0, 2, 5, 0, 2, 4, 3, 1, 4, 0, 1, 3, 4, 1

====The 8-sequence====

4, 2, 1, 4, 1, 5, 5, 1, 3, 4, 1, 1, 5, 2

====The 9-sequence====

0, 3, 3, 0, 3, 0, 0, 3, 2, 0, 3, 4

====The 10-sequence====

1, 5, 4, 1, 4, 2, 2, 4, 0, 2, 5

====The 12-sequence====

3, 1, 0, 5, 2, 3, 4, 1, 4

== Relevant code ==
The code(s) (or a link to the code(s)) used to find this sequence should be posted here.

Different upper and lower bound

2010-01-09T19:00:37Z

SuneJ: /* Status */

If <math>N(a,b)</math> is the maximum length of a <math>\pm 1</math> sequence with the partial sums along its HAPs bounded below by <math>-a</math> and above by <math>b</math>, then:

<math>N(a, b) = N(b, a)</math>

<math>N(0, b) = b</math> (everything must be <math>+1</math>)

<math>N(1, 1) = 11</math> (there are <math>4</math> such sequences: choose <math>x_1</math>, and use the constraints <math>x_n +x_{2n} = 0</math> and <math>x_1 + \ldots + x_{2n} = 0</math> to determine the entries up to <math>10</math>; then choose <math>x_{11}</math>)

<math>N(1, 2) = 41</math> (there are <math>4</math> such sequences -- example below)

<math>N(1, 3) = 83</math> (there are <math>216</math> such sequences -- example below)

<math>N(1, 4) = 131</math> (there are <math>87144</math> such sequences -- example below)

<math>N(1,b)<\infty</math> ([http://www.dpmms.cam.ac.uk/~ardm/erdoschu.pdf On a conjecture of Erdős and Čudakov])

<math>N(2, 2) \geq 1124</math> (e.g [[the first 1124-sequence]])

For the zero-based problem, see [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4822 this commend]

==Method==

Here should be a short description of the way the sequences was found. (The code(s) used should be further down this page.)

== Status ==

Is the data still relevant (e.g. longest know)? Is the method still relevant, or have we found a better method? Is the program still running on a computer somewhere?

== The data==

<math>N(1, 2) = 41</math> (there are <math>4</math> such sequences -- example below)

0 + - - + - + + - + + - - +
- + + - + - - - + - + + - -
+ + - + - + + - - - + - + +

<math>N(1, 3) = 83</math> (there are <math>216</math> such sequences -- example below)

0 - + - + - + + - + + - - +
- + + - - + - - + - + + - +
+ + - - - + + - + + - - + -
+ - - + + - - + - + + + - +
- - - + + - + - + - - + - +
+ - + + - - + - + - - - + +

<math>N(1, 4) = 131</math> (there are <math>87144</math> such sequences -- example below)

0 + - - + - + + - - + -
+ + - + + + + - - - + -
- + - + + - - + + + - -
- + + - + - + - - + + -
+ + - - + - - + - + + +
+ - - + - + - - + + + -
+ - - - - + + - - - + +
- - + + + + - - - - + +
- + - + + + + - - + + -
+ - - - + + - - - + - -
+ + + - + + - - + - - +

<math>N(2, 2) \geq 1124</math>

--[[User:Alec|Alec]] 13:46, 9 January 2010 (UTC)

==Relevant code==

The code(s) (or a link to the code(s)) used to find this sequence should be posted here.

Experimental results

2010-01-09T19:00:04Z

SuneJ:

2010-01-09T11:29:34Z

SuneJ:

== Terminology for zero-based APs ==

Could we abbreviate 'zero-based arithmetic progression' to ZAP (the 'H' for 'homogeneous' being redundant)? We'd then need a term for the discrepancy with respect to ZAPs, such as Z-discrepancy, unless it's clear from the context.

== Repository of examples ==

We could do with a place on this Wiki to post interesting examples of sequences, and perhaps other experimental data, since currently they're scattered around the blog and I have one or two I'd like to add. In particular a page of 'longest sequences found so far' for various constraints and dimensions would be nice.

--[[User:Alec|Alec]] 09:01, 9 January 2010 (UTC)

You could place it in [[Experimental results]]. It would be great if we could use the wiki to post more information than we can on the blog. E.g: Short description of the program used to find the example, the program/code itself, status of the program (are we trying to find longer sequences with this program, or why not) and author of the program.
Perhaps we could also create wish list: A page that only contains the short description of programs that have not been written.
--[[User:SuneJ|SuneJ]] 09:18, 9 January 2010 (UTC)

== quasi-multiplicative sequence ==

"Let us also call a <math>\pm 1</math> sequence quasi-multiplicative if it is a composition of a completely multiplicative function from <math>\mathbb{N}</math> to an Abelian group G with a function from G to {-1,1}."
Every <math>\pm 1</math> sequence is on this form. E.g. take G=Q and let the function be the inclusion function. Do you mean "to a finite Abelian group G"? --[[User:SuneJ|SuneJ]] 11:29, 9 January 2010 (UTC)

Talk:The Erdős discrepancy problem

2010-01-09T11:29:18Z

SuneJ: /* quasi-multiplicative sequence */ new section

== Terminology for zero-based APs ==

Could we abbreviate 'zero-based arithmetic progression' to ZAP (the 'H' for 'homogeneous' being redundant)? We'd then need a term for the discrepancy with respect to ZAPs, such as Z-discrepancy, unless it's clear from the context.

== Repository of examples ==

We could do with a place on this Wiki to post interesting examples of sequences, and perhaps other experimental data, since currently they're scattered around the blog and I have one or two I'd like to add. In particular a page of 'longest sequences found so far' for various constraints and dimensions would be nice.

--[[User:Alec|Alec]] 09:01, 9 January 2010 (UTC)

You could place it in [[Experimental results]]. It would be great if we could use the wiki to post more information than we can on the blog. E.g: Short description of the program used to find the example, the program/code itself, status of the program (are we trying to find longer sequences with this program, or why not) and author of the program.
Perhaps we could also create wish list: A page that only contains the short description of programs that have not been written.
--[[User:SuneJ|SuneJ]] 09:18, 9 January 2010 (UTC)

== quasi-multiplicative sequence ==

"Let us also call a <math>\pm 1</math> sequence quasi-multiplicative if it is a composition of a completely multiplicative function from <math>\mathbb{N}</math> to an Abelian group G with a function from G to {-1,1}."
Every <math>\pm 1</math> sequence is on this form. E.g. take G=Q and let the function be the inclusion function. Do you mean "to a finite Abelian group G"?

Talk:The Erdős discrepancy problem

2010-01-09T09:18:31Z

SuneJ:

The Erdős discrepancy problem

2010-01-07T16:32:06Z

SuneJ: /* Simple observations */ Corrected parenthesis mismatch

The Erdős discrepancy problem

2010-01-07T15:49:51Z

SuneJ: /* Simple observations */ Links have been added (unless you meant link to other wikipages?)