Kwangmin Kim - BIB 의 구성 방법 — 차분 집합·시리즈·기하학적 접근

1 Difference Set 방법

정의: \((v, k, \lambda)\) Difference Set

집합 \(D = \{d_1, d_2, \ldots, d_k\} \subseteq \mathbb{Z}_v\) 에서 모든 비-zero 차이 \(d_i - d_j\) 가 정확히 \(\lambda\) 번 등장.

이 set 의 cyclic shifts 가 \(v\) 개 BIB block 을 생성.

1.1 예시 — \((7, 3, 1)\) Difference Set

\(D = \{1, 2, 4\}\) in \(\mathbb{Z}_7\).

차이: - \(1 - 2 = -1 \equiv 6\) - \(1 - 4 = -3 \equiv 4\) - \(2 - 1 = 1\) - \(2 - 4 = -2 \equiv 5\) - \(4 - 1 = 3\) - \(4 - 2 = 2\)

비-zero 잔류: \(\{1, 2, 3, 4, 5, 6\}\) — 각 1 번. ✓ (\(\lambda = 1\))

7 블록 생성: \(D, D+1, D+2, \ldots, D+6\) (cyclic shifts).

Block 1: {1, 2, 4}
Block 2: {2, 3, 5}
Block 3: {3, 4, 6}
Block 4: {4, 5, 0}
Block 5: {5, 6, 1}
Block 6: {6, 0, 2}
Block 7: {0, 1, 3}

이 BIB 는 Fano plane (finite projective plane PG(2, 2)) 와 동치.

직관: Cyclic Shift 의 자동 균형

\(\mathbb{Z}_v\) 의 cyclic structure 가 BIB 의 균형을 보장.

\(D\) 의 비-zero 차이가 모든 잔류류 \(\{1, \ldots, v-1\}\) 를 동일 횟수 cover → cyclic shifts 가 모든 처치 쌍을 동일 횟수 같이 등장시킴.

이는 Fourier transform 의 기하학적 정수.

2 Finite Geometry 기반 구성

2.1 Projective Geometry PG(\(d\), \(s\))

\(s^d + s^{d-1} + \ldots + 1\) 점, 각 line 에 \(s + 1\) 점, 각 점 쌍이 정확히 1 line 에 등장.

\(d, s\)	\(v = (s^{d+1}-1)/(s-1)\)	\(k = s+1\)	BIB
(2, 2)	7	3	\((7, 7, 3, 3, 1)\)
(2, 3)	13	4	\((13, 13, 4, 4, 1)\)
(2, 4)	21	5	\((21, 21, 5, 5, 1)\)
(2, 5)	31	6	\((31, 31, 6, 6, 1)\)
(3, 2)	15	7	\((15, 35, 7, 3, 1)\) — line 의 부분집합

PG 가 자동으로 BIB 산출.

2.2 Affine Geometry AG(\(d\), \(s\))

\(s^d\) 점, parallel lines, 각 line 에 \(s\) 점.

PG 와 비슷한 BIB 생성.

3 Hadamard Matrix 기반

\(2^k - 1\) 처치, \(2^{k-1}\) 블록 크기 BIB. Hadamard matrix 로 구성.

\(H_{4t}\) Hadamard 가 BIB \((4t-1, 4t-1, 2t-1, 2t-1, t-1)\) 산출.

\(t\)	BIB 모수
2	\((7, 7, 3, 3, 1)\) — Fano
3	\((11, 11, 5, 5, 2)\)
4	\((15, 15, 7, 7, 3)\)
5	\((19, 19, 9, 9, 4)\)

4 \((11, 11, 5, 5, 2)\) Difference Set

\(\mathbb{Z}_{11}\) 의 quadratic residues: \(\{1, 3, 4, 5, 9\}\) (\(x^2 \mod 11\)).

이는 \((11, 5, 2)\) difference set. 11 cyclic shifts 가 BIB 산출.

Block 1: {1, 3, 4, 5, 9}
Block 2: {2, 4, 5, 6, 10}
Block 3: {3, 5, 6, 7, 0}
...

5 Python 코드

import numpy as np
from itertools import combinations

