4장 — 콜라츠: 요동은 어디서 오는가

이 장에서 배우는 것 — 두 줄짜리 규칙이 만드는 궤도가 왜 예측 불가능하게 요동치는지를 묻는다. 표준 수학의 답은 세 층위로 올라간다: 동전던지기 모형(휴리스틱), Terras와 Tao의 부분 정리('거의 모든'이라는 한정어가 생명이다), 그리고 2-adic 세계의 구조 정리(랜덤이 비유가 아니라 동형이 되는 곳). 새로 만나는 개념은 콜라츠 사상 $T$, 랜덤워크·드리프트·분산, 정지 시간과 로그 밀도, 2-adic 정수 $\mathbb{Z}_2$, 패리티 벡터, 시프트와 켤레, 그리고 2와 3의 곱셈적 독립이다.

들어가며 — 초등학생도 아는 규칙, 아무도 못 푼 문제

아무 양의 정수나 하나 고르자. 짝수면 2로 나누고, 홀수면 3배 하고 1을 더한다. 나온 수에 같은 규칙을 또 적용한다. 이걸 반복하면 무슨 일이 일어날까?

7로 해 보자. 7은 홀수니까 $3 \cdot 7 + 1 = 22$. 짝수니까 11. 홀수니까 34. 그다음 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. 열여섯 걸음 만에 1에 도착했고, 1에 오면 $1 \to 4 \to 2 \to 1$로 제자리를 돈다.

콜라츠 추측(Collatz conjecture — 이름은 독일 수학자 로타르 콜라츠에게서 왔다)은 "모든 양의 정수의 궤도가 결국 1에 도달한다"는 주장이다. 이 추측은 미해결이며, 2025년 기준 $2^{71} \approx 2.36 \times 10^{21}$까지의 모든 출발점에 대해 계산으로 확인되었다. 21자리 수까지 전부 1로 내려왔는데도, "전부 그렇다"는 증명은 아직 없다. 정확한 최초 착상 연도와 현재 형태의 기원은 뒤의 계보 표에서 별도로 구분한다.

이 문제의 역사는 한 사람이 답을 향해 직선으로 전진한 역사가 아니다. 원래 질문을 그대로 풀지 못한 대신, 수학자들은 "대부분은 내려가는가", "홀짝 기록은 어떤 구조인가", "비슷한 규칙 전체는 판정 가능한가"처럼 주변 질문을 하나씩 정확하게 만들었다.

연구 계보 | 질문이 어떻게 자랐는가

저자(블로그 "정보수학")는 글 9에서 콜라츠 추측을 "두 가지 간단한 상태변화를 다루는 프로그램"으로 재해석하고, 그 궤적이 "마치 랜덤처럼 변화하면서 숫자가 평균적으로 작아지기는 하지만 모든 숫자가 그런지는 알려지지 않았다"고 관찰했다. 이 한 문장에는 놀랍게도 이 장에서 배울 표준 수학의 핵심이 전부 압축되어 있다: "마치 랜덤처럼"(층위 1), "평균적으로 작아진다"(층위 1의 드리프트), "모든 숫자가 그런지는 알려지지 않았다"(층위 2의 벽).

궤도의 요동 — 단조롭게 줄지 않고 크게 오르내리는 성질 — 에 대한 표준적 답은 세 층위로 올라간다. 층위 1은 동전던지기 휴리스틱: 그럴듯하지만 증명은 아닌 확률 모형이다. 층위 2는 부분 정리: "거의 모든"이라는 한정어를 단 채로 휴리스틱의 일부가 엄밀해진다. 층위 3은 구조 정리: 수 체계를 넓히면 '마치 랜덤처럼'의 "마치"가 떨어져 나가고, 랜덤성이 문자 그대로의 수학적 동형이 된다. 미리 말해 두면, 이 장의 최대 수확은 어떤 최종 결론이 아니라 이 세 층위의 구분 그 자체다.

층위 1 [휴리스틱] — 동전던지기 모형: 드리프트와 분산의 경쟁

