콜라츠 추측

1 개요

로타르 콜라츠(Lothar Collatz)가 1937년에 제기한 충격과 공포의 추측. 페르마의 대정리와 같이 수학자들을 고민에 빠트린 전설의 문제이다. 대표적인 권위자로 Jeffrey C.Lagarias 교수가 있다.

2 어떤 추측인가?

이른바 '우박수' 또는 '우박 수열'이라는 이름으로 아는 사람이 많을 것이다. 즉,

[math] T(n) = \begin{cases} n/2 , & \mathsf{if} \ n \ \mathsf{is \ even} \\ 3n+1, & \mathsf{if} \ n \ \mathsf{is \ odd} \end{cases} [/math]

이 함수 T(n)을 모든 자연수 n에 대해 유한번 재귀 반복하면 1로 가냐는 추측이다. 참 쉽죠?

이해가 잘 안되는 사람을 위해 풀어서 설명하자면, 아무 자연수나 생각한 다음 그게 홀수라면 3을 곱한 다음 1을 더하고, 짝수라면 2로 나눈다. 그렇게 나온 수를 다시 저 식에 집어 넣고 이하 반복, 이걸 계속하다보면 1이 나온다는 것이다. 예를 들어 5에서 시작하면, 5는 홀수니까 3x5+1=16이 되고, 16은 짝수니까 16/2=8, 이후 4와 2를 거쳐 1에 도달하게 된다.

당연한 얘기지만 이 추측의 반례는 아직 나오지 않았고, 아마도 참일 것으로 추정된다. 이미 80년대에 컴퓨터를 이용해 약 500경(...)까지의 숫자를 넣어보았지만 모두 1에 도달했다.

아무튼 이 추측은 80년이 넘는 동안 풀리지 않고 있다. 게다가 상금이 1000파운드에 500달러!

약간 변형된 표현으로
[math] T'(n) = \begin{cases} n/2 , & \mathsf{if} \ n \ \mathsf{is \ even} \\ (3n+1)/2, & \mathsf{if} \ n \ \mathsf{is \ odd} \end{cases} [/math]
라고 나오기도 한다. 홀수에 대해서 3n+1 을 하면 무조건 짝수가 되는데, 그 다음 단계에서 2로 나누게 되므로 한단계를 생략하고 미리 2로 나눈 것이다. 이 수열의 끝이 1이냐 아니냐만 중요하기에 중간 단계를 간략화하는 것은 별다른 영향을 주지는 않는다.

3 아이고 맙소사 이거 왜 안 풀리지

콜라츠 추측이 풀기 어려운 이유를 알려면 일단 이거부터 알아야 된다. 점근 표기법은 O(f(x))의 형식으로 표기되며 영어로는 Big O notation이다. O(f(x))=g(x)가 의미하는 바는 f(x)에 비해 g(x)의 값이 일정 범위 내에서 항상 같거나 떨어진다는 것이다. 콜라츠 추측은 이 Big O notation에 의한 분류에서 야생 함수로 분류된다.

그리고 야생 함수이기 때문에 헬게이트가 오픈된다. 증가율이 항상 높기 때문. 이것 때문에 심지어 "항상 콜라츠 함수의 값은 감소한다"는 명제도 증명이 안 되고 있다.

4 일반화라도 안 될까?

결론부터 말하면 그 반대는 증명되었다. 무슨 뜻이냐면 임의의 x에 대해 n번의 시행을 거쳐 1을 갈 때 x의 값이 정해지면 이에 따른 n의 일반항을 정할 수 있느냐의 문제인데 "불가능하다"라고 증명되었다. 컴퓨터 프로그래밍을 전공한 사람은 알 법한 정지 문제의 방식으로 증명했는데, 즉 콜라츠 추측은 언제나 정지하는 일정한 TRUE를 반환할 수 없다는 것이다. 망했어요.

5 페르마의 마지막 정리는 수학자로 낚시 연구의 피해자가 정해졌는데

증명의 악랄한 난이도에 비해 문제 자체는 초등학생도 이해할 수 있을 정로도 단순하다. 당장 덧셈, 뺄셈, 곱셈, 나눗셈, 자연수의 개념만 알아도 이해가 되니까.페르마의 마지막 정리는 그래도 지수의 개념은 알아야 되는데 이 놈은...
지금 당장 구글에 The proof of the Collatz conjecture이라고 치면 전문 수학자부터 20살, 심지어 15살(!)이 쓴 논문까지 존재한다. 그런데 문제는 이들 논문이 전부 틀렸다. 일반적으로 논문 검증 과정이 대략 3년 걸리는데, 검색된 논문들은 이전에 반례가 발견되었거나 작성된 지 3년이 지났다. 즉, 이들 논문의 증명에 오류가 있다는 것. 이렇게 계속 증명해도 안 되니까 최근에는 역으로 괴델의 불완전성 정리에 따른 증명 불가능설이 고개를 들고 있으며 상당한 신빙성을 얻고 있다.

이 추측은 위에서 말했듯이 대중들에게 이미 인지도가 높으며, 겉으로 보기에도 상당히 증명이 쉬워 보이는 추측인데 반백년 넘어 이제 한 세기를 향해 달려가는 미제이다. 디씨 수학 갤러리에서 가끔 떡밥으로 등장하고 최근에 모 블로그에서 증명을 발견했다고 사진을 올리기도 했지만 연산값 오류도 있고 설사 모든 증명이 맞다고 해도 리만 가설 항목에서 하디가 무한 해를 발견한 것과 유사한 것이라 사실상 폐기 확정. 전문 이론을 들고 나오며 미분방정식, 컴퓨터 프로그래밍, 사영기하학, 선형대수 등 온갖 기라성 같은 수식과 학문들을 쏟아 부어서도 증명이 안 된 역대급 함정 떡밥 문제이다.

6 여담

만약 이 추측이 거짓이라면, 1로 가지 않는 반례가 존재한다는 것을 의미한다. 수학자들은 이런 대표적인 반례에 대해서 자기 자신으로 순환하는 루프가 존재할 것으로 예상된다. 3n+1 문제에 대해서는 발견되지 않았으므로, 문제를 3n+1 이 아니라 3n-1 로 살짝 변경하면 아래와 같은 루프가 만들어 진다.

counter example of (3n-1) problem 5 → 14 → 7 → 20 → 10 → 5

물론 3n+1 문제에 대해서는 현재까지 이런 반례가 발견되지는 않았다.

다른 가능성으로는 무한히 발산한다는 것이 있다. 다만, 이는 반례의 존재 증명이 어렵다는 문제점이 있다. 그래서 허무맹랑해 보이기도 하지만, 존재하지 않는 것이 거의 확실해 보이기로는 순환 루프나 발산이나 오십보백보 수준이다.

이 문제의 연구가 의외로 도움이 될 수 있다. 위에서 언급했던 일반화의 불가능성이 암호로 유용하게 쓰일 수 있으나 실질적인 논문이나 연구 자료는 아직 나오지 않고 있다. 또 다른 장점이라면 수 체계를 재정비할 수 있다. 자연수 체계가 페아노 공리계에서 정리된 것 외에도 이 콜라츠 추측을 활용한 콜라츠 공리계로 새로이 정의될 수도 있다. 다만 전자는 실질적으로 가능하지만 두 번째는 증명이 될 때 가능하다는 게 흠.

7 관련항목

• 네이버캐스트 - 우박수