Kwangmin Kim - MOLS 의 최대 수 — \(n

1 정리: 최대 MOLS 수

Theorem

$n \times n$ Latin square 의 mutually orthogonal set 의 최대 크기는 $n - 1$.

1.1 증명 sketch

$n \times n$ Latin square 의 row 와 column 을 1, 2, …, $n$ 으로 정렬. 각 직교 Latin Square 의 첫 행을 $1, 2, \ldots, n$ 으로 정규화 (standardize).

직교 조건에서 두 squares 의 첫 column 의 두 번째 행 값이 일치하지 못함. 따라서 가능한 값의 수는 $n - 1$ (자기 자신 제외).

자세한 증명은 finite projective plane 이론 (Bose, 1938) 참고.

직관: $n - 1$ 의 의미

$n \times n$ Latin square 의 첫 행이 $(1, 2, ..., n)$ 으로 표준화 → 둘째 행은 $(1, ..., n)$ 의 derangement (모든 위치에서 첫 행과 다름).

$M$ 개의 MOLS 가 직교라면 첫 column 의 둘째 행 값들이 모두 다름. 그 값은 $\{1, 2, ..., n\}$ 중 자기 자신 (= 첫 행의 첫 원소) 제외 → 최대 $n - 1$.

즉 MOLS 의 최대 수가 $n - 1$.

2 도달 가능 조건

정의: Complete Set of MOLS

$n - 1$ 개 MOLS 가 모두 직교 → Complete Set of MOLS 또는 Finite Projective Plane of order $n$.

$n - 1$ MOLS 가 존재 ⟺ finite projective plane of order $n$ 이 존재.

$n$	$n-1$ MOLS 존재?	비고
2	1 (자명)
3	✓	$GF(3)$
4	✓ ($GF(4)$)	3 MOLS
5	✓	$GF(5)$
6	❌	1 MOLS 만
7	✓	$GF(7)$
8	✓	$GF(8)$
9	✓	$GF(9)$
10	?	2 MOLS 발견, 9 MOLS 의 존재 미해결
11	✓	$GF(11)$
12	?	5 MOLS 알려짐

$n = $ prime power 에서는 항상 $n - 1$ MOLS 도달 (Galois Field 기반 구성).

3 $GF(p^k)$ 기반 구성

$n = p^k$ (prime power). $GF(n)$ 의 nonzero 원소를 $\alpha_1, \ldots, \alpha_{n-1}$.

$L_a$ ($a$ 번째 Latin Square) 의 cell $(i, j)$ 값: \[ L_a(i, j) = \alpha_a \cdot i + j \pmod{GF(n)} \]

이 $n - 1$ Latin squares 가 mutually orthogonal.

직관: GF(n) 의 자동 직교성

$GF(n)$ 의 산술이 자동으로 직교성 보장. 임의의 두 $a, a' \in GF(n)^*$ ($a \ne a'$):

두 Latin squares $L_a, L_{a'}$ 가 직교 ⟺ 모든 cell 에서 $(L_a, L_{a'})$ 가 unique pair.

