2021-01-31

エレファントな整数論(18)

整数の素因数分解

整数 $a \notin I = \{0, 1, -1\}$ が素数であることは

(1) $a = bc$ ならば $b = \pm 1$ または $c = \pm 1$

であることと同値となります。

素数全体の集合を $P$ とし、 $f(a)$ を $a$ の絶対値とします。

$X_n = \{ a \in \mathbb{Z} \setminus I \mid f(a) \le n \}$ とおくと $\displaystyle \mathbb{Z} = I \cup \bigcup_{n \in \mathbb{N}} X_n$ となります。

$X, Y \subseteq \mathbb{Z}$ に対して $XY = \{ xy \mid x \in X, y \in Y \}$ 、 $X^* = X \cup XX \cup XXX \cup \cdots$ と書くことにします。

(2) $a \notin I$ ならば $a$ は素数の積で表すことができます。

[証明] (1)より $X_n \subseteq P \cup X_{n-1}^*$ となります。よって
$\begin{eqnarray*} X_n & \subseteq & P^* \cup P^* X_{n-1}^* \cup X_{n-1}^* \\ & \subseteq & P^* \cup P^*(P^* \cup X_{n-2}^* )^* \cup (P^* \cup X_{n-2}^* )^* \\ & \subseteq & P^* \cup P^* X_{n-2}^* \cup X_{n-2}^* \\ \end{eqnarray*}$
となって、これを繰り返して $X_n \subseteq P^* \cup P^* X_{1}^* \cup X_{1}^* \subseteq P^*$ となります。

よって $\displaystyle \mathbb{Z} = I \cup \bigcup_{n \in \mathbb{N}} X_n = I \cup P^*$ となります。よって $a \notin I$ ならば $a$ は素数の積で表すことができます。[証明終わり]

整数の素因数分解の多重集合としての一意性

重複度を含めた集合を多重集合*1と呼びます。多重集合 $\{| x_1, x_2, \cdots , x_m |\}$ とは、通常の集合とは異なり、 $x_1, x_2, \cdots , x_m$ の中に重複するものがあったとき、その出現する回数が異なれば多重集合としては異なるものとするものです。

多重集合 $\{| x_1, x_2, \cdots , x_m |\}$ と $\{| y_1, y_2, \cdots , y_n |\}$ は全単射 $g: \{1, 2, \cdots, m\} \to \{1, 2, \cdots, n\}$ が存在して任意の $i \in \{1, 2, \cdots, m\}$ に対して $x_i = y_{g(i)}$ であるとき $\{| x_1, x_2, \cdots , x_m |\} = \{| y_1, y_2, \cdots , y_n |\}$ とします。

整数 $a$ の倍数全体の集合を $(a)$ とします。

(3) $(a)(b) \subseteq (p) \implies (a) \subseteq (p) \lor (b) \subseteq (p)$

を満たす整数 $p$ で $p \notin \{0, 1, -1\}$ であるもの全体の集合を $Q$ とします。

(4) $Q \subseteq P$

[証明]
$\begin{eqnarray*} p \in Q & \iff & \bigl[ \ (a)(b) \subseteq (p) \implies (a) \subseteq (p) \lor (b) \subseteq (p) \ \bigr] \\ & \implies & \bigl[ \ ab = p \implies a \in (ab) \lor b \in (ab) \ \bigr] \\ & \iff & \bigl[ \ ab = p \implies (b) = (1) \lor (a) = (1) \ \bigr] \\ & \iff & p \in P \end{eqnarray*}$
[証明終わり]

(5) $\mathbb{Z} = I \cup Q^*$

[証明] (4) より $Q$ に対しても (2) が成り立ちます。[証明終わり]

(6) $P = Q$

[証明] (5) より $P = P \cap Q^* \subseteq Q$ となります。 [証明終わり]

(7) $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$ ならば任意の $i$ に対して $j$ が存在して $p_i = q_j$ となります。

[証明] $(q_1 q_2 \cdots q_n) \subseteq (p_i)$ であり (6) より $p_i \in Q$ なので $(q_j) \subseteq (p_i)$ となる $j$ が存在します。(1)より $p_i = \pm q_j$ となります。[証明終わり]

多重集合 $\mathcal{X} = \{| x_1, x_2, \cdots , x_m |\}$ と $\mathcal{Y} = \{| y_1, y_2, \cdots , y_n |\}$ に対して

