플랙틱 모노이드

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

플랙틱 모노이드는 전순서 집합에 정의된 모노이드로, 크누스 동치라는 동치 관계를 통해 단어들을 분류한다. 크누스 동치는 플랙틱 모노이드의 동일한 원소를 나타내는 단어들을 묶는 관계이며, 단어의 역 격자성, 비감소 부분 수열의 길이 등을 보존한다. 플랙틱 모노이드의 각 원소는 준표준 영 타블로에 대응하며, 쉔슈테드 삽입을 통해 곱셈을 정의할 수 있다. 플랙틱 모노이드의 모노이드 링을 태블로 링이라고 하며, 성장 함수는 특정 형태를 가진다. 크누스 동치는 도널드 크누스가 발견했으며, 플랙틱 모노이드라는 용어는 알랭 라스쿠와 마르셀폴 쉬첸베르게르에 의해 도입되었다.

플랙틱 모노이드

📚 더 읽어볼만한 페이지

반군론 - 멱등원
멱등원은 연산을 통해 자기 자신을 결과로 반환하는 원소로, 환이나 모노이드에서는 <math>e^2 = e</math>를 만족하는 원소 <math>e</math>를 의미하며, 환의 구조 분석에 중요한 역할을 하고 범주론에서는 자기 사상 <math>e</math>가 <math>e \circ e = e</math>를 만족시킬 때 멱등 사상이라고 정의한다.
반군론 - 화환곱
화환곱은 군론에서 두 군의 구조를 결합하여 더 큰 군을 만드는 연산으로, 반군 작용을 통해 정의되며 다양한 종류가 존재하고 결합 법칙을 따르며 여러 분야에 응용된다.

1. 개요
2. 정의
3. 크누스 동치 (Knuth Equivalence)
4. 준표준 영 타블로와의 대응 (Correspondence with Semistandard Young Tableaux)
- 4.1. 조각 그림 맞추기 (Jeu de Taquin)
5. 태블로 링 (Tableau Ring)
6. 성장 (Growth)
7. 역사

2. 정의

전순서 집합 $(\Sigma,\le)$ 위의 플랙틱 모노이드는 다음과 같이 표시되는 모노이드이다.
: $\langle \Sigma | \{yzx = yxz \colon x < y \le z\} \cup \{ xzy = zxy \colon x \le y < z\} \rangle$
즉, 그 원소는 알파벳 $\Sigma$ 에 대한 단어들의 동치류이다. 단어에 대한 동치 관계를 크누스 동치라고 한다.
완전 순서 집합 알파벳(주로 양의 정수) 위의 플랙틱 모노이드는 다음과 같은 표현을 갖는 모노이드이다.

* 생성원은 알파벳의 문자이다.
* 관계는 다음과 같다. 만약 x < y ≤ z이면 기본 크누스 변환 yzx ≡ yxz이고, 만약 x ≤ y < z이면 xzy ≡ zxy이다.

3. 크누스 동치 (Knuth Equivalence)

두 단어가 플랙틱 모노이드의 동일한 요소를 나타내는 경우, 즉 하나의 단어가 일련의 기본 Knuth 변환을 통해 다른 단어에서 얻을 수 있는 경우, 이 두 단어를 Knuth 동치라고 부른다.

Knuth 동치는 몇 가지 속성을 보존한다.
* 단어가 역 격자 단어이면 Knuth 동치인 모든 단어도 역 격자 단어이다.
* 두 단어가 Knuth 동치이면, 가장 오른쪽의 최대 원소를 제거하여 얻은 단어와 가장 왼쪽의 최소 원소를 제거하여 얻은 단어도 서로 Knuth 동치이다.
* Knuth 동치는 가장 긴 비감소 부분 수열의 길이를 보존하며, 더 일반적으로는 고정된 모든 k에 대해 k개의 서로소인 비감소 부분 수열 길이의 합의 최댓값을 보존한다.

4. 준표준 영 타블로와의 대응 (Correspondence with Semistandard Young Tableaux)

