콜라츠 추측

콜라츠 추측의 규칙을 사상으로 쓰면 다음과 같습니다.

한 번의 비행은 $n$에서 출발해 $f(n)$, $f(f(n))$ 등을 거치며, 1에 도달하면 끝납니다. 그 뒤에는 1 → 4 → 2 → 1만 반복하기 때문입니다. 추측은 모든 양의 정수가 그곳에 도달한다고 말합니다. 여기서는 정수를 하나씩 또는 무리 지어 날릴 수 있으며, 수백 자리 정수도 가능합니다. 추측을 그럴듯하게 만드는 대략적인 논리와 비교하고, 그 논리가 왜 증명은 아닌지 볼 수 있습니다.

가로축은 단계 수, 세로축은 값이며, 원래 값을 선택하지 않으면 로그 눈금입니다. 원래 값을 선택하면 익숙한 우박 모양의 그래프가 됩니다. 무리의 각 수는 색깔 있는 선이므로, 많은 수가 지나는 구간은 색이 더 강합니다. 어두운 화면에서는 더 밝고, 밝은 화면에서는 더 짙습니다. 살펴보는 수는 강조되며, 현재 위치는 빨간 점으로 표시됩니다. 비행은 예측하기 어렵습니다. 27은 9,232까지 올라갔다가 111단계 만에 1에 도달하지만, 28은 18단계면 됩니다.

왜 이 추측을 믿을까요? 홀수 단계는 항상 짝수를 만들므로, 바로 다음의 2로 나누기와 묶어 하나의 단축 단계로 셉니다. 이제 이 단계들의 홀짝이 서로 독립적인 공정한 동전 던지기와 같다고 가정해 봅시다. 절반의 경우 $n$에 약 3/2를 곱하고, 나머지 절반에는 1/2을 곱하므로, 단축 단계 한 번에 $\ln n$의 평균 변화량은

입니다. 그러면 수는 작아져야 하며, 보통 단축 단계 두 번마다 이전 값의 3/4이 됩니다. 로그축에서 이 하향 추세를 나타내는 것이 파선이며, 100개 이상의 수로 이루어진 비슷한 크기 무리에 표시됩니다. 다만 착륙은 고려하지 않습니다. 1에 도달한 수는 바닥에 머무르므로, 끝에 가까워지면 이 축에서 무리의 평균 높이는 파선보다 느리게 내려갑니다.

동전 던지기는 수의 평균적인 행동을 나타내는 모형일 뿐입니다. 추측은 모든 양의 정수에 관한 것으로, 1에 영원히 도달하지 않는 비행이 하나만 있어도 틀린 추측이 됩니다.

음수는 이 논리가 놓치는 점을 보여 줍니다. 같은 규칙을 음수에 적용하면 순환이 생기며, −5 → −14 → −7 → −20 → −10 → −5처럼 세 가지가 알려져 있습니다. 동전 모형은 음수에서도 크기가 줄어들 것으로 예측하지만, 어떤 순환이든 한 바퀴 돌면 $\log|n|$의 변화는 정확히 0입니다. 평균적으로 내려가는 추세만으로 순환을 배제할 수는 없으며, 양수에서도 마찬가지입니다.

산호는 비행을 거꾸로 뒤집습니다. 1에서 역방향으로 뻗으면 무리의 경로가 나무를 이룹니다. 새 수가 짝수이면 각 변은 앞 변에서 $+\alpha$만큼, 홀수이면 $-\alpha \log_2 3$만큼 꺾이며, α는 굽힘각으로 정합니다. 1에서 거꾸로 갈 때 짝수 단계는 수를 두 배로 하고 그 $\log_2$를 1만큼 늘립니다. 홀수 단계는 이를 $\log_2 3$보다 조금 더 줄입니다. 따라서 n에 이르는 변은 수직 위 방향에서 모두 합해 $\alpha \log_2 n$만큼 돌아가고, 홀수 단계마다 조금씩 더해집니다. 그 회전량에 n의 크기가 기록되는 것입니다. 가지를 따라 방향이 한 비행의 수들과 함께 오르내리므로, 각 가지는 비행을 감아 놓은 모습입니다. 비행이 만나는 곳에서 가지도 합쳐집니다. 이 표현에서 추측은 1에서 자란 나무가 모든 양의 정수를 포함한다는 뜻입니다.

이 문제는 보통 1930년대에 이런 질문들을 제기한 로타어 콜라츠의 것으로 알려져 있습니다. 산호 그림은 에드먼드 해리스의 “Collatz seaweed”(2016)를 따릅니다.