Arithmetic function

Arithmetic function - a function defined on the set of natural numbers $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ and taking values in a set of complex numbers $\mathbb {C}$ ${\ displaystyle \ mathbb {C}}$ $\ mathbb {C}$ .

Definition

As follows from the definition, an arithmetic function is any function

f\colon \mathbb {N} \to \mathbb {C}

{\ displaystyle f \ colon \ mathbb {N} \ to \ mathbb {C}}

f\colon \mathbb {N} \to \mathbb {C}

The name arithmetic function is due to the fact that many functions are known in number theory $f(n)$ ${\ displaystyle f (n)}$ $f(n)$ natural argument expressing certain arithmetic properties $n$ ${\ displaystyle n}$ $n$ . Therefore, informally speaking, an arithmetic function is understood to mean a function $f(n)$ ${\ displaystyle f (n)}$ $f(n)$ , which "expresses some arithmetic property" of a natural number $n$ ${\ displaystyle n}$ $n$ (see examples of arithmetic functions below ).

Many arithmetic functions considered in number theory are actually integer-valued.

Operations and Related Concepts

The sum of the arithmetic function $f$ ${\ displaystyle f}$ $f$ call function $F:[0,+\infty )\to \mathbb {C}$ ${\ displaystyle F: [0, + \ infty) \ to \ mathbb {C}}$ $F:[0,+\infty )\to \mathbb {C}$ defined as

F(x)=\sum _{n\leq x}f(n).

{\ displaystyle F (x) = \ sum _ {n \ leq x} f (n).}

F(x)=\sum _{n\leq x}f(n).

This operation is a “discrete analogue” of the indefinite integral; at the same time, although the initial function was determined only on $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\mathbb {N}$ , its sum turns out to be convenient to be considered defined on the entire positive semiaxis (while it is, of course, piecewise constant).

The Dirichlet convolution of two arithmetic functions f and g is the arithmetic function h defined by the rule

h(n)=\sum _{d|n}f(d)g(n/d).

{\ displaystyle h (n) = \ sum _ {d | n} f (d) g (n / d).}

h(n)=\sum _{d|n}f(d)g(n/d).

The arithmetic function f can be associated with its "generating function" - the Dirichlet series

\Phi _{f}(s)=\sum _{n}f(n)n^{-s}.

{\ displaystyle \ Phi _ {f} (s) = \ sum _ {n} f (n) n ^ {- s}.}

\Phi _{f}(s)=\sum _{n}f(n)n^{-s}.

In this Dirichlet convolution of two arithmetic functions, the product of their generating functions corresponds.

Pointwise multiplication by the logarithm,

f\mapsto f',\quad f'(n)=f(n)\cdot \ln n,

{\ displaystyle f \ mapsto f ', \ quad f' (n) = f (n) \ cdot \ ln n,}

f\mapsto f',\quad f'(n)=f(n)\cdot \ln n,

is a differentiation of the algebra of arithmetic functions: with respect to convolution, it satisfies the Leibniz rule,

(f*g)'=f'*g+f*g'.

