← 返回 PaperDaily 大模型与智能体

WPI携手ChatGPT-5.6：奇环香农容量下界刷新，C7超3.258

一篇让数学界看到AI潜力的工作：用ChatGPT-5.6找到了比传统启发式更大的独立集，把C7香农容量下界又推高了那么一丢丢。数字虽小，意义不小——LLM正在学会做真正的数学发现。尽管本地搜索算法和模拟退火苦战三月未果，LLM仅靠对话就突破了关键壁垒。这种"聊天式科研"的范式，会不会成为未来的新常态？

龙哥读论文发布于 2026-08-14 09:11:25 阅读 3 查看原文

#大语言模型 #AI科研 #人工智能

原论文信息如下：

论文标题:
Improved lower bounds for the Shannon capacity of odd cycles

发表日期:
2026年7月发表单位:
Worcester Polytechnic Institute, Constructive Codes 原文链接:
https://arxiv.org/pdf/2607.21517v1.pdf 开源代码链接:
https://github.com/nathanielitty/lower-bounds-for-shannon-capacity

当大语言模型化身数学研究员：改进奇环Shannon容量下界的AI辅助构造

有些论文看起来像在和数学界“抠单位数”，但背后其实是在改写一个很老的问题：大语言模型能不能真的帮人做数学发现。这篇工作就是个很典型的例子——不是让模型背公式，而是让它自己生成搜索程序，再去撞出更大的独立集。结果还真撞出来了，而且还不是一次，是连续撞出了几组更好的构造。

如果把这事放进现实场景里理解，就像让一个“只会聊天”的助手，去帮忙在一堆看似没头绪的组合里找一条最优路径。人类原本以为这类活儿只能靠长期手工试错，结果模型偏偏给出了传统启发式都没找到的答案。

问题背景：Shannon容量与奇环独立集难题

这篇论文的核心对象是图论里的Shannon容量。它最早来自 Claude Shannon 在 1956 年关于零错误通信的研究，意思是：一个噪声信道里，信息最高能以多快的速度被无错传输。对于图来说，Shannon容量记作 Θ(G)，衡量的是图的幂次结构里能找到多大的独立集增长率。

图1：Shannon容量的定义。这里的 α(Gd) 表示图 G 的 d 次强积 里的最大独立集大小，外面的 1/d 次方 则是在看“平均到每一维”的增长率。

对于偶环，Shannon容量早就算明白了；但对奇环，尤其是 C7、C11、C13 这些最经典的例子，精确值至今都还没定。原因也很朴素：只要把图做强积，顶点数就爆炸式增长，找独立集这件事很快就变成组合搜索里的硬骨头，甚至在一般情形下近似也很难。

奇环问题难在哪？因为它不是单纯找“离得远”的点，而是要在高维笛卡尔积里找一组两两不相邻的向量。维度一高，搜索空间就像突然从小区车库变成宇宙级迷宫，靠肉眼和穷举都不现实。

核心突破：LLM迭代交互挖掘出更大独立集

这篇论文最有意思的地方，不是“找到了更大独立集”这么简单，而是用 ChatGPT-5.6 Sol Pro 通过多轮提示，自己生成搜索程序、自己跑程序、再继续改提示。也就是说，模型不是被动回答，而是直接参与了构造搜索策略的形成。

这就有点像让模型当“数学研究员”而不是“算题机器”：先给它一个目标，比如把某个已有构造再往前推一点点，再让它返回程序与候选集合。作者再验证可行性，确认独立性成立后继续迭代。论文里明确提到，手工实现的搜索启发式、模拟退火，甚至一些由生成式 AI 设计出的本地搜索，长时间都没越过这道坎。

这背后说明一个挺反常识的结论：在某些组合数学问题上，LLM 的价值不是“懂不懂定义”，而是能不能借助语言、规则和程序生成，帮人探索人脑没覆盖到的搜索路径。它不是替代证明，而是在“找构造”这一步给了额外火力。

论文主体思路

*表格超出部分左右可以滑动

项目	内容
应用场景	利用程序搜索与大语言模型交互，寻找奇环强积中的更大独立集，从而改进 Shannon 容量下界。
问题建模	把 Ckd 中独立集搜索转化为组合构造问题：任意两点必须在至少一个坐标上相隔超过 1（按环距离）。
模型 Backbone 及选择原因	使用 ChatGPT-5.6 Sol Pro，通过自然语言提示生成搜索程序、调整构造并继续迭代；适合在未知搜索空间里做启发式探索。
损失函数	无标准训练损失；目标是最大化独立集大小，并在每轮迭代后验证是否保持独立性。
训练数据集	无监督数据集；主要依赖已有最优构造、搜索约束与提示词描述。
测试数据集	C710、C116、C136 以及若干奇环低阶强积的辅助测试。
训练方法	多轮对话式搜索：给定目标规模、当前最佳构造和格式约束，模型生成候选构造，作者验证后继续追问更优方案。
实验效果	对 C7、C11、C13 的 Shannon 容量下界均有小幅但明确的提升；部分独立集下界也同步刷新。
方法优势	能在人工启发式之外探索新的构造路径，特别适合“有规则、难穷举、可验证”的组合数学问题。
方法缺点	依赖外部验证，搜索过程不可解释性较强，对提示设计和任务表述非常敏感，泛化到其他问题未必稳定。

