에르되시 팔(Paul Erdős)

에르되시 팔(서양식으로는 폴 에르되시)은 1913년 부다페스트에서 두 수학 교사의 아들로 태어났습니다. 20세기 초의 헝가리는 작은 나라였지만 폰 노이만을 비롯한 뛰어난 수학자와 과학자를 줄줄이 길러 냈고, 학생들은 수학 잡지의 문제를 풀며 자랐습니다. 한편 1920년부터는 유대계 학생의 대학 입학을 제한하는 법이 있었습니다. 1930년 대학에 들어간 에르되시는 도시 공원의 동상 아래 모여 문제를 풀던 젊은 유대계 학생들의 모임에 합류했고, 이 모임에서 20세기 조합론⁠(combinatorics)⁠의 한 줄기가 시작됩니다.

나이 세 ·

그가 태어나기 며칠 전 두 누나가 성홍열로 세상을 떠났고, 1914년 1차 세계대전이 터지자 아버지는 러시아군의 포로가 되어 시베리아에서 6년을 보냈습니다. 어머니는 외아들을 학교에 잘 보내지 않고 집에서 가르쳤고, 그는 어려서부터 머릿속으로 큰 수를 곱했으며 네 살에 사람이 살아온 시간을 초로 셈했다는 이야기가 전합니다. 그를 키운 것은 부다페스트의 수학 문화였습니다. 1894년 창간된 고등학생 수학 잡지(KöMaL)는 달마다 문제를 싣고 풀이를 보낸 학생들의 이름을 실었고, 같은 해 시작된 경시대회는 졸업생들의 실력을 겨뤘습니다. 이 문화 속에서 폰 노이만과 물리학자 실라르드 레오, 위그너 예뇌, 텔러 에데 같은 과학자들이 자랐고, 그들이 미국으로 건너간 뒤 동료들은 반쯤 농담으로 이들을 '화성인'이라 불렀습니다. 에르되시는 1934년 부다페스트 대학에서 푸리에 급수⁠(Fourier series)⁠ 연구로 이름난 수학자 페예르 리포트의 지도로 박사 학위를 받았는데, 페예르는 폰 노이만의 학위 논문도 지도한 사람입니다.

첫 이름은 소수⁠(prime number)⁠에서 얻었습니다. 1932년 열아홉 살의 그는 1보다 큰 모든 n에 대해 n과 2n 사이에 소수가 있다는 베르트랑 공준(1852년 체비쇼프가 처음 증명)에 짧은 새 증명을 내놓았습니다. 열쇠는 이항계수⁠(binomial coefficient)⁠ $\binom{2n}{n}$입니다. 이 수는 $4^n/(2n+1)$보다 작지 않습니다. $(1+1)^{2n} = 4^n$을 펼친 이항계수 2n+1개 가운데 가장 큰 것이기 때문입니다. 그런데 n과 2n 사이에 소수가 하나도 없다면 그 소인수분해⁠(prime factorization)⁠에 들어갈 수 있는 소수와 지수가 너무 제한되어, n이 충분히 크면 수가 그만큼 커질 수 없습니다. 남는 작은 n은 직접 확인합니다. 1939–40년에는 폴란드 출신 수학자 마크 카츠와 함께 서로 다른 소인수의 개수(이를테면 60 = 2² × 3 × 5는 3개)가 어떻게 흩어지는지를 밝혔습니다. 1부터 N까지의 정수⁠(integer)⁠ 가운데 하나를 고르게 뽑아 그 소인수 개수를 세면, N이 커질수록 그 분포가 평균⁠(mean)⁠과 분산⁠(variance)⁠이 모두 약 $\ln\ln N$인 정규분포⁠(normal distribution)⁠에 한없이 가까워진다는 것입니다. 개수들이 $\ln\ln N$을 가운데 두고 종 모양으로 흩어진다는 뜻입니다. $\ln\ln N$은 아주 느리게 자라서, N이 100억이어도 3.1쯤입니다. 가장 결정적인 대상인 소수 속에 중심극한정리⁠(central limit theorem)⁠가 들어앉은 것입니다. 1948–49년에는 노르웨이의 아틀레 셀베르그와 에르되시가, x 이하의 소수의 개수와 x / ln x의 비가 x가 커질수록 1에 다가간다는 소수 정리⁠(prime number theorem)⁠를 복소수⁠(complex number)⁠ 함수⁠(function)⁠의 이론 없이 실수⁠(real number)⁠의 셈만으로 증명하는 '초등적' 증명을 내놓았는데, 두 사람은 결국 따로 발표했고 누구의 몫이 얼마인지를 두고 불편한 논쟁이 뒤따랐습니다.

