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

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

基本信息

  • 论文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. 不可分解元素

定义了三类不可分解元素：

  • 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，极大子半群有三种类型：

  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篇相关文献，涵盖了变换半群理论的主要发展历程，特别是保序变换、保向变换和相关半群结构的研究成果。

总体评价：这是一篇高质量的理论数学论文，系统地研究了一个新的变换半群类，获得了完整的结构理论结果。虽然是纯理论研究，但方法创新，结果完整，为变换半群理论做出了重要贡献。