2025-11-10T02:36:05.255019

On certain semigroups of finite oriented and order-decreasing partial transformations

Ayık, Ayık, Dimitrova et al.
Let $\mathcal{PORD}_{n}$ be the semigroup consisting of all oriented and order-decreasing partial transformations on the finite chain $X_{n}=\{ 1<\cdots<n \}$. Let $\mathcal{IORD}_{n}$ be the subsemigroup of $\mathcal{PORD}_{n}$ consisting of all injective transformations of $\mathcal{PORD}_{n}$. For $2\leq r\leq n$, let $\mathcal{PORD}(n,r) =\{ α\in \mathcal{PORD}_{n} :\lvert \text{im}(α) \rvert \leq r\}$ and $\mathcal{IORD}(n,r)=\{ α\in \mathcal{IORD}_{n} :\lvert \text{im}(α)\rvert \leq r\}$. In this paper, we determine some minimal generating sets and ranks of $\mathcal{PORD}(n,r)$ and $\mathcal{IORD}(n,r)$, and moreover, we characterize the maximal subsemigroups of $\mathcal{PORD}(n,r)$ and $\mathcal{IORD}(n,r)$.
academic

有限有向かつ順序減少部分変換の特定の半群について

基本情報

  • 論文ID: 2510.13484
  • タイトル: On certain semigroups of finite oriented and order-decreasing partial transformations
  • 著者: Gonca Ayık, Hayrullah Ayık, Ilinka Dimitrova, Jörg Koppitz
  • 分類: math.RA（環と代数）
  • 発表日: 2025年10月15日
  • 論文リンク: https://arxiv.org/abs/2510.13484v1

要約

本論文は、有限鎖Xn={1<⋯<n}X_n = \{1 < \cdots < n\}上の有向かつ順序減少部分変換半群PORDn\mathcal{PORD}_nおよびその単射部分半群IORDn\mathcal{IORD}_nを研究する。2≤r≤n2 \leq r \leq nに対して、PORD(n,r)={α∈PORDn:∣im(α)∣≤r}\mathcal{PORD}(n,r) = \{\alpha \in \mathcal{PORD}_n : |\text{im}(\alpha)| \leq r\}およびIORD(n,r)={α∈IORDn:∣im(α)∣≤r}\mathcal{IORD}(n,r) = \{\alpha \in \mathcal{IORD}_n : |\text{im}(\alpha)| \leq r\}を定義する。本論文はPORD(n,r)\mathcal{PORD}(n,r)とIORD(n,r)\mathcal{IORD}(n,r)の最小生成集合と秩を決定し、それらの極大部分半群を特徴付ける。

研究背景と動機

問題背景

変換半群理論は代数学の重要な分野であり、集合上の変換の代数構造を研究する。本論文が焦点を当てる中心的な問題は以下の通りである：

  1. 有向変換：部分変換α\alphaが有向であるとは、それが順序保存的または順序反転的である場合
  2. 順序減少：定義域内の各要素xxに対してxα≤xx\alpha \leq xが成立
  3. 半群の生成集合と秩：半群の最小生成集合およびその大きさ（秩）を決定
  4. 極大部分半群：半群内のすべての極大部分半群の構造を特徴付け

研究の重要性

  1. 理論的価値：変換半群理論を拡張し、特に有限鎖上の特殊な変換クラスに関する理論を深化
  2. 構造分析：このクラスの半群の代数構造と組合せ的性質を深く理解
  3. 応用基礎：関連する組合せ数学と代数構造研究に理論的基礎を提供

既存研究の限界

順序保存変換や順序保存的変換に関する研究は存在するが、有向かつ順序減少の両条件を満たす部分変換半群の生成集合、秩、および極大部分半群の完全な特徴付けは依然として不明確である。

