【未解決問題の解決】テトリス代数とupho半順序集合

(反射律) $x = x * e$より$x \leq x$
(推移律) $x \leq y,\ y \leq z$のとき，ある$a,b \in M$が存在して$x * a = y,\ y * b = z$である．
よって，$x * (a * b) = (x * a) * b = y * b = z$なので，$x \leq z$
(反対称律) $x \leq y,\ y \leq x$のとき，ある$a,b\in M$が存在して$x * a = y,\ y * b = x$なので，
$x * (a * b) = (x * a) * b = y * b = x = x * e$であり，左簡約性より$a * b = e$である．
また，可逆元が単位元のみであることから$a = b = e$であり，$x = y$が従う．
(upho性)
$$ \{x \in M \mid x \geq a\} = \{ a * y \mid y \in M \} $$
であり，左$a$倍写像が順序同型
$$ M \to \{x \in M \mid x \geq a\},\quad y \mapsto a * y $$
を与える．

任意の$(u,m) \in \mathcal{P}$に対し，$\sigma(v_0) = u$なるグラフの自己同型$\sigma \in \mathrm{Aut}(\Gamma)$をとれば，
$$ \mathcal{P} \to \{(v',n') \in \mathcal{P} \mid (v',n') \geq (u,m) \},\quad (v,n) \mapsto (\sigma(v), n + m) $$
は順序同型になる．

$\Gamma$はCayleyグラフなので，自己同型群の部分群$H$が存在して，任意の頂点は$\sigma \in H$を用いて$\sigma (v_0)$と一意的に表せる．そこで，$\mathcal{P}$の演算$*$を
$$ (\sigma (v_0),m) * (\tau (v_0),n) := (\sigma \tau (v_0), m+n) $$
によって定めると，これは$\mathcal{P}$の順序を誘導するLCIFモノイドとなる．

$\mathcal{P}$の積付け$*$が存在すると仮定する．$a = (u,n) \in \mathcal{P}$を固定する．左$a$倍写像は，写像$\phi_{a,m} : V_m \to V$を用いて
$$ a * (v,m) = (\phi_{a,m}(v), n+m) $$
と書ける．この証明の肝は，$\phi_{a,m}$が$m$によらないということである．

一旦この主張を認める．このとき，
$$ a * (v,m) = (\phi_a(v), m+n) $$
である．$*$ の結合性から$\phi_{a * b} = \phi_a \circ \phi_b$であり，$\phi_{(v_0,0)} = \mathrm{id}$なので，
$$ (\mathcal{P}, *) \to (\mathrm{Aut}(\Gamma), \circ),\quad a \mapsto \phi_a $$
はモノイドの準同型となる．さて，$\mathcal{P}_n := V_n \times \{n\} \subset \mathcal{P}$とすると，$m,n \geq N_0$に対しては，
$$ \mathcal{P}_m * \mathcal{P}_n = \mathcal{P}_{m+n} $$
である．よって，$H_n := \{ \phi_a \mid a \in \mathcal{P}_n \}$とすると，
$$ H_m H_n = H_{m+n} $$
である．よって$\{H_n \mid n \geq N_0\}$は半群となる．空でない有限半群は冪等元をもつので，ある$N$が存在し，
$$ H_N H_N = H_N $$
である．よって$H_N$は有限群$\mathrm{Aut}(\Gamma)$の部分半群だから部分群である．また，$a = (v,N) \in \mathcal{P}_N$に対し，$a * (v_0,0) = (v,N)$
であるので，$\phi_a(v_0) = v$であり，$H_N$は$V$に正則に作用することが分かる．これは$\Gamma$がCayleyグラフであることを意味するが，$\Gamma$は非Cayleyグラフなので矛盾．

$\Gamma$の隣接行列を$A$とし，$\phi,\psi$に対応する置換行列を$P,Q$とすれば，
$$ PA = AQ, \quad QA = AP $$
である．よって，$B := P-Q$とすると，
$$ AB = -BA $$
である．したがって，$A$の固有値$\lambda$の固有ベクトル$x$に対して，
$$ ABx = -BAx = -\lambda Bx $$
なので，$Bx$は$-\lambda$の固有空間に属す．一方，Petersenグラフの隣接行列$A$の固有値は$3, 1^5, (-2)^4$であり，$\lambda$と$-\lambda$が同時に固有値になることはない．$A$は実対称行列であり対角化可能であるため，すべての固有空間に対してこの考察をすることで$B = O$が得られる．

左$a$倍写像は全単射なので，
$$ \phi_{a,m}(v) = \phi_{a,m}(w) \iff a*(v,m) = a*(w,m) \iff (v,m) = (w,m) $$
であり，$\phi_{a,m}$は単射である．特に$m \geq N_0$のとき，$\phi_{a,m}$は全単射である．
任意の$(v,m) \in \mathcal{P}$と$w \in V$に対して,
\begin{align} v \sim w &\iff (v,m) \leq (w,m+1) \\ &\iff a * (v,m) \leq a * (w,m+1) \\ &\iff (\phi_{a,m}(v), n + m) \leq (\phi_{a,m+1}(w), n + m + 1) \\ &\iff \phi_{a,m}(v) \sim \phi_{a,m+1}(w) \end{align}
である．特に，$m \geq N_0$のとき，
$$ \forall v,w \in V, \quad v \sim w \iff \phi_{a,m}(v) \sim \phi_{a,m+1}(w) $$
であるから，補題7より
$$ \phi_{a,N_0} = \phi_{a,N_0+1} = \cdots $$
である．これを$\phi_a$と書く．このとき，任意の$v,w \in V$に対して，
$$ v \sim w \iff \phi_a(v) \sim \phi_a(w) $$
なので，$\phi_a \in \mathrm{Aut}(\Gamma)$である．次に，各$0 \leq m < N_0$に対して$\phi_{a,m}$が$\phi_a$の制限になっていることを，$m$についての減少する帰納法で示す．$\phi_{a,m+1} = \phi_a|_{V_{m+1}}$と仮定する．任意の$v \in V_m$と$w \in N(v) \subset V_{m+1}$に対して，
$$ \phi_{a,m}(v) \sim \phi_{a,m+1}(w) = \phi_a(w) $$
であることから，
$$ N(\phi_a(v)) = \phi_a(N(v)) \subset N(\phi_{a,m}(v)) $$
であり，両辺の元の数が等しく$3$なので，等号$N(\phi_a(v)) = N(\phi_{a,m}(v))$が成り立つ．$\Gamma$はtwin-free($N(v) = N(w) \Longrightarrow v = w$)なので，$\phi_{a,m}(v) = \phi_a(v)$が得られる．