직교 라틴 방진

3. 역사

조선 시대의 수학자 최석정(1646~1715)은 1710년에서 1715년 사이에 출판된 것으로 추정되는 수학서 《구수략》^[39]에서 서로 직교하는 9×9 라틴 방진 쌍과, 서로 직교하지는 않는 두 개의 10×10 라틴 방진을 제시했다.^[40] 최석정은 이 방진들에 각각 백자자수음양착종도(白子子數陰陽錯綜圖), 백자모수음양착종도(白子母數陰陽錯綜圖), 구구모수변궁양도(九九母數變宮陽圖)라는 이름을 붙였다. 이는 레온하르트 오일러보다 약 60년 앞선 연구 결과이다.

서양에서는 프랑스의 수학자 자크 오자낭(Jacques Ozanam^프랑스어, 1640~1718)이 1694년에 수학 퍼즐 책을 출판했으며,^[41] 1778년 장에티엔 몽튀클라(Jean-Étienne Montucla^프랑스어, 1725~1799)가 편집한 개정판에는 4×4 직교 라틴 방진에 해당하는 플레잉카드 퍼즐이 수록되었다.^[42] 이 퍼즐은 네 가지 슈트와 네 등급의 카드를 사용하여 각 행과 열에 모든 슈트와 등급이 한 번씩 나타나도록 배열하는 문제였다.

레온하르트 오일러는 1779년에 집필하여 1782년에 출판된 논문^[43]에서 직교 라틴 방진 문제를 본격적으로 다루었다. 그는 이 논문에서 방진의 원소를 라틴 문자로 표기한 데서 '라틴 방진'이라는 용어를 사용했고, 두 개의 직교하는 라틴 방진을 결합한 것을 라틴 문자와 그리스 문자를 써서 표현하며 '그레코라틴 방진'(Graeco-Latin square)이라고 불렀다. 오일러는 n이 4로 나누어 2가 남지 않는 수일 경우, 서로 직교하는 n×n 라틴 방진 쌍이 존재함을 증명하고, 이것이 직교 라틴 방진 쌍이 존재할 필요충분조건일 것이라고 추측했다. 오일러가 이 연구를 시작하게 된 계기는 6×6 크기의 직교 라틴 방진 쌍을 찾는 문제, 즉 '36 장교 문제'였으나, 그는 해답을 찾지 못하고 이러한 배열이 불가능할 것이라고 예상했다.

1901년, 프랑스의 수학자 가스통 타리(Gaston Tarry^프랑스어, 1843~1913)는 모든 가능한 경우를 검토하여 6×6 크기의 직교 라틴 방진 쌍이 존재할 수 없음을 엄밀하게 증명하여 오일러 추측의 일부(n=6인 경우)를 확인했다.^[44]

그러나 n이 4로 나누어 2가 남는 다른 경우(n=10, 14, ...)에 대한 오일러의 추측은 결국 틀린 것으로 밝혀졌다. 1959년에 인도의 수학자 라지 찬드라 보스와 샤라드찬드라 샨카르 슈리칸데(शरदचंद्र शंकर श्रीखंडे^hi, Sharadchandra Shankar Shrikhande^영어)는 22×22 크기의 직교 라틴 방진 쌍을 구성하는 데 성공했다.^[45] 곧이어 1960년, 보스와 슈리칸데는 미국의 수학자 어니스트 틸던 파커(Ernest Tilden Parker^영어, 1926~1991)와 함께 n=10인 경우를 포함하여 오일러가 불가능하다고 추측했던 n이 4로 나누어 2가 남는 형태의 모든 n ≥ 10 값에 대해 직교 라틴 방진 쌍이 존재함을 증명했다.^[46] 이로써 n=2와 n=6인 경우를 제외한 모든 자연수 n ≥ 3에 대해 n×n 직교 라틴 방진 쌍이 존재한다는 사실이 확립되었다.

3. 1. 36 장교 문제

