반 데르 바르던 정리(Van der Waerden's theorem)

1부터 N까지의 자연수를 빨강과 파랑 두 색으로 칠합니다. 같은 색으로 된 세 수 $a,\ a+d,\ a+2d$, 곧 길이 3인 한 색 등차수열을 피할 수 있을까요? N = 8까지는 됩니다. 1, 2, 5, 6을 빨강, 3, 4, 7, 8을 파랑으로 칠하면 됩니다. 그러나 N = 9이면 어떻게 칠해도 한 색 등차수열이 생깁니다.

1부터 까지. 수를 누르면 색이 바뀝니다. 피하는 칠하기 찾기 무작위

정리. 1927년 네덜란드의 수학자 바르텔 반 데르 바르던은 다음을 증명했습니다. 색의 수 r과 길이 k가 무엇이든, N이 충분히 크면 1부터 N까지를 r가지 색으로 어떻게 칠해도 길이 k인 한 색 등차수열이 생깁니다. 그런 가장 작은 N을 반 데르 바르던 수⁠(van der Waerden number)⁠ $W(r, k)$라고 합니다. 위에서 본 것이 $W(2,3) = 9$이고, $W(3,3) = 27$, $W(2,4) = 35$, $W(2,5) = 178$입니다. $W(2,6) = 1132$는 2008년 무렵, 논리식을 참으로 만드는 값이 있는지 따지는 SAT 풀이기로 확인되었습니다(불 대수⁠, Boolean algebra⁠).

이 정리에서 자연수 전체를 유한 가지 색으로 칠하면 어느 한 색에 임의로 긴 등차수열들이 들어 있다는 것이 따라 나옵니다(거꾸로도 성립합니다). 흔히 이것을 '한 색으로 된 끝없는 등차수열이 있다'로 읽지만, 그렇지 않습니다. 끝없는 등차수열은 하나씩 차례로 늘어세울 수 있으므로, 차례마다 그 수열에서 아직 칠하지 않은 두 수를 서로 다른 색으로 칠해 나가면 한 색 끝없는 등차수열이 하나도 없는 칠하기가 만들어집니다.

증명의 뼈대는 비둘기집 원리⁠(pigeonhole principle)⁠를 겹겹이 쓰는 것입니다. 예를 들어 연속한 다섯 수로 된 구간을 두 색으로 칠하는 방법은 $2^5 = 32$가지뿐이므로, 그런 구간을 33개 늘어놓으면 칠한 모양이 똑같은 두 구간이 반드시 있습니다. 이렇게 되풀이되는 모양을 이용해 등차수열을 찾아냅니다. 이 방법으로 얻는 N은 어마어마하게 커서, 실제 값과의 차이를 줄이는 것이 지금도 연구 주제입니다. 아래쪽 한계는 무작위로 칠해 보는 확률적 방법⁠(probabilistic method)⁠으로 얻습니다.

램지 이론⁠(Ramsey theory)⁠의 한 가족. 이 정리는 램지 이론에서 가장 오래된 결과 가운데 하나로, 어떻게 칠하든 질서 있는 부분이 생긴다는 모양이 같습니다. 1975년 헝가리의 수학자 엔드레 세메레디는 더 강한 것을 증명했습니다. 색칠이 아니라 '밀도'만 있으면 충분합니다. 1부터 N까지 가운데 그 집합⁠(set)⁠에 드는 수의 비율이 N이 아무리 커져도 0으로 줄어들지 않으면(정확히는 위 밀도⁠(upper density)⁠가 양수이면), 그 집합은 임의로 긴 등차수열을 품습니다. 예를 들어 3의 배수⁠(multiple)⁠ 전체는 비율이 1/3이라 조건을 만족합니다. 색칠 판에서는 r가지 색 가운데 적어도 한 색이 이런 조건을 만족하므로, 반 데르 바르던 정리가 여기서 따라 나옵니다.

소수 속 등차수열. 소수는 N 이하에 약 $N/\ln N$개뿐이라(소수 정리⁠, prime number theorem⁠) 비율이 0으로 줄어들고, 세메레디 정리⁠(Szemerédi's theorem)⁠를 쓸 수 없습니다. 그런데도 2004년 영국의 벤 그린과 오스트레일리아 출신의 테런스 타오는 소수 안에 임의로 긴 등차수열이 있음을 증명했습니다. 5, 11, 17, 23, 29는 공차 6인 길이 5짜리, 7, 37, 67, 97, 127, 157은 공차 30인 길이 6짜리 소수 등차수열입니다. 한편 1837년 독일의 디리클레는 a와 d가 서로소(최대공약수⁠(greatest common divisor)⁠가 1)이면 등차수열 $a, a+d, a+2d, \ldots$에 소수가 무한히 많다는 것을 증명했습니다. 이것은 'd로 나눈 나머지⁠(remainder)⁠가 a인 소수가 무한히 많다'는 말이어서 모듈러 연산⁠(modular arithmetic)⁠의 언어로 쓰입니다. 그린–타오 정리와 달리 한 수열에 소수가 많다는 것이지, 소수만으로 된 긴 등차수열이 있다는 것은 아닙니다. 차이가 2인 소수 쌍이 무한히 많은지를 묻는 쌍둥이 소수⁠(twin primes)⁠ 문제는 오히려 아직 풀리지 않았습니다.

이어지는 곳. '피하는 칠하기 찾기'는 되돌아가기(백트래킹) 탐색을 합니다. 1부터 차례로 색을 정하다가 한 색 등차수열이 생기면 한 걸음 물러나 다른 색을 해 봅니다. 지도를 네 색으로 칠하는 4색 정리⁠(four color theorem)⁠의 그림도 같은 탐색으로 칠합니다. 이런 탐색은 최악의 경우 걸리는 시간이 크기에 따라 지수적으로 늘어납니다. 답이 주어지면 확인하기 쉬운 문제를 언제나 크기의 다항식(n², n³ 같은) 정도의 시간에 풀 수 있느냐가 P 대 NP 문제⁠(P versus NP problem)⁠입니다.