CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)

이 논문은 군론 연구에 인공지능을 적용한 'CayleyPy' 프로젝트의 세 번째 논문으로, 기존 시스템보다 수백 배 빠른 성능을 제공하는 오픈소스 라이브러리를 공개하고, 대칭군 및 멱영군 등 다양한 군의 Cayley 그래프에 대한 200 여 개의 새로운 추측과 효율적인 지름 계산 공식을 제시합니다.

핵심

이 논문은 **"CayleyPy(케일리파이)"**라는 이름의 새로운 인공지능(AI) 도구를 소개하고, 이 도구를 이용해 수학의 난제들을 어떻게 해결했는지, 그리고 어떤 놀라운 발견들을 했는지에 대한 보고서입니다.

간단히 말해, **"AI 를 이용해 수학의 미로 찾기 문제를 해결하고, 그 과정에서 새로운 지도를 그렸다"**고 이해하시면 됩니다.

이 내용을 일상적인 비유와 함께 쉽게 설명해 드릴게요.

---

1. 이 연구는 무엇인가요? (CayleyPy 란?)

상상해 보세요. 거대한 미로가 있다고 칩시다. 이 미로의 각 교차로는 '상태'이고, 길을 가는 방법은 '이동'입니다. 수학자들은 이 미로를 **'케일리 그래프 (Cayley Graph)'**라고 부릅니다.

• 기존의 문제: 이 미로가 너무 커서 (예: 100! 개의 상태가 있는 경우) 기존 컴퓨터 프로그램 (GAP, Sage 같은 것들) 으로 길을 찾거나 미로의 가장 깊은 곳 (최대 거리) 을 계산하려면 수백 년이 걸릴 수도 있습니다. 마치 100 층짜리 빌딩을 한 계단씩 올라가며 모든 방을 확인하는 것과 비슷합니다.
• CayleyPy 의 등장: 이 연구팀은 **AI(인공지능)**와 **GPU(그래픽 카드)**의 힘을 빌려 이 미로를 훨씬 더 빠르고 효율적으로 탐색하는 새로운 도구 'CayleyPy'를 만들었습니다.
• 결과: 기존 프로그램보다 최대 1,000 배 더 빠릅니다. 마치 걸어서 가던 길을 초고속 열차로 바꾼 것과 같습니다. 덕분에 이제까지 계산할 수 없었던 거대한 미로들도 분석할 수 있게 되었습니다.

2. 이 도구로 무엇을 발견했나요? (주요 발견 3 가지)

연구팀은 이 강력한 도구를 이용해 약 200 개의 새로운 수학 가설 (추측) 을 세웠습니다. 그중 가장 흥미로운 것들은 다음과 같습니다.

① "미로의 크기는 예측 가능한 패턴이 있다" (준다항식 가설)

보통 미로의 가장 깊은 곳 (최대 거리) 을 찾는 것은 매우 어렵고, 컴퓨터로도 풀기 힘든 문제 (NP-hard) 로 알려져 있습니다. 하지만 연구팀은 **"어떤 규칙적인 미로들은 크기가 n(미로의 규모) 에 따라 아주 간단한 공식 (이차함수나 일차함수) 으로 예측 가능하다"**는 것을 발견했습니다.

• 비유: 미로가 커질 때마다 복잡해지기만 할 것 같지만, 알고 보니 "크기가 10 배 커지면 거리는 약 100 배 늘어난다"는 아주 단순한 법칙이 숨어있다는 것입니다. 이 법칙을 알면, 미로 전체를 다 찾아보지 않아도 크기를 쉽게 추정할 수 있습니다.

② "가장 먼 곳까지 가는 길은 '네모와 수염' 모양이다" (최대 거리 패턴)

어떤 미로에서 시작점과 가장 먼 지점 (최대 거리) 을 만드는 '열쇠' (생성자) 를 찾았을 때, 그 열쇠들의 모양이 무작위가 아니라 아주 특정한 패턴을 따른다는 것을 발견했습니다.

