4색 문제

지난 글에서 4색 문제 및 일반적인 곡면에서의 채색 문제를 간단히 소개했다(오늘의 과학, 오일러 표수-4색문제 참고). 어려워 보이던 곡면에서의 채색 문제는 해결됐지만, 가장 간단한 곡면인 평면에서의 채색 문제를 해결하는 것이 더 어려운 기현상을 본 바 있다. 이제, 인류가 어떤 투쟁을 벌여 4색 정리를 정복했는지 살펴보기로 하자.

전문 수학자의 무릎을 꿇린 4색 문제

헤르만 민코프스키(Hermann Minkowski, 1864-1909) 4차원 세계를 표현한 ‘민코프스키 공간’으로 유명한 수학자.

전에도 말했지만, 4색 정리에 뛰어들었던 사람 중에는 전문 수학자도 많았다. 어떤 지도를 가져오든 다섯 개의 영역을 골라, 각 영역이 나머지 네 개 영역과 모두 인접하게 만들 수는 없다는 걸 증명한 건 드 모르간(Augustus de Morgan, 1806~1871)이다.

그다지 어렵지 않은 관찰이기 때문에 비전문 수학자 중에도 이를 눈치챈 사람은 많다. 사실 이런 비슷한 논증을 써서 4색 정리를 증명했다며 선언하는 경우가 많은데, 이런 종류의 관찰은 대부분 오래 전에 증명된 것이거나, 이것만으로는 4색 정리의 증명으로 불충분한 경우가 많다. 백 개짜리 영역을 갖고 있으면서 묘하게 얽혀 있어 꼭 5색이 필요할지 누가 아느냐는 얘기다.

헤르만 민코프스키(Hermann Minkowski, 1864-1909)는 당대 정상급 수학자인데, 어느 날 4색 문제에 대해 들었다고 한다. 민코프스키는 이런 문제는 하수들이 푸는 것으로, 자신은 며칠이면 풀 수 있다고 호언장담했다고 한다. 하지만 사색 문제를 사색하던 민코프스키의 낯빛은 사색으로 변하고 만다. 결국 민코프스키는 자신이 경솔했음을 깨닫고, 사색 문제가 결코 만만한 문제가 아님을 인정할 수밖에 없었다고 한다.

민코프스키의 절친한 친구이자 역시 일류급 수학자인 다비트 힐베르트(David Hilbert) 역시 한동안 4색 문제에 흥미를 가졌던 것 같다. 말년에 쓴 콘-포센과의 공동 저서 [Anschauliche Geometrie, GeometryandtheImagination]에서, 훨씬 어려운 경우에는 해가 있는데 가장 쉬워 보이는 경우가 뚜렷한 이유도 없이 어려운 대표적인 문제로 4색 문제를 언급할 정도였다. 수많은 수학적 혁신을 이뤘던 힐베르트도 4색 문제 앞에서만큼은 겸손해질 수밖에 없었던 것이다.

컴퓨터로 증명할 것을 생각한 헤슈

하인리히 헤슈(Heinrich Heesch, 1906-1995)는 힐베르트의 제자였다. 1935년 집권한 나치가 학계에서 유태인을 쫓아낼 때 헤슈는 이에 동참하지 않고 낙향하여 혼자 ‘쪽매’(tiling)에 대해 공부한다. 나치가 패망한 뒤 헤슈는 하노버 대학에서 교편을 잡고 ‘그래프 이론’을 연구한다. 여기서 그래프란 대충 말해 꼭짓점과 모서리로 이뤄진 도형을 말하는데, 그래프 이론은 컴퓨터 이론의 발달에 기여한 분야이기도 하다. 헤슈는 컴퓨터를 이용하여 4색 정리를 증명하자는 생각을 하고, 증명의 기본 뼈대를 세운다. 하지만 패전 조국 독일에는 변변한 컴퓨터가 갖춰져 있지 않았고, 당시 가장 빠른 컴퓨터는 승전국 미국이 보유하고 있었다. 헤슈는 1960년대 말부터 70년대 초까지 자주 미국을 방문하며, 그곳의 학자들과 4색 정리를 컴퓨터로 증명하자는 아이디어를 공유한다.

