On the problem of large gcd for disjoint residue classes

당신이 숫자들이 서로로부터 어떻게 숨어있는지를 해결하려는 탐정이라고 상상해 보십시오. 수학의 세계, 특히 정수론(number theory)이라 불리는 분야에서 숫자들은 '잉여류(residue classes)'라는 이름의 '가면'을 쓰고 종종 숨어 있습니다. 잉여류는 원형 탁자의 특정 좌석과 같다고 생각할 수 있습니다. 각 좌석에는 숫자가 배정되지만, 그 숫자가 특정 크기인 '법(modulus)'으로 나누었을 때 동일한 '나머지'를 남길 때만 그 자리에 앉을 수 있습니다. 예를 들어, 12개의 좌석이 있는 탁자에서 '3시 방향' 좌석은 3, 15, 27 등과 같은 숫자들을 위한 자리입니다.

이제, 당신에게 매우 엄격한 규칙이 적용되는 좌석 그룹이 있다고 상상해 보십시오. 두 좌석은 절대 겹칠 수 없습니다. 만약 한 좌석이 5의 배수보다 1 큰 숫자들을 위한 자리이고, 다른 좌석이 7의 배수보다 2 큰 숫자들을 위한 자리라면, 그들은 우연히 하나의 숫자(예: 22)를 공유하게 될 수도 있습니다. 만약 그렇게 된다면, 그들은 '서로소(disjoint)'가 아닙니다. 이 이야기 속의 수학자들은 까다로운 질문을 던지고 있습니다: 만약 당신이 이 좌석들이 결코 숫자를 공유하지 않도록 완전히 분리되도록 강제한다면, 이 테이블 크기들(법) 사이의 공통된 요소(최대공약수, GCD)는 얼마나 커야 할까요? 이는 마치 퍼즐 조각들이 서로 맞지 않을 때, 그 모양들이 얼마나 유사해야 하는지를 묻는 것과 같습니다. 이 문제를 이해하는 것은 숫자들이 어떻게 분포되어 있는지를 파악하는 데 도움이 되며, 이는 암호학에서부터 소수의 리듬을 이해하는 것에 이르기까지 매우 중요합니다.

---

거대한 GCD 미스터리: 섞이기를 거부하는 숫자들

이 논문에서 Jan Fornal과 Yu-Chen Sun은 수학자들을 오랫동안 괴롭혀 온 퍼즐을 다룹니다. 그들은 모두 **쌍별로 서로소(pairwise disjoint)**인, 즉 어떤 두 개도 단 하나의 숫자도 공유하지 않는 $k$개의 서로 다른 '잉여류'(우리의 특별한 좌석들)를 살펴보고 있습니다. 핵심적인 질문은 이것입니다: 만약 당신에게 $k$개의 겹치지 않는 좌석이 있다면, 두 테이블 크기 사이의 최대 공약수(GCD)는 최소 얼마나 커야 할까요?

오랫동안 Sun이라는 수학자는 대담한 추측(conjecture)을 해왔습니다. 그는 만약 $k$개의 서로소인 좌석이 있다면, 어떤 두 테이블 크기 사이의 최대 공약수는 적어도 $k$여야 한다고 생각했습니다. 이는 깔끔하고 명쾌한 아이디어입니다. 만약 100개의 겹치지 않는 좌석이 있다면, 두 테이블은 적어도 100의 공약수를 가져야 한다는 뜻입니다. Sun은 적은 수의 좌석(20개까지)에 대해 이를 증명했고, 다른 이들은 특정 유형의 군(group)에 대해 이를 증명했지만, 임의의 수 $k$에 대한 일반적인 사례는 여전히 미스터리로 남아 있었습니다.

Fornal과 Sun은 Sun의 정확한 추측인 $k$를 증명하지는 못했지만, 놀라울 정도로 근접했습니다. 그들은 최대 GCD가 대략 $k$를 아주 작은, 줄어드는 분수로 나눈 값임을 증려했습니다. 그들의 표현을 빌리자면, 그들은 최대 GCD가 적어도 다음과 같음을 보여주었습니다:
$$\exp\left( -(2 + o(1)) \sqrt{\frac{\log k}{\log \log k}} \right)$$
이 무서운 수학 기호들에 겁먹지 마십시오. 쉬운 말로 풀이하자면, 답은 $k$의 아주 1에 가까운 지수 승이라는 뜻입니다. 이는 거의 $k$에 가깝지만, 아주 약간 더 작습니다. 따라서, 그들이 Sun의 정확한 수치인 $k$를 확인한 것은 아니지만, 최대 GCD가 좌석의 수만큼 빠르게 성장한다는 것을 확인했습니다. 이는 Sun의 직관이 본질적으로 옳았으며, 단지 아주 약간의 여유가 필요했을 뿐임을 증명한 거대한 진전입니다.

