Erdős Problem #64 난제 풀기

최근 나는 한가지 궁금한게 생겼다.

AI가 얼마나 발전했을까? 어디까지 건드릴 수 있을까?

그래서 나는 AI를 어떤식으로 써볼까 고민을 좀 해봤다.

사실 ChatGPT Plus를 쓰는데 토큰이 좀 많이 남아서 어떻게 쓸까 고민하다가 여기까지 온거같다. (근데 이것 덕분에 배보다 배꼽이 더 커져서 Pro 구독까지 갈 줄은…)

그러던 중 인스타를 보다가 한 게시글이 내 이목을 끌었다.

“AI로 수학 난제를 풀었다!” 는 글이였다.

오… 나도 해볼까? 라는 생각이 들었고, 바로 풀만한 난제 탐색에 들어갔다. (이것마저 AI한테 시킨 게 좀 웃기긴 한데ㅋㅋ)

그중 가장 시도해볼만한 난제는 1000$의 상금이 걸린 Erdős Problem #64 문제였고, 나는 바로 연구에 착수했다.

코덱스를 이용하여 먼저 난제연구를 위한 툴들을 설치하고 대략적인 기초틀을 만든 후, 연구를 시작했다.

그런데 세상에!! 정말 진전을 보이는것 아닌가! (사실 이때는 아주 제한적인 수준의 그래프 일부를 다루는 정도였지만..)

이게 된다고..?? 싶어서 흥분을 감추지 못했다.

그런데 이럴수가.. GPT Plus의 한도는 생각보다 넉넉치 못했다…

나는 고민했다…

눈 딱 감고 Pro 한 번 구독해볼까..?

Pro플랜의 가격은 무려.. 16만원…!!! 아무런 경제활동도 하지 않는 대학생인 나에겐 너무나도 큰 투자였다..

하지만.. 이 난제를 풀면.. 1000달러 주잖아..?

대략 30분간의 고민 끝에 나는 결국 Pro플랜을 결제했고, 험난한 수학 난제풀기 여정이 본격적으로 시작되었다.

그렇게 내가 고른 문제는 정확히 이런 문제였다.

“모든 정점이 최소 3개의 선으로 연결된 그래프에는, 길이가 4, 8, 16, 32, … 중 하나인 고리가 반드시 존재하는가?”

수식으로 쓰면 대충 이런 느낌이다.

δ(G) ≥ 3 인 모든 finite simple graph G는
길이 2^k, k ≥ 2 인 simple cycle을 가지는가?

처음 보면 뭔 소린가 싶다.

쉽게 말하면, 그래프는 점과 선으로 이루어진 구조다.

점 하나하나를 “정점”, 선을 “간선”이라고 부른다.

그리고 최소차수 3이라는 말은 모든 점이 적어도 선 3개 이상에 연결되어 있다는 뜻이다.

예를 들면 이런 느낌이다.

한 점이 외톨이면 안 됨.
선 하나만 달린 점도 안 됨.
선 두 개만 달린 점도 안 됨.
모든 점이 최소 3갈래 이상으로 뻗어 있어야 함.

그런데 이렇게 촘촘하게 연결된 그래프라면, 그 안에 반드시 어떤 “고리”가 생긴다.

문제는 그 고리의 길이가 꼭

4, 8, 16, 32, ...

처럼 2의 거듭제곱인 경우가 있느냐는 것이다.

처음엔 솔직히 “이게 왜 어렵지?” 싶었다.

그래프가 복잡하면 고리도 많을 텐데, 그중 하나쯤은 4나 8이나 16 아니겠어?

라고 생각했다.

하지만 난제는 괜히 난제가 아니었다.

반례를 만들려면 이런 괴상한 그래프를 찾아야 한다.

모든 정점은 최소 3개 이상 연결되어 있음.
그런데 길이 4짜리 고리 없음.
길이 8짜리 고리 없음.
길이 16짜리 고리 없음.
길이 32짜리 고리 없음.
...

즉, 연결은 빡빡한데 2의 거듭제곱 길이 고리만 전부 피해가는 그래프를 찾아야 한다.

이게 말이 쉽지, 막상 컴퓨터로 뒤져보면 계속 이런 식이다.

C4는 피했다!
→ C8이 나옴

C4, C8은 피했다!
→ C16이 나옴

C4, C8, C16까지 피했다!
→ C32가 튀어나옴

마치 두더지 잡기 같았다.

하나를 누르면 다른 쪽에서 튀어나오고,

그걸 또 누르면 더 큰 놈이 튀어나왔다.

처음에는 그냥 그래프들을 무작정 생성해서 검사했다.

