RL unknotter, hard unknots and unknotting number

This paper introduces a reinforcement learning pipeline that successfully simplifies complex knot diagrams and determines the unknotting number of the composite knot $4_1\#9_{10}$ as three, confirming a recently established upper bound.

The Gist

Imagine you have a tangled piece of string (a knot) lying on a table. Your goal is to untangle it until it becomes a perfect, simple circle (the "unknot").

In the world of mathematics, this isn't just a puzzle; it's a massive search problem. The paper you provided describes a new way to solve this using Artificial Intelligence (AI), specifically a type called Reinforcement Learning.

Here is the story of how they taught a computer to be a master untangler, explained without the heavy math jargon.

1. The Problem: The "Tangled Deck of Cards"

Think of a knot diagram not as a string, but as a deck of cards.

• The Cards: Each crossing in the knot is a card.
• The Moves: To untangle the knot, you can perform three types of moves (called Reidemeister moves):
  1. Add/Remove Cards: You can temporarily add extra crossings (like adding cards to the deck) or remove them.
  2. Shuffle: You can slide parts of the string over each other without changing the number of crossings.

The Trap:
If you try to untangle a knot by only removing cards (greedy strategy), you often get stuck. Sometimes, to untie a knot, you must first make it messier by adding more crossings, shuffling them around, and then removing them.

• Analogy: Imagine trying to untie a knot in a shoelace. If you just pull on the ends, it tightens. You have to loosen it first (make it look worse) to get it out.
• The Computer's Struggle: Traditional computer programs get stuck in "local minima." They see a move that makes the knot look slightly more complex and refuse to do it, even though that move is necessary to solve the puzzle later. They get stuck in a deep hole.

2. The Solution: The "AI Untangler" (The Agent)

The authors built a robot brain (a neural network) they call the "Unknotter." They didn't program it with rules like "always pull this loop." Instead, they used Reinforcement Learning.

• The Game: The AI plays a game where the "state" is the current knot diagram.
• The Goal: Reach a state with zero crossings (a perfect circle).
• The Reward: Every time the AI makes the knot simpler (fewer crossings), it gets a point. If it gets stuck or makes the knot messier, it gets a small penalty.
• The Learning: The AI tries millions of moves. When it accidentally finds a path that works (even if it had to make the knot messy first), it remembers that path. Over time, it learns a "gut feeling" (a heuristic) for which moves are promising, even if they don't look like immediate progress.

The Result: The AI learned to be brave. It learned that sometimes you have to "add cards to the deck" and "shuffle" to find the exit.

3. The Stress Test: "Very Hard" Knots

The researchers tested their AI on a set of knots known as "Very Hard Unknots."

• These are knots that look incredibly complicated but are actually just simple circles in disguise.
• They are designed to trick human experts and standard computer algorithms.
• The Score: The AI succeeded in untangling 94.5% of these "very hard" knots. Even more impressively, it solved every single one of them if you gave it enough tries. It proved that the AI could navigate the "messy" parts of the puzzle that other methods missed.

4. The Big Discovery: The "Magic Trick" with Two Knots

The most exciting part of the paper involves a specific knot made by tying two smaller knots together (a "connected sum"). Let's call it Knot A + Knot B.

The Old Belief:
Mathematicians used to think that if Knot A is hard to untie (needs 2 moves) and Knot B is hard to untie (needs 2 moves), then tying them together would need 4 moves to untie. (2 + 2 = 4).

The Surprise:
Recent research showed this isn't always true. For a specific knot called 4₁ # 9₁₀, the math says it might only need 3 moves to untie, not 4. But nobody could show the proof because the standard diagrams of this knot were too confusing to find the solution.

How the AI Helped:
The researchers used a clever trick called "Diagram Inflation."

1. Inflate: They took the standard diagram of the knot and artificially made it much more complex (adding hundreds of unnecessary crossings) while keeping it the same knot.
2. Search: They asked the AI to try changing just a few crossings (flipping them) and then untangling the rest.
3. The Win: By looking at this "inflated," messy version, the AI found a path. It showed that by flipping just 3 specific crossings, the knot could be untangled.

This provided a concrete, visual proof that the "magic trick" works: you can untie this complex knot with fewer moves than you'd expect, but you have to look at it from a very strange, complex angle to see it.

Summary

• The Problem: Untangling knots is hard because the solution often requires making the knot look worse before it gets better.
• The Tool: An AI trained to learn this "make it worse to make it better" strategy.
• The Achievement: The AI can untangle knots that stump other computers.
• The Impact: It helped verify a surprising mathematical fact: that two difficult knots tied together can sometimes be untied with fewer moves than the sum of their parts, but only if you know how to look at the "messy" version of the knot.

In short, the authors taught a computer to stop being a perfectionist and start being a strategic explorer, allowing it to solve some of the most stubborn tangles in mathematics.

Technical Summary

Here is a detailed technical summary of the paper "RL UNKNOTTER, HARD UNKNOTS AND UNKNOTTING NUMBER" by Dranowski, Kabkov, and Tubbenhauer.

1. Problem Statement

The paper addresses the computational challenge of knot simplification and unknotting number determination.

