등차수열 여러 개로 정수 집합 덮기

…, -2, 0, 2, 4, 6, 8, 10, … (짝수)
…, -3, 0, 3, 6, 9, 12, 15, … (3의 배수)
…, -3, 1, 5, 9, 13, 17, … (4의 배수+1)
…, -5, 3, 11, 19, 27, 35, … (8의 배수+3)
…, -5, 7, 19, 31, 43, … (12의 배수+7)
…, -1, 23, 45, 68, … (24의 배수+23)

어떤 수 $n$을 24로 나눈 나머지를 생각해보면 모든 정수는 위 등차수열 중 적어도 하나에는 반드시 포함됨을 알 수 있다. 유명한 수학자 에르되시( Erdős)는 1950년 논문에서 임의의 $N$에 대해, 공차가 $N$ 이상인 등차수열만 써도 이런 식으로 모든 정수 집합을 덮을 수 있지 않겠냐고 적었다. 하지만 이 문제는 지난 수십년 간 풀리지 않았었고, 에르되시는 1980년 논문에서 본인이 1934년에 이 문제를 생각했다며 증명이나 반증에 $500을 준다고 했다. 에르되시는 1913년 태어났으니 1934년이면 21살일 때가 되겠다.

수학을 사랑한 아이 책 표지
2013년에는 에르되시에 관한 그림동화책도 한글로 번역되어 출판되었다.

예를 들어 N=3인 경우 아래처럼 등차수열들을 구성하면 공차는 서로 다르면서 전체 정수 집합을 덮을 수 있다.

3의 배수, 4의 배수, 5의 배수, 6의 배수+1, 8의 배수+1, 10의 배수+2, 12의 배수+11, 15의 배수+1, 20의 배수+14, 24의 배수+5, 30의 배수+8, 40의 배수+6, 60의 배수+58, 120의 배수+26.

1968년엔 Churchhouse가 N=9인 방법을 찾고, 1971년에는 Krukenberg가 박사논문에서 N=18인 방법을 기술했으며, S. L. G. Choi가 1971년에 N=20인 방법을 찾았다. 1981년 Morikawa는 N=24까지 올리고 2009년엔 Gibson은 대규모 컴퓨터 계산을 통해 N=25인 방법을 찾았으며, 같은 해 Nielson이 N=40인 방법에 대한 논문을 출판했다. 이 문제에 대한 Nielson의 설명을 아래 동영상에서 볼 수 있다.

2013년  옥스포드대학의 Bob Hough 박사는 에르되시의 위 추측은 거짓이고, 만일 공차가 서로 다른 등차수열로 정수 집합을 덮을 수 있다면 그 중 적어도 하나의 등차수열의 공차는 $10^{18}$보다 클 수 없음을 증명하였다. 이로써 무려 63년만에 에르되시의 미해결 문제 하나가 해결된 셈이다. 증명은 확률론적 방법을 쓰는데, Lovasz Local Lemma를 응용한다고 한다. (arxiv에 올라온 논문)

(이 분야 논문이 있는 캐나다 밴쿠버의 British Columbia 대학 교수로 70년대 주로 활동한 S.L.G. Choi라는 분이 한국인일까요? 아닐 것 같긴 합니다만.)

잘 짜인 동아리 (Generalized Steiner System)

전체 $n$명의 사람이 있는 학교에서 $q$명의 학생들로 구성된 동아리들이 있다고 한다. 그런데 아무렇게나 $r$명의 학생을 모아도 그 $r$명이 동시에 속한 동아리의 수는 정확히 $\lambda$로 똑같다고 한다. 과연 $n$, $q$, $r$, $\lambda$ 값이 어떤 경우에 이런 식으로 동아리들을 구성할 수 있을까?

