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 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 ${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}$ .

Like this:

Be the first to like this post.

This entry was posted on Wednesday, March 23rd, 2011 at 8:35 pm and is filed under Recreational Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to Polymath5 – A collection of results concerning the completely multiplicative case

Polymath5 – A somewhat surprising observation « Random Thoughts says:

April 5, 2011 at 10:43 am

[...] still is) to find a slowly growing example possibly beating the current record holder (please read my last post for more [...]

Reply

Random Thoughts