CCapacity Atlas
seven-cycle-zero-error-channel

Seven-cycle zero-error channel

The Shannon capacity of the seven-cycle remains unknown.

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)}\]
Known results and bounds for Seven-cycle zero-error channel
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

Open question

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

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

Research directions

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

Formal verification

Lean coverageFormally stated

Concrete operational definitions and admitted research statements are present. Existing proofs are preserved. New statements require mathematical review and proof completion.

Claims

  • The seven-cycle Shannon capacity lies between 367^(1/5) and 7 cos(π/7)/(1+cos(π/7)).
    capacity-bounds · capacity bounds · solved · Formally stated · v1
  • Operational zero-error versions of the existing seven-cycle graph bounds.
    operational-capacity-bounds · capacity bounds · solved · Formally stated · v1
  • Independently tracked operational achievability.
    operational-achievability · achievability · solved · Formally stated · v1
  • Independently tracked operational converse.
    operational-converse · converse · solved · Formally stated · v1
Lean declarations (4)

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

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\)