# Difference set 검증 — (7, 3, 1)
D = {1, 2, 4}
v = 7
diffs = []
for d1 in D:
    for d2 in D:
        if d1 != d2:
            diffs.append((d1 - d2) % v)

from collections import Counter
counts = Counter(diffs)
print(f"Difference counts: {dict(counts)}")
print(f"All non-zero have count {len(D)*(len(D)-1) // (v-1)}? "
      f"{all(c == 1 for c in counts.values())}")

# BIB cyclic shifts 생성
print("\nBIB blocks (cyclic from D = {1, 2, 4}):")
for shift in range(v):
    block = sorted([(d + shift) % v for d in D])
    print(f"  Block {shift+1}: {block}")

# (11, 5, 2) BIB — quadratic residues in Z_11
QR = sorted({(x * x) % 11 for x in range(1, 11)})
print(f"\n(11, 5, 2) BIB — Quadratic residues mod 11: {QR}")

# 검증
v = 11
D = set(QR)
diffs = []
for d1 in D:
    for d2 in D:
        if d1 != d2:
            diffs.append((d1 - d2) % v)
counts = Counter(diffs)
print(f"All non-zero have count {len(D)*(len(D)-1) // (v-1)}? "
      f"{all(c == 2 for c in counts.values() if c)}")

6 Computer-Aided BIB Search

큰 \(v\) 에 대해 BIB 검색은 컴퓨터 알고리즘:

Coordinate exchange: 시작 design 에서 cell swap 으로 균형 검색.
Simulated annealing: stochastic 검색.
Backtracking: exhaustive 검색.

R crossdes, agricolae. Python pyDOE2. SAS PROC OPTEX.

7 가정과 한계

차분 집합 존재 필요: 모든 \((v, k, \lambda)\) 에 대해 존재 X.
순환 구조: cyclic 이 아닌 BIB 는 다른 방법 (geometry, Hadamard).
컴퓨터 자동 검색: 큰 \(v\) 에 표준.
Fisher’s inequality: \(b \ge v\).

8 응용

각 BIB 모수의 응용:

BIB	응용
\((7, 7, 3, 3, 1)\)	임상 7 약 × 환자 3 시점
\((11, 11, 5, 5, 2)\)	농학 11 품종 × plot 5
\((13, 13, 4, 4, 1)\)	식품 13 레시피 × 패널 4
\((16, 20, 5, 4, 1)\)	교육 16 항목 × 4 시험
\((25, 30, 6, 5, 1)\)	산업 25 공정 × 5 station

9 ML 매핑

매핑: ML 의 BIB 모델 평가

ML 에서 많은 모델 비교 (예: 13 모델) 인데 자원 (예: 4 GPU) 제약:

$(13, 13, 4, 4, 1)$ BIB:
- 13 모델 × 13 evaluation rounds.
- 각 round 에 4 모델 동시 평가.
- 각 쌍 정확히 1 번 같이 평가.

이는 균형 systematic 모델 비교. random sampling 보다 균형 ↑.

10 본 시리즈

G-MON5-0  개관
G-MON5-1  BIB 도입
G-MON5-2  BIB Construction  ← 현재 글
G-MON5-3  BIB Analysis
G-MON5-4  Youden + Lattice
G-MON5-5  PBIB
G-MON5-6  Recovery + Optimality

11 관련 주제

선행 지식

후속 주제

G-MON5-3: BIB Analysis

다른 카테고리 연결

G-MON6-3: Euler’s Conjecture — finite geometry 와 combinatorial design.

12 더 읽을 거리

Hanani, H. (1975). “Balanced incomplete block designs and related designs.” Discrete Mathematics 11(3): 255-369 — BIB construction 종합 reference.
Hall, M. (1986). “Combinatorial Theory” (2nd ed). Wiley.
Beth, T., Jungnickel, D., Lenz, H. (1999). “Design Theory” (2 vols, 2nd ed). Cambridge University Press.
Stinson, D. R. (2003). “Combinatorial Designs: Constructions and Analysis.” Springer.
Colbourn, C. J., Dinitz, J. H. (eds.) (2007). “Handbook of Combinatorial Designs” (2nd ed). CRC Press.