$GF(n)$ 의 cancellation 정리: \[ \alpha_a i + j = \alpha_{a'} i' + j' \quad \text{and} \quad i \cdot \text{anything} = i' \cdot \text{anything} \implies (i, j) = (i', j') \]

이는 GF 의 group 구조에서 자동.

4 $n = 4$ 의 3 MOLS — $GF(4)$

$GF(4) = \{0, 1, \alpha, \beta\}$, $\alpha + \beta = 1$, $\alpha\beta = 1$.

$L_a$ 의 cell $(i, j)$ 값: $a \cdot i + j \pmod{GF(4)}$.

$L_1, L_\alpha, L_\beta$ 가 3 MOLS:

L_1:                  L_α:                  L_β:
0 1 α β               0 1 α β               0 1 α β
1 0 β α               α β 0 1               β α 1 0
α β 0 1               β α 1 0               1 0 β α
β α 1 0               1 0 β α               α β 0 1

직교 검증: 각 cell 에서 $(L_1, L_\alpha, L_\beta)$ triple 이 unique.

5 $n = 6$ — 특이성

$n = 6 = 2 \times 3$ 은 prime power 가 아닌 합성수. $GF(6)$ 가 존재하지 않음 (field 정리).

Tarry (1900) 가 brute force 로 두 직교 Latin Square 가 없음을 증명.

함정: $n = 6$ 의 조합론적 특이성

$n = 6$ 은 단순한 산술적 이유가 아닌 deep 한 조합론적 특이성. $6 \times 6$ 의 Latin Square 는 매우 많지만 (~$10^7$), 어느 두 개도 직교 안 됨.

이는 Schoenfließ-Burnside 의 group theoretical 결과와 연결.

→ Euler’s 36 officers problem 이 풀리지 않은 이유.

6 $n = 10$ — 미해결

$n = 10$: 2 MOLS 알려짐 (Parker 1959). 그러나 $n - 1 = 9$ MOLS 의 존재 여부 미해결.

이는 finite projective plane of order 10 의 존재 문제. 현재까지 강력한 거부 증거 (Lam 등 1989) 있지만 100% 확정 아님.

7 가정과 한계

$n$ prime power: $n-1$ MOLS 존재 보장.
$n$ 합성수: 일부 $n$ 에 부족.
$n = 6$ 의 특이성: 독특한 사례.
컴퓨터 검색의 한계: 큰 $n$ 에서.

8 Resolvable BIB 와의 관계

직관: MOLS = Resolvable BIB

Complete set of MOLS 는 finite projective plane.

Finite projective plane of order $n$ 은 BIB $(n^2 + n + 1, n^2 + n + 1, n+1, n+1, 1)$.

→ $n - 1$ MOLS = $(n^2 + n + 1)$ 처치의 resolvable BIB.

MOLS 와 BIB 는 같은 조합론적 객체의 다른 시각.

9 가설 적용

9.1 사례 — $n = 5$ Hyper-Graeco-Latin

$n = 5$, 4 MOLS 가능 (5-1).

5×5 격자에 5 차원 처치: - 행 = 5 wells. - 열 = 5 시점. - $L_1$ = 시약 종류. - $L_2$ = 농도. - $L_3$ = pH. - $L_4$ = 온도.

총 25 cells 로 6 차원 (행, 열, 4 처치) 의 직교 통제. 정보 효율 매우 높음.

10 본 시리즈

G-MON6-0  개관
G-MON6-1  Definition + Maximum Number  ← 현재 글
G-MON6-2  Construction
G-MON6-3  Euler's Conjecture

11 관련 주제

선행 지식

G-MON6-0: 개관

후속 주제

12 더 읽을 거리

Bose, R. C. (1938). “On the application of the properties of Galois fields to the problem of construction of hyper-Graeco-Latin squares.” Sankhyā 3: 323-338.
Tarry, G. (1900). “Le problème de 36 officiers.” Compte Rendu de l’Association Française pour l’Avancement des Sciences 1: 122-123.
Lam, C. W. H. (1989). “How reliable is a computer-based proof?” Mathematical Intelligencer 12(1): 8-12 — $n = 10$ 의 컴퓨터 증명.
Stinson, D. R. (2003). “Combinatorial Designs.” Springer.

MOLS 의 최대 수 — \(n - 1\) 이라는 상한

1 정리: 최대 MOLS 수

1.1 증명 sketch

2 도달 가능 조건

3 \(GF(p^k)\) 기반 구성

4 \(n = 4\) 의 3 MOLS — \(GF(4)\)

5 \(n = 6\) — 특이성

6 \(n = 10\) — 미해결

7 가정과 한계

8 Resolvable BIB 와의 관계

9 가설 적용

9.1 사례 — \(n = 5\) Hyper-Graeco-Latin

10 본 시리즈

11 관련 주제

12 더 읽을 거리