メモ

yukicoderでゆるふわgolf

位数Xのアーベル群

出典

この問題は「互いに区別できるX要素の集合に、アーベル群の構造を入れる方法は何通りあるか？」と同じになる。
これはOEISで検索すると見つかる。
A034382 - OEIS
項の数が少なく(注:この記事を書いた当時は20項しかなかった)、求め方も載っていないので、最初のツイートの制約で解くにはまだ足りない。導出を考えてみよう。

以下、単に群といえばアーベル群を指すものとする。
各記号を次の通り定める。
pは素数とする
C_n 位数nの巡回群　\mathbb{Z}/n\mathbb{Z}のこと
S(X) 位数Xのアーベル群の同型類の集合(各同型類とその代表元を同一視する)　これはここだけの記号であり一般的なものではない
Aut(G) Gの自己同型群
GL(k,R) 可換環Rのk×k行列で可逆なものの集合
単に「元gの位数がn」といった場合は「ちょうどn」とは限らないものとする。（例えばC4の元は全て位数4である）


X=\prod p_i^{e_i}とする。
S(X)から群を1つとりGとすると、それと同型になるようにするには、どの元にどれを割り当てるかX!通り。……ではなくX!/#Aut(G)通り。
例えばC_3になるよう{0,1,2}に群構造を入れるとき、0を単位元にしたら、のこりの2つの元のどちらを1,2に割り当てても同じになるので。
ということで、求める答えは
\displaystyle{ \sum_{G \in S(X)} \frac{X!}{\# Aut(G)} }
ここで、a,bが互いに素ならS(ab)=S(a)×S(b)であること、
GとG'の位数が互いに素ならAut(G×G')=Aut(G)×Aut(G')であることから
\displaystyle{ \sum_{G \in S(X)} \frac{X!}{\# Aut(G)}\\ =X!\prod_i \sum_{G \in S(p_i^{e_i})} \frac{1}{\# Aut(G)} }
となる。
（これは\sum_{i,j,k}a_i b_j c_k=(\sum_i a_i)(\sum_j b_j)(\sum_k c_k)と同じ式変形）
位数p^eの群は、必ず\prod_i C_{p^{n_i}}^{k_i} の形で書くことができる。ここで\{n_i\}は狭義単調増加するようとるものとする。
位数の条件からe=\sum_i n_i k_iである。
巡回群は生成元の行き先さえ決めれば準同型が定まる。n_iの大きい方から考えることで、準同型が同型であるためには、C_{p^{n_i}}^{k_i}の生成元たちは送った先でもこの部分を生成していなければならないことがわかる。そのような割り当て方は
\displaystyle{ \# GL(k_i,\mathbb{Z}/p^{n_i}\mathbb{Z})=p^{(n_i-1)k_i^2}\prod_{j=0}^{k_i-1} (p^{k_i}-p^{j}) }通りである。
(n_i=1のとき、\mathbb{Z}/p\mathbb{Z}が体であることから「k次元ベクトルk本を一次独立に選ぶ」ことと対応するので総積部分が得られる。n_i \geq 2のときは、"1の位"をそのように決め、"pの位"から上は自由に決められるので残りの部分が得られる)
また各iについて、送った先でC_{p^{n_i}}^{k_i}にあたる部分以外は位数p^{n_i}であれば何を割り当ててもよいので、\displaystyle{ ( \prod_{j\neq i} p^{\min(n_i,n_j)k_j} )^{k_i} }通りとなる。
（例えばC2×C4×C8のとき、C4の生成元はC2の部分は自由に取れ、C8の部分は位数4の元4つの中から自由にとれる）

よって以上より
\displaystyle{ \# Aut(\prod_i C_{p^{n_i}}^{k_i}) =\prod_i \left( (p^{(n_i-1)k_i^2}\prod_{j=0}^{k_i-1} (p^{k_i}-p^{j})) ( \prod_{j\neq i} p^{\min(n_i,n_j)k_j} )^{k_i} \right) }通りとなる。

ここで\# S(p^e)はeの分割数に等しいことがわかるので、これは対して大きくならず、結局計算のボトルネックになるのはXの素因数分解部分であり、計算量はO(\sqrt{X})である。

……と思ったのだが、プログラムを書いて計算すると、X=16のときがOEISの結果と一致しない。
上の計算式によれば
#Aut(C16)=8
#Aut(C2×C8)=(1×2)×(2×4)=16
#Aut(C4×C4)=(16×3×2)=96
#Aut(C2×C2×C4)=((3×2)×2^2)×(2^2×2)=192
#Aut(C2^4)=(15×14×12×8)=20160
であるから、求める答えは16!×(1/8+1/16+1/96+1/192+1/20160)=4250979532800となる。
一方、OEISでは4248755596800になっている。これは第4項が1/192ではなく1/196なら一致することがわかるが、プログラムを書いてみると、確かにAut(C2×C2×C4)=192であることが確かめられる。そもそも49の倍数になるわけないだろ、なんでだよ


ここまでの議論に誤りを見つけた方、または、OEISの記述が間違っていると確信が持てる方はご一報ください。
なお、上の議論に則って実装したコードはこれです。(mod 10^9+7で出力）
https://wandbox.org/permlink/9RLseRNaHU5CeQiU
自己同型群の位数が計算できてるので実装がバグってることはないはず

(2019/09/13追記)
mathoverflowできいた。
mathoverflow.net
OEISが間違っていた。（えー）
その結果、OEISにsugarknriの名前が載った（！！！？？？！？？！？！？）