$\{| x_1, x_2, \cdots , x_m, y_1, y_2, \cdots , y_n |\}$ を $\mathcal{X} + \mathcal{Y}$ と書くことにします。
$\mathcal{X} + \mathcal{Z} = \mathcal{Y}$ となる多重集合 $\mathcal{Z}$ が存在するとき $\mathcal{X} \le \mathcal{Y}$ 、 $\mathcal{Z} = \mathcal{Y} - \mathcal{X}$ と書くことにします。
$m$ を $\# \mathcal{X}$ と書くことにします。
$\displaystyle \prod_{i=1}^m x_i$ を $\displaystyle \prod \mathcal{X}$ と書くことにします。 $\# \mathcal{X} = 0$ のときは $\displaystyle \prod \mathcal{X} = 1$ とします。

$\mathcal{Y} \le \mathcal{X}$ のとき $(\mathcal{X} - \mathcal{Y}) + \mathcal{Y} = \mathcal{X}$ となります。

(8) $\mathcal{P}, \mathcal{Q}$ を0個以上の有限個の正の素数からなる多重集合とするとき、 $\prod \mathcal{P} = \prod \mathcal{Q}$ ならば $\mathcal{P} = \mathcal{Q}$ となります。

[証明] $\# \mathcal{P} = 0$ とすると $\prod \mathcal{P} = 1$ となります。 $\prod \mathcal{P} = \prod \mathcal{Q}$ ならば $\prod \mathcal{Q} = 1$ となって $\# \mathcal{Q} = 0$ となるので $\mathcal{P} = \mathcal{Q}$ となります。

$\# \mathcal{P} \ne 0$ とすると $\{| p |\} \le \mathcal{P}$ となる $p$ が存在します。(7) より $\{| p |\} \le \mathcal{Q}$ となります。 $\mathcal{P}' = \mathcal{P} - \{| p |\}$ 、 $\mathcal{Q}' = \mathcal{Q} - \{| p |\}$ とおくと $\prod \mathcal{P} = \prod \mathcal{Q}$ より $\prod \mathcal{P}' = \prod \mathcal{Q}'$ となります。このとき $\mathcal{P}' = \mathcal{Q}'$ と仮定すると、 $\mathcal{P} = \mathcal{P}' + \{| p |\} = \mathcal{Q}' + \{| p |\} = \mathcal{Q}$ となります。

よって $\mathcal{P} = \{| p_1, p_2, \cdots , p_m |\}$ とすると
$\begin{eqnarray*} & & \left[ \ \prod \mathcal{P} = \prod \mathcal{Q} \implies \mathcal{P} = \mathcal{Q} \ \right] \\ & \Longleftarrow & \left[ \ \prod (\mathcal{P} - \{| p_1 |\}) = \prod (\mathcal{Q} - \{| p_1 |\}) \implies \mathcal{P} - \{| p_1 |\} = \mathcal{Q} - \{| p_1 |\} \ \right] \\ & \Longleftarrow & \left[ \ \prod (\mathcal{P} - \{| p_1, p_2 |\}) = \prod (\mathcal{Q} - \{| p_1, p_2 |\}) \implies \mathcal{P} - \{| p_1, p_2 |\} = \mathcal{Q} - \{| p_1, p_2 |\} \ \right] \\ & \Longleftarrow & \\ & \vdots & \\ & \Longleftarrow & \left[ \ \prod (\mathcal{P} - \mathcal{P}) = \prod (\mathcal{Q} - \mathcal{P}) \implies \mathcal{P} - \mathcal{P} = \mathcal{Q} - \mathcal{P} \ \right] \\ \end{eqnarray*}$
となって、最後の項は $\# \mathcal{P} = 0$ の場合なので成り立ちます。よって $\prod \mathcal{P} = \prod \mathcal{Q}$ ならば $\mathcal{P} = \mathcal{Q}$ となります。[証明終わり]

*1:Wikipediaの多重集合の項を参考にします。多重集合の書き方はいろいろあるようですがここでは $\{| \cdots |\}$ を採用します。 $X$ の生成する自由可換モノイドとの関連についてリンクがありますが、リンク先は自由加群となっていてモノイドの場合については書かれていないようです。アーベル群の場合と同様の議論ができると考えられます。

2021-01-28

エレファントな整数論(17)

整数の素数の積への分解

$R$ を整域、 $\langle R \rangle$ を $R$ の単項イデアル全体の集合とします。 $a \in R$ で生成された単項イデアルを $(a)$ と書きます。 $0$ だけからなるイデアルを $(0)$ と書き、イデアル $(0)$ だけからなる集合を $\langle 0 \rangle$ と書くことにします。

(E2) $(a), (b) \in \langle R \rangle$ 、 $(a) \ne (0)$ 、 $(b) \ne (0)$ ならば $f( (a) ) < f( (a)(b) )$