从结构上看，这篇论文其实做了两件事。第一件是构造更大的独立集，把它们塞进对应强积里；第二件是证明这种构造不是“运气好瞎蒙”，而是可以通过一套稳定的对话式搜索流程不断产出。论文还把搜索提示、程序和结果都开源了，这一点对可复现性非常关键。

构造细节：从C7到C13的独立集设计

论文的构造策略并不神秘，甚至可以概括成一句朴素的话：在已有最优构造附近继续“精修边角料”，把少量向量删掉、重排、补回，最后让总数变大。真正难的是，这种“修边角料”不是人工瞎调，而是在高维约束下保持独立性。

先看 C7。作者以已有的 5 维独立集为基础，通过删去一部分向量得到子集 B，再在此基础上用精心设计的补充项扩展到 10 维。这里出现的 PH、PV，本质上是两组“水平/垂直”参考点，用来筛出哪些 x 需要接某些特定向量，哪些地方该补 q，哪些地方该保留 r。

图2：PH 和 PV 的定义。它们分别表示从两类基准向量中挑出的集合，后面会用来判断某个候选向量是否与这些参考点相邻。

图3：集合 A 和 D 的定义。简单说，就是先找出那些会“碰到”参考点的 x，再根据它们来自哪个方向决定后续怎么补构造。

最后把这些部件拼成一个 10 维独立集 I。这个构造最妙的地方在于，它不是简单复制旧集合，而是把旧集合 B 与新补项交错叠加，等于是把“旧骨架”保留住，再在缝隙里塞进额外向量，最终多出来的不是几个零头，而是一个可验证的提升。

图4：C7 里最终使用的独立集定义。这里的关键是把 B×B 和两类补充项合起来，保证总规模超过原来的简单笛卡尔积。

到 C11 时，思路类似，但构造更复杂：从已有的 3 维独立集出发，论文把它拆分成多个子块，再定义 H(x) 和 V(y) 这样的集合值函数。直白点说，就是某个 x 来了以后，不是给它一个固定补位，而是给它一篮子可选补位；y 也一样。这种设计更像“按位置发配件”，而不是“一刀切拷贝模板”。

图5：C11 构造的最终拼接式定义。这个式子看着长，但本质还是“基底 + 条件补丁”的组合，只是补丁分支更多了。

而 C13 的做法又换了一种味道。这里先构造一个 13×4 的矩阵 A，再在一个变换后的图 GA 上做随机局部搜索，先找出 370 个 4 维向量组成的集合 S，然后把所有满足 A x ∈ S 的 6 维向量收进最终独立集。这个思路明显更“代数化”，像是先把问题压缩，再从压缩空间里反推出更大的构造。

图6：C13 的最终定义。先在辅助空间里找集合 S，再用线性映射 A 把它“拉回”到 6 维空间，得到更大的独立集。

结果对比：微小的数值改进背后的理论意义

这类论文最容易被路人忽略，因为数字提升看上去都不大：有时只是在原有下界上多抬了一点点。但数学里很多问题就是这样，尤其是 Shannon 容量这种老问题，一个小数点后几位的变化，背后往往意味着搜索方法、构造思路、甚至问题理解都往前挪了一步。

比如 C7 从 367 个点的 5 维构造推进到 10 维 134753 个点，本质上是把长期以来“简单复用已有结构”的边界往外推了一点；C11 和 C13 也分别刷新了下界。更值得注意的是，论文不仅改进了 Shannon 容量下界，还顺手改进了一批强积独立数 的已知下界，这些结果虽然不直接改变最终容量值，但可能是后续继续往上拱的“垫脚石”。

表1：本文对 C7、C11 和 C13 的 Shannon 容量下界改进。可以看到，提升幅度不算夸张，但每一项都是真实有效的增量，不是“纸面上好看”的凑数。

表2：若干奇环强积独立数下界的改进。虽然这些结果没有直接推动 Shannon 容量再上一个台阶，但对未来搜索更强构造很有用，属于典型的“主战场外，先把地形摸清”。

表3：C13 构造中使用的 370 个辅助向量。这个表格就是典型的“看起来像数据清单，实际是构造的骨架”。

更关键的是方法论意义。过去这类结果常常依赖专家经验、局部搜索和人工巧思的组合；这篇论文则把 LLM 加进来之后，出现了一个新的合作模式：人负责定义问题边界，模型负责扩展搜索空间，验证程序负责兜底。这种协作很像“人类给地图，模型去踩点”，踩出路了再回过头来总结规律。

实验验证与可复现性：代码已开源

这篇论文在“实验”层面没有深度学习里那种大规模训练集、验证集、测试集的套路，但它做了组合数学里最关键的一步：给出可验证构造。每个独立集都经过作者检查，确认任意两点都不相邻，才会作为最终结果写入论文。

