定义在正整数集合上的函数称为数论函数 (或算术函数).

若算术函数 `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` 为完全积性函数.

  1. 幂函数 `n^s` 是完全积性函数; 特别 `1` 是完全积性函数;
  2. 下文提到的 `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` 互素的正整数之和, 证明:
  1. `f(n) = n varphi(n)//2 = varphi(n^2)//2`;
  2. `f(n)` 为单射.
  1. `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)`.
  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` 时成立.

  1. 对 `ge 3` 的素数 `p`, 有 `varphi(p) gt sqrt p`;
  2. 对素数幂 `p^a`, `a ge 2`, 有 `varphi(p^a) ge sqrt(p^a)`, 等号只在 `p^a = 4` 时成立;
  3. 设 `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` 为积性函数,
  1. 考虑 `n` 的素因子分解, 有 `sum_(d | n) f(d)` `= prod_(p | n) sum_(p^k | n) f(p^k)`,
  2. Euler 乘积 若级数 `sum_(n ge 1) f(n)` 绝对收敛, 则 `sum_(n ge 1) f(n) = prod_p sum_(k ge 0) f(p^k)`. 其中 `prod_p` 表示对全体素数求积.
  1. `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)`.
  2. 设 `p_1=2, p_2=3, cdots` 是全体素数, 由算术基本定理, 正整数 `n` 与下面的多重集合一一对应: `{p_1: alpha_1, p_2: alpha_2, cdots}` 即公式左边的每一项, 恰对应右边的唯一一项.
  1. Euler 函数 `varphi(n)` 的和函数 `sum_(d | n) varphi(d) = n`;
  2. 因子和函数 `sigma(n) = sum_(d | n) d` `= prod_(i=1)^r (p_i^(alpha_1+1)-1)/(p_i-1)`;
  3. 因子个数函数 `tau(n) = sum_(d | n) 1` `= prod_(i=1)^r (alpha_i+1)`;
  4. `f(n) = n^-s` 是积性函数, 因此 Riemann zeta 函数 `zeta(s) = sum_(n ge 1) n^-s` `= prod_p (1-p^-s)^-1`. 这一公式将 `zeta(s)` 与素数联系在一起.
  1. 利用 `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`.
  2. `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)`.
  3. 与 `sigma(n)` 类似, `tau(n)` `= prod_(i=1)^r sum_(k=0)^(alpha_i) 1` `= prod_(i=1)^r (alpha_i+1)`.
  4. 利用等比级数求和公式, 左边 `= prod_p sum_(k ge 0) p^(-s k) =` 右边.

素数无穷的又一证明 [Stein《Fourier Analysis》] 全体素数的倒数和发散: `sum_p 1/p = oo`.

  1. 先证引理: 若 `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` 时, 它的倒数也收敛.
  2. 使用反证法. 若 `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`.

    1. 全体算术函数在卷积运算下构成交换幺半群, 即:
    1. `f ** g = g ** f`;
    2. `(f ** g) ** h = f ** (g ** h)`;
    3. `iota(n) := {1, if n = 1; 0, if n gt 1:}` 是卷积运算的单位元: `iota ** f = f ** iota = f`.
      4. 若考虑函数自然的加法, 则它们构成交换环.
  2. 若 `f(1) != 0`, 则存在逆元 `f^-1`, 使得 `f ** f^-1 = f^-1 ** f = iota`. 又显然 `(f ** g)(1) = f(1) g(1) != 0`, 故全体可逆的算术函数在卷积运算下构成 Abel 群.
  3. 两个积性函数的卷积也是积性函数, 故全体可逆的积性函数也构成 Abel 群.
  1. 交换律是因为 `sum_(d | n) f(d) g(n//d) = sum_(d | n) f(n // d) g(d)`, 这类似于定积分的区间再现方法. 结合律与单位元直接计算验证.
  2. 归纳定义 `f^-1` 如下: 首先由 `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)`.
  3. 设 `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)`.

Möbius 反演

现在假设 `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`.

注意, 若 `S` 是 `f` 的和函数, 则 `S = f ** 1`. 两边同乘 `mu` 就得到 `S ** mu = f`, 这就是下面的 Möbius 反演公式:

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` 也是积性函数.

  1. Euler 函数的和函数 设 `f(n) = n^s`, 则 `mu ** f = n^s prod_(p | n) (1-p^-s)`. 特别取 `s = 1` 有 `mu ** n = varphi`, 即 `varphi ** 1 = n`.
  2. zeta 函数的倒数 `zeta(s)^-1 = sum_(n ge 1) (mu(n))/n^s`.
  1. 等号两边都是积性函数, 只需证明 `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)`.
  2. 代入 Euler 乘积公式 `zeta(s)^-1 = prod_p (1 - p^-s)` `= 1 - sum_p p^-s + sum_(p_1 != p_2) (p_1 p_2)^-s - cdots` 上式每一项都含有有限个不同素数的乘积, 且符号与素数个数的奇偶相关, 这正是 Möbius 函数.

广义反演定理 [知乎@TravorLZH] 设 `alpha, beta` 是互逆的算术函数 (即 `alpha ast beta = iota`), `z` 是非平凡的完全积性函数, `f, g` 是定义在 `[1, +oo)` 的两个实函数, 则 `g(x) = sum_(n le x) z(n) alpha(n) f(x//n)` 当且仅当 `f(x) = sum_(n le x) z(n) beta(n) g(x//n)`.

`z` 非平凡意味着 `z !-= 0`, 于是 `z(1) = 1`. 我们只证一个方向. 假设第一式成立, 则第二式的右边等于 `sum_(n le x) z(n) beta(n) sum_(k le x//n) z(k) alpha(k) f(x//(n k))` 记 `m = n k`, 上式等于 `sum_(m le x) z(m) f(x//m) sum_(k | m) alpha(k) beta(m//k)` `= sum_(m le x) z(m) f(x//m) iota(m)` `= z(1) f(x)` `= f(x)`.

Dirichlet 特征*

[Stein《Fourier Analysis》]

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` 是不恒为零的数论函数, 满足条件:
  1. `(n, q) gt 1` 时, `chi_q(n) = 0`;
  2. 周期为 `q`: `chi_q(n+q) = chi_q(n)`;
  3. 完全可乘: `AA a, b in ZZ`, `chi_q(a b) = chi_q(a) chi_q(b)`.
    4. 当 `q` 确定时, 特征也简写为 `chi`. 条件 1, 2 表明 `chi_q` 由它在既约剩余系 `ZZ_q^**` 上的取值完全确定.
  1. `chi_q^0(n) = { 1, if (n,q) = 1; 0, otherwise :}` 是模 `q` 的特征, 称为主特征 (principal character)或平凡特征 (trivial character) 或单位特征 (unit character);
  2. 模 1 的特征只有一个 `chi_1(n) = 1`, 模 2 的特征也只有一个 `chi_2(n) = {1, n " odd"; 0, n " even" :}`.
  3. Legendre 符号 / Jacobi 符号 `(n/q)` 是模 `q` 的特征.
  1. 由完全可乘性知 `chi(1) = 1`, `chi(-1) = +-1`.
  2. `(n, q) = 1` 时, `chi(n)^(varphi(q))` `= chi(n^(varphi(q)))` `= chi(1) = 1`, 这表明 `chi(n)` 是 `varphi(q)` 次单位根.
  3. 若特征 `chi` 只取实值 `0` 和 `+-1`, 则称它为实特征; 否则 `chi` 至少在某处取虚数, 称为复特征.

将模 `q` 的特征 `chi` 限制在 `G = ZZ_q^**` 上, 就成为 `G` 到单位根群 `C_|G| = C_(varphi(q))` 的群同态. 所有这些同态构成一个有限 Abel 群 `hat G`, 称为 `G` 的特征群. `hat G` 的乘法是通常的函数乘法, 单位元是主特征, `chi` 的复共轭 `bar chi` 正好是它的逆元, 称为它的共轭特征.

特征群 `hat G` 有多大? 若 `G` 是循环群, 设它的生成元 (原根) 为 `a`, 则 `chi(a)` 的取值完全决定了特征函数 `chi`, 于是 `|hat G| = |C_(|G|)| = |G|`. 根据有限 Abel 群的结构定理, `G` 可以分解为循环群的直积: `G ~= C_(n_1) xx cdots xx C_(n_k)`, 根据下文的特征唯一分解定理, `hat G ~= hat C_(n_1) xx cdots xx hat C_(n_k)`, 故 `|hat G| = |G|`. 代入 `G = ZZ_q^**` 可知, 模 `q` 的特征函数共有 `|hat G| = varphi(q)` 个.

    用定义可以验证:
  1. 设 `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` 的特征.
  2. `chi_a chi_b` 是模 (最小公倍数) `[a, b]` 的特征.
    特征的唯一分解定理 设 `(q_1, q_2) = 1`, `q = q_1 q_2`, `chi_q` 是模 `q` 的特征, 则
  1. 存在唯一的一对分别模 `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` 均为实特征.
  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)` 的特征.
    3. 可以将此定理与中国剩余定理作类比.
  1. 唯一性. 观察等式 `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` 的论证类似.
  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)`.
  3. 主特征与实特征. 设整数 `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` 也是一样.

导子与本原特征 设 `chi_q` 是模 `q` 的特征, 则存在一个最小正整数 `d | q` 和一个模 `d` 的特征 `chi_d`, 使得 `chi_q(a) = chi_d(a)`, `quad (a, q) = 1`. 我们称 `d` 是 `chi_q` 的导子 (conductor), 它可以理解为 `chi_q` 的最小正周期 (排除掉与 `q` 不互素的点). 如果 `chi_q` 的导子恰好等于 `q`, 则称它是一个本原特征 (primitive character).

[deepseek] 考虑模 6 的特征 `chi_6(n) = (n/6)`, 其满足 `chi_6(1) = 1`, `chi_6(5) = -1`. 再考虑模 3 的特征 `chi_3(n) = (n/3)`, 其满足 `chi_3(1) = 1`, `chi_3(2) = -1`. 容易验证对一切与 6 互素的 `a` 都有 `chi_6(a) = chi_3(a)`. 由于模 1 和模 2 的特征都只有平凡特征, 可见 `chi_6` 的导子为 3, 它由本原特征 `chi_3` 诱导得到.

  1. 对任意正整数 `q` 都存在模 `q` 的本原特征.
  2. 如果 `chi` 是模 `q ge 3` 的本原实特征, 则存在整数 `d` 满足 `|d| le q`, `d` 不是平方数, 且 `chi(p) = (d/p)`, `quad p !| q, p != 2`. 其中 `(d/p)` 是 Kronecker 符号 (Jacobi 符号的推广).

离散 Fourier 变换

[参见快速 Fourier 变换 (FFT)]

设 `G` 是有限 Abel 群, `|G| = n`. 称同态 `e: G to CC^xx` 为 `G` 上的特征 (函数), 其中 `CC^xx = CC - {0}` 是复数乘法群. 称 `e(a) -= 1` 是主特征. 容易看出对任意 `a in G`, `e(a)` 都是 `n` 次单位根. 因此也可以说 `e: G to C_n`, `C_n` 是 `n` 次单位根群. `G` 上的全体特征按复数乘法构成有限 Abel 群, 称为特征群或对偶群 `hat G`.
例如, 当 `G = ZZ//nZZ` 时, 它的全体特征为 `e_j(k) = exp(2pi"i"j k//n)`, `quad j = 0, cdots, n-1`. 其中 `e_0` 是主特征.