$i\le r$인 어떤 수 $i$에 대해, 학생 $i$명의 집합 $Z$를 생각해보자. 이 집합 $Z$의 학생을 동시에 포함한 $r$명의 학생의 집합$Y$는 정확히 $\binom{n-i}{r-i}$개가 있으므로, 집합 $Z$의 학생을 동시에 포함한 동아리 $X$가 있을 때 $(X,Y)$의 순서쌍의 수는 정확히 $\lambda\binom{n-i}{r-i}$가 된다. 반대로, $Z$를 포함한 동아리 $X$에 대해 위의 조건을 만족하는 $Y$의 수는 $q-i$명에서 $r-i$명을 뽑는 수와 같으므로 $\binom{q-i}{r-i}$이다. 모든 $Z$를 포함하는 동아리에 대해 위 성질이 성립하므로 \begin{equation}\text{모든 $0\le i\le r$에 대해 $\binom{q-i}{r-i}$는 $\lambda\binom{n-i}{r-i}$의 약수}\label{eq:st} \end{equation}여야 한다.

그럼 조건 \eqref{eq:st}을 만족하는 모든 $n$, $q$, $r$, $\lambda$가 있다면 저런 식으로 동아리를 반드시 짤 수 있을까?

이 문제는 조합론 분야에서 정말 오래된 난제 중 하나이다. $r=2$일 때 이러한 식으로 동아리를 짤 수 있냐 물어보는 문제를 Steiner System이라고 하고, 일반적인 $r$에 대해서는 Generalized Steiner System이라고 한다. 이 문제는 무려 1800년대 중반까지 역사가 거슬러갈 정도로 조합수학 분야에서 정말 오래된 난제 중에 하나인데, 올해 초 이 분야 연구자들을 깜짝 놀라게 한 연구결과를 옥스포드 대학 Peter Keevash 교수가 발표하였다. (arxiv에 올라온 논문)

정리 (Keevash 2014): 모든 $n$, $q$, $r$, $\lambda$가 조건 \eqref{eq:st}을 만족하며 $n$이  충분히 크다면 위와 같은 식으로 동아리를 짜는 것이 가능하다.

Peter Keevash 교수
Peter Keevash 교수 (2003년에 Banff 워크샵 갔을때 만나서 찍었던 사진)

Steiner System에 관한 연구의 역사는 1800년대 중반 수학자들 Plücker (1835년), Kirkman (1846년), Steiner (1853년)로 거슬러 올라간다.  $r=2$인 경우에는 이 문제는 1970년대  칼텍의 Richard M. Wilson 교수가 $n$이 충분히 크면 참이라고 증명하였다.  일반적인 $r$은 아직까지 미해결로 남아있었다.

2014년 6월 미국 미니애폴리스에서 열린 SIAM Conference on Discrete Mathematics라는 학회에서는 긴급하게 “Hot Topic Session”이라는 이름으로 저녁 8시에 Peter Keevash 교수를 초청해서 이 결과에 대한 강연을 듣는 자리가 있었다. 보통 이런 학회의 초청강연자 명단은 몇 달 전에 잡히기 때문에 초청강연자로 하기에는 너무 늦은 상황이지만 결과가 매우 중요하기 때문에 이렇게 늦게 시간을 잡았다고 한다.

이 문제의 해법은 확률론적 방법을 사용하는데 Keevash 교수는 그것을 “Randomized Algebraic Construction”이라고 부른다. 앞으로 이러한 방법이 다양한 문제를 해결하는데 큰 도구가 될 것으로 생각된다.

영국 출신인 Peter Keevash 교수는 프린스턴대학에서 Benny Sudakov 교수 지도 하에 2004년에 박사학위를 받았다. 올 봄에 만났을 때, 어떻게 이 문제에 관심을 가지고 해결하게 되었냐 물어보니, 칼텍에서 박사후 연구원을 할 때 Richard M. Wilson 교수로부터 이 문제를 잘 알게 되었고 그 후 다른 연구를 하면서도 이 문제에 대하여 항상 관심을 가지고 있었다고 한다.

안녕하세요!

이산수학, 조합수학, 그래프이론 연구자들 몇 명이 모여서 흥미로운 최신 연구 결과나 미해결 문제를 한국어로 소개하는 블로그를 만들었습니다.  앞으로 많은 관심 부탁드립니다.