매우 흥미로운 질문으로, 오랫동안 많은 사람들의 독창성을 발휘하게 했으며, 특히 조합 연구와 같은 새로운 분석 분야를 열어주는 듯한 다음과 같은 연구를 하게 했습니다. 이 질문은 6개의 서로 다른 연대에서 차출된 36명의 장교를 각 행(가로 및 세로)에 서로 다른 계급과 서로 다른 연대의 장교가 6명씩 있도록 정방형으로 배치하는 것입니다.
— 레온하르트 오일러

4. 상호 직교 라틴 방진의 수

같은 차수의 라틴 방진 집합에서, 임의의 두 방진을 골랐을 때 서로 직교한다면, 이 집합을 상호 직교 라틴 방진(Mutually Orthogonal Latin Squares) 집합이라고 부른다. 줄여서 MOLS라고 표기하며, 차수 ''n''을 명시할 때는 MOLS(''n'')으로 쓴다.

주어진 차수 ''n''에 대해, MOLS(''n'') 집합에 포함될 수 있는 방진의 최대 개수는 ''n'' − 1개이다.^[23] ''n'' − 1개의 방진으로 이루어진 MOLS(''n'') 집합을 완전 MOLS 집합이라고 부른다. 완전 MOLS 집합은 ''n''이 소수 또는 소수의 거듭제곱일 때 존재한다는 것이 알려져 있다. 이는 유한체를 이용한 구성을 통해 증명될 수 있다.^[31] 그러나 일반적인 ''n''에 대해 존재할 수 있는 MOLS의 최대 개수는 알려져 있지 않으며, 이는 조합론의 주요 연구 주제 중 하나이다.

크기가 ''n'' − 1인 MOLS(''n'') 집합, 즉 완전 MOLS 집합은 차수가 ''n''인 유한 아핀 평면과 동치 관계에 있다.^[24] 또한 모든 유한 아핀 평면은 같은 차수의 유한 사영 평면으로 유일하게 확장될 수 있으므로, 완전 MOLS 집합의 존재는 유한 사영 평면의 존재 문제와도 연결된다.^[25]

''n''이 소수 또는 소수 거듭제곱일 때는 완전 MOLS 집합, 즉 차수 ''n''의 유한 사영 평면이 존재한다. 다른 차수 ''n''에 대한 유한 사영 평면의 존재 여부는 일반적으로 알려져 있지 않다.^[24] 유한 사영 평면의 비존재에 대한 중요한 결과는 브루크-라이저-차울라 정리이다. 이 정리에 따르면, 만약 차수 ''n''의 유한 사영 평면이 존재하고 ''n'' ≡ 1 (mod 4) 또는 ''n'' ≡ 2 (mod 4) 라면, ''n''은 반드시 두 정수 제곱의 합으로 표현될 수 있어야 한다.^[26] 이 정리에 따라 차수가 6 또는 14인 유한 사영 평면은 존재하지 않는다. 따라서 MOLS(6)과 MOLS(14)는 완전 집합을 가질 수 없다 (즉, MOLS(6)은 최대 1개, MOLS(14)는 최대 13개가 아니다). 그러나 이 조건은 필요조건일 뿐 충분조건은 아니다. 예를 들어, ''n'' = 10은 1² + 3²으로 두 제곱수의 합이지만, 대규모 컴퓨터 탐색 결과 차수 10의 유한 사영 평면은 존재하지 않는다는 것이 밝혀졌다.^[27] 이는 곧 ''n''=10일 때 9개의 MOLS(10) 집합, 즉 완전 MOLS 집합이 존재하지 않음을 의미한다. 2020년 기준으로, 완전 MOLS 집합의 존재 여부가 결정되지 않은 가장 작은 차수는 12이다.^[24]

