CCapacity Atlas
pentagon-zero-error-channel

Pentagon zero-error channel

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

Channel and question

Input
Five symbols represented by the vertices of the cycle graph C5.
Output
Channel outputs induce confusability exactly along the edges of C5.
Law
Two input symbols can share an output if and only if they are adjacent in the pentagon confusability graph.
Quantity
Zero-error capacity \(C_0(C_5)\), measured in bits per channel use.

Criterion. Asymptotic zero-error communication.

  • Decoding error must be exactly zero.
  • Independent channel uses correspond to strong graph products.

Current status

\[\Theta(C_5)=\sqrt5,\qquad C_0(C_5)=\frac12\log_2 5\]

Theta is the multiplicative Shannon capacity of the graph.

ResultRelationMethodYear
Lower\(\Theta(C_5)\ge\sqrt5\)Five independent codewords exist in the two-fold strong product.1956
Upper\(\Theta(C_5)\le\vartheta(C_5)=\sqrt5\)The Lovász theta function upper-bounds Shannon capacity.1979

Lean formalization

Canonical statementNone

Version 1 · Lean. This is a good first substantial external proof after graph products and Lovász theta are available.

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.

Discussion

Thread key: capacityatlas:pentagon-zero-error-channel

Find discussionStart discussion

Related problems

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 Z-channel Z-channel

One binary symbol is transmitted perfectly while the other can flip in only one direction.

Point-to-point Binary Finite alphabet Discrete memoryless Asymmetric Capacity Exact
Solved \(C_Z(p)=\log_2\!\left(1+(1-p)p^{p/(1-p)}\right)\)
Binary erasure channel BEC

Each transmitted bit is received correctly or replaced by a visible erasure symbol.

Point-to-point Binary Finite alphabet Discrete memoryless Symmetric Erasure Capacity Exact
Solved \(C_{\mathrm{BEC}}(\varepsilon)=1-\varepsilon\)
Binary symmetric channel BSC

Each bit is independently flipped with probability p, giving the canonical finite noisy channel.

Point-to-point Binary Finite alphabet Discrete memoryless Symmetric Capacity Exact
Solved \(C_{\mathrm{BSC}}(p)=1-h_2(p)\)