Analytic Number Theory

Analytic Number Theory (I)

Some Elementary Results

$\sum p^{-1}$ Diverges

The infinitude of prime numbers had been well known since Euclid. A stronger result is that the following series diverges: \[\sum_p \frac{1}{p} \rightarrow \infty.\]

An Elementary Proof

Suppose the series above converges, i.e. there is a $q$ such that \[\sum_{p>q} \frac{1}{p} < \frac{1}{2}.\] Then we let $p_1,\cdots,p_m$ denotes all prime numbers less than $q$, and let \[Q = p_1 \cdots p_m.\] Now since $\{1+nQ\}$ are not divisible by $p_1,\cdots,p_m$, we find that \[\sum_{n=1}^r \frac{1}{1+nQ} \le \sum_{i=1}^\infty (\sum_{p>q} \frac{1}{p})^i\] since every item on the LHS is included in the summation on the RHS. This yields a contradiction.

Arithmetic Functions

We define $\operatorname{id}_k(n) = n^k$, and $\operatorname{id}(n) = n$.

The Dirichlet Convolution and Derivative

Definition. $\displaystyle (f * g)(n) = \sum_{d | n} f(d) g\qty(\frac{n}{d}).$

Under this definition, the commutation law and the association law hold. \[f*g = g*f,\quad (f*g)*h = f*(g*h).\] The Dirichlet inverse of $f$ is denoted by $f^{-1}$ and satisfies $f^{-1}*f = I$. If $f(1) \neq 0$, then the inverse exists and is unique.

Definition. The derivative of a arithmetic function is defined by $f'(n) = f(n)\log n$, for $n\ge 1$.

Many properties of the derivative in calculus hold for the arithmetic derivative as well.

$(f+g)' = f' + g'$.
$(f*g)' = f'*g + f*g'$.
$(f^{-1})' = -f' * (f * f)^{-1}$.

Multiplicative Functions

Multiplicative functions make up a subgroup of arithmetic functions under the binary operation defined by the Dirichlet convolution, i.e. if $f*g$ is multiplicative if both $f$ and $g$ are, and $f^{-1}$ is multiplicative if $f$ is.

Examples of multiplcative functions includes

$1(n)$ (completely multiplicative),
$\operatorname{id}_k(n)$ (completely multiplicative),
$\lambda(n)$ (complete multiplicative),
$\varphi(n)$,
$\mu(n)$,
$\sigma_k(n)$.

Theorem. Let $f$ be multiplicative. Then $f$ is completely multiplicative if and only if $f^{-1}(n) = \mu(n) f(n)$.

Theorem. If $f$ is multiplicative, then \[\sum_{d|n} \mu(d) f(d) = \prod_{p|n} (1-f(p)).\]

The Number Theoretic $\delta$-Function

Definition. $\displaystyle I(n) = \qty(n) = \begin{cases} 1, & \text{if } n = 1; \\ 0, & \text{if } n > 1.\end{cases}{}$

This is the analogy of the $\delta$-function in number theory. \[I * f = f * I = f.\]

The Möbius Function $\mu(n)$

Definition. $\mu(1) = 1$, and for $n = p_1^{\alpha_1}\cdots p_k^{\alpha_k}>1$ we define \[\mu(n) = \begin{cases} (-1)^k, & \text{if } \alpha_1 = \cdots = \alpha_k = 1; \\ 0, & \text{otherwise}. \end{cases}{}\]

Theorem. If $n\ge 1$ we have \[(1 * \mu)(n) = \sum_{d | n} \mu(d) = I(n) = \qty[\frac{1}{n}] = \begin{cases} 1, & \text{if } n = 1; \\ 0, & \text{if } n > 1. \end{cases}{}\]

The Euler's Totient Function $\varphi(n)$

Definition. $\varphi(n)$ is defined to be the number of of integers in $1,\cdots,n$ that's coprime with $n$.

Theorem. If $n\ge 1$ we have \[(1 * \varphi)(n) = \sum_{d | n} \varphi(d) = n.\]

