A Fibonacci theorem for Collatz trajectories via modular graph structure

기술 요약: 모듈러 그래프 구조를 통한 콜라츠 궤적의 피보나치 정리

문제 정의
본 논문은 가속된 콜라츠 사상(Collatz map) $T(n)$의 역학을 다룬다. 여기서 $T(n)$은 $n$이 짝수일 때 $n/2$, 홀수일 때 $(3n+1)/2$로 정의된다. 콜라츠 추측은 모든 양의 정수가 결국 순환 $1 \leftrightarrow 2$에 도달한다고 상정하지만, 이에 대한 증명은 존재하지 않는다. 본 논문은 궤적의 특정 구조적 성질, 즉 홀수가 초기 반복 과정 동안 모듈러 그래프에서 잔여 클래스 $4 \pmod 6$를 회피하는 빈도에 초점을 맞춘다. 구체적으로, 단계 $2, \dots, m$ 동안 $T$ 하에서의 궤적이 모듈러 그래프의 정점 $4$를 방문하지 않는 홀수$n \in {1, \dots, 2^m}$의 개수를 조사한다.

방법론
저자는 이진법과 모듈러 관점을 동시에 분석하고, 이를 특정 전단사 함수와 구조적 대칭성을 통해 연결하는 이중 인코딩 프레임워크를 사용한다.

1. 이진 인코딩과 교정 잔여(Corrective Residue):
   본 논문은 패리티 인코딩 $C_m(n) = (c_1, \dots, c_m)$을 활용하며, 여기서 $c_i = T^{i-1}(n) \pmod 2$이다. 핵심적인 대수적 도구는 "교정 잔여" $R(C_m(n))$으로, 이는 $T^m(n) = (3^s n + R)/2^m$을 만족하도록 정의된다(여기서 $s$는 인코딩의 해밍 무게이다). 논문은 $R$이 오직 이진 인코딩에만 의존함을 입증하여, $T^m(n)$에 대한 분석을 특정 정수 값 $n$에 대한 참조 없이 오직 이진 문자열 수준에서 수행할 수 있게 한다.

2. 모듈러 인코딩과 그래프 구축:
   역학은 또한 $6$에 대한 모듈러 연산을 통해 인코딩되며, 정점${0, 1, 2, 3, 4, 5}$를 갖는 유향 그래프$G$를 사용한다. 전이는 현재 반복값의 패리티에 의해 결정된다. 저자는 정수 집합${1, \dots, 6 \cdot 2^m}$에서$G$내의 길이$m$인 유향 경로의 집합$\mathcal{P}_m(G)$로의 전단사 함수$\Psi_m$을 구축한다. 이 전단사 함수는 이진 인코딩 맵$\Phi_m$과 구조적 성질(전단사성, 주기성, 반대칭성)을 공유한다.

3. 스펙트럴 그래프 이론(Spectral Graph Theory):
   분석은 유효 부분 그래프 $G' = G[\{1, 2, 4, 5\}]$에 집중된다. 이는 (단계 2 이후) 홀수 궤적을 위한 유일한 흡수 강결합 성분(absorbing strongly connected component)이다. 본 논문은 $G'$의 스펙트럴 성질과 특정 정점을 제거하여 얻은 부분 그래프들의 성질을 조사한다. 핵심 메커즘은 전체 유효 부분 그래프 $G'$와 정점 4를 제거하여 얻은 부분 그래프 $H_4$ 사이의 스펙트럴 갭(spectral gap)에 기반한다.

주요 기여 및 결과

• 정확한 피보나치 개수 (정리 4.7):
  본 논문의 주요 결과는 특정 잔여를 회피하는 홀수의 정확한 개수를 산출하는 것이다. 각 $m \ge 1$에 대하여, 단계 $2, \dots, m$ 동안 잔여 클래스 $4 \pmod 6$를 회피하는 $\{1, \dots, 2^m\}$ 내의 홀수는 정확히 $F(m+1)$개이다. 여기서 $F(m+1)$은 $(m+1)$번째 피보나치 수이다. 이 개수는 회피 부분 그래프 $H_4$의 스펙트럴 반지름인 황금비 $\phi = (1+\sqrt{5})/2$로부터 도출된다.

