知识卡片：奇环香农容量的下界改进与LLM辅助组合构造

一句话结论

本文通过构造更大的独立集，将奇环 (C_7)、(C_{11})、(C_{13}) 的香农容量下界分别提升至约 3.258020、5.289773、6.300109，并展示了大型语言模型（LLM）在发现显式组合构造中的潜在作用。

事件概述与研究问题

香农容量 (\Theta(G)) 是图 (G) 在无噪声信道中零误差传输信息的最大速率。它的下界由任意 (d) 下 (α(G^d)^{1/d}) 给出，其中 (α(G^d)) 是图的第 (d) 次强幂的独立数。奇环（odd cycles）的香农容量精确值长期未知，此前已有大量关于 (C_5, C_7, C_{11}, C_{13}) 等奇环的下界改进工作。本研究聚焦 (C_7)、(C_{11})、(C_{13}) 这三个奇环，旨在进一步收紧它们的香农容量下界。

方法/产品要点

• 构造方法：为 (C_7^{10})、(C_{11}^{6})、(C_{13}^{6}) 分别构造了大小为 134753、21909、62530 的独立集，从而得到改进的下界。
• LLM辅助发现：这些构造是通过与大型语言模型（LLM）迭代交互发现的，展示了LLM在显式组合构造问题中的潜力。
• 附加改进：还改进了多个单个奇环强幂的独立数下界，这些改进不直接提升香农容量下界，但可能对相关组合问题有意义。

主要结果与产业意义

• 奇环香农容量下界更新：
  • (\Theta(C_7) \geq 134753^{1/10} > 3.258020)
  • (\Theta(C_{11}) \geq 21909^{1/6} > 5.289773)
  • (\Theta(C_{13}) \geq 62530^{1/6} > 6.300109)
• 产业意义：香农容量影响通信编码理论，更紧的下界有助于设计更好的纠错码；LLM辅助构造范例可推广至其他组合优化问题。

为什么重要

• 香农容量是信息论与图论交叉的经典难题，奇环的精确容量自1950年代提出以来未被完全解决。本文对三个奇环的下界推进具有理论意义。
• 首次在高质量组合构造论文中系统使用LLM作为发现工具，可能开启“人机协作”数学发现的新范式。

局限与不确定性

• 文中未给出新下界是否最优；香农容量精确值仍未知。
• LLM发现的具体交互过程未详述，构造的可复现性和LLM贡献的可分离性有待进一步评估。
• 改进的独立集尺寸可能不是最优的，存在进一步改进空间。

可用于图书/PPT/简报的角度

• 香农容量入门：用奇环例子直观说明零误差信道容量的定义。
• LLM在数学研究中的应用：作为组合构造生成的“搭档”，结合人类评估。
• 组合数学与信息论的交叉：独立数、强幂与编码理论的关系。

原始材料

• 英文标题：Improved lower bounds for the Shannon capacity of odd cycles
• 英文关键词：Shannon capacity; odd cycles; independence number; strong power; LLM-assisted construction
• 来源：arXiv:2607.21517v1 (cs.IT, cs.AI, cs.DM, math.CO)
• URL：https://arxiv.org/abs/2607.21517v1