궤도의 오르내림을 정량화하는 첫걸음은 로그 눈금으로 갈아타는 것이다(이 책에서 $\log$는 자연로그다). 가속형 $T$의 한 걸음은, $n$이 짝수면 정확히 $\times \frac{1}{2}$이고, 홀수면 $\frac{3n+1}{2n} \approx \frac{3}{2}$배 — $n$이 클수록 $\times \frac{3}{2}$에 가깝다. 로그 눈금에서 곱셈은 덧셈이 되므로, 한 걸음은 $\log n$에 약 $+\log\frac{3}{2} \approx +0.4055$를 더하거나(홀수) 정확히 $\log\frac{1}{2} \approx -0.6931$을 더하는(짝수) 것이 된다.

여기서 잠깐 — 어느 쪽 걸음이 나올지는 무엇이 정하는가? 현재 수의 홀짝, 즉 패리티(parity)다. 궤도를 따라가며 홀짝을 기록하면 0과 1의 열이 나오는데, 이 열이 마치 공정한 동전던지기처럼 보인다는 것이 저자의 관찰이자 이 층위의 가정이다. 그 가정을 받아들이면 궤도는 확률의 언어로 번역된다.

콜라츠의 로그 걸음에 이 언어를 적용하자. 홀짝이 확률 $\frac{1}{2}$씩의 공정한 동전이라면, 한 걸음의 기대(평균) 로그 증분은 손으로 계산할 수 있다:

$$\frac{1}{2}\log\frac{3}{2} + \frac{1}{2}\log\frac{1}{2} = \frac{1}{2}\left(\log\frac{3}{2} + \log\frac{1}{2}\right) = \frac{1}{2}\log\frac{3}{4} \approx -0.1438 < 0.$$

말로 다시 읽기: 상승 걸음($+0.4055$)과 하강 걸음($-0.6931$)을 반반의 무게로 평균 내면 한 걸음마다 로그 눈금에서 평균 $0.1438$씩 내려간다. 숫자를 직접 확인해 보자: $\log\frac{3}{2} = \log 3 - \log 2 \approx 1.0986 - 0.6931 = 0.4055$이고, $\log\frac{1}{2} = -\log 2 \approx -0.6931$이니 둘의 합은 $-0.2877$, 그 절반이 $-0.1438$이다. 상승폭보다 하강폭이 커서 평균이 음수가 되는 것 — 이것이 "평균적으로 작아진다"의 정체다.

즉 $\log T^k(n)$은 음의 드리프트를 가진 랜덤워크처럼 행동한다: 평균적으로 하강하지만 한 걸음의 분산이 커서, 요동(변동성) = 드리프트(평균 하강)와 분산(패리티 열의 랜덤성)의 경쟁이다. 저자의 "마치 랜덤처럼, 평균적으로 작아진다"(글 9)는 관찰이 정확히 이 모형이다.

이 모형은 공짜 예측도 준다. 출발점 $n$의 로그 높이는 $\log n$이고 한 걸음에 평균 $0.1438 = \frac{1}{2}\log\frac{4}{3}$씩 내려가니(부호를 뒤집으면 $-\frac{1}{2}\log\frac{3}{4} = \frac{1}{2}\log\frac{4}{3}$), 1까지 내려가는 데 걸리는 걸음 수는 대략

$$\frac{\log n}{\frac{1}{2}\log\frac{4}{3}} = \frac{2}{\log(4/3)}\,\log n \approx 6.95 \log n.$$

말로 다시 읽기: 총 정지 시간 — 궤도가 1에 도달할 때까지의 걸음 수 — 의 평균은 출발점의 자연로그의 약 7배라는 예측이다. 이것이 Kontorovich–Lagarias의 정량 예측(가속형 $T$ 기준)이다. 7로 검산해 보자: $6.95 \times \log 7 \approx 6.95 \times 1.946 \approx 13.5$걸음 예측인데 실제는 11걸음이었다. 평균에 대한 예측이므로 개별 수와 정확히 맞을 이유는 없지만 규모는 맞는다. 같은 모형에서 궤도 최댓값은 $n^{2+o(1)}$ 규모로 예측된다 — 말로: 전형적인 궤도는 출발점의 제곱 규모까지 치솟는다는 뜻이다(지수에 붙은 $o(1)$은 $n$이 커질수록 0으로 가는 보정항). 나아가 시나이(2003)는 적절히 스케일한 궤도가 기하 브라운 운동 — 로그를 취하면 랜덤워크의 연속판인 브라운 운동이 되는 확률 과정(랜덤이 시간에 따라 전개되는 모형) — 으로 수렴함을 보였다.

