해밍 결합 도식

조합론에서 해밍 결합 도식(Hamming結合圖式, 영어: Hamming association scheme)은 해밍 거리가 주어진 곱집합으로 구성된 결합 도식이다.

정의

해밍 거리를 통한 정의

다음 데이터가 주어졌다고 하자.

• 유한 집합 $\Sigma$
• 자연수 $n\in \mathbb {N}$

그렇다면, 곱집합 $\Sigma ^{n}$ 위에 다음과 같은 이항 관계 $(\sim _{0},\sim _{1},\dotsc ,\sim _{n})$들을 주자.

$u\sim _{i}v\iff \operatorname {d_{H}} (u,v)=i\qquad (u,v\in \Sigma ^{n})$

여기서

• $\operatorname {d_{H}} \colon \Sigma ^{n}\times \Sigma ^{n}\to \{0,1,\dotsc ,n\}$은 해밍 거리이다.

그렇다면, $(\Sigma ^{n},\{\sim _{i}\}_{0\leq i\leq n})$은 결합 도식을 이룬다. 이를 $(n,|\Sigma |)$-해밍 결합 도식이라고 한다.^{:18–19, §1.4.3:2479, Example 1}

군 작용을 통한 정의

해밍 결합 도식은 대신 군의 작용을 통해 정의될 수도 있다.^{:2482, Example 1 (continued)}

구체적으로, 곱집합 $\Sigma ^{n}$이 주어졌을 때, 다음과 같은 두 단사 군 준동형을 생각할 수 있다.

$f\colon \operatorname {Sym} (n)\hookrightarrow \operatorname {Sym} (\Sigma ^{n})$

$g\colon \operatorname {Sym} (\Sigma )^{n}\hookrightarrow \operatorname {Sym} (\Sigma ^{n})$

여기서

• $f$는 $\Sigma ^{n}$의 원소의 $n$개의 성분들 사이의 순열을 취하는 것이다.
• $g$는 $\Sigma ^{n}$의 원소의 $n$개의 성분들에 각각 순열을 가하는 것이다.

$g$의 상은 $\operatorname {Sym} (\Sigma ^{n})$의 정규 부분군이며, 분할 완전열

$1\to \operatorname {Sym} (\Sigma )^{n}{\xrightarrow {g}}\operatorname {Sym} (\Sigma ^{n})\to \operatorname {Sym} (n)\to 1$

이 존재한다. 그렇다면, $f$와 $g$의 상으로 생성되는, 대칭군 $\operatorname {Sym} (\Sigma ^{n})$의 부분군을 생각할 수 있으며, 이는 $\operatorname {Sym} (n)$과 $\operatorname {Sym} (\Sigma )^{n}$의 반직접곱

$G=\operatorname {Sym} (\Sigma )^{n}\rtimes \operatorname {Sym} (n)\leq \operatorname {Sym} (\Sigma ^{n})$

이다.

그렇다면, $\Sigma ^{n}\times \Sigma ^{n}$ 위에 $G$의 성분별 작용

$g\cdot (u,v)=(g\cdot u,g\cdot v)$

을 가했을 때, 그 궤도들은 $\Sigma ^{n}$ 위의 결합 도식을 정의하며, 이를 해밍 결합 도식이라고 한다.

일반화 해밍 결합 도식

다음 데이터가 주어졌다고 하자.

• 결합 도식 $(\Sigma ,m,{\mathcal {R}}=(R_{0},R_{1},\dotsc ,R_{m}))$
• 자연수 $n\in \mathbb {N}$

그렇다면, 곱집합 $\Sigma ^{n}$의 임의의 두 원소 $u,v\in \Sigma ^{n}$에 대하여,

$h(u,v)=(h_{0}(u,v),h_{1}(u,v),\dotsc ,h_{m}(u,v))\in \mathbb {Z} ^{m+1}$

$h_{i}(u,v)={\begin{cases}1&(u,v)\in R_{i}\\0&(u,v)\not \in R_{i}\end{cases}}$

를 정의하자. 그렇다면,

$\sum _{i=0}^{m}h_{i}(u,v)=n$

이다. 이제, ${\mathcal {H}}$가

• $m+1$개의 성분을 가지며,
• 모든 성분이 0 또는 1이며,
• 모든 성분의 합이 $n$인

벡터들의 집합이라고 하자. 그렇다면, $\Sigma ^{n}$ 위에 각 $h'\in {\mathcal {H}}$에 대하여

$u\sim _{h'}v\iff h(u,v)=h'$

를 주면, 이는 결합 도식을 이룬다. 이를 $(\Sigma ,m,{\mathcal {R}})$ 위의 $n$차 일반화 해밍 결합 도식(영어: generalized Hamming association scheme)이라고 한다.

성질

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

대수적 성질

해밍 결합 도식 $\operatorname {H} (n,|\Sigma |)$의 인접 행렬들이 $(D_{i})_{0\leq i\leq n}$라고 하자.

해밍 결합 도식의 구조 상수는 다음과 같다.^{:334, §2.3}

$D_{i}D_{j}=\sum _{k=0}^{n}p_{ij}^{k}D_{k}$

$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}$

특히, $|\Sigma |=2$일 때 이는 $m=(i+j-k)/2$인 항만 남게 되며, 이 경우 구조 상수는 다음과 같다.

$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\leq i,j,k\leq n)$

그렇다면, 해밍 결합 도식의 복소수 계수 보스-메스너 대수의 최소 멱등원들은 다음과 같다.

$E_{a}={\frac {1}{|\Sigma |^{n}}}\sum _{i=0}^{n}Q_{ai}D_{i}\qquad (0\leq a\leq n)$

$D_{i}=\sum _{a=0}^{n}P_{ia}E_{i}\qquad (0\leq i\leq n)$

$Q_{ai}=\operatorname {K} _{a}(i;n,|\Sigma |)$

$P_{ia}=\operatorname {K} _{i}(a;n,|\Sigma )$

여기서

$\operatorname {K} _{i}(x;n,q)=\sum _{j=0}^{i}(-)^{j}(q-1)^{i-j}{\binom {x}{j}}{\binom {n-x}{i-j}}\in \mathbb {Z} [x]$

는 크라우추크 다항식(Кравчук多項式, 영어: Krawtchouk polynomial)이다.

또한, 다음이 성립한다.^{:2481, §II.B, Example 1 (continued)}

$v_{i}=p_{ii}^{0}={\binom {n}{i}}(|\Sigma |-1)^{i}$

$m_{a}=\dim \operatorname {im} E_{a}={\binom {n}{a}}(|\Sigma |-1)^{a}$

여기서 ${\vec {v}}$ 및 ${\vec {m}}$이 같은 것은 해밍 결합 도식이 스스로의 쌍대이기 때문이다.

예

(2,2)-해밍 결합 도식은 다음과 같다.

	AA	AB	BA	BB
AA	0	1	1	2
AB	1	0	2	1
BA	1	2	0	1
BB	2	1	1	0

역사

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

크라우추크 다항식은 우크라이나의 수학자 미하일로 필리포비치 크라우추크(우크라이나어: Миха́йло Пили́пович Кравчу́к, 러시아어: Михаил Филиппович Кравчук 미하일 필리포비치 크랍추크^[*], 1892~1942)가 도입하였다.

외부 링크

• “Association scheme”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Hamming scheme”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Krawtchouk polynomial”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• McKinley, Sky (2003년 5월). 《The Hamming codes and Delsarte’s linear programming bound》 (PDF) (영어). 석사 학위 논문 (지도 교수 John S. Caughman Ⅳ). Portland State University.