Perfect $2$-codes over arbitrary alphabets

당신이 혼란스럽고 무질서한 은하계를 가로질러 비밀 메시지를 보내고 있다고 상상해 보십시오. 메시지를 전송할 때마다마다 장난기 가득한 우주 고블린이 나타나 글자를 다른 것으로 바꾸거나 아예 떨어뜨려 버릴 수도 있습니다. 이 혼돈 속에서 살아남기 위해, 당신은 단순히 메시지를 한 번 보내는 것이 아니라, 코드 안에 직접 "예비 부품"을 내장하여 보냅니다. 이것이 바로 당신의 텍사트 메시지, 우주 탐사선, 스트리밍 비디오가 엉망진창으로 변하는 것을 막아주는 보이지 않는 방패인 **오류 정정 부호(error-correcting codes)**의 세계입니다.

이 우주에서 "완벽한 부호(perfect code)"는 성배와 같습니다. 그것은 마치 거대한 상자(모든 가능한 메시지) 안에 최대한 많은 "안전 구역"(우리의 실제 메시지)을 집어넣으려는 퍼즐 맞추기와 같습니다. 각 안전 구역에는 보호를 위한 반경이 있습니다. 만약 메시지가 고블린의 공격을 받아 약간 변하더라도, 그것은 여전히 하나의 안전 구역 안에 머물게 되며, 수신자는 그것이 원래 어떤 메시지였는지 정확히 알 수 있습니다. 코드가 "완벽하다"는 것은 이 안전 구역들이 틈이나 겹침 없이 마치 직소 퍼즐처럼 딱 들어맞는다는 것을 의미합니다. 만약 퍼즐에 틈이 있다면 메시지를 잃어버릴 수 있고, 만약 겹친다면 어떤 메시지가 전송되었는지 혼동할 수 있습니다.

수십 년 동안 수학자들은 이 퍼즐의 궁극적인 버전, 즉 어떤 크기의 알파벳을 사용하더라도 두 개의 오류를 동시에 수정할 수 있는 "완벽한 2-부호(perfect 2-code)"를 찾는 문제를 해결하기 위해 노력해 왔습니다. 그들은 세 개 이상의 오류를 수정하는 완벽한 부호와 한 개의 오류를 수정하는 부호는 찾아냈지만, "특이한" 알파벳 크기(단순한 소수의 거듭제곱이 아닌 10이나 15 같은 크기)를 사용하여 정확히 두 개의 오류를 수정하는 경우에 대해서는 여전히 풀리지 않는 난제로 남아 있었습니다. 이는 2개, 4개 또는 8개의 아이템을 완벽하게 짐 가방에 넣는 방법은 알면서도, 6개나 10개를 넣는 방법은 전혀 모르는 것과 같습니다.

마이클 베넷(Michael Bennett)이 작성한 이 논문은 바로 그 특정한 미스터리를 깊이 파고듭니다. 저자는 매우 크고 특정한 계열의 "특이한" 알파벳 크기에 대해, 완벽한 2-부호가 단순히 존재하지 않는다는 것을 증명하는 데 목적을 둡니다. 이 논문은 단순히 추측하는 것이 아니라, 숫자들이 서로 닿지 않으면서 얼마나 가까워질 수 있는지를 측정하는 도구, 즉 고급 수학의 중화기를 사용하여, 만약 그러한 코드가 존재한다면 산술의 법칙을 깨뜨릴 정도로 믿을 수 없을 만큼 거대하고 기이해야 함을 보여줍니다.

이 논문의 주요 결과는 강력한 "불가능 영역(no-go zone)"을 제시합니다. 베넷은 알파벳 크기가 2의 거듭제곱에 소수의 거듭제곱을 곱한 형태($2^\alpha \times p^\beta$)인 경우, 완벽한 2-부호를 만드는 것은 불가능하다고 증명합니다. 구체적으로, 그는 이러한 코드가 이론적으로 가능하려면 관련 소수가 $10^{10}$(백억)보다 커야 하며, 2의 거듭제곱($\alpha$)은 20보다 커야 한다고 보여줍니다. 또한, 그러한 코드가 존재한다면 해당 소수를 8로 나누었을 때 나머지가 3이어야 합니다.

