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

素因数分解の一般化

$S$ で生成された自由モノイド $S^*$ の有限部分集合全体を $S^{**}$ とおきます。モノイドの演算子を $*$ 、和集合の演算子を $+$ とすると、 $S^{**}$ は $*$ を積、 $+$ を和とする半環となります。積の単位元を $1$ 、和の単位元を $0$ と書きます。

$S^{**}$ の元 $r$ は
$r = s_{1,1} * \cdots * s_{1,n_1} + \cdots + s_{m,1} * \cdots * s_{m,n_m} \ (s_{i,j} \in S)$
と表すことができます(この $s_{i,j}$ を $r[i,j]$ と書くことにします)。 $f: S \to S^{**}$ を
$f^{**}(r) = f(s_{1,1}) * \cdots * f(s_{1,n_1}) + \cdots + f(s_{m,1}) * \cdots * f(s_{m,n_m})$
と定義することにより $f^{**}: S^{**} \to S^{**}$ に拡張することができます。

素因数分解の部分写像

$S = I + R$ 、 $d: R \to S$ とします。 $s \in S$ を「素因数分解」する「形式的写像」 $f(s)$ を

(1) $s \in I$ のとき $s$
(2) $s \in R$ のとき $f^{**}(d(s))$

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

(k1) $s \in I$ のとき $s$
(k2) $s \in R$ のとき $f_{k+1}^{**}(d(s))$

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

$s \in S$ に対して $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(s) = f'(s)$ であるとします。

この $f$ を $\rho_d$ とおきます。

順序

$S$ は順序 $\le$ を持つとします。

$s \in S$ 、 $r \in S^{**}$ に対して、任意の $i,j$ に対して $r[i,j] < s$ であるとき $r < s$ とします。
任意の $s \in R$ に対して $d(s) < s$ であるとします。(*)

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

このとき $\rho_d$ は $S$ から $S^{**}$ への写像となります。

項の素因数分解

$C = C_0 + C_1 + C_2 + \cdots$
$M = C^*$ (演算子は $\cdot$ または省略します)
$I = C$
$R = C \cdot M = \{c \cdot s \mid c \in C, \ s \in M\}$
とおきます。

$d: R \to M^{**}$ を
$\displaystyle d(s) = \sum_{n \in \mathbb{N}} \sum_{c \in C_n} \sum_{s = c s_1 \cdots s_n} c * s_1 * \cdots * s_n$
とおきます。ここで $\mathbb{N} = \{0, 1, 2, \cdots \}$ 、 $\displaystyle \sum_{s = c s_1 \cdots s_n}$ は $s = c s_1 \cdots s_n$ で、各 $s_i$ は単位元ではない $s_1, \cdots, s_n$ のすべての組についての和を表します。