블록 설계

조합론에서 블록 설계(block設計, 영어: block design 블록 디자인^[*])는 같은 크기의 일련의 부분 집합들이 주어져 있는 유한 집합이다. 이 경우, 이러한 부분 집합을 블록(영어: block)이라고 하며, 블록 설계는 (예를 들어) “$k$개의 원소들을 포함하는 블록의 수는 원소의 선택에 상관없이 $\lambda$개”와 같은 꼴의 조건을 만족시켜야 한다.

정의

존슨 결합 도식 속의 블록 설계

세 자연수 $t,k,n\in \mathbb {N}$가 주어졌다고 하자. $(t,k,n)$-블록 설계 $(X,{\mathcal {B}})$는 다음과 같은 데이터로 주어진다.

• 크기 $n$의 유한 집합 $X$. 그 원소를 점(點, 영어: point)이라고 한다.
• $X$의, 크기 $k$의 부분 집합들의 족 ${\mathcal {B}}\subseteq \operatorname {Pow} _{k}(X)$. 그 원소를 블록(영어: block)이라고 한다. (여기서 $\operatorname {Pow} _{k}(X)$는 $X$의 부분 집합들 가운데 크기가 $k$인 것들로 구성된, 멱집합의 부분 집합이다.)

이는 다음 조건을 만족시켜야 한다.

• $t$개의 서로 다른 점들이 주어졌을 때, 이 점들을 모두 포함하는 블록의 개수는 선택한 점들에 상관없는 값 $\lambda _{t}>0$이다. (0을 제외하는 것은 피셔 부등식 등을 따르지 않는 $(X,{\mathcal {B}}=\varnothing )$를 배제하기 위함이다.)

두 $(t,k,n)$-블록 설계 $(X,{\mathcal {B}})$, $(X',{\mathcal {B}}')$가 주어졌다고 하자. 만약 이 둘 사이에 전단사 함수

$\iota \colon X\to X'$

가 존재하여

$\{\iota (B)\}_{B\in {\mathcal {B}}}={\mathcal {B}}'$

라면, $(X,{\mathcal {B}})$와 $(X',{\mathcal {B}}')$가 서로 동형이라고 한다.

$\lambda _{t}=1$인 $(t,k,n)$-블록 설계는 $(t,k,n)$-슈타이너 계(Steiner系, 영어: Steiner system 스타이너 시스템^[*])라고 한다. 보통, $\lambda _{t}=1$인 $(t,k,n)$-블록 설계 $(X,{\mathcal {B}})$는 $\operatorname {S} (t,k,n)$로 표기된다.

일반적 결합 도식 속의 블록 설계

위 정의는 결합 도식의 개념을 통해 일반화된다.^{:2483–2486, §Ⅲ}

구체적으로, 결합 도식 $(X,\{D_{i}\in \operatorname {Mat} (|X|,|X|;\mathbb {Z} )\}_{i\in I})$이 주어졌다고 하자. 그렇다면, 그 복소수 계수 보스-메스너 대수

${\mathcal {A}}=\operatorname {Span} _{\mathbb {C} }\{D_{i}\}_{i\in I}\subseteq \operatorname {Mat} (|X|,|X|;\mathbb {C} )$

는 반단순 대수이며, 따라서 그 최소 멱등원들의 집합

$(E_{a})_{a\in A}$

$E_{a}E_{b}=\delta _{ab}E_{a}$

$\sum _{a\in A}E_{a}=1_{\mathcal {A}}$

를 정의할 수 있다. 특히,

$E_{0}={\frac {1}{|X|}}{\mathsf {J}}_{|X|\times |X|}$

는 항상 최소 멱등원이다. (${\mathsf {J}}_{|X|\times |X|}$는 모든 성분이 1인 $|X|\times |X|$ 정사각 행렬이다.)

이제, 계수

$E_{a}=\sum _{i=0}^{|I|}Q_{ai}D_{i}$

들을 정의할 수 있다. $X$의 부분 집합(즉, $X$ 속의 블록 부호) $C\subseteq X$가 주어졌을 때, 내부 분포