해결 방법: 색칠된 그래프 게임

이 코드를 풀기 위해, 저자들은 이 문제를 점들을 연결하는 게임, 즉 수학자들이 '그래프(graph)'라고 부르는 것으로 전환했습니다. 각 $k$개의 서로소인 좌석을 종이 위의 점(정점, vertex)이라고 상상해 보십시오. 이제 모든 점의 쌍 사이에 선(간선, edge)을 그리십시오. 하지만 여기 반전이 있습니다. 두 테이블 크기의 GCD에 따라 각 선의 색을 칠하는 것입니다. 만약 두 테이블이 모두 6의 배수라면, 그 사이의 선은 "6" 색으로 칠해집니다.

저자들은 만약 점(좌석)이 너무 많고 선(GCD)이 너무 작다면, 그래프가 서로소인 좌석으로는 도저 는 불가능한 특정한 형태를 띠어야 한다는 사실을 깨달았습니다. 그들은 체(sieve)라고 불리는 영리한 트릭을 사용하여 테이블 크기들을 카테고리로 분류했는데, 이는 마치 카드 덱을 문양과 숫자에 따라 분류하는 것과 비슷하지만, 여기서는 소인수(prime factor)를 기준으로 합니다.

그 후, 그들은 "가중치(weight)" 시스템을 도입했습니다. 어떤 점들은 다른 점들보다 더 중요합니다. 그들은 자신이 속한 그룹의 수에 따라 점들에 가중치를 부여했습니다. 핵심 통찰은 구조적 보조정리(structural lemma, 그래프의 형태에 관한 멋진 규칙)에서 왔습니다. 그들은 만약 어떤 점이 "이상한" 색(두 테이블 크기의 단순한 GCD가 아닌 GCD)의 선들로 많은 다른 점들과 연결되어 있다면, 그 점은 아주 작은 "예외적인(exceptional)" 그룹에 속하거나, 혹은 매우 작은 가중치를 가져야 한다는 것을 발견했습니다.

이러한 가중치들을 조절하고, 숫자의 숨겨진 리듬을 듣는 방법과 같은 '이산 푸리에 변환(discrete Fourier transform)'이라는 도구를 사용함으로써, 그들은 그래프의 총 가중치가 GCD를 크게 만들 수밖에 없음을 보여주었습니다. 만약 GCD가 작았다면, 수학적 모순이 발생하여 계산이 무너졌을 것입니다.

결론

이 논문은 임의의 $k$개의 쌍별로 서로소인 잉여류 집합에 대하여, 임의의 두 법(moduli) 사이의 최대 GCD는 적어도 다음과 같음을 증명합니다:
$$k^{1 - o(1)}$$
이는 $k$가 매우 커짐에 따라, 공유되는 인수가 $k$ 자체에 점점 더 가까워진다는 것을 의미합니다.

그들은 또한 서로소인 등차수열(일정한 간격을 가진 수의 수열)의 "극단적 가족(extremal families)"에 관한 관련 문제에도 이 결과를 적용했습니다. 그들은 가장 큰 규모의 이러한 수열 집합 내에서, 두 숫자가 거대한 공통 인수를 공유해야 함을 보여주었습니다. 구체적으로는 $x L(x)^{-1+o(1)}$ 정도이며, 여기서 $L(x)$는 로그를 포함하는 특정 함수입니다.

요약하자면, Fornal과 Sun은 단순히 추측한 것이 아니라, 그래프, 체, 그리고 푸리에 분석을 사용하여 서로소인 숫자들은 놀라울 정도로 강력한 연결을 갖도록 강제된다는 것을 증명하는 엄밀한 수학적 가교를 구축했습니다. 그들이 문제를 완벽하게 해결한 것은 아닙니다 (정확한 $k$는 여전히 추측 단계입니다). 하지만 그들은 연결이 추측이 예측한 것만큼이나 강력하다는 것을 증명함으로써, 그 간극을 크게 좁혔습니다.