사상 최초로 컴퓨터로 증명한 수학 정리

일리노이 대학교 수학과에서 4색정리를 기념하여 사용한 미터스탬프(meterstamp, 우표대신 사용하는 스탬프).

증명을 눈앞에 둔 헤슈에게 독일 정부로부터 연구 자금 제공 중단 통보가 날아온다. 패전국이 겪는 재정 압박이 가장 큰 이유였겠으나, 이 때문에 4색 정리의 증명은 1976년 6월 미국 일리노이 대학교 어바나-샴페인 대학의 케네스 아펠(Kenneth Appel, 1932- )과 볼프강 하켄(Wolfgan Haken, 1928- )에게 넘어가게 된다.

물론 1200시간 여의 계산을 수행한 컴퓨터에게도 증명의 공로가 돌아갔지만, 정작 헤슈의 이름은 4색 정리의 증명자에 들어있지 않게 된다.

컴퓨터는 무슨 재주로 4색 정리를 증명했나?

그런데 컴퓨터는 무슨 수로 4색 정리를 증명한 걸까? 평면에 그릴 수 있는 지도는 무한 개인데, 제아무리 컴퓨터라지만 무한 개의 지도를 다 칠했을 리는 없지 않은가? 헤슈는 무슨 아이디어를 써서 컴퓨터가 증명할 수 있는 형태로 만든 걸까? 기본적인 아이디어는 역시 켐프의 틀린 증명에 들어 있다. 먼저 ‘모든 꼭짓점마다 모서리가 딱 세 개인 지도를 4색으로 칠할 수 있으면, 임의의 지도를 4색으로 칠할 수 있다’는 것을 설명해 보자. 각 꼭짓점마다 모서리가 세 개 이상 모이면, 아래 그림처럼 그 주변으로 작은 영역을 만들어 주면, 모든 꼭짓점마다 모서리가 딱 세 개인 지도를 만들 수 있다.

이때, 가정에 의해 오른쪽의 지도를 4색으로 칠할 수 있다. 예를 들어 아래 오른쪽처럼 칠했다면, 원래 지도는 아래 왼쪽처럼 칠해주면 원래 지도 역시 4색으로 충분히 칠할 수 있음을 쉽게 확인할 수 있다.

따라서 ‘모든 꼭짓점마다 모서리가 딱 세 개인 지도를 4색으로 칠할 수 있다’는 사실만 증명하면 된다. 이제, 예를 들어 인접한 면의 수가 3개인 영역이 있다고 해보자. 그러면 모서리 중 하나를 골라 지워서 면의 개수를 줄인다. 만일 이렇게 면의 개수를 줄인 것을 4색으로 칠할 수 있으면, 원래 지도 역시 4색으로 칠할 수 있다. 다음 그림을 보면 이해가 갈 것이다.

이처럼 원래 지도보다 면의 개수를 줄여서 4색으로 칠할 수 있을 때, 원래 지도를 4색으로 칠하는 방법을 찾을 수 있으면 ‘축소가능하다’고 말한다. 즉, 인접한 면의 개수가 3개인 영역이 하나라도 있으면 그런 지도는 축소가능하다. 하나 더 예를 들어 보자. 인접한 면의 개수가 4개인 영역이 있으면, 역시 다음 그림과 같은 방법을 쓰면 축소가능함을 알 수 있다.

그런데, 오일러 표수를 이용하면 (각 꼭짓점마다 모서리의 개수가 3개인 경우) 인접한 면의 개수가 3개 혹은 4개 혹은 5개인 것이 반드시 하나는 있음을 증명할 수 있다. 즉, ‘인접한 면의 개수가 3인 지도, 인접한 면의 개수가 4인 지도, 인접한 면의 개수가 5인 지도’ 중 하나를 ‘피할 수 없다’는 얘기다. 따라서 인접한 면의 개수가 5개인 면을 갖는 지도가 축소가능하다면 4색 정리는 진작에 증명이 끝났을 것이다. 켐프는 그렇다고 생각했지만, 히우드가 반례를 찾아낸 것이 문제라면 문제였다.

