エレファントな整数論(16) - エレファント・コンピューティング調査報告

自由生成可換モノイド

可換モノイド $M$ (演算を $+$ と書きます)の部分集合 $X$ は以下の条件 (F1) を満たすとします。

(F1)

$m, n \ge 1$ 、 $x_1, x_2, \cdots , x_m, y_1, y_2, \cdots , y_n \in X$ 、 $x_1 + x_2 + \cdots + x_m = y_1 + y_2 + \cdots + y_n$ ならば、任意の $i \in \{1, 2, \cdots, m\}$ に対して $j \in \{1, 2, \cdots, n\}$ が存在して、 $x_i = y_j$ となって、 $x_1, x_2, \cdots , x_m$ から $x_i$ を除いたものを $x'_1, x'_2, \cdots , x'_{m-1}$ 、 $y_1, y_2, \cdots , y_n$ から $y_j$ を除いたものを $y'_1, y'_2, \cdots , y'_{n-1}$ とすると、
$x'_1 + x'_2 + \cdots + x'_{m-1} = y'_1 + y'_2 + \cdots + y'_{n-1}$
となります。

可換モノイド $M$ の部分集合 $X$ が (F1) を満たすならば以下の (F2) を満たします。

$x_1, x_2, \cdots , x_n \in X$ 、 $a_1, a_2, \cdots , a_n, b_1, b_2, \cdots , b_n \in \mathbb{N}$ 、 $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b_1 x_1 + b_2 x_2 + \cdots + b_n x_n$ ならば、任意の $i \in \{1, 2, \cdots, n\}$ に対して $a_i \le b_i$ となり、 $c \le a_i$ に対して
$a_1 x_1 + a_2 x_2 + \cdots + (a_i - c) x_i + \cdots + a_n x_n = b_1 x_1 + b_2 x_2 + \cdots + (b_i - c) x_i + \cdots + b_n x_n$
となります。

[証明] $a_i = 0$ のときは主張は成り立っています。

$a_i > 0$ とすると (F1) より $b_i > 0$ 、 $a_1 x_1 + a_2 x_2 + \cdots + (a_i - 1) x_i + \cdots + a_n x_n = b_1 x_1 + b_2 x_2 + \cdots + (b_i - 1) x_i + \cdots + b_n x_n$ となります。

これを繰り返すと主張が成り立ちます。[証明終わり]

可換モノイド $M$ の部分集合 $X$ が (F2) を満たすならば以下の (F3) を満たします。

[証明] (F2) より任意の $i \in \{1, 2, \cdots, n\}$ に対して $a_i \le b_i$ となります。左辺と右辺を入れ替えると $a_i \ge b_i$ となり $a_i = b_i$ となります。[証明終わり]

$\mathbb{N}[(X)]$ を、 $X$ から $\mathbb{N}$ への写像 $f$ で $X_f = \{ x \in X \mid f(x) \ne 0 \}$ が有限集合であるもの全体の集合とすると、 $\mathbb{N}[(X)]$ は写像の加法に関して可換モノイドとなります。

(F4) $M$ が $X$ で生成された可換モノイドで (F3) を満たすならば、モノイドの同型 $\bar{\varphi}: \mathbb{N}[(X)] \to M$ が存在します。

[証明] $\varphi: X \to M$ を包含写像( $x \in X$ に $x \in M$ を対応させる写像)とします。 $f \in \mathbb{N}[(X)]$ は $X$ から $\mathbb{N}$ への写像で $X_f = \{ x \in X \mid f(x) \ne 0 \}$ が有限集合であるものとなります。 $X_f = \{ x_1, x_2, \cdots, x_n \}$ とします。 $\bar{\varphi}(f) = f(x_1) \varphi(x_1) + f(x_2) \varphi(x_2) + \cdots + f(x_n) \varphi(x_n)$ と定義します。この定義は $X_f$ を含む任意の有限集合で定義しても同じものとなります。よって $f, g \in \mathbb{N}[(X)]$ に対して、 $X_{f+g}$ のかわりに $X_f \cup X_g$ を含むある有限集合 $X'$ で定義しても同じものになり、 $X_f$ のかわりに $X'$ としても $X_g$ のかわりに $X'$ としても同じものになります。

よって $\bar{\varphi}(f + g) = \bar{\varphi}(f) + \bar{\varphi}(g)$ が成り立つので $\bar{\varphi}$ はモノイドの準同型となります。

$\bar{\varphi}(f) = \bar{\varphi}(g)$ とします。 $X_f \cup X_g \subseteq \{x_1, x_2, \cdots, x_n \}$ とします。 $\bar{\varphi}(f) = f(x_1) \varphi(x_1) + f(x_2) \varphi(x_2) + \cdots + f(x_n) \varphi(x_n)$ 、 $\bar{\varphi}(g) = g(x_1) \varphi(x_1) + g(x_2) \varphi(x_2) + \cdots + g(x_n) \varphi(x_n)$ であるから (F3) より任意の $x_i$ に対して $f(x_i) = g(x_i)$ となって、 $f = g$ となります。よって $\bar{\varphi}$ は単射となります。

$M$ は $X$ で生成されるので $\bar{\varphi}$ は全射となります。

よって $\bar{\varphi}$ はモノイドの同型となります。[証明終わり]

このような可換モノイドを自由生成可換モノイドと呼ぶことにします。

整数の素因数分解の一意性

整数全体の環は整域なので、以前に述べた整域に関する議論が成り立ちます。
$M = \{ P \mid P \ は有限個の素数の積で生成される単項イデアル \}$
とおくと、 $M$ はイデアルの乗法に関して自由生成可換モノイドとなります。

よって $m, n \ge 1$ とし、 $p_1, p_2, \cdots , p_m, q_1, q_2, \cdots , q_n$ を素数、 $p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n$ とすると、 $m = n$ であり、適当に並べ替えると任意の $1 \le i \le m$ に対して $p_i = q_i$ または $p_i = -q_i$ となります。

正の素数に限定した場合を考えると $m, n \ge 1$ とし、 $p_1, p_2, \cdots , p_m, q_1, q_2, \cdots , q_n$ を正の素数、 $p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n$ とすると、 $m = n$ であり、適当に並べ替えると任意の $1 \le i \le m$ に対して $p_i = q_i$ となります。

自由生成可換モノイドに関する帰納法

$f \in \mathbb{N}[(X)]$ に対して $\displaystyle \#f = \sum_{x \in X} f(x)$ と定義すると、 $\# : \mathbb{N}[(X)] \to \mathbb{N}$ はモノイドの準同型となります。 $n \in \mathbb{N}$ に対して $X * n = \{ f \in \mathbb{N}[(X)] \mid \#f = n \}$ と定義します。すると $\mathbb{N}[(X)] = \displaystyle \bigcup_{n \in \mathbb{N}} (X * n)$ となります。よって $\{0\} \subseteq M \subseteq \mathbb{N}[(X)]$ が