최근 수정 시각 : 2022-08-05 21:14:48

콜라츠 추측

[math(\large 3n+1)]
콜라츠 추측 관련 둘러보기 틀
[ 펼치기 · 접기 ]
----
이산수학 · 수리논리학
Discrete Mathematics · Mathematical Logic
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px"
{{{#!wiki style="letter-spacing: -1px"
이론
기본 대상 명제 · 집합 · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
명제 논리 · 논증{ 귀납논증 · 연역논증} · 공리 및 공준 · 증명{ 귀류법( 자동정리증명) · 수학적 귀납법 · 반증 · 역산( 검산) · PWW · 더블 카운팅 · 논증의 재구성} · 존재성과 유일성 · · · 대우 · 예비사항( 약어 및 기호) · 논리함수 · 논리 연산 · 동치관계( 등식) · 잘 정의됨 · 조건문( 조각적 정의) · 명제 논리 · 양상논리 · 술어 논리
집합 원소 · 공집합 · 집합족( 묶어 세기) · 곱집합 · 멱집합 · 관계 · 서수( 비교하기 · 순서 관계 · 하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC( 선택공리) · 구간 · 기수( 초한기수) · 절대적 무한
수열 등차수열( 뛰어 세기 · 등차중항) · 등비수열( 등비중항) · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
알고리즘 순서도 · 시간 복잡도( 점근 표기법) · 자료구조 · 해시 · 오토마타( FSM · 푸시다운 · 튜링 머신 · 콘웨이의 생명 게임) · 동적 계획법( 사전 공격 · 레인보우 테이블) · 프로그래밍( 코딩 · 컴파일링) · 유클리드 알고리즘 · RSA( 쇼어 알고리즘) · 유전 알고리즘
조합 경우의 수( 공식) · 순열( 완전순열 · 염주순열) · 치환 · 분할( 분할수) · 최단거리 · 스털링 수( 제1종 스털링 수 · 제2종 스털링 수) · 카탈랑 수 · 벨 수 · 라흐 수 · 그래프( 수형도) · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로)
확률 사건 · 가능성 · 확률 변수 · 확률 분포( 정규 분포 · 이항 분포 · 푸아송 분포 · 카이-제곱 분포 · t-분포 · z-분포) · 조건부 확률 · 기댓값 · 도박사의 오류 · 몬티 홀 문제 · 뷔퐁의 바늘
기타 셈 측도 · 비율( 분율) · 진법( 2 · 8 · 10 · 12 · 16 · 60) · 난수 · 암호 · 시행착오( 예상과 확인 · 브루트 포스) · 벤 다이어그램 · 구구단( 네이피어 계산봉) · 주산 · 산가지 · 암산 · 논리 회로 · 인접행렬 · 결합법칙 · 분배법칙 · 교환법칙 · 마크업 언어
정리
4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 베이즈 정리 · 비둘기 집의 원리 · 포함·배제의 원리 · 드모르간 법칙 · 대각선 논법 · 전체 확률의 법칙 · 쾨니히스베르크 다리 건너기 문제 · 상트페테르부르크의 역설 · 러셀의 역설 · 거짓말쟁이의 역설 · 투표의 역설 · 바나흐-타르스키 역설 · 퍼스의 항진명제 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 마르코프 부등식 · 체비쇼프 부등식 · 큰 수의 법칙( 무한 원숭이 정리 · 던파확률의 법칙) · 중심극한정리 · 굿스타인 정리 · 불완전성 정리 · 힐베르트의 호텔 · 정지 문제 · 연속체 가설 · P-NP 문제미해결 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 카오스 이론미해결
분야
집합론 · 조합론 · 범주론 · 정수론 · 확률론 · 전산학 · 암호학 · 통계학 · 수학철학 · 수리사회학
관련 문서
철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 }}}}}}}}}}}}