{\ displaystyle (f * g) '= f' * g + f * g '.}

The transition to a generating function turns this operation into ordinary differentiation.

Known Arithmetic Functions

Number of dividers

Arithmetic function $\tau \colon \mathbb {N} \to \mathbb {N}$ ${\ displaystyle \ tau \ colon \ mathbb {N} \ to \ mathbb {N}}$ defined as the number of positive divisors of a natural number $n$ ${\ displaystyle n}$ :

\tau (n)=\sum _{d|n}1

{\ displaystyle \ tau (n) = \ sum _ {d | n} 1}

If a $m$ ${\ displaystyle m}$ and $n$ ${\ displaystyle n}$ are mutually simple , then each divisor of the product $m n$ ${\ displaystyle mn}$ can be uniquely represented as a product of divisors $m$ ${\ displaystyle m}$ and $n$ ${\ displaystyle n}$ , and vice versa, each such product is a divisor $m n$ ${\ displaystyle mn}$ . It follows that the function $\tau$ ${\ displaystyle \ tau}$ multiplicative :

\tau (mn)=\tau (m)\tau (n)

{\ displaystyle \ tau (mn) = \ tau (m) \ tau (n)}

If a $n=\prod _{i=1}^{r}p_{i}^{s_{i}}$ ${\ displaystyle n = \ prod _ {i = 1} ^ {r} p_ {i} ^ {s_ {i}}}$ - canonical decomposition of the natural $n$ ${\ displaystyle n}$ , due to the multiplicativity

\tau (n)=\tau (p_{1}^{s_{1}})\tau (p_{2}^{s_{2}})\ldots \tau (p_{r}^{s_{r}})

{\ displaystyle \ tau (n) = \ tau (p_ {1} ^ {s_ {1}}) \ tau (p_ {2} ^ {s_ {2}}) \ ldots \ tau (p_ {r} ^ { s_ {r}})}

Since the positive divisors of the number $p_{i}^{s_{i}}$ ${\ displaystyle p_ {i} ^ {s_ {i}}}$ are $s_{i}+1$ ${\ displaystyle s_ {i} +1}$ numbers $1,p_{i},\ldots ,p_{i}^{s_{i}}$ ${\ displaystyle 1, p_ {i}, \ ldots, p_ {i} ^ {s_ {i}}}$ then

\tau (n)=(s_{1}+1)(s_{2}+1)\ldots (s_{r}+1)

{\ displaystyle \ tau (n) = (s_ {1} +1) (s_ {2} +1) \ ldots (s_ {r} +1)}

The number of divisors of a large integer n grows on average as $\ln n$ ${\ displaystyle \ ln n}$ ^[1] . More precisely - see the Dirichlet formula .

Sum of dividers

Function $\sigma \colon \mathbb {N} \to \mathbb {N}$ ${\ displaystyle \ sigma \ colon \ mathbb {N} \ to \ mathbb {N}}$ defined as the sum of the divisors of a natural number $n$ ${\ displaystyle n}$ :

\sigma (n)=\sum _{d|n}d

{\ displaystyle \ sigma (n) = \ sum _ {d | n} d}

Summarizing Functions $\tau (n)$ ${\ displaystyle \ tau (n)}$ and $\sigma (n)$ ${\ displaystyle \ sigma (n)}$ for arbitrary, generally complex $k$ ${\ displaystyle k}$ can be determined $\sigma _{k}(n)$ ${\ displaystyle \ sigma _ {k} (n)}$ - amount $k$ ${\ displaystyle k}$ degrees of positive divisors of a natural number $n$ ${\ displaystyle n}$ :

\sigma _{k}(n)=\sum _{d|n}d^{k}

{\ displaystyle \ sigma _ {k} (n) = \ sum _ {d | n} d ^ {k}}

Using Iverson notation , you can write

\sigma _{k}(n)=\sum _{d}d^{k}[\,d|n\,]

{\ displaystyle \ sigma _ {k} (n) = \ sum _ {d} d ^ {k} [\, d | n \,]}

Function $\sigma _{k}$ ${\ displaystyle \ sigma _ {k}}$ multiplicative:

m\perp n\Rightarrow ~\sigma _{k}(mn)=\sigma _{k}(m)\sigma _{k}(n)

{\ displaystyle m \ perp n \ Rightarrow ~ \ sigma _ {k} (mn) = \ sigma _ {k} (m) \ sigma _ {k} (n)}

If a $n=\prod _{i=1}^{r}p_{i}^{s_{i}}$ ${\ displaystyle n = \ prod _ {i = 1} ^ {r} p_ {i} ^ {s_ {i}}}$ - canonical decomposition of the natural $n$ ${\ displaystyle n}$ then

\sigma _{k}(n)=\prod _{i=1}^{r}{\frac {p_{i}^{(s_{i}+1)k}-1}{p_{i}^{k}-1}}

{\ displaystyle \ sigma _ {k} (n) = \ prod _ {i = 1} ^ {r} {\ frac {p_ {i} ^ {(s_ {i} +1) k} -1} {p_ {i} ^ {k} -1}}}

The sum of the divisors of n grows on average as a linear function of cn, where the constant c is found by Euler and is $c=\zeta (2)=\pi ^{2}/6$ ${\ displaystyle c = \ zeta (2) = \ pi ^ {2} / 6}$ ^[1] .

Euler Function

Euler function $\varphi (n)$ ${\ displaystyle \ varphi (n)}$ , or totiant , is defined as the number of positive integers not exceeding $n$ ${\ displaystyle n}$ which are mutually simple with $n$ ${\ displaystyle n}$ .

Using Iverson's notation , you can write:

\varphi (n)=\sum _{1\leq k\leq n}[k\perp n]

{\ displaystyle \ varphi (n) = \ sum _ {1 \ leq k \ leq n} [k \ perp n]}

The Euler function is multiplicative:

m\perp n\Rightarrow ~\varphi (mn)=\varphi (m)\varphi (n)

{\ displaystyle m \ perp n \ Rightarrow ~ \ varphi (mn) = \ varphi (m) \ varphi (n)}

Explicitly, the value of the Euler function is expressed by the formula:

\varphi (n)=n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\dots \left(1-{\frac {1}{p_{r}}}\right)

{\ displaystyle \ varphi (n) = n \ left (1 - {\ frac {1} {p_ {1}}} \ right) \ left (1 - {\ frac {1} {p_ {2}}} \ right) \ dots \ left (1 - {\ frac {1} {p_ {r}}} \ right)}

Where $p_{1},p_{2},\ldots ,p_{r}$ ${\ displaystyle p_ {1}, p_ {2}, \ ldots, p_ {r}}$ - various simple dividers $n$ ${\ displaystyle n}$ .

Mobius function

Mobius function $\mu (n)$ ${\ displaystyle \ mu (n)}$ can be defined as an arithmetic function that satisfies the following relation:

\sum _{d|n}\mu (d)={\begin{cases}1,&n=1\\0,&n>1\end{cases}}

{\ displaystyle \ sum _ {d | n} \ mu (d) = {\ begin {cases} 1, & n = 1 \\ 0, & n> 1 \ end {cases}}}

That is, the sum of the values of the Mobius function for all divisors of a positive integer $n$ ${\ displaystyle n}$ equal to zero if $n>1$ ${\ displaystyle n> 1}$ , and equals $one$ ${\ displaystyle 1}$ , if a $n=1$ ${\ displaystyle n = 1}$ .

It can be shown that only one function satisfies this equation, and it can be explicitly defined by the following formula:

\mu (n)={\begin{cases}(-1)^{r},&n=p_{1}p_{2}\ldots p_{r}\\0,&p^{2}|n\\1,&n=1\end{cases}}

{\ displaystyle \ mu (n) = {\ begin {cases} (- 1) ^ {r}, & n = p_ {1} p_ {2} \ ldots p_ {r} \\ 0, & p ^ {2} | n \\ 1, & n = 1 \ end {cases}}}

Here $p_{i}$ ${\ displaystyle p_ {i}}$ - various prime numbers, $p$ ${\ displaystyle p}$ - Prime number. In other words, the Mobius function $\mu (n)$ ${\ displaystyle \ mu (n)}$ is equal to $0$ ${\ displaystyle 0}$ , if a $n$ ${\ displaystyle n}$ not free from squares (i.e. divided by the square of a prime), and is equal to $\pm 1$ ${\ displaystyle \ pm 1}$ otherwise (plus or minus is selected depending on the parity of the number of prime divisors $n$ ${\ displaystyle n}$ ).

The Mobius function is a multiplicative function . The importance of the Mobius function in number theory is associated with the Mobius formula for inversion .

Notes

↑ ¹ ² V. And Arnold. Dynamics, statistics and projective geometry of Galois fields. - M .: ICMMO, 2005 .-- S. 70. - 72 p.

Literature

Vinogradov I. M. Fundamentals of number theory . - M.-L .: GITTL, 1952. - 180 p.
Nesterenko Yu. V. Number theory: a textbook for students. higher studies. institutions. - M .: Publishing Center "Academy", 2008. - 272 p. - ISBN 978-5-7695-4646-4 .
Chandrasekharan K. Introduction to Analytic Number Theory = Introduction to Analytic Number Theory. - M .: "The World", 1974. - 188 p.

[Arnold-1] ¹ ² V. And Arnold. Dynamics, statistics and projective geometry of Galois fields. - M .: ICMMO, 2005 .-- S. 70. - 72 p.