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 \begin{equation}\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) \end{equation} 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 \begin{equation}\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) \end{equation} and \begin{equation}\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) \end{equation} 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 \begin{equation}\label{eq:7} A x + O\left( \log x \right) \le \psi(x) \end{equation} 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*}

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, ... ".

Other posts about Chebyshev's mémoire
  1. How not to prove Bertrand's postulate
  2. Lower and upper bound for Chebyshev's psi function

No comments:

Post a Comment