Processing math: 12%

Saturday, July 25, 2015

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
dx M(xd)+dxμ(d)ωP(xd)ωP(x)M(x)=0
where
  • μ the Möbius function
  • M(x)=nxμ(n) the Mertens function
  • ωP(x)={kN|1kx and p1 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.

Sunday, July 19, 2015

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.