‘불규칙에서 규칙성 찾은’ 수학자, 아벨상 수상자로

한겨레에 실린 글 ‘불규칙에서 규칙성 찾은’ 수학자, 아벨상 수상자로를 옮겨 놓는다.

수학자 세머레디의 ‘무작위와 규칙성’의 수학 “불규칙해 보여도 규모가 충분히 크다면 거기엔 규칙성 있다”

헝가리 출신 수학자 세머레디(71, Endre Szemerédi) 교수가 수학계의 노벨상이라고 할 수 있는 아벨상의 수상자로 결정되었다. 아벨상은 수학자 아벨의 이름을 따서 노르웨이 왕실에서 해마다 매우 큰 업적을 남긴 수학자에게 수여하는 상으로 600만 노르웨이 크로네(원화로 약 11억 원)의 상금이 있는 명예로운 상이며 2003년에 첫 상이 수여되었다. 앞으로 2년 뒤에 서울에서 열릴 국제수학자대회(ICM)에서 수여되는 필즈상은 40세 이하의 수학자만 받을 수 있지만, 아벨상은 노벨상처럼 나이 제한이 없다.

세머레디 교수의 전공 분야는 이산수학 혹은 조합수학이라 불리는데, 특히 극단 조합론(Extremal Combinatorics) 분야를 많이 연구하였다. 수많은 공저자를 가진 수학자로 잘 알려진 에르디시의 영향으로 헝가리 수학자들이 전통적으로 강한 분야이다. 200여 편의 논문을 쓰고 아울러 일흔이 넘은 지금도 여전히 연구에 매진하는 세머레디 교수의 연구결과를 모두 소개하는 것은 매우 어렵다. 하지만 수학의 다른 분야에 비해 상대적으로 이산수학의 문제들은 풀기는 매우 어렵더라도 누구나 쉽게 이해할 수 있는 경우가 많다.

이 글에서는 세머레디의 가장 잘 알려지고 중요한 업적인 ‘등차수열이 있을지’에 관한 연구와 그 과정에서 파생되었으나 수많은 응용을 낳은 “규칙성 보조정리”라는 것에 관해 다루고자 한다.

긴 등차수열 찾기

3, 6, 9, 12, 15나 5, 8, 11, 14처럼 같은 수를 계속 더해서 나오는 수들을 나열한 것을 등차수열이라고 한다. 이제 철수와 영희가 다음과 같은 게임을 한다고 하자. 1부터 15까지 수 중 1/3을 영희가 마음대로 뽑았을 때 그중에 3개의 서로 다른 수로 이루어진 등차수열이 있으면 철수가 이기고, 그러한 등차수열이 없으면 영희가 이긴다.

예컨대 영희가 2, 4, 5, 8, 12를 뽑는다면 이 중에 4, 8, 12가 길이가 3인 등차수열이 되므로 영희가 지게 되지만, 1, 3, 6, 7, 10을 뽑는다면 여기에는 길이가 3인 등차수열이 없어서 영희가 이기게 된다. 어쨌든 이 경우 영희 입장에서는 1, 3, 6, 7, 10만 뽑기만 하면 이길 수 있으니 철수에게는 매우 불리한 게임이다. 철수를 위해서 이번에는 15를 100 정도의 큰 수로 바꿨다고 생각해 보자. 이때는 철수가 이길 수 있을까?

100도 부족하다면 그보다 훨씬 더 큰 충분히 큰 수 N으로 바꾼다면 철수가 이길 수 있을까? 영국의 수학자인 로스는 1953년에 N이 충분히 크다면 이 게임에서는 항상 철수가 이긴다는 것을 증명하였고, 이 업적으로 1958년에 필즈상을 받았다. 로스는 심지어 1/3 대신 1%든 0.001%든지 아무리 작은 비율로 게임을 만들더라도 N이 충분히 크기만 하다면 1부터 N까지 수 중에 그 비율의 수를 아무렇게나 뽑더라도 그 수 중에는 길이 3인 등차수열이 있어서 철수가 이기게 된다고 증명하였다.

세머레디는 1975년, 이 로스의 결과에서 3을 10이든 10000이든 어떤 수로 바꿔도 N만 더 크게 잡으면 된다는 것을 증명하였다. 예를 들어 1부터 N까지 수 중에 0.1%를 어떻게 뽑든지 간에 N이 충분히 크기만 하다면 길이가 100인 등차수열이 반드시 있다는 것이다. 이 문제는 원래 헝가리의 두 수학자 에르디시와 튜란이 1936년에 물어본 것인데, 세머레디가 증명하기 전까지 무려 39년 동안 미해결 문제로 남아 있었다. 놀라운 점은 이 세머레디의 증명은 복잡하긴 해도 현대수학의 깊은 지식이 없이도 읽을 수 있을 정도의 기본적인 수학만 사용한다는 것이다.

영국 케임브리지대학의 그린(35) 교수와 미국 로스엔젤레스 캘리포니아대학(UCLA)의 타오(36) 교수는 세머레디의 아이디어를 확장하여 2, 3, 5, 7, 11과 같은 소수들의 수열에는 원하는 길이의 등차수열이 항상 있다는 것을 증명하였다. 이 결과는 타오 교수가 2006년에 필즈상을 받을 때 언급된 중요한 업적 중 하나이다. 이처럼 세머레디의 결과는 현재까지도 많이 연구되고 다뤄지는 중요한 연구들의 시금석이 되었다.

