에르되시와 확률론적 방법: 우연으로 존재를 증명하기
파울 에르되시는 집도, 통상적인 의미의 직업도, 거의 아무런 소유물도 없었다. 그는 여행 가방 하나를 들고 대학들 사이를 떠돌며 일생을 보냈고, 동료의 문 앞에 나타나 "내 두뇌는 열려 있다"는 말로 인사한 뒤, 수학자들이 오늘날까지도 풀어가고 있는 정리와 미해결 문제의 흐름을 남겼다. 그가 만들어낸 모든 것 가운데, 하나의 아이디어가 증명이 이루어지는 방식 자체를 바꾸어 놓았다는 점에서 단연 돋보인다. 그것은 확률론적 방법이라 불리며, 그 핵심에는 거의 속임수처럼 들리는 한 수가 있다. 무언가를 만들기를 거부함으로써 그것이 존재한다는 것을 증명하는 것이다.
질문: 언제 질서는 피할 수 없는가?
간단해 보이는 수수께끼로 시작하자. 여섯 사람이 모인 파티에서 임의의 두 사람은 친구이거나 낯선 사람이다. 그런데 임의의 여섯 사람 중에서는 언제나 서로 모두 친구인 세 사람, 또는 서로 모두 낯선 세 사람을 찾을 수 있다. 질서가 스스로 나타나도록 강제된다. 이것이 반드시 일어나는 때를 연구하는 수학의 분야가 램지 이론이며, 이 질문에 하나의 수를 붙인다.
램지의 정리는 이 수들이 존재함을 보장하지만, 그것들이 얼마나 큰지는 말해주지 않는다. 자연스러운 후속 질문은 이것이다. 크기 k의 단색 군집을 전혀 만들지 않으면서 그룹은 얼마나 커질 수 있는가? 이에 답하려면 그러한 영리한 색칠이 존재함을 증명해야 한다. 그리고 바로 여기서 손으로 직접 하나를 만드는 일은 가망이 없어진다. 가능한 색칠의 수가 천문학적이기 때문이다.
에르되시의 한 수: 만들지 말고 세어라
1947년 에르되시의 통찰은, 좋은 색칠을 설계하려는 시도를 멈추고 대신 완전히 무작위로 색칠한 다음, 산술이 일하게 두는 것이었다. 그 논증은 전부 따라갈 수 있을 만큼 짧다.
동전을 던져 모든 연결을 칠하라
n명을 두고, 모든 쌍이 변으로 이어진 완전 네트워크를 생각하자. 각 변을 서로 독립적으로 무작위로, 각각 확률 1/2로 빨강 또는 파랑으로 칠한다. 영리함도, 설계도 없다. 그저 변 하나하나마다 공정한 동전 하나뿐이다.
한 그룹이 단색일 가능성을 측정하라
특정한 k명의 집합 하나를 고정하자. 그들 사이에는 C(k,2)개의 변, 즉 k(k-1)/2개의 연결이 있다. 그 모든 변이 단 하나의 색을 공유할 가능성은 낮다. 두 색이 있고 C(k,2)번의 동전 던지기가 모두 일치해야 하므로, 그 확률은 2 × (1/2)^C(k,2)이다. 이 작은 수를 p라 부르자.
나쁜 그룹의 기대 개수를 더하라
걱정해야 할 서로 다른 k명의 그룹은 C(n,k)개 있다. 기대값의 선형성에 의해, 완전히 단색인 그룹의 기대 개수는 단지 그룹의 수에 각각의 확률을 곱한 것이다. 즉 C(n,k) × 2 × (1/2)^C(k,2)이다. 이 하나의 식이, 무작위 색칠이 평균적으로 얼마나 많은 단색 군집을 담을지를 포착한다.
평균이 1보다 작으면, 결함 없는 색칠이 반드시 존재한다
이제 n을 대략 2^(k/2)로 고르자. 그 선택에서는 위의 기대 개수가 1보다 작게 계산된다. 그런데 실제 단색 그룹의 개수는 정수이고, 모든 색칠에 대한 평균이 1보다 작다면 적어도 하나의 색칠은 반드시 0점을 받아야 한다. 그 색칠에는 크기 k의 단색 그룹이 전혀 없다. 따라서 R(k,k)는 n보다 크며, 그것은 약 2^(k/2)이다.
저 마지막 단계를 다시 읽어보라. 그것이 마법의 전부이기 때문이다. 우리는 좋은 색칠을 결코 만들어내지 않았다. 우리는 그것을 결코 묘사하지 않았다. 우리는 평균적인 색칠이 결함 없음에 너무나 가까워서 완벽한 것이 그 더미 어딘가에 존재하도록 강제됨을 보였다. 그 증명은 어떤 특정한 대상도 가리키지 않으면서, 특정한 대상에 대한 확실성을 건네준다.
이것이 왜 혁명적이었나
에르되시 이전에는 무언가가 존재함을 증명하는 일이 거의 언제나 그것을 구성하거나, 적어도 그것을 만들어낼 절차를 묘사하는 것을 뜻했다. 확률론적 방법은 그 기대를 깨뜨렸다. 그것은 무작위성 자체가 증명으로 쓰일 수 있음을 확립했다. 무작위 시도가 0보다 큰 어떤 확률로든 성공한다면, 성공은 가능하다, 그것으로 끝이다.
이 비구성적 성격은 이 논증을 수학에서 가장 우아한 결과들과 같은 부류에 놓는다. 칸토어의 대각선 논법 또한, 명시적 구성이 아니라 순수한 논리적 힘을 통해, 어떤 목록에도 빠진 수라는 무언가의 존재를 증명한다. 둘은 그 조용하고 거의 불안할 만큼의 힘을 공유한다. 결론은 그것이 약속하는 것을 결코 보여주지 않으면서도 빈틈없이 완벽하다. 여기서의 무작위성은 확률을 직관적으로 이해하기에서 다룬 것과 같은 토대 위에 놓여 있으며, 그곳에서는 셋째 단계의 동력인 기대값이라는 개념이 처음부터 차근차근 세워진다.
에르되시 문제들과 그 AI의 순간
에르되시는 정리만 증명한 것이 아니었다. 그는 수백 개의 문제를 제기했고, 까다로운 연습 문제에는 몇 달러부터 진정으로 깊다고 믿은 질문에는 수천 달러까지 이르는 작은 현상금을 종종 걸었다. 그 문제들 중 다수는 여전히 미해결이며, erdosproblems.com에 세심하게 목록화되고 관리되고 있다.
그 안의 선(禪)
확률론적 방법이 아름다운 것은 좋은 마술이 아름다운 것과 같은 이유에서다. 당신은 모든 단계를 지켜보고, 속은 지점을 찾을 수 없으며, 그런데도 결과는 여전히 불가능하게 느껴진다. 손재주의 속임수는 없다. 기대값은 정말로 1보다 작고, 자기 자신의 평균보다 작은 정수는 정말로 어딘가에서 0으로 떨어져야 한다. 확실성은 완전하고, 구성은 부재하며, 그 두 가지가 동시에 참이다.
그것이 에르되시가 남긴 지속되는 교훈이다. 존재와 구성은 같은 것이 아니다. 때로는 완벽한 대상이 저기 있음을 아는 가장 깔끔한 길은, 평균적인 대상이 거의 완벽함을 증명하고 그 간극이 나머지를 하게 두는 것이다. 서로 무관해 보이는 아이디어들을 한 줄이 묶어내는 또 다른 결과로는 오일러 항등식이 반대 종류의 아름다움을 제공한다. 에르되시가 세는 것으로부터 존재를 불러낸다면, 오일러는 정확하고 필연적인 하나의 수를 못 박아낸다.
자주 묻는 질문
- 확률론적 방법이란 무엇인가요?
- 어떤 성질을 가진 대상이 존재한다는 것을, 그 대상을 직접 구성하지 않고 증명하는 방법입니다. 대상의 무작위 버전을 만들고, 그것이 원하는 성질을 가질 확률이 0보다 크다는 것을 보인 뒤, 그러한 대상이 적어도 하나는 반드시 존재한다고 결론짓습니다. 파울 에르되시가 이 기법을 개척했으며, 지금은 조합론과 컴퓨터 과학의 핵심 도구가 되었습니다.
- 에르되시는 이것으로 무엇을 증명했나요?
- 1947년의 기념비적 결과로 그는 램지 수의 하한을 제시했습니다. 즉 대각 램지 수 R(k,k)가 2^(k/2)보다 크다는 것을 보였습니다. 쉽게 말해, 큰 네트워크의 연결을 두 색으로 칠하되 어떤 큰 그룹도 한 색으로만 완전히 연결되지 않도록 하는 방법이 존재한다는 것입니다. 그는 그러한 색칠을 단 하나도 제시하지 않고, 오직 세는 것만으로 그것들이 존재함을 증명했습니다.
- 무언가를 만들지 않고 존재를 어떻게 증명하나요?
- 평균을 이용합니다. 대상을 무작위로 하나 고르고 그것이 가진 결함의 기대 개수를 계산했을 때 그 기대값이 1보다 작게 나온다면, 모음 안의 적어도 하나의 대상은 결함이 0이어야 합니다. 평균 결함 개수가 1보다 작은 무작위 선택은 완벽한 예가 모음 어딘가에 반드시 있음을 보장합니다. 비록 그 논증은 그것이 어느 것인지 결코 가리키지 않지만 말입니다.
- 램지 수란 무엇인가요?
- 램지 수 R(k,k)는 어떻게 배열하든 질서가 나타나도록 강제하는 가장 작은 그룹 크기입니다. 구체적으로 R(k,k)는, 모든 쌍을 친구 또는 낯선 사람으로 어떻게 나누더라도 서로 모두 친구이거나 서로 모두 낯선 사람인 k명의 그룹이 반드시 생기도록 보장하는 가장 작은 인원수입니다. 램지의 정리는 이 수들이 존재한다고 말하며, 에르되시의 방법은 그것들이 매우 빠르게 커진다는 것을 보여줍니다.
- 오늘날 확률론적 방법이 왜 중요한가요?
- 이 방법은 무작위성을 증명 기법으로 바꾸어 놓았고, 그 아이디어는 이제 조합론, 알고리즘 설계, 부호 이론, 이론 컴퓨터 과학 전반에 흐르고 있습니다. 네트워크와 알고리즘에 관한 많은 결과는 여전히 무작위 구성이 양의 확률로 작동함을 보임으로써 증명됩니다. 이 방법은 또한 에르되시 자신의 문제들 가운데 상당수가 지금도 활발한 연구 대상으로 남아 있는 이유이기도 합니다.
