해밍 결합 도식

틀:위키데이터 속성 추적 조합론에서 해밍 결합 도식(Hamming結合圖式, 틀:Llang)은 해밍 거리가 주어진 곱집합으로 구성된 결합 도식이다.

정의

해밍 거리를 통한 정의

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

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

그렇다면, 곱집합 ${\mathrm{\Sigma }}^n$ 위에 다음과 같은 이항 관계 $({\sim }_0,{\sim }_1,\dots ,{\sim }_n)$들을 주자.

$u{\sim }_{i}v⟺{\mathrm{d}}_{\mathrm{H}}(u,v)=i(u,v\in {\mathrm{\Sigma }}^n)$

여기서

• ${\mathrm{d}}_{\mathrm{H}}:{\mathrm{\Sigma }}^n\times {\mathrm{\Sigma }}^n\to \{0,1,\dots ,n\}$은 해밍 거리이다.

그렇다면, $({\mathrm{\Sigma }}^n,\{{\sim }_i{\}}_{0\le i\le n})$은 결합 도식을 이룬다. 이를 $(n,|\mathrm{\Sigma }|)$-해밍 결합 도식이라고 한다.틀:Rp틀:Rp

군 작용을 통한 정의

해밍 결합 도식은 대신 군의 작용을 통해 정의될 수도 있다.틀:Rp

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

$f:\mathrm{Sym}(n)\hookrightarrow \mathrm{Sym}({\mathrm{\Sigma }}^n)$

$g:\mathrm{Sym}(\mathrm{\Sigma }{)}^n\hookrightarrow \mathrm{Sym}({\mathrm{\Sigma }}^n)$

여기서

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

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

$1\to \mathrm{Sym}(\mathrm{\Sigma }{)}^n\stackrel{g}{\to }\mathrm{Sym}({\mathrm{\Sigma }}^n)\to \mathrm{Sym}(n)\to 1$

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

$G=\mathrm{Sym}(\mathrm{\Sigma }{)}^n⋊\mathrm{Sym}(n)\le \mathrm{Sym}({\mathrm{\Sigma }}^n)$

이다.

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

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

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

일반화 해밍 결합 도식

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

• 결합 도식 $(\mathrm{\Sigma },m,ℛ=(R_0,R_1,\dots ,R_m))$
• 자연수 $n\in \mathbb{N}$

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

$h(u,v)=(h_0(u,v),h_1(u,v),\dots ,h_m(u,v))\in {\mathbb{Z}}^{m+1}$

$h_i(u,v)=\{\begin{array}{cc}1& (u,v)\in R_i\\ 0& (u,v)\in ̸R_i\end{array}$

를 정의하자. 그렇다면,

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

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

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

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

$u{\sim }_{h^{\prime }}v⟺h(u,v)=h^{\prime }$

를 주면, 이는 결합 도식을 이룬다. 이를 $(\mathrm{\Sigma },m,ℛ)$ 위의 $n$차 일반화 해밍 결합 도식(틀:Llang)이라고 한다.

성질

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

대수적 성질

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

해밍 결합 도식의 구조 상수는 다음과 같다.틀:Rp

$D_i{D}_j=\sum _{k=0}^n{p}_{ij}^k{D}_k$

$p_{ij}^k=\sum _{m=0}^{n-k}(\genfrac{}{}{0ex}{}{k}{k+m-i})(\genfrac{}{}{0ex}{}{i-m}{k-j+m})(\genfrac{}{}{0ex}{}{n-k}{m})(|\mathrm{\Sigma }|-1{)}^m(|\mathrm{\Sigma }|-2{)}^{i+j-k-2m}$

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

$p_{ij}^k=\{\begin{array}{cc}(\genfrac{}{}{0ex}{}{k}{(i-j+k)/2})(\genfrac{}{}{0ex}{}{n-k}{(i+j-k)/2})& 2\mid i+j-k\\ 0& 2\nmid i+j-k\end{array}(0\le i,j,k\le n)$

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

$E_a=\frac{1}{|\mathrm{\Sigma }{|}^n}\sum _{i=0}^n{Q}_{ai}{D}_i(0\le a\le n)$

$D_i=\sum _{a=0}^n{P}_{ia}{E}_i(0\le i\le n)$

$Q_{ai}={\mathrm{K}}_a(i;n,|\mathrm{\Sigma }|)$

$P_{ia}={\mathrm{K}}_i(a;n,|\mathrm{\Sigma })$

여기서

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

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

또한, 다음이 성립한다.틀:Rp

$v_i=p_{ii}^0=(\genfrac{}{}{0ex}{}{n}{i})(|\mathrm{\Sigma }|-1{)}^i$

$m_a=\dim \mathrm{im}{E}_a=(\genfrac{}{}{0ex}{}{n}{a})(|\mathrm{\Sigma }|-1{)}^a$

여기서 $\overrightarrow{v}$ 및 $\overrightarrow{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

역사

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

크라우추크 다항식은 우크라이나의 수학자 미하일로 필리포비치 크라우추크(틀:Llang, 틀:Llang, 1892~1942)가 도입하였다.

외부 링크

• 틀:Eom
• 틀:매스월드
• 틀:매스월드
• 틀:서적 인용