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
$$\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$$
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

\sum_{d \le 7}\!\phantom{}^{\prime}\ M\left( \frac{50}{d} \right) = M(50) + M(10) + M(7)

The second term is

\sum_{d \le 7} \mu(d) \omega_P\left( \frac{50}{d} \right)

If I use

\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

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

M(50) + M(10) +M(7) + 0 - 3 M(7) =0

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$

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}

then calculate the Dirichlet convolution
e_P \ast\mu = 1_{\langle P \rangle} \cdot \mu
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

\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})

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.