해밍 결합 도식 문서 원본 보기

{{위키데이터 속성 추적}}
[[조합론]]에서 '''해밍 결합 도식'''(Hamming結合圖式, {{llang|en|Hamming association scheme}})은 [[해밍 거리]]가 주어진 [[곱집합]]으로 구성된 [[결합 도식]]이다.

== 정의 ==
=== 해밍 거리를 통한 정의 ===
다음 데이터가 주어졌다고 하자.
* [[유한 집합]] <math>\Sigma</math>
* [[자연수]] <math>n\in\mathbb N</math>
그렇다면, [[곱집합]] <math>\Sigma^n</math> 위에 다음과 같은 [[이항 관계]] <math>(\sim_0,\sim_1,\dotsc,\sim_n)</math>들을 주자.
:<math>u\sim_i v\iff \operatorname{d_H}(u,v)=i\qquad(u,v\in\Sigma^n)</math>
여기서
* <math>\operatorname{d_H}\colon\Sigma^n\times\Sigma^n\to\{0,1,\dotsc,n\}</math>은 [[해밍 거리]]이다.
그렇다면, <math>(\Sigma^n,\{\sim_i\}_{0\le i\le n})</math>은 [[결합 도식]]을 이룬다. 이를 '''<math>(n,|\Sigma|)</math>-해밍 결합 도식'''이라고 한다.<ref name="Bailey">{{서적 인용| first=Rosemary Anne | last=Bailey | url=http://www.maths.qmul.ac.uk/~rab/Asbook | title=Association schemes: designed experiments, algebra and combinatorics|publisher=Cambridge University Press|year=2004|isbn=978-0-521-82446-0| mr=2047311|doi=10.1017/CBO9780511610882|언어=en}}</ref>{{rp|18–19, §1.4.3}}<ref name="DL">{{저널 인용|doi=10.1109/18.720545|제목=Association schemes and coding theory|issn=0018-9448|저널= Institute of Electrical and Electronics Engineers Transactions on Information Theory|권=44|호=6|날짜=1998-10|이름=Philippe|성=Delsarte|이름2=Vladimir Iosifovich|성2=Levenshtein|저자링크2=블라디미르 레벤시테인|쪽= 2477–2504|url=http://www.keldysh.ru/papers/1998/source/article/DELFIN.PS|언어=en}}</ref>{{rp|2479, Example 1}}

=== 군 작용을 통한 정의 ===
해밍 결합 도식은 대신 [[군의 작용]]을 통해 정의될 수도 있다.<ref name="DL"/>{{rp|2482, Example 1 (continued)}}

구체적으로, [[곱집합]] <math>\Sigma^n</math>이 주어졌을 때, 다음과 같은 두 [[단사 함수|단사]] [[군 준동형]]을 생각할 수 있다.
:<math>f\colon\operatorname{Sym}(n)\hookrightarrow \operatorname{Sym}(\Sigma^n)</math>
:<math>g\colon\operatorname{Sym}(\Sigma)^n\hookrightarrow\operatorname{Sym}(\Sigma^n)</math>
여기서
* <math>f</math>는 <math>\Sigma^n</math>의 원소의 <math>n</math>개의 성분들 사이의 [[순열]]을 취하는 것이다.
* <math>g</math>는 <math>\Sigma^n</math>의 원소의 <math>n</math>개의 성분들에 각각 [[순열]]을 가하는 것이다.
<math>g</math>의 [[상 (수학)|상]]은 <math>\operatorname{Sym}(\Sigma^n)</math>의 [[정규 부분군]]이며, [[분할 완전열]]
:<math>1\to\operatorname{Sym}(\Sigma)^n\xrightarrow g\operatorname{Sym}(\Sigma^n)\to\operatorname{Sym}(n)\to1</math>
이 존재한다. 그렇다면, <math>f</math>와 <math>g</math>의 [[상 (수학)|상]]으로 생성되는, [[대칭군 (군론)|대칭군]] <math>\operatorname{Sym}(\Sigma^n)</math>의 [[부분군]]을 생각할 수 있으며, 이는 <math>\operatorname{Sym}(n)</math>과 <math>\operatorname{Sym}(\Sigma)^n</math>의 [[반직접곱]]
:<math>G=\operatorname{Sym}(\Sigma)^n\rtimes\operatorname{Sym}(n)\le\operatorname{Sym}(\Sigma^n)</math>
이다.

그렇다면, <math>\Sigma^n\times\Sigma^n</math> 위에 <math>G</math>의 성분별 [[군의 작용|작용]]
:<math>g\cdot(u,v)=(g\cdot u,g\cdot v)</math>
을 가했을 때, 그 궤도들은 <math>\Sigma^n</math> 위의 [[결합 도식]]을 정의하며, 이를 '''해밍 결합 도식'''이라고 한다.

=== 일반화 해밍 결합 도식 ===
다음 데이터가 주어졌다고 하자.
* [[결합 도식]] <math>(\Sigma,m,\mathcal R=(R_0,R_1,\dotsc,R_m))</math>
* [[자연수]] <math>n\in\mathbb N</math>
그렇다면, [[곱집합]] <math>\Sigma^n</math>의 임의의 두 원소 <math>u,v\in\Sigma^n</math>에 대하여,
:<math>h(u,v)=(h_0(u,v),h_1(u,v),\dotsc,h_m(u,v))\in\mathbb Z^{m+1}</math>
:<math>h_i(u,v)=\begin{cases}
1&(u,v)\in R_i\\
0&(u,v)\not\in R_i
\end{cases}</math>
를 정의하자. 그렇다면,
:<math>\sum_{i=0}^mh_i(u,v)=n</math>
이다. 이제, <math>\mathcal H</math>가
* <math>m+1</math>개의 성분을 가지며,
* 모든 성분이 0 또는 1이며,
* 모든 성분의 합이 <math>n</math>인
벡터들의 집합이라고 하자. 그렇다면, <math>\Sigma^n</math> 위에 각 <math>h'\in\mathcal H</math>에 대하여
:<math>u\sim_{h'}v\iff h(u,v)=h'</math>
를 주면, 이는 [[결합 도식]]을 이룬다. 이를 <math>(\Sigma,m,\mathcal R)</math> 위의 <Math>n</math>차 '''일반화 해밍 결합 도식'''({{llang|en|generalized Hamming association scheme}})이라고 한다.<ref>{{저널 인용|arxiv=1011.1044|제목=Generalized Hamming schemes|이름=Chris|성=Godsil|bibcode=2010arXiv1011.1044G|날짜=2010|언어=en}}</ref>

== 성질 ==
해밍 결합 도식은 대칭 결합 도식이다. 즉, 그 모든 [[이항 관계]]는 [[대칭 관계]]이다.

=== 대수적 성질 ===
해밍 결합 도식 <math>\operatorname H(n,|\Sigma|)</math>의 인접 행렬들이 <math>(D_i)_{0\le i\le n}</math>라고 하자.

해밍 결합 도식의 구조 상수는 다음과 같다.<ref>{{저널 인용|url=http://www.kurims.kyoto-u.ac.jp/EMIS/journals/JACO/Volume20_3/t5q1424552661540.fulltext.pdf|저널=Journal of Algebraic Combinatorics|권=20|호=3|쪽=331–340|제목=Modular adjacency algebras of Hamming schemes|이름=Masayoshi|성=Yoshikawa|doi=10.1023/B:JACO.0000048521.68503.2b|issn= 0925-9899|언어=en}}</ref>{{rp|334, §2.3}}
:<math>D_iD_j=\sum_{k=0}^np_{ij}^kD_k</math>
:<math>p_{ij}^k=
\sum_{m=0}^{n-k}
\binom k{k+m-i}
\binom{i-m}{k-j+m}
\binom{n-k}m
(|\Sigma|-1)^m(|\Sigma|-2)^{i+j-k-2m}
</math>
특히, <math>|\Sigma|=2</math>일 때 이는 <math>m=(i+j-k)/2</math>인 항만 남게 되며, 이 경우 구조 상수는 다음과 같다.
:<math>p_{ij}^k=\begin{cases}
\binom k{(i-j+k)/2}\binom{n-k}{(i+j-k)/2} & 2\mid i+j-k \\
0& 2\nmid i+j-k
\end{cases}\qquad(0\le i,j,k\le n)</math>

그렇다면, 해밍 결합 도식의 복소수 계수 보스-메스너 대수의 최소 멱등원들은 다음과 같다.
:<math>E_a=\frac1{|\Sigma|^n}\sum_{i=0}^nQ_{ai}D_i\qquad(0\le a\le n)</math>
:<math>D_i=\sum_{a=0}^nP_{ia}E_i\qquad(0\le i\le n)</math>
:<math>Q_{ai}=\operatorname K_a(i;n,|\Sigma|)</math>
:<math>P_{ia}=\operatorname K_i(a;n,|\Sigma)</math>

여기서
:<math>\operatorname K_i(x;n,q)=\sum_{j=0}^i(-)^j(q-1)^{i-j}\binom xj\binom {n-x}{i-j}\in\mathbb Z[x]</math>
는 '''크라우추크 다항식'''(Кравчук多項式, {{llang|en|Krawtchouk polynomial}})이다.<ref>{{저널 인용|arxiv=1101.1798|제목=On Krawtchouk polynomials|이름=Rodney|성=Coleman|날짜=2011|bibcode=2011arXiv1101.1798C|언어=en}}</ref>

또한, 다음이 성립한다.<ref name="DL"/>{{rp|2481, §II.B, Example 1 (continued)}}
:<math>v_i=p^0_{ii}=\binom ni(|\Sigma|-1)^i</math>
:<math>m_a=\dim\operatorname{im}E_a=\binom na(|\Sigma|-1)^a</math>

여기서 <math>\vec v</math> 및 <math>\vec m</math>이 같은 것은 해밍 결합 도식이 스스로의 쌍대이기 때문이다.

== 예 ==
(2,2)-해밍 결합 도식은 다음과 같다.
{| class=wikitable style="text-align: center"
|-
! !! AA !! AB !! BA !! BB
|-
! AA
| 0 || 1 || 1 || 2
|-
! AB
| 1 || 0 || 2 || 1
|-
! BA
| 1 || 2 || 0 || 1
|-
! BB
| 2 || 1 || 1 || 0
|}

== 역사 ==
“해밍 결합 도식”이라는 용어는 [[리처드 해밍]]의 이름을 땄으며, [[해밍 거리]]에서 유래하였다.

크라우추크 다항식은 우크라이나의 수학자 미하일로 필리포비치 크라우추크({{llang|uk|Миха́йло Пили́пович Кравчу́к}}, {{llang|ru|Михаил Филиппович Кравчук|미하일 필리포비치 크랍추크}}, 1892~1942)가 도입하였다.<ref>{{인용| last1=Krawtchouk | first1=M. | title=Sur une généralisation des polynomes d’Hermite | url=http://gallica.bnf.fr/ark:/12148/bpt6k3142j.pleinepage.f620  | jfm=55.0799.01 | 날짜=1929-09-23 | journal=Comptes rendus hebdomadaires des séances de l’Académie des sciences | volume=189 | pages=620–622 | 언어=fr}}</ref>

== 참고 문헌 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Association scheme}}
* {{매스월드|id=HammingScheme|title=Hamming scheme}}
* {{매스월드|id=KrawtchoukPolynomial|title=Krawtchouk polynomial}}
* {{서적 인용|url=https://pdfs.semanticscholar.org/8e9a/8f541375c4aacf848740b1e373acd5917e75.pdf|제목=The Hamming codes and Delsarte’s linear programming bound|이름=Sky|성=McKinley|기타=석사 학위 논문 (지도 교수 John S. Caughman Ⅳ)|출판사=Portland State University|날짜=2003-05|언어=en}}

{{전거 통제}}

[[분류:조합론]]
[[분류:부호 이론]]