단, 여기서 절대 놓치면 안 되는 것이 있다. 이 모든 것은 확률 모형 내부에서는 정리이지만, 실제 개별 궤도에 대한 예측으로서는 휴리스틱(추측)이다. "패리티 열이 정말 공정한 동전처럼 행동한다"는 것 자체가 미증명이기 때문이다. 동전 모형 안에서의 계산은 얼마든지 엄밀하게 할 수 있다 — 그러나 콜라츠 궤도가 그 모형을 따른다는 다리가 놓여 있지 않다. 층위 1은 그래서 [휴리스틱] 배지를 단다.

층위 2 정리 — Terras와 Tao: '거의 모든'까지 올라간 사다리

휴리스틱의 일부는 실제로 증명되었다. 먼저 과녁을 정확히 하자. $n$의 정지 시간(stopping time)은 궤도가 처음으로 출발점 $n$보다 작아지는 시각(걸음 수)이다. 7의 궤도 $7 \to 11 \to 17 \to 26 \to 13 \to 20 \to 10 \to 5 \to \cdots$에서 7보다 작은 값이 처음 나오는 것은 일곱 걸음째의 5이므로, 7의 정지 시간은 7이다. 앞에서 쓴 총 정지 시간(1에 도달하는 시각)과는 다른 개념임에 주의하자.

왜 하필 이 개념이 과녁인가? 만약 모든 $n \ge 2$의 정지 시간이 유한하다면 콜라츠 추측이 통째로 따라온다: $n = 2$는 곧장 1로 가고, $n \ge 3$의 궤도는 언젠가 $n$ 아래의 어떤 수에 도달하는데, 그 수는 (강한 귀납법 — $n$ 미만의 모든 수에 대해 이미 성립한다고 가정하는 귀납법 — 의 가정에 의해) 1에 도달하기 때문이다. 그래서 "정지 시간이 유한하다"를 얼마나 많은 $n$에 대해 증명할 수 있는가가 이 문제의 진도표가 된다.

정리 Terras(1976): 자연밀도 1의 양의 정수에 대해 정지 시간이 유한하다. 자연밀도는 3장에서 설명한 개념 — "$x$ 이하에서 그 성질을 갖는 수의 비율이 $x \to \infty$에서 갖는 극한" — 이고, 밀도 1이란 그 비율이 100%로 수렴한다는 뜻이다. 이 결과는 표준으로 정착했으며, Terras 자신이 밀도 존재성에 대한 보충 노트(1979)를 냈고 Everett(1977), Möller(1977/78), Heppner(1978)의 독립 증명이 있다.

정리 Tao(2019/2022): $f(N) \to \infty$인 임의의 함수 $f$에 대해, 로그 밀도 의미에서 거의 모든 $N$이 궤도 최솟값 $\le f(N)$을 만족한다. 예컨대 거의 모든 $N$의 궤도는 $\log\log\log\log N$ 이하까지 내려간다. 이 4중 로그는 발산함이 증명되어 있지만 "발산하는 모습이 관측된 적은 없다"는 수론학자들의 농담이 있을 만큼 느리게 자란다 — $N$이 우주의 원자 수 규모인 $10^{80}$이어도 그 값은 아직 1에도 미치지 못한다(약 0.5). 정리의 힘은 바로 거기에 있다: 그렇게까지 낮은 문턱조차, 거의 모든 궤도가 결국 그 아래로 내려간다는 것이다.

Tao의 정리에는 한정어가 세 개 붙어 있고, 하나라도 빼면 증명되지 않은 다른(더 강한) 주장으로 변한다. (i) 거의 모든 — 전부가 아니다. 예외 집합이 밀도 0으로 허용된다. (ii) 로그 밀도 — 자연밀도로는 증명되지 않았다. (iii) almost bounded — 궤도가 유계(어떤 고정된 상한 아래)라는 뜻이 아니라, 임의로 느리게 발산하는 함수 $f(N)$ 이하까지 내려간다는 뜻이다. 이 세 한정어는 장식이 아니라 정리의 몸통이다.

