beet's soil

競プロのことなど

畳み込み 可逆性 判定

あけまして おめおめでとう ございます(575)

導入

$\cdot$ を適当な畳み込み演算として、$f = f \cdot g + 1$ のとき、$f = 1 / (1 - g)$ ←これマジ?

定理

各点和、 {and, or, xor} 畳み込み積を演算とする環 $R$ において、 $g \in R$が可逆 ⇔ $ \mathrm{WHT}(g) $ が可逆 ⇔ $\forall_i \mathrm{WHT}(g)_i \neq 0$

補題1

$f$ : 環同型とする(上の $f$ とは別)

$a$ : 零因子 ⇔ $f(a)$ : 零因子

証明: 定義より、$\exists_{x \neq 0} ax = 0$

$f(a) f(x) = f(a x) = f(0), f(x) \neq f(0) $

補題2

WHT は環同型である

証明:「ここに適切な証明が入る」

定理の証明

$\forall_i \mathrm{WHT}(g)_i \neq 0$ のとき、存在性は $h_i = 1 / \mathrm{WHT}(g)_i$ として $\mathrm{iWHT}(h)$ を考えればよい。 $h \cdot g = 1$ は明らか

あとは一意性を言えばOK

$f \cdot g = h \cdot g \Leftrightarrow f = h$ を示せばよい

$f \cdot g = h \cdot g \Leftrightarrow (f - h) \cdot g = 0$

ここで $\mathrm{WHT}(g)$ は可逆であったから、$g$ も可逆である、つまり零因子でない、したがって $f - h = 0$

おまけ

$f = \displaystyle \sum_{i=0}^{\infty} g^{i} \Leftrightarrow f = f \cdot g + 1 $

証明:略

問題例