콜라츠 추측

로타르 콜라츠(Lothar Collatz)가 1937년에 제기한 추측. 페르마의 마지막 정리와 같이 수학자들을 고민에 빠트린 전설의 문제이다.

이에 대한 대표적인 권위자로 제프리 라가리어스(Jeffrey C. Lagarias)[1] 교수가 있다. 제프리 교수는 2010년에 이 문제에 대한 알려진 정보만을 토대로 "이것은 현재의 수학에서 완전히 벗어난 매우 어려운 문제입니다"라고 주장했다.

이른바 "우박수" 또는 "우박 수열"이라는 이름으로 아는 사람이 많을 것이다. 이는 숫자가 커졌다 작아졌다를 반복하다 결국 1에 수렴하는 걸 비구름에서 빗방울이 오르락내리락하며 우박이 되는 모습에 빗대어 그렇게 부른다.

이 함수 $T(n)$을 모든 자연수 $n$에 대해 유한번 재귀 반복하면 1로 간다는 추측이다. 약간 변형된 표현으로

라고 제시하기도 한다. 홀수에 대해서 $3n+1$을 하면 무조건 짝수가 되는데 그 다음 단계에서 2로 나누게 되므로 한단계를 생략하고 미리 2로 나눈 것이다. 이 수열의 끝이 1이냐 아니냐만 중요하기에 중간 단계를 간략화하는 것은 별다른 영향을 주지는 않는다. 단 최대 얼마까지 커지느냐를 따지는 경우라면 원래의 표현을 기준으로 해야 한다.

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

이 추측의 반례는 아직 나오지 않았고 아마도 참일 것으로 추정된다. 반례가 하나라도 나오는 순간 별다른 증명이 필요없이 저 추측은 거짓인 것으로 문제가 끝나기 때문이다. 이미 1980년대에 컴퓨터를 이용해 약 1해($=10^{20}$)까지의 숫자를 넣어보았지만 모두 1에 도달했다. 2020년 $2^{68}$($=2.95×10^{20}$)까지 참으로 드러났다.

이 추측은 87년이 넘도록 풀리지 않고 있다. 게다가 상금도 걸려 있다. 1000파운드와 500달러의 상금이 걸려 있는데, 이중 500달러의 상금을 건 사람은 에르되시 팔이다.[2] 또한 1.2억엔(약 11억)의 상금을 지급한다.#

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

그리고 원시함수이기 때문에 증가율이 항상 높다. 이것 때문에 심지어 "항상 콜라츠 함수의 값은 감소한다"는 명제도 증명이 안 되고 있다.

결론부터 말하면 일반화를 해도 진전이 없다. 콘웨이의 생명 게임 창시자로 유명한 존 호튼 콘웨이가 1972년에 정지 문제를 이용해 일반화한 문제는 결정 불가능하다고 증명했기 때문이다. 콜라츠 추측 자체가 결정 불가능하다는 게 아니다. 콜라츠 추측은 짝수면 $\cfrac12$을 곱하고 홀수면 $3n+1$을 하는 함수 $g$가 주어지고 모든 $n$에 대해 이것이 수렴하는지 묻는 것인데 이제는 자연수 $P$가 주어진 상황에서 다음과 같이 $n~(\bmod P)$에 따라서 서로 다른(혹은 일부는 같아도 상관 없다) $P$개의 일차함수를 통해 값을 반환하는 더 일반화된 함수 $g$를 생각하자는 것이다.

이때 콘웨이의 증명은 특정한 함수 $g$가 주어졌을 때 임의의 $n$에 대하여 $g^m(n)=1$을 만족하는 $m$이 항상 존재하는지 찾는 알고리즘은 결정 불가능하다는 것이다.[3]

$P=1$인 경우 $g$는 자명하게 계속 증가하거나 감소한다.

콜라츠 추측은 다음과 같이 표현할 수도 있다.
$P=2$, 자연수 $k$에 대해

그리고 2007년 Simon과 Kurtz는 이를 $n>0$인 경우로만 한정하는 대신 모든 $n>0$ 에 대해 1로 수렴하는지 물어보는 문제로 바꾸어 이 문제 역시 결정 불가능함을 증명했다. 더 놀라운 것은 2015년에는 $\bmod P$에서 $P$를 $P=6480$으로 고정시켜도 그 문제 역시 결정 불가능하다는 것이 증명되었다.

