박과 팜, 6페이지 증명으로 칸-칼라이 추측을 해결하다: 덮개를 통한 접근

무작위 그래프는 삼각형이나 해밀턴 순환 같은 성질을 갑작스럽게 획득한다. 어떤 확률 아래에서는 그 구조가 거의 결코 나타나지 않고, 그 바로 위에서는 거의 항상 나타난다. 정확한 임계값은 계산하기 어려우므로 수학자들은 쉬운 하한인 기댓값 임계값을 사용한다. 2006년 제프 칸과 길 칼라이는 실제 임계값이 기댓값 임계값을 로그 인자 이상 초과하지 않는다고 추측했다. 이 주장은 저자들 자신에게조차 너무 강해 보였고, 그들은 수년간 반례를 찾아 헤맸지만, 이 추측은 임계값 문제를 거의 기계적으로 해결해 줄 것이기에 핵심 미해결 문제가 되었다.

이 추측에 대해 인정받던 경로는 미셸 탈라그랑이 제안한 더 약한 버전을 거치는 것이었는데, 이는 기댓값 임계값을 분수 변형으로 대체한다. 칸, 박진영과 동료들은 2019년 해바라기 돌파구에서 가져온 기법과 '스프레드'라는 개념을 도입하여 2021년에 그 버전을 증명했다. 칸 본인은 그 동등성을 증명하는 것만이 완전한 추측으로 가는 유일한 길이라고 늘 생각했다고 말했다. 한편 박과 팜 후이 투안은 또 다른 탈라그랑 문제를 연구하던 중 자신들의 아이디어가 보기보다 더 강력하다는 것을 깨달았다.

2022년 3월의 한 잠 못 이룬 밤 동안 그들은 직접적인 논증을 찾아냈다. 원래 추측에 출발점을 주지 않는 스프레드 대신, 그들은 관점을 바꾸어 그 주장을 덮개로 다시 썼다. 즉 무작위 집합이 어떤 목표 구조도 포함할 가능성이 낮다면, 그 구조들의 모임은 기댓값 임계값에 대한 기여가 작은 작은 덮개를 가진다는 것이다. 그들은 조각조각 표본추출하여 그 덮개를 구성하고 계수 논증으로 마무리했으며, 일주일 후인 2022년 3월 31일에 6페이지 논문을 게재했다.

동료들은 경악했다. 칼라이는 그것을 놀랍도록 단순하고 독창적이라고 불렀고, 제이컵 폭스는 그 증명을 마법 같다고 했으며, 데이비드 콘런은 그것이 가정된 로드맵을 곧장 뚫고 나갔다고 말했다. 이 추측은 추상적 집합 위에 쓰여 있기 때문에, 그 증명은 수백 가지의 구체적인 임계값 명제를 한꺼번에 해결하며 다른 이들이 재사용할 것으로 기대되는 기법을 남긴다. 콴타는 2022년 4월 25일에 이 결과를 보도했고, 박과 팜은 임계값 사이의 격차가 최악의 경우보다 작아지는 때에 관한 더 정교한 질문에 이 방법을 적용하기 시작했다.

덮개로 재구성하고 그것을 직접 계수한다

덮개는 원래의 기댓값 임계값에 직접 작용한다. 목표 구조들의 작은 덮개는 가중 평균에 대한 작은 기여이므로, 분수 대체물로 약화시킬 필요가 없었다.

그 주장을 대우로 다시 쓰는 것은 확률적 보장을 구성 과제로 바꾸었다. 즉 작은 덮개를 만드는 것인데, 조각조각 표본추출로 그것을 달성할 수 있었다.

계수 논증이 빠진 추진력을 제공했으므로, 그 증명은 학계가 유일한 다리라고 믿었던 스프레드-분수 동등성을 전혀 필요로 하지 않았다.

6페이지라는 분량은 전체 학계가 그 논증을 즉시 읽고 채택할 수 있음을 뜻했고, 그래서 선배 수학자들이 그것을 단지 옳은 것이 아니라 마법 같다고 불렀다.

모두가 더 약한 버전을 거치는 우회가 유일한 경로라고 가정할 때, 그 가정을 의심하라. 문제를 표현하는 방식을 바꾸면 직접 공격이 짧아질 수 있다

두 사람은 2022년 3월 31일에 '칸-칼라이 추측의 증명'을 arXiv에 게재했다(2023년 4월 13일 개정). 콴타 매거진은 2022년 4월 25일에 이를 무작위 구조의 출현에 관한 우아한 6페이지 증명으로 보도했고, 그 이야기는 2022년 4월 26일 해커 뉴스에서 589점과 166개의 댓글을 얻었다. 그 후 박과 팜은 기댓값 임계값과 실제 임계값 사이의 격차가 로그 최악의 경우보다 작아지는 때에 관한 더 정교한 질문에 이 방법을 돌렸는데, 이는 학계가 여전히 사례별로 풀어내야 하는 문제였다.