Ark's Blog

𝔇eadline-𝔇riven 𝔇evelopment

ようこそ

gcd/lcmとmin/maxが同型という話

DDCC2017本戦の問題「B - GCDロボット」の解説の別解、gcd/lcmとmin/maxの話が面白かったので考察してみた。

結論から言うと、gcd/lcmの空間はmin/maxの空間の可算無限個の直積と束同型であることがわかった。

束論のことを何も知らない人が付け焼刃の知識で書いた記事なので大嘘があるかもしれないです。なにか間違いとかあったら教えてください><

B - GCDロボット

問題のURLはここ

問題文を要約すると、

入力  N, Z, a_i に対し \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} を出力せよ。

となる(ここで  \mathbb{N} は非負整数全体の集合、 \mathbb{N}_{>0} は正の整数全体の集合とします)。

考察すると、これは \begin{align} \text{lcm} \{\text{gcd}( Z, a_i) \mid i \in \{ 1, \cdots, N \} \} \end{align}

を求めることと同値だということがわかるので解ける。

で、これがほんとに同値だということを証明する必要があるが、解説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}

ここで  \mathbb{P}素数全体の集合、 x_p, y_p x, y をそれぞれ素因数分解したときの素数  p の指数を意味するものとする。

次に束に関する諸々の定義。

Def.1 束

 (L, \leq) を半順序集合(partially ordered set, poset)とする。

このとき

  •  ^\forall x, y\in L について  \sup\{x, y\}, \inf\{x, y\} が存在するとき、 (L, \leq)束(lattice)という。

Def.2 結び、交わり

 (L, \leq) を束とする。

このとき

  •  x\lor y := \sup\{x, y\} x y結び(join)
  •  x\land y := \inf\{x, y\} x y交わり(meet)

と定義する。

Rem. 3

  •  \lor \land を明示するために  (L, \lor, \land, \leq) の4つ組を束ということがある。
  • 各演算が明らかなときは単に  L とだけかくこともある。

E.g. 4

  •  (\mathbb{N}, \max, \min, \leq) は束である。
  •  (\mathbb{N}_{>0}, \text{lcm}, \text{gcd}, {}\mid{}) は束である。
    •  x \mid y :\Leftrightarrow  x y を割り切る
  • 任意の集合  X について  (2^{X}, \cup, \cap, \subseteq) は束である。

E.g. 5

集合  \mathbb{N}^\mathbb{P} に対し、 \leq, \max, \min

  •  (x_p)_{p \in \mathbb{P}} \leq (y_p)_{p \in \mathbb{P}} :\Leftrightarrow ^\forall p \in \mathbb{P}, x_p \leq y_p
  •  \max\left(\left(x_p\right)_{p \in \mathbb{P}}, \left(y_p\right)_{p \in \mathbb{P}}\right) := (\max(x_p,  y_p))_{p \in \mathbb{P}}
  •  \min\left(\left(x_p\right)_{p \in \mathbb{P}}, \left(y_p\right)_{p \in \mathbb{P}}\right) := (\min(x_p,  y_p))_{p \in \mathbb{P}}

で定義する。 このとき  (\mathbb{N}^\mathbb{P}, \max, \min, \leq) は束である。

Def. 6 束準同型

 (L, \lor_L, \land_L, \leq_L), (K, \lor_K, \land_K, \leq_K) を束とする。 このとき

  •  L K束準同型(lattice homomorphism)である  :\Leftrightarrow ^\exists f: L \rightarrow K \text{ s.t. } ^\forall x, y \in L, \begin{cases}
f(x \lor_L y) = f(x) \lor_K f(y)\\
f(x \land_L y) = f(x) \land_K f(y)
\end{cases}

と定義する。この  f準同型写像という。

Def. 7 束同型

 (L, \lor_L, \land_L, \leq_L), (K, \lor_K, \land_K, \leq_K) を束とする。 このとき

と定義する。同型なとき  L \cong K と表記する。

Prop. 8

E.g.4の  (\mathbb{N}_{>0}, \text{lcm}, \text{gcd}, {}\mid{}) とE.g.5の  (\mathbb{N}^\mathbb{P}, \max, \min, \leq) について \begin{align} (\mathbb{N}_{>0}, \text{lcm}, \text{gcd}, {}\mid{}) \cong (\mathbb{N}^\mathbb{P}, \max, \min, \leq) \end{align} が成り立つ。

proof

 f: \mathbb{N}^\mathbb{P} \rightarrow \mathbb{N}_{>0} を \begin{align} f\left(\left(x_p\right)_{p \in \mathbb{P}}\right) := \prod_{p \in \mathbb{P}} p^{x_p} \end{align} で定める。

 f全単射であることは素因数分解の一意性より明らか。

このとき、 ^\forall \left(x_p\right)_{p \in \mathbb{P}}, \left(y_p\right)_{p \in \mathbb{P}} \in \mathbb{N}^\mathbb{P} について \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} が成り立つ。  \max \text{lcm} についても同様である。 よって  f は束準同型写像である。

以上より  f全単射な束準同型写像なので \begin{align} (\mathbb{N}_{>0}, \text{lcm}, \text{gcd}, {}\mid{}) \cong (\mathbb{N}^\mathbb{P}, \max, \min, \leq) \end{align} が成り立つ  _\blacksquare

あとがき

以上の議論からgcd/lcm は束の上でmin/maxと同じ構造を持つことがわかった。最高かな。

今まで束論はそういう名前の概念があるくらいしか知らなかったけど、調べてみると色々と応用がききそうで楽しそうだったのでちゃんと勉強したいな。

ところで、DDCCは予選で大爆死して本戦チャレンジ失敗したので来年はなんとしても突破したい。

参考文献