숨을 고르자. 층위 2가 우리에게 준 것은 "거의 모든 수는 휴리스틱이 예언한 대로 행동한다"는 정리다. 그런데 왜 여기서 멈추는가? Tao의 방법으로도 "거의 모든"을 "모든"로 올릴 수 없다 — 통계적 논법은 본질적으로 밀도 0의 예외집합을 허용하기 때문이다. 100%의 수가 말을 듣는다는 것과 예외가 하나도 없다는 것 사이에는 무한히 많은 수가 들어갈 자리가 남아 있다. 바로 이 '거의 모든'과 '모든' 사이의 벽이 콜라츠가 어려운 이유다.

층위 3 정리 — 2-adic 세계: '마치'가 떨어져 나가는 곳

층위 1의 동전은 가정이었고 층위 2는 그 가정의 통계적 그림자를 증명했다. 층위 3은 방향을 바꾼다: 수 체계 자체를 넓히면, 동전던지기가 가정이 아니라 문자 그대로의 사실이 되는 세계가 있다.

그 세계를 만나기 위해 2진법으로 생각하자. 7은 2진법으로 $111$, 1024는 $10000000000$이다. 보통의 수는 왼쪽으로 유한한 자릿수에서 끝난다. 이제 규칙을 하나만 바꾸자: 왼쪽으로 무한히 긴 2진 자릿수를 허용한다. 이렇게 만들어지는 수들의 체계가 2-adic 정수 $\mathbb{Z}_2$다. 표기에 관한 주의 하나를 본문에 박아 두겠다: 이 책에서 $\mathbb{Z}_2$라는 기호는 오직 이 2-adic 정수만을 가리킨다. "홀짝의 세계", 즉 나머지 0과 1로 이루어진 두 원소짜리 군은 항상 $\mathbb{Z}/2\mathbb{Z}$로 쓴다(1장). 문헌에 따라 $\mathbb{Z}_2$가 후자를 뜻하기도 하므로 다른 책을 읽을 때는 주의가 필요하다.

왼쪽으로 무한히 긴 수는 괴물이 아니라 계산이 되는 대상이다. 직접 하나 계산해 보자.

$\mathbb{Z}_2$에는 크기 개념도 있는데, 우리가 아는 자와는 다른 자다. $x$가 2로 $v$번 나누어떨어지면(2진 표기에서 아래쪽에 0이 $v$개 깔려 있으면) $x$의 2-adic 크기를 $|x|_2 = 2^{-v}$로 정한다. 2로 많이 나눠질수록 작다.

이제 핵심 관찰: 콜라츠 사상 $T$는 이 세계 전체에서 그대로 계산된다. 홀짝은 마지막 비트 하나만 보면 알 수 있고, 짝수의 "2로 나누기"는 비트열을 오른쪽으로 한 칸 미는 것이며, $3n+1$은 자리올림 덧셈이라 왼쪽으로 무한한 비트열에서도 문제없이 실행된다. 정리 실제로 $T$는 $\mathbb{Z}_2$ 전체로 유일하게 연속 확장되며, 이 확장은 하르 측도 — $\mathbb{Z}_2$ 위의 균등 측도로, "모든 비트를 독립인 공정한 동전으로 채우는 확률 모형"이라고 읽으면 정확하다 — 를 보존하고 에르고딕하다(측도 보존·에르고딕성의 원 논문은 Matthews–Watts 1984; Lagarias 1985 서베이).

다음 등장인물은 궤도의 홀짝 기록이다. $x$에서 출발해 $x, T(x), T^2(x), \ldots$의 홀짝을 1(홀수)과 0(짝수)으로 차례차례 적으면 무한한 0/1 열이 나온다. 7이라면: 7(홀)·11(홀)·17(홀)·26(짝)·13(홀)·20(짝)·10(짝)·5(홀)·8(짝)·4(짝)·2(짝)·1(홀)… 이므로 기록은 $1,1,1,0,1,0,0,1,0,0,0,1,\ldots$이고, 궤도가 순환 $\{1,2\}$에 갇힌 뒤로는 $1,0$이 영원히 반복된다. 이 무한 기록을 다시 "왼쪽으로 무한한 2진수"의 자릿수로 읽으면 $\mathbb{Z}_2$의 원소 하나가 된다. 이렇게 만든 사상 $Q_\infty: \mathbb{Z}_2 \to \mathbb{Z}_2$를 패리티 벡터 사상이라 부른다.

