Kwangmin Kim - Pairwise Balanced Design 과 Euler 추측의 거짓

1 정의

정의: Pairwise Balanced Design (PBD)

처치 (요소) 의 집합 \(V\) (\(|V| = v\)) 와 블록의 집합 \(\mathcal{B}\) 에 대해,

각 블록 \(B \in \mathcal{B}\) 가 \(V\) 의 부분집합.
임의의 두 처치 쌍 \(\{x, y\} \subseteq V\) 가 정확히 \(\lambda\) 개 블록에 같이 등장.

블록 크기는 다양해도 무방 (이것이 Balanced Incomplete Block 의 일반화).

PBD 는 BIB (블록 크기 일정) 의 일반화로, \(n \times n\) MOLS 의 존재 문제를 푸는 도구로 사용된다.

2 Euler 의 추측 (1782)

Leonhard Euler 는 1782 년 “36 명 장교 문제 (36 officers problem)” 를 제기했다. \(6 \times 6\) 격자에 6 개 군대 × 6 개 계급 (\(6 \times 6 = 36\) 명) 의 장교를 배치하되, 각 행과 각 열에 각 군대가 한 번씩, 각 계급이 한 번씩 등장하도록 — 즉 \(6 \times 6\) 의 직교 Latin Square 쌍을 찾는 문제.

Euler 는 해를 찾지 못했고 다음을 추측했다:

Euler’s Conjecture (1782)

\(n \equiv 2 \pmod 4\) (\(n = 6, 10, 14, 18, 22, 26, \ldots\)) 인 경우, 두 개의 직교 Latin Square 가 존재하지 않는다.

이 추측은 \(n - 1\) 개 MOLS 의 존재 문제와 직결된다 (G-MON6-1 의 상한 \(n-1\) 이 최소 1 개로 떨어진다는 주장).

3 \(n = 6\) — Tarry 의 brute force 증명 (1900)

Gaston Tarry (1900) 는 \(6 \times 6\) Latin Square 의 모든 표준형을 손으로 분류하여, 어떤 두 Latin Square 도 서로 직교하지 않음을 증명했다.

직관: 왜 \(n = 6\) 만 어려운가

\(GF(n)\) 이 존재하는 prime power \(n = p^k\) 에서는 자동으로 \(n - 1\) MOLS 가 만들어진다 (G-MON6-1). \(n = 6 = 2 \times 3\) 은 prime power 가 아니다. \(GF(2)\) 와 \(GF(3)\) 의 직접 곱 (direct product) 으로 만들 수 있는 MOLS 수는 \(\min(1, 2) = 1\) — 직교 쌍을 못 만든다.

실제로 \(6 \times 6\) 의 모든 가능한 Latin Square 쌍을 검색해도 직교 쌍이 없다. 이는 \(n = 6\) 의 조합론적 특이성으로, 단순한 산술적 이유가 아니라 그룹 이론적 deep 한 구조에 근거한다.

4 \(n = 10, 14, 22, \ldots\) — Bose-Shrikhande-Parker (1959)

Euler 의 추측은 약 180 년간 정설이었다. Raj Chandra Bose, S. S. Shrikhande, E. T. Parker 는 1959 년 다음을 증명했다:

Theorem (Bose-Shrikhande-Parker, 1959)

\(n \equiv 2 \pmod 4\) 이고 \(n > 6\) 인 모든 \(n\) 에 대해, 두 개 이상의 직교 Latin Square 가 존재한다.

따라서 Euler 의 추측은 \(n = 6\) 을 제외하고 거짓.

이는 20 세기 조합론의 가장 유명한 결과 중 하나. New York Times 1 면 기사로 보도되었다.

4.1 증명의 핵심 아이디어

Bose 등은 Pairwise Balanced Design (PBD) 을 통해 큰 MOLS 를 작은 MOLS 들로부터 구성하는 cofactor 방법 을 개발했다.

핵심 정리 (간략):

\(v\) 가 PBD 로 분해 가능하고 각 블록 크기 \(k\) 에 대해 \(k - 1\) MOLS 가 존재하면, \(v - 1\) MOLS 가 존재한다.

이 도구로 \(n = 22\) 에 대해 두 직교 Latin Square 의 명시적 구성을 제시. 이후 다른 \(n\) 에 일반화.

5 \(n = 22\) 의 직접 구성 (sketch)

\(22 = 5 \times 4 + 2\). 22 개 처치를 5 그룹 × 4 + 2 의 PBD 로 분해. 각 그룹 내 MOLS 존재 + cofactor 결합 → 22 차원 두 직교 Latin Square.

