定义在正整数集合上的函数称为数论函数 (或算术函数).
若算术函数 `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` 为奇数时 `varphi(2n) = varphi(2) * varphi(n)` `= varphi(n)`.
`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)`.
[群友@Lucifer]
设 `n gt 1` 为正整数, `f(n)` 表示不超过 `n` 的所有与 `n` 互素的正整数之和,
证明:
- `f(n) = n varphi(n)//2 = varphi(n^2)//2`;
- `f(n)` 为单射.
- `n gt 1`, `k lt n//2` 时, 由 `gcd(k, n) = gcd(n-k, n) = 1`
两两配对知道 `f(n)` 是 `n` 的倍数, 且这个倍数等于 `varphi(n)//2`.
例如 `n = 8` 时, `f(8) = 1 + 3 + 5 + 7 = (1+7) + (3+5) = 2*8 = 16`.
利用公式 `varphi(n) = n prod_(p | n) (1 - 1/p)` 即知 `n varphi(n) = varphi(n^2)`.
-
[stack exchange]
记 `g(n) = 2 f(n) = n varphi(n)`, 则 `g(n)` 是积性函数. 下证 `g` 为单射.
令 `n = p_1^(a_1) * cdots * p_s^(a_s)`, 则
`varphi(n) = prod_(k=1)^s p_k^(a_k)(1-1/p_k)`.
令 `p = p_s` 是 `n` 的最大素因子, `p` 在 `n` 中的最大次数是 `a_s`, 记为 `v_p(n) = a_s`.
则由上式知道
`v_p(varphi(n)) = a_s - 1`,
从而
`v_p(g(n)) = v_p(n varphi(n)) = 2 a_s - 1`.
若 `g(m) = g(n)`, 则 `v_p(g(m)) = 2 a_s - 1`. 因此必有 `v_p(m) = v_p(n) = a_s`.
现在从 `m` 和 `n` 中同时约去 `p_s^(a_s)`, 由 `g` 的积性有 `g(n/p_s^(a_s)) = g(m/p_s^(a_s))`.
对 `n` 的最大素因子作归纳即得 `m = n` 的证明.
对正整数 `n ge 2` 成立 `varphi(n) ge sqrt(n//2)`.
等号只在 `n=2` 时成立.
- 对 `ge 3` 的素数 `p`, 有 `varphi(p) gt sqrt p`;
- 对素数幂 `p^a`, `a ge 2`, 有 `varphi(p^a) ge sqrt(p^a)`, 等号只在 `p^a = 4` 时成立;
- 设 `n = 2^(a_0) p_1^(a_1) cdots p_s^(a_s)`, 若 `a_0 = 0` 或 `a_0 ge 2`,
由 1. 2. 的结论易得 `varphi(n) ge sqrt n`.
现在设 `a_0 = 1`, 于是
`varphi(n) ge varphi(2) * sqrt(n//2) = sqrt(n//2)`.
由 1. 知上式等号只在 `n = 2` 时成立.
找出所有满足 `varphi(n) = 2` 的正整数 `n`.
利用不等式 `varphi(n) ge sqrt(n//2)` 知道 `n ge 8`.
易知 `n = 2, 3, 6`.
和函数
算术函数 `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_(p | n) sum_(p^k | n) f(p^k)`,
- Euler 乘积 若级数 `sum_(n ge 0) f(n)` 绝对收敛, 则
`sum_(n ge 0) f(n) = prod_p sum_(k ge 0) f(p^k)`.
其中 `prod_p` 表示对全体素数求积.
- `n = prod_(i=1)^r p_i^(alpha_i)` 的全体正因子可以表示为
`{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 1) 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) =` 右边.
素数无穷的又一证明
[Stein《Fourier Analysis》] 全体素数的倒数和发散:
`sum_p 1/p = oo`.
- 先证引理: 若 `sum a_n` 绝对收敛,
那么 (1) 乘积 `prod (1+a_n)` 收敛. (2) 每项 `a_n + 1 != 0` 时, `prod (1+a_n)^-1` 也收敛.
由已知 `a_n to 0`, 设 `n ge N` 时有 `|a_n| lt 1//2`, 则
`prod_(k=N)^n (1+a_k)`
`= exp(sum_(k=N)^n ln(1+a_k))`.
当 `|x| lt 1/2` 时, 成立不等式 `|ln(1+x)| le |2x|`, 因此
`sum_(k=N)^n |ln(1+a_k)|`
`le sum_(k=N)^n |2 a_k| lt oo`.
因此 `prod_(k=N)^n (1+a_k)` 收敛.
特别每项 `a_n+1 != 0` 时, 它的倒数也收敛.
-
使用反证法. 若 `sum_p 1//p lt oo`, 则乘积 `prod_p (1-1//p)^-1` 收敛,
但另一方面对任意正整数 `n`, 将每个 `1 le k le n` 做素因子分解得到
`sum_(k=1)^n 1/k`
`le prod_(p le n) sum_(k ge 0) 1/p^k`
`= prod_(p le n) (1-1//p)^-1`.
令 `n to oo`, 上式左边发散而右边收敛, 矛盾.
`s gt 1` 时, 对 `zeta(s)` 取对数得
`ln zeta(s) = - sum_p ln(1-p^-s)`
`= sum_p (p^-s + O(p^(-2s)))`
`le sum_p p^-s + O(sum_n n^-2)`
`= sum_p p^-s + O(1)`.
令 `s to 1^+`, 上式左边趋于 `oo`, 这意味着
`sum_p p^-1 ge sum_p p^-s to oo`.
卷积
两个算术函数 `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, if n " 含有平方因子";
:}`
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`.
Möbius 反演不要求 `f` 或 `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 特征*
Euclid 曾通过构造 `p_1 cdots p_n + 1` 证明素数有无穷多.
类似地, 构造 `4 p_1 cdots p_n + 3`, 还能证明 `4n+3` 型素数有无穷多.
1837 年, Dirichlet 证明了如下定理: 任给互素正整数 `a, b`,
存在无穷多形如 `a + n b` 的素数.
在他的证明中, 第一次引入了数论中的重要概念: 特征.
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` 只取实值 `0` 和 `+-1`, 则称它为实特征; 否则 `chi`
至少在某处取虚数, 称为复特征.
将模 `q` 的特征 `chi` 限制在 `G = ZZ_q^**` 上, 就成为 `G` 到单位根群 `C_|G| = C_(varphi(q))`
的群同态.
所有这些同态构成一个有限 Abel 群 `hat G`, 称为 `G` 的特征群.
`hat G` 的乘法是通常的函数乘法, 单位元是主特征,
`chi` 的复共轭 `bar chi` 正好是它的逆元, 称为它的共轭特征.
用定义可以验证:
- 设 `a, b` 由相同的素因子构成 (仅次数不同), 且 `a | b`, 则模 `a`
的特征一定是模 `b` 的特征. 从群同态的观点看, `ZZ_a^**` 是 `ZZ_b^**` 的商群,
`C_(varphi(a))` 是 `C_(varphi(b))` 的子群, 从而有同态
`ZZ_b^**`
`overset"自然同态" --> ZZ_a^**`
`overset chi --> C_(varphi(a))`
`overset"嵌入同态" --> C_(varphi(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, 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)` 的特征.
可以将此定理与中国剩余定理作类比.
-
唯一性. 观察等式 `chi_q = chi_1 chi_2`,
当 `k -= 1 (mod q_2)` 时, `chi_q(k) = chi_1(k)`.
换言之 `chi_1` 应该满足等式
`chi_1(m q_1 + n q_2 + 1) = chi_q(n q_2 + 1)`.
`(**)`
由于 `(q_1, q_2) = 1`, 当 `m, n` 跑遍 `ZZ` 时, `m q_1 + n q_2 + 1` 也跑遍 `ZZ`,
所以 `chi_1` 的值被完全确定.
上式是良定义的, 因为若 `m q_1 + n q_2 = (m+a) q_1 + (n-b) q_2`,
则 `a q_1 = b q_2` 从而 `q_1 | b`.
根据 `chi_q` 的周期性,
`chi_q((n-b) q_2+1) = chi_q(n q_2+1)`.
`chi_2` 的论证类似.
-
存在性. 按 `(**)` 式定义 `chi_1`, 下证它是模 `q_1` 的特征.
由定义 `chi_1` 具有周期 `q_1`. 又, `chi_1` 完全可乘:
`chi_1(a q_1 + b q_2 + 1) chi_1(c q_1 + d q_2 + 1)`
`= chi_q(b q_2+1) chi_q(d q_2+1)`
`= chi_q(b d q_2^2 + (b+d)q_2 + 1)`
`= chi_1((a q_1 + b q_2 + 1)(c q_1 + d q_2 + q))`.
最后, 记 `k = m q_1 + n q_2 + 1`, 则 `(k, q_1) gt 1` 时
`chi_1(k) = chi_q(k - m q_1) = 0`.
类似可证 `chi_2` 是模 `q_2` 的特征. 下证 `chi_q = chi_1 chi_2`,
事实上
`chi_1(m q_1 + n q_2 + 1) chi_2(m q_1 + n q_2 + 1)`
`= chi_q(n q_2+1) chi_q(m q_1 + 1)`
`= chi_q(m n q_1 q_2 + m q_1 + n q_2 + 1)`
`= chi_q(m q_1 + n q_2 + 1)`.
- 主特征与实特征.
设整数 `k` 与 `q_1` 互素,
我们可以找到 `n` 使得 `k + n q_1 -= 1 (mod q_2)`, 于是
`chi_1(k)`
`= chi_1(k + n q_1)`
`= chi_q(k + n q_1)`.
`k + n q_1` 同时与 `q_1, q_2` 互素, 从而与 `q` 互素.
若 `chi_q` 是主特征, 上式右边等于 1, 故 `chi_1` 也是主特征;
若 `chi_q` 是实特征, 上式右边为 `+-1`, 故 `chi_1` 也是实特征.
反之显然 `(k, q) = 1` 时, 同时成立 `(k, q_1) = (k, q_2) = 1`.
故 `chi_1, chi_2` 同时为主特征 (实特征) 时, `chi_q` 也是一样.
Dirichlet 定理
设 `chi` 是模 `q` 的非主特征, 则
- `sum_(k=1)^q chi(k) = 0`;
- 对任意正整数 `n` 有 `|sum_(k=1)^n chi(k)| le q`.
-
任取 `a in ZZ_q^ast`, 则
`chi(a) sum_(k=1)^q chi(k)`
`= sum_(k=1)^q chi(a k)`
`= sum_(k=1)^q chi(k)`.
由于 `chi` 为非主特征, 存在一个 `a` 使得 `chi(a) != 1`, 于是 `sum_(k=1)^q chi(k) = 0`.
-
记 `n = a q + b`, 其中 `0 le b lt q`,
于是
`|sum_(k=1)^n chi(k)|`
`= sum_(k=1)^b |chi(k)|`
`le q`.
`L` 函数
设 `chi(n)` 是模 `q` 的特征. 类似于 Riemann zeta 函数, 定义 `L` 函数如下:
`L(s, chi) := sum_(n ge 1) (chi(n))/n^s`
`= prod_p (1 - chi(p)//p^s)^-1`.
取对数得到
`ln L(s, chi)`
`= - sum_p ln(1-(chi(p))/p^s)`
`= sum_p ((chi(p))/p^s + O(1/p^(2s)))`
`= sum_p (chi(p))/p^s + O(1)`.
当 `chi` 是主特征时,
`L(s, chi) = zeta(s) prod_(p | q) (1-p^-s)`.
特别 `s to 1^+` 时, 和 `zeta(s)` 一样有 `L(s, chi) to oo`.
当 `chi` 是非主特征时, `L(s, chi)` 在 `s gt 0` 上连续可微.
只证 `chi` 为非主特征的情形.
易知对任意 `delta gt 1`, 级数 `L(s, chi) = sum_(n ge 1) (chi(n))/n^s` 在
`s in [delta, oo)` 上绝对收敛且一致收敛,
这推出 `L(s, chi)` 在 `s gt 1` 时连续可微.
然而, 运用分部求和的技巧, 可以将定义域扩张到 `s gt 0`:
记 `s_k = sum_(j=1)^k chi(j)`, 于是
`sum_(k=1)^n (chi(k))/k^s`
`= sum_(k=1)^n (s_k - s_(k-1))/k^s`
`= s_n/n^s + sum_(k=1)^(n-1) s_k(k^-s - (k+1)^-s)`.
记 `f_k(s) = s_k (k^-s - (k+1)^-s)`, 运用中值定理和 `|s_k| le q` 有
`|f_k(s)| le q s k^(-s-1)`.
于是对任意 `delta gt 0`, `sum f_k(s)` 在 `s in [delta, oo)` 上绝对收敛且一致收敛.
同理, 对级数 `L(s, chi) = sum_(n ge 1) (chi(n))/n^s` 逐项微分, 得到级数
`- sum (chi(n))/n^s ln n`,
同样可以分部求和, 得到级数
`sum s_k ((k+1)^-s ln(k+1) - k^-s ln k)`,
然后用中值定理说明, 对任意 `delta gt 0`, 该级数在 `[delta, oo)` 上一致收敛.
综上有 `L(s, chi)` 在 `s gt 0` 上连续可微.
存在无穷多 `4n+1` 型素数.
考虑模 4 的特征 `chi(n)`, 其中 `chi(1) = 1`, `chi(3) = -1`.
定义它的 `L` 函数为
`L(s, chi) = sum_(n ge 1) (chi(n))/n^s`
`= 1 - 1/3^s + 1/5^s - 1/7^s + cdots`.
因此 `L(1, chi) = pi/4 != 0`, `ln L(1, chi)` 有界. 再结合等式
`ln L(s, chi) = sum_p (chi(p))/p^s + O(1)`
推出 `sum_p chi(p)//p` 有界.
另一方面已知 `sum_p 1//p = oo`, 两式相加推出
`sum_(p -= 1(mod 4)) 2/p = oo`.
因此有无穷多 `4n+1` 型素数.
对所有模 `q` 的特征 `chi` 求和, 有
`sum_chi bar(chi(a)) chi(n)`
`= { varphi(q), if n -= a (mod q); 0, otherwise :}`
若 `n -= a (mod q)`, 求和的每项均为 `1`, 结果等于特征群阶数, 即模 `q` 的特征总数 `varphi(q)`.
否则,
🚧
对所有模 `q` 的特征 `chi` 求乘积, 有
`prod_chi L(s, chi) ge 1`.
注意, 这表明上式左边是实数.
取对数,
`sum_chi ln L(s, chi)`
`= sum_chi sum_p -ln(1-(chi(p))/p^s)`
`= sum_chi sum_p sum_(k ge 1) (chi(p)^k)/(k p^(k s))`
`= sum_p sum_(k ge 1) sum_chi (chi(p^k))/(k p^(k s))`.
由前一引理 (取 `a = 1`) 有 `sum_chi chi(p^k) = varphi(q) [p^k -= 1]`,
于是上式等于
`varphi(q) sum_p sum_(k ge 1) ([p^k -= 1])/(k p^(k s)) ge 0`.
这证明原式左边 `ge 1`.
设 `chi` 为非主特征,
运用 Euler-Maclaurin 公式与分部求和技巧可得:
- `sum_(1 le n le N) 1/n = log N + gamma + O(1/N)`;
- `sum_(1 le n le N) 1/sqrt n = 2 sqrt N + c + O(1/sqrt N)`;
- `sum_(a le n le b) (chi(n))/n = O(1/a)`;
- `sum_(a le n le b) (chi(n))/sqrt n = O(1/sqrt a)`.
Dirichlet 定理
[Stein《Fourier Analysis》]
对任意互素正整数 `a, q`, 存在无穷多形如 `a + q n` 的素数. 事实上它们的倒数和发散:
`sum_(p -= a (mod q)) 1/p = oo`.
-
记 `chi_0` 为模 `q` 的主特征. 由
`sum_(p -= a (mod q)) (varphi(q))/p^s`
`= sum_chi bar(chi(a)) sum_p (chi(p))/p^s`
`= sum_p (chi_0(p))/p^s + sum_(chi != chi_0) bar(chi(a)) sum_p (chi(p))/p^s`
`= A + B`.
上式第一项中 `chi_0(p) = 1` 当且仅当 `(p, q) = 1`, 于是
`A = sum_((p, q) = 1) 1/p^s to oo`, `quad s to 1^+`.
这是因为 `q` 的素因子只有有限个, 而全体素数的倒数和发散.
-
以下考虑非主特征 `chi != chi_0`.
只需证 `s to 1^+` 时 `B` 有界, 即 `sum_p chi(p)//p^s` 有界.
利用 `L` 函数的连续性以及估计
`ln L(s, chi) = sum_p chi(p)//p^s + O(1)`,
只需证 `0 lt |L(1, chi)| lt oo`.
其中 `lt oo` 的部分是显然的, 因为 `chi` 为非主特征时, `L(s, chi)` 在 `s gt 0` 上连续可微.
- 下证 `L(1, chi) != 0`, 这是最深刻和困难的部分. 先设 `chi` 是复特征,
若 `L(1, chi) = 0`, 则由中值定理有
`|L(s, chi)| le |L'(s, chi)| |s-1|`
`= O(|s-1|)`,
`quad s to 1^+`.
另一方面, 根据 Euler-Maclaurin 公式,
`zeta(s)` 满足
`zeta(s) = O(|s-1|^-1)`, `quad s to 1^+`,
从而主特征的 `L` 函数 `L(s, chi_0)` 也满足相同估计.
由, 乘积
`prod_chi L(s, chi) ge 1`.
如果存在复特征 `chi` 使得 `L(1, chi) = 0`, 则 `L(1, bar chi) = bar(L(1, chi)) = 0`,
并且 `chi != bar chi`. 这表明上述乘积中, 至少两项以 `O(|s-1|)` 的速度趋于零,
但只有一项 `L(s, chi_0)` 以 `O(|s-1|^-1)` 的速度趋于无穷.
乘积的其它项都有界, 而整个乘积大于 1, 这是不可能的.
-
再设 `chi != chi_0` 为实特征, 考虑求和
`S_N = sum_(m n le N) (chi(n))/sqrt(m n)`.
其中 `m, n` 为正整数. 使用所谓“双曲线下求和”的技巧, 有
`S_N = sum_(1 le k le N) sum_(m n = k) (chi(n))/sqrt(m n)`
`= sum_(1 le k le N) 1/sqrt k sum_(n | k) chi(n)`.
我们估计 `T_k = sum_(n | k) chi(n)`.
事实上, 当 `k = p^a` 时,
`T_k = sum_(n | k) chi(n) = sum_(j=0)^a chi(p^j)`
`= {a+1, if chi(p) = 1; (1-chi(p)^(a+1))/(1-chi(p)), otherwise:}`
由于 `chi` 是实特征, 上式总是 `ge 0`, 并且当 `a` 是偶数时上式 `ge 1`.
一般地, 将 `k` 分解为素数幂, 则 `T_k ge 0`, 且当 `k` 为平方数时 `T_k ge 1`.
总之, `N to oo` 时
`S_N = sum_(1 le k le N) T_k/sqrt k`
`ge sum_(1 le j le sqrt N) 1/j`
`to oo`.
另一方面, `S_N` 可以分为三个求和 `S_"I" + S_"II" + S_"III"`, 其中
`S_"I" = sum_(m lt sqrt N) sum_(sqrt N lt n le N//m)`,
`S_"II" = sum_(m le sqrt N) sum_(n le sqrt N)`,
`S_"III" = sum_(n lt sqrt N) sum_(sqrt N lt m le N//n)`.
事实上由,
`S_"I" = sum_(m lt sqrt N) 1/sqrt m sum_(sqrt N lt n le N//m) (chi(n))/sqrt n`
`= sum_(m lt sqrt N) 1/sqrt m O(1/sqrt N)`
`= O(1)`,
`S_"II" + S_"III"`
`= sum_(n le sqrt N) (chi(n))/sqrt n sum_(m le N//n) 1/sqrt m`
`= sum_(n le sqrt N) (chi(n))/sqrt n (2 sqrt(N//n) + c + O(1//sqrt(N//n)))`
`= 2 sqrt N sum_(n le sqrt N) (chi(n))/n`
`+ c sum_(n le sqrt N) (chi(n))/sqrt n`
`+ O(1)`
`= 2 sqrt N (L(1, chi) - sum_(n gt sqrt N) (chi(n))/n)`
`+ O(1) + O(1)`
`= 2 sqrt N (L(1, chi) - O(1//sqrt N))`
`= 2 sqrt N L(1, chi) + O(1)`.
两式相加得到 `S_N = 2 sqrt N L(1, chi) + O(1)`, 于是从 `S_N to oo` 立即得到 `L(1, chi) != 0`.
离散 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 k//N) = {N, if n = 0; 0, if (n, N) = 1 and N gt 1:}`