정리 패리티 벡터 사상 $Q_\infty$는 2-adic 등거리(거리를 보존하는 사상)이자 측도 보존 동형(두 세계를 정보 손실 없이 맞바꾸는 가역 대응)이다. 특히 홀짝 기록만으로 출발점이 하나로 결정된다 — 정보가 한 비트도 손실되지 않는다. 그리고 이 좌표 변환이 $T$의 정체를 폭로한다. 무한 0/1 열의 세계에서 "첫 기록을 지우고 열을 한 칸 밀기"라는 사상을 시프트 $\sigma$라 하자. 공정한 동전던지기가 만드는 0/1 열에 시프트를 얹은 계가 베르누이 계 — 확률론이 "완전한 랜덤"의 표준형으로 삼는 계다. 그러면:

$$Q_\infty \circ T = \sigma \circ Q_\infty.$$

말로 다시 읽기: $T$로 한 걸음 간 뒤 블랙박스를 읽으나, 블랙박스 기록을 한 칸 밀어 읽으나 같다. 이런 관계에 있는 두 사상을 켤레(공액, conjugate)라 한다 — 가역인 좌표 변환을 사이에 두고 완전히 같은 동역학(규칙의 반복이 만드는 운동)이라는 뜻이다(이 개념은 7장에서 로지스틱 사상을 만날 때 재회한다). 즉 $Q_\infty$는 $T$를 시프트 사상 — 공정한 동전던지기(베르누이 계)의 표준 모형 — 과 켤레로 만든다.

여기서 잠깐, 왜 이게 놀라운지 보자. 층위 1에서 "패리티 열이 동전던지기 같다"는 것은 검증 안 된 비유였다. 그런데 확장을 끝낸 공간 $\mathbb{Z}_2$에서는, 하르 측도(= 공정한 동전으로 비트를 채우는 확률)로 잰 콜라츠 동역학이 동전던지기의 표준 모형과 좌표 변환까지 명시된 채로 동일한 계다. 층위 1의 동전던지기는 이 세계에서 비유가 아니라 정확한 구조 정리다. 배지가 [휴리스틱]에서 정리로 바뀌는 대신, 무대가 $\mathbb{Z}^+$에서 $\mathbb{Z}_2$로 바뀌었다.

그렇다면 추측이 풀린 것 아닌가? 아니다 — 그리고 그 이유가 이 정리의 가장 쓰라린 교훈이다. 양의 정수 전체 $\mathbb{Z}^+$는 $\mathbb{Z}_2$ 안에서 측도 0이다: 하르 동전으로 비트를 무한히 채울 때 "어느 자리 이후 전부 0"(= 보통의 양의 정수)이 나올 확률은, 동전을 무한히 던져 어느 시점 이후 뒷면만 나올 확률과 같은 0이다. 에르고딕 이론의 결론("하르-거의 모든 점")은 측도 0인 $\mathbb{Z}^+$에 대해 아무것도 말해주지 않는다. 정수 궤도에서 관찰되는 요동은 이 베르누이 랜덤성이 측도 0의 부분집합 $\mathbb{Z}^+ \subset \mathbb{Z}_2$에 드리운 그림자다.

넓힌 세계가 정수의 세계와 정말 다르다는 것은 순환의 목록에서도 보인다. $\mathbb{Z}_2$에는 $\{1,2\}$ 순환 말고도 순환이 실존한다 — 위에서 본 고정점 $-1$이 그렇고, 음의 정수 순환도 있다.

