Ze Chen

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

0%

Uploaded successfully.

0%

Uploaded successfully.


0%

Uploaded successfully.

0%

Uploaded successfully.