核心的貢献

  1. PORD(n,r)\mathcal{PORD}(n,r)の最小生成集合の決定：n−⌊n/3⌋≤r≤n−1n-\lfloor n/3 \rfloor \leq r \leq n-1のとき、Er∪Fr∪GnE_r \cup F_r \cup G_nが最小生成集合であることを証明
  2. 半群の秩の計算：
    • rank(PORD(n,r))=(nr)2n−r+(2n−r−1)(r−2)2+n(n−3)2\text{rank}(\mathcal{PORD}(n,r)) = \binom{n}{r}2^{n-r} + \frac{(2n-r-1)(r-2)}{2} + \frac{n(n-3)}{2}
    • rank(PORDn)=n2−n+1\text{rank}(\mathcal{PORD}_n) = n^2 - n + 1
  3. 単射の場合の特徴付け：IORD(n,r)\mathcal{IORD}(n,r)の生成集合と秩の公式を提供
  4. 極大部分半群の完全な特徴付け：異なるパラメータ範囲に対してすべての極大部分半群の分類を提供

方法の詳細説明

基本的な定義と記号

  • 有限鎖：Xn={1<2<⋯<n}X_n = \{1 < 2 < \cdots < n\}
  • 部分変換：XnX_nの部分集合からXnX_nへの写像
  • 有向変換：順序保存的または順序反転的な変換
  • 順序減少：すべてのx∈dom(α)x \in \text{dom}(\alpha)に対してxα≤xx\alpha \leq x

主要な技術的概念

1. 冪等元の分類

論文はE(PORDn)=E(POPDn)E(\mathcal{PORD}_n) = E(\mathcal{POPD}_n)を証明し、以下が成立：

  • Er(PORDn)={α∈E(PORDn):∣im(α)∣=r}E_r(\mathcal{PORD}_n) = \{\alpha \in E(\mathcal{PORD}_n) : |\text{im}(\alpha)| = r\}
  • ∣Er(PORDn)∣=(nr)2n−r|E_r(\mathcal{PORD}_n)| = \binom{n}{r}2^{n-r}

2. 既約元素

3つのクラスの既約元素を定義：

  • ErE_r：像の大きさがrrである冪等元
  • FrF_r：特定の形式の冪等元ξp,qr\xi^r_{p,q}
  • GnG_n：特定の順序反転変換γp,q\gamma_{p,q}

3. 反転減少度

α∈PORDn∗\alpha \in \mathcal{PORD}^*_nに対して以下を定義： ord(α)=max⁡{m:α∣Xm∈PMDn and max⁡(im(α))=(m+1)α}\text{ord}(\alpha) = \max\{m : \alpha|_{X_m} \in \mathcal{PMD}_n \text{ and } \max(\text{im}(\alpha)) = (m+1)\alpha\}

中心定理

定理8（主要結果）

n−⌊n/3⌋≤r≤n−1n - \lfloor n/3 \rfloor \leq r \leq n-1のとき、Er∪Fr∪GnE_r \cup F_r \cup G_nはPORD(n,r)\mathcal{PORD}(n,r)の最小生成集合であり、以下が成立： rank(PORD(n,r))=(nr)2n−r+(2n−r−1)(r−2)2+n(n−3)2\text{rank}(\mathcal{PORD}(n,r)) = \binom{n}{r}2^{n-r} + \frac{(2n-r-1)(r-2)}{2} + \frac{n(n-3)}{2}

証明の概要

  1. 各要素が既約であることを証明
  2. 生成集合の必要性を証明
  3. 生成集合の十分性を証明し、任意の要素を生成元の積として表現

実験設定

理論的検証

本論文は純粋な理論研究であり、数学的証明により結果を検証：

  1. 組合せ計数：各クラスの要素数の公式を検証
  2. 具体例：小規模な場合の具体的な計算を提供
  3. 特殊な場合：既知の結果を特殊ケースとして検証

検証方法

  • 帰納法による主要定理の証明
  • 異なるパラメータ範囲を分類討論で処理
  • 構成的証明により生成過程を展示

実験結果

主要な結果

1. 秩の計算結果

  • rank(PORD4)=13\text{rank}(\mathcal{PORD}_4) = 13
  • rank(PORD5)=21\text{rank}(\mathcal{PORD}_5) = 21
  • 一般公式：rank(PORDn)=n2−n+1\text{rank}(\mathcal{PORD}_n) = n^2 - n + 1