게다가 하르 측도 1의 점은 최종 주기적(언젠가부터 순환에 들어가는 상태)이지 않아서 어느 순환에도 흡수되지 않는다. "모든 궤도가 $\{1,2\}$로 흡수된다"는 콜라츠 추측의 그림은 $\mathbb{Z}_2$ 전체에서는 성립조차 하지 않는다 — 그 그림이 성립할 수 있는 무대는 (추측이 참이라면) 양의 정수라는 측도 0의 특수한 부분집합뿐이다. 즉 정수의 특수성이 문제의 본질이다.

마지막으로 이 정리를 저자의 세계관에 겹쳐 보자. 패리티 벡터 $Q_\infty$가 등거리 동형이라는 사실은 "상태를 전이의 sequence로 코딩하면 정보가 하나도 손실되지 않는다"는 정리다. "상태란 과거 전환의 sequence의 약식 표기"라는 저자의 존재론(글 10, 23)이 콜라츠 문맥에서 문자 그대로 성립하는 사례인 것이다 — 수 $x$와 그 궤도의 홀짝 기록 전체는 수학적으로 맞바꿔 쓸 수 있는 동일한 정보다. 이것은 철학의 우연한 적중이 아니라 정식화 명제의 지위를 갖는 대응이지만, 그 이상의 판정(추측의 참·거짓)과는 별개다.

콜라츠와 골드바흐 — 반례를 '확인'할 수 있는가

저자는 글 9에서 콜라츠 추측과 골드바흐 추측(모든 4 이상의 짝수는 두 소수의 합)을 나란히 놓고, 둘 다 "반례 탐색 프로그램의 정지 여부" 문제로 환원한 뒤, "칸토어가 무한을 등급화했듯 거듭되는 변환(프로그램)을 유형화하는 메타 학문"을 제안했다. 훌륭한 직관인데, 한 단계의 교정이 필요하다: 두 추측은 논리적 유형이 다르다.

차이는 "반례를 유한한 계산으로 확인할 수 있는가"에 있다. 골드바흐의 반례 후보는 짝수 하나다. 어떤 짝수 $2k$가 반례인지 확인하려면 $2k$ 미만의 소수들 — 유한 개다 — 을 나열하고, 각 소수 $p$에 대해 $2k - p$가 소수인지 유한 번의 나눗셈으로 검사하면 끝난다. 어느 분해도 성공하지 못하면 "반례다"라는 판정이 유한 검사로 확정된다. 그래서 "골드바흐가 거짓이면 반례 탐색 프로그램이 언젠가 멈춘다"는 환원은 정확하다.

콜라츠는 다르다. 추측은 "모든 $n$에 대해, 어떤 $k$가 존재하여 $T^k(n) = 1$" — 기호로 $\forall n\, \exists k\, (T^k(n) = 1)$ — 꼴의 문장이다. 반례에는 두 형태가 있다. 하나는 1을 지나지 않는 순환 궤도인데, 이것은 궤도가 이미 나온 수로 되돌아오는 순간 유한하게 확정되므로 골드바흐형이다. 문제는 다른 형태 — 영원히 커져만 가는 발산 궤도다. 반례가 발산 궤도라면 그 발산 자체가 유한하게 확인 불가능하다: 아무리 오래 계산해도 "아직 안 내려왔다"와 "영원히 안 내려온다"를 유한 관찰로 구별할 수 없다. 반례 탐색기가 영원히 돌아도, 그것이 "반례가 없어서"인지 "반례를 만났는데 확인을 못 끝내서"인지 알 수 없는 것이다. "추측마다 반례 탐색의 논리적 모양이 다르다"는 이 사실 자체가, 저자가 원한 '프로그램 유형화'의 첫 번째 실제 사례다.

