메뉴바로가기본문바로가기

동아사이언스

[주말N수학]협력의 힘을 발휘하다

통합검색

[주말N수학]협력의 힘을 발휘하다

2019.11.16 06:00

 

집합의 벤 다이어그램이 마치 해바라기와 같아 ‘해바라기의 꽃잎’과 ‘해바라기’라 불리는 집합이 있습니다. 이와 관련된 문제인 ‘에르되시-라도의 해바라기 추측’은 어렵기로 악명이 높아 문제에 상금도 걸려 있습니다. 그런데 최근 이 문제에 성과가 있었습니다. 문제가 완전히 풀린 건 아니지만 기존에 알려진 것보다 더 좋은 결과입니다. 

 

여러 개의 집합 S₁, S₂,…, S_{r} 에서 S₁∩S₂, S₁∩S₃, S₁∩S_{r}, S₂∩S₃, …, S_{r-1}S_{r}이 모두 같은 집합이면 S₁, S₂, …, S_{r}의 모임을 ‘해바라기’라고 부릅니다. 각각의 집합 S₁, S₂, …, S_{r}은 ‘해바라기의 꽃잎’이라고 합니다. 예를 들어 위 그림 {1, 2, 3}, {1, 2, 4, 5}, {1, 2, 6, 7}, {1, 2, 8}, {1, 2, 9}는 꽃잎이 5개인 해바라기입니다. 해바라기 꽃을 생각해보면 왜 이런 이름을 붙였는지 상상할 수 있습니다. 

 

1960년 헝가리 수학자 에르되시 팔과 독일 수학자 리하르트 라도는 크기가 같은 집합이 아주 많이 모여 있으면 그중에 꽃잎이 r개인 해바라기가 반드시 있다는 것을 증명했습니다. 즉 다음과 같은 성질을 만족하는 함수 f(k,r)이 있다는 것을 밝혔습니다.

 

이 정리는 꽤 유용합니다. 필자 또한 연구하면서 집합이 복잡하게 얽혀있을 때 상황을 간단하게 정리하기 위해서 사용합니다.


에르되시와 라도는 논문에서 f(k,r)k!(r-1)^{k}이면 된다고 증명합니다. 하지만 이 값이 최적이라고 생각하지는 않았습니다. 만약 f(k,r)을 위의 성질을 만족시키는 최솟값이라고 하면 에르되시와 라도의 결과는 f(k,r)k!(r-1)^{k}이라고 표현됩니다. 


에르되시와 라도는 같은 논문에서  f(k,r)(r-1)^{k}라는 것도 예를 찾아서 보입니다. 그리고 만일 r이 고정돼 있다면  f(k,r)(r-1)^{k}처럼 지수함수 형태이면 되지 않겠냐고 추측합니다. 그게 바로 ‘에르되시-라도의 해바라기 추측’입니다.

 

문제의 일부만 풀어도 상금


거의 60년이 다 돼가는 이 문제는 아직도 해결될 기미가 보이지 않습니다. 그만큼 문제가 어렵다는 뜻입니다. 에르되시는 r=3인 경우만 풀어도 상금을 1000달러 주겠다고 했습니다. 에르되시는 문제의 난이도에 따라 1달러부터 5000달러까지 상금을 걸기로 유명합니다. 이 문제는 온라인에서 난제를 함께 푸는 폴리매스 프로젝트의 10번 문제이기도 합니다. 


에르되시-라도 해바라기 추측은 1996년 러시아 수학자 알렉산드로 코스토치카가 결과를 낸 이후에 한동안 이렇다 할 결과가 나오지 않았습니다. r이 3일 때를 포함한 모든 r에 대해 코스토치카의 결과가 약 20년  동안 최고였습니다.


