해밍 결합 도식

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

정의

해밍 거리를 통한 정의

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

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

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

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

여기서

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

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

군 작용을 통한 정의

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

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

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

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

여기서

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

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

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

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

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

이다.

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

${\displaystyle g\cdot (u,v)=(g\cdot u,g\cdot v)}$

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

일반화 해밍 결합 도식

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

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

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

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

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

를 정의하자. 그렇다면,

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

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

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

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

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

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

성질

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

대수적 성질

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

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

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

${\displaystyle 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}}$

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

${\displaystyle 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)}$

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

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

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

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

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

여기서

${\displaystyle \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)이다.^[5]

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

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

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

여기서 ${\displaystyle {\vec {v}}}$ 및 ${\displaystyle {\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)가 도입하였다.^[6]