Lower and upper bound for Chebyshev's psi function

In this post, I prove the inequalities \begin{equation}\label{eq:1} \log 2 \cdot x - 3 \log x \le \psi(x) \le 2 \log 2 \cdot x + \frac{3}{\log 2} \log^2 x \end{equation} for all real \( x \ge 2 \). Hereby is \( \psi(x) = \sum_{n \le x } \Lambda(n) \) with \( \Lambda \) the von Mangoldt function. This is a second post motivated by Chebyshev's paper "Mémoire sur les nombres premiers" from 1852. In this paper, Chebyshev uses a more complex variant of the calculation below to obtain stronger inequalities. Similar inequalities can also be found on page 50 in Murty's book.

How not to prove Bertrand's postulate

This is a first post motivated by Chebyshev's paper "Mémoire sur les nombres premiers" from 1852. In this paper Chebyshev proves Bertrand's postulate that there is always a prime between \( a \) and \( 2a \) for all \( a \ge 2 \). Chebyshev bases his proof on inequalities for the function \begin{equation}\label{HNTPeq:1} 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 \begin{equation*} T(x) = \sum_{ 1 \le n \le x} \log n \end{equation*} Chebyshev's paper is quite easy to read and can be found at this link. In this post I will follow Chebyshev's reasoning on an easier version of \eqref{HNTPeq:1}.

Neue Empirische Daten Über Die Zahlentheoretische Funktion sigma(n), von Sterneck, 1913. Part II

This post is about a formula that von Sterneck used to calculate values of \( M(n) \) for \( n \) up to 5,000,000. The formula is

\begin{equation} \sum_{d \le \sqrt{x}}\!\!\phantom{}^{\prime}\ M\left( \frac{x}{d} \right) + \sum_{d \le \sqrt{x}} \mu(d) \omega_P\left( \frac{x}{d} \right) - \omega_P(\sqrt{x})M(\sqrt{x}) =0 \end{equation}

where

• \( \mu \) the Möbius function
• \( M(x) = \sum_{ n \le x} \mu(n) \) the Mertens function
• \( \omega_P(x) = \left\{ k \in\mathbb{N} \middle| 1 \le k \le x \text{ and } p_1 \nmid k \text{ and } \cdots \text{ and } p_j \nmid k\right\} \) with \(P = \left\{ p_1, \ldots p_j \right\}\) a non-empty set of primes
• \(\sum_{k \le x}^{\prime}\) the sum over integers \(k\) with \( p_1 \nmid k \text{ and } \cdots \text{ and } p_j \nmid k\)
• \( x \ge p_1 p_2 \cdots\ p_j \)

An example
I calculate an example for \( x = 50 \) and \( P = \{ 2,3 \} \). The first term is
\begin{equation}
\sum_{d \le 7}\!\phantom{}^{\prime}\ M\left( \frac{50}{d} \right) = M(50) + M(10) + M(7)
\end{equation}
The second term is
\begin{equation}
\sum_{d \le 7} \mu(d) \omega_P\left( \frac{50}{d} \right)
\end{equation}
If I use
\begin{equation}
\omega_P(x) = \lfloor x \rfloor - \left\lfloor \frac{x}{2} \right\rfloor -  \left\lfloor \frac{x}{3}\right\rfloor + \left\lfloor \frac{x}{6} \right\rfloor
\end{equation}
then it can be calculated that the second term is zero. The third term is \( \omega(7) M(7) = 3 M(7) \). All together, von Sterneck's formula gives the recursive relation
\begin{equation}
M(50) + M(10) +M(7) + 0 - 3 M(7) =0
\end{equation}
Because \( M(10) = -1 \) and \( M(7) = -2 \) this gives \( M(50) = -3 \).

Sketch of the proof of the formula
The proof proceeds as follows. Define the function \( e_P \)
\begin{equation}
e_P(m) = \begin{cases} 1 \quad\text{if}\quad p_1 \nmid m \text{ and } \cdots \text{ and } p_j \nmid m\\ 0 \quad\text{otherwise} \end{cases}
\end{equation}
then calculate the Dirichlet convolution 

\begin{equation} e_P \ast\mu = 1_{\langle P \rangle} \cdot \mu
\end{equation} where \( 1_{\langle P \rangle}\) is the characteristic function on the set \( \langle P \rangle = \left\{ n \in \mathbb{N} \middle|\quad \forall p: p | n \implies p \in P \right\} \). Because \( \sum_{ k \le x}e_P(k) = \omega_P(x) \), Dirichlet's hyperbola method gives
\begin{equation}
\sum_{n \le x} 1_{\langle P \rangle} (n) \mu(n) = \sum_{d \le \sqrt{x}}e_P(d) \ M\left( \frac{x}{d} \right) + \sum_{d \le \sqrt{x}} \mu(d) \omega_P\left( \frac{x}{d} \right) - \omega_P(\sqrt{x})M(\sqrt{x})
\end{equation}
The result then follows because the left hand side is zero for \( x \ge p_1 p_2 \cdots\ p_j \)