그러던 2017년 ‘약한 해바라기 추측’이 풀립니다. {1, 2, …, n}의 서로 다른 부분집합 1.89ⁿ개를 모으면 그중에 반드시 꽃잎이 3개인 해바라기가 있다는 것으로, 당시 미국 프린스턴대 대학원생이던 수학자가 해결합니다. ('폴리매스 프로젝트 10번 해바라기 추측' 수학동아 2017년 5월호 참고 http://dl.dongascience.com/magazine/view/M201705N005) .


하지만 약한 해바라기 추측이 풀렸다고 에르되시-라도의 해바라기 추측이 증명된 건 아닙니다. r=3일 때 조차 미해결로 남아있지요. 최근까지 큰 진전이 없다가 2018년에 일본 수학자 준이치로 후쿠야마가 r이 3일 때 기존 값을 개선한 결과를 내놓았습니다. 

 


대학생도 참여한 연구 

 

최근 에르되시-라도의 해바라기추측에서 의미있는 결과를 낸 중국 북경대 대학생 우커원. 우커원 제공
최근 에르되시-라도의 해바라기추측에서 의미있는 결과를 낸 중국 북경대 학생 우커원. 우커원 제공

2019년 8월 말 인터넷에 모든 r에 대해 성립하는 놀라운 결과가 올라왔습니다. 연구의 주인공은 라이언 알웨이스 미국 프린스턴대 대학원생과 샤차르 러벳 미국 샌디에이고 캘리포니아대 교수, 중국 베이징대 학부생인 우커원, 러벳 교수의 제자였던 장자펑 미국 하버드대 연구원입니다. 이들은 인터넷 논문 공개사이트인 ‘아카이브’에 다음과 같은 식이 성립하는 c가 있다는 것을 증명해 올렸습니다.

 

이런 식이 익숙하지 않은 분들은 이게 정말 기존 것보다 더 작은 건가 궁금할 수 있을 것 같습니다. 기존 결과들은 k!이 들어 있어서 대략 k^{k}처럼 증가한다고 볼 수 있는데, 새 결과는 대략 (logk)^{k}처럼 증가하는 식이라 기존의 결과를 대폭 개선한 겁니다. 물론 문제를 완전히 해결하려면 logk를 상수까지 내려야 하겠지만, 일단 이렇게 느리게 증가하는 logk까지 내릴 수 있었다는 것이 대단합니다.


2019년 9월에는 아눕 라오 미국 워싱턴대 교수가 이들의 증명을 간단하게 만들었다며 아카이브에 5쪽짜리 논문을 올렸습니다. 여기서는 위의 결과와 거의 비슷한 이런 식을 증명합니다.

 

이 최근 결과들은 아직 완전히 검증되지는 않았지만, 20년 이상 진척이 없던 에르되시-라도의 해바라기 추측에 큰 돌파구가 생긴 것은 분명합니다. 이번에 나온 라오 교수의 증명은 미국 수학자 클로드 섀넌이 정보이론을 창시했다고 평가받는 1948년 논문에서 나온 도구를 사용하고 있습니다. 어떻게 이 연구들이 서로 연결됐는지, 앞으로 또 어떤 연구에 활용될지 기대됩니다. 


그런데 어떻게 베이징대 학생이 이런 연구에 참여하게 됐을까요? 찾아보니 우 씨는 지난 6월부터 9월까지 미국에서 이 논문의 두 번째 저자인 러벳 교수의 지도 아래 학부생 연구에 참여했습니다. 바로 이런 인연으로 함께 논문을 쓴 것 같습니다. 


필자도 간혹 학부생들과 연구를 하다가 논문으로 이어진 경험이 있었습니다. 수학 연구라는 것이 어떤 방향에서 진전이 나올지 모르기 때문에 간혹 대학생의 연구도 좋은 결과로 이어집니다. 우리나라에도 이런 사례가 많아지길 바랍니다. 

 

 

 

관련기사 

수학동아 11월호. [따끈따끈한 수학] 협력의 힘을 발휘하다! 에르되시-라도의 해바라기 추측

 

 

※필자소개

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

 

이 기사가 괜찮으셨나요? 메일로 더 많은 기사를 받아보세요!

댓글 0

19 + 10 = 새로고침
###
    과학기술과 관련된 분야에서 소개할 만한 재미있는 이야기, 고발 소재 등이 있으면 주저하지 마시고, 알려주세요. 제보하기