블록 설계

조합론에서 **블록 설계**(block設計, 블록 디자인)는 같은 크기의 일련의 부분 집합들이 주어져 있는 유한 집합이다.언어=en언어=en언어=en언어=en 이 경우, 이러한 부분 집합을 **블록**(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系, 스타이너 시스템)라고 한다. 보통, \lambda_t=1인 (t,k,n)-블록 설계 (X,\mathcal B)는 \operatorname S(t,k,n)로 표기된다.
## 일반적 결합 도식 속의 블록 설계
위 정의는 결합 도식의 개념을 통해 일반화된다.언어=en언어=en2483–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_aE_b=\delta_{ab}E_a :\sum_{a\in A}E_a=1_{\mathcal A} 를 정의할 수 있다. 특히, :E_0=\frac1{|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\le i\le t가 주어졌을 때, i개의 점들을 모두 포함하는 블록의 개수는 정확히 \lambda_i이다. 특히, i=0일 경우, * 블록의 수는 \textstyle\lambda_0 = \lambda_t \binom nt / \binom kt이다. 이에 따라, 모든 (t,k,n)-블록 설계는 임의의 0\le t'\le t에 대하여 (t',k,n)-블록 설계이다.
## 존재의 필요 조건
**피셔 부등식**(Fisher不等式, Fisher’s inequality)에 따르면, 임의의 (2,k,n)-블록 설계 (X,\mathcal B)에 대하여, 다음이 성립한다. :|X| \ge \lambda_0 :k \ge \lambda_1 (X\lambda_1=k\lambda_0이므로, 두 조건은 사실 동치이다.) 이 부등식을 포화시키는 블록 설계, 즉 점의 수가 블록의 수와 같은 2-블록 설계를 **정사각 블록 설계**(正四角block設計, square block matrix) 또는 **대칭 블록 설계**(對稱block設計, symmetric block design)라고 한다. 보다 일반적으로, 임의의 (t,k,n)-블록 설계 (X,\mathcal B)에 대하여, 다음이 성립한다.언어=en :\lambda_0 \ge \binom n{\lfloor t/2\rfloor} **브룩-라이저-차울라 정리**(Bruck-Ryser-चावला定理, Bruck–Ryser–Chowla theorem)에 따르면,언어=en언어=en 임의의 (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)\ne(0,0,0)가 존재한다.
## 개수
작은 크기의 (t=2, k=3, n)-슈타이너 계의 동형류들의 수들은 다음과 같다. A30129 {| class=wikitable ! n | 1 || 3 || 7 || 9 || 13 || 15 || 19 | rowspan=2 | … |- ! (2,3,n)-슈타이너 계의 동형류의 수 | 1 || 1 || 1 || 1 || 2 || 80 || 11084874829 |} 작은 크기의 (t=3, k=4, n)-슈타이너 계의 동형류들의 수들은 다음과 같다. A51390 {| class=wikitable ! n | 1 || 2 || 4 || 8 || 10 || 14 || 16 | rowspan=2 | … |- ! (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,356\\} 이는 (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\ne\mathcal B\subseteq\operatorname{Pow}_k(X)에 대하여, (X,\mathcal B)는 \lambda_0=|\mathcal B|인 (0,k,|X|)-블록 설계를 이룬다. 임의의 유한 집합 X 및 양의 정수 1\le k\le|X|에 대하여, (X,\operatorname{Pow}_k(X))는 \textstyle (k, k, |X|)-블록 설계를 이루며, 이 경우 :\lambda_i=\binom{|X|-i}{k-i}\qquad(0\le i\le k) 이다. 이는 t=k이므로 정사각 블록 설계이며, \lambda_t=1이므로 슈타이너 계이다.
# 역사
웨슬리 스토커 바커 울하우스 야코프 슈타이너 1844년에 영국의 보험계리인 웨슬리 스토커 바커 울하우스(Wesley Stoker Barker Woolhouse, 1809~1893)가 자신이 편집자로 있던 잡지 《레이디즈 앤드 젠틀먼즈 다이어리》(Lady’s and Gentleman’s Diary)에서 블록 설계에 대한 퍼즐을 제시하였다.언어=en 그 전문(全文)은 다음과 같다. 이는 현대적 용어로는 (q,p,n)-슈타이너 계를 다루는 것이다. 이후 이 문제는 1847년에 영국의 잉글랜드 성공회 사제 토머스 페닝턴 커크먼(Thomas Penyngton Kirkman, 1806~1895)이 해결하였다.언어=en 그러나 이들의 논문은 크게 관심을 불러일으키지 못했다. 이후 울하우스와 커크먼과 독자적으로 야코프 슈타이너가 1853년에 블록 설계에 대한 논문을 출판하였다.언어=de 이후 그의 이름을 따 \lambda_t=1인 t-블록 설계는 “슈타이너 계”로 불리게 되었다. 비트 설계는 1931년에 로버트 대니얼 카마이클이 최초로 발견하였으며,언어=en 에른스트 비트가 1938년에 마티외 군을 연구하던 도중 재발견하였다.언어=de 피셔 부등식은 로널드 피셔가 1940년에 증명하였다.언어=en