Ramanujan和(Ramanujan sum)とは、正の整数 $q$ と整数 $n$ について、$1$ の原始 $q$ 乗根の $n$ 乗をすべて足した和 $c_q(n)=\sum_{\gcd(a,q)=1}e^{2\pi ian/q}$ である。値は整数で $\sum_{d\mid\gcd(q,n)}\mu(q/d)d$ に等しく、$c_q(1)=\mu(q)$、$q\mid n$ なら $\varphi(q)$ となる。互いに素な $q,r$ について $c_{qr}(n)=c_q(n)c_r(n)$ で、$q$ の約数 $d$ にわたる $c_d$ は直交する。$\sigma(n)/n=\frac{\pi^2}6\sum_qc_q(n)/q^2$ のような算術関数の展開に使われる。
Ramanujan和(Ramanujan sum)は、正の整数 $q$ と整数 $n$ について、$1$ の原始 $q$ 乗根の $n$ 乗をすべて足した和
$$
c_q(n)=\sum_{\substack{1\le a\le q\\ \gcd(a,q)=1}}e\Bigl(\frac{an}q\Bigr),\qquad e(t)=e^{2\pi it}
$$
である。複素数の和として定義されるが、値はいつも整数で、Möbius 関数を使った有限和
$$
c_q(n)=\sum_{d\mid\gcd(q,n)}\mu\Bigl(\frac qd\Bigr)d
$$
に等しい(thm-rs-divisor)。$n=1$ なら $c_q(1)=\mu(q)$、$q\mid n$ なら $c_q(n)=\varphi(q)$ で、Ramanujan 和は Möbius 関数と Euler 関数をつなぐ量になっている。
和そのものはそれ以前の文献にも現れるが、その重要性を見抜いて系統的に使ったのは 1918 年の Ramanujan の論文である(HW60 第 5 章の注, p. 62)。Ramanujan 和を使うと、算術関数を $\sum_q a_q\,c_q(n)$ の形の級数に展開できる。たとえば約数の和 $\sigma(n)$ について
$$
\frac{\sigma(n)}n=\frac{\pi^2}6\sum_{q=1}^{\infty}\frac{c_q(n)}{q^2}
$$
が成り立つ(thm-rs-expansion)。この記事では、約数の公式、$q$ についての乗法性、Hölder の式、直交性と有限の展開、この Ramanujan 展開を証明する。
正の整数 $q$ と整数 $n$ について
$$
c_q(n):=\sum_{\substack{a=1\\ \gcd(a,q)=1}}^{q}e\Bigl(\frac{an}q\Bigr)
$$
を Ramanujan 和 という。$c_1(n)=1$ である。
$a$ が法 $q$ の既約剰余類を一巡するとき、$e(a/q)$ は $1$ の原始 $q$ 乗根を一巡する(1の冪根)。よって $c_q(n)$ は原始 $q$ 乗根の $n$ 乗の和であり、$n$ を法 $q$ で取り替えても変わらない。$a\mapsto q-a$ も既約剰余類の置換なので $\overline{c_q(n)}=c_q(-n)=c_q(n)$ で、$c_q(n)$ は実数である。
定義から直接、$c_2(n)=(-1)^n$、素数 $p$ について $c_p(n)=-1$($p\nmid n$)、$c_p(n)=p-1$($p\mid n$)である。$q=4$ では原始 4 乗根は $\pm i$ なので $c_4(n)=i^n+(-i)^n$ で、$n=1,2,3,4$ に対して $0,-2,0,2$ である。一般に次のようになる(定義の和と thm-rs-divisor の両方から計算した)。
| $c_q(n)$ | $n=1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $q=3$ | $-1$ | $-1$ | $2$ | $-1$ | $-1$ | $2$ | $-1$ | $-1$ | $2$ | $-1$ | $-1$ | $2$ |
| $q=4$ | $0$ | $-2$ | $0$ | $2$ | $0$ | $-2$ | $0$ | $2$ | $0$ | $-2$ | $0$ | $2$ |
| $q=6$ | $1$ | $-1$ | $-2$ | $-1$ | $1$ | $2$ | $1$ | $-1$ | $-2$ | $-1$ | $1$ | $2$ |
| $q=8$ | $0$ | $0$ | $0$ | $-4$ | $0$ | $0$ | $0$ | $4$ | $0$ | $0$ | $0$ | $-4$ |
| $q=9$ | $0$ | $0$ | $-3$ | $0$ | $0$ | $-3$ | $0$ | $0$ | $6$ | $0$ | $0$ | $-3$ |
| $q=12$ | $0$ | $2$ | $0$ | $-2$ | $0$ | $-4$ | $0$ | $-2$ | $0$ | $2$ | $0$ | $4$ |
各行は $n$ について周期 $q$ をもち、$q\mid n$ の列で最大値 $\varphi(q)$ をとる。
鍵は、$1$ の $d$ 乗根の全部を位数ごとに分けることである。
正の整数 $d$ と整数 $n$ について
$$
\sum_{e\mid d}c_e(n)=\sum_{b=1}^{d}e\Bigl(\frac{bn}d\Bigr)=\begin{cases}d&(d\mid n)\\0&(d\nmid n)\end{cases}
$$
である。
$1\le b\le d$ について $g:=\gcd(b,d)$、$e:=d/g$、$a:=b/g$ とおくと $\frac bd=\frac ae$、$e\mid d$、$1\le a\le e$、$\gcd(a,e)=1$ である。逆に $e\mid d$ と $1\le a\le e$、$\gcd(a,e)=1$ から $b:=a\cdot d/e$ が戻り、この対応は全単射である。よって $\sum_{b=1}^de(bn/d)=\sum_{e\mid d}\sum_{\gcd(a,e)=1}e(an/e)=\sum_{e\mid d}c_e(n)$ である。一方 $\zeta:=e(n/d)$ について $\sum_{b=1}^d\zeta^b$ は、$d\mid n$ なら $\zeta=1$ で $d$、そうでなければ $\zeta\ne1$、$\zeta^d=1$ なので等比数列の和 $\zeta(\zeta^d-1)/(\zeta-1)=0$ である。$\square$
正の整数 $q$ と整数 $n$ について
$$
c_q(n)=\sum_{d\mid\gcd(q,n)}\mu\Bigl(\frac qd\Bigr)d
$$
である。とくに $c_q(n)$ は整数で、$\lvert c_q(n)\rvert\le\sigma(\gcd(q,n))$ が成り立つ($n=0$ では $\gcd(q,0)=q$)。
$n$ を固定し、正の整数 $d$ について $f(d):=c_d(n)$、$F(d):=d$($d\mid n$)、$F(d):=0$($d\nmid n$)とおく。lem-rs-all-roots は $F(d)=\sum_{e\mid d}f(e)$ がすべての $d\ge1$ で成り立つことを言っている。Möbius関数 の定理「Möbiusの反転公式」により $f(q)=\sum_{d\mid q}\mu(q/d)F(d)$ である。$F(d)\neq0$ となるのは $d\mid n$ のときだけなので、和は $d\mid q$ かつ $d\mid n$、すなわち $d\mid\gcd(q,n)$ にわたり、主張の式を得る。右辺は整数の和なので整数である。$\lvert\mu\rvert\le1$ なので $\lvert c_q(n)\rvert\le\sum_{d\mid\gcd(q,n)}d=\sigma(\gcd(q,n))$ である。$\square$
この公式は HW60 §16.6 の Theorem 271(p. 237)で、そこでも Möbius の反転で示されている。特別な場合を並べておく。
1 と 3 は、thm-rs-divisor で $\gcd(q,n)=1$ なら和が $d=1$ の項 $\mu(q)$ だけになることによる。2 では $\gcd(q,n)=q$ で、和は $\sum_{d\mid q}\mu(q/d)d$ になり、Möbius関数 の命題「Eulerの $\varphi$ 関数の表示」により $\varphi(q)$ に等しい(2 は定義からも直接、$\varphi(q)$ 個の $1$ の和として出る)。$\square$
1 は、$1$ の原始 $q$ 乗根を根とする円分多項式 $\Phi_q$ の $x^{\varphi(q)-1}$ の係数が $-\mu(q)$ であることと同じ内容である(根と係数の関係)。
$q,r$ を互いに素な正の整数とすると、すべての整数 $n$ について $c_{qr}(n)=c_q(n)\,c_r(n)$ である。
$A$ を法 $q$ の既約剰余類の代表 $1\le a\le q$、$B$ を法 $r$ の既約剰余類の代表の集合とし、$\Phi(a,b):=ar+bq\bmod qr$ とおく。
像が既約剰余類であること. 素数 $p$ が $qr$ を割るとする。$p\mid q$ なら $p\nmid r$(互いに素)で、$ar+bq\equiv ar\pmod p$ は $p\nmid a$、$p\nmid r$ より $0$ でない。$p\mid r$ でも同様である。よって $\gcd(ar+bq,qr)=1$ である。
単射であること. $ar+bq\equiv a'r+b'q\pmod{qr}$ なら、法 $q$ で見て $ar\equiv a'r$ で、$r$ は法 $q$ で可逆なので $a\equiv a'\pmod q$、すなわち $a=a'$ である。同様に $b=b'$ である。
$\lvert A\times B\rvert=\varphi(q)\varphi(r)=\varphi(qr)$(Euler関数 の乗法性)なので、$\Phi$ は $A\times B$ から法 $qr$ の既約剰余類全体への全単射である。$e\bigl(\frac{(ar+bq)n}{qr}\bigr)=e\bigl(\frac{an}q\bigr)e\bigl(\frac{bn}r\bigr)$ なので
$$
c_{qr}(n)=\sum_{a\in A}\sum_{b\in B}e\Bigl(\frac{an}q\Bigr)e\Bigl(\frac{bn}r\Bigr)=c_q(n)\,c_r(n)
$$
である。$\square$
これは HW60 §5.6 の Theorem 67(p. 56)である。$n$ を固定したとき $q\mapsto c_q(n)$ は乗法的関数なので、素数冪での値から全体が決まる。それを閉じた式にしたのが次の定理である。
正の整数 $q$ と整数 $n$ について、$g:=\gcd(q,n)$ とおくと
$$
c_q(n)=\mu\Bigl(\frac qg\Bigr)\frac{\varphi(q)}{\varphi(q/g)}
$$
である。
$n$ を固定する。$q=q_1q_2$($\gcd(q_1,q_2)=1$)なら $\gcd(q,n)=\gcd(q_1,n)\gcd(q_2,n)$ で、$\mu$ と $\varphi$ は乗法的なので、右辺も $q$ について乗法的である。左辺は thm-rs-multiplicative により乗法的なので、$q=p^k$($p$ は素数、$k\ge1$)で比べればよい。$p^v$ を $n$ を割る $p$ の最大の冪とする($n=0$ なら $v=\infty$)。
左辺.thm-rs-divisor の和は $d=p^j$($0\le j\le\min(k,v)$)にわたり、$\mu(p^{k-j})$ が $0$ でないのは $j=k$(値 $1$)と $j=k-1$(値 $-1$)だけである。よって $v\ge k$ なら $p^k-p^{k-1}$、$v=k-1$ なら $-p^{k-1}$、$v\le k-2$ なら $0$ である。
右辺.$v\ge k$ なら $q/g=1$ で $\varphi(p^k)=p^k-p^{k-1}$ である。$v=k-1$ なら $q/g=p$ で $-\varphi(p^k)/\varphi(p)=-p^{k-1}$ である。$v\le k-2$ なら $q/g$ は $p^2$ で割れて $\mu(q/g)=0$ である。両辺は一致する。$\square$
HW60 §16.6 の Theorem 272(p. 238)は同じ式を thm-rs-divisor から直接計算して示している。$q=12$、$n=2$ では $g=2$、$q/g=6$ で、$\mu(6)\varphi(12)/\varphi(6)=1\cdot4/2=2$ となり、表の値と一致する。
$q$ を正の整数、$d,e$ を $q$ の正の約数とすると
$$
\frac1q\sum_{n=1}^{q}c_d(n)\,c_e(n)=\begin{cases}\varphi(d)&(d=e)\\0&(d\neq e)\end{cases}
$$
である。
$d\mid q$ のとき、$\gcd(a,d)=1$ となる $1\le a\le d$ について $e(an/d)=e(a(q/d)n/q)$ である。そこで $X_d:=\{a(q/d)\bmod q\mid1\le a\le d,\ \gcd(a,d)=1\}$ とおくと、$X_d$ は $\varphi(d)$ 個の元からなり、$c_d(n)=\sum_{x\in X_d}e(xn/q)$ である。$x\in X_d$ なら $\gcd(x,q)=q/d$ なので、$d\ne e$ なら $X_d\cap X_e=\emptyset$ である。$c_e(n)$ は実数なので $c_e(n)=\overline{c_e(n)}=\sum_{y\in X_e}e(-yn/q)$ であり、
$$
\frac1q\sum_{n=1}^qc_d(n)c_e(n)=\sum_{x\in X_d}\sum_{y\in X_e}\frac1q\sum_{n=1}^qe\Bigl(\frac{(x-y)n}q\Bigr)
$$
となる。内側の和は lem-rs-all-roots の計算と同じく、$x\equiv y\pmod q$ なら $1$、そうでなければ $0$ である。よって左辺は $\lvert X_d\cap X_e\rvert$ に等しく、主張を得る。$\square$
関数 $f\colon\mathbb Z\to\mathbb C$ の値が $\gcd(n,q)$ だけで決まるとき、$f$ を 法 $q$ の偶関数 という。$d\mid q$ なら $\gcd(n,d)=\gcd(\gcd(n,q),d)$ なので、thm-rs-divisor から $c_d$ は法 $q$ の偶関数である。
法 $q$ の偶関数 $f$ は、ただ 1 通りに
$$
f(n)=\sum_{d\mid q}\alpha_d\,c_d(n),\qquad\alpha_d=\frac1{q\varphi(d)}\sum_{n=1}^qf(n)\,c_d(n)
$$
と書ける。
法 $q$ の偶関数全体 $V$ は、$q$ の各約数 $g$ について $\gcd(n,q)=g$ となる $n$ での値を自由に決めて得られるので、$q$ の約数の個数 $d(q)$ 次元の複素ベクトル空間である。$V$ に内積 $\langle f,h\rangle:=\frac1q\sum_{n=1}^qf(n)\overline{h(n)}$ を入れると、thm-rs-orthogonal により $c_d$($d\mid q$)は $0$ でない互いに直交する $d(q)$ 個の元なので一次独立であり、$V$ の基底になる。展開の係数は内積をとって $\langle f,c_d\rangle=\alpha_d\varphi(d)$ から決まる($c_d$ は実数値)。$\square$
$f(n)=\gcd(n,q)$ を考える。$\gcd(n,q)=\sum_{d\mid\gcd(n,q)}\varphi(d)$(Euler関数 の定理「Gaussの約数和公式」)と、lem-rs-all-roots の言い換え「$d\mid n$ なら $1$、そうでなければ $0$」$=\frac1d\sum_{e\mid d}c_e(n)$ を組み合わせると
$$
\gcd(n,q)=\sum_{d\mid q}\frac{\varphi(d)}d\sum_{e\mid d}c_e(n)=\sum_{e\mid q}\Bigl(\sum_{e\mid d\mid q}\frac{\varphi(d)}d\Bigr)c_e(n)
$$
を得る。$q=6$ では $\alpha_1=1+\frac12+\frac23+\frac13=\frac52$、$\alpha_2=\frac12+\frac13=\frac56$、$\alpha_3=\frac23+\frac13=1$、$\alpha_6=\frac13$ である。$n=1$ で $\frac52-\frac56-1+\frac13=1$、$n=6$ で $\frac52+\frac56+2+\frac23=6$ となって確かに $\gcd(n,6)$ を再現する。cor-rs-even の内積の式で計算しても同じ係数になる($q=6,12$ で計算して確かめた)。
有限の展開を $q$ について無限に延ばすと、Ramanujan が使った級数の展開になる。
正の整数 $n$ と実数 $s>1$ について
$$
\sum_{q=1}^{\infty}\frac{c_q(n)}{q^s}=\frac{\sigma_{1-s}(n)}{\zeta(s)}
$$
であり、級数は絶対収束する。ここで $\sigma_t(n)=\sum_{d\mid n}d^t$、$\zeta$ は Riemannゼータ関数 である。とくに $s=2$ で
$$
\frac{\sigma(n)}n=\frac{\pi^2}6\sum_{q=1}^{\infty}\frac{c_q(n)}{q^2}
$$
が成り立つ。
thm-rs-divisor により $\lvert c_q(n)\rvert\le\sigma(n)$ なので、$s>1$ で級数は絶対収束する。$q$ の約数 $d$ で $d\mid n$ となるものについて $q=dm$ と書くと、thm-rs-divisor から
$$
\sum_{q\ge1}\frac{c_q(n)}{q^s}=\sum_{q\ge1}\sum_{\substack{d\mid q\\ d\mid n}}\frac{\mu(q/d)\,d}{q^s}=\sum_{d\mid n}d^{1-s}\sum_{m\ge1}\frac{\mu(m)}{m^s}
$$
である(二重級数は絶対収束するので並べ替えてよい)。$\sum_m\mu(m)m^{-s}$ と $\zeta(s)=\sum_kk^{-s}$ の積を展開すると、$N^{-s}$ の係数は $\sum_{m\mid N}\mu(m)$ で、Möbius関数 の定理「約数にわたる和」により $N=1$ で $1$、$N\ge2$ で $0$ である。よって $\sum_m\mu(m)m^{-s}=1/\zeta(s)$ で、第 1 の式を得る。$s=2$ では $\sigma_{-1}(n)=\sum_{d\mid n}d^{-1}=\sigma(n)/n$($d\mapsto n/d$)と $\zeta(2)=\pi^2/6$(Basel問題)を使う。$\square$
これは HW60 §17.5 の Theorems 292–293(pp. 250–251)である。$n=1$ では $c_q(1)=\mu(q)$ なので、等式は $\sum_q\mu(q)/q^2=6/\pi^2$ になる。$n=2$ では $c_q(2)$ は $q$ が奇数なら $\mu(q)$、$q=2m$($m$ は奇数)なら $\mu(m)$、$4\mid q$ なら $\mu(q/2)\cdot2$ の形の値をとり、右辺は $\sigma(2)/2=\frac32$ である。$q\le Q$ までの部分和に $\pi^2/6$ を掛けた値は、$n=12$($\sigma(12)/12=\frac73$)で $Q=100,1000,10000$ に対して $2.33370$、$2.33332$、$2.33333$ となる(数値で確かめた)。
左辺の各項 $c_q(n)$ は $n$ について周期 $q$ の関数なので、Ramanujan 展開は「算術関数を周期の違う周期関数の重ね合わせとして書く」ものと読める。Fourier 級数と違い、各周期の成分 $c_q$ そのものが整数値である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-rs-multiplicative で $q,r$ が互いに素 | $q=r=2$、$n=2$ | $c_4(2)=-2$ だが $c_2(2)^2=1$ である |
| cor-rs-special の 1 で $\gcd(a,q)=1$ の $a$ に限ること | $q=3$ ですべての $1\le a\le3$ にわたって和をとる | 和は $e(\frac13)+e(\frac23)+1=0$ で、$\mu(3)=-1$ にならない。一般にこの和は $q\mid n$ で $q$、それ以外で $0$ である(lem-rs-all-roots) |
| thm-rs-orthogonal で $d,e$ が $q$ を割る | $q=4$、$d=2$、$e=3$ | $\sum_{n=1}^4c_2(n)c_3(n)=1-1-2-1=-3\ne0$ である |
| thm-rs-expansion で $s>1$ | $s=1$、$n=1$ | $\sum_q\lvert c_q(1)\rvert/q=\sum_{q\text{ は平方因子なし}}1/q$ は発散し、絶対収束しない |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する