• 지수적 감소율 (따름정리 4.9):
  그러한 정수의 비율은 $(\phi/2)^m$의 속도로 지수적으로 감소한다. 이 비율은 회피 부분 그래프의 스펙트럴 반지름 $\rho(H_4) = \phi$를 전체 유효 부분 그래프의 스펙트럴 반지름 $\rho(G') = 2$로 나눈 값과 정확히 일치한다.

• 모듈러 경로 정리 (정리 4.1):
  본 논문은 변위 $+2^m$이 모듈러 인코딩에 미치는 작용을 규명한다. 정수 $n$에 대하여, 모듈러 경로 레벨 $i$가 이 변위 하에서 보존될 필요충분조건은 $2^{i-1} \nmid n$인 것이다. 만약 $2^{i-1} \mid n$이라면, 경로는 $m+i$의 패리티에 따라 $+2$ 또는 $+4 \pmod 6$만큼 이동한다. 이러한 경직성(rigidity)은 차이가 $2^m$인 산술 급수 내의 길이 $m$인 순환들이 최소 $6 \cdot 2^m$만큼 떨어져 있음을 의미한다.

• 정점 필수성 및 스펙트럴 계층 구조 (정리 4.15):
  본 논문은 유효 부분 그래프 $G'$의 어떤 정점도 없앨 수 없음을 입증한다. $G'$ 내의 임의의 단일 정점 $v \in \{1, 2, 4, 5\}$를 제거하면 스펙트럴 반지름이 2 미만으로 엄격하게 감소한다. 결과적인 스펙트럴 반지름들은 다음과 같은 엄격한 계층 구조를 형성한다:
  $$\rho(H_2) = 1 < \rho(H_5) = \sqrt{2} < \rho(H_4) = \rho(H_1) = \phi < \rho(G') = 2$$
  이 계층 구조는 각 정점을 회피하는 궤적의 지수적 감소율을 결정한다.

• 양의 순환에 대한 제약 (따름정리 4.17 및 4.19):
  스펙트럴 계층 구조를 바탕으로, 본 논문은 $T$의 모든 양의 순환은 반드시 잔여 클래스 $2 \pmod 6$를 방문해야 함을 증명한다. 또한, $G'$ 내의 흐름 보존 항등식(flow conservation identities)을 사용하여, 정점 2가 길이 $m$인 임의의 양의 순환에서 전체 단계 중 $18\%$($> m(1-\log_3 2)/2$) 이상의 비중을 차지해야 함을 보여준다.

의의 및 주장
본 논문은 순열의 조합론적 열거 방식과는 구별되는, 모듈러 그래프 상의 스펙트럴 논증을 통해 콜라츠 궤적에서 피보나치 수가 나타나는 구조적 설명을 제공한다고 주장한다. 이러한 연결은 회피 부분 그래프의 페론-프로베니우스 고유값(Perron–Frobenius eigenvalue)인 황금비 $\phi$로부터 기인한다.

저자는 피보나치 개수가 근사치가 아니라, 스펙트럴 갭 $\phi/2 < 1$에 의해 구동되는 정확하고 무조건적인(exact and unconditional) 결과임을 강조한다. 이 연구는 기존 문헌에는 없는 새로운 모듈러 전단사 함수 $\Psi_m$과 그 구조적 성질을 도입한다. 본 논문은 콜라츠 추측 자체를 해결하지는 못하지만, 가설적 순환 내의 잔여 분포에 대한 엄격한 제약을 설정하며, 특히 정수 2가 불가피하며 임의의 순환 길이에서 상당한 비중을 차지해야 함을 증명한다. 결론적으로 본 논문은 효과성(effectivity)의 문제(정점 4의 첫 출현 횟수 제한)와 $G'$의 모든 정점이 비자명한 순환에 의해 방문되는지에 관한 열린 질문들을 제시한다.