$\alpha _{i}={\frac {|C^{2}\cap R_{i}|}{|C|}}$

및 쌍대 내부 분포

$\beta _{a}=\sum _{i\in I}Q_{ai}\alpha _{i}$

를 정의할 수 있다.

만약 어떤 부분 집합 $E\subseteq A$가 주어졌을 때, 만약 $X$의 부분 집합 $C\subseteq X$가 다음 조건을 만족시킬 경우, $E$-블록 설계(영어: $E$-block design)라고 한다.^{:2484, Definition 7}

임의의 $a\not \in E$에 대하여, $\beta _{a}=0$

만약 $X$가 존슨 결합 대수일 때, 이는 첫째 정의로 귀결된다.

연산

유도 블록 설계

임의의 $(t,k,n)$-블록 설계 $(X,{\mathcal {B}})$ 및 점 $x\in X$가 주어졌다고 하자. 그렇다면,

$X'=X\setminus \{x\}$

${\mathcal {B}}'=\{B\setminus \{x\}\colon x\in B\in {\mathcal {B}}\}$

는 $(t-1,k-1,n-1)$-블록 설계를 이루며,

$\lambda '_{t-1}=\lambda _{t}$

이다. 이를 $(X,{\mathcal {B}})$의 유도 블록 설계(誘導block設計, 영어: derived block design)이라고 한다. (서로 다른 점에서 취한 유도 블록 설계는 서로 동형이지 못할 수 있다.)

특히, 슈타이너 계의 유도 블록 설계는 항상 슈타이너 계이다.

결합 행렬

$(t,k,n)$-블록 설계 $(X,{\mathcal {B}})$에서, $X=\{x_{1},\dotsc ,x_{n}\}$와 ${\mathcal {B}}=\{B_{1},\dotsc ,B_{\lambda _{0}}\}$ 위에 각각 임의로 전순서를 주자. 그렇다면, $(X,{\mathcal {B}})$의 결합 행렬(영어: incidence matrix)은 다음과 같은 $n\times \lambda _{0}$ 행렬

$M\in \operatorname {Mat} (n,\lambda _{0};\mathbb {F} _{2})$

이다.

$M_{ij}={\begin{cases}1&x_{i}\in B_{j}\\0&x_{i}\not \in B_{j}\end{cases}}$

정사각 블록 설계의 경우 결합 행렬은 정사각 행렬이다.

성질

임의의 $(t,k,n)$-블록 설계 $(X,{\mathcal {B}})$가 주어졌을 때, 다음 정수들을 정의하자.

$\lambda _{i}={\frac {\lambda _{t}{\binom {n-i}{t-i}}}{\binom {k-i}{t-i}}}\qquad (i\in \{0,1,\dotsc ,t\})$

그렇다면, 다음이 성립한다.

• $0\leq i\leq t$가 주어졌을 때, $i$개의 점들을 모두 포함하는 블록의 개수는 정확히 $\lambda _{i}$이다.

특히, $i=0$일 경우,

• 블록의 수는 $\textstyle \lambda _{0}=\lambda _{t}{\binom {n}{t}}/{\binom {k}{t}}$이다.

이에 따라, 모든 $(t,k,n)$-블록 설계는 임의의 $0\leq t'\leq t$에 대하여 $(t',k,n)$-블록 설계이다.

존재의 필요 조건

피셔 부등식(Fisher不等式, 영어: Fisher’s inequality)에 따르면, 임의의 $(2,k,n)$-블록 설계 $(X,{\mathcal {B}})$에 대하여, 다음이 성립한다.

$|X|\geq \lambda _{0}$

$k\geq \lambda _{1}$

($X\lambda _{1}=k\lambda _{0}$이므로, 두 조건은 사실 동치이다.) 이 부등식을 포화시키는 블록 설계, 즉 점의 수가 블록의 수와 같은 2-블록 설계를 정사각 블록 설계(正四角block設計, 영어: square block matrix) 또는 대칭 블록 설계(對稱block設計, 영어: symmetric block design)라고 한다.

보다 일반적으로, 임의의 $(t,k,n)$-블록 설계 $(X,{\mathcal {B}})$에 대하여, 다음이 성립한다.