논문은 더 나아가, 가장 큰 소인수가 13 이하인 모든 알파벳 크기에 대해 이러한 완벽한 부호의 존재를 부정합니다. 실제로 저자는 $2^\alpha \times p^\beta$ 형태(작은 $\alpha$ 값을 가진 경우 포함)의 많은 특정 숫자들에 대해 완벽한 2-부호가 존재하지 않는다는 오랜 가설을 확인합니다. 저자는 단순히 "그럴 것 같다"고 말하는 것이 아니라, 엄격한 수학적 증명을 통해 그러한 코드가 존재하기 위한 조건들이 수학적 모순을 일으킨다는 것을 보여줍니다. 비록 이 논문이 우주의 모든 가능한 알파벳 크기를 배제하는 것은 아니지만, 가장 흔하고 흥미로운 "특이한" 크기들에 대한 문을 효과적으로 닫아버리며, 실질적으로 상상조차 할 수 없을 정도로 거대한 숫자들만이 남겨진 아주 좁고 제한적인 가능성만을 남겨둡니다.

불가능한 퍼즐의 이야기

마이클 베넷가 무엇을 했는지 이해하기 위해, 그가 풀고자 했던 퍼즐을 살펴봅시다. 특정 알파벳으로 만들 수 있는 모든 단어의 거대한 격자가 있다고 상상해 보십시오. 당신은 이 격자 위에 "비콘(beacon)"(당신의 코드 단어)을 배치하고자 합니다. 각 비콘 주변에는 모든 단어를 포함하는 원(두 번의 오류 거리 이내)을 그립니다. 코드가 완벽하려면, 이 원들이 겹치지 않으면서 격자 전체를 덮어야 합니다.

수학자들은 알파벳 크기가 "소수의 거듭제곱"(2, 3, 4, 8, 9, 16 등)인 경우 몇 가지 특별한 사례에서만 이것이 완벽하게 작동한다는 것을 오래전부터 알고 있었습니다. 하지만 알파벳 크기가 10, 12, 20과 같다면 어떻게 될까요? 이들은 소수의 거듭제곱이 아닌 "합성수"입니다. 한 개의 오류를 수정하는 데 대해서는 일부 해법이 알려져 있습니다. 세 개 이상의 오류를 수정하는 데 대해서는 해법이 없다는 것도 알려져 있습니다. 그렇다면 두 개의 오류를 수정하는 경우에는 어떨까요? 그것이 바로 열려 있던 질문이었습니다.

베넷의 논문은 특정 형태의 합성수에 집중합니다: $2^\alpha \times p^\beta$ 형태의 숫자들입니다. 이것을 알파벳 크기를 만드는 데 사용되는 수많은 2와 단일 소수 $p$(예: 5, 7, 11 등)의 곱이라고 생각하십시오. 질문은 이것입니다: 이 크기들을 사용하여 완벽한 2-부호를 만들 수 있는가?

수학적 탐정 작업

베넷은 단순히 코드를 만들어 실패한 것이 아니라, 특정한 다항식 방정식의 "근(roots)"을 살펴봄으로써 그것들이 존재할 수 없음을 증명했습니다. 이 방정식을 만약 완벽한 코드가 존재한다면 비콘이 반드시 있어야 할 위치를 알려주는 지도라고 생각하십시오. 만약 완벽한 코드가 존재한다면, 이 지도는 매우 가까운 두 개의 정수 지점(근)을 가져야 합니다.

저자의 돌파구는 이 두 숫자, $r_1$과 $r_2$가 "S-단위수(S-units)"여야 한다는 사실을 깨달은 데 있었습니다. 쉽게 말해, 이들의 소인수는 오직 매우 작고 특정한 숫자 목록(알파벳 크기와 숫자 2를 나누는 소수들)에서만 나올 수 있다는 뜻입니다.

여기서 영리한 점은, 베넷이 완벽한 코드가 존재하기 위해서 이 두 숫자가 믿을 수 없을 정도로 가까워야 한다는 것을 보여준 것입니다. 즉, 두 숫자의 차이가 크기에 비해 매우 작아야 합니다. 그러나 숫자를 분수로 근사하는 방법을 연구하는 **디오판토스 근사론(Diophantine approximation)**이라는 유명한 수학 분야에 따르면, 제한된 소인수를 가진 숫자들은 매우 작지 않은 한 서로 그렇게 가까워질 수 없습니다.

