Cobham's theorem for the Gaussian integers

숫자의 비밀 언어

당신이 로봇에게 숫자를 세는 법을 가르치고 있다고 상상해 보세요. 당신은 로봇에게 "숫자 5를 '101'로 적으라"와 같은 규칙을 줍니다. 이것이 우리 뇌와 컴퓨터가 작동하는 방식입니다. 우리는 진법 체계(numeration system), 즉 큰 숫자를 더 작은 기호(자릿수)의 문자열로 바꾸는 방법을 사용합니다. 보통 우리는 10진법(숫자 0부터 9까지)을 사용하지만, 2진법(0과 1만 사용)이나 심지어 12진법을 사용할 수도 있습니다.

이제 단순히 숫자를 읽는 것이 아니라, 다음에 올 것을 예측하는 로봇을 상상해 보세요. 만약 당신이 숫자 형태의 문자열을 입력하면, 로봇은 색깔이나 소리를 내뱉습니다. 만약 로봇이 출력을 결정하기 위해 제한된 수의 "상태(states)" 또는 "기분(moods)"을 사용하는 것처럼 충분히 단순하다면, 우리는 그 로ست이 만들어내는 패턴을 **자동 수열(automatic sequence)**이라고 부릅니다. 이 패턴들은 무작로 보일 만큼 복잡하면서도, 아주 작은 기계에 의해 만들어질 수 있을 만큼 단순하기 때문에 매우 매혹적입니다.

