数論的関数

数論的関数(すうろんてきかんすう、英: arithmetic(al) function）とは、定義域が正整数である複素数を値に持つ関数のことである。

複素数の無限数列 $\{a_{n}\}_{n\geq 1}$ は $n\mapsto a_{n}$ という対応で、数論的関数とみなすことができる。

素因数分解に関連する関数

正整数 n に対して

$n=\prod _{p;\operatorname {prime} }p^{\nu _{p}(n)}\ \ \ \ \ (\nu _{p}(n)\geq 1)$

と素因数分解する。

この項では、 $a(n)$ が $\scriptstyle \{a(p^{k})|k\geq 0,\ p;\operatorname {prime} \}$ によって得られる数論的関数について述べる。

加法的関数

互いに素である正整数 m と n に対して、 $a(mn)=a(m)+a(n)$ が成立するとき、加法的関数 (additive function)という。

つまり、

$a(n)=\sum _{p;\operatorname {prime} }a(p^{\nu _{p}(n)})$

が成立する関数である。

特に、任意の正整数 m と n に対して、 $f(mn)=f(m)+f(n)$ が成立するとき、完全加法的関数 (completely additive function)という。つまり、完全加法的関数とは

$a(n)=\sum _{p;\operatorname {prime} }\nu _{p}(n)a(p)$

が成立する数論的関数である。

例

対数関数: $\log n$
n の相異なる素因数の個数を表す $\omega (n)$ $\omega (n)$
- $\omega (n)=\#\{p|\nu _{p}(n)\neq 0\}$
n の重複度を数えた素因数の個数を表す $\Omega (n)$ $\Omega (n)$
- $\Omega (n)=\sum _{p;\operatorname {prime} }\nu _{p}(n)$
素数 p に対して、n を割る最大指数を表す、 $\nu _{p}(n)$

乗法的関数

互いに素である正整数 m と n に対して、 $f(mn)=f(m)f(n)$ が成立するとき、乗法的関数 (multiplicative function)という。

つまり、

$a(n)=\prod _{p;\operatorname {prime} }a(p^{\nu _{p}(n)})$

が成立する関数である。

特に、任意の正整数 m と n に対して、 $f(mn)=f(m)f(n)$ が成立するとき、完全乗法的関数 (completely multiplicative function)という。つまり、完全乗法的関数とは

$a(n)=\prod _{p;\operatorname {prime} }a(p)^{\nu _{p}(n)}$

が成立する数論的関数である。

例

任意の整数 k に対する $n^{k}$
指数関数: 任意の正数 C に対する $C^{n}$
メビウス関数: $\mu (n)$ $\mu (n)$
- $\mu (n)={\begin{cases}1&(n=1)\\(-1)^{r}&(n=p_{1}\cdots p_{r})\\0&({\mbox{otherwise}})\end{cases}}$
約数関数: n の約数の個数を表す $d(n)$ $d(n)$
- $d(n)=\sum _{d|n,\ d>0}\!\!\!\!1$
k乗約数和関数: $\sigma _{k}(n)$ $\sigma _{k}(n)$
- $\sigma _{k}(n)=\sum _{d|n,\ d>0}\!\!\!\!d^{k}$
n の正の奇数の約数の個数を表す $\tau _{o}(n)$ $\tau _{o}(n)$
- $\tau _{o}(n)=\sum _{2\nmid d|n,\ d>0}\!\!\!\!\!1$
n の正の奇数の約数の和を表す $\sigma _{o}(n)$ $\sigma _{o}(n)$
- $\sigma _{o}(n)=\sum _{2\nmid d|n,\ d>0}\!\!\!\!\!d$
オイラー関数: $\scriptstyle \varphi (n)$ $\scriptstyle \varphi (n)$
- $\varphi (n)=\#\{k|k\geq 1,\ (k,n)=1\}$
ディリクレ指標: $\chi (n)$
リウヴィルのラムダ関数: $\lambda (n)=(-1)^{\Omega (n)}$
ラマヌジャンの和関数:

$c_{q}(n)=\!\!\sum _{1\leq h\leq q,\ (h,q)=1}\!\!\!\!\!\!\!\!\!e^{2\pi ihn/q}$

ラマヌジャンの τ 関数: $\tau (n)$ $\tau (n)$
- $\tau (n)$ は、 $x\prod _{n=1}^{\infty }(1-x^{n})^{24}$ の n 次の係数
任意の正整数 k に対する、 $k^{\omega (n)}$

q進展開に関連する関数

q を 2以上の正整数とする。

このとき、任意の正整数 n に対して

$n=\sum _{j\geq 0}b_{j}(n)q^{j}\ \ \ \ \ (b_{j}(n)=0,\ 1,\ldots ,\ q-1)$

と q 進展開する。

この項では、 $a(n)$ が $\scriptstyle \{a(bq^{j})|j\geq 0,\ b=0,\ 1,\ldots ,\ q-1\}$ によって得られる数論的関数について述べる。

q加法的関数

$\scriptstyle a(n)=\sum _{j\geq 0}a(b_{j}(n)q^{j})$ を満たすとき、q加法的関数 (q-additive function)という。

特に、q加法的関数 $a(n)$ が $\scriptstyle a(bq^{j})=a(b)$ $\scriptstyle (j\geq 0,\ b=0,\ 1,\ldots ,\ q-1)$ を満たすとき、強q加法的関数 (strongly q-additive function)という。

例

sum of digits 関数 $\textstyle s_{q}(n)=\sum _{j\geq 0}b_{j}(n)$
digit counting 関数 $e_{q}(b;n)=\#\{j|b_{j}(n)=b\}$ 但し、b は $\scriptstyle 1,2,\ldots ,q-1$ のいずれか。

q乗法的関数

$\scriptstyle a(n)=\prod _{j\geq 0}a(b_{j}(n)q^{j})$ を満たすとき、q乗法的関数 (q-multiplicative function)という。

特に、q乗法的関数 $a(n)$ が $\scriptstyle a(bq^{j})=a(b)$ $\scriptstyle (j\geq 0,\ b=0,\ 1,\ldots ,\ q-1)$ を満たすとき、強q乗法的関数 (strongly q-multiplicative function)という。

例

トゥエ＝モース数列 $a(n)=(-1)^{e_{2}(1;n)}$
product of digits 関数 $\textstyle p_{q}(n)=\prod _{j=0}^{r}b_{j}(n)\ \ \ \ \ (b_{r}(n)\neq 0,\ b_{j}(n)=0\ (j>r))$

その他の数論的関数

(1) 素数に関係する関数

n 以下の素数の個数を与える $\pi (n)$
フォン・マンゴルト関数: $\Lambda (n)$ $\Lambda (n)$
- $\Lambda (n)={\begin{cases}\log p&(n=p^{m},\ m\geq 1,\ p;\operatorname {prime} )\\0&(n\neq p^{m})\end{cases}}$
$\textstyle \vartheta (n)=\sum _{p\leq n,\ p;\operatorname {prime} }\log p$
$\textstyle \psi (n)=\sum _{p^{m}\leq n,\ p;\operatorname {prime} }\log p$

(2) 数の表現・分割

n を２つの平方数の和で表す表し方の数を与える $r_{2}(n)$
n を正整数の和で表す表し方の数を与える $p(n)$
ウェアリングの問題
- 全ての正整数が s 個の k 乗数の和で表される様な s の最小値 $g(k)$
- 十分大きな全ての正整数が s 個の k 乗数の和で表される様な s の最小値 $G(k)$

性質

代数的性質

数論的関数 $\scriptstyle f(n),\ g(n)$ に対して、ディリクレ積 $f*g$ を

$(f*g)(n)=\!\!\!\sum _{d\geq 1,\ d|n}\!\!\!f(d)g(n/d)$

と定めると、 $f*g$ は数論的関数となる。従って、数論的関数全体集合は多元環となる。

乗法的関数 $\scriptstyle f(n),\ g(n)$ に対して、ディリクレ積 $f*g$ で得られた数論的関数は乗法的関数となる。

数論的関数 $f(n)$ が、ある正数 C と、数論的関数 $g(n)$ が存在して、 $\scriptstyle f(n)=C^{g(n)}$ と表されるとする。すると、 $f(n)$ が(完全)乗法的関数である必要十分条件は、 $g(n)$ は(完全)加法的関数である。

位数

(1) 最大位数

数論的関数 $a(n)$ に対して、ある単純な形をした n の関数 $\psi (n)$ が存在して

$\limsup _{n\to \infty }{\frac {a(n)}{\psi (n)}}=1$

が成立するとき、 $a(n)$ の最大位数は $\psi (n)$ であるという。

(2) 平均位数

数論的関数 $a(n)$ に対して、ある単純な形をした n の関数 $\psi (n)$ が存在して

$\lim _{n\to \infty }{\frac {\sum _{k=1}^{n}a(k)}{\sum _{k=1}^{n}\psi (k)}}=1$

が成立するとき、 $a(n)$ の平均位数は $\psi (n)$ であるという。

従って、 $a(n)$ は、だいたい $\psi (n)$ であると思われるが、数論的関数の多くは、値の振る舞いが複雑であり、 $a(n)$ がほぼ $\psi (n)$ である様な n は正整数のなかで少数であることも珍しいことではない。

(3) 正規位数

任意の正数 ϵ とほとんど全て^[1]の正整数 n に対して

$(1-\varepsilon )\psi (n)<a(n)<(1+\varepsilon )\psi (n)\!$

が成立するとき、 $a(n)$ の正規位数は $\psi (n)$ であるという。

平均位数と正規位数は、常に存在する訳ではない。平均位数は持つが正規位数はもたない、その逆で、平均位数は持たないが正規位数を持つ数論的関数が存在する。

例

(1) 約数関数 $d(n)$

最大位数は、

$2^{\log n/\log \log n}\!$

であり、平均位数は $\log n$ である。さらに $\log d(n)$ の正規位数は $log2\log \log n$ である。従って、任意の正数 ε とほとんど全ての正整数 n に対して

$(\log n)^{(1-\epsilon )\log 2}<d(n)<(\log n)^{(1+\epsilon )\log 2}\!$

が成立する。

つまり、ほとんど全ての正整数に対して、 $d(n)$ の値は、平均位数よりも小さい。

(2) 約数和関数 $\sigma (n)$

最大位数は

$e^{\gamma }n\log \log n\!$

であり、平均位数は $\pi ^{2}n/6$ である。

(3) オイラー関数 $\varphi (n)$

最大位数は $n-1$ であり、平均位数は $6n/\pi ^{2}$ である。

(4) n の相異なる素因数の個数を表す関数 $\omega (n)$

平均位数および正規位数は共に $\log \log n$ である.

(5) n の重複を込めた素因数の個数を表す関数 $\Omega (n)$