MOLS(''n'') 집합에 포함될 수 있는 방진의 최소 개수 또한 중요한 문제이다. ''n'' = 2 또는 ''n'' = 6일 때는 단 하나의 라틴 방진만이 존재하여 직교하는 쌍을 만들 수 없으므로 최소 개수는 1이다. 그 외의 모든 ''n'' > 6에 대해서는 최소 2개의 MOLS(''n'')이 존재한다는 것이 알려져 있다.

MOLS(''n'')의 최소 개수에 대한 하한은 MacNeish의 정리를 통해 얻을 수 있다. 정수 ''n''의 소인수분해가 $n\; =\; p\_1^\{\backslash alpha\_1\}p\_2^\{\backslash alpha\_2\}\backslash dots\; p\_r^\{\backslash alpha\_r\}$ (여기서 $p\_i$는 서로 다른 소수)일 때, MOLS(''n'')의 최소 개수는 $\backslash ge\; \backslash min\_\{i\}\; \backslash \{p\_i^\{\backslash alpha\_i\}\; -\; 1\; \backslash \}$ 이다. 이 정리는 ''n''이 소수 거듭제곱일 때는 정확한 값(''n''-1)을 주지만, 일반적인 합성수 ''n''에 대해서는 실제 최소 개수보다 훨씬 작은 값을 하한으로 제시하는 경우가 많다. 예를 들어, ''n'' ≡ 2 (mod 4) (즉, 소인수분해에서 2의 지수가 1인 경우)일 때, 이 정리는 하한으로 1을 주는데, 이는 ''n'' > 6인 경우 알려진 최소값 2보다 작다.

일반적인 합성수 ''n''에 대한 MOLS(''n'')의 정확한 최대 개수(N(''n'')으로 표기)는 대부분 알려져 있지 않다. ''n'' = 2부터 시작하는 N(''n'') 값은 1, 2, 3, 4, 1, 6, 7, 8, ... 이다.

N(''n'') 값이 알려지지 않은 가장 작은 ''n'' 값은 10이다. MOLS(10)은 최소 2개 존재한다는 것은 알려져 있으며 (MacNeish 정리는 하한 1을 줌), 차수 10의 유한 사영 평면이 존재하지 않으므로 최대 개수는 9개 미만, 즉 8개 이하이다. 현재까지 3개의 MOLS(10) 집합은 발견되지 않았으며, MOLS(10)의 정확한 최대 개수는 아직 미해결 문제이다.

충분히 큰 ''n''에 대해서는 MOLS(''n'')의 개수가 $n^\{1/14.8\}$보다 크다는 것이 증명되었다. 이는 ''n''이 커짐에 따라 MOLS의 개수도 무한히 커짐을 의미한다. 따라서 어떤 고정된 수 ''k''에 대해 N(''n'')=''k'' 인 ''n''은 유한개 뿐이다. 더욱이, 모든 ''n'' > 90에 대해 최소 6개의 MOLS(''n'')이 존재한다는 사실도 알려져 있다.

4. 1. 유한체 구성

5. 관련 개념

같은 차수를 가지는 라틴 방진들의 집합에서, 모든 방진 쌍이 서로 직교할 때 (즉, 그리스-라틴 방진을 형성할 때), 이 집합을 '''상호 직교 라틴 방진'''(Mutually Orthogonal Latin Squares, MOLS) 집합이라고 한다. 차수 n의 MOLS 집합은 보통 '''MOLS(n)'''으로 줄여서 표기한다.

예를 들어, 차수 4의 상호 직교 라틴 방진 집합, 즉 MOLS(4)의 한 예시는 다음과 같다.^[19]



그리고 MOLS(5)의 한 예시는 다음과 같다.^[20]



\qquad\begin{matrix}1&2&3&4&5\\5&1&2&3&4\\4&5&1&2&3\\3&4&5&1&2\\2&3&4&5&1\end{matrix}

\qquad\begin{matrix}1&2&3&4&5\\4&5&1&2&3\\2&3&4&5&1\\5&1&2&3&4\\3&4&5&1&2\end{matrix}

