불리언 피타고라스 트리플 문제가 해결되었나?

해커뉴스[1]에서 어느 수학 문제의 기괴한 증명을 소개하고 있다.

Boolean Pythagorean triples problem이라는 문제가 있다고 한다. 자연수 전체를 겹치지 않는(disjoint) 두 부분집합으로 나누되, 어느 한 쪽의 세 원소도 피타고라스 트리플(a^2 + b^2 = c^2) 을 만족하는 세 수가 안 되도록 나누는 것이 가능하냐는 질문이다. 뭐 본인은 처음 듣는 문제인데, 위키피디아에 따르면 안 풀린지 거진 30년이 돼 가는 듯.

이 문제의 풀이가 근래 제시된 모양[2]인데, 네이쳐 뉴스[3]에 따르면 증명의 가장 중요한 부분이 컴퓨터로 해결되었다고 한다. 그런데 그 용량이 200테라바이트나 돼서 도저히 사람이 직접 확인할 수 없는 분량이라고.

뭐 이게 증명이냐?하고 묻는 건 4색 문제 논의의 재탕이다. 다른 머신으로 다른 코드로 교차증명을 시도하면 될 일인 듯 하다. 다만, 좀 더 쌈빡한 증명이 나왔으면 하는 바램은 있다. ㅋ

문제만 보면 걍 정수론 문제 같은데, 막상 논문[2]을 보면 완전 전산 수학이다. 앞부분 부터 본인이 완전 첨보는 용어와 정리들이 쏟아져 나온다. Van der Waerden’s theorem 같은 정리는 처음 본다-_-

모르는 용어가 많아서 대충 보고 접었는데 ㅋ, 왠지 해석적이나 대수적 정수론 방법으로도 접근할 수 있지 않을까 하는 생각이 든다. 어쨌든 sum-free set을 구성한다는 점에서 페르마의 마지막 정리와 유사한 점은 있다.

 


2016.6.14
Just how big is a big proof? in the Aperiodical
와하하

 


2016.7.21
Very Long Proofs in Azimuth

 


[1] https://news.ycombinator.com/item?id=11783648
[2] Marijn J. H. Heule, Oliver Kullmann, Victor W. Marek (2016) “Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer”, arXiv:1605.00723 [cs.DM]
[3] 네이쳐 Two-hundred-terabyte maths proof is largest ever 26 May 2016

2 thoughts on “불리언 피타고라스 트리플 문제가 해결되었나?

  1. 대수적이나 해석적 정수론 문제는 절대 아니고, 그냥 순수 조합론 문제일 거예요. 그것도 직관같은 거 없는 그런 (…)
    자연수라는 말부터 대수적 정수론을 전혀 쓸 수 없게 생겼고, 해석적 정수론도 뭔가 해석학적으로 해석할 거리가 너무 없어서… 그냥 Remsey theory 문제인 걸로…
    그나저나 이게 완전히 컴퓨터의 힘만으로 풀린다니… 이제 정수론이 멸망할 때가…

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중