这点很重要，因为组合构造论文最怕两件事：一是“看起来像真，实际没验过”；二是“能验，但别人复现不了”。这里作者把独立集构造、生成程序、提示词和辅助文档都放到了 GitHub，至少让同行能顺着路径复查，而不是只看一个漂亮的数字结论。

图7：项目开源页面与构造说明。对这类工作来说，能否复现比“讲得多玄乎”更重要，毕竟独立集这种东西不能靠嘴硬，得靠程序和验证。

从工程视角看，这篇工作的现实价值并不在“马上能做产品”，而在于它展示了一条很有潜力的路线：把 LLM 变成搜索策略生成器。凡是那种规则明确、结果可校验、但搜索空间巨大的人类难题，都可能从这种方式里受益。只是要注意，能在奇环上奏效，不代表别的问题也能照搬；数学问题之间的结构差异，往往比表面相似大得多。

龙迷三问

下面是龙哥对于大家可能的一些问题的解答：

这篇论文到底解决了什么问题？它不是去证明 Shannon 容量的精确值，而是给 C7、C11、C13 找到更大的独立集，从而把已知下界往上推了一点。对于这类长期未解问题，哪怕只提升一点，也可能意味着新的构造路线被打开了。

文中的“强积”“独立集”是什么意思？强积可以理解为把同一个图在多个坐标上拼起来，顶点变成向量；独立集则是一组彼此没有边相连的顶点。对奇环来说，就是要找一串向量，让任意两条都至少在一个坐标上“离得足够远”。

这类 LLM 辅助数学搜索靠谱吗？靠谱，但前提很苛刻：问题必须能形式化、候选结果必须能验证，而且还得有人把搜索目标说得非常清楚。它更像一个强力的“构造建议器”，不是自动定理证明器；离开人工判断，效果会立刻打折。

如果还有哪些想继续追问的，欢迎在评论区留言或者讨论~

龙哥点评

论文创新性分数：★★★★☆

把 LLM 放进组合构造搜索里不是第一次见，但这篇的亮点在于它不是停留在“生成几个候选”，而是形成了可持续迭代的发现流程，并且真的在老问题上抠出了新下界。

实验合理度：★★★★☆

结果验证路径比较清晰，构造都经过独立性检查，且开源了生成程序和提示词。遗憾是搜索过程本身仍带有较强的黑箱色彩，严格可控性不如纯解析推导。

学术研究价值：★★★★★

对 Shannon 容量这种经典难题来说，任何稳定的构造推进都很有价值。更重要的是，它给“LLM + 数学发现”提供了一个相当具体的范式，不是泛泛而谈。

稳定性：★★★☆☆

从论文描述看，方法对提示设计、任务表述和人工验证依赖都很强，不算即插即用。换个问题、换个约束，未必还能保持同样效果。

适应性以及泛化能力：★★★☆☆

适用于“可编码、可验证、搜索空间巨大”的组合问题，但不是所有数学问题都能套。它的泛化更多体现在方法框架，而不是一次迁移就能稳定涨点。

硬件需求及成本：★★★★☆

相比训练大模型，这里主要成本在调用模型与反复验证构造，算力压力不算离谱。真正耗时的是搜索迭代和人工审查，不是显卡烧得厉害。

复现难度：★★★★☆

代码和构造已开源，复现入口比较友好；但要真正复现“找出更优构造”的过程，仍然依赖较多搜索尝试，不是下载代码一跑就自动出新结果。

产品化成熟度：★★☆☆☆

离产品化还很远，原因很简单：这不是一个能直接落地到业务里的功能，而是一个面向数学发现的研究工具。更现实的价值，是作为研究辅助系统继续演化。

可能的问题：结果漂亮，但依赖多轮提示和人工验证，黑箱程度仍高；对其他问题未必同样有效，更多像“高水平定制搜索”，还没到通用数学引擎的阶段。

主要参考文献

Claude Shannon. The zero error capacity of a noisy channel. IRE Transactions on Information Theory, 1956.

László Lovász. On the Shannon capacity of a graph. IEEE Transactions on Information theory, 1979.

Sven C. Polak and Alexander Schrijver. New lower bound on the Shannon capacity of C7 from circular graphs. Information Processing Letters, 2019.

Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, and Daniel Reichman. Improved lower bounds for the Shannon capacity of odd cycles. arXiv:2607.21517v1, 2026.

项目代码：https://github.com/nathanielitty/lower-bounds-for-shannon-capacity

*本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～想了解更多原文细节的小伙伴，可以点击"阅读原文"，查看更多原论文细节哦！

香农容量下界又涨了一丁点，但背后是AI做数学的星星之火！想亲眼见证LLM如何破解组合难题？
欢迎加入龙哥读论文粉丝群，扫描下方二维码或者添加龙哥助手微信号加群：kangjinlonghelper。一定要备注：研究方向+地点+学校/公司+昵称（如图像处理+上海+清华+龙哥），根据格式备注，可更快被通过且邀请进群。

『龙哥读论文』微信群目前包含：图像处理、大模型及智能体、自动驾驶及机器人、AI医疗及AI金融5个群
wechat_helper