MOLS를 그리스-라틴 방진처럼 각 칸에 여러 기호를 함께 표시하는 "복합" 행렬 형태로 나타낼 수도 있다. 예를 들어 위의 MOLS(5) 예시는 다음과 같이 표현 가능하다.

하지만 MOLS를 표현할 때는 직교 배열 형태로 나타내는 것이 더 일반적이다.^[21]

지금까지 제시된 MOLS 예시에서는 모든 방진이 동일한 기호 집합(예: 숫자 1부터 n까지)을 사용했지만, 반드시 그럴 필요는 없다. 각 방진마다 완전히 다른 기호 집합을 사용할 수도 있다. 예를 들어, 아래 표는 4개의 MOLS(5)를 서로 다른 속성(배경색, 전경색, 텍스트, 글꼴 유형)을 사용하여 표현한 것이다. 이들 속성 중 임의의 두 가지를 선택하면 직교 라틴 방진 쌍을 형성한다.

위 표는 MOLS(5) 예시를 네 가지 속성으로 나타낸 것이다. 각 속성은 5개의 기호(값)를 가진다.

• 배경색: 검정, 진홍색, 청록색, 남색, 은색
• 전경색: 흰색, 빨간색, 라임, 파란색, 노란색
• 텍스트: 피오르, 턱, 가래, 큐비우트, 징키 (내부 링크 제거, 고유명사 아님)
• 글꼴 유형: 세리프, 산세리프, 고정폭 글꼴, 필기체, 슬래브 세리프

• 모든 방진의 행 순서를 동시에 바꾸는 것.
• 모든 방진의 열 순서를 동시에 바꾸는 것.
• 각 방진의 기호(항목)를 독립적으로 재배열하는 것.

• 직교 배열^[33]
• 그물 (특히 아핀 평면)^[24]
• 횡단 디자인^[37]
• 그래프 이론적 분할^[24]

5. 1. 직교 배열

위 표에서 'r'과 'c' 열은 각 라틴 방진에서의 행과 열 위치를 나타낸다. 특정 'r'과 'c' 값에 해당하는 행의 나머지 열(L₁, L₂, L₃)에는 각 MOLS에서 해당 (r, c) 위치에 있는 기호가 채워진다.

이 과정은 역으로도 가능하다. 즉, ''s'' ≥ 3인 직교 배열 OA(''s'', ''n'')가 주어졌을 때, 임의의 두 열을 각각 행('r')과 열('c') 정보로 사용하고, 나머지 ''s''-2개 열 각각을 이용하여 ''s''-2개의 MOLS(''n'')을 만들 수 있다.

더 일반적인 형태의 직교 배열은 서로 직교하는 라틴 입방체와 같이 MOLS 개념을 확장한 것을 나타낸다.

5. 2. 그물 (Net)

5. 3. 횡단 디자인 (Transversal Design)

• ''X''는 ''kn''개의 원소(점)로 이루어진 집합이다.
• ''G'' = {''G''₁, ''G''₂, ..., ''G''_''k''}는 ''X''를 분할하는 ''k''개의 부분 집합(그룹)들의 모임이며, 각 그룹 ''G_i''는 ''n''개의 원소를 가진다. (여기서 '그룹'은 대수학적 의미의 군을 뜻하지 않는다.)
• ''B''는 ''X''의 부분 집합(블록)들의 모임으로, 각 블록은 크기가 ''k''이며 모든 그룹 ''G_i''와 정확히 하나의 원소를 공유한다. 또한, 서로 다른 그룹에 속하는 임의의 두 원소는 정확히 λ개의 블록에서 함께 나타난다.

이 디자인의 다섯 개 그룹은 다음과 같이 구성된다.

5. 4. 그래프 이론

6. 응용

