d라이브러리

인터넷에서 여러 수학자가 힘을 합쳐 난제를 푸는 폴리매스 프로젝트의 10번 문제인 해바라기 추측이 오늘 소개할 연구입니다. 해바라기 추측은 아직 해결되지 않았지만, 이 추측의 따름정리격인 약한 해바라기 추측이 2016년 8월호에 소개한 새로운 도구 덕분에 풀렸습니다.


서로 다른 집합 A1, A2, …, Ar에서 어느 두 집합에 속한 원소가 무조건 모든 집합에 다 속하면 이 집합들을 ‘해바라기’라고 합니다.

집합 A1, A2, …, Ar 각각은 ‘해바라기의 꽃잎’이라고 하지요. 예를 들어 {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 2, 6}은 꽃잎이 4개인 해바라기입니다.

1960년 에르되시 팔과 리처드 라도는 크기가 같은 집합을 충분히 많이 모으면 어떻게 모으더라도 꽃잎의 개수가 r개인 해바라기가 반드시 있다는 것을 증명했습니다. 조금 더 엄밀하게 이야기하면 다음 성질을 만족하는 함수 f(k, r)이 있다는 거지요.
 

에르되시와 라도의 해바라기 정리
원소의 개수가 k개인 서로 다른 집합을 f(k, r)개 보다 많이 모으면,
그 중에 반드시 꽃잎이 r개인 해바라기가 있다.
 

이 정리는 비교적 간단하게 증명할 수 있습니다. 증명을 토대로 f(k, r)을 k!(r-1)k으로 잡을 수 있지요. 문제는 이 f(k, r)이 최적이냐는 겁니다. 에르되시와 라도 역시 최적인지를 밝히기 위해 노력했지만 답을 찾지 못했습니다. 다만 f(k, r)이 (r-1)k보다 작을 때 꽃잎이 r개인 해바라기가 없을 수 있다는 것을 알아냈습니다. 결국 최적인 f(k, r)은 (r-1)k과 k!(r-1)k 사이지요. 이어 에르되시와 라도는 최적인 f(k, r)은 (r-1)k처럼 지수함수라고 생각하고 다음과 같이 추측했습니다.
 

에르되시와 라도의 해바라기 추측
모든 k에 대해 f(k, r)≤crk를 만족하는 상수 c1, c2, c3, …가 있다.

 

에르되시도 인정한 어려운 문제
해바라기 추측은 어렵기로 악명이 높습니다. 에르되시는 미해결 문제에 상금을 걸기로 유명한데, 쉬워 보이는 문제에는 1달러처럼 낮은 상금을 걸고 어려운 문제에는 1000달러를 걸었습니다. 그런데 이 문제는 r=3인 경우만 풀어도 1000달러를 주겠다고 약속했습니다. 문제가 나온 지 50년이 지났지만 아직까지 1000달러의 주인공은 나타나지 않았지요. 지금까지 가장 좋은 결과는 1996년 알렉산드르 코스토치카가 알아낸 것으로, 다음처럼 무시무시하게 생긴 부등식입니다.

에르되시와 세메레디의 해바라기 추측
{1, 2, …, n}의 서로 다른 부분집합 1.99n개를 모으면
그 중에 반드시 꽃잎이 3개인 해바라기가 있다.
 

원소가 n개인 집합의 부분집합 총 개수는 2n개 입니다. 따라서 부분집합을 1.99n개나 뽑았으면 대부분의 부분집합을 뽑은 것일 테니 꽃잎이 3개짜리인 해바라기 정도는 당연히 있을 거라고 생각하기 쉽습니다. 하지만 1.99n과 2n은 엄청난 차이가 있습니다. 예를 들어 1.99n을 2n으로 나누면 n이 충분히 클 때 0에 가까운 수가 됩니다. 따라서 n이 충분히 크면 1%도 안 되는 부분집합만 뽑은 셈이 되지요.

1978년에 제기된 약한 해바라기 추측 역시 무려 38년간 미해결 문제였습니다. 2016년 6월 갑작스럽게 이 문제의 해법이 나왔습니다. 답을 찾은 주인공은 미국 프린스턴대학교 대학원생이었던 에릭 나슬런드와 윌리엄 사윈입니다. 그렇게 어려운 문제였는데, 증명은 1쪽밖에 되지 않습니다. 더욱이 나슬러드와 사윈은 1.99를 1.89까지 낮춰 다음과 같은 정리를 만들었습니다.
 

{1,2,…,n}의 서로 다른 부분집합 1.89n개를 모으면
그 중에 반드시 꽃잎이 3개인 해바라기가 있다.

 

신형 도구 위력
도대체 어떤 방법으로 악명 높은 문제를 간단히 풀었을까요? 바로 ‘세트’ 게임을 풀 때 나온 새로운 도구로, 2016년 5월 수학계에서 크게 화제가 된 방법입니다. 2016년 수학동아 8월호에서 이 도구에 대해 다뤘었지요.

어니 크루트와 프세볼로드 레브, 피터 파흐는 세트 게임에서 서로 다른 카드의 수가 3n개일 때 세트가 없는 최대 카드수인 D(n)과 관련된 문제를 푸리에 변환을 쓰는 원래 방법이 아닌 새로운 방법으로 풀었습니다. 다항식과 선형대수학만 써서 문제를 푼 것인데, 폴리매스 프로젝트를 처음 제안한 티머시 가워스가 이 도구를 도구상자에 저장했다가 적재적소에 써야 한다고 말했을 정도로 획기적이고 유용합니다.

조던 엘렌버그와 디온 헤이스베이트가 곧바로 이 도구를 써서 n이 커질 때 D(n)이 얼마나 커지는지 밝혔습니다. 그런데 비슷한 시기에 이 도구를 쓴 수학자가 또 있었던 겁니다.

나슬런드와 사윈은 엘렌버그와 헤이스베이트의 증명을 새로운 시각에서 해설한 테렌스 타오의 블로그 글을 보고 새로운 도구에 대해 알았습니다. 그리고 여기서 아이디어를 얻어 약한 해바라기 추측을 해결했습니다.
 

수학 발전 돕는 인터넷의 힘
새로운 도구가 5월 5일에 나왔고, 약한 해바라기 추측의 논문이 6월 30일에 아카이브(논문 등록 웹사이트)에 올라왔으니 이 모든 일이 두 달도 채 되지 않은 사이에 벌어졌습니다. 1970년대만 해도 정보 공유가 제대로 되지 않아 이미 증명된 사실을 몇 년 후에 다른 사람이 또 증명하기도 했는데, 이제는 그렇지 않습니다. 인터넷이 발전하다 보니 수학계에서 새로운 연구 도구가 눈 깜빡할 사이에 퍼지고, 오래된 난제가 불과 한두 달 사이에 풀리는 일이 여럿 생기고 있습니다.

저 또한 엘렌버그와 헤이스베이트의 논문을 꼼꼼히 읽고, 그 내용을 강의하기도 했습니다. 이 새로운 도구를 써서 풀 수 있는 문제가 얼마나 더 있는지 대단히 궁금합니다. 여러분들도 함께 생각해보면 좋겠습니다.


엄상일 교수는 KAIST 수학과를 졸업하고, 미국 프린스턴대학교에서 박사 학위를 받았습니다. 현재는 KAIST에서 강의와 연구를 하고 있습니다. 그래프이론과 이산수학, 조합적 최적화가 주요 연구 분야입니다. 2012년에는 젊은과학자상(대통령상)을 수상했고, 2017년에는 한국차세대과학기술한림원 회원으로 선정됐습니다.