CCapacity Atlas
seven-cycle-zero-error-channel

Seven-cycle zero-error channel

The exact Shannon capacity of the seven-cycle remains unknown between a finite fifth-power certificate and the Lovász theta bound.

Zero error Finite alphabet Discrete memoryless Zero-error capacity Bounds only Regularized characterization

Channel and question

Input
Seven symbols indexed cyclically.
Output
Confusability is exactly adjacency in the cycle graph \(C_7\).
Law
Two length-n words are confusable when every coordinate is equal or adjacent in \(C_7\).
Quantity
Multiplicative Shannon capacity \(\Theta(C_7)\), measured in zero-error alphabet growth per channel use.

Criterion. Supremum of nth roots of zero-error code cardinalities.

  • Decoding error is exactly zero.
  • Independent uses correspond to strong graph powers.

Current status

\[367^{1/5}\le\Theta(C_7)\le\frac{7\cos(\pi/7)}{1+\cos(\pi/7)}\]
ResultRelationMethodYear
Lower\(\Theta(C_7)\ge367^{1/5}\)Explicit independent set of size 367 in the fifth strong power.2019
Upper\(\Theta(C_7)\le\vartheta(C_7)=\frac{7\cos(\pi/7)}{1+\cos(\pi/7)}\)Lovász theta, multiplicative under strong product.1979

Research frontier

Determine \(\Theta(C_7)\) exactly or strictly improve either certified endpoint.

Why it remains open. Finite strong-power independent sets and known multiplicative upper bounds leave a persistent gap.

What would count as progress

  • Verify larger strong-power independent-set certificates.
  • Find an upper parameter below Lovász theta for this graph.

Lean formalization

Canonical statementStatement

Version 1 · Lean. Decimal approximations are omitted; the proposition records exact symbolic endpoints.

Substantial proofs0 linked

No external Lean proof is registered. Proofs longer than roughly 50 lines or requiring problem-specific infrastructure should live in a dedicated repository and link back to this statement version.

References

  1. Claude E. Shannon (1956). The Zero Error Capacity of a Noisy Channel. IRE Transactions on Information Theory. DOI 10.1109/TIT.1956.1056798.
  2. László Lovász (1979). On the Shannon Capacity of a Graph. IEEE Transactions on Information Theory. DOI 10.1109/TIT.1979.1055985.
  3. Sven Polak and Alexander Schrijver (2019). New Lower Bound on the Shannon Capacity of C7 from Circular Graphs. Information Processing Letters. DOI 10.1016/j.ipl.2018.11.006.

Discussion

Thread key: capacityatlas:seven-cycle-zero-error-channel

Find discussionStart discussion

Related problems

Pentagon zero-error channel C5

The confusability graph is a five-cycle, whose Shannon capacity is exactly the square root of five.

Zero error Finite alphabet Discrete memoryless Zero-error capacity Exact Regularized characterization
Solved \(\Theta(C_5)=\sqrt5,\qquad C_0(C_5)=\frac12\log_2 5\)
Zero-error capacity of a general confusability graph

For a finite confusability graph, the regularized independence number defines capacity but is difficult to compute or characterize.

Zero error Finite alphabet Discrete memoryless Zero-error capacity Regularized characterization Bounds only
Open \(\Theta(G)=\sup_{n\ge1}\alpha(G^{\boxtimes n})^{1/n}\)
Binary deletion channel BDC

Each input bit is independently deleted without an erasure marker; the exact capacity is unknown for every nontrivial deletion probability.

Point-to-point Binary Finite alphabet Memory Deletion Capacity Bounds only
Open \(0.1221(1-d)<C_{\mathrm{del}}(d)\le0.3578(1-d)\)
Binary random-insertion channel

In the fixed iid random-insertion model, each transmitted bit may be followed by one independent fair inserted bit and exact capacity is unknown.

Point-to-point Finite alphabet Binary Memory Capacity Bounds only
Open \(0\le C_{\mathrm{ins}}(p)\le1\)