(ユークリッド関数の条件(2)*1と同様の条件)を満たす $f: \langle R \rangle \setminus \langle 0 \rangle \to \mathbb{N}$ が存在するとします*2。

$R$ の素元全体の集合を $X$ とします。 $X$ によって( $R$ の乗法によって)生成されたモノイドを $P$ とおきます。 $P$ の元で生成された単項イデアル全体の集合を $\langle P \rangle$ とします。

このとき $\langle R \rangle = \langle P \rangle \cup \langle 0 \rangle$ が成り立ちます。

[証明] $\langle R \rangle \setminus (\langle P \rangle \cup \langle 0 \rangle) \ne \varnothing$ と仮定します。 $m = \min \{ f( (a) ) \mid (a) \in \langle R \rangle \setminus (\langle P \rangle \cup \langle 0 \rangle) \}$ とし、 $f( (a) ) = m$ となる $(a) \in \langle R \rangle \setminus (\langle P \rangle \cup \langle 0 \rangle)$ をとります。

$(a) \notin \langle P \rangle \cup \langle 0 \rangle$ なので $(a) = (b)(c)$ 、 $(b) \ne (1)$ 、 $(c) \ne (1)$ となる $(b), (c) \in \langle R \rangle$ が存在します*3。

(E2)より $f( (b) ) < m$ 、 $f( (c) ) < m$ となります。 $(b), (c) \in \langle P \rangle \cup \langle 0 \rangle$ となって、 $(a) \ne (0)$ より $(b) \ne (0)$ 、 $(c) \ne (0)$ なので $(b), (c) \in \langle P \rangle$ となります。よって $(a) = (b)(c) \in \langle P \rangle$ となって矛盾。

よって $\langle R \rangle = \langle P \rangle \cup \langle 0 \rangle$ となります。[証明終わり]

$R$ が整数全体の集合のとき、 $f( (a) )$ を $a$ の絶対値とすると、(E2)を満たします。よって $\langle R \rangle = \langle P \rangle \cup \langle 0 \rangle$ となります。すなわち任意の整数 $a$ は $a = p_1 p_2 \cdots p_n$ という素数の積で表すことができます。

整数全体の集合はユークリッド整域であることから単項イデアル整域となるので、単項イデアル整域の議論からも上記の結論が成り立ちます*4。

*1:「エレファントな整数論(9) - エレファント・コンピューティング調査報告」を参照

*2:Wikipediaによると条件(1)を満たす関数が存在すれば条件(1)と(2)を満たす関数が存在します

*3:「エレファントな整数論(15) - エレファント・コンピューティング調査報告」を参照

*4:「エレファントな整数論(13) - エレファント・コンピューティング調査報告」を参照

2021-01-28

エレファントな整数論(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)]$ が

任意の $n \in \mathbb{N}$ に対して $X * n \subseteq M$ ならば $X * (n+1) \subseteq M$

であるならば $M = \mathbb{N}[(X)]$ となります。

2021-01-27

エレファントな整数論(15)

整域の元の素元への分解の一意性

(1) 整域 $R$ の素元 $p$ に対して、 $(p) = (a_1 a_2 \cdots a_n)$ ならば、 $(p) = (a_i)$ となる $a_i$ が存在します。

[証明]
$\begin{eqnarray*} p \ は素元 & \iff & \bigl[ \ (a)(b) \subseteq (p) \implies (a) \subseteq (p) \ または \ (b) \subseteq (p) \ \bigr] \\ & \implies & \bigl[ \ (a)(b) = (p) \implies (a) \subseteq (a)(b) \ または \ (b) \subseteq (a)(b) \ \bigr] \\ & \iff & \bigl[ \ (a)(b) = (p) \implies (b) = (1) \ または \ (a) = (1) \ \bigr] \\ \end{eqnarray*}$
となるので、これを繰り返すとある $a_i$ が存在して $a_i$ 以外のすべての $a_j$ に対して $(a_j) = (1)$ となるので主張が成り立ちます。[証明終わり]

(2) 整域 $R$ の素元 $p$ に対して、 $(p) \subseteq (a)$ ならば、 $(p) = (a)$ または $(a) = (1)$

[証明] $p = ab$ と書けるので、 $(a) \ne (1)$ とすると(1)より $(p) = (a)$ となります。[証明終わり]

(3) $m, n \ge 1$ とし、 $p_1, p_2, \cdots , p_m, q_1, q_2, \cdots , q_n$ を整域 $R$ の素元とします。 $(p_1 p_2 \cdots p_m) = (q_1 q_2 \cdots q_n)$ ならば任意の $i$ に対して $j$ が存在して $(p_i) = (q_j)$ となります。