Theorem. If $n\ge 1$ we have \[(\mu*\operatorname{id})(n) = \sum_{d | n}\mu(d)\frac{n}{d} = \varphi(n).\]

Theorem. $\varphi$ could be written as the product form \[\varphi(n) = n \prod_{p | n} \qty(1-\frac{1}{p}).\]

Some properties of the totient function are given below.

For a prime number $p$, $\varphi(p^\alpha) = p^\alpha - p^{\alpha-1}{}$.
$\displaystyle\varphi(mn) = \varphi(m)\varphi(n)\qty(\frac{d}{\varphi(d)})$ where $d = \gcd(m,n)$.
In particular, if $\gcd(m,n) = 1$ then $\varphi(mn) = \varphi(m)\varphi(n)$.
If $a|b$ then $\varphi(a)|\varphi(b)$.
For $n\ge 3$, $\varphi(n)$ is even. If $n$ has $r$ different prime factors, then $2^r | \varphi(n)$.

The Möbius Inversion Formula

Theorem. If $f = 1 * g$, then $g = f * \mu$.

The von Mangoldt Function $\Lambda(n)$

Definition. \[ \displaystyle \Lambda(n) = \begin{cases}\log p, & \text{if } n = p^m, \text{ where } p \text{ is a prime}, \text{ and } m\ge 1; \\ 0, &\text{otherwise}.\end{cases}{} \]