$\lambda _{0}\geq {\binom {n}{\lfloor t/2\rfloor }}$

브룩-라이저-차울라 정리(Bruck-Ryser-चावला定理, 영어: Bruck–Ryser–Chowla theorem)에 따르면, 임의의 $(t,k,n)$-블록 설계 $(X,{\mathcal {B}})$에 대하여, 만약 $|X|=\lambda _{0}$라면,

• 만약 $|X|$가 짝수라면, $k-\lambda _{2}$는 제곱수이다.
• 만약 $|X|$가 홀수라면, $x^{2}=(k-\lambda _{2})y^{2}+(-1)^{(|X|-1)/2}\lambda _{2}z^{2}$를 만족시키는 정수 $(x,y,z)\neq (0,0,0)$가 존재한다.

개수

작은 크기의 $(t=2,k=3,n)$-슈타이너 계의 동형류들의 수들은 다음과 같다. (OEIS의 수열 A30129)

$n$	1	3	7	9	13	15	19	…
$(2,3,n)$-슈타이너 계의 동형류의 수	1	1	1	1	2	80	11084874829

작은 크기의 $(t=3,k=4,n)$-슈타이너 계의 동형류들의 수들은 다음과 같다. (OEIS의 수열 A51390)

$n$	1	2	4	8	10	14	16	…
$(3,4,n)$-슈타이너 계의 동형류의 수	1	1	1	1	1	4	1054163

예

다음과 같은 (2,4,8)-블록 설계를 생각하자.

$X=\{0,1,2,3,4,5,6,7\}$

${\mathcal {B}}=\{0123,0124,0156,0257,0345,0367,0467,1267,1346,1357,1457,2347,2356,2456\}$

그렇다면,

• 총 8개의 점이 있다 ($n=8$).
• 모든 블록의 크기는 4이다 ($k=4$).
• 블록의 수는 14이다 ($\lambda _{0}=14$).
• 임의의 한 점은 7개의 블록에 포함된다 ($\lambda _{1}=7$).
• 임의의 두 점은 3개의 블록에 포함된다 ($\lambda _{2}=3$).

파노 평면

파노 평면 (유한체 $\mathbb {F} _{2}$ 위의 사영 평면) $\mathbb {P} _{\mathbb {F} _{2}}^{2}$을 생각하자.

여기서, 각 선을 블록으로 생각하자. 즉, 다음과 같은 블록 설계를 생각하자.

$X=\{1,2,3,4,5,6,7\}$

${\mathcal {B}}=\{123,145,167,246,257,347\}$

이는 $(2,3,7)$-슈타이너 계를 이룬다.

• 총 7개의 점이 있다 ($n=7$).
• 모든 블록은 정확히 세 개의 점을 갖는다 ($k=3$).
• 블록의 수는 7이다 ($\lambda _{0}=7$).
• 모든 점은 정확히 세 개의 블록에 포함된다 ($\lambda _{1}=3$).
• 임의의 서로 다른 두 점이 주어졌을 때, 이를 포함하는 블록은 정확히 한 개이다. ($\lambda _{2}=1$).

이진 골레 부호

 이 부분의 본문은 이진 골레 부호입니다.

이진 골레 부호 $G_{24}\subseteq \mathbb {F} _{2}^{24}$는 759개의 옥타드(값이 1인 성분이 8개인 벡터)를 가지며, 각 옥타드를 $\{1,2,\dotsc ,24\}$의, 크기 8의 부분 집합으로 여길 수 있다. 이에 따라, 이진 골레 부호의 옥타드의 집합은 (5,8,24)-슈타이너 계를 이룬다. 이는 비트 설계(Witt設計, 영어: Witt design)라고 불린다.

아다마르 설계

 이 부분의 본문은 아다마르 설계입니다.

$4m\times 4m$ 아다마르 행렬이 주어졌으며, 그 첫 열과 첫 행이 모두 1로 구성돼 있다고 하자. 그렇다면, 첫 열과 첫 행을 제거하고, 나머지 성분 가운데 −1을 0으로 치환한 뒤, 이를 어떤 정사각 블록 설계의 결합 행렬로 해석할 수 있다. 이를 아다마르 설계라고 하며, 이는 $\lambda _{2}=m-1$인 $(2,2m,4m-1)$-블록 설계이다.

