해밍 결합 도식

조합론에서 **해밍 결합 도식**(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\le i\le n})은 결합 도식을 이룬다. 이를 **(n,|\Sigma|)-해밍 결합 도식**이라고 한다.언어=en18–19, §1.4.3언어=en2479, 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)\to1 이 존재한다. 그렇다면, f와 g의 상으로 생성되는, 대칭군 \operatorname{Sym}(\Sigma^n)의 부분군을 생각할 수 있으며, 이는 \operatorname{Sym}(n)과 \operatorname{Sym}(\Sigma)^n의 반직접곱 :G=\operatorname{Sym}(\Sigma)^n\rtimes\operatorname{Sym}(n)\le\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}^mh_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)이라고 한다.언어=en
# 성질
해밍 결합 도식은 대칭 결합 도식이다. 즉, 그 모든 이항 관계는 대칭 관계이다.
## 대수적 성질
해밍 결합 도식 \operatorname H(n,|\Sigma|)의 인접 행렬들이 (D_i)_{0\le i\le n}라고 하자. 해밍 결합 도식의 구조 상수는 다음과 같다.언어=en334, §2.3 :D_iD_j=\sum_{k=0}^np_{ij}^kD_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\le i,j,k\le n) 그렇다면, 해밍 결합 도식의 복소수 계수 보스-메스너 대수의 최소 멱등원들은 다음과 같다. :E_a=\frac1{|\Sigma|^n}\sum_{i=0}^nQ_{ai}D_i\qquad(0\le a\le n) :D_i=\sum_{a=0}^nP_{ia}E_i\qquad(0\le i\le 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 xj\binom {n-x}{i-j}\in\mathbb Z[x] 는 **크라우추크 다항식**(Кравчук多項式, Krawtchouk polynomial)이다.언어=en 또한, 다음이 성립한다.2481, §II.B, Example 1 (continued) :v_i=p^0_{ii}=\binom ni(|\Sigma|-1)^i :m_a=\dim\operatorname{im}E_a=\binom na(|\Sigma|-1)^a 여기서 \vec v 및 \vec m이 같은 것은 해밍 결합 도식이 스스로의 쌍대이기 때문이다.
# 예
(2,2)-해밍 결합 도식은 다음과 같다. {| class=wikitable |- ! !! 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)가 도입하였다.