In this post I have collected results of the fifth Polymath project on the Erdös discrepancy problem. With hundreds and maybe even thousands of posts I have decided to restrict this to the (maybe) simplest non-trivial special case, namely completely multiplicative functions with values in . That has some justification since there are results reducing the problem to the completely multiplicative case (albeit with values in ). Furthermore my focus is on elementary examples related to the problem and how far one can get with textbook methods. It that sense this can be seen as a beginner’s guide with the quoted results being nothing more than exercises. I have arranged the results within the following sections
- Statement of the problem
- Examples related to the problem
- Necessary conditions for bounded discrepancy
- Discrepancy results
What fascinates me about the problem is that it can be stated without much technicalities and that a solution seems to be within reach due to recent results in number theory.
Discrepancy Problem. Find or prove the non-existence of a function with the following properties:
- is completely multiplicative, i.e. for all .
- has bounded partial sums (bounded discrepancy), i.e. there is a such that for all .
Let me fix some notation before I present examples related to the above question. In the following denotes a completely multiplicative function with values in , denote primes and is a complex number with real part and imaginary part .
Examples related to the problem.
- for all is completely multiplicative and has unbounded discrepancy .
- Liouville function for all primes .
- Dirichlet characters of modulus are completely multiplicative with values in . Since Dirichlet characters assume the value they are strictly speaking not in the focus of this post. However, they can be used to construct -valued examples (cf. the next example) and they play a central role in the discussions.
- The functions and with being the quadratic Dirichlet character mod (Legendre symbol) and an odd prime.
- To generalize the last example fix and a set . Define if the last non-zero digit of in its -ary representation is in . In all other cases . Immediately from the definition we find if . To not obtain unbounded discrepancy it is necessary that for . Moreover, we find which implies logarithmic growth. Since is completely multiplicative we have if n is a quadratic residue mod , implying for an odd prime. We construct some for small composite :
- For we have for the quadratic residues and thus depending on whether we include either or .
- For we get . Since for all we cannot include and . Because is included this forces for all . Now using complete multiplicativity and we get the four cases: , , and .
- For we have that . Thus . Since we have , a contradiction.
Necessary conditions for bounded discrepancy.
- If has bounded partial sums, then the Dirichlet series converges for . Proof idea: Integration by parts.
- If has bounded partial sums, then . Proof idea: One first establishes like in the proof of Dirichlet’s theorem on primes in arithmetic progressions. This estimate is then used in the textbook proof on the growth of .
- If has bounded partial sums, then for infinitely many primes one has and for infinitely many primes one has . Proof idea: Otherwise one would get a contradiction to the standard result on the growth of .
- With not so elementary methods one can prove results ‘in the spirit of’: Let have bounded partial sums and let be a non-principal Dirichlet character. Then . Here more serious number theory kicks in and this is probably where most are currently heading to.
- Computer experiments (no link found) show that there are with for all . No such sequence exists for . There is no traditional proof of this, not even for .
- Liouville’s function does not have bounded partial sums since its Dirichlet series equals and thus has a singularity at .Alternatively one can proceed as in the proof of Dirichlet’s theorem on primes in arithmetic progressions and apply Dirichlet’s hyperbola method to ultimately showing that under the assumption of bounded partial sums grows like . This is a contradiction since grows logarithmically. Showing that the discrepancy of the Liouville function is for all is equivalent to solving the Riemann hypothesis.
- For primitive Dirichlet characters mod one has . Proof idea: Apply partial summation to the associated Gauss sum and use .
- We have and with equality holding only for and .
- is optimal in the following sense: with equality holding only for . Proof idea: One constructs a sequence such that with and . With the lower bound for the discrepancy of primitive Dirichlet characters one can eliminate all but finitely many cases. These can then be checked by computer. A similar argument shows that the sums of grow faster than .
- Computer experiments so far did not find a that grows slower than . For a given let . Then with is the largest such that there is an with . Proof idea: Do a computer search among all completely multiplicative discrepancy 2 functions with domain ( must be less than 247). A beating thus has at least and thus implying .