Improved lower bounds for the Shannon capacity of odd cycles

기술 요약: 홀수 사이클의 샤논 용량에 대한 개선된 하한값

문제 정의
그래프 $G$의 샤논 용량 $\Theta(G)$는 $G$로 정의된 노이즈 채널에 대한 최대 무오류 통신율을 정량화한다. 이는 $\Theta(G) = \sup_{d \in \mathbb{N}} \alpha(G^d)^{1/d}$로 정의되며, 여기서 $\alpha(G^d)$는 $G$의 $d$차 강곱(strong product)의 독립수(independence number)이다. $\Theta(C_p)$의 경우 짝수 사이클에 대해서는 $p/2$이고, $C_5$에 대해서는 $\sqrt{5}$이지만, $r > 2$인 홀수 사이클 $C_{2r+1}$에 대한 값은 여전히 알려져 있지 않다. $\Theta(C_7)$을 결정하는 것은 매우 어려운 미해결 과제이다. 하한값을 설정하기 위한 표준적인 접근 방식은 $C_k^d$의 강곱에서 큰 독립 집합을 구성하여 $\alpha(C_k^d)^{1/d}$라는 양을 극대화하는 것이다.

방법론
저자들은 명시적인 조합론적 독립 집합 구성을 발견하기 위해 대규모 언어 모델(LLM), 구체적으로 ChatGPT-5.6 Sol Pro와 반복적인 상호작용을 사용하는 방법을 채택하였다. 이 방법론은 저자들이 광범的一한 시도에도 불구하고 보고된 하한값에 도달하지 못했다고 언급한 전통적인 휴리스틱 탐색(예: 시뮬레이티드 어닐링 또는 로컬 서치 알고리즘)과는 차이가 있다.

과정은 다음과 같다:

1. 프롬프팅(Prompting): 저자들은 LLM에 특정 매개변수(사이클 길이 $k$, 곱 차원 $d$, 기존의 최선 알고리즘, 그리고 개선 목표 대상 크기)를 제공하였다.
2. 생성 및 실행(Generation and Execution): 모델은 탐색 프로그램을 생성하고, 자신의 환경 내에서 이를 실행한 뒤, 후보 독립 집합을 반환하였다.
3. 반복적 정교화(Iterative Refinement): 저자들은 모델이 찾은 초기 결과보다 카디널리티(cardinality)를 더 높이기 위해 후속 프롬프트를 진행하였다.
4. 검증(Verification): 구성된 모든 집합은 저자들에 의해 엄격하게 검증되었으며, 이는 두 벡터가 모듈로 $k$에 대해 모든 좌표에서 1 이하로 차이 나지 않는 유효한 독립 집합임을 보장한다.

주요 기여 및 결과
본 논문은 강곱에서의 더 큰 독립 집합을 구성함으로써 네 가지 특정 홀수 사이클에 대한 개선된 샤논 용량 하한값을 제시한다:

• $C_7$ (7-사이클): 저자들은 강 10-곱 $C_7^{10}$에서 크기가 134,753인 독립 집합을 구성하였다. 이는 이전의 최선치인 $367^{1/5}$ (즉, $C_7^5$에서의 크기 367 집합)를 개선한 것이다.

  • 새로운 하한값: $\Theta(C_7) \geq 134753^{1/10} > 3.258020$ (이전 값 $> 3.257865$).
  • 구성 전략: 해당 집합은 Polak와 Schrijver의 크기-367 집합 $R$을 수정하여 도출되었다. 저자들은 $R$에서 특정 벡터들을 삭제하여 부분 집합 $B$를 형성한 후, $R$과 특정 변환으로부터 유도된 추가 벡터들을 결합하여 최종 집합 $I$를 구성하였다($I = B \times B$에 추가 벡터를 증강함).

• $C_{11}$ (11-사이클): $C_{11}^6$에서 크기 21,909인 독립 집합이 발견되었다.

  • 새로운 하한값: $\Theta(C_{11}) \geq 21909^{1/6} > 5.289773$ (이전 값 $148^{1/3} > 5.289572$).
  • 구성 전략: 크기-148인 $C_{11}^3$의 집합으로부터 시작하여, 저자들은 특정 부분 집합($DL, DR, BL, BR$)과 보조 벡터 집합($F_A, F_B, \dots$)을 정의하여 6-곱에서의 집합을 구성하였다.

• $C_{13}$ (13-사이클): $C_{13}^6$에서 크기 62,530인 독립 집합이 발견되었다.

  • 새로운 하한값: $\Theta(C_{13}) \geq 62530^{1/6} > 6.300109$ (이전 값 $247^{1/3} > 6.274305$).
  • 구성 전략: LLM은 보조 그래프 $G_A$ (134개의 정점 보유) 상에서 무작위 로컬 서치를 구현하여 $\mathbb{Z}_{13}^4$ 내의 370개 벡터를 가진 큰 독립 집합 $S$를 찾았다. 최종 집합 $I$는 $\{x \in \mathbb{Z}_{13}^6 : Ax \in S\}$로 정의된다.

• $C_{15}$ (15-사이클): $C_{15}^8$에서 크기 8,076,974인 독립 집합이 발견되었다.

  • 새로운 하한값: $\Theta(C_{15}) \geq 8076974^{1/8} > 7.301399$ (이전 값 $2842^{1/4} > 7.301397$).
  • 구성 전략: 크기-2842인 $C_{15}^4$ 집합으로부터 시작하여, 저자들은 특정 벡터들을 삭제하고 다른 벡터들을 추가하여 기초 집합 $R$을 형성하였다. 최종 집합은 인접 조건에 기반한 룩업 테이블($W_0, W_1$)로 결정되는 벡터들을 증강한 $B \times B$ ($B \subset R$)로 형성되었다.

또한, 본 논문은 샤논 용량 하한값을 직접적으로 개선하지는 않지만, 개별 강곱의 독립수(independence number)에 대한 개선된 하한값들(예: $\alpha(C_{11}^4) \geq 766$, $\alpha(C_{15}^3) \geq 383$)을 보고한다.

의의 및 주장
본 논문은 이러한 결과들이 $\Theta(C_7), \Theta(C_{11}), \Theta(C_{15})$의 알려진 하한값에 대한 완만한 개선이며, $\Theta(C_{13})$에 대해서는 더 유의미한 개선이라고 주장한다.

이 연구의 주요 의의는 방법론에 있다:

1. LLM의 효능: 이러한 구성들은 LLM과의 반복적인 상호작용을 통해 발견되었으며, 이는 저자들이 수개월간의 노력에도 불구하고 실패했던 기존의 휴리스틱 탐색(시뮬레이티드 어닐링 및 AI가 구축한 로컬 서치 알고리즘 포함)을 뛰어넘는 성과를 냈다.
2. 지식의 역할: 저자들은 LLM의 성공이 기존의 수학적 지식을 활용하고 알려진 독립 집합을 "작은" 변화를 통해 수정하는 능력에서 비롯되었을 수 있다고 제안하며, 이는 명시적인 조합론적 구성을 찾는 데 있어 LLM의 잠재력을 강조한다.
3. 향endo 방향: 본 논문은 독립 집합을 찾는 과정에서 LLM이 전통적인 탐색 휴리스틱을 능가할 수 있게 하는 메커니즘을 연구하는 것이 가치 있는 향후 연구 방향이라고 상정한다.

저자들은 수치적 개선의 폭(예: $\Theta(C_{15})$의 증가량은 소수점 여섯째 자리 수준)에 대해서는 겸허한 태도를 유지하면서도, 발견 과정의 참신함을 강조한다. 모든 구성과 코드는 공개 저장소에 제공된다.