The Shannon capacity of the 7-cycle

How many messages per symbol can be sent with zero error over a channel whose seven symbols are each confusable with their two neighbours on a cycle? This is the Shannon capacity of the 7-cycle, known only to lie between 3.25883 and 3.3177; lower bounds are explicit codes that can be checked by computer.

Problem

For a graph $G$, let $G^{\boxtimes n}$ be its $n$-th strong power: the vertices are words $x = (x_1, \dots, x_n)$ over $V(G)$, and two distinct words are adjacent when, in every coordinate, their letters are equal or adjacent in $G$. Let $\alpha$ denote the independence number. The Shannon capacity of $G$ is

$$\Theta(G) = \sup_{n \ge 1} \alpha\!\left(G^{\boxtimes n}\right)^{1/n}.$$

Let $C_7$ be the cycle on 7 vertices. Determine $\Theta(C_7)$, or narrow the known range $3.25883262 \le \Theta(C_7) \le 3.3177$.

Background

Shannon introduced this quantity in 1956 as the zero-error capacity of a noisy channel: if $G$ records which symbols can be confused, an independent set in $G^{\boxtimes n}$ is a code of length $n$ in which no two codewords can be mistaken for each other. Lovász (1979) invented his theta function to prove $\Theta(C_5) = \sqrt{5}$, and showed $\Theta(C_7) \le \vartheta(C_7) = 7\cos(\pi/7)/(1+\cos(\pi/7)) \approx 3.3177$. For no odd cycle longer than $C_5$ is the capacity known, which makes $C_7$ the smallest open case.

What is known

• Upper bounds: $7/2$ (Shannon, 1956) and $\vartheta(C_7) \approx 3.3177$ (Lovász, 1979). The source records no improvement since then.
• Lower bounds (each from a large independent set in a strong power): $343^{1/5} \approx 3.2141$ (Baumert et al., 1971); $108^{1/4} \approx 3.2237$ (Vesel and Žerovnik, 2002); $350^{1/5} \approx 3.2271$ (Mathew and Östergård, 2017); $367^{1/5} \approx 3.2578$ (Polak and Schrijver, 2019).
• 2026 records (preprints, not yet refereed): $134753^{1/10} \approx 3.258020$ (Itty, Rosin, Carstensen and Reichman, found with help from a language model); $3.258789\ldots$ from a recursive product construction in the 200th power, with a program that checks its finite steps (Gao); $3.258805\ldots$, fully formalized in Lean (Buys, Polak and Zuiddam); and the current record $3.25883262\ldots$ from a heterogeneous recursion in the 500th power (Tandon), not yet formalized.

What would count as progress

• An independent set in some $C_7^{\boxtimes n}$ with size above $3.25883262^n$. For explicit sets, checking that no two words are confusable is a pairwise test that runs in minutes for $10^5$ words; very high powers are given as recursive recipes, which can be checked from the recipe itself (Buys, Polak and Zuiddam did so in Lean).
• Larger independent sets in small fixed powers, which feed the recursive constructions and are easy to verify.
• Any upper bound below $3.3177$. This needs a new method beyond the theta function and would be a major result.
• A Lean statement is in formal-conjectures (Ben Green's open problem 38, an equivalent formulation).

References

1. C. E. Shannon, "The zero error capacity of a noisy channel", IRE Transactions on Information Theory 2 (1956), 8–19. doi:10.1109/TIT.1956.1056798
2. L. Lovász, "On the Shannon capacity of a graph", IEEE Transactions on Information Theory 25 (1979), 1–7. doi:10.1109/TIT.1979.1055985
3. S. Polak and A. Schrijver, "New lower bound on the Shannon capacity of $C_7$ from circular graphs", Information Processing Letters 143 (2019), 37–40. doi:10.1016/j.ipl.2018.11.006
4. P. Buys, S. Polak and J. Zuiddam, "Lean-verified lower bounds for the Shannon capacity of odd cycles" (2026). arXiv:2607.29681
5. R. Tandon, "Strengthening recursive constructions for zero-error Shannon capacity" (2026). arXiv:2608.30273

Source

Imported from Optimization Constants in Mathematics, constant 9, curated by Terence Tao and contributors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.