엔드레 세메레디: 모든 혼돈 속에는 질서가 있다

의과대학에 입학한 지 6개월 만에 엔드레 세메레디(Endre Szemerédi)는 자신이 메스를 다룰 자신이 없다고 판단했습니다. 그는 훗날 “그런 막중한 책임을 지는 일을 할 수 있을지” 의구심이 들었다고 말하며 의대를 떠났습니다. 한동안 방황하던 그는 수학을 공부하기로 했고, 행정적 실수로 인해 전혀 요청한 적 없는 박사 지도교수를 배정받았습니다. 그 서류상의 실수 덕분에 그는 자신이 원했던 알렉산더 겔폰드(Alexander Gelfond)가 아닌, 20세기 위대한 수학자 중 한 명인 이스라엘 겔판트(Israel Gelfand) 밑에서 모스크바에서 공부하게 되었습니다. 이는 수학 분야에서 가장 훌륭한 사고(事故) 중 하나입니다.

부다페스트에서 모스크바까지, 실수로 이어진 길

세메레디는 1940년 8월 21일 부다페스트에서 태어났습니다. 의대 진학을 짧게 포기한 후, 그는 부다페스트의 외트뵈시 로란드 대학교(Eötvös Loránd University)에서 학사 학위를 받았고, 이후 모스크바 국립 대학교에서 석사 및 박사 학위를 취득했습니다. 그곳에서 그는 자신을 잘못된 지도교수에게 보낸 행정적 실수의 주인공인 겔판트 밑에서 이산수학 분야의 경력을 시작했으며, 결국 조합수학 분야에서는 드물게 필즈상에 버금가는 인정인 아벨상(Abel Prize)을 받게 되었습니다.

그의 이름을 딴 정리

1975년에 발표된 세메레디의 결정적인 업적은 폴 에르되시(Paul Erdős)와 투란 팔(Pál Turán)이 수십 년 전에 제기했으나 그간 모든 증명 시도를 거부했던 추측을 해결한 것입니다. 그 추측은 양의 상밀도를 가진 자연수의 모든 집합—대략적으로 말해, 전체 수 직선상에서 전혀 희석되지 않는 모든 집합—은 길이가 얼마든 상관없이 모든 길이의 등차수열을 포함해야 한다는 것이었습니다. 이는 숨겨진 질서에 관한 진술입니다. 아무리 불규칙하거나 듬성듬성해 보이는 실수의 집합이라도, 그 안에는 반드시 패턴이 있는 수열이 묻혀 있다는 것입니다. 아벨상 위원회는 훗날 그의 연구 정신을 한 문장으로 요약했습니다. “모든 혼돈 속에는 질서가 있다.”

정칙성 보조정리

그 정리의 증명 과정은 정리 자체보다 훨씬 더 큰 결과를 낳았습니다. 그 과정에서 세메레디는 오늘날 '세메레디 정칙성 보조정리(Szemerédi regularity lemma)'라고 불리는 것을 도입했습니다. 이는 충분히 큰 모든 그래프가 통계적으로 거의 무작위처럼 보이는 유한한 수의 조각으로 분할될 수 있음을 보여주는 구조적 결과입니다. 이는 기술적인 보조정리처럼 들리지만, 현대 조합수학의 핵심 도구 중 하나가 되어 속성 테스트, 그래프 극한 이론, 그리고 그 후 수십 년간 발전한 극값 그래프 이론의 상당 부분을 뒷받침하게 되었습니다. 티모시 고어스(Timothy Gowers)와 로바스 라슬로(László Lovász)를 포함한 필즈상 수상자들은 그 결과의 추적에 전 강의를 할애하기도 했습니다. 이는 증명의 부산물이 원래의 정리보다 더 큰 영향력을 갖게 된 희귀한 사례입니다.

이름이 붙은 연구 결과들

세메레디의 경력은 오늘날 협력자들과 함께 그의 이름을 딴 많은 결과를 낳았습니다. 평면 위의 점과 선이 만나는 횟수의 상한을 정한 발생 기하학의 세메레디-트로터 정리(Szemerédi–Trotter theorem), 그래프 색칠 문제의 하이날-세메레디 정리(Hajnal–Szemerédi theorem), 산술 조합수학 분야의 기초가 된 유한 집합의 합과 곱에 관한 에르되시-세메레디 정리(Erdős–Szemerédi theorem), 그리고 미클로시 아이타이(Miklós Ajtai)와 함께한 코너 정리(corners theorem)가 그것입니다. 그는 아이타이와 야노스 콤로시(János Komlós)와 함께 램지 수(Ramsey numbers)에 대한 영향력 있는 한계를 설정하고 최적 깊이의 정렬 네트워크를 구축했는데, 이는 순수 수학에서 이론 컴퓨터 과학으로의 드문 외도였으며 그가 컴퓨터 과학과에 자리를 잡는 근거가 되었습니다. 또한 아이타이, 바츨라프 흐바탈(Václav Chvátal), 먼로 뉴본(Monroe Newborn)과 함께 그래프 드로잉의 기초적 한계인 교차 수 부등식(crossing number inequality)을 증명했습니다. 출판된 200편 이상의 논문을 관통하는 주제는 일관됩니다. 겉보기에는 무질서해 보이는 대상(정수 집합, 그래프, 점 구성) 내부에 엄격하고 불가피한 구조를 찾아내는 것입니다.

