🔢 mathematics

Lean-verified lower bounds for the Shannon capacity of odd cycles

This paper presents new, fully formalized in Lean, lower bounds for the Shannon capacities of several small odd cycles ( $C_7, C_{11}, C_{13}, C_{15}, C_{19}, C_{21}, C_{23}$ ) derived using an iterative procedure based on recent methods by Gao and Itty et al.

Original authors: Pjotr Buys, Sven Polak, Jeroen Zuiddam

Published 2026-08-03

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Pjotr Buys, Sven Polak, Jeroen Zuiddam

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message across a noisy, chaotic city. The city is full of distractions, and sometimes your signal gets mixed up with the wrong street names. In the world of information theory, this is a real problem: how do you send data perfectly without any errors? In the 1950s, a mathematician named Claude Shannon figured out that if you have a "noisy" channel, you can still send messages perfectly, but only if you are clever about how you group your letters together. He introduced a concept called "Shannon capacity," which is essentially a score telling you the maximum speed at which you can send perfect messages through a specific type of noisy network.

To visualize this, imagine a game played on a map of the city. The map is a graph, where the intersections are dots and the streets are lines. Some streets are "safe" to travel together, while others are dangerous and will cause a crash if you mix them up. The goal is to pick the largest possible group of intersections (an "independent set") that you can visit without ever taking a dangerous street between any two of them. The "Shannon capacity" asks a tricky question: if you play this game not just once, but by stacking multiple copies of the map on top of each other to create a giant, multi-dimensional city, how much bigger can your safe group get? For some shapes, we know the answer. For others, specifically the odd-shaped loops in the city (like a pentagon or a heptagon), the answer has been a mystery for decades. It's like knowing the speed limit on a straight road but having no idea how fast you can go on a winding, seven-cornered track.

This paper is about cracking that mystery for several of those tricky, seven-cornered (and larger) tracks. The authors, a team of mathematicians and computer scientists, have found new, slightly faster ways to send perfect messages through these specific loops. They didn't just guess; they used a clever, step-by-step recipe to build larger and larger groups of safe intersections. To make sure they didn't make a single mistake in their complex math, they had a super-strict digital referee named "Lean" check every single step of their work. The result? They have proven that for these specific odd loops, the maximum speed of perfect communication is higher than anyone had previously calculated.

The Game of Safe Intersections

Let's break down what the authors actually did. They were looking at graphs that look like simple rings with an odd number of dots: a ring of 7, a ring of 11, a ring of 13, and so on. For a long time, mathematicians knew the "speed limit" (the Shannon capacity) for a 5-dot ring. But for rings with 7 dots or more, the answer has been stuck in a fog. We knew it was at least a certain number, but we didn't know if it could be higher.

The authors used a method that feels like a magical recipe for growing your safe group. Imagine you have a small, safe club of friends (a set of dots) on a single map. The paper describes a "product theorem," which is like a machine that takes two of these maps and smashes them together to create a new, bigger map. If you have a safe club on the first map and a safe club on the second, you can combine them to make a safe club on the new, bigger map. Usually, the size of this new club is just the size of the first club times the size of the second. But the authors found a special "gadget" or trick. By using a specific pattern of connections (called a "valid tuple"), they could make the new club bigger than the simple multiplication would suggest.

Think of it like this: If you have a team of 2 people who can work together without fighting, and you combine two such teams, you might expect a team of 4. But with this special trick, the authors found a way to combine them and get a team of 5 people who all get along perfectly. By repeating this trick over and over, stacking the maps higher and higher, they could grow these safe teams into massive groups.

The New Records

The team applied this recipe to seven different odd rings: those with 7, 11, 13, 15, 19, 21, and 23 dots. For each one, they started with a known safe group and ran their "stacking" machine many times. The result was a new, higher lower bound for the Shannon capacity.

Here is what they found, with the numbers exactly as they calculated them:

For the 7-dot ring, they proved the capacity is at least 3.258805369885. This is a tiny bit higher than the previous best guess.
For the 11-dot ring, the new floor is 5.294502522149.
For the 13-dot ring, they pushed the limit to 6.302455083464.
For the 15-dot ring, the number is 7.301600534487.
For the 19-dot ring, they reached 9.357192705918.
For the 21-dot ring, the bound is 10.342455853338.
And for the 23-dot ring, they found a capacity of at least 11.328224257774.

These numbers might look like a string of random digits, but in the world of information theory, they represent a concrete improvement. They mean that for these specific networks, we now know for sure that we can send messages slightly faster than we thought possible before.

The Digital Referee

What makes this paper special isn't just the numbers, but how they got them. The math involved is incredibly complex, involving huge sets of data and thousands of steps. It's the kind of work where a human might easily miss a tiny error. To solve this, the authors wrote their entire proof in a computer language called Lean.

Think of Lean as a hyper-strict, digital referee that doesn't accept "I think this is right" or "it looks good to me." It demands absolute, logical proof for every single step. If the authors made a mistake in their logic, Lean would stop and say, "No, that doesn't follow." The fact that the paper is "Lean-verified" means that a computer has checked every single line of their reasoning and confirmed that their new bounds are mathematically solid. They didn't just simulate the results; they formally proved them.

The authors also mention that they used large language models (like advanced AI chatbots) to help them find the initial patterns and recipes for these safe groups. It's a bit like having a creative assistant who suggests a wild idea, and then the mathematicians use their rigorous tools to test if that idea actually holds water. In this case, the AI suggested a path, and the human-mathematician-AI team walked it all the way to a verified finish line.

Why It Matters

You might wonder, "So what? We just know the number is a little higher." The answer lies in the nature of the problem. For decades, the capacity of these odd rings has been an open question. We knew the answer was somewhere between a lower limit and an upper limit (the Lovász bound), but we couldn't pin it down. Every time we push the lower limit up, even by a tiny fraction, we narrow the gap. We are getting closer to the true answer.

This work shows that even for problems that have been stuck for a long time, there is still room for improvement if you have the right tools and the patience to check your work with the most rigorous standards possible. The authors haven't solved the entire mystery of the Shannon capacity for all odd rings, but they have cleared a few more foggy corners, proving that for rings of 7, 11, 13, 15, 19, 21, and 23, we can communicate a little faster than we previously believed.

Technical Summary: Lean-verified Lower Bounds for the Shannon Capacity of Odd Cycles

Problem Statement
The paper addresses the long-standing open problem of determining the Shannon capacity, $\Theta(G)$ , for odd cycles $C_n$ where $n \geq 7$ . The Shannon capacity is defined as $\Theta(G) := \sup_{d \geq 1} \alpha(G^{\boxtimes d})^{1/d}$ , where $\alpha$ denotes the independence number and $\boxtimes$ denotes the strong graph product. While Lovász determined $\Theta(C_5) = \sqrt{5}$ using the theta function $\vartheta(G)$ , the exact capacities for all odd cycles of length seven or greater remain unknown. The primary challenge lies in finding larger independent sets in higher strong powers of these cycles to improve the known lower bounds.

Methodology
The authors employ an iterative procedure based on a "gadget construction" and a "product lemma" recently proposed by Gao (2026), which itself builds upon methods by Itty, Rosin, Carstensen, and Reichman (2026). The core of the methodology involves:

Valid Tuples: For a graph $G$ , a valid tuple $\tau = (I, S, f_0, f_1, X)$ is defined, where $I$ is an independent set, $S \subseteq I$ , and $f_0, f_1$ are specific mappings satisfying strict neighborhood constraints. This tuple generates a "profile" $\Pi(\tau) = (|I|, |S|, |X|, |X \setminus (N_G[f_0(S)] \cup N_G[f_1(S)])|)$ .
Product Operation: A binary operation $\star$ is defined on profiles. Theorem 1 establishes that if $\tau$ and $\tau'$ are valid tuples for graphs $G$ and $H$ , there exists a valid tuple for the strong product $G \boxtimes H$ whose profile is the $\star$ -product of the individual profiles.
Iterative Construction: Starting from a computationally discovered valid tuple in a specific power of an odd cycle, the authors iteratively apply the $\star$ -product to generate profiles for higher powers. This process constructs independent sets in strong powers $C_n^{\boxtimes d}$ that are larger than those obtainable by simple Cartesian products of the base independent sets.
Formal Verification: A critical component of the methodology is the full formalization of these bounds in the Lean proof assistant. The base tuples (sets $I, S, X$ and maps $f_0, f_1$ ) are encoded as explicit literals, and their validity is mechanically verified within the Lean environment.

Key Contributions and Results
The paper presents new, improved lower bounds for the Shannon capacities of seven small odd cycles ( $C_7, C_{11}, C_{13}, C_{15}, C_{19}, C_{21}, C_{23}$ ). These bounds are derived by identifying specific base valid tuples and applying the iterative product procedure. The results are:

$\Theta(C_7)$ : Improved to $\geq 3.258805369885\dots$ (previously $3.2587891\dots$ by Gao 2026). The construction utilizes a base tuple in $C_7^{\boxtimes 5}$ iterated to power 200.
$\Theta(C_{11})$ : Improved to $\geq 5.294502522149\dots$ (previously $5.2897736\dots$ by Itty et al. 2026). The base tuple is in $C_{11}^{\boxtimes 3}$ , iterated to power 174.
$\Theta(C_{13})$ : Improved to $\geq 6.302455083464\dots$ (previously $6.3001091\dots$ by Itty et al. 2026). The base tuple is in $C_{13}^{\boxtimes 6}$ , iterated to power 432.
$\Theta(C_{15})$ : Improved to $\geq 7.301600534487\dots$ (previously $7.3013990\dots$ by Itty et al. 2026). The base tuple is in $C_{15}^{\boxtimes 4}$ , iterated to power 4096.
$\Theta(C_{19})$ : Improved to $\geq 9.357192705918\dots$ (previously $9.3571200\dots$ by Baumert et al. 1971). The base tuple is in $C_{19}^{\boxtimes 4}$ , iterated to power 16384.
$\Theta(C_{21})$ : Improved to $\geq 10.342455853338\dots$ (previously $10.3422729\dots$ by Baumert et al. 1971). The base tuple is in $C_{21}^{\boxtimes 4}$ , iterated to power 4096.
$\Theta(C_{23})$ : Improved to $\geq 11.328224257774\dots$ (previously $11.3278379\dots$ by Baumert et al. 1971). The base tuple is in $C_{23}^{\boxtimes 4}$ , iterated to power 2048.

The improvements, while numerically small (ranging from $10^{-5}$ to $10^{-3}$ ), represent the current state-of-the-art for these specific cycles.

Significance and Claims
The paper claims significance primarily through the rigorous verification of these results. By formalizing the entire construction and the resulting bounds in Lean, the authors ensure that the complex combinatorial arguments and the specific set constructions are free from human error. The work follows the trajectory of recent research utilizing large language models (LLMs) to discover initial constructions (as seen in [IRCR26] and [Gao26]), but distinguishes itself by providing a fully formalized, machine-checked proof of the validity of the base tuples and the correctness of the iterative product theorem application. The authors do not claim to have solved the general problem of Shannon capacity for odd cycles, nor do they propose new theoretical frameworks beyond the application of Gao's existing product lemma; rather, they provide the best currently known numerical lower bounds for these specific instances, verified with mathematical certainty.

The Game of Safe Intersections

The New Records

The Digital Referee

Why It Matters

Technical Summary: Lean-verified Lower Bounds for the Shannon Capacity of Odd Cycles

More like this