베넷은 이를 문제의 기하학적 구조에서 유도된 특정 방정식과 결합했습니다:
$$q(r_2 - r_1)^2 = 2(r_1 + r_2) + q - 6$$
이 방정식은 "결정적 증거(smoking gun)"입니다. 이것은 알파벳 크기 $q$를 두 근 사이의 거리와 직접 연결합니다.

거대한 폭로

이 방정식과 수론의 강력한 도구들을 사용하여, 베넷은 일련의 "불가능" 결과들을 증명했습니다:

1. "작은 소수" 금지: 알파벳 크기의 가장 큰 소인수가 13 이하인 경우, 완벽한 2-부호는 불가능합니다. 그는 가능한 모든 숫자의 쌍을 나열하고 그중 어느 것도 방정식에 부합하지 않음을 보여줌으로써 이를 수행했습니다.
2. "거대한 숫자" 장벽: $2^\alpha \times p^\beta$ 형태의 일반적인 경우, 만약 코드가 존재한다면 소수 $p$는 $10^{10}$(백억)보다 커야 함을 증명했습니다. 더욱 엄격하게는, 2의 거듭제곱($\alpha$)은 20보다 커야 합니다.
3. "Mod 8" 규칙: 만약 그러한 코드가 존재한다면, 소수 $p$는 8로 나누었을 때 나머지가 3인 숫자(3, 11, 19 등)여야 합니다.

이 논문은 본질적으로 다음과 같이 말합니다: "우리는 작은 숫자들을 확인해 보았고, 그것들은 작동하지 않습니다. 큰 숫자들의 경우, 수학적으로 그러한 코드가 존재하려면 너무나 거대해야 하고 매우 엄격한 규칙을 따라야 하므로 사실상 존재하지 않는 것과 다름없습니다."

슈뢰더-히파르쿠스(Schröder-Hipparchus)의 놀라움

이 논문에서 가장 즐거운 부분 중 하나는 고전 조합론에서 온 슈뢰더-히파르쿠스 수(또는 슈퍼 카탈란 수)라는 수열을 사용하는 방식입니다. 이 숫자들은 보통 괄호를 배치하는 방법이나 격자 위의 경로를 세는 문제에서 등장하는데, 갑자기 완벽한 2-부호 증명의 중간에 나타납니다.

베넷은 이 숫자들을 사용하여 복잡한 방정식을 일련의 항들로 전개했습니다. 이것은 마치 혼돈스러운 소음 속에서 숨겨진 패턴을 찾아내는 것과 같습니다. 이 숫자들을 사용하여 방정식을 전개함으로써, 그는 관련 숫자들이 터무니없이 크지 않은 한, 완벽한 코드가 존재하기 위해 필요한 "가까운 근접성"을 허용하기에는 항들이 너무 빠르게 성장한다는 것을 보여줄 수 있었습니다.

최종 판결

결론은 무엇입니까? 이 논문은 수학계의 오랜 의구심을 확인해 줍니다: 임의의 알파벳에 대한 완벽한 2-부호는 존재하지 않을 가능성이 높습니다.

이 논문은 우주에 숨어 있을지도 모르는 '단 하나의 완벽한 코드'를 찾아냈다고 주장하는 것이 아닙니다(왜냐고 만약 존재한다면 그것은 $10^{10}$보다 커야 하며 불가능한 제약을 따라야 함을 증명했기 때문입니다). 대신, 이 논문은 대다수의 경우를 효과적으로 배제합니다. 10, 15, 21 등 많은 알파벳 크리에에 대한 문을 닫아버리고, 해결 가능성을 너무나 거대한 숫자의 영역으로 밀어 넣어 사실상 존재하지 않는 것으로 간주하게 만듭니다.

저자의 작업은 "부정적(negative)" 증명의 승리입니다. 보물을 찾은 대신, 그는 보물 상자가 비어 있거나, 적어도 그 상자를 여는 열쇠가 아직 발명되지 않은 자물쇠를 필요로 한다는 것을 증명했습니다. 이러한 특정 알파벳 크기에 대한 오류 정정 부호를 만들려는 사람들에게 메시지는 명확합니다: 완벽한 2-부호를 찾는 일을 멈추십시오. 그것은 그곳에 없습니다.