헝가리의 토대 위에 세운 미국의 경력

세메레디는 1986년 럿거스 대학교(Rutgers University)의 뉴저지 주립 컴퓨터 과학 교수로 부임하여 현재 명예교수직을 유지하고 있으며, 20세기 중반 이후 헝가리 수학의 본산인 부다페스트의 알프레드 레니 수학 연구소(Alfréd Rényi Institute of Mathematics)와도 계속 관계를 맺고 있습니다. 그 사이 그는 스탠퍼드, 맥길, 사우스캐롤라이나 대학, 시카고 대학에서 객원 교수를 역임했으며 프린스턴 고등연구소(Institute for Advanced Study)의 회원이기도 했습니다. 이는 냉전 시대 헝가리와 소련권에서 미국 연구 대학으로의 수학적 이주를 아우르는 경력입니다.

인정

50년에 걸쳐 쌓인 영예는 다음과 같습니다. 정리 발표 직후인 1973년의 알프레드 레니 상과 1975년의 조지 폴리아 상(George Pólya Prize), 2008년의 르로이 P. 스틸 상(Leroy P. Steele Prize)과 롤프 쇼크 수학상(Rolf Schock Prize), 2010년 미국 국립과학원 회원 선출, 그리고 2012년의 아벨상 수상입니다. 아벨상은 “이산수학 및 이론 컴퓨터 과학에 대한 근본적인 기여와 가법 수론 및 에르고딕 이론에 미친 심오하고 지속적인 영향”을 인정받아 수여되었으며, 이는 그의 연구가 좁은 의미의 조합수학을 넘어 여러 분야를 재구성했음을 명시적으로 인정하는 것입니다. 헝가리는 2020년 그에게 성 이슈트반 훈장(Order of Saint Stephen)을 수여했습니다.

엔드레가 천재라고 불리는 이유

세메레디의 천재성에 대한 증거는 수학계에서 제시할 수 있는 가장 명확한 사례 중 하나입니다. 단 하나의 오래된 추측에 대한 단 하나의 증명에서 파생된 도구(정칙성 보조정리)가, 그 증명 대상인 정리 자체보다 더 큰 영향력을 갖게 된 것입니다. 방법론이 원래의 목적보다 더 오래 살아남고 커지는 이러한 2차 영향력은, 눈앞의 문제만 해결하는 것이 아니라 가장 깊은 구조적 수준에서 작동하는 정신을 보여주는 가장 확실한 지표 중 하나입니다. 아벨상 위원회의 언어인 '혼돈 속에서 질서를 찾는다'는 것은 과장이 아닙니다. 그것은 정칙성 보조정리가 실제로 하는 일에 대한 공정한 설명이며, 고어스와 로바스 같은 분야의 거장들이 그의 결과의 결과를 설명하는 데 상당한 강의 시간을 할애했다는 사실은 인위적으로 만들어내거나 부풀릴 수 없는 동료들의 찬사입니다.

주의할 점이 있다면 과장이 아니라 좁은 범위에 관한 것입니다. 세메레디의 명성은 압도적으로 이산수학 및 조합수학의 결과물에 기초하고 있는데, 이 분야들은 20세기 대부분 동안 수학계 주류로부터 해석학, 기하학, 정수론보다 덜 권위 있는 것으로 간주되었습니다. 조합수학자에게 아벨상을 수여한 것 자체가 당시에는 그 분야가 오랫동안 받지 못했던 인정을 받아야 한다는 암묵적인 주장으로 읽혔습니다. 이것이 그의 업적을 깎아내리는 것은 아닙니다. 이는 여기서 말하는 '천재'라는 라벨이 물리나 수학 분야의 일반적인 명성과 달리, 특정하고 기술적인 구조적 통찰력에 대한 것이라는 점을 의미합니다.

유산

정칙성 보조정리는 현재 전 세계 대학원 조합수학 과정에서 표준 자료로 가르치고 있으며, 세메레디가 1975년 처음 작성했을 당시에는 존재하지 않았던 이론 컴퓨터 과학, 가법 조합수학, 그래프 극한 이론과 같은 영역을 포함한 새로운 연구의 활발한 원동력으로 남아 있습니다. 80대 중반의 나이에도 명예교수로서 활동 중인 그는, 하나의 증명 방식이 그것이 설계된 정리보다 더 큰 영향을 미치게 된 현대 수학의 가장 명확한 사례로 남아 있습니다.