## Polymath5 – A collection of results concerning the completely multiplicative case

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 ${\{\pm 1\}}$. That has some justification since there are results reducing the problem to the completely multiplicative case (albeit with values in ${S_1}$). 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 ${f:\mathbb{N}\rightarrow\{\pm 1\}}$ with the following properties:

• ${f}$ is completely multiplicative, i.e. ${f(m n)=f(m) f(n) }$ for all ${m,n\in\mathbb{N}}$.
• ${f}$ has bounded partial sums (bounded discrepancy), i.e. there is a ${C>0}$ such that ${\left|\sum_{n\leq x}f(n)\right|\leq C}$ for all ${x\in\mathbb{R}}$.

Let me fix some notation before I present examples related to the above question. In the following ${f}$ denotes a completely multiplicative function with values in ${\{\pm 1\}}$, ${p,q}$ denote primes and ${s=\sigma + i t}$ is a complex number with real part ${\sigma}$ and imaginary part ${t}$.

Examples related to the problem.

• ${f(n)=1}$ for all ${n\in\mathbb{N}}$ is completely multiplicative and has unbounded discrepancy ${\sum_{n\leq x}1=\lfloor x\rfloor}$.
• Liouville function ${\lambda(p):=-1}$ for all primes ${p}$.
• Dirichlet characters of modulus ${k}$ are completely multiplicative with values in ${\{0\}\cup\{e^{2 \pi i n / k}:1\leq n \leq k\}}$. Since Dirichlet characters assume the value ${0}$ they are strictly speaking not in the focus of this post. However, they can be used to construct ${\{\pm 1\}}$-valued examples (cf. the next example) and they play a central role in the discussions.
• The functions $\displaystyle \mu_p(q):=\left\{ {(\frac{q}{p}) \textnormal{ if } q\not= p} \atop -1 {\textnormal{ if } q=p}\right.$ and $\displaystyle \lambda_p(q):=\left\{ {(\frac{q}{p}) \textnormal{ if } q\not= p} \atop 1 {\textnormal{ if } q=p}\right.$with ${(\frac{q}{p})}$ being the quadratic Dirichlet character mod ${p}$ (Legendre symbol) and ${p}$ an odd prime.
• To generalize the last example fix ${m \in \mathbb{N}}$ and a set ${S\subseteq \{1,\ldots, m-1\}}$. Define ${\lambda_{m,S}(n):=1}$ if the last non-zero digit of ${n}$ in its ${m}$-ary representation is in ${S}$. In all other cases ${\lambda_{m,A}(n):=-1}$. Immediately from the definition we find $\displaystyle \lambda_{m,S}(n+l)=\lambda_{m,S}(n)$ if ${\textnormal{ord}_m l>\textnormal{ord}_m n}$. To not obtain unbounded discrepancy it is necessary that ${\sum_{i=1}^{m/d-1}\lambda_{m,S}(i)=0}$ for ${1. Moreover, we find ${\sum_{i=1}^{n}\lambda_{m,S}(i)=\sum_{j=0}^l \sum_{i=1}^{d_j}\lambda_{m,S}(i) }$ which implies logarithmic growth. Since ${\lambda_{m,S}}$ is completely multiplicative we have ${\lambda_{m,S}(n)=1 }$ if n is a quadratic residue mod ${m}$, implying ${\lambda_{p,S}=\lambda_p}$ for ${p}$ an odd prime. We construct some ${\lambda_{m,S}}$ for small composite ${m}$:
• For ${m=9}$ we have for the quadratic residues ${\{1,4,7\} \subseteq S}$ and thus depending on whether we include ${3}$ either ${\lambda_{9,\{1,3,4,7\}}=\lambda_3}$ or ${\lambda_{9,\{1,4,6,7\}}=\mu_3}$.
• For ${m=15}$ we get ${\{1,4,6,9,10\} \subseteq S}$. Since ${\sum_{i=1}^4 \lambda_{15,S}(i)=0}$ for all ${S}$ we cannot include ${2}$ and ${3}$. Because ${10}$ is included this forces ${\lambda_{15,S}(5)=-1}$ for all ${S}$. Now using complete multiplicativity and ${\sum_{i=1}^{14} \lambda_{15,S}(i)=0}$ we get the four cases: ${S_{15,\{1,4,6,9,10,11,14\}}}$, ${S_{15,\{1,4,6,7,9,10,11\}}}$, ${S_{15,\{1,4,6,9,10,13,14\}}}$ and ${S_{15,\{1,4,6,7,9,10,13\}}}$.
• For ${m=21}$ we have that ${9^2\equiv 18 \mod 21}$. Thus ${1=\lambda_{21,S}(18)=\lambda_{21,S}(2)}$. Since ${3|21}$ we have ${\sum_{i=1}^2\lambda_{21,S}(i)=0}$, a contradiction.

Necessary conditions for bounded discrepancy.

• If ${f}$ has bounded partial sums, then the Dirichlet series ${\sum_{n\leq x} \frac{f(n)}{n^s}}$ converges for ${\sigma>0}$. Proof idea: Integration by parts.
• If ${f}$ has bounded partial sums, then ${\sum_{p\leq x} \frac{f(p)}{p}=A+O\left(\frac{1}{\log{x}}\right)}$. Proof idea: One first establishes ${\sum_{p\leq x} \frac{f(p)\log{p}}{p}=O(1)}$ 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 ${\sum_ {p\leq x} \frac{1}{p}}$.
• If ${f}$ has bounded partial sums, then for infinitely many primes ${p}$ one has ${f(p)=1}$ and for infinitely many primes ${q}$ one has ${f(q)=-1}$. Proof idea: Otherwise one would get a contradiction to the standard result on the growth of ${\sum_{p\leq x} \frac{1}{p}}$.
• With not so elementary methods one can prove results ‘in the spirit of’: Let ${f:\mathbb{N}\rightarrow S_1}$ have bounded partial sums and let ${\chi}$ be a non-principal Dirichlet character. Then ${\sum_{p}\frac{|1-f(p)\overline{\chi(p)}|}{p}=\infty}$. Here more serious number theory kicks in and this is probably where most are currently heading to.

Discrepancy results.

• Computer experiments (no link found) show that there are ${f}$ with ${\left|\sum_{n\leq x}f(n)\right|\leq 2}$ for all ${x\leq 246}$. No such sequence exists for ${x=247}$. There is no traditional proof of this, not even for ${x=\infty}$.
• Liouville’s function does not have bounded partial sums since its Dirichlet series equals ${\frac{\zeta(2 s)}{\zeta(s)}}$ and thus has a singularity at ${s=\frac{1}{2}}$.Alternatively one can proceed as in the proof of Dirichlet’s theorem on primes in arithmetic progressions and apply Dirichlet’s hyperbola method to ${A(x):= \sum_{n\leq x}\frac{1*\lambda(n)}{\sqrt{n}}}$ ultimately showing that under the assumption of bounded partial sums ${A(x)}$ grows like ${\sqrt{x}}$. This is a contradiction since ${A(x)}$ grows logarithmically. Showing that the discrepancy of the Liouville function is ${O(n^{1/2+\varepsilon})}$ for all ${\varepsilon>0}$ is equivalent to solving the Riemann hypothesis.
• For primitive Dirichlet characters ${\chi}$ mod ${k}$ one has ${\max_{n\leq x}\left|\sum_{i\leq n}\chi(i) \right|\geq \frac{\sqrt{k}}{2\pi}}$. Proof idea: Apply partial summation to the associated Gauss sum ${G(1,\chi):=\sum_{1\leq m\leq k} \chi(m) e^{2 \pi i m /k}}$ and use ${|G(1,\chi)|^2=k}$.
• We have ${\mu_3(n) = \lambda_{9,\{1,4,6,7\}}(n)}$ and  $\displaystyle \left|\sum_{i=1}^n\mu_3(i)\right|\leq\log_9(8n+1)$ with equality holding only for ${n=\frac{9^m-1}{8}}$ and ${m\in\mathbb{N}}$.
• ${\mu_3}$ is optimal in the following sense: $\displaystyle \limsup_{x\rightarrow\infty}\frac{\left|\sum_{n\leq x}\mu_p(n)\right|}{\log{x}}\geq \frac{1}{2 \log{3}}$ with equality holding only for ${p=3}$. Proof idea: One constructs a sequence ${x_i}$ such that ${\lim_{x_i\rightarrow\infty}\frac{\left|\sum_{n\leq x_i}\mu_p(n)\right|}{\log{x_i}}\geq \frac{M_p-m_p}{2\log{p}}}$ with ${M_p:=\max_{1\leq n< p}\sum_{1\leq i\leq n} (\frac{i}{p})}$ and ${m_p:=\min_{1\leq n< p}\sum_{1\leq i\leq n} (\frac{i}{p})}$. 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 ${\lambda_p}$ grow faster than ${\mu_3}$.
• Computer experiments so far did not find a ${\lambda_{m, S}}$ that grows slower than ${\mu_3}$. For a given ${\lambda_{m,S}}$ let ${M_{m,S}:=\max_{1\leq n< m}\left|\sum_{1\leq i\leq n} \lambda_{m,S}(i)\right|}$. Then ${m=39}$ with ${S=}$ $\displaystyle \{1,3,4,9,10,12,13,14,16,19,22,25,27,29,30,31,34,35,36\}$ is the largest ${m}$ such that there is an ${S}$ with ${M_{m,S}=2}$. Proof idea: Do a computer search among all completely multiplicative discrepancy 2 functions with domain ${\{1,\ldots,m-1\}}$ (${m}$ must be less than 247). A ${\lambda_{m, S}}$ beating ${\mu_3}$ thus has at least ${M_{m,S}=3}$ and thus ${\frac{1}{\log 9}>\frac{3}{\log m}}$ implying ${m>729}$.