The unknotting number, hard unknot diagrams, and reinforcement learning

📄 arXiv: 2409.09032v2 📥 PDF

作者: Taylor Applebaum, Sam Blackwell, Alex Davies, Thomas Edlich, András Juhász, Marc Lackenby, Nenad Tomašev, Daniel Zheng

分类: math.GT, cs.AI, cs.LG

发布日期: 2024-09-13 (更新: 2025-07-19)

备注: 30 pages, 17 figures; to appear in Experimental Mathematics

💡 一句话要点

利用强化学习求解解纽数，发现难解纽结图并确定纽结不变量

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 强化学习 纽结理论 解纽数 纽结图 组合优化

📋 核心要点

  1. 传统纽结解纽数计算复杂，难以处理大规模纽结图，尤其是在寻找最小解纽序列时面临挑战。
  2. 利用强化学习，智能体通过学习策略，逐步优化解纽交叉变化序列，从而逼近最小解纽数。
  3. 实验结果表明，该方法能够有效确定大量纽结的解纽数，并发现难解纽结图，为纽结理论研究提供新工具。

📝 摘要（中文）

本文开发了一种强化学习智能体，能够为具有高达200个交叉的纽结图找到最小的解纽交叉变化序列，从而给出解纽数的上限。利用该智能体，确定了57k个纽结的解纽数。对于具有相反符号的纽结的连通和的纽结图，智能体发现了解纽交叉变化序列中的若干交叉变化会导致双曲纽结的例子。基于此，证明了在一些温和的假设下，对于纽结$K$和$K'$，存在它们的连通和的纽结图，以及$u(K) + u(K')$个解纽交叉，改变其中任何一个都会产生素纽结。作为副产品，获得了包含260万个不同的难解纽结图的数据集，其中大多数少于35个交叉。假设解纽数的可加性，确定了43个最多12个交叉的纽结的解纽数，而这些纽结的解纽数是未知的。

🔬 方法详解

问题定义：论文旨在解决纽结理论中解纽数的计算问题，特别是对于复杂纽结图，传统方法计算量大，难以找到最优解纽序列。现有方法在处理大规模纽结图时效率低下，且难以发现具有特殊性质的纽结图，例如改变解纽交叉后产生双曲纽结的图。

核心思路：论文的核心思路是利用强化学习，将寻找最优解纽序列问题转化为一个马尔可夫决策过程。智能体通过与纽结图环境交互，学习如何选择交叉变化，以最小化解纽所需的交叉变化次数。这种方法能够有效地探索解空间，并找到接近最优的解纽序列。

技术框架：整体框架包含以下几个主要模块：1) 纽结图环境：模拟纽结图的状态和交叉变化操作；2) 强化学习智能体：基于深度神经网络，学习策略函数，选择最优交叉变化；3) 奖励函数：根据解纽结果和交叉变化次数，给予智能体奖励或惩罚；4) 训练过程：通过大量迭代，优化智能体的策略函数。

关键创新：最重要的技术创新点在于将强化学习应用于纽结解纽问题，并设计了合适的奖励函数和网络结构，使得智能体能够有效地学习解纽策略。与传统方法相比，该方法能够处理更大规模的纽结图，并发现具有特殊性质的纽结图。

关键设计：奖励函数的设计至关重要，需要平衡解纽速度和交叉变化次数。网络结构通常采用卷积神经网络或循环神经网络，以提取纽结图的特征。参数设置包括学习率、折扣因子、探索率等，需要根据具体问题进行调整。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

该研究成功地利用强化学习确定了57k个纽结的解纽数，并发现了一个包含260万个难解纽结图的数据集。此外，该方法还确定了43个最多12个交叉的纽结的解纽数，而这些纽结的解纽数是之前未知的。实验结果表明，该方法能够有效地处理大规模纽结图，并发现具有特殊性质的纽结图。

🎯 应用场景

该研究成果可应用于纽结理论的多个领域，例如纽结分类、纽结不变量计算、以及新纽结的发现。此外，该方法还可以推广到其他组合优化问题，例如蛋白质折叠、电路设计等。未来，该研究有望促进纽结理论与其他领域的交叉融合，推动相关技术的发展。

📄 摘要（原文）

We have developed a reinforcement learning agent that often finds a minimal sequence of unknotting crossing changes for a knot diagram with up to 200 crossings, hence giving an upper bound on the unknotting number. We have used this to determine the unknotting number of 57k knots. We took diagrams of connected sums of such knots with oppositely signed signatures, where the summands were overlaid. The agent has found examples where several of the crossing changes in an unknotting collection of crossings result in hyperbolic knots. Based on this, we have shown that, given knots $K$ and $K'$ that satisfy some mild assumptions, there is a diagram of their connected sum and $u(K) + u(K')$ unknotting crossings such that changing any one of them results in a prime knot. As a by-product, we have obtained a dataset of 2.6 million distinct hard unknot diagrams; most of them under 35 crossings. Assuming the additivity of the unknotting number, we have determined the unknotting number of 43 at most 12-crossing knots for which the unknotting number is unknown.