The exact zero-error Shannon capacity of the seven-cycle
Let $C_7$ be the cycle with vertex set $\mathbb{Z}/7\mathbb{Z}$, distinct vertices being adjacent when their difference is $\pm 1$. For $k \ge 1$ let $a_k$ be the largest size of a set $\mathcal{C} \subset (\mathbb{Z}/7\mathbb{Z})^k$ such that any two distinct $x, y \in \mathcal{C}$ have a coordinate $i$ with $x_i - y_i \notin \{0, 1, -1\}$ modulo $7$; equivalently, $a_k$ is the independence number of the $k$-th strong power of $C_7$. The Shannon capacity of $C_7$ is $$\Theta(C_7) = \sup_{k \ge 1} a_k^{1/k},$$ and $\log_2 \Theta(C_7)$ is the zero-error capacity, in bits per use, of a channel with seven symbols in which neighbouring symbols can be confused. Lovász proved $\Theta(C_5) = \sqrt{5}$ and, for odd $n$, $\Theta(C_n) \le \vartheta(C_n) = n \cos(\pi/n) / (1 + \cos(\pi/n))$, which is less than $3.3177$ for $n = 7$. Polak and Schrijver found an independent set of size $367$ in the fifth strong power of $C_7$, so that $\Theta(C_7) \ge 367^{1/5} > 3.2578$, and a 2026 preprint of Tandon raises the lower bound to $3.25883262\ldots$.
Problem. Determine $\Theta(C_7)$ exactly.
Source: Shannon (1956), who defined the zero-error capacity of a channel and its graph; for the seven-cycle see Lovász (1979) and Polak and Schrijver (2019).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- IT
- Keywords
- AIM Open Applied Problems, Shannon capacity, strong graph products, zero-error codes
References
@article{shannon1956,
author = {Shannon, Claude E.},
title = {The zero error capacity of a noisy channel},
journal = {IRE Trans. Inform. Theory},
volume = {2},
number = {3},
year = {1956},
pages = {8--19},
doi = {10.1109/TIT.1956.1056798},
}
@article{lovasz1979,
author = {Lov{\'a}sz, L{\'a}szl{\'o}},
title = {On the {S}hannon capacity of a graph},
journal = {IEEE Trans. Inform. Theory},
volume = {25},
number = {1},
year = {1979},
pages = {1--7},
doi = {10.1109/TIT.1979.1055985},
}
@article{polak2019,
author = {Polak, Sven C. and Schrijver, Alexander},
title = {New lower bound on the {S}hannon capacity of {$C_7$} from circular graphs},
journal = {Inform. Process. Lett.},
volume = {143},
year = {2019},
pages = {37--40},
doi = {10.1016/j.ipl.2018.11.006},
eprint = {1808.07438},
archivePrefix = {arXiv},
}
@misc{tandon2026,
author = {Tandon, Ravi},
title = {Strengthening recursive constructions for zero-error {S}hannon capacity},
year = {2026},
eprint = {2608.30273},
archivePrefix = {arXiv},
}
@misc{aim-seven-cycle-shannon-capacity,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The exact zero-error Shannon capacity of the seven-cycle}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/260-seven-cycle-shannon-capacity.md},
note = {Entry 260 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00553, "The exact zero-error Shannon capacity of the seven-cycle", clopen.solutions.