이러한 결과들은 콜라츠 추측을 일반화시켜 연구하는 것이 어려울 것임을 시사한다. 그러나 콜라츠 추측의 참/거짓/증명불가능성과는 직접적인 연관이 없는데 일반화된 알고리즘이 없어도 각 경우를 모두 풀 수 없는 것은 아니기 때문이다.[4]

위의 일반화된 $g$함수와 같은 꼴을 띠는 특정[5] 문제를 콜라츠 추측 유사 문제라고 부르는데, 특히 입출력이 없는 튜링 머신에서 이러한 경향성을 보이는 경우가 있다. 이러한 튜링 머신을 통틀어 Collatz-like Busy Beaver라고 부른다. 이들은 낮은 수의 바쁜 비버 연구에서 핵심적인 역할을 한다. 특히 일부 튜링 머신의 정지 여부를 판단하는 것은 콜라츠 추측과 비슷한 난이도를 가지고 있을 것으로 보인다.[6]

증명의 악랄한 난이도에 비해 문제 자체는 초등학생도 이해할 수 있을 정도로 단순하다.[7] 당장 사칙연산과 자연수의 개념만 알아도 이해가 되기 때문. 페르마의 마지막 정리는 그래도 지수의 개념은 알아야 되고 리만 가설도 복소수와 리만 함수에 대한 이해가 필요하다는 점을 생각해보면 콜라츠 추측이 얼마나 단순한지 알 수 있다.

지금 당장 구글에 The proof of the Collatz conjecture이라고 치면 전문 수학자부터 20살, 심지어 15살이 쓴 논문까지 존재한다. 그리고 아무것도 동료평가를 통과하지 못했다. 이렇게 계속 증명 시도가 좌절되니 괴델의 불완전성 정리에 따른 증명 불가능설이 고개를 들고 있으며 상당한 신빙성을 얻고 있다.[8]

2019년 9월 8일 타오가 콜라츠 추측을 건드렸다.논문기사

물론 이 말은 콜라츠 추측 자체를 증명한 것이 아니다.[10] 참고로 "콜라츠 추측은 (거의) 필연적으로 감소한다"는 것은 타오 이전에도 이미 증명되었는데 1976년에 $f(x)=x$인 경우[11][12]가 1979년에 $f(x)=x^{0.869}$인 경우가, 1994년에 $f(x)=x^{0.7925}$인 경우가 증명되었기 때문이다. 즉 타오의 업적은 이를 엄청나게 일반화 시켜서 '거의 모든 자연수에 대하여 콜라츠 추측이 성립한다'를 증명한 것이다.[13] 2020년 타오 본인이 정리한 프레젠테이션을 보면 관련 내용이 언급된다.

타오가 제시한 방법은 케임브릿지 수학 저널에 게재되었다저널 논문. 물론 이 증명이 참이라 해도 여전히 반례가 존재할 가능성은 있다. 단적으로 임의의 $N\in\N$이 합성수일 확률은 1에 수렴하지만(즉 거의 모든 자연수는 합성수이지만) 그 반례인 소수는 가산무한히 많음이 잘 알려져 있다.

만약 이 추측이 거짓이라면 1로 가지 않는 반례가 존재한다는 것을 의미한다. 수학자들은 이런 '예상되는 반례'가 만약 진짜 존재한다면, 자기 자신으로 순환하는 루프가 존재할 것으로 생각한다.[14] 예를 들어 콜라츠 추측을 $3n+1$ 이 아니라 $3n-1$ 로 살짝 변경하면 5의 경우 아래와 같은 루프가 만들어 진다.

17의 경우에도 비슷한 루프가 만들어진다.

비록 $3n-1$의 명제의 경우 반례가 있어서 거짓으로 증명되었지만 1억까지 대입했을 때 5 루프와 17 루프 이외의 다른 루프(반례)는 없었다고 한다. 확률적으로 감소한다는 통계가 유한번 재귀했을 때 1로 수렴하는 것을 증명하지 못한다는 걸 보여주는 좋은 예시라고 할 수 있다.

$3n-1$ 문제는 $3n+1$ 문제를 음수로 확장한 것과 동일하다. 즉, 위의 2개의 루프를 음수로 확장한 $3n+1$ 로 생각할 경우 아래와 같이 된다.

그리고, 4 → 2 → 1 루프와 마찬가지로 -1 → -2 로 로 반복되는 기본 루프가 또하나 존재한다.

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

C++언어를 사용해서 직접결과를 계산해보았다.

계산결과 링크 https://www.asahi-net.or.jp/~kc2h-msm/mathland/math07/collatz04.htm