A proof of the cyclotomic conjecture and the non-existence of almost Moore digraphs

당신이 가장 효율적인 도시를 건설하려는 숙련된 건축가라고 상상해 보십시오. 당신에게는 엄격한 규칙이 있습니다. 모든 건물("노드")은 오직 정해진 수의 이웃("차수")에게만 메시지를 보낼 수 있으며, 어떤 메시지도 다른 건물에 도달하기 위해 너무 많은 단계를 거쳐서는 안 됩니다("지름"). 수학, 특히 그래프 이론의 세계에서 이것은 "차수-지름 문제(degree-diameter problem)"라고 알려져 있습니다. 이것은 마치 사람들이 한 방에 최대한 많이 모여 있으면서도, 각자가 몇 명의 소개만으로도 서로 인사를 나눌 수 있고, 모든 사람이 특정 횟수의 소개 안에 다른 모든 사람에게 인사를 건넬 수 있도록 하는 것과 같습니다.

수학자들은 오랫동안 이 "완벽한" 도시의 크기, 즉 이러한 규칙 하에서 가능한 절대적인 최대 건물 수를 나타내는 "무어 경계(Moore bound)"를 알고 있었습니다. 하지만 이러한 완벽한 도시는 매우 단순하고 평범한 시나리오에서만 존재하며, 극히 드물게 나타납니다. 이 논문은 바로 이 "거의 완벽한" 도시들이 존재하는지에 대한 질문을 다룹니다. 이들은 "거의 무어 유향 그래프(almost Moore digraphs)"라고 불립니다. 수십 년 동안 연구자들은 이 근접 완벽한 구조들을 찾아 헤맸으며, 이들이 복잡하고 큰 도시에서도 존재하는지, 아니면 단순히 수학적 법칙이 이를 금지하는 것인지 궁금해했습니다.

자스카란 카우르(Jaskaran Kaur)와 히테쉬 쿠마르(Hitesh Kumar)가 작성한 이 논문은 이 사건을 종결짓는 최종 탐정 보고서 역할을 합니다. 저자들은 모든 건물당 출구가 하나보다 많고($d > 1$) 경로 길이가 2보다 큰($k > 2$) 복잡한 시나리오에서는 이러한 "거의 완벽한" 도시가 존재하지 않음을 증명했습니다. 이를 해결하기 위해 그들은 단순히 도시 지도를 살펴보는 데 그치지 않고, "사이클로토믹 다항식(cyclotomic polynomials)"이라는 깊고 추상적인 세계로 뛰어들었습니다. 이 다항식들은 도시 구조의 비밀스러운 DNA 또는 근본적인 악보와 같습니다. 이 논문은 이 수학적 DNA가 복잡해질 때 항상 특정한 방식으로 분해된다는 것을 보여줌으로써, "거의 완벽한" 도시가 수학적으로 불가능함을 입증하며 "사이클로토믹 추측(cyclotomic conjecture)"을 해결했습니다.

사라진 도시의 미스터리

유향 네트워크(연결에 특정 방향이 있는 경우, 예: 일방통행 도로)의 세계에서, 수학자들은 주어진 출구 수($d$)와 최대 이동 시간($k$)을 가진 가장 큰 도시를 만드는 공식이 있습니다. 이 공식 $M_{d,k} = 1 + d + \dots + d^k$는 "무어 경계"라는 이론적 천장입니다.

우리는 이 천장에 정확히 도달하는 도시들이 거의 존재하지 않는다는 것을 알고 있습니다. 그것들은 단순한 루프나 완전히 연결된 허브와 같은 사소한 경우에만 나타납니다. 따라서 큰 질문은 이것입니다. 그렇다면 딱 한 단계 작은 도시는 어떨까요? 이 "거의 무어 유향 그래프"들은 성배와 같았습니다. 만약 이것들이 존재한다면, 그것들은 복잡한 시스템을 위한 가장 효율적인 네트워크가 될 것이기 때문입니다.

수년 동안 수학자들은 작은 사례들을 조사했습니다. 특정하고 아주 작은 설정에서는 몇 가지를 발견했지만, 더 크고 흥미로운 숫자들에 대해서는 검색 결과가 없었습니다. 문제는 이들이 존재하지 않음을 증명하기 위해 사이클로토믹 다항식과 관련된 매우 까다로운 퍼즐을 풀어야 했다는 점입니다. 사이클로토믹 다항식은 단위근(원의 근본적인 주파수라고 생각할 수 있음)과 관련된 특별한 수학적 표현식입니다.