피할 수 없는 지도의 모임이면서 모두 축소가능한 것을 하나만 찾아내면 4색 정리를 증명할 수 있을 것이다. 문제는 지도가 복잡할수록 축소가능성을 확인하는 게 쉽지 않다는 것이었다. 이를 컴퓨터를 이용하여 확인하자는 게 헤슈의 아이디어였다. 헤슈가 축소가능성을 판별하는 교묘한 방법을 많이 찾아냈고 하켄이 판별법을 개선하였지만, 피할 수 없는 모임으로 축소가능한 지도들의 후보 집합은 어림잡아 원소가 만 개나 됐다. 때문에 실제로 원하는 집합임을 (당시의) 컴퓨터로 확인하는데 얼마의 시간이 걸릴 지는 짐작조차 할 수가 없었다. 헤슈가 떠난 빈 자리에서 1975년쯤 아펠과 하켄은 후보를 2000개로 줄일 수 있었고, 축소가능성을 검사하는 훨씬 더 빠른 판별법도 찾아낸다. 그런 뒤 후보 지도들을 컴퓨터에 입력했다. 축소가능하지 않은 것으로 판별되는 지도가 있으면 더 복잡하지만 여전히 피할 수 없는 지도 모임으로 교체하고, 다시 축소가능성을 판별하도록 반복 작업을 시키면서 부디 컴퓨터가 멈추길 비는 수밖에 없었다.

드디어 컴퓨터가 계산을 멈추었다

4색정리는 컴퓨터를 이용해서 증명했다는 것이 큰 논란거리였다. 사진은 70년대에 사용하던 컴퓨터의 모습.
<출처: (cc) Ben Franske>

487가지의 판별 규칙을 통해 검사하던 컴퓨터가 50여 일에 걸친 계산을 멈추고, 피할 수 없는 1,936 개의 지도의 모임이 축소가능하다는 것을 입증한다. 컴퓨터는 자신이 내놓은 결과의 의미를 전혀 몰랐겠지만, 난공불락이던 4색 문제가 드디어 4색 정리가 된 역사적 순간이었다. 주요 수학 정리 중 컴퓨터로 증명한 것은 4색 정리가 최초이기 때문에, 당시 이 증명을 받아들일 것이냐에 대해 활발한 논쟁이 일어난 것은 어쩌면 당연한 일이라 하겠다.

‘인간이 검증할 수 없는 증명’은 받아들일 수 없다며 거부하는 움직임도 많았다. 하지만, 오늘날에는 더 빨라진 컴퓨터, 더 개선된 판별 규칙을 쓰면 몇 시간 내로 더 작은 개수의 집합을 내놓는다. 따라서 컴퓨터가 증명할 때 오류를 일으켰을지도 모른다는 주장은 억지에 가까운 것으로, 요즘에는 컴퓨터가 증명에 성공했다는 사실만큼은 인정한다.

아름다운 증명을 찾아서

하지만 수학자들이 컴퓨터로 한 증명을 받아들이지 않았던 게, 꼭 인간이 검증할 수 없기 때문만은 아니다. 수학자들은 정리의 증명에도 아름다움을 추구하는 사람들이다. 물론 어떤 증명이 아름답냐는 건 사람마다 기준이 다를 것이다. 하지만 ‘왜 4색 정리가 참이어야 하는가’라든지 ‘증명에 담긴 본질은 무엇인가’에 대한 만족스런 대답으로 볼 수 없다는 건 분명한 것 같다. 그래서 아직도 아름다운 증명을 찾아나서는 노력은 끝나지 않았다. 예를 들어, 처음 제기했던 ‘대진표가 두 개인 유니폼 색깔 문제’처럼 4색 문제와 동일한 다른 문제로 바꾸려는 것도 아름다운(?) 증명을 찾으려는 노력의 일환이다. 어쩌면 기존의 증명 방법과는 전혀 다른 데서 길이 보일 수도 있을 것이다. 부질없는 희망일 수도 있으나 아름다운 증명이 나오길 바라는 마음이다.

네이버캐스터