유대계 젊은이가 헝가리에서 자리를 얻을 길은 좁았습니다. 1934년 그는 영국 맨체스터로 가서 정수론자 루이스 모델의 초청으로 연구원 생활을 했고, 부다페스트에는 방학 때만 돌아왔습니다. 1938년 가을, 나치 독일이 오스트리아를 합병하고 체코슬로바키아를 압박하던 무렵 그는 미국으로 건너가 프린스턴 고등연구소에서 1년짜리 자리를 얻었습니다. 카츠와의 공동 연구도 이 무렵 시작되었습니다. 카츠의 회고로는 1939년 그가 프린스턴에서 소인수 개수의 분포에 관해 강연하자, 청중석의 에르되시가 강연이 끝나기 전에 빠져 있던 정수론⁠(number theory)⁠의 조각을 채워 넣었습니다. 전쟁 동안 그는 미국의 여러 대학을 떠돌았고 헝가리에 남은 가족의 소식은 끊겼습니다. 아버지는 1942년 세상을 떠났고 친척 여럿이 홀로코스트에서 목숨을 잃었으며, 어머니는 숨어 지내며 살아남았습니다.

램지 이론⁠(Ramsey theory)⁠의 둘째 출발점도 부다페스트의 모임이었습니다. 에스테르 클라인이 평면 위에 어느 세 점도 한 직선 위에 있지 않게 찍은 점 다섯 개 가운데 네 개는 늘 볼록 사각형(안쪽으로 파인 곳이 없는 사각형)을 이룬다는 것을 보이자, 에르되시와 세케레시 죄르지는 어떤 n에 대해서도 점을 충분히 많이 찍으면 볼록 n각형이 반드시 생기게 하는 개수가 있음을 증명해 1935년 「기하학의 한 조합 문제」로 발표했습니다. 에르되시는 이것을 '행복한 결말 문제⁠(happy ending problem)⁠'라 불렀는데, 문제를 낸 클라인과 풀이에 매달린 세케레시가 결혼했기 때문입니다. 두 사람은 뒤에 나치를 피해 상하이로 건너가 전쟁을 견디고 오스트레일리아에 자리 잡았습니다. 1947년 에르되시는 반대쪽 한계를 동전으로 얻었습니다. 램지 수⁠(Ramsey number)⁠ R(k)(식으로는 R(k, k))는 점 n개를 모두 선으로 이은 그래프의 선들을 두 색으로 어떻게 칠해도 한 색의 선으로만 서로 이어진 점 k개의 덩어리가 반드시 생기게 하는 가장 작은 n입니다. 이를테면 R(3) = 6입니다. 점 5개로는 한 색 삼각형을 피하는 칠하기가 있지만, 6개면 반드시 생깁니다. 에르되시가 보인 것은 그 아래쪽 한계, 곧 n이 너무 작으면 그런 덩어리를 피하는 칠하기가 있다는 것입니다. 선마다 동전을 던져 빨강과 파랑을 칠하면, 점 k개가 한 색으로만 이어진 덩어리 수의 기댓값⁠(expected value)⁠은 $\binom{n}{k}\,2^{1-\binom{k}{2}}$입니다. k가 3 이상이고 $n \le 2^{k/2}$이면 이 값이 1보다 작습니다. 덩어리 수는 0, 1, 2, … 같은 정수인데 그 평균이 1보다 작으려면 0인 경우가 반드시 있어야 하니, 한 색 덩어리가 하나도 없는 칠하기가 적어도 하나 있습니다. 따라서 $R(k) > 2^{k/2}$입니다. 목록을 보여 주지 않고 존재를 증명하는 이 확률적 방법을 그는 평생 조합론, 정수론, 기하학 곳곳에 퍼뜨렸습니다.

1959년부터는 헝가리의 수학자 레니 얼프레드와 함께, 점 n개 사이에 선을 무작위로 하나씩 더해 가는 그래프를 연구했습니다. 선이 적을 때는 작은 조각들뿐이지만, 선의 수가 점의 수의 절반, 곧 한 점에 평균 한 개의 이웃이 생기는 문턱⁠(threshold)⁠을 넘으면 전체의 일정한 비율을 품는 거대한 연결 덩어리가 나타납니다. 문턱 아래에서는 가장 큰 덩어리도 점 수의 로그 정도 크기에 머뭅니다. 정확히는 n이 커질수록 확률⁠(probability)⁠이 1에 다가간다는 극한⁠(limit)⁠의 진술이고, n이 클수록 이 바뀜이 가파릅니다. 물이 얼음이 되는 것처럼 한 문턱에서 모습이 확 바뀌는 이 현상은 무작위 그래프 이론의 첫 대표 결과였고, 오늘날 좁은 세상⁠(small world)⁠이나 감염병이 퍼지는 연결망을 연구하는 출발점이 되었습니다. 확률과 그래프 이론⁠(graph theory)⁠이 만나는 자리입니다.

