수학의 ‘2층 침대 추측’, 틀린 것으로 판명

직관적이고 심지어 당연해 보였다. 그러나 틀렸다.

수학의 많은 부분은 직관에 의해 움직입니다. 어떤 것이 사실일 것이라는 깊은 믿음에서 시작되죠. 하지만 때로는 이러한 본능이 수학자를 잘못된 길로 이끌기도 합니다. 초기 증거가 전체 그림을 대변하지 않을 수도 있고, 겉보기에 분명해 보이는 명제가 숨겨진 복잡성에 의해 반박될 수도 있습니다.

최근, 세 명의 수학자가 확률론의 잘 알려진 가설 중 하나인 ’2층 침대 추측(bunkbed conjecture)’이 이러한 범주에 속한다는 것을 밝혀냈습니다. 이 추측은 2층 침대처럼 쌓아 올린 그래프라는 수학적 미로를 탐색하는 방법에 대한 것입니다. 이 추측은 자연스럽고, 심지어 자명하게 보였습니다. 프린스턴 대학교의 그래프 이론 학자 마리아 추드노브스키(Maria Chudnovsky)는 이번 연구에 참여하지 않았지만 이렇게 말했습니다. “우리의 뇌가 말하는 모든 것이 이 추측이 옳다고 말하는 것처럼 보였습니다.”

하지만 그건 틀린 생각이었습니다. 지난달, 세 명의 수학자가 반례(counterexample)를 제시하며 이 추측을 반박했습니다. 이 결과는 고체 물질의 성질에 대한 물리학 문제를 다루는 새로운 접근법을 제시할 뿐만 아니라, 수학이 어떻게 작동하는지에 대한 깊은 질문을 제기합니다. 수학적 노력의 상당 부분은 추측을 입증하는 데 집중됩니다. 반면, 그것을 반박하려는 시도는 훨씬 더 외로운 길입니다. 이번 연구를 진행한 팀은 반례를 찾기 전까지 수많은 실패를 겪었습니다. 그들의 이야기는 수학자들이 자신의 가정을 더 자주 의심할 필요가 있음을 시사합니다.

그래프 위의 그래프

1980년대 중반, 네덜란드의 물리학자 피터 카스텔레인(Pieter Kasteleyn)은 액체가 다공성 고체를 통해 흐르는 방식에 대한 수학적 증명을 시도하던 중 이층침대 추측(Bunkbed Conjecture)을 제기했습니다.

이를 이해하려면 먼저 그래프(graph)라는 개념을 살펴보아야 합니다. 그래프는 점(정점, vertex)과 이를 연결하는 선(변, edge)의 모음입니다.

우선, 주어진 그래프를 하나 복사해서 원래 그래프 바로 위에 놓습니다. 그런 다음, 아래 그래프의 일부 정점과 위 그래프의 대응 정점을 연결하는 수직 기둥(추가적인 변)을 그립니다. 이 구조는 마치 이층침대처럼 보입니다.

이제 아래 그래프의 한 변을 선택하고 동전을 던져 결과에 따라 변을 삭제하거나 유지합니다. 동전이 앞면(heads)이면 해당 변을 삭제하고, 뒷면(tails)이면 그대로 둡니다. 이 과정을 모든 변에 대해 반복합니다. 그러면 아래 그래프와 위 그래프는 서로 다른 모양이 되지만, 여전히 수직 기둥으로 연결되어 있습니다.

마지막으로 아래 그래프의 두 정점을 선택합니다. 첫 번째 질문: 그래프의 변을 따라가면서 한 정점에서 다른 정점으로 이동할 수 있을까요? 즉, 두 정점 사이에 경로가 존재할 확률을 계산할 수 있습니다.

두 번째 질문: 선택한 두 정점 중 하나를 위 그래프의 대응 정점으로 “점프”시킨 뒤, 시작 정점에서 위쪽의 종료 정점까지 이동 가능한 경로가 존재할까요?