자명한 블록 설계

임의의 유한 집합 $X$ 및 $\varnothing \neq {\mathcal {B}}\subseteq \operatorname {Pow} _{k}(X)$에 대하여, $(X,{\mathcal {B}})$는 $\lambda _{0}=|{\mathcal {B}}|$인 $(0,k,|X|)$-블록 설계를 이룬다.

임의의 유한 집합 $X$ 및 양의 정수 $1\leq k\leq |X|$에 대하여, $(X,\operatorname {Pow} _{k}(X))$는 $\textstyle (k,k,|X|)$-블록 설계를 이루며, 이 경우

$\lambda _{i}={\binom {|X|-i}{k-i}}\qquad (0\leq i\leq k)$

이다. 이는 $t=k$이므로 정사각 블록 설계이며, $\lambda _{t}=1$이므로 슈타이너 계이다.

역사

웨슬리 스토커 바커 울하우스

야코프 슈타이너

1844년에 영국의 보험계리인 웨슬리 스토커 바커 울하우스(영어: Wesley Stoker Barker Woolhouse, 1809~1893)가 자신이 편집자로 있던 잡지 《레이디즈 앤드 젠틀먼즈 다이어리》(영어: Lady’s and Gentleman’s Diary)에서 블록 설계에 대한 퍼즐을 제시하였다. 그 전문(全文)은 다음과 같다.

“	XV. 상금 문제 (1733번). 편집부 출제. $n$개의 기호들로 만들 수 있는, 각각 $p$개의 기호를 갖는 조합들의 수를 계산하라. 다만, 임의의 $q$개의 기호들의 조합은 두 개 이상에 속할 수 없다. XV. Oʀ PRIZE QUEST. (1733) ; by the Editor. Determine the number of combinations that can be made out of n symbols, p symbols in each; with this limitation, that no combination of q symbols, which may appear in any one of them shall be repeated in any other.	”
	—

이는 현대적 용어로는 $(q,p,n)$-슈타이너 계를 다루는 것이다.

이후 이 문제는 1847년에 영국의 잉글랜드 성공회 사제 토머스 페닝턴 커크먼(영어: Thomas Penyngton Kirkman, 1806~1895)이 해결하였다. 그러나 이들의 논문은 크게 관심을 불러일으키지 못했다.

이후 울하우스와 커크먼과 독자적으로 야코프 슈타이너가 1853년에 블록 설계에 대한 논문을 출판하였다. 이후 그의 이름을 따 $\lambda _{t}=1$인 $t$-블록 설계는 “슈타이너 계”로 불리게 되었다.

비트 설계는 1931년에 로버트 대니얼 카마이클이 최초로 발견하였으며, 에른스트 비트가 1938년에 마티외 군을 연구하던 도중 재발견하였다.

피셔 부등식은 로널드 피셔가 1940년에 증명하였다.

참고 문헌

• Street, Anne Penfold; Street, Deborah J. (1987). 《Combinatorics of experimental design》 (영어). Clarendon Press. ISBN 0-19-853256-3. 
• Lindner, Charles C.; Rosa, Alexander (1978). “Steiner quadruple systems — a survey”. 《Discrete Mathematics》 (영어) 22 (2): 147-181. doi:10.1016/0012-365X(78)90122-X. 

외부 링크

• “Block design”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Symmetric design”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Pairwise balanced design”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Design with mutually orthogonal resolutions”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Partially balanced incomplete block design”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Balanced incomplete block design”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Affine design”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Steiner system”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Block design”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Symmetric block design”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Steiner system”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Steiner triple system”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Steiner quadruple system”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Fisher's block design inequality”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Bruck-Ryser-Chowla theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Block design”. 《nLab》 (영어). 
• “Steiner system”. 《nLab》 (영어). 
• 이철희. “슈타이너 시스템 S(5, 8, 24)”. 《수학노트》. 
• “DesignTheory.org” (영어). Queen Mary University of London.