• 비유: 열쇠들을 그림으로 그리면 **'네모난 상자 (Square)'**와 그 옆에 붙은 '수염 (Whiskers)' 같은 모양이 반복됩니다. 연구팀은 이 패턴을 이용해 "아마도 이 모양의 열쇠들이 가장 긴 미로를 만들 것"이라고 추측했고, 실제로 작은 미로들에서 이 추측이 맞다는 것을 증명했습니다.

③ "소련 사이버네틱스之父가 남긴 50 년 전 숙제를 풀었다" (글루쇼프 문제)

1968 년, 소련의 유명한 과학자 글루쇼프는 "특정 두 가지 이동 규칙을 쓸 때, 미로의 최대 거리가 정확히 얼마일까?"라는 질문을 남겼습니다. 50 년 넘게 아무도 정확한 답을 못 냈습니다.

• 결과: CayleyPy 를 이용해 수많은 실험을 한 결과, 연구팀은 **"n 이 홀수일 때는 A 공식, 짝수일 때는 B 공식"**이라는 정확한 답을 추측했습니다. 마치 50 년간 잠들어 있던 퍼즐 조각을 AI 가 맞춰준 것과 같습니다.

3. 왜 이것이 중요한가요? (실생활과 미래)

이 연구는 단순히 수학 문제를 푸는 것을 넘어, 다음과 같은 의미를 가집니다.

• AI 가 수학을 발견한다: 과거에는 AI 가 이미 알려진 문제를 푸는 데만 쓰였지만, 이번에는 AI 가 아직没人이 모른 새로운 수학 법칙 (가설) 을 찾아냈습니다.
• 유전체 분석 (생물학): 우리 몸의 DNA 서열은 마치 퍼즐 조각을 뒤섞는 것과 같습니다. 이 연구에서 개발된 '미로 찾기' 기술은 유전자가 어떻게 변이되는지, 두 유전체 사이의 거리가 얼마나 되는지 계산하는 데 바로 쓸 수 있습니다.
• LLM(거대 언어 모델) 의 능력 테스트: 연구팀은 이 미로 문제를 "순서대로 정렬하는 문제"로 바꾸어 AI 챗봇 (LLM) 에게 풀게 했습니다. 결과는... 아직 AI 가 새로운 수학적 알고리즘을 스스로 만들어내기는 어렵다는 것을 보여주었습니다. 하지만 이는 AI 의 한계를 확인하고, 더 발전시킬 수 있는 좋은 '시험지'가 되었습니다.

4. 요약: 이 논문이 전하는 메시지

"우리는 AI 를 이용해 거대한 수학 미로 (Cayley Graph) 를 훨씬 빠르게 탐색할 수 있게 되었습니다. 그 과정에서 우리는 미로의 크기를 예측하는 새로운 법칙을 발견했고, 50 년 전의 미해결 문제를 풀었으며, 생물학의 DNA 분석에도 쓸 수 있는 도구를 만들었습니다. 이제 AI 는 단순한 계산기를 넘어, 새로운 수학적 진리를 발견하는 탐험가가 되었습니다."

이 연구는 **"컴퓨터의 빠른 계산 능력 + 인간의 통찰력 + AI 의 패턴 인식"**이 결합되었을 때, 어떤 놀라운 일이 일어날 수 있는지를 보여주는 멋진 사례입니다.

기술 요약

1. 연구 배경 및 문제 정의 (Problem)

• 케일리 그래프 (Cayley Graph) 의 중요성: 군론 (Group Theory) 의 핵심 개념인 케일리 그래프는 대수적 구조를 시각화하고, 조합론적 최적화 문제 (예: 퍼즐 해결, 경로 탐색) 와 밀접하게 연관되어 있습니다.
• 핵심 문제:
  • 지름 (Diameter): 그래프 내 두 노드 간 최단 경로의 최대 길이로, 군의 생성자 (generators) 집합에 따라 결정됩니다. 이는 '신의 숫자 (God's number)'로도 불리며, 퍼즐의 최악의 경우 해결 단계를 의미합니다.
  • 성장 (Growth): 특정 거리 (층) 에 있는 원소의 수를 나타내는 벡터로, 그래프의 확률 분포적 특성을 보여줍니다.
  • 계산적 난이도: 일반적인 유한 케일리 그래프에서 지름을 찾거나 요소를 생성자의 곱으로 분해하는 문제는 NP-난해 (NP-hard) 또는 P-space 완전 문제로 알려져 있습니다. 기존 컴퓨터 대수 시스템 (GAP, Sage) 은 대규모 군 (예: $S_{10}$ 이상) 에 대해 계산이 매우 느리거나 불가능합니다.
