JMO予選12番を単因子論で解く

表題の通りです. https://mathlog.info/articles/J9UQTOoRHts6LWMW8jZc と本質的に同じな気もします.

問題

問題は https://www.imojp.org/archive/mo2024/problems/jmo34yqa.pdf 　から引用した.

解答

初等的考察

すこし, 初等的な考察をする. $\gcd(k,2100)=1 \iff \gcd(k,210)=1 $なので, $a_i=a_{i+210}$が成立する. ここで, $c_i=b_i+b_{i+210}+\ldots +b_{i+1890}$と置くと,
$$ a_i\equiv \sum_{\substack{\gcd(j-i,210)=1 \\ 1\leqq j\leqq 210}} c_j \pmod{2100} $$
が成立する. 逆に, このような$a_i$が条件を満たすのはほぼ自明. ($ c_i$を$0$拡張して$b_i$にすればよい.) よって, $a,b$の長さは$210$として解いてよい.

言い換え

まず, 問題を環上の加群の話に置き換える.
$R=\Z/2100\Z$, と置く.
自然数$n$に対し, $R^n$の標準基底を$e_i(0\leq i< n)$と置き, この添え字は$\mod{n}$で考える.
$R$線形写像$f_n:R^n\to R^n$を,
$$ e_i \mapsto \sum_{\substack{\gcd(j,n)=1 \\ 0\leq j< n}} e_{j+i} $$
となるように定める.
このとき問題は$\#\mathrm{Im}(f_{210})$を求めることに帰着される.

テンソル積への分解

次に, $f_{210}$をテンソル積に分解することを考える.
$R$線形写像$\iota:R^{210}\to R^2\otimes R^3\otimes R^{5}\otimes R^7$を,
$$ e_i\mapsto e_i\otimes e_i\otimes e_i\otimes e_i $$
と定める. 中国剰余定理より$\iota$は, 全単射. さらに, $(f_2\otimes f_3\otimes f_{5} \otimes f_7)\circ \iota=\iota \circ f_{210} $が成立する. 実際, 両辺の$R$線形より,$e_i$を代入して等しければよい. これは次のように確かめられる:
\begin{align} &(f_2\otimes f_3\otimes f_{5} \otimes f_7)\circ \iota(e_i)\\ =& f_2(e_i)\otimes f_3(e_i)\otimes f_{5}(e_i)\otimes f_7(e_i)\\ =& \sum_{\gcd(p,2)=1,\gcd(q,3)=1,\gcd(r,5)=1,\gcd(s,7)=1} e_{i+p}\otimes e_{i+q}\otimes e_{i+r}\otimes e_{i+s}\\ =& \sum_{\gcd(j,210)=1} e_{i+j}\otimes e_{i+j} \otimes e_{i+j} \otimes e_{i+j}\\ =& \sum_{\gcd(j,210)=1} \iota(e_{i+j})\\ =& f_{210}(e_i) \end{align}
ここで, $j$は$0$から$209$, $p$は$0$から$1$, $q$は$0$から$2$,$r$は$0$から$4$, $s$は$0$から$6$を渡る. 3番目の等式では, 中国剰余定理と, $\gcd(k,210)=1\iff \gcd(k,p)=1(p\in \{2,3,5,7\})$を用いた.
$\iota$が全単射だったことを思い出すと, $\mathrm{Im}(f_{210})=\mathrm{Im}(f_2\otimes f_3\otimes f_{5} \otimes f_7)$である.

$f_p$の単因子

次に$f_p$($p$は素数)の単因子を求める. $R^p$の元の列$t_0\ldots t_{p-1}$, および$u_0,u_1,\ldots u_{p-1}$を次のように定める.
$$ t_i=\begin{cases} \sum_{i=0}^{p-1} e_i && i=0\\ e_i && i>0 \end{cases} $$
$$ u_i=\begin{cases} \sum_{i=0}^{p-1} e_i && i=0\\ f(e_i) && i>0 \end{cases} $$
$(t_i)_i$が$R^n$の生成元であることはあきらか. $(u_i)_i$も, $u_0-u_i=e_i$に注意すると, $R^n$を生成することがわかる. $R^n$が有限集合であることから, 結局$(t_i)_i,(u_i)_i$は$R^n$の基底である.
よって, $f(e_0)=(p-1)u_0$に注意すると, $f_p$の単因子は$(p-1,1,\ldots 1)$である.

答え

最後にここまでをまとめ, 答えを出す.
一般に$f$の単因子が$(a_i)_i$, $g$の単因子が$(b_j)_j$のとき, $f\otimes g$の単因子は$(a_ib_j)_{i,j}$である.
よって, $f_2\otimes f_3\otimes f_{5} \otimes f_7$の単因子は$(2^{\delta_{q,0}+2\delta_{r,0}+\delta_{s,0}}3^{\delta_{s,0}})_{p,q,r,s}$となる. ($p,q,r,s$の渡る範囲は前の$\sum$と同じ. ) $R=\Z/2100\Z$では, $4,8,16$は同伴である. よって, 単因子としてありうるのは, $1,2,4,3,6,12$のどれか.

$2$で$1$回割れる単因子の数

$(q,r,s)$の中に$0$が$1$個以上あることと同値.
$2\times 3\times 5\times 7-2\times 2\times 4\times 6=114$個.

$2$で$2$回割れる単因子の数

$r=0$または$q=s=0$と同値.
$r=0$となるのが, $2\times 3\times 1\times 7=42$個.
$q=s=0$となるのが, $2\times 1\times 5\times 1=10$個.
かぶりが$2$個あるので, $42+10-2=52$個.

$3$で$1$回割れる単因子の数

$s=0$と同値. $2\times 3\times 5\times 1=30$個

よって, $\frac{2100^{210}}{2^{114}2^{52}3^{30}}=2^{256}3^{180}5^{420}7^{210}$が答え.

感想

過去に予選で, 本質的に$V_4$の話をする問題が出たことはあったりするんですが, ここまで大学数学が刺さる予選問題もでるんですね.
$2100$という数, 作者の勘で答えを当てさせない気概を感じます. 平方因子をもちつつ, $\phi(2100)\not\mid 2100$なので. あと$2^{256}$が出てくるのがややウケますね.