EDP and some first steps in number theory

February 12, 2011

Last year I have spent some time to think about the Erdös Discrepancy Problem (EDP). My interest was sparked by Tim Gower’s Polymath project and two comments of Terence Tao (1, 2) on the special case of completely multiplicative functions. Let me state this version of EDP.

Problem. Prove or disprove the 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, 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}}.

In his comments Terence Tao describes how one can use ideas of Dirichlet’s proof (of the theorem on primes in arithmetic progressions) to get first an elementary proof of the unboundedness of the summatory Liouville function and second a necessary condition for unbounded discrepancy using properties of {\sum_{p\leq  x}f(p)}. While the ‘positivity’ part is straight forward I had some trouble to fully digest the complex analysis part at the end of his second comment (bounded discrepancy implies {\sum_{p\leq  x} f(p)=o\left(x/ \log x\right)}). However, all this can be achieved with textbook arguments and I took this as an opportunity to learn some (analytic) number theory. In what follows I elaborate some ideas on the analytic number theory approach and (in an upcoming post) on the positivity approach (Dirichlet’s idea).

Analytic Method. To show where we can apply complex analysis let me first repeat a standard argument. Define { \psi_f(x):=\sum_{n\leq  x}f(n)\Lambda(n) } with {\Lambda} being the von Mangoldt function. Plugging in the definition yields

\displaystyle  \psi_f(x)=\sum_{p\leq  x}\sum_{\alpha=1 \atop p^\alpha\leq x} f(p^\alpha)\log p=\sum_{p\leq  x}\log p\sum_{\alpha=1}^{\left\lfloor\log_p x\right\rfloor} f(p)^\alpha.

Separating primes with {f(p)=1} from primes with {f(p)=-1} we find (using {\{x\}:=x-\lfloor  x\rfloor})

\displaystyle   \begin{array}{rcl}  \psi_f(x) & = & \sum_{p\leq x\atop  f(p)=1}\log p\left\lfloor\log_p x\right\rfloor - \sum_{p\leq x,  \left\lfloor\log_p x\right\rfloor \textnormal{ odd}\atop f(p)=-1}\log  p\\ & = & \log x \sum_{p\leq x\atop f(p)=1}1 - \sum_{p\leq  x\atop f(p)=1}\log p\left\{\log_p x\right\} \\ & & \hspace{1cm}-  \sum_{p\leq x, \left\lfloor\log_p x\right\rfloor \textnormal{ odd}\atop  f(p)=-1}\log p. \end{array}

Setting {f(n)=1} for all {n} we find that {\psi(x)= \pi(x)\log  x-\sum_{p\leq x}\log p\left\{\log_p x\right\}} and since {\pi(x)\frac{\log x}{x}=\frac{\psi(x)}{x}+o(1)} we find for all {f}

\displaystyle  \begin{array}{rcl}  0\leq\sum_{2<p\leq x\atop  f(p)=1}\log p\left\{\log_p x\right\} & \leq & \sum_{2<p\leq  x}\log p\left\{\log_p x\right\}\\ & = & -\log 2\left\{\log_2  x\right\}+o(x). \end{array}

Defining {\pi_{f,1}(x):=\sum_{p\leq x\atop  f(p)=1}1} and {\vartheta_{f,-1}(x):=-\sum_{p\leq  x\atop f(p)=-1}\log p} we arrive at the


\displaystyle   \psi_f(x)=\pi_{f,1}(x)\log x +\sum_{1\leq i \textnormal{ odd}}  \left(\vartheta_{f,-1}(x^\frac{1}{i})-  \vartheta_{f,-1}(x^\frac{1}{i+1})\right)+o(x)

The above argument indicates how to proceed. Using analytic number theory similar to the proof of the prime number theorem (PNT) one gets information on {\psi_f(x)} for general {f}. It might even be possible to prove that {f} having bounded partial sums implies {\psi_f(x)=o(x)}, although I have not yet checked the details. If true, we would get a nice analog to the PNT in the (still maybe empty) case of bounded partial sums.

Conjecture. If {f} has bounded partial sums, then

\displaystyle  \pi_{f,1}(x)\frac{\log x}{x} =-\frac{1}{x}\sum_{1\leq i  \textnormal{ odd}} \left(\vartheta_{f,-1}(x^\frac{1}{i})-  \vartheta_{f,-1}(x^\frac{1}{i+1})\right)+o(1).