• 연구 목표: 인공지능 (AI) 및 심층 학습 기법을 활용하여 기존 시스템보다 수천 배 빠른 계산 속도로 대규모 케일리 그래프의 성장과 지름을 계산하고, 이를 통해 새로운 수학적 추측 (Conjectures) 을 도출하는 것입니다.

2. 방법론 (Methodology)

• CayleyPy 라이브러리 개발:
  • 오픈 소스 Python 라이브러리로, GPU 가속을 활용한 효율적인 너비 우선 탐색 (BFS) 알고리즘을 구현했습니다.
  • 성능: 기존 GAP/SAGE 시스템 대비 최대 1000 배 빠른 속도로 성장 계산을 수행하며, $S_{15}$ (약 $1.3 \times 10^{12}$ 원소) 와 같은 거대 군의 처리가 가능합니다.
  • 기능: 임의의 치환군 (Permutation groups) 및 행렬군 지원, 사전 정의된 생성자 집합 (퍼즐, 생물학적 모델 등) 포함, 그래프 시각화, 무작위 보행 (Random Walk) 시뮬레이션.
• 데이터 기반 발견 파이프라인:
  1. 계산 실험: CayleyPy 를 사용하여 다양한 생성자 집합에 대해 $n \le 15$ (일부 경우 $n \le 42$) 까지의 지름과 성장 데이터를 수집합니다.
  2. 패턴 인식: 수집된 데이터를 기반으로 지름과 성장 분포의 수학적 패턴 (다항식, 준다항식 등) 을 식별합니다.
  3. 추측 도출: 식별된 패턴을 바탕으로 새로운 수학적 추측을 제안합니다.
  4. 검증: AI 기반 경로 탐색 (Beam Search, Diffusion 모델 등) 을 통해 대규모 $n$에 대한 추측을 검증합니다.
• 벤치마킹 및 LLM 평가:
  • Kaggle 챌린지 형태로 10 개 이상의 벤치마크 데이터셋을 공개하여 다양한 경로 탐색 알고리즘을 평가합니다.
  • 생성자 제한 하의 정렬 문제를 LLM 에게 제시하여 연구 문제 해결 능력을 테스트합니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

가. 수학적 추측 (Mathematical Conjectures)

약 200 개의 새로운 수학적 추측을 도출하였으며, 그 중 주요 내용은 다음과 같습니다.

1. 지름의 준다항식성 (Quasi-polynomiality of Diameter):

   • $S_n$ (대칭군) 의 많은 케일리 그래프에서 지름이 $n$에 대한 준다항식 (Quasi-polynomial) (즉, $n \pmod s$에 따라 선형 또는 2 차 다항식으로 정의됨) 으로 표현된다는 것을 발견했습니다.
   • 이는 지름 계산이 일반적으로 NP-난해임에도 불구하고, 특정 생성자 집합에서는 효율적으로 계산 가능함을 시사합니다.