• The Core Difficulty: Determining if a knot diagram is the unknot (trivial knot) or simplifying a complex diagram is computationally hard. The search space of Reidemeister moves (R1, R2, R3) is vast and highly branching.
• Local Minima: Standard greedy heuristics often fail because simplifying a knot sometimes requires increasing the crossing number temporarily (via R1/R2) and shuffling the diagram (via R3) before a reduction becomes possible. These "hard" and "very hard" unknots trap deterministic algorithms.
• Unknotting Number ($u(K)$): Finding the minimum number of crossing changes required to turn a knot into the unknot is difficult because the optimal sequence of changes is often hidden in non-minimal, "inflated" diagrams rather than standard low-crossing representations.
• Additivity Conjecture: A long-standing open problem was whether the unknotting number is additive under connected sum ($u(K \# J) = u(K) + u(J)$). Recent work showed this is false for specific cases (e.g., $4_1 # 9_{10}$), but verifying this requires finding specific, non-obvious diagrammatic witnesses.

2. Methodology

The authors develop a Reinforcement Learning (RL) pipeline to navigate the diagrammatic move graph.

A. The RL Environment (The "Unknotter")

• State Representation: Knot diagrams are encoded as Planar Diagram (PD) codes (lists of quadruples representing crossing connectivity). The agent observes a compact feature vector including:
  • Current crossing number $c(D)$.
  • Number of link components.
  • Step counter.
  • Binary flags indicating if a basic simplification would reduce crossings or if the previous step did.
• Action Space (Macro-actions): The agent chooses from four macro-actions, parameterized by a count $\kappa$:
  1. Basic Simplify (m=0): Applies all possible R1 and R2 moves to reduce crossings.
  2. Level Shuffle (m=1): Applies R3 moves (shuffling) to rearrange the diagram.
  3. Pickup Shuffle (m=2): A variant of R3 shuffling.
  4. Backtrack (m=3): A stochastic "escape" move that increases the crossing number (adding random R1/R2 moves) followed by a shuffle. This allows the agent to leave local minima.
• Reward Shaping: The reward function encourages crossing reduction ($\Delta > 0$) and penalizes increases ($\Delta < 0$) and step costs. Crucially, a blocking heuristic is implemented: if a non-backtrack mode increases crossings, it is temporarily blocked to prevent the agent from wasting steps on unproductive paths.
• Training: The agent is trained using Proximal Policy Optimization (PPO) on a mixture of "hard" unknots (from [ABD+25]) and random diagrams.

B. The Crossing-Change Search Pipeline

To determine unknotting numbers for composite knots, the authors propose a two-stage workflow:

1. Inflation: Starting from a base diagram, the system generates a pool of "inflated" diagrams (higher crossing numbers) via random walks of Reidemeister moves. This expands the search space to find hidden simplification paths.
2. Crossing-Change Sweep:
   • For a target number of flips $m$, the system enumerates combinations of crossings to flip.
   • The trained Unknotter acts as an oracle/verifier: it attempts to simplify the resulting diagram to the unknot within a step budget.
   • Success: If the Unknotter reaches a crossing-free diagram, an explicit diagrammatic witness is produced.
3. One-Flip Identification (Optional): For $m=1$, the system simplifies the result and matches the Jones polynomial against a database (e.g., KnotInfo) to identify the resulting knot type and its known unknotting number.

3. Key Contributions

1. RL for Knot Theory: Formalizes knot simplification as a Markov Decision Process (MDP) where the agent learns a policy to navigate the move graph, effectively learning a heuristic for "distance-to-simplification."
2. The Unknotter Agent: A trained neural network capable of solving "very hard" unknots that defeat standard tools like SnapPy. It successfully handles the necessity of temporary crossing increases.
3. Automated Unknotting Number Verification: A pipeline that recovers upper bounds for unknotting numbers by combining diagram inflation, crossing-change enumeration, and RL-based simplification.
4. **Verification of $4_1 # 9_{10}$:** Provides a new, algorithmic verification that the unknotting number of the composite knot$4_1 # 9_{10}$ is at most 3, recovering the surprising result from recent literature [BH25, BH26].

4. Results

• Hard Unknots: Tested on 385 "very hard" unknot diagrams from [ABD+25].
  • Success Rate: The agent achieved a mean per-run unknotting rate of 94.57% (with $T=500$ steps and 10 runs per instance).
  • Robustness: Every single instance was successfully unknotted in at least one of the 10 runs. 266 instances were solved in all 10 runs.
• Composite Knot $4_1 # 9_{10}$:
  • The pipeline generated inflated diagrams and tested crossing changes.
  • While a direct 3-flip witness was not found in the specific sweep of 53,950 diagrams (finding only 4-flip witnesses), the One-Flip Identification pipeline successfully identified a specific 1-flip result.
  • Flipping a specific crossing in an inflated diagram yielded a knot identified as $15n4866$ (via Jones polynomial matching).
  • Since $u(15n4866) = 2$, this proves $u(4_1 \# 9_{10}) \le 1 + 2 = 3$. This confirms the non-additivity of the unknotting number for this specific case.

5. Significance

• Overcoming Greedy Limitations: The work demonstrates that RL is superior to deterministic greedy heuristics for topological problems where the optimal path requires non-monotonic exploration (temporarily making the problem "worse" to solve it).
• Algorithmic Topology: It provides a practical, automated workflow for generating diagrammatic evidence for knot invariants, moving beyond theoretical proofs to computational verification.
• Scalability: The method applies to arbitrary knots and links, not just specific families, offering a general tool for simplifying complex diagrams.
• Reproducibility: The authors provide full code, trained models, and datasets, enabling the community to reproduce the "very hard" unknotting results and the $4_1 # 9_{10}$ verification.

In summary, this paper bridges Reinforcement Learning and Knot Theory, creating a powerful tool that can navigate the complex, non-convex search space of knot diagrams to solve problems that are intractable for traditional algorithmic approaches.