당대의 많은 수학자에게 확률적 방법은 영리한 요령 정도로 보였지만, 이 생각은 뒤에 여러 분야로 퍼졌습니다. 수학자 노가 알론과 조엘 스펜서는 1992년 『확률적 방법』이라는 교과서로 이것을 하나의 분야로 정리했고, 컴퓨터 과학에서는 무작위로 골라도 대개 좋다는 논증이 무작위 알고리즘⁠(randomized algorithm)⁠과 계산 복잡도⁠(computational complexity)⁠ 이론의 기본 도구가 되었습니다. 에르되시–레니의 무작위 그래프는 1990년대 말 인터넷과 사회 연결망을 연구하는 연결망 과학의 기준 모형이 되었는데, 동시에 그 한계도 드러났습니다. 1998년 던컨 와츠와 스티븐 스트로가츠는 실제 연결망이 무작위 그래프보다 훨씬 끼리끼리 뭉쳐 있으면서도 거리는 짧다는 것을 보였고, 1999년 물리학자 앨버트라슬로 바라바시와 레카 알베르트는 실제 연결망에는 이웃이 엄청나게 많은 '허브'가 있어서 이웃 수의 분포가 무작위 그래프와 전혀 다르다고 지적했습니다. 무작위 그래프는 틀린 모형이 되었다기보다, 실제 연결망이 얼마나 무작위에서 벗어나 있는지를 재는 기준으로 남았습니다.

냉전은 그의 떠돌이 삶에 국경을 그었습니다. 1954년 암스테르담의 국제수학자대회에 가려던 그에게 매카시 시대의 미국 이민국은 재입국 허가를 내주지 않았고, 그는 1963년까지 미국에 들어가지 못했습니다. 그 사이 그는 이스라엘의 대학들과 영국, 네덜란드를 오가며 지냈고, 헝가리 국적을 지닌 채 철의 장막 양쪽을 드나드는 드문 수학자가 되었습니다. 부다페스트에서는 1950년 레니가 세운 헝가리 과학 아카데미 수학 연구소(지금의 레니 연구소)가 그의 집이나 다름없었습니다. 흔히 에르되시의 말로 알려진 "수학자는 커피를 정리로 바꾸는 기계다"는 레니가 한 말로 전합니다.

그의 삶은 수학만큼 유명합니다. 집도 정해진 직장도 없이 여행 가방 하나를 들고 세계 곳곳 동료의 집을 옮겨 다니며, 도착하면 함께 풀 문제부터 꺼냈다고 합니다. 그렇게 1,500편 가까운 논문을 500명이 넘는 공동 저자와 썼습니다. 수학자들은 에르되시와 함께 논문을 쓴 사람에게 1, 그 사람과 함께 쓴 사람에게 2를 매기는 '에르되시 수⁠(Erdős number)⁠'로 공동 연구 그래프 위의 최단 경로⁠(shortest path)⁠ 길이를 셉니다. 이 이름은 1969년 수학자 캐스퍼 고프먼이 『미국 수학 월보』에 쓴 짧은 글로 널리 퍼졌습니다. 그는 아이들을 아주 작은 양을 뜻하는 '엡실론'이라 부르는 등 자기만의 말을 썼고, 풀지 못한 문제마다 상금을 걸었으며, 신이 가장 아름다운 증명들만 적어 둔 '그 책'이 있다고 즐겨 말했습니다. 1998년 수학자 마르틴 아이그너와 귄터 치글러가 그를 기리며 낸 증명 모음은 제목을 『그 책의 증명들(Proofs from THE BOOK)』이라 붙였습니다.

그의 떠돌이 생활을 받쳐 준 사람들도 있었습니다. 벨 연구소의 조합론자 로널드 그레이엄은 오랫동안 그의 돈과 우편물과 논문을 관리했고 집에 그의 방을 마련해 두었습니다. 에르되시는 오랜 세월 각성제에 기대어 밤낮없이 수학을 했는데, 1979년 그레이엄이 한 달만 끊어 보라고 내기를 걸자 한 달을 채운 뒤 덕분에 수학이 한 달 늦어졌다고 불평했다는 이야기가 전합니다. 1983/84년도 이스라엘의 울프 재단이 주는 울프상을 받았을 때도 상금의 대부분을 장학금으로 내놓았고, 누군가 상금을 건 문제를 풀면 여기저기서 받은 돈으로 값을 치렀습니다. 그는 1996년 9월 바르샤바의 학회에 머물던 중 심장마비로 세상을 떠났습니다.

