그래프의 샤논 용량은 잡음이 있는 채널에서 오류 없이 보낼 수 있는 정보의 최대 속도를 나타내는 값으로 정의된다. 이번 arXiv 프리프린트는 홀수 사이클의 강한 거듭제곱에서 독립집합을 직접 구성해 그 하한을 끌어올리는 데 초점을 맞춘다. 핵심은 이론적 상계가 아니라, 실제로 셀 수 있는 독립집합을 얼마나 크게 만들 수 있는가에 있다.
연구진이 제시한 새 구성은 세 그래프에서 확인된다. $C_7^{10}$에서는 크기 134753, $C_{11}^{6}$에서는 21909, $C_{13}^{6}$에서는 62530의 독립집합을 만들었다. 이를 통해 샤논 용량 하한은 각각 $Θ(C_7) ≥ 134753^{1/10} > 3.258020$, $Θ(C_{11}) ≥ 21909^{1/6} > 5.289773$, $Θ(C_{13}) ≥ 62530^{1/6} > 6.300109$로 갱신된다. 표 1에는 이전 최선 하한과 새 하한이 함께 정리돼 있다.
변화는 샤논 용량만이 아니다. 일부 홀수 사이클의 개별 강한 거듭제곱에 대해서도 독립수 하한이 개선됐지만, 그런 경우는 샤논 용량의 하한을 더 높이진 않는다. 즉 이번 결과는 “최종 용량 값”을 푸는 것이 아니라, 특정 거듭제곱 위의 명시적 조합 구성을 더 크게 만드는 쪽에 가깝다.
구성의 발견 과정도 특이하다. 초록은 이 독립집합들이 대규모 언어모델과의 반복적 상호작용을 통해 찾아졌다고 밝힌다. 이 표현은 LLM이 곧바로 정리를 증명했다는 뜻이 아니라, 명시적 조합 구성을 찾는 탐색 과정에서 보조적 역할을 했다는 의미로 읽힌다. 본문 4쪽의 정의에 따르면 두 정점은 각 좌표에서 순환거리 1 이하일 때 간선으로 연결되며, 뒤쪽 부록에는 실제 좌표 목록이 길게 제시된다.
| 대상 그래프 | 새 독립집합 크기 | 새 샤논 용량 하한 | 이전 최선 하한 |
|---|---|---|---|
| C_7^{10} | 134753 | Θ(C_7) ≥ 134753^{1/10} > 3.258020 | 3671^{1/5} > 3.257865 |
| C_{11}^{6} | 21909 | Θ(C_{11}) ≥ 21909^{1/6} > 5.289773 | 1481^{1/3} > 5.289572 |
| C_{13}^{6} | 62530 | Θ(C_{13}) ≥ 62530^{1/6} > 6.300109 | 2471^{1/3} > 6.274305 |
자료: STORIUM 정리
문헌상 홀수 사이클의 샤논 용량은 여전히 정확한 값이 알려지지 않았다. 본문 2쪽은 짝수 사이클의 경우 $Θ(C_p)=p/2$가 쉽다고 설명하지만, $C_{2r+1}$에서 $r>2$인 경우는 미해결이라고 적는다. 그런 상황에서 이번 결과는 계산 가능하고 검증 가능한 독립집합을 통해 하한을 한 단계씩 밀어 올린 사례로 볼 수 있다.
저작권자 © STORIUM 무단전재 및 재배포 금지