이층침대 추측은 다음과 같이 말합니다: “아래 그래프에서 경로를 찾을 확률은, 위쪽으로 점프하여 경로를 찾을 확률보다 항상 크거나 같다.” 이는 시작 그래프의 형태, 수직 기둥의 개수, 시작 및 종료 정점의 선택과 관계없이 성립한다고 주장합니다.

수십 년 동안 수학자들은 이 추측이 사실일 것이라고 생각했습니다. 직관적으로, 같은 층(한 그래프 내)에서 이동하는 것이 다른 층(위/아래 그래프)을 오가는 것보다 더 쉽다고 판단했습니다. 위쪽으로 점프하는 데 추가적인 수직 이동이 필요하기 때문에, 가능한 경로의 수가 제한된다고 여겨졌습니다.

게다가, 수학자들은 이층침대 추측이 사실이기를 간절히 바랐습니다. 이 추측은 침투 이론(percolation theory)이라는 영역에 속하는 여러 명제 중 하나입니다. 침투 이론은 그래프의 변이 무작위로 삭제된 후 남은 경로와 군집에 대해 연구합니다. 이는 스펀지처럼 다공성 재료 내부를 액체가 이동(침투)하는 방식을 단순화한 모델로 볼 수 있습니다.

이층침대 추측이 증명된다면, 물리학에서 널리 받아들여진 액체가 고체를 통과하는 확률에 관한 가정을 수학적으로 뒷받침할 수 있습니다. 또한 침투 물리학(percolation physics)에 관련된 다른 문제를 해결하는 데 실마리를 제공할 수도 있습니다.

하지만 이 추측이 사실임을 증명하는 일은 오랫동안 누구도 성공하지 못했습니다. 그 이유는 무엇일까요?

틀렸을 가능성

캘리포니아 대학교 로스앤젤레스(UCLA)의 수학자 이고르 팍(Igor Pak)은 이층침대 추측이 참이라는 점에 대해 처음부터 의심을 품고 있었습니다. 그의 대학원생 니키타 글래드코프(Nikita Gladkov)는 이렇게 말했습니다.
“그는 처음부터 회의적이었어요. 팍 교수님은 오래된 추측을 잘 믿지 않는 분입니다.”

팍은 수학자들이 이러한 추측을 증명하는 데 초점을 맞추는 경향에 대해 공개적으로 비판해 왔습니다. 그는 이렇게 주장합니다.
“만약 이런 추측들이 전부 틀렸다면 어떨까요?”

팍이 이층침대 추측을 의심했던 특별한 이유도 있었습니다. 이 추측이 지나치게 포괄적인 주장을 담고 있었기 때문입니다. 그는 이 추측이 모든 가능한 그래프에 대해 성립한다고 보기는 어렵다고 생각했습니다.
“어떤 추측은 실질적 동기에서 비롯되고, 다른 추측은 희망적 사고에서 비롯됩니다. 이층침대 추측은 후자에 가깝습니다.”

2022년, 팍은 이층침대 추측이 틀렸다는 것을 증명하려는 시도를 시작했습니다. 1년 동안 여러 방법을 시도했지만 모두 실패로 끝났습니다. 결국 그는 글래드코프에게 컴퓨터를 사용해 가능한 모든 그래프를 철저히 탐색하는 작업을 지시했습니다.

작업이 고도화된 프로그래밍 기술을 요구한다는 것을 깨달은 글래드코프는 고등학교 시절 친구였던 알렉산드르 지민(Aleksandr Zimin)에게 도움을 요청했습니다. 지민은 현재 매사추세츠공과대학(MIT)의 대학원생이었죠.
“사실 우리 둘은 대학 시절 룸메이트였어요. 기숙사에 진짜 이층침대를 썼습니다.”라고 글래드코프는 회상했습니다.

글래드코프, 팍, 지민은 정점이 9개 미만인 모든 그래프를 수작업으로 검토할 수 있었습니다. 이 경우 이층침대 추측은 성립한다는 것을 확인할 수 있었습니다. 하지만 더 큰 그래프에서는 가능한 경우의 수가 기하급수적으로 늘어나기 시작했습니다. 변이 삭제되거나 경로가 형성되는 모든 경우를 검토하는 것은 불가능해졌습니다.