对于无限 Abel 群, 我们要求它的特征是连续函数. 例如 `(RR, +)` 的特征是 `e_xi(x) = exp(2pi"i"xi x)`, `quad xi in RR`. 如果不要求连续性, 可能会出现病态的函数, 参见 Cauchy 函数方程. 不过以下我们只讨论有限 Abel 群. 总假定 `G` 是有限 Abel 群, `|G| = n`.

特征求和公式 对任意 `e in hat G`, `sum_(a in G) e(a)` `= { n, if e " 是主特征"; 0, otherwise :}`

主特征的情形显然. 下设 `e` 是非主特征, 则存在 `b in G` 使得 `e(b) != 1`. 于是 `e(b) sum_(a in G) e(a)` `= sum_(a in G) e(a) e(b)` `= sum_(a in G) e(a b)`. 当 `a` 取遍 `G` 中元素时, `a b` 也取遍 `G` 中元素, 故上式右边等于 `sum_(a in G) e(a)`. 再由 `e(b) != 1` 推出 `sum_(a in G) e(a) = 0`.

  1. `int_0^1 exp(2pi"i" j x) dx = {1, if j = 0; 0, otherwise:}`
  2. `sum_(k=1)^n exp(2pi"i" j k//n) = {n, if j -= 0 (mod n); 0, otherwise:}`

