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

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

問題

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

解答

初等的考察

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

言い換え

まず, 問題を環上の加群の話に置き換える.
$R=\mathbb{Z}/2100\mathbb{Z}$, と置く.
自然数$n$に対し, $R^n$の標準基底を$e_i(0\le i<n)$と置き, この添え字は$\mathrm{mod}n$で考える.
$R$線形写像$f_n:R^n\to R^n$を,
$$e_i\mapsto \sum _{\begin{array}{c}gcd(j,n)=1\\ 0\le j<n\end{array}}{e}_{j+i}$$
となるように定める.
このとき問題は$\mathrm{\#}\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{array}{rl}& (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{array}$$
ここで, $j$は$0$から$209$, $p$は$0$から$1$, $q$は$0$から$2$,$r$は$0$から$4$, $s$は$0$から$6$を渡る. 3番目の等式では, 中国剰余定理と, $gcd(k,210)=1⟺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\dots t_{p-1}$, および$u_0,u_1,\dots u_{p-1}$を次のように定める.
$$t_i=\{\begin{array}{lll}\sum _{i=0}^{p-1}{e}_i& & i=0\\ e_i& & i>0\end{array}$$
$$u_i=\{\begin{array}{lll}\sum _{i=0}^{p-1}{e}_i& & i=0\\ f(e_i)& & i>0\end{array}$$
$(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,\dots 1)$である.

答え

最後にここまでをまとめ, 答えを出す.
一般に$f$の単因子が$(a_i{)}_i$, $g$の単因子が$(b_j{)}_j$のとき, $f\otimes g$の単因子は$(a_i{b}_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=\mathbb{Z}/2100\mathbb{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$という数, 作者の勘で答えを当てさせない気概を感じます. 平方因子をもちつつ, $\varphi (2100)\nmid 2100$なので. あと$2^{256}$が出てくるのがややウケますね.