2. 単射の場合

rank(IORD(n,r))=(nr)+n(n−2r−1)+(r−2)n−r2−r−22+n(n−3)2\text{rank}(\mathcal{IORD}(n,r)) = \binom{n}{r} + n\binom{n-2}{r-1} + \frac{(r-2)n - r^2 - r - 2}{2} + \frac{n(n-3)}{2}

3. 極大部分半群の分類

n−⌊n/3⌋≤r≤n−1n - \lfloor n/3 \rfloor \leq r \leq n-1に対して、極大部分半群は3つのタイプ：

  1. PORD(n,r)∖{ε}\mathcal{PORD}(n,r) \setminus \{\varepsilon\}、ただしε∈Er\varepsilon \in E_r
  2. PORD(n,r)∖Fp,qr\mathcal{PORD}(n,r) \setminus F^r_{p,q}
  3. PORD(n,r)∖Gp,q\mathcal{PORD}(n,r) \setminus G_{p,q}

重要な発見

命題1

rn=max⁡{∣im(α)∣:α∈PRDn∗}=n−⌊n/3⌋r_n = \max\{|\text{im}(\alpha)| : \alpha \in \mathcal{PRD}^*_n\} = n - \lfloor n/3 \rfloor

この結果は順序反転減少変換の最大像の大きさを決定する。

関連研究

歴史的発展

  1. Gomes と Howie (1992)：順序保存変換半群の秩を決定
  2. Fernandes ら (2009)：順序保存的変換の秩を研究
  3. Dimitrova と Koppitz (2012)：順序保存拡張変換を研究
  4. Ayık ら (2025)：順序保存的順序減少変換を研究

本論文の貢献

本論文は有向かつ順序減少の部分変換半群を初めて完全に研究し、この特定の変換クラスの理論的空白を埋める。

結論と考察

主要な結論

  1. PORD(n,r)\mathcal{PORD}(n,r)とIORD(n,r)\mathcal{IORD}(n,r)の秩を完全に決定
  2. 明示的な最小生成集合を提供
  3. すべての極大部分半群を完全に特徴付け

限界

  1. 3≤r<n−⌊n/3⌋3 \leq r < n - \lfloor n/3 \rfloorの場合、∣Hnr∣|H^r_n|の明示的な公式が得られていない
  2. いくつかの証明は複雑な分類討論に依存しており、より簡潔な方法が存在する可能性

今後の方向

論文が提示する未解決問題：∣Hnr∣|H^r_n|の明示的な公式は存在するか？これは後続研究の方向性を示唆している。

深い評価

利点

  1. 完全性：新しい変換半群クラスを体系的に研究
  2. 技術的革新：順序反転減少度などの新しい概念を導入
  3. 結果の完全性：生成集合、秩、極大部分半群の問題を同時に解決
  4. 証明の厳密性：すべての結果に完全な数学的証明を提供

不足点

  1. 計算複雑性：いくつかの公式は複雑で、実際の計算が困難
  2. 未解決問題：依然として解決されていない組合せ計数問題が存在
  3. 応用の限界：主に理論的結果であり、実際の応用は明確でない

影響力

  1. 理論的貢献：変換半群理論を豊かにする
  2. 方法的価値：提供される技術的方法は類似の問題に応用可能
  3. 後続研究：関連分野の研究に基礎を提供

適用場面

  1. 代数構造研究：半群理論と変換半群
  2. 組合せ数学：有限構造の計数問題
  3. 理論計算機科学：オートマトン理論における変換構造

参考文献

論文は変換半群理論の主要な発展過程を網羅する30篇の関連文献を引用し、特に順序保存変換、順序保存的変換、および関連する半群構造の研究成果を含む。

総合評価：これは高品質な理論数学論文であり、新しい変換半群クラスを体系的に研究し、完全な構造理論的結果を得ている。純粋な理論研究ではあるが、方法が革新的で結果が完全であり、変換半群理論に重要な貢献をしている。