팀은 머신러닝으로 방향을 돌렸습니다. 신경망을 훈련시켜 상위 그래프로의 점프를 선호할 가능성이 있는 복잡한 경로를 가진 그래프를 생성하도록 했습니다.

신경망이 생성한 예시들 중, 아래층 경로가 위층 경로보다 아주 조금 더 가능성이 높은 경우를 다수 발견했습니다. 하지만 반대되는 결과를 보이는 그래프는 찾을 수 없었습니다.

또 다른 문제가 있었습니다. 신경망이 생성한 그래프는 너무 커서, 동전 던지기 과정에서 발생할 수 있는 모든 결과를 하나하나 확인할 수 없었습니다. 대신 팀은 이 결과들의 일부만을 샘플링해 확률을 계산해야 했습니다. 이는 마치 여론조사에서 표본을 통해 선거 결과를 예측하는 것과 비슷한 방식입니다.

수학자들은 신경망이 제공한 반례에 대해 99.99% 이상의 신뢰도를 가질 수 있었습니다. 그러나 이는 엄밀한 증명으로는 부족했습니다. 학계가 이를 설득력 있는 반례로 받아들이기는 어려웠습니다. 주요 학술지가 이를 공식적인 증명으로 인정할 가능성도 낮았습니다.

팍은 자신의 블로그에 이렇게 적었습니다.
“박사과정 학생들은 이론이 아니라 현실에서 직장을 구해야 합니다.”
실제로 글래드코프와 지민은 곧 취업 준비를 해야 했습니다.
“그래서 우리가 멈춘 이유가 바로 그것입니다. 왜 다른 방법을 시도할 수 있는데 논란을 만들며 이 길을 고집해야 하나요?”

팀은 컴퓨터 기반 접근 방식을 포기했지만, 문제 자체에 대한 고민을 멈추지는 않았습니다. 이후 몇 달 동안, 그들은 컴퓨터를 사용하지 않고도 증명할 수 있는 이론적 접근 방식을 모색했습니다. 그러나 필요한 모든 단서를 찾지 못했습니다.

그러던 중, 해외에서 놀라운 돌파구가 찾아왔습니다.

컴퓨터는 정말 필요한가?

2024년 6월, 케임브리지 대학교의 로렌스 홀롬(Lawrence Hollom)은 이층침대 문제의 또 다른 맥락에서 변형된 버전을 반박하는 데 성공했습니다. 그가 다룬 것은 그래프가 아닌 초그래프(hypergraph)라는 개념이었습니다. 초그래프에서는 변(edge)이 두 정점을 연결하는 것으로 정의되지 않고, 다수의 정점을 연결할 수 있습니다.

홀롬은 이 변형된 추측에 대한 반례를 발견했습니다. 그는 세 개의 정점을 연결하는 변을 가진 작은 초그래프를 만들어냈습니다.

글래드코프는 홀롬의 논문을 우연히 발견했습니다. 그날 밤, 그는 논문을 읽느라 새벽 3시까지 잠을 이루지 못했습니다.
“와, 정말 놀라운 내용이에요. 완전히 머리가 뒤집혔습니다.”라고 그는 회상했습니다. 글래드코프는 잠들기 전, 동료 지민에게 문자를 보냈고, 다음 날 두 사람은 전화 통화를 하며 이 반례를 논의했습니다.
“이 반례를 활용해 원래의 이층침대 추측을 반박할 수 있을까?”

사실 두 사람은 초그래프를 일반 그래프로 변환하는 문제를 이전부터 고민해 왔습니다. 1년 전, 이들은 한 콘서트에 참석하기 직전에도 이에 대해 논의한 적이 있었습니다.
“레드 핫 칠리 페퍼스(Red Hot Chili Peppers)가 노래를 부르고 있었지만, 저는 그 문제만 생각했어요. 음악에 집중하지도 못했죠.”라고 글래드코프는 말했습니다.