그가 남긴 문제들은 지금도 수학을 움직입니다. 1930년대에 던진 '불일치 문제'는 2015년 테런스 타오가 풀었습니다. +1과 −1을 끝없이 늘어놓은 수열 x₁, x₂, x₃, …을 어떻게 고르든, 간격 d와 개수 n을 알맞게 골라 $x_d + x_{2d} + \cdots + x_{nd}$의 절댓값⁠(absolute value)⁠을 원하는 만큼 크게 만들 수 있느냐는 물음이고, 답은 '그렇다'였습니다. 1935년 세케레시와 얻은 램지 수의 상한⁠(upper bound)⁠, 곧 R(k)가 $4^k$보다 작다는 결과는 2023년에야 처음으로 밑 4보다 작은 수의 거듭제곱으로 줄었습니다. 그가 문제마다 건 상금의 액수는 수학자들 사이에서 문제의 어려움을 재는 눈금처럼 쓰였습니다. 폴 호프먼이 1998년 펴낸 전기(한국어판 『우리 수학자 모두는 약간 미친 겁니다』)는 그를 수학 밖에도 널리 알렸습니다.

이어지는 곳. 램지 이론은 램지가 1928년 논리학 문제의 보조정리⁠(lemma)⁠로 증명한 정리에서 출발했고, 칸보다 물건이 많으면 어느 칸엔가 둘이 들어간다는 비둘기집 원리⁠(pigeonhole principle)⁠가 그 가장 작은 경우입니다. 1936년 투란 팔과 함께 던진 밀도 질문, 곧 자연수⁠(natural number)⁠ 가운데 일정한 비율 이상을 차지하는 집합⁠(set)⁠에는 3, 7, 11, 15처럼 같은 간격으로 늘어선 수(등차수열⁠, arithmetic progression⁠)가 원하는 만큼 길게 들어 있느냐는 물음은 1975년 세메레디 엔드레의 정리로 풀렸고 에르되시는 걸어 둔 상금을 건넸습니다(반 데르 바르던 정리⁠(van der Waerden's theorem)⁠). 역수⁠(inverse)⁠의 합이 발산⁠(divergence)⁠하는 자연수 집합에는 임의 길이의 등차수열이 있으리라는 그의 추측은 조화급수⁠(harmonic series)⁠와 오일러가 보인 소수 역수 합의 발산에서 나온 물음입니다. 길이 3인 경우는 2020년 토머스 블룸과 올로프 시사스크가 증명했지만 일반적인 경우는 아직 열려 있습니다. 무작위로 고른 것이 평균적으로 좋다는 논법은 한 해 뒤 섀넌이 통로 부호화 정리⁠(noisy-channel coding theorem)⁠에서 쓴 무작위 부호와 같은 생각이며, 무작위가 증명과 계산의 도구가 되어 간 이야기는 무작위성에 모았습니다.

관계.

• 영향을 받음 스리니바사 라마누잔 — 하디와 라마누잔이 1917년 보인 '보통의 수 n은 대략 ln ln n개의 소인수를 가진다'는 결과를, 에르되시는 카츠와 함께 소인수 개수가 정규분포를 따른다는 법칙으로 다듬었습니다.
• 영향을 받음 프랭크 램지 — 세케레시가 1935년 논문을 준비하며 램지의 1928년 정리를 다시 발견했고, 에르되시는 평생 그 둘레의 문제들을 '램지 이론'이라는 분야로 키웠습니다.
• 영향을 받음 레온하르트 오일러 — 오일러가 보인 '소수의 역수를 모두 더하면 발산한다'는 사실은, 역수의 합이 발산하는 집합에는 임의 길이의 등차수열이 있으리라는 에르되시의 추측이 출발한 곳입니다.

연표.

• 1930년 부다페스트 공원의 문제 모임에 합류하다
• 1932년 n과 2n 사이에 소수가 있다는 베르트랑 공준⁠(Bertrand's postulate)⁠에 새 증명을 내다
• 1934년 박사 학위를 받고 맨체스터로 가다
• 1935년 세케레시와 「기하학의 한 조합 문제」를 발표하다
• 1938년 프린스턴 고등연구소로 옮기다
• 1940년 카츠와 함께 소인수 개수의 정규분포 법칙을 발표하다
• 1947년 동전 던지기 논증으로 램지 수의 하한⁠(lower bound)⁠을 얻다
• 1949년 소수 정리의 초등적 증명에 이르다
• 1954년 미국 이민국이 재입국 허가를 내주지 않아 미국을 떠나다
• 1959년 레니 얼프레드와 무작위 그래프를 연구하기 시작하다
• 1963년 다시 미국에 들어가다
• 1984년 1983/84년도 울프상을 받다
• 1996년 9월 바르샤바의 학회에 머물던 중 세상을 떠나다