Von Sterneck used this formula with \( P = \{ 2,3,5,7 \} \). In that way he could calculate values of \(M(n) \)  for \( n \) up to 5,000,000 based on a pre-computed table of \(M(n) \)  for \( n \) up to 500,000.

Neue Empirische Daten Über Die Zahlentheoretische Funktion sigma(n), von Sterneck, 1913. Part I

In the paper in the title, von Sterneck performs numerical tests on the inequality
\begin{equation}\label{Neueeq:1}
| M (n) | \le \sqrt{n}
\end{equation}
where \( M(n) = \displaystyle\sum_{k=1}^n \mu(n) \) is the Mertens function. The inequality (1) is of historical interest, because it implies the correctness of the Riemann hypothesis. In 1985 however, Odlyzko and te Riele, showed that (1) is incorrect, although an explicit number \( n \) for which (1) fails is still not known. Nevertheless, I find von Sterneck's paper still interesting because I want to see how \( M(n) \) was calculated for large values of \( n \) before the advent of (electronic) computers.

On Kronecker's lemma

While reading some parts of the nice lecture notes on Analytic Number Theory by Hildebrand, I encountered Kronecker's lemma on page 58.

If \( f : \mathbb N \to \mathbb C \) is a function, and \( s \in \mathbb C \) with \( \Re(s) > 0 \) is a complex number such that the Dirichlet series \( L(f,s) = \displaystyle\sum_{n=1}^{\infty} \frac{f(n)}{n^s} \) converges, then \( \displaystyle\sum_{n \le x } f(n) = o(x^s) \quad\text{for}\quad x \to + \infty \)

As an example, take \( f(n) = 1 \), then \( \displaystyle\sum_{n=1}^{\infty} \frac{1}{n^{s}} \) converges for \( s > 1 \) and indeed \( \displaystyle\sum_{n \le x } 1 = \lfloor x \rfloor = o(x^s) \) for all \( s > 1 \).

As a second example, take \( f(n) = \frac{1}{n} \), then \( \displaystyle\sum_{n=1}^{\infty} \frac{1}{n^{1+s}} \) converges for \( s > 0 \) and indeed \( \displaystyle\sum_{n \le x } \frac{1}{n} = \log x = o(x^s) \) for all \( s > 0 \).

What I like about Kronecker's lemma is that its statement and proof involve real analysis only; one does not need to know anything about the behaviour of the function \(L(f,s) \) for complex numbers \( s \). On the other hand, in analytic number theory, one often uses Perron's formula to estimate sums \( \sum_{n \le x } f(n) \) for number theoretic functions \( f \). One then needs to have information about the zeros of the Dirichlet series, and its behaviour for large imaginary values of \( s \) to make Perron's formula work. All this information is thus not needed when using Kronecker's lemma.

Although a proof of Kronecker's lemma can be found in Hildebrand's lecture notes, I write here a proof for the case \( s \in \mathbb R \). This proof is based on the French Wikipedia article about Kronecker's lemma and is very transparent.

Tauberian Theorem for Cesàro mean

Because the proof of the prime number theorem is related to Tauberian theorems of various kinds (see for example this paper by Mueger), I decided to prove a Tauberian theorem for a very simple case, namely the case of Cesàro means. It seems difficult to find the proof online, I therefore write one down here.

Variation on a theme by Mertens

One of the formulas that Mertens proves in his paper is

\begin{equation}\label{eq1} \sum_{ p \le x } \frac{ \log p}{p} = \log x + R \quad\text{ with }\quad | R | \le 2
\end{equation}

I use Mertens method to prove the variant

\begin{equation}\label{eq2} \sum_{ n \le x } \frac{ \Lambda(n)}{n} = \log x + R \quad \text{ with } \quad -1 \le R \le 2
\end{equation}

Here, \( \Lambda \) is the von Mangoldt function. Equation \eqref{eq2} is thus similar to \eqref{eq1}, the sum is over prime powers instead of primes. It turns out that it is easier to prove \eqref{eq2} than \eqref{eq1}, because including the prime powers actually reduces the amount of estimates one has to make. The proof of \eqref{eq2} serves as a light version of the proof of \eqref{eq1} and gives insight into how the proof of \eqref{eq1} is organized.