“이 그래프에 C4 있나?”

“C8 있나?”

“C16 있나?”

이런 걸 계속 확인했다.

여기서 C8은 길이 8짜리 cycle을 뜻한다.

즉, C16은 길이 16짜리 고리, C32는 길이 32짜리 고리다.

그러다가 점점 이상한 패턴이 보이기 시작했다.

특정 그래프들은 정말 C4, C8, C16을 잘 피해 갔다.

심지어 거의 반례처럼 보이는 친구들도 있었다.

그런데 결정적인 순간마다 C32가 살아 있었다.

“아니 얘는 진짜 되는 줄 알았는데 또 C32네?”

이런 일이 반복됐다.

그래서 처음에는 반례를 찾는 방향으로 갔다가, 점점 생각이 바뀌었다.

혹시 반례가 없는 게 맞고, C32나 C16이 살아나는 이유를 증명할 수 있는 거 아닐까?

이때부터 연구 방향이 바뀌었다.

단순히 그래프를 찾는 게 아니라, 그래프가 왜 자꾸 2의 거듭제곱 길이 고리를 피하지 못하는지 구조를 보기 시작했다.

그러면서 나온 아이디어가 대충 이런 것이다.

그래프 안에는 반복적으로 등장하는 작은 부품들이 있었다.

삼각형
C5 조각
fan 구조
terminal path
hub 주변 구조
ear ladder

이런 것들을 하나의 “부품”, 즉 atom처럼 보고 압축하는 것이다.

비유하자면, 복잡한 회로를 볼 때 저항 하나하나를 다 보는 게 아니라, 특정 회로 블록을 하나의 부품처럼 보는 것과 비슷하다.

그래프도 마찬가지로, 작은 구조들을 접어서 보면 더 큰 뼈대가 보인다.

그리고 핵심은 이거였다.

어떤 압축된 고리를 원래 그래프에서 다시 펼치면, 길이가 하나로 고정되는 게 아니라 여러 가능성이 생긴다.

예를 들어 어떤 부품을 지나갈 때 길이가

1 또는 4

가 될 수도 있고, 다른 부품에서는

2 또는 3

이 될 수도 있다.

그러면 전체 고리 길이는 이런 식으로 가능한 값들의 합이 된다.

possible length = atom_1 length + atom_2 length + atom_3 length + ...

즉 고리 하나가 실제 그래프에서는 여러 길이로 “펼쳐질” 수 있다.

이걸 나는 내부적으로 atom-lift처럼 다루기 시작했다.

어떤 경우에는 가능한 길이들이 듬성듬성하다.

예를 들어 {1,4}처럼 중간에 2,3이 비어 있으면 2의 거듭제곱을 피할 여지가 있다.

그런데 여러 부품이 섞이면 이 빈칸이 메워진다.

예를 들어 가능한 길이들이 점점 이런 식으로 변한다.

{1,4}

에서 시작했는데 다른 부품들이 섞이면,

[5, 6, 7, 8, 9]

처럼 연속된 구간이 되어버린다.

그러면 문제가 생긴다.

연속된 구간이 충분히 두꺼우면, 그 안에 4, 8, 16, 32 같은 2의 거듭제곱이 끼어들 가능성이 매우 높아진다.

그래서 반례가 살아남으려면 가능한 길이 구간을 아주 좁은 틈에 숨겨야 한다.

수식으로 쓰면 이런 느낌이다.

2^k < A ≤ possible lengths ≤ B < 2^(k+1)

즉 가능한 길이 전체가 2의 거듭제곱 사이의 틈, dyadic gap 안에 통째로 숨어야 한다.

그런데 그래프가 복잡해질수록, 이걸 모든 고리에 대해 동시에 만족시키는 게 점점 어려워진다.

여기서 연구가 꽤 흥미로워졌다.

처음에는 그냥 “C16이 있냐 없냐”를 검사했다면, 나중에는 이런 질문을 하게 됐다.

반례가 살아남으려면
어떤 길이를 어디에 숨겨야 하는가?

그 숨는 위치가 실제로 사용 가능한가?

만약 그 위치가 막혀 있다면,
다른 경로로 돌아올 수밖에 없는가?

그 다른 경로가 다시 C8이나 C16을 만드는가?

이런 식으로 문제를 바라보기 시작한 것이다.

특히 최근에는 이런 생각까지 갔다.

반례 후보가 2의 거듭제곱 길이를 피하려면, 위험한 길이가 나오는 지점을 전부 “죽은 자리”에 숨겨야 한다.

내부적으로는 이걸 hole-hiding이라고 부르고 있다.