자세한 구성은 Bose-Shrikhande-Parker (1960) “Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler’s conjecture” 참고.

6 \(n = 14, 26\) 의 경우

비슷한 PBD 분해. \(n = 14 = 7 \times 2\) — \(GF(7)\) 의 6 MOLS 와 trivial 부분의 결합.

7 36 Officers Problem 의 현대 의의

Quantum information 분야에서는 이 문제가 양자역학의 “absolutely maximally entangled states” 와 연결된다 (2022 년 Rains 등의 연구). 고전 조합론에서 풀리지 않은 \(n = 6\) 의 양자 버전은 “quantum solution exists” 가 증명되어 학계의 큰 화제가 되었다.

이는 정통 DOE 의 결과가 양자 물리·암호 등 현대 분야로 확장되는 사례.

8 Pairwise Balanced Design 의 일반 형태

직관: PBD 와 BIB 의 관계

BIB 는 블록 크기가 모두 일정한 PBD 의 특수 형태. 일반 PBD 는 큰 블록과 작은 블록을 섞어 설계의 자유도를 늘림.

예: \(v = 9\) 처치, 블록 크기가 \(\{3, 4\}\) 의 혼합. 어떤 처치 쌍은 크기 3 블록에서, 다른 쌍은 크기 4 블록에서 만남. 이 비균등이 정밀도 trade-off 를 만들지만, 가능한 BIB 가 존재하지 않을 때 유용하다.

9 산업 실험에서의 활용

분야	활용
농학	비균등 plot 크기의 품종 비교
임상시험	일부 환자에 더 많은 약물 시험
식품 평가	패널 별로 다른 시식 수
산업 screening	블록 크기 제약이 다른 단계별 실험

PBD 는 BIB 가 안 될 때의 대안. 분석은 일반 mixed model 로 자동.

10 가정과 한계

블록 크기 균등 가정: BIB 와 같은 단순 분석 안 됨.
추정 정밀도 비균등: 처치 쌍별 다른 분산.
존재 조건의 복잡성: PBD 의 존재가 일반적으로 더 복잡한 조합론.
컴퓨터 보조 필수: 큰 \(v\) 에 대한 PBD 검색.

11 Euler-BSP 의 역사적 의의

수학 외부의 영향력: 36 officers 문제는 수학 분야 밖의 일반인에게도 알려진 매우 드문 조합론 결과.
권위 있는 추측의 거짓: 200 년간 정설이었던 추측이 거짓 → 직관에 의존하지 말고 증명·반례 검색하라는 교훈.
컴퓨터 검색의 보조 (간접): 직접적 컴퓨터 증명은 아니지만 큰 사례 검증에 컴퓨터 사용 (Tarry 의 손계산을 재현).
현대 양자 정보로 확장: 36 officers 의 quantum 버전이 2022 년 해결.

12 MOLS 의 응용 — 디지털 실험

A/B test 의 multivariate testing 에서 여러 변수를 직교 통제하기 위해 MOLS 를 사용 가능. 예: 4 변종 UI × 4 가지 발송 시간 × 4 가지 사용자 세그먼트 의 16 cells 에 4 가지 content 를 직교 배정.

이는 Plackett-Burman 의 정수형 형태이며, 큰 표본 환경에서 효율적인 선별 도구.

13 MON Ch.6 시리즈 정리

G-MON6-0  Orthogonal Latin Squares 개관
G-MON6-1  Definition + Maximum Number ($n - 1$ 상한)
G-MON6-2  Construction (Order 4, 12) — GF(p^k) 기반
G-MON6-3  Pairwise Balanced + Euler's Conjecture  ← 현재 글 (마지막)
    ↓
G-MON7 (Bio-assays / Response Surface)

14 관련 주제

선행 지식

후속 주제

G-MON7 — Bio-assays / Response Surface (작성 예정)

다른 카테고리 연결

Math — Linear Algebra (placeholder) — finite field, group theory
Statistics — 조합론적 실험설계 (placeholder)

15 더 읽을 거리

Bose, R. C., Shrikhande, S. S., & Parker, E. T. (1960). “Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler’s conjecture.” Canadian Journal of Mathematics.
Beth, T., Jungnickel, D., Lenz, H. (1999). “Design Theory” (2 vols), Cambridge University Press — 표준 reference.
Stinson, D. R. (2003). “Combinatorial Designs: Constructions and Analysis.” Springer.