상호 직교 라틴 방진은 통계적 실험 설계, 토너먼트 일정 계획, 오류 정정 및 감지 코드 구성 등 매우 다양한 분야에서 활용된다. 수학자 오일러가 그레이코-라틴 방진(직교 라틴 방진 쌍)에 관심을 가진 계기는 마방진을 만들고자 했던 것이다. 또한, 프랑스 작가 조르주 페렉은 1978년 발표한 소설 인생 사용법의 구조를 10×10 크기의 그레이코-라틴 방진을 기반으로 설계하기도 했다.

참조

_[1] 논문 This has gone under several names in the literature, ''formule directrix'' (Euler), ''directrix'', ''1-permutation'', and ''diagonal'' amongst others.
_[2] 논문
_[3] 논문
_[4] 서적 The Art of Computer Programming https://books.google[...] Addison-Wesley
_[5] 서적 Recreation mathematiques et physiques https://archive.org/[...] Berlin New York de Gruyter
_[6] 논문
_[7] 논문
_[8] 간행물 Magic Squares and Other Problems on a Chess Board https://books.google[...]
_[9] 문서 Euler
_[10] 간행물 Le Probléme de 36 Officiers Secrétariat de l'Association
_[11] 간행물 Le Probléme de 36 Officiers Secrétariat de l'Association
_[12] 논문
_[13] 간행물 On the falsity of Euler's conjecture about the non-existence of two orthogonal Latin squares of order 4''t'' + 2 1959
_[14] 간행물 Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler's conjecture
_[15] 간행물 Thirty-six entangled officers of Euler: Quantum solution to a classically impossible problem
_[16] 간행물 Entanglement and quantum combinatorial designs
_[17] 간행물 Euler's 243-Year-Old 'Impossible' Puzzle Gets a Quantum Solution https://www.quantama[...]
_[18] 간행물 Centuries-old 'impossible' math problem cracked using the strange physics of Schrödinger's cat https://www.livescie[...]
_[19] 논문
_[20] 논문
_[21] 논문
_[22] 논문
_[23] 논문
_[24] 논문
_[25] 문서 The term "order" used here for MOLSs, affine planes and projective planes is defined differently in each setting, but these definitions are coordinated so that the numerical value is the same.
_[26] 간행물 The nonexistence of certain finite projective planes
_[27] 간행물 The Search for a Finite Projective Plane of Order 10 http://www.cecm.sfu.[...]
_[28] 논문
_[29] 논문
_[30] 서적 Design Theory by Thomas Beth https://www.cambridg[...] Cambridge Core 1999-11
_[31] 논문
_[32] 논문
_[33] 논문
_[34] 논문
_[35] 논문
_[36] 인용 1987
_[37] 인용 1987
_[38] 인용 1993
_[39] 서적 구수략 1715?
_[40] 저널 최석정의 직교라틴방진 http://coding.yonsei[...] 2017-06-08
_[41] 서적 Recreations mathematiques et physiques, qui contiennent Pluſieurs Problêmes d’Arithmetique, utiles & agreables, de Geometrie, d’Optique, de Gnomonique, de Coſmographie, de Mecanique, de Pyrotechnie, & de Phyſique. Avec un Traitè nouveau des Horloges Elementaires Chez Jean Jombert 1694
_[42] 서적 Recreations mathematiques et physiques, ou l’on traite. Des Phoſphores naturels & artificiels, & des lampes perpétuelles. Diſſertation phyſique & chymique. Avec l’explication des tours de gibeciere, de gobelets, & autres récréatifs & divertiſſans Chez Claude Jombert 1778
_[43] 저널 Recherches sur une nouvelle espèce de quarrés magiques http://www.biodivers[...] 2021-01-21
_[44] 저널 Le problème des 36 officiers http://gallica.bnf.f[...] 1901-08-04
_[45] 저널 On the falsity of Euler’s conjecture about the non-existence of two orthogonal Latin squares of order 4''t''+2 1959-05-01
_[46] 저널 Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler’s conjecture 1960