그들은 이후 특정 상황에서 초그래프를 그래프로 변환할 수 있는 기술을 개발했습니다. 이제 그 기술을 활용해 홀롬의 초그래프를 변형할 수 있었습니다.

글래드코프, 팍, 지민은 초그래프의 세 정점을 연결하는 각 변을 대규모 점(cluster)과 일반 변으로 대체했습니다. 그 결과, 7,222개의 정점과 14,422개의 변으로 이루어진 거대한 그래프를 만들어냈습니다.

그들은 인공지능 접근법을 포기한 이후 구축한 이론적 논리를 활용해, 이 그래프에서 상위 경로(위층 경로)를 찾을 확률이 $\frac{1}{10^{6500}}$% 더 높다는 것을 증명했습니다. 비록 그 확률이 매우 작았지만, 0이 아닌 값임을 증명했습니다. 결국, 이층침대 추측은 틀렸다는 결론에 도달했습니다.

프린스턴 대학교의 수학자 노가 알론(Noga Alon)은 이 결과가 “아무것도 당연하게 여기지 말아야 한다”는 중요한 교훈을 준다고 말했습니다.
“직관적으로 매우 타당해 보이는 것조차 의심해야 합니다.”

글래드코프, 팍, 지민은 작은 그래프의 경우 이층침대 추측이 성립한다는 많은 예를 확인했습니다. 그러나 이들은 충분히 많은 정점과 변을 가진 복잡한 그래프에서는, 직관과 달리 추측이 성립하지 않는 사례를 만들어낼 수 있음을 보여주었습니다.

홀롬은 이렇게 묻습니다. “우리가 이 모든 것을 정말로 잘 이해하고 있다고 생각할 수 있을까요?”

이층침대 추측에 영감을 준 고체 내 연결된 위치에 대한 물리학적 명제는 여전히 수학자들에게 신뢰를 받고 있습니다. 그러나 이를 증명하는 데는 다른 접근 방식이 필요합니다.

팍은 수학적 증명의 본질에 대해 더 활발한 논의가 필요하다고 강조합니다. 그는 이번 반박에 있어 논란이 될 수 있는 계산적 방법에 의존하지 않았고, 절대적인 확실성을 가진 증명을 제시했습니다. 하지만 점점 더 많은 수학 연구가 컴퓨터와 인공지능 기반의 방법을 활용함에 따라, 수학계의 기준이 바뀔 가능성에 대한 논쟁이 이어지고 있습니다.

알론은 이 질문을 이렇게 표현했습니다.
“확률적으로만 참인 증명을 어떻게 받아들여야 할까요? 이는 철학적 질문입니다.”

반면, 컴퓨터를 공동 저자로 인정하는 것으로 유명한 럿거스 대학교의 수학자 도론 차일버거(Doron Zeilberger)는 이렇게 말했습니다.
“수학의 미래는 이러한 확률적 증명을 받아들이는 데 달려 있습니다. 앞으로 50년, 어쩌면 더 빨리 사람들의 태도가 바뀔 것입니다.”

하지만 알론은 이러한 미래가 본질적인 이해를 위협할 수 있다고 우려합니다.
“확률적 증명은 우리가 진정으로 무슨 일이 일어나고 있는지에 대한 이해나 직관을 줄일 수 있습니다.”

팍은 이러한 유형의 결과가 더 흔해질수록 별도의 학술지를 만들어야 한다고 제안합니다. 이렇게 하면 이들 결과의 가치를 수학자들이 잃지 않을 것이라고 주장합니다. 그러나 그의 주된 목표는 대화를 시작하는 것입니다.
“정답은 없습니다. 커뮤니티가 명상하듯 다음번 이와 같은 결과를 인정할지 고민해보길 바랍니다.”

기술이 수학에 더 깊숙이 침투하고 변화를 가져오면서, 이 질문은 점점 더 중요해질 것입니다.