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.

Known results and bounds for Pentagon zero-error channel
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

Formal verification

Lean coverageFormally stated

New statements await mathematical review and proofs.

Claims

  • Both the graph growth constant and operational zero-error capacity of the pentagon typewriter.
    operational-capacity · exact capacity · solved · Formally stated · v1
  • Independently tracked graph capacity.
    graph-capacity · exact capacity · solved · Formally stated · v1
  • Independently tracked typewriter capacity.
    typewriter-capacity · exact capacity · solved · Formally stated · v1
Lean declarations (3)

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

Find discussionStart discussion

Related problems

Seven-cycle zero-error channel C7

The Shannon capacity of the seven-cycle remains unknown.

Zero error Finite alphabet Discrete memoryless Zero-error capacity Bounds only Regularized characterization
Open \(367^{1/5}\le\Theta(C_7)\le\frac{7\cos(\pi/7)}{1+\cos(\pi/7)}\)
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\)