Polymath5 – A collection of results concerning the completely multiplicative case

March 23, 2011

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<d|m}. 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}.
Advertisements