불규칙해 보여도 규모 충분히 크다면 거기엔 규칙성이 있다. 숫자를 많이 모으기만 해도 원하는 길이의 등차수열이 항상 있다는 세머레디의 결과는 이산수학에서 알려진 다른 여러 결과들과 유사한 점들이 많다.

예를 들어 충분히 많은 점을 찍으면 그 점 중에 100개를 잘 뽑으면 그 점들로 만들어지는 100각형의 모든 내각이 180도보다 작게 만들 수 있다거나, 충분히 많이 숫자를 나열하면 그중에 점을 잘 뽑으면 숫자가 증가하거나 감소하는 숫자 10개짜리 수열을 만들 수 있다거나 하는 식의 정리들은 20세기 초반부터 알려져 있었다.

세머레디의 다른 중요한 업적으로 흔히 “세머레디의 규칙성 보조정리(Szemerédi regularity lemma)”라고 불리는 것이 있다. 이것은 앞에 설명한 등차수열에 관한 결과를 증명하는 데 사용된 것인데 이산수학, 정수론, 이론 전산 분야에 많은 파급 효과를 가지고 왔다. 이산수학, 특히 그래프이론에서 흔히 다루게 되는 그래프라는 것은 꼭짓점들과 그 꼭짓점을 잇는 선으로 구성된 수학적 대상인데, 그래프이론에서는 그 선이 어떻게 구부러지는지에 관심 있는 게 아니라 꼭짓점 어느 것과 어느 것이 이어졌는지에만 관심을 갖는다.

예를 들어 수도권 지하철 노선도를 나타낼때 실제 역의 위치를 그대로 지도에 그리는 게 아니라 지하철역을 점으로, 두 역이 지하철 노선에서 이웃하면 선으로 이은 방식으로 간단한 그림으로 표현한다. 이렇게 하여 역과 역의 연결관계를 손쉽게 파악할 수 있고 쉽게 갈아타는 역을 찾을 수 있다.

세머레디의 규칙성 보조정리는 이러한 그래프에 관한 정리이다.

아주 대충 이 정리의 특수 경우를 설명하자면, 꼭짓점이 충분히 많은 모든 그래프는 꼭짓점들을 10가지 분류로 비슷한 크기로 잘 나누되, 서로 다른 분류에 속한 꼭짓점들 사이에 있는 선의 수는 마치 두 분류 사이에 선이 생길 빈도를 미리 정해놓고 그 빈도에 맞게 주사위를 던져 선을 그은 것에서 많이 벗어나지 않는다는 식이다.

물론 10을 다른 숫자로 바꾸는 것도 가능하다. 이것을 이용하면 꼭지점 수가 충분히 큰 모든 그래프에 대해 대략의 구조가 항상 존재한다는 것을 알 수 있어서 이것을 이용하여 수많은 문제들이 해결되었다. 이 규칙성 보조정리는 현재도 수많은 응용과 확장, 다양한 증명방법이 연구되고 있다. 특히 정답을 할 확률이 어떤 확률 이상이 되는 것이 보장된다는 식의 확률적 알고리듬을 만드는 연구에서 이 규칙성 보조정리가 중요하게 사용되고 있다.

한국에서도 필즈상, 아벨상 수상자가 나오길 기원하며

이번 아벨상 수상은 인구 천만 명 정도를 지닌 헝가리가 배출한 수학자로는 2005년 랙스 교수에 이어 2번째 수상자이며 헝가리 신문들은 인터넷 뉴스에서 머리기사로 다루었다고 한다. 헝가리의 수학적 전통은 매우 오래된 것으로, 100년 넘는 역사를 자랑하는 수학경시대회도 있고, 한때는 헝가리 공중파 텔레비전 방송에서 수학경시대회를 열어 중계방송을 하고, 최종 결선에 출연한 학생은 마치 연예 프로그램의 스타처럼 국가적 관심을 받았다고 한다.

헝가리 수학계에 큰 영향을 끼친 수학자 에르디시는 수학에 재능 있는 영재들을 일찍부터 발굴하고 수학계로 이끌었는데, 그 중에 현재까지 수학계에 널리 알려진 대가들이 많다. 세머레디 역시 에르디시에 의해 재능이 발견된 학생이었다고 한다. 인구 4900만 명인 한국에서는 아직 아벨상이나 필즈상 수상자가 나오지 않았다.

하지만 우리나라에서 수학이 제대로 교육되고 연구된 전통은 이제 고작 수십 년밖에 안 된 것이고 최근 들어 매우 급속도로 수학계가 발전하고 있으며, 이를 인정받아 국제수학자대회(ICM)를 2014년 서울에서 개최하는 등의 추세를 볼때, 앞으로 훌륭한 수학자들이 많이 탄생할 것으로 기대된다. 헝가리에 비해 늦게 시작하였지만 한국에서도 수학에 재능 있는 많은 학생들이 발굴되고 육성되어 큰 발자취를 남기는 한국인 수학 대가들이 많이 탄생하기를 바란다.