자물쇠를 여는 열쇠: 사이클로토믹 추측

이 논문의 저자들은 이러한 "거의 완벽한" 도시의 존재 여부가 $F_{n,k}(x)$라는 다항식의 특정 속성에 전적으로 달려 있다는 것을 깨달았습니다. 이 다항식은 사이클로토믹 다항식($\Phi_n$)에 단순한 합($1 + x + \dots + x^k$)을 대입하여 만들어집니다.

1999년, 수학자 김베르트(Gimbert)는 이 다항식 $F_{n,k}(x)$가 언제 분해(가약, reducible)되고 언제 온전하게 유지(기약, irreducible)되는지를 설명하는 "사이클로토믹 추측"을 제안했습니다.

• 만약 다항식이 온전하게 유지된다면(기약), 그것은 단단하고 깨지지 않는 블록처럼 작동합니다.
• 만약 다항식이 분해된다면(가약), 그것은 더 작은 조각들로 쪼개집니다.

이 연결 고리는 매우 중요합니다. 만약 다항식이 특정한 방식으로 분해된다면, 이는 "거의 무어" 도시가 존재할 수도 있음을 의미합니다. 반대로 다항식이 온전하게 유지된다면, 그 도시는 불가능합니다. 이전의 연구자들은 작은 숫자들에 대해서는 이를 증명했지만, 일반적인 경우에는 여전히 미스터리로 남아 있었습니다.

돌파구: 추측의 증명

카우르와 쿠마르는 작은 숫자가 아닌 모든 숫자에 대해 이 추측을 증명하기 위해 투입되었습니다. 그들은 다항식 $F_{n,k}(x)$를 복잡한 기계처럼 취급하고, 그 기계의 톱니바퀴(근과 계수)가 어떻게 상호작용하는지 분석했습니다.

그들은 사이클로토믹 다항식에 변형을 가한 보조 다항식 $q(x)$를 정의했습니다. 그런 다음 $q(x)$와 그 거울 이미지인 $q^\#(x)$ 사이의 "최대 공약수"를 분석했습니다. 이 단계는 마치 기계에 느슨한 나사가 있어 부서지게 만들 요소가 있는지 확인하는 것과 같았습니다.

그들의 분석은 엄격한 규칙을 드러냈습니다:

1. $k$가 짝수인 경우: 다항식은 특정 숫자 $n$이 $k+2$를 나눌 때만 분해됩니다.
2. $k$가 홀수인 경우: 다항식은 $n$이 짝수이고 $2(k+2)$를 나눌 때만 분해됩니다.

그 외의 모든 경우에는 다항식이 기약(unbreakable) 상태로 유지됩니다.

최종 판결: "거의 완벽한" 도시는 없다

추측을 증명한 후, 저자들은 이 논리를 도시 건설 문제에 적용했습니다. 그들은 건물당 출구가 하나보다 많고($d > 1$) 이동 시간이 2단계보다 큰($k > 2$) 모든 경우에 대해, "거의 무어" 도시가 존재하기 위해 필요한 수학적 조건이 결코 충족되지 않음을 보여주었습니다.

다항식 $F_{n,k}(x)$는 도시 형성을 막는 바로 그 방식으로 기약 상태를 유지합니다. 결과적으로, 저자들은 그러한 유향 그래프는 존재하지 않는다는 것을 증명했습니다.

이는 당신이 이러한 규칙 하에 어떤 복잡한 네트워크를 구축하려고 하더라도, 이론적 최대 크기에 단 한 노드조차 근접할 수 없음을 의미합니다. 가장 좋은 네트워크와 이론적 한계 사이의 간격은 최소 두 개의 노드입니다. "거의 완벽한" 도시는 수학적 신화입니다.

이 논문은 이러한 매개변수에 대해 유향 차수-지름 문제의 확정적인 답이 있음을 확인하며 결론을 맺습니다. 즉, 가장 큰 네트워크는 항상 무어 경계보다 최소 두 단계 작습니다. "거의 무어" 유향 그래프를 찾는 추적은 끝났습니다; 그것은 애초에 존재하지 않았기 때문입니다.