n 阶阿贝尔群计数

· · 算法·理论

阿贝尔敲可爱的

发现自己还不会 n 阶阿贝尔群的计数。

首先,有个定理叫有限阿贝尔群的准素分解定理,内容是设 G 是一个 n 阶阿贝尔群,n = pm,且 p,m 互质。则一定存在一个 p 阶子群 Am 阶子群 B,满足 AB = g,且 A,B 的交集只有单位元。

证明:由斐蜀定理,一定有 u, v,满足 up + vm = 1。那么,对于 G 中任意一个元素 g,有 g = g^1 = g^{up+vm} = (g^p)^u(g^m)^v。设 (g^p)^u = x,(g^m)^v=y。因为 G 中元素的阶一定为 n 的约数,所以 x^m = (g^{pm})^u = e^u=e,y^p = (g^{pm})^v = e^v=e,那么,x 的阶数为 m 的因数,y 的阶数为 p 的因数。那么对于任意 g \in G,总有 x \in A, y \in B,使得 xy = g

再证明只有 e 满足 x \in A, x \in B。假设 x \in A, x \in B,那么有 x^p = x^m = e,则 x = x^{up+vm} = x^{up}x^{vm}=e^pe^m=e

这个定理告诉我们,设 n = \prod_{k=1}^m{p_k^{\alpha_k}}, 则对于一个 n 阶的阿贝尔群 G,则一定存在 m 个阿贝尔群 G_1,G_2,\cdots,G_m,使得 \prod_{k=1}^m G_k=G,且 G_k 的阶为 p_k^{\alpha_k}

那么,让我们来考虑 G_i。设其中阶最大的元素是 aa 的阶为 p^m, 令 A = \langle a \rangle,设 BG_i 中与 A 交集为单位元的最大的子群。那么有 AB = G。证明:

x \in G_i, x \notin AB。那么,根据柯西定理,x^p \in AB。设 x^p = a^i b(b \in B)。令 x 的阶为 p^k。因为 a 是阶最大的元素,所以 k\le m。所以 (x^p)^{p^k} = (a^i b(b \in B))^{p^k} \Rightarrow a^{ip^k}=b^{-p^k},但是,A,B 的交集只有 e,所以 a^{ip^k}=e,那么 ip^k 一定是 p^m 的倍数,可以推导出 i 一定是 p 的倍数。

i = cp,y=xa^{-c}。则有 x^p=a^{pc}b,y^p=x^pa^{-pc}=b,所以 y^p \in B。所以我们可以将 y 放入 B 中,构造出一个更大的群。但是这与我们BG_i 中不在 A 中的元素这个条件不符合。

所以,AB=G_i。注意到我们其实可以再细分 B,使得 G_i 变为一堆循环群的乘积。那么,方案数就是幂次的划分数。

所以,n 阶阿贝尔群的个数就是 n 质因数分解后每个数幂次的划分数的乘积。