Shannon capacity of the seven-cycle

Put seven letters around a circle. A channel can confuse neighboring letters, but can distinguish non-neighbors. A safe message set must never contain two messages the receiver could confuse. The puzzle asks how large safe sets become when many letters are sent together.[1] [2]

A seven-symbol channel confuses neighboring symbols around a cycle. Jointly choosing whole words can beat repeating the best one-symbol choice; the unknown is the optimal growth factor over arbitrarily long blocks. Write $\alpha(G)$ for the largest independent set of graph $G$. The $n$-fold strong power of $C_7$ connects distinct words when every coordinate is equal or adjacent. Its independent sets are zero-error codes, and $\Theta(C_7)=\sup_{n\geq1}\alpha(C_7^{\boxtimes n})^{1/n}$; $\log_2\Theta(C_7)$ is the rate in bits per channel use. Repeating a finite block code gives longer codes with the same normalized growth factor, so a finite construction certifies an asymptotic lower bound, rather than determining the optimum.[1] [2]

For one use, three well-spaced letters are safe. Two uses can carry ten distinct safe messages, already better than repeating a three-letter choice. Researchers can build much larger sets, but still do not know the best long-run rate.[1] [2]

The semidefinite Lovász bound is Θ(C₇)≤7 cos(π/7)/(1+cos(π/7)), approximately 3.31766721. The August 2026 preprint reports an independent set in C₇^⊠500 giving a lower bound near 3.25883262. Neither a finite certificate nor verification of its arithmetic supplies the upper bound needed to prove that its rate is optimal.[1] [2]

This example shows why a channel’s ultimate power cannot always be read off from one use. Correlations between positions can create additional perfectly distinguishable messages, even though each position has exactly the same confusion rule.[1] [2]

A receiver need not tell every symbol apart on its own to identify a whole message. Two words can be confusable in one position but separated in another, and different pairs of words can rely on different positions. That flexibility lets the seven-symbol channel carry ten distinct two-symbol messages where separate three-symbol choices give nine, without changing the channel’s confusion rule. It connects a graph’s nonadjacent word sets to information that can be distinguished without error: the important structure is which complete messages can coexist. Counting messages per block would reward longer transmissions automatically; the normalized growth factor instead exposes the gain per channel use. Determining its ultimate value would reveal the extent of this collective gain, which finite constructions demonstrate but do not exhaust.[1] [2]