2-아딕 정수에서 콜라츠 사상과 그 켤레 사상(패리티/켤레 지도)을 다루며, 정수로 라벨된 무한 이진 트리 표현을 통해 부호 있는 피보나치 수열이 자연스럽게 포함됨을 보이고 콜라츠 반복의 홀짝 패턴과의 연결을 제시한다.
URL: https://vincentrolfs.dev/blog/collatz
Title: 콜라츠 추측과 피보나치 수 사이의 관계
2026년 2월 16일 – 97회 조회
면책조항 1
이 글에 제시된 결과는 동료 심사를 거치지 않았습니다. 초기 피드백을 얻기 위해 이곳에 공개합니다. 이 결과는 향후 몇 주 안에 학술지에 투고할 예정입니다.
면책조항 2
본문 작성과 수학적 결과는 AI의 도움 없이 만들어졌습니다. 모든 실수는 전적으로 제 책임입니다. 질문이나 제안이 있다면 언제든지 연락해 주세요.
다음과 같이 시작하는, 간선에 정수 라벨이 붙은 무한 이진 트리가 하나 있습니다:
콜라츠 사상을 나타내는 무한 이진 트리의 시작 부분. 클릭하면 새 탭에서 열립니다.
라벨은 점화식 과 을 통해 재귀적으로 정의할 수 있습니다. 값 들은 에서 값을 가지며 트리에서의 “경로”를 결정합니다. 예를 들어, 인데, 이는 뿌리에서 시작해 “오른쪽, 왼쪽, 오른쪽”으로 이동하면 라벨이 인 간선에 도달하기 때문입니다.
이 점화식은 부호 있는 피보나치 수 , 즉 로 시작하며 와 로 정의되는 수열과 다소 유사합니다. 실제로 우리의 트리에는 부호 있는 피보나치 수가 포함되어 있습니다. 트리에서 “오른쪽”과 “왼쪽” 회전을 번갈아 하면 그 수들에 도달합니다. 즉, , 그리고 계속해서 그런 식입니다.
이 트리는 콜라츠 추측과도 직접 관련됩니다. 콜라츠 사상 를 상기해 봅시다. 콜라츠 추측은 양의 자연수 를 시작값으로 두고 에 계속 적용하면 결국 에 도달한다는 유명한 명제입니다. 값들이 결국 홀수와 짝수 사이를 번갈아가며 나타남을 보이면 충분하다는 사실은 잘 알려져 있습니다. 왜냐하면 홀수 단계 뒤에 짝수 단계가 오면 ( )에 대해 엄밀히 감소하는 계산 에 해당하기 때문입니다.
또한 사상 은 -아딕 정수로 확장될 수 있다는 것도 잘 알려져 있습니다. 이 더 큰 영역에서는 의 반복에서 원하는 어떤 홀/짝 거동도 관찰할 수 있습니다. 예를 들어, 다음과 같은 거동을 보이는 시작값을 찾고 싶다고 합시다: 은 홀수, 은 홀수, 은 짝수, 은 짝수, 은 홀수, 은 홀수, 은 짝수… 즉 “홀수 두 번, 짝수 두 번”을 반복하고 싶습니다. -아딕 정수에서는 이런 거동을 보이는 시작값이 정확히 하나 존재한다는 것이 잘 알려져 있습니다.
여기서 트리와의 연결이 나타납니다. 위의 무한 트리를 따라가며 오른쪽으로 두 번, 왼쪽으로 두 번, 다시 오른쪽으로 두 번… 이런 식으로 진행하면서 만나는 라벨들을 적어 봅시다. 그러면 처음에는 로 시작할 것입니다. 이 라벨들을 라고 부르겠습니다. 그러면 우리가 찾는 -아딕 정수는
로 주어집니다.
피보나치 수로 돌아가서, 트리에서 “오른쪽”과 “왼쪽”을 번갈아 하면 수 들을 얻으므로, 이 절차는 콜라츠 반복 아래에서 “홀수”와 “짝수”를 번갈아 보이는 값을 산출해야 합니다. 그 값은 분명히 입니다. 즉, 우리의 결과는 잘 알려진 공식 를 함의하며, 꽤 멋집니다!
이 글의 요지는 위 트리가 피보나치 수와 콜라츠 추측을 놀라운 방식으로 연결한다는 점입니다. 이 결과는 수론적 관점에서 추측을 연구할 기회를 열어줄지도 모릅니다.
이 글에서는 2-아딕 정수 위에서 정의된
형태의 콜라츠 사상 을 고려합니다. 콜라츠 추측은 양의 자연수 에 대해 어떤 반복 가 와 같아진다고 주장합니다. 값들이 결국 홀수와 짝수 사이를 번갈아가게 됨을 보이면 충분하다는 사실은 잘 알려져 있습니다 [1].
콜라츠 추측 연구에서 중요한 도구는 켤레 사상(conjugacy map) 로, 1985년에 처음 고려되었고 [1], Bernstein과 Lagarias에 의해 광범위하게 연구되었습니다 [2]. 그 역함수는 다음으로 직접 정의될 수 있습니다: . 따라서 함수 는 반복값들의 짝/홀(parity) 정보를 2-아딕 정수로 부호화합니다. 콜라츠 추측은 와 동치임을 보일 수 있습니다 [2].
함수 는 2-아딕 정수 (무한한 0과 1의 스트림으로 해석)을 받아, 콜라츠 반복에서의 짝/홀 단계 거동이 정확히 그 스트림이 되도록 하는 2-아딕 정수로 보냅니다. 예를 들어, -아딕 값 는 2-아딕 전개가 이고, 인데, 이는 콜라츠 반복 아래에서 값이 홀수 단계와 짝수 단계를 번갈아 보이기 때문입니다.
놀랍게도, 사상 는 다음과 같은 명시적 공식
을 만족함을 보일 수 있습니다 [2]. 여기서 는 의 2-아딕 전개입니다. 이 표현은 정수가 아닌 값들의 무한합을 포함합니다.
이 글에서는 를 정수들의 무한합으로 나타내는 다음 표현을 증명합니다:
여기서 이고, 값 들은 을 만족하며 다음 공식을 갖습니다:
수 들은 점화식 때문에, 그리고 실제로 부호 있는 피보나치 수를 포함하기 때문에, 부호 있는 피보나치 수의 자연스러운 일반화로 볼 수 있습니다. 번갈아 나오는 를 고려합시다. 로부터 를 얻고, 부호 있는 피보나치 수 에 대한 표준 공식 를 얻습니다. 이는 또한 잘 알려진 -아딕 항등식 를 함의합니다. 수 들은 간선에 라벨이 붙은 무한 이진 트리로 자연스럽게 시각화할 수 있는데, 이를 라고 부릅니다.
더 일반적으로, -아딕 정수( 소수)에서,
로 정의되는 함수(단, 이고 가 꼴인 경우)는 켤레 사상 에 대해 정수 표현을 가지며, 다음과 같이 주어집니다:
여기서 이고
입니다.
콜라츠 경우에는 , 그리고 입니다.
이 글은 먼저 에서 함수 반복에 대한 몇 가지 간단한 일반 결과로 시작합니다. 다음으로 에서 수축 사상(contracting function)의 트리 표현 개념을 소개합니다. 주정리를 통해 위와 같은 점화식을 갖는 트리 표현을 어떻게 도출하는지 보입니다. 마지막으로 콜라츠 추측을 위한 트리를 살펴보고 그 성질 몇 가지를 진술합니다.
우리는 소수 에 대해 -아딕 정수 에서 작업하며, [2]에서 정의된 대로
로 주어지는 시프트 사상 이 있습니다. 임의의 사상 을 고려합시다. 패리티 사상 을 다음과 같이 정의합니다:
패리티 사상 은 의 반복이 만들어내는 짝/홀 정보를 부호화합니다. 우리는 다른 글들 [2]에서 다루는 켤레 사상 을 직접 연구하는 것보다, 패리티 사상을 직접 연구하는 것이 더 유익하다고 봅니다.
이 글에서는 가 어떤 의미에서 선형인 경우에 집중합니다. 의 성질은 두 가지 정규형(normal form) 중 하나로 표현함으로써 더 잘 이해할 수 있습니다. 이 장에서는 그 정규형들을 정의하고 왜 그것들을 고려하는지에 대한 동기를 제공합니다. 이 장의 증명은 어렵지 않고 본문의 주요 결과에 필요하지 않으므로 생략합니다.
정규형의 성질은 의 성질뿐 아니라, 다음 장에서 보일 에 대한 새로운 공식에도 직접 영향을 줍니다.
정의
에서의 사상 이 주어졌을 때, 그 첫 번째 정규형 은 다음으로 주어지는 위의 사상들의 모음 입니다:
즉, 각 와 에 대해 가 성립하도록 합니다.
이 정규형의 중요성은 다음 주석에 담겨 있습니다. 여기서 우리는 잘 알려진 사실, 즉 위의 거리 보존 사상(distance-preserving map)은 항상 전사이며 따라서 등거리사상(isometry)이라는 점을 상기시킵니다.
주석
에서의 사상 에 대해 다음은 동치입니다:
유사하게 다음도 동치입니다:
□
예시
콜라츠 사상 의 경우, 와 이며 둘 다 명백히 거리 보존이므로 는 등거리사상입니다.
다음 장에서는 첫 번째 정규형이 켤레 사상 에 대한 명시적 공식을 어떻게 직접적으로 알려주는지 볼 것입니다. 이는 두 번째 정규형 에 대해서도 마찬가지입니다:
정의
에서의 사상 이 주어졌을 때, 그 두 번째 정규형 은
로 주어지는 사상들의 모음 입니다. 즉 각 와 에 대해 가 되도록 합니다. 여기서 는 에서 정의됩니다.
주석
에서의 사상 에 대해 다음은 동치입니다:
에 대해, 가 거리 보존이면 는 항상 엄밀히 수축임에 유의합니다. 따라서 에서는, 가 수축인 것과 가 거리 보존인 것이 동치입니다.
첫 번째 정규형에서와 같이, 거리 보존의 경우도 전부 진술할 수 있습니다. 다음은 동치입니다:
□
예시
콜라츠 사상 의 경우, 와 이며 둘 다 명백히 거리 보존이므로 는 등거리사상이고 는 엄밀히 수축입니다. 이는 처음엔 흥미로워 보이지만, 손으로도 자명하게 확인할 수 있습니다.
정의
위의 사상 이 어떤 에 대해
꼴이면 선형(linear)이라고 합니다. 주의: 이런 사상은 항상 수축입니다. 거리 보존일 필요충분조건은 입니다.
주석
의 두 번째 정규형에 있는 사상 이 선형인 것과, 첫 번째 정규형의 가 선형이고 선도계수(leading coefficient)가 을 만족하는 것은 동치입니다.
그 경우, 이면 를 얻습니다.
□
어떤 거리 보존 사상도 자명하게 수축이며, 모든 수축 사상은 트리 형태의 편리한 표현을 갖습니다. 가 위의 수축 사상이라고 하고 두 입력 를 고려합시다. 이들의 -진 전개에서의 계수들을 “비트(bits)”라고 부르겠습니다. 가 수축이므로, 와 가 처음 비트에서 일치하면 와 도 처음 비트에서 일치함이 분명합니다(사실 이것이 “수축”의 정의와 정확히 대응합니다). 즉, 의 처음 비트는 의 처음 비트에만 의존합니다. 따라서
로 쓸 수 있는데, 여기서 는 에서 정의된 함수이며 정의역은 입니다. 흔한 약어로 를 씁니다. 사상 는 각 노드가 개의 자식을 갖는 무한 트리로 시각화할 수 있습니다. 트리에서 경로 를 따라가 도달한 노드의 라벨은 입니다:
트리의 시각화. 클릭하면 새 탭에서 열립니다.
를 에서의 정확 트리(exact tree) 라고 부릅니다. 위의 수축 함수들과 위의 정확 트리들 사이에는 일대일 대응이 있음을 보이기 어렵지 않습니다.
하지만 위와 같이 정의된 정확 트리는 종종 명시적으로 쓰기 어렵습니다. 따라서 우리는 다음과 같이 일반 트리를 정의합니다:
정의
위의 트리(tree) 란 에서 로 가는 사상입니다(치역에 주의). 위 그림처럼 시각화할 수 있습니다.
주석
어떤 트리도 하나의 수축 함수를 만들어냅니다: 가 위의 트리이고, 의 -진 전개가 라면
로 정의하면 이는 수축 함수입니다. 반대로 모든 수축 함수는 무한히 많은 트리 표현을 가지며, 그중 정확히 하나만이 정확 트리입니다. 수축 함수가 거리 보존일 필요충분조건은 그 정확 트리가 균형(balanced)이라는 것인데, 이는 임의로 고정한 에 대해 집합 이 모든 동치류 를 포함한다는 뜻입니다.
□
이제 본문의 주정리에 도달합니다.
정리
위의 사상 이 두 번째 정규형에서 선형이라 하자. 즉 에 대해, 그리고 및 에 대해 어떤 를 써서
가 성립한다고 하자.
앞과 같이 패리티 사상 을
로 정의하자.
그러면 패리티 사상 는 거리 보존이며, 그 역함수 는 다음으로 주어지는 트리 표현을 갖는다:
그리고 다음 재귀식으로 주어진다:
( ).
즉, 에서 값을 갖는 임의의 무한 수열 에 대해, 는 다음을 만족하는 유일한 -아딕 정수이다:
콜라츠 사상 의 경우, 이고 이다. 따라서 트리는 와 로 주어진다.
증명
왜 가 거리 보존인가? 이고 인 를 취하자. 만약 이면 어떤 에 대해 이다. 그러면 가 수축이므로 이고, 는 생략될 수 있다. 이 적용 절차를 계속하면 인 최소의 가 정확히 임을 알 수 있다. 의 정의에 의해 . 따라서 가 거리 보존이면 전단사이며 역함수를 가진다.
이제 -진 전개가 인 를 취하자. 우리는
임을 보이고자 한다. 로 둔다. 이제 -아딕 정수 가 아니라 -아딕 수 (numbers)에서의 값들의 수열을 재귀적으로 정의한다:
다음에 유의하자: 각 가 사실 -아딕 정수 임을 보일 수 있다면 끝이다. 그 경우 합은 수렴하고, 다음과 같은 망원경(telescoping) 논증을 사용할 수 있다:
이 때문에 우리는 위에서 정의한 값들에 대해 및 라고 쓴다. 이는 이 값들이 및 따라서 에 의존한다는 사실로 정당화된다(왜냐하면 이기 때문이다).
이제 다음을 증명하는 것이 목표다.
CLAIM 1: 모든 및 모든 에 대해 이다.
임의의 에 대해 이고 또한 이다. 간단한 귀납으로, 다음을 보이면 충분하다:
CLAIM 2: 모든 및 모든 에 대해 이다.
이제 에 대한 귀납으로 claim 2를 증명하며 부터 시작한다. 두 번째 정규형의 정의에 의해 이고 따라서
이다. 이것으로 인 경우가 해결된다. 이제 귀납 단계 를 보이자.
정리하면 을 보여야 한다. 이 시점에서 가 의 -진 전개로 정의되었음을 상기하는 것이 중요하다. 그런데 는 패리티 사상이므로 -진 전개는 단지 이다. 특히 이다. 마지막으로, 의 정의에 의해
이다.
이로써 주정리가 증명된다.
□
주석
완전성을 위해 첫 번째 정규형에 기반한 유사한 정리를 진술한다. 증명은 같은 방식으로 되지만 더 단순하다. 콜라츠 사상의 경우 결과 공식은 오래전부터 알려져 있으나, 정수가 아닌 값들이 나타나므로 덜 흥미로울 수 있다.
의 첫 번째 정규형이 ( )로 주어지는 선형이라 하자. 그러면 패리티 사상은 가역이며, 그 역함수는
로 주어지는 트리 표현과 다음 재귀식을 갖는다:
( ). 이는 다음 명시적 공식을 함의한다:
□
이제 콜라츠 사상 에 대한 함의를 더 자세히 살펴보자. 트리는 와 로 주어진다.
귀납을 사용하면 에 대한 다음 명시적 공식을 증명할 수 있다:
트리 시각화는 다음과 같이 시작한다:
콜라츠 사상을 나타내는 무한 이진 트리. 클릭하면 새 탭에서 열립니다.
주석
트리는 임의의 에 대해 다음 성질들을 갖는다:
증명
(1.) 점화식에서 바로 따른다. (2.) 귀납으로 바로 따른다. (3.) 에 대한 귀납. 에 대해 를 보여야 하는데, 이는 계산으로(또는 위 시각화에서 읽어) 확인할 수 있다. 귀납 단계 에 대해, 점화식을 사용하면:
이고, 이는 보이고자 한 바이다. (4.) 먼저 를 가정하자. 로 둔다. 그러면 (1.)과 (3.)과 를 사용하여
를 얻는다. 이는 맨 앞에 0 하나를 추가한 효과다. 또 하나를 추가하면 이므로 이 효과가 상쇄된다.
□
위 첫 번째 사실은 선행 0들이 생략될 수 있음을 의미하며, 이는 음이 아닌 정수에 기반한 인덱싱 방식이 자연스럽다는 것을 강하게 시사한다. 실제로, -진 전개가 인 (단 )에 대해 다음을 정의할 수 있다:
예를 들어 이다.
이는 의 -진 전개 끝에 0을 추가하는 것이 의 맨 앞에 0을 추가하는 것에 대응하며, 둘 다 값을 바꾸지 않기 때문에 잘 정의된다.
정수 수열은 다음으로 시작한다:
이 관점에서는 시각화의 왼쪽 절반 전체가 불필요해진다. 인 값들만(사실상 이전 시각화의 오른쪽 부분) 보여 주면 트리를 더 잘 시각화할 수 있다:
홀수 시작값만을 보여주는 트리의 오른쪽 부분. 클릭하면 새 탭에서 열립니다.
이 수열은 간선 라벨을 행(row)별로 읽은 것에 해당한다.
주석
앞의 성질들은 정수 수열 의 관점에서 다음처럼 진술할 수 있다.
□
이 글의 결과는 피보나치 수와 콜라츠 추측을 놀랍고(바라건대) 흥미로운 방식으로 연결합니다. 이는 수론적 관점에서 이 추측을 연구할 기회를 열어줄지도 모릅니다.
향후 글에서는 트리와 해당 정수 수열 의 추가 성질들을 살펴볼 것입니다. 또한 패리티 사상에 대한 이론적 결과도 더 발표할 예정입니다. 여기서 작은 예고를 하자면, 지금까지는 콜라츠 사상 에 대한 패리티 사상 를 연구했지만, 자체가 또 다른 사상 의 패리티 사상이라는 것을(적어도 첫 번째 출력 비트를 제외하면) 보일 수 있습니다. 더 정확히는, 는 다음을 만족하는 사상 입니다: 모든 에 대해
여기서 는 시프트 함수입니다. 이 사상은 매우 명시적으로 기술될 수 있습니다.
mail@vincentrolfs.dev 로 이메일을 보내셔도 좋습니다. 또는 Mastodon에서 @vincentrolfs@hachyderm.io 를 팔로우하실 수 있습니다.