''' 이론 컴퓨터 과학
{{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"'''
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px"
{{{#!wiki style="letter-spacing: -1px"
이론
기본 대상 수학기초론( 수리논리학 · 계산 가능성 이론 · 범주론 · 집합론), 이산수학( 그래프 이론)
다루는 대상과 주요 토픽
계산 가능성 이론 재귀함수 · 튜링 기계 · 바쁜 비버
계산 복잡도 이론 점근 표기법 · 튜링 기계^ 고전, PRAM, 양자, 비결정론적^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법)
오토마타 이론 FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식
수학적 최적화 조합 최적화 TSP · 담금질 기법 · 유전 알고리즘 · 기계학습
볼록 최적화 내부점 방법 · 경사하강법
선형계획법 심플렉스법
주요 알고리즘 및 자료구조
기초 정렬 알고리즘 · 순서도
추상적 자료형과 그 구현 배열^ 벡터^ · 리스트^ 연결 리스트^ · 셋(set)^ 레드-블랙 트리, B-트리^ · 우선순위 큐^, 피보나치 힙^
계산 수론 및 암호학 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · RSA · AES · LLL 알고리즘 · 해시( 암호화폐)
계산기하학 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN
그래프 이론 탐색^ BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘
정리
정지 문제 대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 }}}}}}}}}}}}

해석학 · 미적분학
Analysis · Calculus
{{{#!wiki style="word-break: keep-all; margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px; letter-spacing: -1px"
<colbgcolor=#8f76d6> 함수 합성 · 항등원 · 역원 · 멱함수( 비례·반비례 ) · 초등함수( 대수함수 · 초월함수) · 특수함수 · 범함수 · 다변수 ( 동차 · 숨은 함수( 다가 함수 )) · 그래프 · 대칭 · 증감표 · 극값 · 연속 · 매끄러움 · 계단형 · 미끄럼틀형 · 볼록/오목 · 닮은꼴 함수 · 병리적 함수 · 해석적 연속 · 로그함수 · 지수함수 · 삼각함수
정리 · 토픽 좌표계 · 중간값 정리 · 최대·최소 정리 · 부동점 정리 · 오일러 동차함수 정리 · 립시츠 규칙
극한 부정형 · 어림( 유효숫자 ) · 근방 · 수열의 극한 · 엡실론-델타 논법 · 수렴 ( 균등수렴 ) · 발산 · 점근선 · 무한대 · 무한소 · 스털링 근사
정리 · 토픽 로피탈의 정리 · 슈톨츠-체사로 정리
수열
급수
규칙과 대응 · 단조 수렴 정리 · 멱급수 · 테일러 급수 ( 일람 ) · 조화급수 · 그란디 급수 · 망원급수 ( 부분분수분해 ) · 오일러 수열 · 베르누이 수열 · 파울하버의 공식 · 리만 재배열 정리
정리 · 토픽 바젤 문제 · 라마누잔합 · 0.999…=1 · 콜라츠 추측미해결
미적분 미분 도함수 일람 · 차분 · 유율법 · 변화량 · 변분법 · 도함수 ( 편도함수 ) · 곱미분 · 몫미분 · 연쇄 법칙 · 역함수 정리 · 임계점 ( 변곡점 · 안장점 ) · 미분형식 · 미분방정식 ( 풀이 ) · [math(boldsymbolnabla)] · 라그랑주 승수법
적분 역도함수 일람 · 부분적분 ( LIATE 법칙 · 도표적분법 · 예제 ) · 치환적분 · 정적분 ( 예제 ) · 이상적분 · 중적분 ( 선적분 · 면적분 · 야코비안 ) · 르베그 적분 · 스틸체스 적분 · 코시 주요값
정리 · 토픽 평균값 정리 ( 롤의 정리 ) · 스토크스 정리 ( 발산 정리 · 그린 정리 ) · 라플라스 변환 · 푸리에 해석 ( 푸리에 변환 ) · 아다마르 변환 · 미적분의 기본정리 · 2학년의 꿈 · 리시 방법

해석
측도론 ( 측도 · 르베그 측도 ) · 유계( 콤팩트성 ) · 칸토어 집합 · 비탈리 집합
정리 · 토픽
복소
해석
복소평면 · 편각 · 코시-리만 방정식
정리 · 토픽 오일러 공식 ( 드 무아브르 공식 ) · 리우빌의 정리 · 바이어슈트라스 분해 정리 · 미타그레플레르 정리
여타 하위 학문 수치해석학 ( FEM ) · 미분기하학 · 해석기하학 · 해석적 정수론 ( 소수 정리 ) · 벡터 미적분학 · 확률론 ( 중심극한정리 )
기타 뉴턴-랩슨 방법 · 디랙 델타 함수 · 리만 가설미해결 · 카오스 이론미해결 · merry=x-mas
응용 수리물리학 · 수리경제학( 경제수학) · 공업수학 }}}}}}}}}
1. 개요2. 어떤 추측인가?3. 해결하기 어려운 이유4. 일반화5. 페르마의 마지막 정리와의 비교6. 테렌스 타오의 접근7. 여담8. 관련 링크

