## Thursday, October 8, 2015

### Sylvester, On Arithmetical Series, 1892

In Chebyshev's MÃ©moire, which is a famous paper in the history of number theory, Chebyshev obtains bounds on the function \begin{equation*} \psi(x) = \sum_{p^{\alpha} \le x} \log p \end{equation*} where the sum is over prime powers. Sylvester improved Chebyshev's bounds in his paper On Arithmetical Series by applying two strategies:
1. Whereas Chebyshev analyzed the expression \begin{equation*} T(x) - T\left( \frac{x}{2} \right)- T\left( \frac{x}{3} \right)- T\left( \frac{x}{5} \right)+ T\left( \frac{x}{30} \right) \end{equation*} where $T(x) = \sum_{ 1 \le n \le x} \log n\$, Sylvester analyzed more complex expressions, for example \begin{equation*} T(x) - T\left( \frac{x}{2} \right)- T\left( \frac{x}{3} \right)- T\left( \frac{x}{5} \right)+ T\left( \frac{x}{6} \right)-T\left( \frac{x}{7} \right)+ T\left( \frac{x}{70} \right)- T\left( \frac{x}{210} \right) \end{equation*}
2. Sylvester also applied an iterative method so that he could strengthen bounds he obtained in a recursive manner.
Method (1) is explained in part II, §1 of the paper; method (2) in part II, §2. Sylvester obtained the best bounds by combining (1) and (2). The whole exercise is now more of historical interest because the prime number theorem, which is the statement $\psi(x) \sim x$, has been proved four years after the publication of Sylvester's paper. Nevertheless, in this post I will see how method (2) works in a simple situation. I will of course obtain bounds that are weaker than Sylvester's. More elaborations on method (1) can be found in this post.
I start with the expression \begin{equation*} V(x) = T(x) - T\left( \frac{x}{2} \right)-2 T\left( \frac{x}{3} \right)+ T\left( \frac{x}{6} \right) \end{equation*} It then follows that \begin{equation*} V(x) = \psi(x) -\psi\left( \frac{x}{3} \right)+ \psi\left( \frac{x}{5} \right)- \psi\left( \frac{x}{6} \right)+ \psi\left( \frac{x}{7} \right)- \psi\left( \frac{x}{9} \right) + \cdots \end{equation*} Because \begin{equation*} V(x) = B x + O(\log x) \end{equation*} with $B = \frac{1}{6} \log 108$, one can obtain easily (see here for details) that $$\label{20151007startpsi} B x + O(\log^2 x ) \le \psi(x) \le \frac{3}{2} B x + O(\log^2 x )$$ This is numerically \begin{equation*} 0.780355\ x + O(\log^2 x ) \le \psi(x) \le 1.17053\ x + O(\log^2 x ) \end{equation*} Sylvester's recursive method works as follows. Suppose one has already obtained that \begin{equation*} u x + O(\log^2 x ) \le \psi(x) \le v x + O(\log^2 x ) \end{equation*} then one can improve the lower bound as follows. Write $$\label{20151007longupper} \psi(x) = V(x) + \underbrace{\psi\left( \frac{x}{3} \right)- \psi\left( \frac{x}{5} \right)}_{\ge 0}+ \underbrace{\psi\left( \frac{x}{6} \right)- \psi\left( \frac{x}{7} \right)}_{\ge 0}+ \underbrace{\psi\left( \frac{x}{9} \right) - \psi\left( \frac{x}{11} \right)}_{\ge 0} + \cdots$$ I will now keep some of the terms in the right hand side. First, I calculate with the bounds already obtained so far \begin{equation*} \psi\left( \frac{x}{n} \right)-\psi\left( \frac{x}{m} \right) \ge u \frac{x}{n} - v \frac{x}{m} \end{equation*} This is $\ge 0$ if and only if $\frac{m}{n} \ge \frac{v}{u}$. Hence, I will keep the terms $\psi\left( \frac{x}{n} \right)-\psi\left( \frac{x}{m} \right)$ if and only if $\frac{m}{n} \ge \frac{v}{u}$. The rationale is that if $\frac{m}{n} < \frac{v}{u}$, it is better to replace $\psi\left( \frac{x}{n} \right)-\psi\left( \frac{x}{m} \right)$ with the lower bound $0$ instead of $u \frac{x}{n} - v \frac{x}{m}$.
At the start of the iteration, I know from \eqref{20151007startpsi} that \begin{equation*} \frac{v}{u} = \frac{3}{2} \end{equation*} Because $\frac{5}{3} > \frac{3}{2}$, I keep the term $\psi\left( \frac{x}{3} \right)-\psi\left( \frac{x}{5} \right)$. Because $\frac{7}{6} < \frac{3}{2}$, I drop the term $\psi\left( \frac{x}{6} \right)-\psi\left( \frac{x}{7} \right)$ and so on. Thus from \eqref{20151007longupper}, I select \begin{equation*} \psi(x) \ge V(x) + \psi\left( \frac{x}{3} \right)- \psi\left( \frac{x}{5} \right) \ge B x + O(\log x ) + u \frac{x}{3} - v \frac{x}{5} + O(\log^2 x) \end{equation*} Thus I obtain the recursive equation $$\label{20151007recu} u_{i+1} = B + \frac{u_i}{3} - \frac{v_i}{5}$$ In a similar way, I can improve the upper bound as follows. First write $$\label{20151007longlower} \psi(x) = V(x) + \psi\left( \frac{x}{3} \right)\underbrace{- \psi\left( \frac{x}{5} \right)+\psi\left( \frac{x}{6} \right)}_{\le 0} \underbrace{- \psi\left( \frac{x}{7} \right)+ \psi\left( \frac{x}{9} \right)}_{\le 0} - \cdots$$ Because $\frac{6}{5} < \frac{3}{2}$, I drop the term $- \psi\left( \frac{x}{5} \right)+\psi\left( \frac{x}{6} \right)$. For similar reason, all the next pairs are also dropped. Thus \begin{equation*} \psi(x) \le V(x) + \psi\left( \frac{x}{3} \right) \le B x + O(\log x ) + v \frac{x}{3} + O(\log^2 x) \end{equation*} Thus I obtain the recursive equation $$\label{20151007recv} v_{i+1} = B + \frac{v_i}{3}$$ The solution of the recursive equations \eqref{20151007recu} and \eqref{20151007recv}, together with the initial conditions $u_0 = B$ and $v_0 = \frac{3}{2} B$, is \begin{align*} u_i &= \left( \frac{-1}{20} 3^{-i} + \frac{21}{20} \right) B\\ v_i &= \frac{3}{2} B \end{align*} Taking $i$ large, one can thus see that for all $\epsilon > 0$, $\psi(x)$ is bounded by $$\label{20151007endpsi} \left( \frac{21}{20} B - \epsilon \right) x + O(\log^2 x ) \le \psi(x) \le \frac{3}{2} B x + O(\log^2 x )$$ The lower bound in \eqref{20151007startpsi} is thus improved; the upper bound not. Numerically, \eqref{20151007endpsi} is the bound \begin{equation*} \left( 0.819373- \epsilon \right) x + O(\log^2 x ) \le \psi(x) \le 1.17053\ x + O(\log^2 x ) \end{equation*} In part II, §2 of his paper, Sylvester gives a very readable account of the application of this recursive method on Chebyshev's choice \begin{equation*} T(x) - T\left( \frac{x}{2} \right)- T\left( \frac{x}{3} \right)- T\left( \frac{x}{5} \right)+ T\left( \frac{x}{30} \right) \end{equation*} which then leads to the bound \begin{equation*} \left( \frac{51072}{50999} D - \epsilon \right) x + O(\log^2 x ) \le \psi(x) \le \frac{59595}{50999} D x + O(\log^2 x ) \end{equation*} with $D = \frac{1}{2} \log 2 + \frac{1}{3} \log 3 + \frac{1}{5} \log 5 - \frac{1}{30} \log 30$. Numerically, this is \begin{equation*} \left( 0.922611- \epsilon \right) x + O(\log^2 x ) \le \psi(x) \le 1.07658\ x + O(\log^2 x ) \end{equation*}