定义在正整数集合上的函数称为数论函数 (或算术函数).
若算术函数 `f` 满足对任意互素的 `a, b` 有 `f(a b) = f(a) f(b)`,
则称 `f` 为积性函数 (或乘性函数). 此时若 `n`
有素因子分解
`n = prod_(i=1)^r p_i^(alpha_i)`,
则
`f(n) = prod_(i=1)^r f(p_i^(alpha_i))`.
特别当 `f(a b) = f(a) f(b)` 对任意正整数 `a, b` 成立时, 称 `f`
为完全积性函数.
- 幂函数 `n^s` 是完全积性函数; 特别 `1` 是完全积性函数;
- 下文提到的 `varphi`, `mu`, `iota`, `sigma`, `tau` 都是积性函数.
Euler 函数
Euler 函数 `varphi(n)` 是积性函数.
设 `a, b` 互素, 我们有
`(n, a b) = 1 iff (n, a) = 1 and (n, b) = 1`.
列出 `a b` 以内的所有正整数:
1 2 3 ... b
b+1 b+2 b+3 ... 2b
...
(a-1)b+1 (a-1)b+2 (a-1)b+3 ... ab
我们来寻找与 `a b` 互素的元素.
表中第 `j` 列的任一元素与 `b` 的最大公约数为 `(k b+j, b) = (j, b)`,
因此只需看 `(j, b) = 1` 的列, 这样的列有 `varphi(b)` 个.
又 `(a, b) = 1`, 故该列的全体元素
`k b + j`, `quad k = 0, 1, cdots, a-1`
构成模 `a` 的完全剩余系, 其中与 `a` 互素的元素恰有 `varphi(a)` 个.
因此 `varphi(a b) = varphi(a) varphi(b)`.
`varphi(n) = n prod_(p | n) (1-1/p)`, `p` 取遍 `n` 的所有素因子.
先考虑素数幂, 由于 `m` 与 `p^a` 互素当且仅当 `p !| m`, 因此只需排除
`p^(a-1)` 个 `p` 的倍数, 得到
`varphi(p^a) = p^a - p^(a-1) = p^a(1-1/p)`.
现在利用 `varphi` 的积性
`varphi(n)`
`= prod_(i=1)^r varphi(p_i^(alpha_i))`
`= prod_(i=1)^r p_i^(alpha_i)(1-1/p_i)`
`= n prod_(p | n) (1-1/p)`.
`n ge 3` 时 `varphi(n)` 是偶数.
若 `n` 有奇素数因子 `p`, 则 `varphi(n)` 有偶数因子 `p^a - p^(a-1)`.
否则, `n` 是 `2` 的幂. 设 `n = 2^a`, `a ge 2`, 则 `varphi(n)` 有偶数因子
`2^a - 2^(a-1)`.
和函数
算术函数 `f(n)` 的和函数定义为 `S(n) = sum_(d | n) f(d)`,
其中 `d` 取遍 `n` 的正因子.
积性函数的和函数也是积性函数.
设 `f` 是积性函数, `S` 是其和函数; `a, b` 互素. 则 `a b` 的每个因子 `d`
可以看作 `a` 的因子 `d_1` 和 `b` 的因子 `d_2` 之积, 且 `d_1, d_2` 互素:
`S(a b) = sum_(d | a b) f(d)`
`= sum_(d_1 | a) sum_(d_2 | b) f(d_1) f(d_2)`
`= S(a) S(b)`.
积性函数的求和公式
设 `f` 为积性函数,
- 若 `n` 有
所示的素因子分解, 则
`sum_(d | n) f(d) = prod_(i=1)^r sum_(k=0)^(alpha_i)
f(p_i^k)`,
- 若级数 `sum_(n ge 0) f(n)` 绝对收敛, 则
`sum_(n ge 0) f(n) = prod_p sum_(k ge 0) f(p^k)`.
其中 `prod_p` 表示对全体素数求积.
- `n` 的全体正因子可以表示为
`{d: d | n}`
`= {prod_(i=1)^r p_i^(k_i):
0 le k_i le alpha_i, i = 1, cdots, r}`.
因此
`sum_(d | n) f(d)`
`= sum_(k_1=0)^(alpha_1) cdots sum_(k_r=0)^(alpha_r)
f(prod_(i=1)^r p_i^(k_i))`,
再由 `f` 的积性, 上式等于
`prod_(i=1)^r sum_(k=0)^(alpha_i) f(p_i^k)`.
- 设 `p_1=2, p_2=3, cdots` 是全体素数,
由算术基本定理, 整数 `n` 与下面的多重集合一一对应:
`{p_1: alpha_1, p_2: alpha_2, cdots}`
即公式左边的每一项, 恰对应右边的唯一一项.
- Euler 函数 `varphi(n)` 的和函数 `sum_(d | n) varphi(d) = n`;
- 因子和函数 `sigma(n) = sum_(d | n) d`
`= prod_(i=1)^r (p_i^(alpha_1+1)-1)/(p_i-1)`;
- 因子个数函数 `tau(n) = sum_(d | n) 1`
`= prod_(i=1)^r (alpha_i+1)`;
- `f(n) = n^-s` 是积性函数, 因此 Riemann zeta 函数
`zeta(s) = sum_(n ge 0) n^-s`
`= prod_p (1-p^-s)^-1`.
这一公式将 `zeta(s)` 与素数联系在一起.
- 利用 `varphi(p^k) = p^k - p^(k-1)`,
左边 `= prod_(i=1)^r sum_(k=0)^(alpha_i) varphi(p_i^k)`
`= prod_(i=1)^r (1 + sum_(k=1)^(alpha_i) (p_i^k - p_i^(k-1)))`
`= prod_(i=1)^r p_i^(alpha_i)`
`= n`.
- `sigma(n)` 是积性函数的和函数, 因此也是积性函数. 利用等比数列求和,
`sigma(n)`
`= prod_(i=1)^r sum_(k=0)^(alpha_i) p_i^k`
`= prod_(i=1)^r (p_i^(alpha_i+1)-1)/(p_i-1)`.
- 与 `sigma(n)` 类似,
`tau(n)`
`= prod_(i=1)^r sum_(k=0)^(alpha_i) 1`
`= prod_(i=1)^r (alpha_i+1)`.
- 利用等比级数求和公式,
左边 `= prod_p sum_(k ge 0) p^(-s k) =` 右边.
卷积
两个算术函数 `f, g` 的 Dirichlet 卷积定义为 `sum_(d | n) f(d)
g(n//d)`, 记为 `f ** g`.
全体算术函数在卷积运算下构成交换幺半群, 即:
- `f ** g = g ** f`;
- `(f ** g) ** h = f ** (g ** h)`;
- `iota(n) := {1, if n = 1; 0, if n gt 1:}` 是卷积运算的单位元:
`iota ** f = f ** iota = f`.
- 若 `f(1) != 0`, 则存在逆元 `f^-1`, 使得 `f ** f^-1 = f^-1 **
f = iota`.
又显然 `(f ** g)(1) = f(1) g(1) != 0`,
故全体可逆的算术函数在卷积运算下构成 Abel 群.
- 两个积性函数的卷积也是积性函数, 故全体可逆的积性函数也构成 Abel 群.
- 这是因为 `sum_(d | n) f(d) g(n//d) = sum_(d | n) f(n // d) g(d)`,
这类似于定积分的区间再现方法.
- 直接计算验证.
- 直接计算验证.
- 用归纳法. 首先由 `1 = iota(1) = f(1) f^-1(1)` 得到 `f^-1(1)
= 1//f(1)`. 假设 `n gt 1`, 且 `f^-1` 对一切小于 `n` 的正整数有定义, 则
`0 = iota(n) = sum_(d | n) f(n // d) f^-1(d)`
`= F(n) + f(1) f^-1(n)`,
故 `f^-1(n) = - F(n)//f(1)`.
- 设 `f, g` 是积性函数, `a, b` 互素. 与前类似, 将 `d` 写成 `a`
的因子和 `b` 的因子之积:
`(f ** g)(a b)`
`= sum_(d | a b) f(d) g(a b // d)`
`= sum_(d_1 | a) sum_(d_2 | b) f(d_1 d_2) g(a // d_1 * b // d_2)`
`= sum_(d_1 | a) f(d_1) g(a // d_1) sum_(d_2 | b) f(d_2) g(b // d_2)`
`= (f**g)(a) (f**g)(b)`.
积性函数的卷积公式 设 `f, g` 为积性函数, 则
`(f ** g)(n) = ??`
Möbius 反演
若已知和函数 `S(n) = sum_(d | n) f(d)`, 该怎样求 `f(n)` 呢?
这就是 Möbius 反演要解决的问题. 首先考虑素数的幂, 我们有
- `S(1) = f(1)`;
- `S(p) = f(1) + f(p)`;
- `S(p^a) = f(1) + f(p) + cdots + f(p^a)`.
因此
- `f(1) = S(1)`;
- `f(p) = S(p) - S(1)`;
- `f(p^a) = S(p^a) - S(p^(a-1))`.
也就是说, 如果我们在素数幂上定义
`mu(p^a) = {
1, if a = 0;
-1, if a = 1;
0, otherwise
:}`,
则当 `n` 是素数的幂时, 有
`f(n) = sum_(d | n) mu(d) S(n//d)`.
利用卷积的记号, 上式简写为 `f = mu ** S = S ** mu`.
现在假设 `mu` 是积性的, 将它的定义域扩充到正整数集:
Möbius 函数 定义为
`mu(n) = {
1, if n = 1;
(-1)^r, if n = p_1 p_2 cdots p_r " 是不同的素数之积";
0, otherwise;
:}`
Möbius 函数的和函数
`sum_(d | n) mu(d) = {
1, if n = 1;
0, if n gt 1;
:}`
用卷积的记号, 上式写为 `mu ** 1 = iota`,
这表明 `mu` 和 `1` 在卷积运算中互为逆元.
等号两边都是积性函数, 因此只需在素数幂上证明它们相等即可.
`n = 1` 时结论显然成立. 考虑素数幂 `n = p^a`, `a ge 1`, 有
`sum_(d | n) mu(d)`
`= mu(1) + mu(p)`
`= 1 - 1 = 0`.
Möbius 反演
若 `S(n) = sum_(d | n) f(d)`, 则
`f(n) = sum_(d | n) mu(d) S(n//d)`.
用卷积的记号表述: 若 `S = f ** 1`, 则 `f = mu ** S`.
右边等于
`sum_(d | n) mu(d) sum_(k | n//d) f(k)`
`= sum_(k | n) f(k) sum_(d | n//k) mu(d)`
`= sum_(k | n) f(k) iota(n//k)`
`= f(n)`.
若 `f` 的和函数 `S` 是积性函数, 则 `f = mu ** S` 也是积性函数.
设 `f(n) = n^s`, 则 `mu ** f = n^s prod_(p | n) (1-p^-s)`.
特别 `mu ** n = varphi`, 即 `varphi ** 1 = n`.
等号两边都是积性函数, 只需证明 `n` 是素数幂 `p^a` 的情形即可.
此时
`(mu ** f)(p^a)`
`= mu(1) f(p^a) + mu(p) f(p^(a-1))`
`= p^(a s) - p^((a-1)s)`
`= n^s (1-p^-s)`.
Dirichlet 特征*
Dirichlet 在 1837 年证明了 Dirichlet 定理: 任给 `(a, q) = 1`,
在算术数列 `n -= a (mod q)` 中一定有无穷多个素数.
在他的证明中, 第一次引入了数论中的重要概念: 特征.
Dirichlet 特征
Dirichlet 特征
设 `q` 为正整数, 模 `q` 的特征 (函数) `chi_q(n): ZZ to CC`
是不恒为零的数论函数, 满足条件:
- `(n, q) gt 1` 时, `chi_q(n) = 0`;
- 周期为 `q`: `chi_q(n+q) = chi_q(n)`;
- 完全可乘: `AA a, b in ZZ`, `chi_q(a b) = chi_q(a) chi_q(b)`.
当 `q` 确定时, 特征也简写为 `chi`.
条件 1, 2 表明 `chi_q` 由它在既约剩余系 `ZZ_q^**` 上的取值完全确定.
- `chi_q^0(n) = { 1, if (n,q) = 1; 0, otherwise :}` 是模 `q` 的特征,
称为主特征;
- Legendre 符号 / Jacobi 符号 `(n/q)` 是模 `q` 的特征.
- 由完全可乘性知 `chi(1) = 1`, `chi(-1) = +-1`.
- `(n, q) = 1` 时,
`chi(n)^(varphi(q))`
`= chi(n^(varphi(q)))`
`= chi(1) = 1`,
这表明 `chi(n)` 是 `varphi(q)` 次单位根, 取值只有有限个.
由于 `chi` 由它在 `ZZ_q^**` 上的取值完全确定, 所以模 `q`
的特征只有有限个.
- 若特征 `chi` 只取实值 `+-1`, 则称它为实特征; 否则 `chi`
至少在某处取虚数, 称为复特征.
模 `q` 的全体特征关于通常的函数乘法构成一个群, 主特征是其单位元.
`chi` 的逆元 `bar chi` 称为它的共轭特征,
其中 `bar chi(n) = bar(chi(n))` (复数的共轭).
- 设 `a | b`, `a, b` 由相同的素因子构成 (仅次数不同), 则模 `a`
的特征一定是模 `b` 的特征;
- `l ge k` 时, 模 `a^k` 的特征一定是模 `a^l` 的特征;
- `chi_a chi_b` 是模 (最小公倍数) `[a, b]` 的特征.
特征的唯一分解定理
设 `(q_1, q_2) = 1`, `q = q_1 q_2`, `chi_q` 是模 `q` 的特征, 则
- 存在唯一的模 `q_1` 的特征 `chi_1` 使得
`n -= 1 (mod q_2)` 时, `chi_q(n) = chi_1(n)`;
- 存在唯一的一对分别模 `q_1, q_2` 的特征 `chi_1, chi_2` 使得
`chi_q = chi_1 chi_2`.
且 `chi_q` 为主特征当且仅当 `chi_1`, `chi_2` 均为主特征;
`chi_q` 为实特征当且仅当 `chi_1`, `chi_2` 均为实特征.
- 推广到有限个特征: 当 `q` 有素因子分解
`q = p_1^(a_1) cdots p_s^(a_s)` 时, 模 `q` 的特征有唯一分解
`chi_q = chi_1 cdots chi_s`,
`quad chi_i` 是模 `p_i^(a_i)` 的特征.
离散 Fourier 变换
记 `e(x) = "e"^(2pi"i"x)`, 则
- `int_0^1 e(n x) dx = {1, if n = 0; 0, if n != 0:}`
- `sum_(k=1)^N e(n/N k) = {N, if n = 0; 0, if (n, N) = 1 and N gt 1:}`