モノイドの素因数分解(1) - 非専門的シンギュラリティー研究所

モノイドの素因数分解

背景と目的

「単一化アルゴリズム(3) - エレファント・ビジュアライザー調査記録」では項を分解する部分写像について調べました。これはモノイドを生成するようなイテレーター的部分写像とみなすことができますが、このようなものについて調べていきます。

まずその例として、整数の素因数分解について考えます。これはこのブログでも何度か扱っています。ここでは一般化したものを扱います。

モノイドの既約元

モノイドに一般化したいのですが、既約元を定義したいので何かの制約が必要となります。ここでは以下のようにします。

$M$ をモノイドとします。演算子は $\cdot$ と書くか、または省略します。単位元は $1$ と書きます。

$M$ は単位元以外の左可逆元、右可逆元を持たないとします。すなわち
$xy = 1$ ならば $x = y = 1$
であるとします。

単位元以外の二つの元の積を可約元とします。可約元の全体を $R(M)$ とおきます。すなわち
$R(M) = \{xy \mid x \ne 1, \ y \ne 1, \ x \in M, \ y \in M\}$
とおきます。

単位元以外の二つの元の積として表すことができない元を既約元とします。既約元の全体を $I(M)$ とおきます。すなわち
$I(M) = \{a \in M \mid a = xy \ ならば \ x = 1 \ または \ y = 1 \ (\forall x, y \in M)\}$
とおきます。

$M = R(M) + I(M) + \{1\}$ (集合の直和)となります。

自由モノイド

集合 $S$ に対して $S^k$ を $k$ 個の $S$ の直積、 $+$ を集合の直和とすると $S^* = 1 + S + S^2 + S^3 + \cdots$ は $S$ で生成された(「文字列の連結」を演算とする)自由モノイドとなります( $1$ は「空文字列」)。

素因数分解の部分写像

$R(M)$ の元 $a$ に対して $a = xy, \ x \ne 1, \ y \ne 1$ を満たす $x, y \in M$ の組の一つをとり、 $r_1(a) = x, \ r_2(a) = y$ として $r_1, r_2: R(M) \to M \setminus \{1\}$ を定義することができます。

$M^*$ を $M$ で生成された自由モノイドとします。演算子は $*$ と書きます。単位元は $1$ と書きます。

$a \in R(M) + I(M)$ に対して素因数分解する「形式的写像」 $f(a)$ を

(1) $a \in I(M)$ のとき $a$
(2) $a \in R(M)$ のとき $f(r_1(a)) * f(r_2(a))$

と定義します。これは $f_k(a)$ を

(k1) $a \in I(M)$ のとき $a$
(k2) $a \in R(M)$ のとき $f_{k+1}(r_1(a)) * f_{k+1}(r_2(a))$

と定義し、 $f=f_0, f_1, f_2, \cdots$ を合成したものを表すとします。

$a \in M$ に対して $f_k$ が(k2)にならない $k$ が存在すれば $f_k$ を $f'_k = 1$ (恒等写像)で置き換え、各 $f_i$ は $f'_{i+1}$ を呼び出すように置き換えた $f'=f'_0, f'_1, f'_2, \cdots, f'_{k-1}, f'_k$ を合成した「部分写像」を $f'$ としたとき $f(a) = f'(a)$ であるとします。

順序

$M \setminus \{1\}$ は順序 $\le$ を持つとします。

$x \ge y \iff y \le x$
$x < y \iff x \le y \ かつ \ x \ne y$
$x > y \iff x \ge y \ かつ \ x \ne y$

とします。

任意の $a \in R(M)$ に対して $r_1(a) < a$ 、 $r_2(a) < a$ であるとします。

$R(M)$ が順序 $\le$ に関して降鎖条件を満たすならば、すなわち任意の $R(M)$ の元の列
$a_{1} \geq a_{2} \geq a_{3} \geq \cdots$
に対して、ある自然数 $n$ が存在して、
$a_{n} = a_{n+1} = a_{n+2} = \cdots$
が成り立つならば、 $f$ は $R(M) + I(M)$ から $M^*$ への写像となります。