设 `T_1, cdots, T_k` 是复线性空间 `V` 上的酉变换, 即满足 `AA v, w in V`, `(T v, T w) = (v, w)`. 若这些酉变换两两可交换, 则它们可以同时对角化, 即存在 `V` 的一个基底, 使得这些酉变换的表示矩阵同时为对角形.

  1. 首先注意, 由于 `T_i T_j = T_j T_i`, 可以推出 `T_i` 的特征子空间都是 `T_j` 的不变子空间. 例如任取 `v in "Ker"(lambda I - T_i)`, 有 `T_i v = lambda v`, 于是 `T_i (T_j v) = T_j (T_i v) = lambda (T_j v)`, 从而 `T_j v in "Ker"(lambda I - T_i)`.
  2. 对 `k` 作归纳. `k = 1` 时应用谱定理知 `T_1` 可以对角化. 若 `k gt 1`, 对 `T_k` 应用谱定理可知 `V` 有直和分解 `V = O+_(i=1)^s V_(lambda_i)`, 其中 `V_(lambda_i) = "Ker"(lambda_i I - T_k)`. 由 1. 知每个 `V_(lambda_i)` 都是 `T_j` 的不变子空间, `j = 1, cdots, k-1`.
  3. 由归纳假设, `T_1, cdots, T_(k-1)` 可同时对角化, 限制到子空间 `V_(lambda_i)` 上仍是如此, 这给出 `V_(lambda_i)` 的一组基底, 使 `T_1, cdots, T_(k-1)` 的表示矩阵同时为对角形. 但在 `V_(lambda_i)` 上 `T_k` 的表示矩阵也是对角形, 这就在子空间上完成了所有酉变换的对角化. 对每个不变子空间 `V_(lambda_i)` 应用结论, 就得到 `V` 的一组基底, 使得所有酉变换的表示矩阵都为对角形.