자연수의 전순서 집합 위의 플랙틱 모노이드의 각 원소는 준표준 영 타블로(즉, 각 행의 길이들은 증가하지 않으며, 각 열의 길이들은 감소하는 영 타블로)에 대응한다.

모든 단어는 동일한 정렬된 알파벳에 대한 고유한 준표준 영 테이블의 단어와 크누스 동치 관계를 갖는다(이는 각 행이 비감소하고 각 열이 엄격하게 증가함을 의미). 여기서 테이블은 행 또는 열별로 읽을 수 있다. 따라서 플랙틱 모노이드의 요소는 준표준 영 테이블과 동일시될 수 있으며, 따라서 이들은 또한 모노이드를 형성한다.

준표준 영 테이블의 단어를 생성자로 왼쪽에서 곱하는 것은 쉔슈테드 삽입을 영 테이블에 삽입하는 것과 같다. 행 순서에서 테이블의 단어는 생성자의 점점 더 긴 비감소 시퀀스의 곱과 같다. 새 생성자는 더 크면 추가하여, 그렇지 않으면 플랙틱 관계를 반복적으로 적용하여 순서가 잘못된 요소를 다음 행으로 이동시켜 적절한 위치에 삽입할 수 있다. 후자의 경우, 순서가 잘못된 요소는 각 행에서 자신보다 큰 가장 왼쪽에 있는 항목을 대체하고, 이동된 요소는 다음 행에 삽입된다.

쉔슈테드 삽입은 영 테이블을 보존하므로, 이는 플랙틱 모노이드의 요소가 영 테이블에 해당하는 표준 형식으로 작성될 수 있다는 귀납적 증명을 제공하며, 이 구성은 준표준 테이블의 자연스러운 곱을 정의한다.

4.1. 조각 그림 맞추기 (Jeu de Taquin)

두 개의 엇갈린 영 도표는 해당 단어 읽기가 크누스 동치, 즉 플랙틱 모노이드의 동치 요소에 해당하는 경우에만 조각 그림 맞추기 동치이다. 이는 영 도표 측면에서 플랙틱 모노이드 곱셈의 대안적인 정의를 제공한다. 두 개의 도표는 빈 직사각형 주위에 모두 그려 엇갈린 도표를 형성하고 조각 그림 맞추기 슬라이드를 사용하여 수정함으로써 곱할 수 있다.

5. 태블로 링 (Tableau Ring)

태블로 링은 플랙틱 모노이드의 모노이드 링으로, 플랙틱 모노이드의 원소로 구성된 Z-기저를 가지며, 플랙틱 모노이드에서의 곱셈과 동일한 곱셈을 갖는다.

알파벳 위의 플랙틱 링에서 (알파벳으로 인덱싱된 변수를 갖는) 다항식 링으로 가는 준동형 사상이 존재하며, 이 준동형 사상은 임의의 태블로를 해당 엔트리의 변수들의 곱으로 매핑하며, 이는 플랙틱 반군의 아벨화에 해당한다.

6. 성장 (Growth)

플랙틱 모노이드의 생성 함수는 크기가 n인 알파벳에 대해 다음과 같다.

: $\Gamma(t) = \frac{1}{(1-t)^n} \frac{1}{(1-t^2)^{n(n-1)/2}} \$

이는 $\frac{n(n+1)}{2}$ 차원의 다항식 성장을 보여준다.

7. 역사

도널드 크누스가 1970년에 크누스 동치 관계를 발견하였다. "플랙틱 모노이드"(모노이드 플락시크/monoïde plaxique^프랑스어)라는 용어는 1981년에 알랭 라스쿠(Alain Lascoux^프랑스어)와 마르셀폴 쉬첸베르게르(Marcel-Paul Schützenberger^프랑스어)가 도입하였으며, 플라크/plaque^프랑스어(판)에서 유래하였다. 이는 플랙틱 모노이드에서, 글자들이 특별한 경우에 서로 가환하는 것을 판 구조론에서 판들이 특별한 경우에 이동할 수 있는 것에 빗댄 것이다.