[証明] $(q_1 q_2 \cdots q_n) \subseteq (p_i)$ であり $(p_i)$ は素イデアルなので $(q_j) \subseteq (p_i)$ となる $j$ が存在します。(2)より $(p_i) = (q_j)$ となります。[証明終わり]

(4) $m, n \ge 1$ とし、 $p_1, p_2, \cdots , p_m, q_1, q_2, \cdots , q_n$ を整域 $R$ の素元とします。 $(p_1 p_2 \cdots p_m) = (q_1 q_2 \cdots q_n)$ ならば、任意の $i$ に対して $p_1, p_2, \cdots , p_m$ の中から $p_i$ を除いた $p'_1, p'_2, \cdots , p'_{m-1}$ と $q_1, q_2, \cdots , q_n$ の中の $q'_1, q'_2, \cdots , q'_{n-1}$ が存在して $(p'_1 p'_2 \cdots p'_{m-1}) = (q'_1 q'_2 \cdots q'_{n-1})$ となります。

[証明] (3)より任意の $i$ に対して $j$ が存在して $(p_i) = (q_j)$ となります。 $q_1, q_2, \cdots , q_n$ から $q_j$ を除いたものを $q'_1, q'_2, \cdots , q'_{n-1}$ とします。 $(p_i)(p'_1 p'_2 \cdots p'_{m-1}) = (q_j)(q'_1 q'_2 \cdots q'_{n-1})$ となり、 $R$ は整域なので $(p'_1 p'_2 \cdots p'_{m-1}) = (q'_1 q'_2 \cdots q'_{n-1})$ となります。[証明終わり]

(5) $m, n \ge 1$ とし、 $p_1, p_2, \cdots , p_m, q_1, q_2, \cdots , q_n$ を整域 $R$ の素元とします。 $(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_1, p_2, \cdots , p_m, q_1, q_2, \cdots , q_n$ は $R$ の素元で、 $(p_1 p_2 \cdots p_m) = (q_1 q_2 \cdots q_n)$ とします。

$m = 1$ のときは $(p_1) = (q_1 q_2 \cdots q_n)$ となります。(1) より $(p_1) = (q_i)$ となる $i$ が存在して、その他の $q_j$ はすべて $(q_j) = (1)$ となりますが、 $q_j$ は素元なので $(q_j) = (1)$ となることはありません。よって $n = 1$ であり $(p_1) = (q_1)$ となります。

$m \gt 1$ として、 $m$ より小さい場合は主張が成り立っているとします。(3) より $(q_i) = (p_1)$ となる $i$ が存在します。番号を付け替えてこの $q_i$ を $q_1$ とします。

(4)より $(p_2 \cdots p_m) = (q_2 \cdots q_n)$ となります。帰納法の仮定より $m = n$ であり、適当に並べ替えると任意の $2 \le i \le m$ に対して $(p_i) = (q_i)$ となります。したがって主張が成り立ちます。[証明終わり]

整域 $R$ の単項イデアル全体の集合はイデアルの乗法に関して可換モノイドとなります。

2021-01-24

エレファントな整数論(14)

「半環上のフラクタル代数(5) - エレファント・コンピューティング調査報告」で環上のモノイド代数について説明しましたが、追加も含めて再び書いておきます。

環上のモノイド代数(の半環版)

$R$ を単位元を持つ可換半環、 $M$ をモノイドとします。
$R[M] = \{ f \mid f : M \to R, \ \{ x \in M \mid f(x) \ne 0 \} は有限集合 \}$
とおきます。 $R[M]$ に加法、乗法と呼ばれる二項演算

$+: R[M] \times R[M] \to R[M]$
$\cdot: R[M] \times R[M] \to R[M]$ ( $f \cdot g$ を $fg$ と書くこともあります)

を

$(f + g) (x) = f(x) + g(x)$
$\displaystyle (fg) (x) = \sum_{x=yz, f(y) \ne 0, g(z) \ne 0} f(y) g(z)$

と定義すると、 $R[M]$ は単位元を持つ可換半環となります。*1

環上の自由加群(の半環版)

単位元を持つ可換半環 $R$ と集合 $X$ に対して
$R[(X)] = \{ f \mid f : X \to R, \ \{ x \in X \mid f(x) \ne 0 \} は有限集合 \}$
と書くことにします。
とおきます。 $R[(X)]$ の加法

$+: R[(X)] \times R[(X)] \to R[(X)]$

とスカラー乗法

$\cdot: R \times R[(X)] \to R[(X)]$ ( $a \cdot f$ を $af$ と書くこともあります)

を

$(f + g) (x) = f(x) + g(x)$
$(af) (x) = af(x)$

と定義します。 $R[(X)]$ は加法に関して可換モノイドとなります。*2

環上の自由加群の元の分解(の半環版)

$\varphi: X \to R[(X)]$ を $x, y \in X$ に対して
$\varphi(x)(y) = \begin{cases} 1 & (x = y \ のとき) \\ 0 & (x \ne y \ のとき) \end{cases}$
とします。

$x = y$ ならば

任意の $z$ に対して「 $x = z \iff y = z$ 」

が成り立ちます。逆に

任意の $z$ に対して「 $x = z \iff y = z$ 」

ならば

$x = y \iff y = y$

となるので $x = y$ となります。よって $x = y$ であることと

任意の $z$ に対して「 $x = z \iff y = z$ 」

であることは同値となります。

$\begin{eqnarray*} \varphi(x) = \varphi(y) & \iff & 任意の \ z \ に対して「 \varphi(x)(z) = \varphi(y)(z) 」\\ & \iff & 任意の \ z \ に対して「 \varphi(x)(z) = 1 \iff \varphi(y)(z) = 1 」\\ & \iff & 任意の \ z \ に対して「 x = z \iff y = z 」\\ & \iff & x = y \\ \end{eqnarray*}$
となって $\varphi$ は単射となります。

$f \in R[(X)]$ に対して $X_f = \{ x \in X \mid f(x) \ne 0 \}$ とおくと $X_f$ は有限集合となります。 $X_f = \{x_1, x_2, \cdots , x_n\}$ とおきます。 $g = f(x_1) \varphi(x_1) + f(x_2) \varphi(x_2) + \cdots + f(x_n) \varphi(x_n)$ とおくと

$x_i \in X_f$ のとき $g(x_i) = f(x_i) \varphi(x_i)(x_i) = f(x_i)$
$y \notin X_f$ のとき $g(y) = 0$

となって $g = f$ となります、よって
$f = f(x_1) \varphi(x_1) + f(x_2) \varphi(x_2) + \cdots + f(x_n) \varphi(x_n)$
となります。

$M$ を可換モノイド、 $\psi: X \to M$ とします。 $\bar{\psi}: \mathbb{N}[(X)] \to \mathbb{N}[M]$ を $\bar{\psi}(f) = f(x_1) \psi(x_1) + f(x_1) \psi(x_1) + \cdots + f(x_n) \psi(x_n)$ と定義すると $\bar{\psi}$ は可換モノイドの準同型となります。

環上の自由加群の帰納的定義(の半環版)

$\varphi: X \to \mathbb{N}[(X)]$ を $x, y \in X$ に対して
$\varphi(x)(y) = \begin{cases} 1 & (x = y \ のとき) \\ 0 & (x \ne y \ のとき) \end{cases}$
とします。 $\varphi(X) \cup \{0\} \subseteq M \subseteq \mathbb{N}[(X)]$ とし、

任意の $f, g \in M$ に対して $f + g \in M$

とします。 $x \in X$ に対して $\{ n \in \mathbb{N} \mid n \varphi(x) \notin M \} \ne \varnothing$ とすると $m = \min\{ n \in \mathbb{N} \mid n \varphi(x) \notin M \}$ が存在します。 $0 \in M$ より $m > 0$ となり、 $(m - 1) \varphi(x) \in M$ 、 $m \varphi(x) \notin M$ となりますが、 $\varphi(x) \notin M$ となって矛盾となります。よって $\{ n \varphi(x) \mid n \in \mathbb{N} \} \subseteq M$ となります。

よって $M = \mathbb{N}[(X)]$ となります。

自由生成可換モノイドの普遍性

$\varphi: M \to \mathbb{N}[M]$ を $x, y \in M$ に対して
$\varphi(x)(y) = \begin{cases} 1 & (x = y \ のとき) \\ 0 & (x \ne y \ のとき) \end{cases}$
とします。 $x \in M$ に対して $\{ n \in \mathbb{N} \mid n \varphi(x) \notin \varphi(M) \} \ne \varnothing$ とすると $m = \min\{ n \in \mathbb{N} \mid n \varphi(x) \notin \varphi(M) \}$ が存在します。 $0 \in \varphi(M)$ より $m > 0$ となり、 $(m - 1) \varphi(x) \in \varphi(M)$ 、 $m \varphi(x) \notin \varphi(M)$ となりますが、 $\varphi(x) \notin \varphi(M)$ となって矛盾となります。よって $\{ n \varphi(x) \mid n \in \mathbb{N} \} \subseteq \varphi(M)$ となります。

よって $\varphi(M) = \mathbb{N}[M]$ となります。

$M$ を可換モノイド、 $\psi: X \to M$ とします。 $\bar{\psi}: \mathbb{N}[(X)] \to M$ を $\bar{\psi}(f) = f(x_1) \psi(x_1) + f(x_1) \psi(x_1) + \cdots + f(x_n) \psi(x_n)$ と定義すると $\bar{\psi}$ は可換モノイドの準同型となります。

$R$ が環で $M$ が $X = \{x_1, x_2, \cdots, x_n\}$ で自由生成された可換モノイドのとき、 $R[M]$ は $R$ 上の多項式環 $R[x_1, x_2, \cdots, x_n]$ となります。 $R[x_1, x_2, \cdots, x_n] = R[\mathbb{N}^n] = R[\mathbb{N}[(X)]]$ となります。

*1: $R$ が環のとき $R[M]$ は $R$ 上の代数となります。 $R[M]$ を $R$ 上のモノイド代数と呼びます。

*2: $R$ が環のとき $R[(X)]$ は $X$ で自由生成された $R$ 上の加群となります。

2021-01-16

エレファントな整数論(13)

整域 $R$ の素元全体の集合を $X$ 、既約元全体の集合を $Y$ とします。 $X$ によって( $R$ の乗法によって)生成されたモノイドを $P$ とおきます。 $R$ のイデアル全体の集合を $I(R)$ とおきます。 $\psi: R \to I(R)$ を $\psi(a) = Ra$ とします。 $\{0\}$ を $0$ と書きます。 $S \subseteq R$ に対して $\psi(S)$ を $\langle S \rangle$ と書きます。

$\langle R \rangle = \langle P \rangle \cup \langle 0 \rangle$ のとき $R$ を一意分解整域と呼びます。

$I(R) = \langle R \rangle$ のとき $R$ を単項イデアル整域と呼びます。

$X \subseteq Y$

[証明]
$\begin{eqnarray*} p \in X & \iff & \bigl[ \ (a)(b) \subseteq (p) \implies (a) \subseteq (p) \lor (b) \subseteq (p) \ \bigr] \\ & \implies & \bigl[ \ ab = p \implies a \in (ab) \lor b \in (ab) \ \bigr] \\ & \iff & \bigl[ \ ab = p \implies (b) = (1) \lor (a) = (1) \ \bigr] \\ & \iff & p \in Y \end{eqnarray*}$
[証明終わり]

$\langle R \rangle = \langle P \rangle \cup \langle 0 \rangle \implies \langle X \rangle = \langle Y \rangle$

[証明] $(p) \in \langle Y \rangle$ とすると $(p) \in \langle R \rangle = \langle P \rangle \cup \langle 0 \rangle$ であり $(p) \ne 0$ なので $(p) \in \langle P \rangle$ となります。よって $(p) = (q_1) \cdots (q_n)$ となる $(q_i) \in \langle X \rangle$ が存在します。 $(p) \in \langle Y \rangle$ よりある $(q_i)$ 以外は $(1)$ となります。よって $(p) = (q_i) \in \langle X \rangle$ となって $\langle Y \rangle \subseteq \langle X \rangle$ となります。

$X \subseteq Y$ より $\langle X \rangle \subseteq \langle Y \rangle$ となるので $\langle X \rangle = \langle Y \rangle$ となります。[証明終わり]

$I(R) = \langle R \rangle \implies \langle R \rangle = \langle P \rangle \cup \langle 0 \rangle$

[証明] $I = \bigcup (\langle R \rangle \setminus \langle P \rangle) = \bigcup \{ (x) \mid (x) \in \langle R \rangle \setminus \langle P \rangle \}$ とおくと( $\bigcup$ は $R$ の部分集合の和集合を表す) $I \in I(R) = \langle R \rangle$ となります。

$I = (a) \in \langle R \rangle$ となる $(a) \in \langle R \rangle$ が存在します。 $a \in (x)$ となる $(x) \in \langle R \rangle \setminus \langle P \rangle$ が存在します。

$(a) \ne 0$ ならば $(a) = (b)(c)$ 、 $(b) \ne (1)$ 、 $(c) \ne (1)$ となる $(b), (c) \in \langle R \rangle$ が存在します。 $(b) \notin \langle P \rangle$ とすると、 $(b) \subseteq (a)$ となります。 $(a) = (b)(c) \subseteq (b)$ より $(a) = (b)$ となります。 $(a) = (b)(c)$ より $(c) = (1)$ となり $(c) \ne (1)$ に矛盾。よって $(b) \in \langle P \rangle$ となります。同様に $(c) \in \langle P \rangle$ となります。 $(a) = (b)(c) \in \langle P \rangle$ となって $(a) \notin \langle P \rangle$ に矛盾。よって $(a) = 0$ となります。

よって $\langle R \rangle = \langle P \rangle \cup \langle 0 \rangle$ となります。[証明終わり]

2021-01-13

エレファントな整数論(12)

エラトステネスのふるい(2)

整数の場合

次に「エラトステネスのふるい」の整数の場合を考えます。

$\mathbb{Z}$ を整数全体の集合とし、以下 $R = \mathbb{Z}$ とします。 $\mathbb{N}$ を自然数全体の集合とし、 $f: \mathbb{Z} \to \mathbb{N}$ を $a \in \mathbb{Z}$ を $a$ の絶対値に写す写像とします。

$a \in R$ は $ab = 1$ となる $b \in R$ が存在するとき $R$ の単元と呼びます。 $R$ の単元全体の集合を $R^\times$ と書きます。 $\mathbb{Z}^\times = \{1, -1\}$ となります。

$S = R \setminus ( R^\times \cup \{0\} )$ とおきます。 $a \in R$ は以下の条件を満たすとき $R$ の既約元と呼びます。 $R = \mathbb{Z}$ のときは素数と呼びます。

(1) $a \in S$
(2) 任意の $b, c \in R$ に対して $a = bc$ ならば $b \in R^\times$ または $c \in R^\times$

$R$ の部分集合 $X$ 、 $Y$ に対して $\{ xy \mid x \in X, y \in Y \}$ を $XY$ と書くことにします。 $XX$ を $X^2$ と書くことにします。

$b \notin R^\times$ 、 $c \notin R^\times$ とすると $bc \in (S \cup \{0\})(S \cup \{0\}) = S^2 \cup \{0\}$ となります。よって条件(2)は $a \in R \setminus (S^2 \cup \{0\})$ と同値となります。よって $a$ が既約元(素数)であることは $a \in S \setminus S^2$ と同値となるので、 $R$ の既約元(素数)全体を $P$ とすると $P = S \setminus S^2$ となります。

(S1) $X$ を $S$ の有限部分集合とすると $S \setminus X R \ne \varnothing$ となります。

[証明] $X = \{a_1, a_2, \cdots, a_n\}$ とします。 $R = \mathbb{Z}$ なので $S \ne 0$ となります。 $n = 0$ のときは $S \ne 0$ なので成り立っています。以下 $n >0$ とします。

任意の $a_i$ に対して $a_1 a_2 \cdots a_n \in a_i R$ が成り立ちます。 $b = f(a_1 a_2 \cdots a_n) + 1$ とおきます( $f$ は絶対値)。 $b \in a_i R$ とすると $1 \in a_i R$ となって $a_i$ は単元ではないので矛盾となります。よって任意の $a_i$ に対して $b \notin a_i R$ となるので $b \notin X R$ となります。

$R = \mathbb{Z}$ なので $f(a_1 a_2 \cdots a_n) \ge 2$ となって $b \ge 3$ となるので $b$ は $0$ でも単元でもありません。

よって $b \in S \setminus X R$ となり、 $S \setminus X R \ne \varnothing$ が成り立ちます。[証明終わり]

(S1)より $S$ の部分集合の列 $P_0, P_1, P_2, \cdots$ を

$P_0 = \varnothing$
$P_{n+1} = P_n \cup f^{-1}(\min f(S \setminus P_n R))$

と帰納的に定義することができます。

$m_{n} = \min f(S \setminus P_n R)$ とおきます。

$P_n \subseteq P_{n+1}$ より $P_n R \subseteq P_{n+1} R$ 、 $S \setminus P_n R \supseteq S \setminus P_{n+1} R$ 、 $f(S \setminus P_n R) \supseteq f(S \setminus P_{n+1} R)$ 、 $\min f(S \setminus P_n R) \le \min f(S \setminus P_{n+1}) R$ 、 $m_{n+1} \le m_{n+2}$ となります。

$m_{n+1} = m_{n+2}$ とすると $m_{n+1} = m_{n+2} \in f(S \setminus P_{n+1} R)$ なので $m_{n+1} = f(a)$ 、 $a \in S \setminus P_{n+1} R$ となる $a$ が存在します。 $m_{n+1} = f(a)$ より $a \in f^{-1}(m_{n+1}) \subseteq P_{n+1}$ となりますが、 $a \in S \setminus P_{n+1} R$ より $a \notin P_{n+1} R \supseteq P_{n+1} \{1\} = P_{n+1}$ となるので、このようは $a$ は存在しません。

よって $m_0 < m_1 < m_2 < \cdots$ となります。

(S2) $f^{-1}( \min f(S \setminus P_n R) ) \subseteq P$

[証明] $a \in f^{-1}( \min f(S \setminus P_n R) )$ とすると $f(a) = \min f(S \setminus P_n R)$ となります。

もし $f(a) = bc$ 、 $b,c \in S$ 、 $b, c > 0$ とすると $R = \mathbb{Z}$ なので $b, c < f(a)$ となります。 $f(a)$ の最小性から $b \notin S \setminus P_n R$ 、 $b \in P_n R$ 、 $f(a) = bc \in P_n R$ となって矛盾となります。よって $f(a) \in P$ となります。

$f$ は絶対値をとる写像なので $f^{-1}( \min f(S \setminus P_n R) ) = \{ a , -a \} \subseteq P$ となります。[証明終わり]

(S2)より $P_{n+1} = f^{-1}(m_0) \cup f^{-1}(m_1) \cup \cdots \cup f^{-1}(m_n) \subseteq P$ となって $P^* = P_1 \cup P_2 \cup P_3 \cup \cdots$ とおくと $P^* \subseteq P$ が成り立ちます。

(S3) $a \in S, \ b \in R, \ f(a) \le f(b) \implies b \in S$

[証明] $R = \mathbb{Z}$ のときは $a \in S \iff f(a) \ge 2$ となるので成り立ちます。[証明終わり]

(S4) $a \in R, \ m_n < f(a) \implies a \notin P_{n+1}$

[証明] $R = \mathbb{Z}$ のときは $\max f(P_{n+1}) = m_n$ で $f$ は絶対値をとる写像なので成り立ちます。[証明終わり]

$a \in R$ 、 $m_n < f(a) < m_{n+1}$ とすると $f(a) \notin f(S \setminus P_{n+1} R)$ となります。 $a \notin S \setminus P_{n+1} R$ となり (S3)より $a \in S$ となるので $a \in P_{n+1} R \subseteq P_{n+1} \cup P_{n+1} S \subseteq P_{n+1} \cup S^2$ となります。(S4)より $a \notin P_{n+1}$ となるので $a \in S^2$ 、 $a \notin P$ となります。よって $f(P) \subseteq \{m_0, m_1, m_2, \cdots \}$ となって $P \subseteq f^{-1}(\{m_0, m_1, m_2, \cdots \}) =P^*$ となります。

よって $P = P^* = P_1 \cup P_2 \cup P_3 \cup \cdots$ となります。

自然数の有限集合の場合

$k \in \mathbb{N}$ に対して $S_k = S \cap \{ 2, 3, 4, \cdots, k \}$ とおきます。
$\begin{eqnarray*} P_1 \cap S_k & = & \{ 2 \}, \\ P_2 \cap S_k & = & \{ 2, 3 \}, \\ P_3 \cap S_k & = & \{ 2, 3, 5 \}, \\ & \vdots & \\ P_n \cap S_k & = & \{ 2, 3, 5, \cdots, m_{n-1} \} \\ \end{eqnarray*}$
となって、ある $n$ で $m_{n-1} \ge k$ となるので $P \cap S_k \subseteq P_n$ となって $S_k$ に含まれる素数をすべて見つけることができます。このように、有限個の自然数から最小値をとってその倍数をとることを繰り返す方法を「エラトステネスのふるい」と呼びます。

この方法は式で書きにくいので、最小値をとるかわりに自然数の小さいものから順に調べていく方法で書き直すと
$\begin{eqnarray*} P & = & P \cap \left( \bigcup_{k \in \mathbb{N}} \{k+1\} \right) \\ & = & \bigcup_{k \in \mathbb{N}} (P \cap \{k+1\}) \\ & = & \bigcup_{k \in \mathbb{N}} ( (S \setminus S^2) \cap \{k+1\}) \\ & = & \bigcup_{k \in \mathbb{N}} ( (S \setminus (P \cap S_{k})S ) \cap \{k+1\}) \\ \end{eqnarray*}$
のようになります。

無限の列を扱うことができるプログラミング言語で書くと、無限の場合も書くことができます。

整数の素因数分解

(2) ならば は素数の積で表すことができます。

整数の素因数分解の多重集合としての一意性

(4)

(5)

(6)

(7) とし、 を正の素数とします。 ならば任意の に対して が存在して となります。

(8) を0個以上の有限個の正の素数からなる多重集合とするとき、 ならば となります。