Theorem. If $n\ge 1$, $\displaystyle (1')(n) = \log n = 1 * \Lambda = \sum_{d|n} \Lambda(d)$.

Theorem. If $n\ge 1$, $\displaystyle \Lambda(n) = \mu * (1') = -\sum_{d|n} \mu(d) \log d$.

The Liouville Function $\lambda(n)$

Definition. $\lambda(1) = 1$, and for $n = p_1^{\alpha_1}\cdots p_k^{\alpha_k}>1$ we define \[\lambda(n) = (-1)^{\alpha_1 + \cdots + \alpha_k}.\]

Theorem. For $n>1$, we have \[ (1 * \lambda)(n) = \sum_{d|n} \lambda(d) = \begin{cases} 1, &\text{if } n \text{ is a perfect square}; \\ 0, & \text{otherwise}. \end{cases} \] We have also $\lambda^{-1}(n) = \mu^2(n)$.

The Divisor Functions $\sigma_k(n)$

Definition. $\sigma_k(n) = \operatorname{id}_k * 1 = \sum_{d|n} d^k$.

In particular, we denote $\sigma_0(n)$ by $d(n)$, which counts the number of divisors, and $\sigma_1(n)$ by $\sigma(n)$, which is the sum of all divisors.

Theorem. The inversion of the divisor function is given by \[\sigma_k^{-1} = (\mu \operatorname{id}_k)*\mu = \sum_{d|n} d^k \mu(d) \mu\qty(\frac{n}{d}).\]

Generalized Convolution

In the following context, $F$ is a function on $(0,+\infty)$ that satisfies $F(x) = 0$ for $x\in (0,1)$.

Definition. $\displaystyle (\alpha\circ F)(x) = \sum_{n\le x} \alpha(n) F\qty(\frac{x}{n})$.

Theorem. Let $\alpha$ and $\beta$ be arithmetic functions. Then \[ \alpha\circ(\beta\circ F) = (\alpha*\beta)\circ F. \]

Theorem. The generalized inversion formula is given by \[ G = \alpha \circ F \Leftrightarrow F = \alpha^{-1}\circ G. \]

Theorem. For a completely multiplcative $\alpha$ we have \[ G = \alpha\circ F \Leftrightarrow F = (\mu\alpha)\circ G. \]

Bell Series

Definition. Let $f$ be a arithmetic function. We define the Bell series of $f$ modulo $p$ by the formal power series \[ f_p(x) = \sum_{n=0}^\infty f(p^n) x^n. \]

Examples of Bell series are listed below.

$\mu_p(x) = 1-x$.
$\displaystyle\varphi_p(x) = \frac{1-x}{1-px}{}$.
If $f$ is completely multiplicative, we have \[ \displaystyle f_p(x) = \frac{1}{1-f(p)x}. \]
- $I_p(x) = 1$.
- $\displaystyle 1_p(x) = \frac{1}{1-x}$.
- $\displaystyle \operatorname{id}_p^\alpha(x) = \frac{1}{1-p^\alpha x}$.
- $\displaystyle \lambda_p(x) = \frac{1}{1+x}$.

Theorem. Let $h = f*g$. Then \[h_p(x) = f_p(x) g_p(x).\]

Summary

We have the following table of convolution relations of various arithmetic functions.

$f*g$	$I$	$1$	$\operatorname{id}{}$	$\varphi$	$\mu$
$I$	$I$	$1$	$\operatorname{id}{}$	$\varphi$	$\mu$
$1$	$1$	$d$	$\sigma$	$\operatorname{id}{}$	$I$
$\operatorname{id}{}$	$\operatorname{id}{}$	$\sigma$	$\sigma\cdot \operatorname{id}{}$		$\varphi$
$\varphi$	$\varphi$	$\operatorname{id}{}$
$\mu$	$\mu$	$I$	$\varphi$

2021/2/6 18:58:36

[title=Analytic Number Theory]

## Analytic Number Theory (I)

---

#### Some Elementary Results

##### $\sum p^{-1}$ Diverges

The infinitude of prime numbers had been well known since Euclid. A stronger result is that the following series diverges:
$$\sum_p \frac{1}{p} \rightarrow \infty.$$
+++ An Elementary Proof
Suppose the series above converges, i.e. there is a $q$ such that
$$\sum_{p>q} \frac{1}{p} < \frac{1}{2}.$$
Then we let $p_1,\cdots,p_m$ denotes all prime numbers less than $q$, and let
$$Q = p_1 \cdots p_m.$$
Now since $\{1+nQ\}$ are not divisible by $p_1,\cdots,p_m$, we find that
$$\sum_{n=1}^r \frac{1}{1+nQ} \le \sum_{i=1}^\infty (\sum_{p>q} \frac{1}{p})^i$$
since every item on the LHS is included in the summation on the RHS. This yields a contradiction.
+++
{.mb-2}

---

#### Arithmetic Functions

We define $\operatorname{id}_k(n) = n^k$, and $\operatorname{id}(n) = n$.

##### The Dirichlet Convolution and Derivative

**Definition.** $\displaystyle (f * g)(n) = \sum_{d | n} f(d) g\qty(\frac{n}{d}).$

Under this definition, the commutation law and the association law hold.
$$f*g = g*f,\quad (f*g)*h = f*(g*h).$$
The Dirichlet inverse of $f$ is denoted by $f^{-1}$ and satisfies $f^{-1}*f = I$. If $f(1) \neq 0$, then the inverse exists and is unique.

**Definition.** The derivative of a arithmetic function is defined by $f'(n) = f(n)\log n$, for $n\ge 1$.

Many properties of the derivative in calculus hold for the arithmetic derivative as well.
- $(f+g)' = f' + g'$.
- $(f*g)' = f'*g + f*g'$.
- $(f^{-1})' = -f' * (f * f)^{-1}$.

##### Multiplicative Functions

Multiplicative functions make up a subgroup of arithmetic functions under the binary operation defined by the Dirichlet convolution, i.e. if $f*g$ is multiplicative if both $f$ and $g$ are, and $f^{-1}$ is multiplicative if $f$ is.

Examples of multiplcative functions includes
- $1(n)$ (completely multiplicative),
- $\operatorname{id}_k(n)$ (completely multiplicative),
- $\lambda(n)$ (complete multiplicative),
- $\varphi(n)$,
- $\mu(n)$,
- $\sigma_k(n)$.

**Theorem.** Let $f$ be multiplicative. Then $f$ is completely multiplicative if and only if $f^{-1}(n) = \mu(n) f(n)$.

**Theorem.** If $f$ is multiplicative, then
$$\sum_{d|n} \mu(d) f(d) = \prod_{p|n} (1-f(p)).$$

##### The Number Theoretic $\delta$-Function

**Definition.** $\displaystyle I(n) = \qty(n) = \begin{cases}
1, & \text{if } n = 1; \\ 0, & \text{if } n > 1.\end{cases}{}$

This is the analogy of the $\delta$-function in number theory.
$$I * f = f * I = f.$$

##### The M&ouml;bius Function $\mu(n)$

**Definition.** $\mu(1) = 1$, and for $n = p_1^{\alpha_1}\cdots p_k^{\alpha_k}>1$ we define
$$\mu(n) = \begin{cases}
(-1)^k, & \text{if } \alpha_1 = \cdots = \alpha_k = 1; \\
0, & \text{otherwise}.
\end{cases}{}$$

::: .border .border-primary .p-2 .mt-2 .mb-2
**Theorem.** If $n\ge 1$ we have
$$(1 * \mu)(n) = \sum_{d | n} \mu(d) = I(n) = \qty[\frac{1}{n}] = \begin{cases} 1, & \text{if } n = 1; \\
0, & \text{if } n > 1.
\end{cases}{}$$
:::

##### The Euler's Totient Function $\varphi(n)$

**Definition.** $\varphi(n)$ is defined to be the number of of integers in $1,\cdots,n$ that's coprime with $n$.

**Theorem.** If $n\ge 1$ we have
$$(1 * \varphi)(n) = \sum_{d | n} \varphi(d) = n.$$

**Theorem.** If $n\ge 1$ we have
$$(\mu*\operatorname{id})(n) = \sum_{d | n}\mu(d)\frac{n}{d} = \varphi(n).$$
:::

::: .border .border-primary .p-2 .mt-2
**Theorem.** $\varphi$ could be written as the product form
$$\varphi(n) = n \prod_{p | n} \qty(1-\frac{1}{p}).$$
:::

Some properties of the totient function are given below.
- For a prime number $p$, $\varphi(p^\alpha) = p^\alpha - p^{\alpha-1}{}$.
- $\displaystyle\varphi(mn) = \varphi(m)\varphi(n)\qty(\frac{d}{\varphi(d)})$ where $d = \gcd(m,n)$.
- In particular, if $\gcd(m,n) = 1$ then $\varphi(mn) = \varphi(m)\varphi(n)$.
- If $a|b$ then $\varphi(a)|\varphi(b)$.
- For $n\ge 3$, $\varphi(n)$ is even. If $n$ has $r$ different prime factors, then $2^r | \varphi(n)$.

##### The M&ouml;bius Inversion Formula

::: .border .border-primary .p-2 .mt-2 .mb-2
**Theorem.** If $f = 1 * g$, then $g = f * \mu$.
:::

##### The von Mangoldt Function $\Lambda(n)$

**Definition.**
$$
\displaystyle \Lambda(n) = \begin{cases}\log p, & \text{if } n = p^m, \text{ where } p \text{ is a prime}, \text{ and } m\ge 1; \\ 0, &\text{otherwise}.\end{cases}{}
$$

**Theorem.** If $n\ge 1$, $\displaystyle (1')(n) = \log n = 1 * \Lambda = \sum_{d|n} \Lambda(d)$.

**Theorem.** If $n\ge 1$, $\displaystyle \Lambda(n) = \mu * (1') = -\sum_{d|n} \mu(d) \log d$.

##### The Liouville Function $\lambda(n)$

**Definition.** $\lambda(1) = 1$, and for $n = p_1^{\alpha_1}\cdots p_k^{\alpha_k}>1$ we define
$$\lambda(n) = (-1)^{\alpha_1 + \cdots + \alpha_k}.$$

**Theorem.** For $n>1$, we have
$$
 (1 * \lambda)(n) = \sum_{d|n} \lambda(d) = \begin{cases}
    1, &\text{if } n \text{ is a perfect square}; \\
    0, & \text{otherwise}.
\end{cases}
$$
We have also $\lambda^{-1}(n) = \mu^2(n)$.

##### The Divisor Functions $\sigma_k(n)$

**Definition.** $\sigma_k(n) = \operatorname{id}_k * 1 = \sum_{d|n} d^k$.

In particular, we denote $\sigma_0(n)$ by $d(n)$, which counts the number of divisors, and $\sigma_1(n)$ by $\sigma(n)$, which is the sum of all divisors.

**Theorem.** The inversion of the divisor function is given by
$$\sigma_k^{-1} = (\mu \operatorname{id}_k)*\mu = \sum_{d|n} d^k \mu(d) \mu\qty(\frac{n}{d}).$$

##### Generalized Convolution

In the following context, $F$ is a function on $(0,+\infty)$ that satisfies $F(x) = 0$ for $x\in (0,1)$.

**Definition.** $\displaystyle (\alpha\circ F)(x) = \sum_{n\le x} \alpha(n) F\qty(\frac{x}{n})$.

**Theorem.** Let $\alpha$ and $\beta$ be arithmetic functions. Then
$$
\alpha\circ(\beta\circ F) = (\alpha*\beta)\circ F.
$$

**Theorem.** The generalized inversion formula is given by
$$
G = \alpha \circ F \Leftrightarrow F = \alpha^{-1}\circ G.
$$

**Theorem.** For a completely multiplcative $\alpha$ we have
$$
G = \alpha\circ F \Leftrightarrow F = (\mu\alpha)\circ G.
$$

##### Bell Series

**Definition.** Let $f$ be a arithmetic function. We define the Bell series of $f$ modulo $p$ by the formal power series
$$
f_p(x) = \sum_{n=0}^\infty f(p^n) x^n.
$$

Examples of Bell series are listed below.
- $\mu_p(x) = 1-x$.
- $\displaystyle\varphi_p(x) = \frac{1-x}{1-px}{}$.
- If $f$ is completely multiplicative, we have
$$
\displaystyle f_p(x) = \frac{1}{1-f(p)x}.
$$
  - $I_p(x) = 1$.
  - $\displaystyle 1_p(x) = \frac{1}{1-x}$.
  - $\displaystyle \operatorname{id}_p^\alpha(x) = \frac{1}{1-p^\alpha x}$.
  - $\displaystyle \lambda_p(x) = \frac{1}{1+x}$.

**Theorem.** Let $h = f*g$. Then
$$h_p(x) = f_p(x) g_p(x).$$

##### Summary

We have the following table of convolution relations of various arithmetic functions.

|---|---|---|---|---|
|$f*g${.border}       |$I$|$1$|$\operatorname{id}{}$|$\varphi$|$\mu${.bg-light}|
|$I$  {.bg-light}     |$I$|$1$|$\operatorname{id}{}$|$\varphi$|$\mu$|
|$1$  {.bg-light}     |$1$|$d$|$\sigma$|$\operatorname{id}{}$|$I$|
|$\operatorname{id}{}$ {.bg-light} |$\operatorname{id}{}$|$\sigma$|$\sigma\cdot \operatorname{id}{}$| &nbsp; | $\varphi$ |
|$\varphi${.bg-light} |$\varphi$|$\operatorname{id}{}$|&nbsp;|&nbsp;| &nbsp; |
|$\mu${.bg-light}     |$\mu$|$I$|$\varphi$|&nbsp;| &nbsp; |
{ .table .text-center }

Post anonymously

\(f*g\)	\(I\)	\(1\)	\(\operatorname{id}{}\)	\(\varphi\)	\(\mu\)
\(I\)	\(I\)	\(1\)	\(\operatorname{id}{}\)	\(\varphi\)	\(\mu\)
\(1\)	\(1\)	\(d\)	\(\sigma\)	\(\operatorname{id}{}\)	\(I\)
\(\operatorname{id}{}\)	\(\operatorname{id}{}\)	\(\sigma\)	\(\sigma\cdot \operatorname{id}{}\)		\(\varphi\)
\(\varphi\)	\(\varphi\)	\(\operatorname{id}{}\)
\(\mu\)	\(\mu\)	\(I\)	\(\varphi\)