数論的関数

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

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

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

正整数 n に対して $${\displaystyle n=\prod _{p\ {\text{prime}}}p^{\nu _{p}(n)}\quad (\nu _{p}(n)\geq 0)}$$ と素因数分解する。

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

加法的関数

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

つまり、 $${\displaystyle a(n)=\sum _{p;\operatorname {prime} }a(p^{\nu _{p}(n)})}$$ が成立する関数である。

特に、任意の正整数 m と n に対して、${\displaystyle f(mn)=f(m)+f(n)}$ が成立するとき、完全加法的関数（completely additive function）という。つまり完全加法的関数とは ${\displaystyle a(n)=\sum _{p\ {\text{prime}}}\nu _{p}(n)a(p)}$ が成立する数論的関数である。

例

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

乗法的関数

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

つまり、

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

が成立する関数である。

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

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

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

例

• 約数関数 σ_x(n) は乗法的関数であるが、完全乗法的関数ではない。

q進展開に関連する関数

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

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

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

と q 進展開する。

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

q加法的関数

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

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

例

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

q乗法的関数

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

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

例

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

その他の数論的関数

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

• 素数計数関数: ${\displaystyle \pi (n)}$
• フォン・マンゴルト関数: ${\displaystyle \Lambda (n)}$
  • ${\displaystyle \Lambda (n)={\begin{cases}\log p&(n=p^{m},\ m\geq 1,\ p;\operatorname {prime} )\\0&(n\neq p^{m})\end{cases}}}$
• ${\displaystyle \textstyle \vartheta (n)=\sum _{p\leq n,\ p;\operatorname {prime} }\log p}$
• ${\displaystyle \textstyle \psi (n)=\sum _{p^{m}\leq n,\ p;\operatorname {prime} }\log p}$

(2) 数の表現・分割

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

性質

代数的性質

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

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

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

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

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

位数

(1) 最大位数

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

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

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

(2) 平均位数

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

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

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

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

(3) 正規位数

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

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

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

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

例

(1) 約数関数 ${\displaystyle d(n)}$

最大位数は、

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

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

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

が成立する。

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

(2) 約数和関数 ${\displaystyle \sigma (n)}$

最大位数は

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

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

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

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

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

平均位数および正規位数は共に ${\displaystyle \log \log n}$ である。

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

平均位数および正規位数は共に ${\displaystyle \log \log n}$ である。

(6) 素数の個数を表す ${\displaystyle \pi (n)}$

正規位数は、${\displaystyle n/\log n}$ である。