1. 개요

Veritasium한국채널의 설명

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

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

2. 어떤 추측인가?

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

[math( T(n) = \begin{cases} \begin{array}{cl} \begin{aligned}\dfrac n2 , \end{aligned}& \textsf{if }n\textsf{ is even} \\ 3n+1, & \textsf{if }n\textsf{ is odd} \end{array} \end{cases} )]

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

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

이 추측의 반례는 아직 나오지 않았고, 아마도 참일 것으로 추정된다. 반례가 하나라도 나오는 순간 별다른 증명이 필요없이 저 추측은 거짓인 것으로 문제가 끝나기 때문이다. 이미 1980년대에 컴퓨터를 이용해 약 1까지의 숫자를 넣어보았지만 모두 1에 도달했다.[2]

아무튼 이 추측은 80년이 넘도록 풀리지 않고 있다. 게다가 상금도 걸려 있다. 1000파운드와 500달러의 상금이 걸려 있는데, 이중 500달러의 상금을 건 사람은 에르되시 팔이다.[3] 또한 1.2억엔(약 11억)의 상금을 지급한다. https://mathprize.net/posts/collatz-conjecture/

약간 변형된 표현으로
[math( T'(n) = \begin{cases}\begin{array}{cl} \begin{aligned} \dfrac n2, \end{aligned}& \textsf{if }n\textsf{ is even} \\ \begin{aligned} \dfrac{3n+1}2, \end{aligned}& \textsf{if }n\textsf{ is odd}\end{array}\end{cases})]
라고 나오기도 한다. 홀수에 대해서 3n+1 을 하면 무조건 짝수가 되는데, 그 다음 단계에서 2로 나누게 되므로 한단계를 생략하고 미리 2로 나눈 것이다. 이 수열의 끝이 1이냐 아니냐만 중요하기에 중간 단계를 간략화하는 것은 별다른 영향을 주지는 않는다. 다만, 최대 얼마까지 커지느냐를 따지는 경우라면 원래의 표현을 기준으로 해야 한다.

3. 해결하기 어려운 이유

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

그리고 야생 함수이기 때문에 헬게이트가 오픈된다. 증가율이 항상 높기 때문. 이것 때문에 심지어 "항상 콜라츠 함수의 값은 감소한다"는 명제도 증명이 안 되고 있다.

4. 일반화

결론부터 말하면 일반화를 해도 진전이 없다. 콘웨이의 생명 게임 창시자로 유명한 존 호튼 콘웨이 1972년 정지 문제를 이용해 일반화한 문제는 결정 불가능하다고 증명했기 때문이다. 콜라츠 추측이 결정 불가능하다는 게 아니다. 콜라츠 추측은 짝수면 1/2를 곱하고, 홀수면 3n+1을 하는 함수 g가 주어지고, 모든 n에 대해 이것이 수렴하는지 묻는 것인데, 이제는 n(mod P)에 따라서 서로 다른 P개의 일차함수를 통해 값을 반환하는 더 일반화된 함수 g를 생각하자는 것이다. 이때, 콘웨이의 증명은 이러한 임의의 g와 n이 주어졌을 때, gk(n)이 1에 도달하는지 푸는 문제는 결정 불가능하다는 것이다.[4]

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

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

5. 페르마의 마지막 정리와의 비교

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

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

6. 테렌스 타오의 접근

2019년 9월 8일 타오가 콜라츠 추측을 건드렸다. 논문 기사
  • 어떤 함수 [math(f(x))]에서
  • [math(x)]가 무한히 커질 때 [math(f(x))]도 무한이 되면
  • 거의 모든 자연수 [math(N)]에 콜라츠 함수를 반복하면 [math(f(N))] 이하로 언젠가는 떨어진다.
  • '거의 모든'이 수학적이지 않아 납득이 안 갈 수 있는데 조건을 만족시키는 수의 확률이 1에 수렴한다는 것을 의미한다.
  • 이 말은 '거의 모든 자연수에 대하여 콜라츠 추측이 성립한다'와 동치이다. 로그를 여러 번 사용한 함수같이 매우 천천히 무한으로 발산하는 함수가 있기 때문이다. 피곤한 웜뱃함수라던가

물론 이 말은 콜라츠 추측 자체를 증명한 것은 아니다. 당장 아래 문단에 있는 3n-1 문제에 대해서도 같은 논리를 적용할 수 있지만, 1로 끝나지 않는 루프가 발견되었다. 참고로 "콜라츠 추측은 (거의) 필연적으로 감소한다"는 것은 타오 이전에도 이미 증명되었는데, 1976년에 [math(f(x)=x)]인 경우[7][8]가, 1979년에 [math(f(x)=x^{0.869})]인 경우가, 1994년에 [math(f(x)=x^{0.7925})]인 경우가 증명되었기 때문이다. 즉 타오의 업적은 이를 엄청나게 일반화 시켜서 '거의 모든 자연수에 대하여 콜라츠 추측이 성립한다'를 증명한 것이다.[9] 2020년 타오 본인이 정리한 프레젠테이션을 보면 관련 내용이 언급된다.

그러나, 테렌스 타오의 논문은 학회지에 게재되지 않아 논문 심사를 통과하지 않은 단독게재 논문이며 그 논문이 참인지는 교차검증되지 않은 상태이다.하지만 타오가 그렇다면 그런 거지. 물론 이 증명이 참이라 해도 여전히 반례가 존재할 가능성이 있다. 단적으로 자연수 N이 합성수일 확률은 1에 수렴하지만(=거의 모든 자연수는 합성수지만) 그 반례인 소수는 무한하다.

7. 여담

만약 이 추측이 거짓이라면, 1로 가지 않는 반례가 존재한다는 것을 의미한다. 수학자들은 이런 대표적인 반례에 대해서 자기 자신으로 순환하는 루프가 존재할 것으로 예상한다[10]. 예를들어 문제를 3n+1 이 아니라 3n-1 로 살짝 변경하면 5의 경우 아래와 같은 루프가 만들어 진다.
counter example of (3n-1) problem
5 → 14 → 7 → 20 → 10 → 5
17의 경우에도 비슷한 루프가 만들어진다.
counter example of (3n-1) problem
17 → 50 → 25 → 74 → 37 → 110 → 55 → 164 → 82 → 41 → 122 → 61 → 182 → 91 → 272 → 136 → 68 → 34 → 17
비록 3n-1의 명제의 경우 반례가 있어서 거짓으로 증명되었지만 1억까지 대입했을 때 5 루프와 17 루프 이외의 다른 루프(반례)는 없었다고 한다. 확률적으로 감소한다는 통계가 유한번 재귀했을 때 1로 수렴하는 것을 증명하지 못한다는 걸 보여주는 좋은 예시라고 할 수 있다.

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

8. 관련 링크



[1] <The Ultimate challenge:The 3x+1 problem>이라는 관련 서적을 쓰기도 했으며 이 외에도 리만 가설을 조화수열 형태로 정리한 걸로 유명하다. [2] 2020년 [math(2^{68})]까지 참으로 드러났다. 하지만 이건 겨우 2.95해에 불과하다. 1919년 제안된 포여 추측은 반례가 무려 [math(1.845\times10^{361})]에서 발견되었기 때문에 이는 한참 부족하다고 볼 수 있다. [3] 에르되시가 500달러를 걸었지만 증명이 안 되자 "수학은 아직 이런 문제를 풀 준비가 되어있지 않다"(Mathematics may not be ready for such questions)라는 말을 남겼다. [4] 사실 이 g가 튜링 완전하기 때문에 정지 문제가 적용된다. 그래서 이걸로 만든 프로그래밍 언어를 FRACTRAN이라고 한다. 콘웨이가 짠 P=6,469,693,230짜리 소수 생성 프로그램은 덤 [5] P=1, g(x)=2x 와 같은 경우가 있다. [6] 상술했듯 이미 일반화한 문제는 결정 불가능함이 증명되었기도 하다. [7] 즉 콜라츠 함수를 반복할 경우 초기값보다 작아질 확률은 1이다. [8] 이 버전을 거의 모든 자연수 [math(N)]에서 모든 자연수 [math(N)]으로 바꿔 증명할 수만 있다면 콜라츠 추측도 무한강하법으로 증명할 수 있지만 아직까진 아무도 성공하지 못했다. [9] 참고로 2003년에는 충분히 큰 자연수 N에 대해 N 이하의 자연수 중 최소 [math(N^{0.84})]만큼은 콜라츠 추측이 성립한다는 것이 증명되었다. [10] 1993년 Eliahou는 반례가 가질 수 있는 루프의 길이를 구하는 공식을 발견했는데, 최소길이가 무려 17,087,915이므로 루프를 찾기가 쉽지는 않다.