Ark's Blog

参加記や備忘録などを書いていきます

ようこそ

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

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

結論から言うと、gcd/lcmの空間は、min/maxの空間の可算無限個の直積と束同型っぽい。

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

B - GCDロボット

問題のURLはここ

問題文を要約すると、

入力$N, Z, a_i$に対し $$ \min \{ X\in \mathbb{N}_{>0} \mid ^\forall i \in \{ 1, \cdots, N \}, \text{gcd}(X, a_i) = \text{gcd}(Z, a_i) \} $$ を出力せよ。

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

考察すると、これは

$$ \text{lcm} \{\text{gcd}( Z, a_i) \mid i \in \{ 1, \cdots, N \} \} $$

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

で、これがほんとに同値だということを証明する必要があるんだけど、解説pdfでは別解として、整数を素因数分解して各素因数の個数に関して無限次元ベクトルで解釈すると、gcd/lcmの操作がmin/maxの操作に帰着できるという説明がされてた。

考え方が代数における同型の考え方と同じでおもしろいなぁと思い色々と調べてみたら、これは束同型という概念に結びつきそうということがわかった。

gcd/lcm

まず前提としてgcd、lcmは次のように書ける。

$$\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) }$$

ここで$\mathbb{P}$は素数全体の集合、$x_p$は$x$を素因数分解したときの素数$p$の指数を意味するものとする。($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}$

Def. 7 束同型

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

$L$と$K$が束同型(lattice isomorphism)である。 $:\Leftrightarrow$ 全単射な束準同型写像$f: L\rightarrow 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)$について

$$(\mathbb{N}_{>0}, \text{lcm}, \text{gcd}, \mid) \cong (\mathbb{N}^\mathbb{P}, \max, \min, \leq)$$ が成り立つ。

proof

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

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

このとき、$^\forall \left(x_p\right)_{p \in \mathbb{P}}, \left(y_p\right)_{p \in \mathbb{P}} \in \mathbb{N}^\mathbb{P}$について

$$\begin{aligned} 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{aligned}$$ が成り立つ。

$\max$と$\text{lcm}$についても同様。 よって$f$は束準同型写像である。

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

あとがき

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

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

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

参考文献