特征构成正交基 考虑 `G` 上全体复函数构成的 `n` 维复线性空间 `V`. 对于 `f in V` 也可以写成 `(f_1, cdots, f_n)`. `V` 上的内积定义为 `(f, g) = 1/n sum_(a in G) f(a) bar(g(a))`. 特征的重要性质是, 它们构成空间 `V` 的正交基.

  1. 任取特征 `e in hat G`, 由 `|e(a)| = 1` 有 `(e, e) = 1/n sum_(a in G) e(a) bar(e(a))` `= 1/n sum_(a in G) |e(a)|^2` `= 1`.
  2. 任取特征 `e != f`, 于是 `e f^-1` 不是主特征, 代入特征求和公式 `0 = sum_(a in G) e(a) (f(a))^-1` `= sum_(a in G) e(a) bar(f(a))`.
  3. 我们已经证明特征函数相互正交, 因此线性无关. 下证 `|hat G| = |G| = n`. 一种方法是像前面那样应用有限 Abel 群结构定理, 这里采用另一方法. 对 `AA a in G`, 定义平移变换 `T_a: V to V` 如下: `(T_a f)(x) = f(a x)`, `quad AA x in G`. 显然每个特征函数 `e in hat G` 都是 `T_a` 的特征向量, 特征值为 `e(a)`. 反过来, 能否从 `T_a` 的特征向量得到特征函数? 这就是下面要做的.
  4. `T_a` 是酉线性变换, 因为 `(T_a f, T_a g)` `= 1/n sum_(x in G) (T_a f)(x) bar((T_a g)(x))` `= 1/n sum_(x in G) f(a x) bar(g(a x))` `= 1/n sum_(x in G) f(x) bar(g(x))` `= (f, g)`. 又由 `G` 是 Abel 群, 显然 `T_a T_b = T_b T_a`. 由引理知 `{T_a}_(a in G)` 可以同时对角化, 即存在 `V` 的基底 `B := {f_b}_(b in G)` 使得每个 `f_b` 都是每个 `T_a` 的特征向量.
  5. 下证每个特征向量 `f in B` 都诱导出一个特征函数. 设 `f` 关于 `T_a` 的特征值为 `lambda_a`, 则 `f(a) = f(a * 1) = (T_a f)(1) = lambda_a f(1)`. 由于 `T_a` 是酉变换, `lambda_a != 0`; 又 `f != 0`, 故上式推出 `f(1) != 0`. 对 `AA x in G`, 定义 `w(x) := lambda_x = f(x)//f(1)`, 则 `w(x y) = f(x y)//f(1)` `= (T_x f)(y)//f(1)` `= lambda_x f(y)//f(1)` `= lambda_x lambda_y f(1)//f(1)` `= w(x) w(y)`. 因此 `w` 是一个特征函数.
  6. 显然不同 `f in B` 诱导的 `w` 线性无关, 所以我们一共得到 `n` 个特征函数. 这证明了 `|hat G| ge n`. 另一方面由于正交性, 特征函数必定线性无关, 这证明了 `|hat G| le n`.

