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)의 최소 생성집합과 계수(rank)를 결정하고, 그들의 극대 부분반군을 특성화한다.

연구 배경 및 동기

문제 배경

변환 반군 이론은 대수학의 중요한 분야로, 집합 위의 변환의 대수 구조를 연구한다. 본 논문이 집중하는 핵심 문제는:

  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편의 관련 문헌을 인용하며, 특히 순서-보존 변환, 방향-보존 변환 및 관련 반군 구조 연구 성과를 다룬다.

종합 평가: 이것은 새로운 변환 반군 클래스를 체계적으로 연구하여 완전한 구조 이론 결과를 얻은 고품질의 이론 수학 논문이다. 순수 이론 연구이지만 방법이 혁신적이고 결과가 완전하여 변환 반군 이론에 중요한 기여를 했다.