콜라츠 추측
1. 개요
로타르 콜라츠(Lothar Collatz)가 1937년에 제기한 추측. 페르마의 마지막 정리와 같이 수학자들을 고민에 빠트린 전설의 문제이다.
이에 대한 대표적인 권위자로 Jeffrey C.Lagarias[1] 교수가 있다. Jeffrey Lagarias 교수는 2010년에 이 문제에 대한 알려진 정보만을 토대로 "이것은 현재의 수학에서 완전히 벗어난 매우 어려운 문제입니다"라고 주장했다.
2. 어떤 추측인가?
이른바 "우박수" 또는 "우박 수열"이라는 이름으로 아는 사람이 많을 것이다. 이는 숫자가 커졌다 작아졌다를 반복하다 결국 1에 수렴하는 걸 비구름에서 빗방울이 오르락내리락하며 우박이 되는 모습에 빗대어 그렇게 부른다.
$$ T(n) = \begin{cases} n/2 , & \mathsf{if} \ n \ \mathsf{is \ even} \\ 3n+1, & \mathsf{if} \ n \ \mathsf{is \ odd} \end{cases} $$
이 함수 T(n)을 모든 자연수 n에 대해 유한번 재귀 반복하면 1로 가냐는 추측이다.
이를 풀어서 설명하자면, 1을 제외한 아무 자연수나 생각한 다음 그게 홀수라면 3을 곱한 다음 1을 더하고, 짝수라면 2로 나눈다. 그렇게 나온 수를 다시 저 식에 집어 넣고 이하 반복, 이걸 계속하다보면 1이 나오냐는 것이다. 예를 들어 5에서 시작하면, 5는 홀수니까 3×5+1=16이 되고, 16은 짝수니까 16/2=8, 이후 4와 2를 거쳐 1에 도달하게 된다.
이 추측의 반례는 아직 나오지 않았고, 아마도 참일 것으로 추정된다. 반례가 하나라도 나오는 순간 별다른 증명이 필요없이 저 추측은 거짓인 것으로 문제가 끝나기 때문이다. 이미 80년대에 컴퓨터를 이용해 약 1해까지의 숫자를 넣어보았지만 모두 1에 도달했다.(최근 컴퓨터 연산 결과가 많아져 약 2^68까지 참으로 드러났다. 하지만 이건 겨우 21자리에 불과하다.)
아무튼 '''이 추측은 80년이 넘도록 풀리지 않고 있다.''' 게다가 상금도 걸려 있다. 1000파운드와 500달러의 상금이 걸려 있는데, 이중 500달러의 상금을 건 사람은 에르되시 팔이다.[2]
약간 변형된 표현으로
$$ T'(n) = \begin{cases} n/2 , & \mathsf{if} \ n \ \mathsf{is \ even} \\ (3n+1)/2, & \mathsf{if} \ n \ \mathsf{is \ odd} \end{cases} $$
라고 나오기도 한다. 홀수에 대해서 3n+1 을 하면 무조건 짝수가 되는데, 그 다음 단계에서 2로 나누게 되므로 한단계를 생략하고 미리 2로 나눈 것이다. 이 수열의 끝이 1이냐 아니냐만 중요하기에 중간 단계를 간략화하는 것은 별다른 영향을 주지는 않는다. 다만, 최대 얼마까지 커지느냐를 따지는 경우라면 원래의 표현을 기준으로 해야 한다.
3. 해결하기 어려운 이유
콜라츠 추측이 풀기 어려운 이유를 알려면 일단 이거부터 알아야 된다. 점근 표기법은 $$\mathcal{O}(f(x))$$의 형식으로 표기되며 영어로는 Big O notation이다. $$\mathcal{O}(f(x))=g(x)$$가 의미하는 바는 $$f(x)$$에 비해 $$g(x)$$의 값이 일정 범위 내에서 항상 같거나 떨어진다는 것이다. 콜라츠 추측은 이 Big O notation에 의한 분류에서 야생 함수로 분류된다.
그리고 야생 함수이기 때문에 헬게이트가 오픈된다. 증가율이 항상 높기 때문. 이것 때문에 심지어 "항상 콜라츠 함수의 값은 감소한다"는 명제도 증명이 안 되고 있다.
4. 일반화라도 안 될까?
결론부터 말하면 콘웨이의 생명 게임 창시자로 유명한 존 호튼 콘웨이가 1972년에 '''일반화가 안 된다고 증명했다.''' 무슨 뜻이냐면 임의의 x에 대해 n번의 시행을 거쳐 1을 갈 때 x의 값이 정해지면 이에 따른 n의 일반항을 정할 수 있느냐의 문제인데 "불가능하다"라고 증명되었다. 정지 문제의 방식으로 증명했는데, 즉 콜라츠 추측은 언제나 정지하는 일정한 TRUE를 반환할 수 없다는 것이다.
2007년 연구 결과는 더 충격적인데, Simon과 Kurtz에 의하면 이는 arithmetic hierarchy[3]해도 여전히 성립한다고 한다. 산술적 계층화란 어떤 집합을 정의하는 식(콜라츠 추측에서 정의하는 일반적인 자연수 집합은 x 정도로 생각할 수 있다. 짝수면 2x 등.)이 매우 복잡할 때, 이것을 '계층'으로 나누어 집합을 분류할 수 있다면, 이를 산술적 계층화 가능이라고 한다는 것이다.
한마디로 요약해 노가다 외의 증명 방법이 존재하지 않는다는 것이다...
5. 페르마의 마지막 정리와의 비교
증명의 악랄한 난이도에 비해 문제 자체는 초등학생도 이해할 수 있을 정도로 단순하다. 당장 사칙연산과 자연수의 개념만 알아도 이해가 되니까. 페르마의 마지막 정리는 그래도 지수의 개념은 알아야 되고 리만 가설도 복소수와 리만 함수에 대한 이해가 필요하다는 점을 생각해보면 콜라츠 추측이 얼마나 단순한지 알 수 있다.
지금 당장 구글에 The proof of the Collatz conjecture이라고 치면 전문 수학자부터 20살, 심지어 15살(!)이 쓴 논문까지 존재한다. 그리고 당연히 아무것도 검증을 통과하지 못했다. 이렇게 계속 증명해도 안 되니까 최근에는 괴델의 불완전성 정리에 따른 증명 불가능설이 고개를 들고 있으며 상당한 신빙성을 얻고 있다.
6. 테렌스 타오의 접근
2019년 9월 8일 타오가 콜라츠 추측을 건드렸다.논문기사
- 어떤 함수 $$f(x)$$에서
- $$x$$가 무한히 커질 때 $$f(x)$$도 무한이 되면
- 거의 모든 자연수 $$N$$에 콜라츠 함수를 반복하면 $$f(N)$$ 이하로 언젠가는 떨어진다.
- '거의 모든'이 수학적이지 않아 납득이 안 갈 수 있는데 조건을 만족시키는 수의 확률이 1에 수렴한다는 것을 의미한다.
- 이 말은 '거의 모든 자연수에 대하여 콜라츠 추측이 성립한다'와 동치이다. 로그를 여러 번 사용한 함수같이 매우 천천히 무한으로 발산하는 함수가 있기 때문이다.
그러나, 테렌스 타오의 논문은 학회지에 게재되지 않아 논문 심사를 통과하지 않은 단독게재 논문이며 그 논문이 참인지는 교차검증되지 않은 상태이다.
7. 여담
만약 이 추측이 거짓이라면, 1로 가지 않는 반례가 존재한다는 것을 의미한다. 수학자들은 이런 대표적인 반례에 대해서 자기 자신으로 순환하는 루프가 존재할 것으로 예상한다. 예를들어 문제를 3n+1 이 아니라 3n-1 로 살짝 변경하면 5의 경우 아래와 같은 루프가 만들어 진다.
17의 경우에도 비슷한 루프가 만들어진다.
비록 3n-1의 명제의 경우 반례가 있어서 거짓으로 증명되었지만 1억까지 대입했을 때 5와 17, 그리고 이 둘을 루프하는 동안 나오는 숫자들 이외의 다른 루프(반례)는 없었다고 한다. 확률적으로 감소한다는 통계가 유한번 재귀했을 때 1로 수렴하는 것을 증명하지 못한다는 걸 보여주는 좋은 예시라고 할 수 있다.
다른 가능성으로는 무한히 발산한다는 것이 있다. 다만, 이는 반례의 존재 증명이 어렵다는 문제점이 있다. 그래서 허무맹랑해 보이기도 하지만, 존재하지 않는 것이 거의 확실해 보이기로는 순환 루프나 발산이나 오십보백보 수준이다. 앞서 언급한 테렌스 타오의 접근으로 콜라츠 추측이 발산 반례를 가질 가능성은 거의 0이라는 것이 사실이라면 반례가 존재할 경우 순환 루프가 될 가능성이 높다.
한국에서 서울대 물리학부 졸업한 사람이 이걸 풀었다고 하는데 사실 이 문서에 나온 문제와는 다른 문제이다.
8. 관련 링크
[1] <The Ultimate challenge:The 3x+1 problem>이라는 관련 서적을 쓰기도 했으며 이 외에도 리만 가설을 조화수열 형태로 정리한 걸로 유명하다.[2] 에르되시가 500달러를 걸었지만 증명이 안 되자 "수학은 아직 이런 문제를 풀 준비가 되어있지 않다"라는 말을 남겼다.[3] 한국 번역이 존재하지 않으며, 일본 번역을 가져오면 '산술적 계층화'라고 표현된다.[4] "수렴"한다는 말도 어폐가 있는 것이, 극한의 개념에서 수렴한다는 말은 가까이 다가간다는 뜻이 아니다. 증명을 통해 접근한 결과가 하나의 완성된 값으로 귀결된다, 즉 특정 값이라는 결론으로 끝난다는 뜻이다.