离散 Fourier 变换 设 `f` 是 `G` 上的复函数, 定义 `f` 关于特征 `e` 的 Fourier 系数为 `{:hat f:}(e) := (f, e) = 1/n sum_(a in G) f(a) bar(e(a))`. (离散 Fourier 变换) 则 `f` 能展开为 Fourier 级数: `f = sum_(e in hat G) {:hat f:}(e) e`. (离散 Fourier 逆变换) 观察两个等式, 前者将 `n` 维向量 `hat f` 写成 `f` 的线性组合, 而后者反之.

只需注意全体特征构成 `V` 的基底, 因此 `f = sum k_e e`, `k_e in CC`. 等式两边与特征 `e'` 作内积, 利用正交性 `(f, e') = sum k_e (e, e') = k_(e')`, 因此 `f = sum (f, e) e`.

Parseval 恒等式 设 `f` 是 `G` 上的复函数, 则 `||f||^2 = sum_(e in hat G) |{:hat f:}(e)|^2`.

利用内积右槽的共轭线性, `||f||^2 = (f, f)` `= (f, sum {:hat f:}(e) e)` `= sum (f, e) bar({:hat f:}(e))` `= sum |{:hat f:}(e)|^2`.

Dirichlet 定理

    设 `chi` 是模 `q` 的非主特征, 则
  1. `sum_(k=1)^q chi(k) = 0`;
  2. 对任意正整数 `n` 有 `|sum_(k=1)^n chi(k)| le q`.
  1. 这是特征求和公式的推论.
  2. 记 `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` 型素数.
用 Jacobi 符号可以记 `chi(n) = ((-1)/n)`.

对所有模 `q` 的特征 `chi` 求和, 有 `sum_chi chi(a) bar(chi(b))` `= { varphi(q), if a -= b (mod q) and (a, q) = (b, q) = 1; 0, otherwise :}` 特别取 `b = 1` 得到 `sum_chi chi(a)` `= { varphi(q), if a -= 1 (mod q); 0, otherwise :}` 此公式与前面的特征求和公式是对偶的.

若 `(a, q) gt 1` 或 `(b, q) gt 1`, 结果显然等于 0. 下设 `(a, q) = (b, q) = 1`, 考虑有限 Abel 群 `ZZ_q^ast` 上的函数 `delta_b(a) := { 1, if a -= b (mod q); 0, otherwise :}` Fourier 展开得 `delta_b(a) = 1/(varphi(q)) sum_chi (delta_b, chi) chi(a)`. 其中 `(delta_b, chi)` `= sum_(a in ZZ_q^ast) delta_b(a) bar(chi(a))` `= bar(chi(b))`.

对所有模 `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))`. 由前一引理有 `sum_chi chi(p^k) = varphi(q) [p^k -= 1] ge 0`, 于是上式 `ge 0`, 这证明原式左边 `ge 1`.

    设 `chi` 为非主特征, 运用 Euler-Maclaurin 公式与分部求和技巧可得:
  1. `sum_(1 le n le N) 1/n = log N + gamma + O(1/N)`;
  2. `sum_(1 le n le N) 1/sqrt n = 2 sqrt N + c + O(1/sqrt N)`;
  3. `sum_(a le n le b) (chi(n))/n = O(1/a)`;
  4. `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`.

  1. 记 `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` 的素因子只有有限个, 而全体素数的倒数和发散.
  2. 以下考虑非主特征 `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` 上连续可微.
  1. 下证 `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, 这是不可能的.
  2. 再设 `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`.