유형화의 꿈에는 천장도 있다. 정리 콘웨이(1972): 콜라츠를 닮은 함수들의 족 — 주기별 선형 분기 함수, 즉 $n$을 어떤 수로 나눈 나머지에 따라 서로 다른 일차식을 적용하는 함수들 — 에 대해, "주어진 함수와 출발점에 대해 궤도가 1에 도달하는가"라는 문제는 결정불가능하다(어떤 단일 알고리즘도 이 질문 전부에 옳게 답할 수 없다는 뜻). 이유는 이런 함수족이 임의의 컴퓨터 프로그램을 시뮬레이션할 수 있기 때문이다 — 콘웨이가 이 아이디어로 만든 FRACTRAN은 그 자체로 완전한 프로그래밍 언어다. 커츠–사이먼(2007)은 아핀 일반형에서 전칭 버전("모든 $n$이 1에 도달하는가")이 결정불가능성의 등급표에서 정확히 어느 칸에 앉는지까지 못 박았다. 골드바흐형·콜라츠형이 앉는 칸에는 각각 $\Pi^0_1$, $\Pi^0_2$(기호에 붙은 위첨자 0은 '산술적 위계'의 층이라는 표시일 뿐 거듭제곱이 아니다 — 커츠–사이먼의 결과는 "$\Pi^0_2$-완전")라는 공식 좌표가 있으며, 이 좌표계(산술적 위계)는 6장에서 정식으로 배운다.

여기서 반드시 새겨야 할 주의가 있다. 이것은 $3n+1$이라는 특정 함수의 결정불가능성이 아니다. 결정불가능한 것은 매개변수화된 클래스 전체에 대한 문제이고, 콜라츠 추측 자체는 하나의 고정된 문장으로서 증명될 수도, 반증될 수도, 특정 공리계로부터 독립일 수도 있으며(공리계로부터의 "독립"이라는 개념은 5장에서 정식으로 만난다) 어느 쪽도 알려져 있지 않다. 콘웨이가 만년에 "콜라츠 자체도 증명 불가능하게 참일 수 있다"고 쓴 것은 사변이다. 저자의 '변환 유형화' 제안에 대한 표준 수학의 대답은 그래서 이렇게 요약된다: 콜라츠형 반복 변환의 클래스는 보편적인 계산을 포함하므로 완전한 분류는 원리적으로 불가능하고, 그 분류 불가능함 자체가 등급표 안의 정확한 좌표로 등급화되어 있다. '분류학이 없는' 것이 아니라 '분류가 불가능함이 분류되어' 있는 것이다.

비교를 낳는 산술적 단서 유추 — 2와 3은 서로 공명하지 않는다

마지막 물음은 "왜 하필 이 규칙이 이런 요동을 낳는가"다. 콜라츠 사상은 두 세계를 강제로 섞는다: "2로 나누기"는 2진법의 세계에 속하고, "3을 곱하기"는 3진법의 세계에 속한다. 그리고 이 두 세계는 근본적으로 화해하지 않는다 — 2와 3은 곱셈적으로 독립이기 때문이다.

곱셈적으로 독립이라는 것은, 2의 거듭제곱 사다리와 3의 거듭제곱 사다리가 (1 이외에서) 영원히 만나지 않는다는 뜻이다. 이 사실만으로 콜라츠 궤도의 패리티가 섞인다거나 음의 로그 드리프트가 생긴다는 결론은 나오지 않는다. 다만 2진 정보와 3진 정보를 동시에 추적하는 문제가 왜 자연스럽게 떠오르는지를 보여 주는 비교 대상은 된다. 이 비교와 주제를 공유하는 엄밀한 수학이 측도 강직성 이론이다. 이름과 방향만 소개한다.

이 대목에서 정확성의 안전벨트를 단단히 매자. 명시적 경고: 퍼스텐버그 추측과 콜라츠 사이에 알려진 직접적 논리 함의는 없다. 공유되는 것은 "×2 구조와 ×3 구조를 동시에 존중하는 대상은 극도로 제한된다"는 주제뿐이다. 이 유추의 콜라츠 번역 — 궤도가 요동하지 않으려면 2진·3진 구조가 장기간 공모해야 하는데, 강직성의 철학은 그런 공모가 없으리라 시사한다 — 은 철학적 좌표이지 정리가 아니다. 그래서 이 절 전체에 유추 배지가 붙는다.

유추 소수를 "곱셈으로 도달할 수 없는 수"로 본 저자의 직관(글 3, 21 — 소수 쪽 이야기는 3장에서 다뤘다)과 연결해, 2와 3의 공명 부재와 콜라츠의 혼합 현상을 나란히 놓아 볼 수는 있다. 그러나 이것은 원인 설명이 아니라 연구 질문을 만드는 유추다. 즉 "2진·3진 정보를 함께 추적하는 어떤 양이 실제 패리티 상관을 제어하는가?"라고 물을 이유를 줄 뿐, 랜덤성·하강·순환 부재 가운데 어느 것도 증명하지 않는다.