오랫동안 수학자들은 이 패턴들을 가지고 게임을 해왔습니다. 그들은 이렇게 물었습니다. "만약 어떤 패턴이 두 가지 서로 다른 계산 체계(예를 들어 2진법과 3진법)에 의해 생성될 수 있다면, 그 패턴은 사실 지루하게 반복되는 루프에 불과한 것일까?" 일반적인 정수의 세계에서 그 대답은 단호하게 **"예"**입니다. 이것은 **코밤의 정리(Cobham's Theorem)**라고 불리는 유명한 규칙입니다. 이 정리는 만약 어떤 패턴이 서로 간단한 관계를 공유하지 않는 두 가지 서로 다른 진법에서 '자동적'이라면, 그 패턴은 반드시 **결국 주기적(eventually periodic)**이어야 함을 의미합니다. 즉, 시간이 지나면 예측 가능한 반복 리듬으로 안착한다는 것입니다.

그런데 우리가 직선 형태의 정수를 벗어나 더 복잡한 세계로 발을 들여놓는다면 어떻게 될까요? 만약 우리의 숫자가 단순히 1, 2, 3이 아니라, $1+i$나 $2-i$와 같은 허수 부분을 포함한다면 어떨까요? 이것들은 **가우스 정수(Gaussian integers)**라고 불립니다. 이들은 하나의 선이 아니라 평면 격자(복소 평면) 위에 존재합니다. 여기서 큰 질문은 이것입니다. 코밤의 정리가 여기에서도 성립할까요? 만약 이 격자 위의 패턴이 두 가지 서로 다른 '허수' 계산 체계에서 단순해 보인다면, 그것은 여전히 단순한 반복 루프에 불 불과할까요?

논문의 발견: 격자를 길들이기

Álvaro Bustos-Gajardo, Robbert Fokkink, 그리고 Reem Yassawi가 저술한 "가우스 정수에 대한 코밤의 정리(Cobham's Theorem for the Gaussian Integers)"라는 제목의 이 논문은 그 질문에 대해 몇 가지 중요한 전제 조건을 달아 확정적인 **"예"**라는 답을 내놓았습니다. 저자들은 만약 가우스 정수의 격자 위에 있는 패턴이 두 가지 서로 다른 '허수' 계산 체계(진법)에 의해 생성될 수 있고, 그 진법들이 서로 "곱셈적으로 독립적"(즉, 하나가 다른 하나의 거듭제곱이 아닌 경우)이라면, 그 패턴은 반드시 결국 주기적이어야 함을 증명했습니다.

이것이 왜 중요한 일인지 이해하려면, 가우스 정수를 광활하고 무한한 체커보드라고 생각해 보세요. 보통 이 판 위의 패턴은 거칠고 혼란스러울 수 있습니다. 저자들은 만약 당신이 이 판 위에서 두 가지 서로 관련 없는 방식으로 숫자를 세는 방식(자동적 방식)을 사용하여 패턴을 '단순하게' 만들려고 시도한다면, 우주는 그 패턴을 깔끔하게 반복되는 타일로 붕괴하도록 강제한다는 것을 보여줍니다. 마치 격자에 숨겨진 법칙이 있는 것과 같습니다. 두 가지 서로 다른 단순한 규칙을 동시에 만족하는 진정으로 복잡하고 비반복적인 패턴은 존재할 수 없다는 것입니다.

하지만 이 논문은 명확한 선을 긋습니다. 이 규칙은 적어도 하나의 계산 진법이 "정수의 거듭제곱근(root of an integer)"이 아닐 때만 작동합니다.

• 예외: 만약 진법이 정수의 거듭제곱근(예를 들어 몇 번 곱했을 때 일반적인 정수가 되는 숫자)이라면, 이 규칙은 깨집니다. 이 특정한 경우에는 두 가지 서로 다른 진법에서 단순하면서도 결코 반복 루프로 안착하지 않는 패턴을 만들어낼 수 있습니다. 저자들은 이러한 "비반복적" 패턴이 존재하며, 이러한 특별한 진법을 선택할 경우 피할 수 없음을 증명했습니다.
• 증명: 저자들은 단순히 추측하거나 시뮬레이션을 돌린 것이 아니라, 엄밀한 수학적 증명을 제공했습니다. 그들은 기계에서 루프를 찾아내는 컴퓨터 과학의 도구인 "펌핑 레마(pumping lemmas)"와 숫자들이 서로 매우 가까운 값을 찾게 해주는 "디리클레 근사(Dirichlet approximation)"라는 기발한 트릭을 사용하여, 진법이 특별한 거듭제곱근이 아니라면 패턴은 반드시 반복되어야 함을 보여주었습니다.

(전문 용어 없이 설명하는) 왜 이것이 중요한가

이 논문 이전에도 수학자들은 이 규칙이 가우스 정수에서도 참일 것이라고 짐작했지만, 수학을 성립시키기 위해 심오한 수론에서 나온 거대하고 증명되지 않은 가정(이를 "4 지수 추측(four exponentials conjecture)"이라 부름)이 필요했습니다. 그 가정은 구름으로 만든 다리와 같았습니다. 유지될 수도 있지만, 아무도 확신할 수 없었죠.

이 논문의 주요 업적은 그 불안정한 다리를 제거했다는 점에 있습니다. 그들은 그 "구름 다리"가 필요하지 않음을 증명했습니다. 그들은 오직 견고하고 확립된 수학만을 사용하여 결과를 증명했습니다. 그들은 "구름 다리"가 결국 필요하지 않았음을 보여주었습니다. 또한 그들은 한셀(Hansel)과 세이퍼(Safer)가 제기한 특정 추측을 해결하여, 가장 흔한 유형의 가우스 계산 체계(자연수를 자릿수로 사용하는 체계)에 대해 패턴은 항상 결국 주기적임을 확인했습니다.

요약하자면, 이 논문은 허수의 혼돈스러운 세계에도 숨겨진 질서가 있다는 것을 알려줍니다. 만약 당신이 이 격자 위의 패턴을 두 가지 서로 관련 없는 언어로 설명하려고 한다면, 그 패턴은 필연적으로 자신의 본성을 드러낼 것입니다. 즉, 단순하고 반복되는 춤이 될 것입니다. 이 춤이 엉망이 되는 유일한 때는 당신이 매우 구체적이고 "특별한" 계산 진법을 선택했을 때뿐이며, 저자들은 이제 그들을 완전히 식별하고 분류해 냈습니다.