2. Babai 추측의 정교화 (Refinement of Babai's Conjecture):

   • Babai 추측 ($S_n$의 지름이 $O(n^2)$ 이하) 을 정교화하여, 표준 비방향 (undirected) 케일리 그래프의 지름 상한을 $n^2/2 + 4n$으로 제안했습니다.
   • 최대 지름을 생성하는 생성자 집합은 'Square-with-whiskers' (네모와 수염) 패턴을 따르는 대합 (Involution) 들임을 발견했습니다. ($n \le 15$까지의 탐색을 통해 확인).

3. Glushkov 문제 (1968) 에 대한 답:

   • 소련 사이버네틱스의 창시자 V. M. Glushkov 가 제기한 문제 (왼쪽 순환 이동과 첫 두 원소의 전치로 생성된 방향 케일리 그래프의 지름) 에 대한 추측적 해답을 제시했습니다.
   • 지름은 $n$이 홀수일 때 $(3n^2 - 8n + 9)/4$, 짝수일 때 $(3n^2 - 8n + 12)/4$로 추정됩니다.

4. 유니터리 군 (Unitriangular Groups) 및 멱영군 (Nilpotent Groups):

   • $\mathbb{Z}/p\mathbb{Z}$ 위의 상부 유니터리 군 $U(n, \mathbb{Z}/p\mathbb{Z})$의 지름이 $p$에 대해 선형적으로 의존한다는 Ellenberg 의 결과를 개선했습니다.
   • 멱영군에서의 성장 분포가 가우시안 분포 (정규 분포) 를 따를 것이라고 추측했습니다 (Diaconis 의 $S_n$ 결과와 유사한 중심극한정리 현상).

5. 생물학적 관련 생성자:

   • 역전 (Reversals) 과 전위 (Transposons) 를 생성자로 하는 그래프에 대해 이진 코셋 (Binary Coset) 상에서의 성장 패턴을 분석하고, 가우시안 분포와 일치하는 결과를 도출했습니다.

나. 기술적 성과

• 성능 향상: CayleyPy 는 GAP 대비 $S_{11}$에서 0.6 초 (GAP 는 2352 초) 로 1000 배 이상 빠른 성장을 계산합니다.
• 새로운 생성자 패밀리: 'Sheveleva2' (방향 그래프용) 와 'Koltsov3involutions' (비방향 그래프용) 라는 새로운 생성자 패밀리를 제안하여, $n \le 15$까지 알려진 최대 지름을 달성했습니다.
• LLM 벤치마크 (CayleyBench): 정렬 문제를 LLM 에게 제시하여 연구 문제 해결 능력을 평가하는 프레임워크를 구축했습니다. 현재 대부분의 LLM 은 잘 알려진 알고리즘 외의 새로운 생성자에 대한 코드를 생성하는 데 실패함을 확인했습니다.

4. 의의 및 중요성 (Significance)

1. 수학 연구의 패러다임 전환: 순수 수학 (군론, 조합론) 분야에서 AI 기반 계산 도구를 활용하여 기존에 풀리지 않던 문제들에 대한 새로운 통찰과 추측을 대량으로 생성할 수 있음을 입증했습니다.
2. 계산 효율성의 혁신: 기존 컴퓨터 대수 시스템의 한계를 극복하고, 거대 규모의 군 (Googol 크기) 에 대한 직접적인 계산을 가능하게 하여, '신의 숫자'와 같은 오랜 난제 해결에 새로운 길을 열었습니다.
3. 오픈 사이언스 및 커뮤니티 참여: Kaggle 챌린지 형식의 벤치마크와 오픈 소스 라이브러리를 통해 전 세계 연구자와 데이터 과학자가 케일리 그래프 문제에 참여하고 검증할 수 있는 환경을 조성했습니다.
4. AI 와 수학의 융합: 강화 학습 (RL) 이 그래프 경로 탐색 문제에 어떻게 적용될 수 있는지 보여주었으며, LLM 이 복잡한 수학적 알고리즘을 발명할 수 있는지에 대한 새로운 평가 기준을 제시했습니다.

5. 결론

이 논문은 CayleyPy라는 강력한 AI 기반 도구를 소개하고, 이를 통해 케일리 그래프의 성장과 지름에 관한 200 여 개의 새로운 수학적 추측을 제시했습니다. 연구진은 계산적 실험을 통해 지름이 준다항식 형태를 띤다는 놀라운 현상을 발견하고, Babai 추측을 정교화하며, 1968 년 Glushkov 의 문제를 해결할 단서를 제공했습니다. 이는 AI 가 이론 수학의 발전에 기여할 수 있는 구체적인 사례를 보여주며, 향후 더 큰 규모의 군과 복잡한 수학적 구조를 탐구하는 데 중요한 발판이 될 것입니다.