무엇이 증명되었고, 무엇이 열려 있는가

이 장이 다룬 주장들의 최종 장부를 정리한다.

층위별로 다시 말하면 이렇다. 층위 1에서 "마치 랜덤처럼"은 비유고, 층위 2에서 부분적으로 증명되며, 층위 3에서 '마치'가 떨어져 나간 문자 그대로의 동형이 된다 — 단, 그 동형이 사는 무대는 우리의 정수가 측도 0으로 잠겨 있는 더 큰 세계다. 콜라츠에 관해 독자가 가져갈 최대의 수확은 어떤 답이 아니라, 휴리스틱 → 부분 정리 → 구조 정리라는 세 층위의 구분 그 자체다. 같은 하나의 직관("랜덤 동전")이 무대와 한정어에 따라 추측이 되기도, 정리가 되기도 한다는 것 — 이것이 이 문제에서 배울 수 있는 가장 정직한 수학이다.

4장 요약

• 콜라츠 사상(가속형)은 $T(n) = n/2$(짝수), $(3n+1)/2$(홀수). 콜라츠 추측("모든 양의 정수의 궤도가 1에 도달")은 미해결이며 $2^{71} \approx 2.36 \times 10^{21}$까지 계산으로 확인되었다.
• 층위 1 [휴리스틱]: 홀짝을 공정한 동전으로 가정하면 로그 걸음의 기댓값은 $\frac{1}{2}\log\frac{3}{4} \approx -0.1438 < 0$ — 요동은 음의 드리프트와 큰 분산의 경쟁이다. 총 정지 시간 $\approx 6.95\log n$, 궤도 최댓값 $n^{2+o(1)}$ 등의 정량 예측이 따르지만, "패리티 열이 동전처럼 행동한다"는 가정 자체가 미증명이라 모형 밖에서는 휴리스틱이다.
• 층위 2 정리: Terras — 자연밀도 1의 정수는 정지 시간 유한. Tao — 로그 밀도 의미에서 거의 모든 $N$의 궤도가 임의로 느린 발산 문턱 아래까지 하강. 세 한정어(거의 모든 / 로그 밀도 / almost bounded)를 빼면 다른 주장이 되며, '거의 모든'과 '모든' 사이의 벽이 문제의 난소다.
• 층위 3 정리: 왼쪽으로 무한한 2진수의 세계 $\mathbb{Z}_2$에서 $T$는 하르 측도 보존·에르고딕이고, 무손실 블랙박스인 패리티 벡터 $Q_\infty$가 $T$를 동전던지기의 표준형(시프트·베르누이 계)과 켤레로 만든다 — 랜덤성이 비유에서 동형으로 승격된다. 그러나 $\mathbb{Z}^+$는 그 세계에서 측도 0이라, 이 정리는 추측 자체에 대해 침묵한다. $\{1,2\}$ 밖의 순환($-1$, $-5 \to -7 \to -10$)이 실존하므로 정수의 특수성이 본질이다.
• 골드바흐의 반례는 유한 검사로 확정되지만 콜라츠의 발산 반례는 유한하게 확인 불가능하다 — 두 추측은 논리적 유형이 다르며, 이 차이가 저자가 제안한 '프로그램 유형화'의 첫 실례다. 콘웨이·커츠–사이먼: 콜라츠형 클래스의 분류 불가능성 자체가 정확히 등급화되어 있다. 단, 이는 $3n+1$ 단일 문장의 결정불가능성이 아니다.
• 유추 2와 3의 곱셈적 독립($2^a = 3^b$ 불가 — 짝홀 두 줄 증명)은 측도 강직성과 비교할 단서다. 이것이 콜라츠의 요동·음의 드리프트·순환 부재를 일으킨다는 직접적 논리 함의는 알려져 있지 않다.

세 문장으로 확인하기

쉬운 출구 — 직관 카드

깊은 출구 — 대학원으로 가는 길