Saturday, September 5, 2015

Variations on a theme by Chebyshev

In his paper "Mémoire sur les nombres premiers", Chebyshev calculates a lower and upper bound on the function \begin{equation*} \psi(x) = \sum_{n \le x } \Lambda(n) \end{equation*} from an analysis of the expression $$\label{eq:2} 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)$$ with $T(x) = \sum_{ 1 \le n \le x} \log n\$. In this post, I quickly review Chebyshev's argument and then calculate which bounds on $\psi(x)$ one can get from expressions that are similar to \eqref{eq:2}.
Chebyshev's argument proceeds as follows. Inserting the expression
\begin{equation*} T(x) = \sum_{n=1}^{\infty} \psi\left(\frac{x}{n} \right) \end{equation*} in \eqref{eq:2} gives \begin{align*} &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) = \\ & \psi\left(x \right) - \psi\left(\frac{x}{6} \right) + \psi\left(\frac{x}{7} \right)-\psi\left(\frac{x}{10} \right) + \psi\left(\frac{x}{11} \right) - \psi\left(\frac{x}{12} \right)+\psi\left(\frac{x}{13} \right)-\psi\left(\frac{x}{15} \right) \\ & + \psi\left(\frac{x}{17} \right) - \psi\left(\frac{x}{18} \right)+\psi\left(\frac{x}{19} \right) - \psi\left(\frac{x}{20} \right) + \psi\left(\frac{x}{23} \right) -\psi\left(\frac{x}{24} \right) + \psi\left(\frac{x}{29} \right) - \psi\left(\frac{x}{30}\right) + \cdots \end{align*} It is easy to see that the coefficients of $\psi\left(\frac{x}{n} \right)$ have period 30. Also, one observes that the coefficients have alternating values $+1$ and $- 1$. The latter property is crucial and leads directly to the inequalities $$\label{eq:5} 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)\le \psi(x)$$ and $$\label{eq:6} \psi\left(x \right) - \psi\left(\frac{x}{6} \right) \le 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)$$ Chebyshev uses explicit bounds on $T(x)$ and inequalities \eqref{eq:5} and \eqref{eq:6} to obtain explicit bounds on $\psi(x)$. In order to make Chebyshev's argument a bit more transparent, I will use the big $O$ notation instead. Because $T(x) = x \log x - x +O\left(\log x \right)\$, and $1 - 1/2 - 1/3 - 1/5 + 1/30 = 0\$, it follow that \begin{align*} 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) =& x \log x - \frac{x}{2} \log\frac{x}{2} - \frac{x}{3} \log\frac{x}{3}-\frac{x}{5} \log\frac{x}{5}+\frac{x}{30} \log\frac{x}{30}\\ &- \left(x - \frac{x}{2} - \frac{x}{3} - \frac{x}{5} + \frac{x}{30} \right)+O\left( \log x \right)\\ =& 0 \cdot \log x + A x +O\left( \log x \right) \end{align*} with \begin{equation*} A = \frac{1}{2} \log 2+\frac{1}{3} \log 3+\frac{1}{5} \log 5 -\frac{1}{30} \log 30 \end{equation*} The inequalities \eqref{eq:5} and \eqref{eq:6} thus become $$\label{eq:7} A x + O\left( \log x \right) \le \psi(x)$$ and \begin{equation*} \psi\left(x \right) - \psi\left(\frac{x}{6} \right) \le A x + O\left( \log x \right) \end{equation*} The expression \eqref{eq:7} is thus a lower bound on $\psi(x)$. To obtain an upper bound, one can proceed as follows \begin{align*} \psi\left(x \right) - \psi\left(\frac{x}{6} \right) \le A x + O\left( \log x \right) \\ \psi\left(\frac{x}{6} \right) - \psi\left(\frac{x}{6^2} \right) \le A \frac{x}{6} + O\left( \log x \right) \\ \psi\left(\frac{x}{6^2} \right) - \psi\left(\frac{x}{6^3} \right) \le A \frac{x}{6^2} + O\left( \log x \right) \end{align*} Adding gives and upper bound on $\psi(x)$ \begin{align*} \psi(x) &\le A x \frac{1}{1 - 1/6}+O\left( \log^2 x \right)\\ &= \frac{6 A}{5} x + O\left( \log^2 x \right) \end{align*}

Variants
Instead of the expression \eqref{eq:2}, one could try to use other expression of the form \begin{equation*} \sum_{n=1}^{\infty} a_n T\left(\frac{x}{n} \right) \end{equation*} To make Chebyshev's argument work, one needs \begin{equation*} \sum_{n=1}^{\infty} \frac{a_n}{n} = 0 \end{equation*} so that the terms with $\log x$ cancel and also that \begin{equation*} \sum_{n=1}^{\infty} a_n T\left(\frac{x}{n} \right) \end{equation*} has alternating coefficients when expanded in $\psi\left(\frac{x}{n} \right)$. If one then obtains \begin{equation*} \sum_{n=1}^{\infty} a_n T\left(\frac{x}{n} \right) = \psi\left(x \right) - \psi\left(\frac{x}{m} \right)+\cdots \end{equation*} then this leads to inequalities \begin{equation*} A x + O\left( \log x \right) \le \psi(x) \le B x + O\left( \log x \right) \end{equation*} with \begin{equation*} A = - \sum \frac{a_n}{n} \log n \ \mbox{ and }\ B = \frac{m+1}{m} A \end{equation*} The only examples I know are the following. I sort them in order of increasing $A$

1. \begin{equation*} T(x) - 2 T\left( \frac{x}{2} \right)- T\left( \frac{x}{3} \right)+ T\left( \frac{x}{4} \right)+ T\left( \frac{x}{6}\right)- T\left( \frac{x}{12}\right) \end{equation*} which gives $A = 0.62$ and $B = 1.24$
2. \begin{equation*} T(x) - 2 T\left( \frac{x}{2} \right) \end{equation*} which gives $A = 0.69$ and $B = 1.39$
3. \begin{equation*} T(x) - T\left( \frac{x}{2} \right)- 2 T\left( \frac{x}{3} \right)+ T\left( \frac{x}{6} \right) \end{equation*} which gives $A = 0.78$ and $B = 1.17$
4. \begin{equation*} T(x) - T\left( \frac{x}{2} \right)- T\left( \frac{x}{3} \right)- T\left( \frac{x}{4}\right) + T\left( \frac{x}{12} \right) \end{equation*} which gives $A = 0.85$ and $B = 1.14$
5. 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 gives $A = 0.92$ and $B = 1.11$
Chebyshev's choice thus gives the tightest inequalities. All these variants are also mentioned in part II of Sylvester's paper "On arithmetical series" from 1892. I tried finding more examples using Mathematica, but did not find any. There might indeed be no other examples, because Sylvester also writes "It would, I believe, be perfectly futile to seek for stigmatic schemes, involving higher prime numbers than 5, that should give rise to stigmatic series of sum-sums in which the successive coefficients should be alternately positive and negative unity, ... ".