gcd/lcmとmin/maxが同型という話
DDCC2017本戦の問題「B - GCDロボット」の解説の別解、gcd/lcmとmin/maxの話が面白かったので考察してみた。
結論から言うと、gcd/lcmの空間はmin/maxの空間の可算無限個の直積と束同型であることがわかった。
束論のことを何も知らない人が付け焼刃の知識で書いた記事なので大嘘があるかもしれないです。なにか間違いとかあったら教えてください><
B - GCDロボット
問題のURLはここ。
問題文を要約すると、
入力 に対し \begin{align} \min \{ X\in \mathbb{N}_{>0} \mid ^\forall i \in \{ 1, \cdots, N \}, \text{gcd}(X, a_i) = \text{gcd}(Z, a_i) \} \end{align} を出力せよ。
となる(ここで は非負整数全体の集合、 は正の整数全体の集合とします)。
考察すると、これは \begin{align} \text{lcm} \{\text{gcd}( Z, a_i) \mid i \in \{ 1, \cdots, N \} \} \end{align}
を求めることと同値だということがわかるので解ける。
- 提出したらちゃんとACが取れた → ソースコード
で、これがほんとに同値だということを証明する必要があるが、解説pdfでは別解として、整数を素因数分解して各素因数の個数に関して無限次元ベクトルで解釈すると、gcd/lcmの操作がmin/maxの操作に帰着できるという説明がされてた。
考え方が代数における同型の考え方と同じでおもしろいなぁと思い色々と調べてみたら、これは束同型という概念に結びつきそうということがわかった。
gcd/lcm
まず前提としてgcd、lcmは次のように書ける。
\begin{align} \text{gcd}(x, y) &= \prod_{p \in \mathbb{P}} p^{ \min(x_p, y_p) }\\ \text{lcm}(x, y) &= \prod_{p \in \mathbb{P}} p^{ \max(x_p, y_p) } \end{align}
ここで は素数全体の集合、 は をそれぞれ素因数分解したときの素数 の指数を意味するものとする。
次に束に関する諸々の定義。
Def.1 束
を半順序集合(partially ordered set, poset)とする。
このとき
- について が存在するとき、 を束(lattice)という。
Def.2 結び、交わり
を束とする。
このとき
- : と の結び(join)
- : と の交わり(meet)
と定義する。
Rem. 3
- と を明示するために の4つ組を束ということがある。
- 各演算が明らかなときは単に とだけかくこともある。
E.g. 4
- は束である。
- は束である。
- は を割り切る
- 任意の集合 について は束である。
E.g. 5
集合 に対し、 を
で定義する。 このとき は束である。
Def. 6 束準同型
を束とする。 このとき
- と が束準同型(lattice homomorphism)である
と定義する。この を束準同型写像という。
Def. 7 束同型
を束とする。 このとき
と定義する。同型なとき と表記する。
Prop. 8
E.g.4の とE.g.5の について \begin{align} (\mathbb{N}_{>0}, \text{lcm}, \text{gcd}, {}\mid{}) \cong (\mathbb{N}^\mathbb{P}, \max, \min, \leq) \end{align} が成り立つ。
proof
を \begin{align} f\left(\left(x_p\right)_{p \in \mathbb{P}}\right) := \prod_{p \in \mathbb{P}} p^{x_p} \end{align} で定める。
このとき、 について \begin{align} f\left(\min\left(\left(x_p\right)_{p \in \mathbb{P}}, \left(y_p\right)_{p \in \mathbb{P}}\right)\right) =&\,f\left(\left(\min\left(x_p, y_p\right)\right)_{p \in \mathbb{P}}\right)\\ =&\,\prod_{p \in \mathbb{P}} p^{\min\left(x_p, y_p\right)}\\ =&\,\text{gcd}\left( \prod_{p \in \mathbb{P}} p^{x_p}, \prod_{p \in \mathbb{P}} p^{y_p} \right)\\ =&\,\text{gcd}\left( f\left( \left(x_p\right)_{p \in \mathbb{P}}\right), f\left(\left(y_p\right)_{p \in \mathbb{P}} \right)\right) \end{align} が成り立つ。 と についても同様である。 よって は束準同型写像である。
以上より は全単射な束準同型写像なので \begin{align} (\mathbb{N}_{>0}, \text{lcm}, \text{gcd}, {}\mid{}) \cong (\mathbb{N}^\mathbb{P}, \max, \min, \leq) \end{align} が成り立つ
あとがき
以上の議論からgcd/lcm は束の上でmin/maxと同じ構造を持つことがわかった。最高かな。
今まで束論はそういう名前の概念があるくらいしか知らなかったけど、調べてみると色々と応用がききそうで楽しそうだったのでちゃんと勉強したいな。
ところで、DDCCは予選で大爆死して本戦チャレンジ失敗したので来年はなんとしても突破したい。