数論的関数

数論的関数（すうろんてきかんすう、英: arithmetic function, arithmetical function, number-theoretical function）とは、定義域が正整数である複素数を値に持つ関数のことである。 複素数の無限数列 { a n } n ≥ 1 {\displaystyle \{a_{n}\}_{n\geq 1}} は n ↦ a n {\displaystyle n\mapsto a_{n}} という対応で、数論的関数とみなすことができる。 正整数 n に対して n = ∏ p   prime p ν p ( n ) ( ν p ( n ) ≥ 0 ) {\displaystyle n=\prod _{p\ {\text{prime}}}p^{\nu _{p}(n)}\quad (\nu _{p}(n)\geq 0)} と素因数分解する。 この項では、 a ( n ) {\displaystyle a(n)} が { a ( p k ) | k ≥ 0 ,   p   prime } {\displaystyle \{a(p^{k})|k\geq 0,\ p\ {\text{prime}}\}} によって得られる数論的関数について述べる。 互いに素である正整数 m と n に対して、 a ( m n ) = a ( m ) + a ( n ) {\displaystyle a(mn)=a(m)+a(n)} が成立するとき、加法的関数（additive function）という。 つまり、 a ( n ) = ∑ p ; prime a ( p ν p ( n ) ) {\displaystyle a(n)=\sum _{p;\operatorname {prime} }a(p^{\nu _{p}(n)})} が成立する関数である。 特に、任意の正整数 m と n に対して、 f ( m n ) = f ( m ) + f ( n ) {\displaystyle f(mn)=f(m)+f(n)} が成立するとき、完全加法的関数（completely additive function）という。つまり完全加法的関数とは a ( n ) = ∑ p   prime ν p ( n ) a ( p ) {\displaystyle a(n)=\sum _{p\ {\text{prime}}}\nu _{p}(n)a(p)} が成立する数論的関数である。 対数関数: log ⁡ n {\displaystyle \log n} n の相異なる素因数の個数を表す ω ( n ) {\displaystyle \omega (n)} ω ( n ) = # { p | ν p ( n ) ≠ 0 } {\displaystyle \omega (n)=\#\{p|\nu _{p}(n)\neq 0\}} n の重複度を数えた素因数の個数を表す Ω ( n ) {\displaystyle \Omega (n)} Ω ( n ) = ∑ p ; prime ν p ( n ) {\displaystyle \Omega (n)=\sum _{p;\operatorname {prime} }\nu _{p}(n)} 素数 p に対して、n を割る最大指数を表す、 ν p ( n ) {\displaystyle \nu _{p}(n)} 互いに素である正整数 m と n に対して、 f ( m n ) = f ( m ) f ( n ) {\displaystyle f(mn)=f(m)f(n)} が成立するとき、乗法的関数 (multiplicative function)という。 つまり、 a ( n ) = ∏ p ; prime a ( p ν p ( n ) ) {\displaystyle a(n)=\prod _{p;\operatorname {prime} }a(p^{\nu _{p}(n)})} が成立する関数である。 特に、任意の正整数 m と n に対して、 f ( m n ) = f ( m ) f ( n ) {\displaystyle f(mn)=f(m)f(n)} が成立するとき、完全乗法的関数 (completely multiplicative function)という。つまり、完全乗法的関数とは a ( n ) = ∏ p ; prime a ( p ) ν p ( n ) {\displaystyle a(n)=\prod _{p;\operatorname {prime} }a(p)^{\nu _{p}(n)}} が成立する数論的関数である。 約数関数 σx(n) は乗法的関数であるが、完全乗法的関数ではない。 q を 2以上の正整数とする。 このとき、任意の正整数 n に対して n = ∑ j ≥ 0 b j ( n ) q j           ( b j ( n ) = 0 ,   1 , … ,   q − 1 ) {\displaystyle n=\sum _{j\geq 0}b_{j}(n)q^{j}\ \ \ \ \ (b_{j}(n)=0,\ 1,\ldots ,\ q-1)} と q 進展開する。 この項では、 a ( n ) {\displaystyle a(n)} が { a ( b q j ) | j ≥ 0 ,   b = 0 ,   1 , … ,   q − 1 } {\displaystyle \scriptstyle \{a(bq^{j})|j\geq 0,\ b=0,\ 1,\ldots ,\ q-1\}} によって得られる数論的関数について述べる。 a ( n ) = ∑ j ≥ 0 a ( b j ( n ) q j ) {\displaystyle \scriptstyle a(n)=\sum _{j\geq 0}a(b_{j}(n)q^{j})} を満たすとき、q加法的関数 (q-additive function)という。 特に、q加法的関数 a ( n ) {\displaystyle a(n)} が a ( b q j ) = a ( b ) {\displaystyle \scriptstyle a(bq^{j})=a(b)} ( j ≥ 0 ,   b = 0 ,   1 , … ,   q − 1 ) {\displaystyle \scriptstyle (j\geq 0,\ b=0,\ 1,\ldots ,\ q-1)} を満たすとき、強q加法的関数 (strongly q-additive function)という。 sum of digits 関数 s q ( n ) = ∑ j ≥ 0 b j ( n ) {\displaystyle \textstyle s_{q}(n)=\sum _{j\geq 0}b_{j}(n)} digit counting 関数 e q ( b ; n ) = # { j | b j ( n ) = b } {\displaystyle e_{q}(b;n)=\#\{j|b_{j}(n)=b\}} 但し、b は 1 , 2 , … , q − 1 {\displaystyle \scriptstyle 1,2,\ldots ,q-1} のいずれか。 a ( n ) = ∏ j ≥ 0 a ( b j ( n ) q j ) {\displaystyle \scriptstyle a(n)=\prod _{j\geq 0}a(b_{j}(n)q^{j})} を満たすとき、q乗法的関数 (q-multiplicative function)という。 特に、q乗法的関数 a ( n ) {\displaystyle a(n)} が a ( b q j ) = a ( b ) {\displaystyle \scriptstyle a(bq^{j})=a(b)} ( j ≥ 0 ,   b = 0 ,   1 , … ,   q − 1 ) {\displaystyle \scriptstyle (j\geq 0,\ b=0,\ 1,\ldots ,\ q-1)} を満たすとき、強q乗法的関数 (strongly q-multiplicative function)という。 トゥエ＝モース数列 a ( n ) = ( − 1 ) e 2 ( 1 ; n ) {\displaystyle a(n)=(-1)^{e_{2}(1;n)}} product of digits 関数 p q ( n ) = ∏ j = 0 r b j ( n )           ( b r ( n ) ≠ 0 ,   b j ( n ) = 0   ( j > r ) ) {\displaystyle \textstyle p_{q}(n)=\prod _{j=0}^{r}b_{j}(n)\ \ \ \ \ (b_{r}(n)\neq 0,\ b_{j}(n)=0\ (j>r))} (1) 素数に関係する関数 素数計数関数: π ( n ) {\displaystyle \pi (n)} フォン・マンゴルト関数: Λ ( n ) {\displaystyle \Lambda (n)} Λ ( n ) = { log ⁡ p ( n = p m ,   m ≥ 1 ,   p ; prime ) 0 ( n ≠ p m ) {\displaystyle \Lambda (n)={\begin{cases}\log p&(n=p^{m},\ m\geq 1,\ p;\operatorname {prime} )\\0&(n\neq p^{m})\end{cases}}} ϑ ( n ) = ∑ p ≤ n ,   p ; prime log ⁡ p {\displaystyle \textstyle \vartheta (n)=\sum _{p\leq n,\ p;\operatorname {prime} }\log p} ψ ( n ) = ∑ p m ≤ n ,   p ; prime log ⁡ p {\displaystyle \textstyle \psi (n)=\sum _{p^{m}\leq n,\ p;\operatorname {prime} }\log p} (2) 数の表現・分割 n を２つの平方数の和で表す表し方の数を与える r 2 ( n ) {\displaystyle r_{2}(n)} n を正整数の和で表す表し方の数を与える p ( n ) {\displaystyle p(n)} ウェアリングの問題 全ての正整数が s 個の k 乗数の和で表される様な s の最小値 g ( k ) {\displaystyle g(k)} 十分大きな全ての正整数が s 個の k 乗数の和で表される様な s の最小値 G ( k ) {\displaystyle G(k)} 数論的関数 f ( n ) ,   g ( n ) {\displaystyle \scriptstyle f(n),\ g(n)} に対して、ディリクレ積 f ∗ g {\displaystyle f*g} を ( f ∗ g ) ( n ) = ∑ d ≥ 1 ,   d | n f ( d ) g ( n / d ) {\displaystyle (f*g)(n)=\!\!\!\sum _{d\geq 1,\ d|n}\!\!\!f(d)g(n/d)} と定めると、 f ∗ g {\displaystyle f*g} は数論的関数となる。従って、数論的関数全体集合は多元環となる。 乗法的関数 f ( n ) ,   g ( n ) {\displaystyle \scriptstyle f(n),\ g(n)} に対して、ディリクレ積 f ∗ g {\displaystyle f*g} で得られた数論的関数は乗法的関数となる。 数論的関数 f ( n ) {\displaystyle f(n)} が、ある正数 C と、数論的関数 g ( n ) {\displaystyle g(n)} が存在して、 f ( n ) = C g ( n ) {\displaystyle \scriptstyle f(n)=C^{g(n)}} と表されるとする。すると、 f ( n ) {\displaystyle f(n)} が(完全)乗法的関数である必要十分条件は、 g ( n ) {\displaystyle g(n)} は(完全)加法的関数である。 (1) 最大位数 数論的関数 a ( n ) {\displaystyle a(n)} に対して、ある単純な形をした n の関数 ψ ( n ) {\displaystyle \psi (n)} が存在して lim sup n → ∞ a ( n ) ψ ( n ) = 1 {\displaystyle \limsup _{n\to \infty }{\frac {a(n)}{\psi (n)}}=1} が成立するとき、 a ( n ) {\displaystyle a(n)} の最大位数は ψ ( n ) {\displaystyle \psi (n)} であるという。 (2) 平均位数 数論的関数 a ( n ) {\displaystyle a(n)} に対して、ある単純な形をした n の関数 ψ ( n ) {\displaystyle \psi (n)} が存在して lim n → ∞ ∑ k = 1 n a ( k ) ∑ k = 1 n ψ ( k ) = 1 {\displaystyle \lim _{n\to \infty }{\frac {\sum _{k=1}^{n}a(k)}{\sum _{k=1}^{n}\psi (k)}}=1} が成立するとき、 a ( n ) {\displaystyle a(n)} の平均位数は ψ ( n ) {\displaystyle \psi (n)} であるという。 従って、 a ( n ) {\displaystyle a(n)} は、だいたい ψ ( n ) {\displaystyle \psi (n)} であると思われるが、数論的関数の多くは、値の振る舞いが複雑であり、 a ( n ) {\displaystyle a(n)} がほぼ ψ ( n ) {\displaystyle \psi (n)} である様な n は正整数のなかで少数であることも珍しいことではない。 (3) 正規位数 任意の正数 ϵ とほとんど全ての正整数 n に対して ( 1 − ε ) ψ ( n ) < a ( n ) < ( 1 + ε ) ψ ( n ) {\displaystyle (1-\varepsilon )\psi (n)<a(n)<(1+\varepsilon )\psi (n)\!} が成立するとき、 a ( n ) {\displaystyle a(n)} の正規位数は ψ ( n ) {\displaystyle \psi (n)} であるという。 平均位数と正規位数は、常に存在する訳ではない。 平均位数は持つが正規位数はもたない、その逆で、平均位数は持たないが正規位数を持つ数論的関数が存在する。 (1) 約数関数 d ( n ) {\displaystyle d(n)} 最大位数は、 2 log ⁡ n / log ⁡ log ⁡ n {\displaystyle 2^{\log n/\log \log n}\!} であり、平均位数は log ⁡ n {\displaystyle \log n} である。 さらに log ⁡ d ( n ) {\displaystyle \log d(n)} の正規位数は l o g 2 log ⁡ log ⁡ n {\displaystyle log2\log \log n} である。 従って、任意の正数 ε とほとんど全ての正整数 n に対して ( log ⁡ n ) ( 1 − ϵ ) log ⁡ 2 < d ( n ) < ( log ⁡ n ) ( 1 + ϵ ) log ⁡ 2 {\displaystyle (\log n)^{(1-\epsilon )\log 2}<d(n)<(\log n)^{(1+\epsilon )\log 2}\!} が成立する。 つまり、ほとんど全ての正整数に対して、 d ( n ) {\displaystyle d(n)} の値は、平均位数よりも小さい。 (2) 約数和関数 σ ( n ) {\displaystyle \sigma (n)} 最大位数は e γ n log ⁡ log ⁡ n {\displaystyle e^{\gamma }n\log \log n\!} であり、平均位数は π 2 n / 6 {\displaystyle \pi ^{2}n/6} である。 (3) オイラー関数 φ ( n ) {\displaystyle \varphi (n)} 最大位数は n − 1 {\displaystyle n-1} であり、平均位数は 6 n / π 2 {\displaystyle 6n/\pi ^{2}} である。 (4) n の相異なる素因数の個数を表す関数 ω ( n ) {\displaystyle \omega (n)} 平均位数および正規位数は共に log ⁡ log ⁡ n {\displaystyle \log \log n} である。 (5) n の重複を込めた素因数の個数を表す関数 Ω ( n ) {\displaystyle \Omega (n)} 平均位数および正規位数は共に log ⁡ log ⁡ n {\displaystyle \log \log n} である。 (6) 素数の個数を表す π ( n ) {\displaystyle \pi (n)} 正規位数は、 n / log ⁡ n {\displaystyle n/\log n} である。