CCapacity Atlas
sun-jafar-six-message-groupcast-index-coding

Sun-Jafar six-message groupcast index-coding instance

A six-message, ten-receiver groupcast instance has linear-encoder capacity 5/13 and a non-Shannon nonlinear upper bound 11/28.

Index coding Finite alphabet Non-Shannon inequalities Nonlinear coding Symmetric capacity Bounds only Linear-encoder-only result

Channel and question

Input
Six independent equal-length messages held by one broadcaster.
Output
Ten receivers demand messages \((1,1,2,3,4,5,6,6,6,6)\) in source order.
Law
The one-based interference rows are \(\{2,4\},\{4,5\},\{5\},\varnothing,\varnothing,\{2\},\{1,3\},\{2,3\},\{3,4\},\{3,5\}\).
Quantity
Zero-error nonlinear symmetric capacity \(C_{\mathrm{sym}}\), measured in message symbols per broadcast symbol.

Criterion. Zero error for every message tuple and receiver, with arbitrary finite alphabet and blocklength.

  • Messages are uniform, independent, and use one common finite alphabet.
  • Decoding error is exactly zero and arbitrary blocklength nonlinear codes are allowed.

Current status

\[\frac5{13}\le C_{\mathrm{sym}}\le\frac{11}{28}\]

Global linear-encoder symmetric capacity is exactly 5/13; Shannon inequalities alone stop at 2/5. The formal quantity permits arbitrary zero-error decoders, pending a proof that they may always be chosen linear.

Known results and bounds for Sun-Jafar six-message groupcast index-coding instance
ResultRelationMethodYear
Lower\(C_{\mathrm{sym}}\ge\frac5{13}\)Explicit vector-linear subspace alignment.2015
Upper\(C_{\mathrm{sym}}\le\frac{11}{28}\)Zhang-Yeung non-Shannon information inequality.2015
Linear Encoder Exact\(C_{\mathrm{sym}}^{\mathrm{linear\text{-}enc}}=\frac5{13}\)Linear-encoder construction and Ingleton converse.2015

Open question

Prove the nonlinear capacity is 5/13 or construct a zero-error nonlinear code above it.

Known non-Shannon inequalities improve the converse but do not meet the linear construction.

Improve either endpoint with an auditable certificate.

Formal verification

Lean coverageFormally stated

Demands and interference rows are machine-checked translations of the one-based primary-source figure.

Claims

  • Unrestricted nonlinear zero-error symmetric capacity equals 5/13.
    exact-capacity · exact capacity · open · Formally stated · v1
  • Published 5/13 linear-encoder achievability bound.
    linear-achievability · achievability · solved · Formally stated · v2
  • Unrestricted 5/13 lower bound derived from linear-encoder achievability.
    unrestricted-achievability · achievability · solved · Formally stated · v1
  • Global finite-field linear-encoder symmetric capacity is at most 5/13.
    linear-converse · converse · solved · Formally stated · v1
  • Unrestricted nonlinear zero-error symmetric capacity is at most 11/28.
    nonlinear-converse · converse · solved · Formally stated · v1
  • The Shannon polymatroid relaxation equals 2/5.
    shannon-relaxation-value · converse · solved · Formally stated · v1
  • Operational 2/5 outer bound derived from the Shannon relaxation.
    shannon-outer-bound · converse · solved · Formally stated · v1
  • Exact translation of all ten source interference rows.
    interference-translation · structural · test · Formally proved · v1
Lean declarations (8)

References

  1. Hua Sun and Syed A. Jafar (2015). Index Coding Capacity: How Far Can One Go With Only Shannon Inequalities?. IEEE Transactions on Information Theory. DOI 10.1109/TIT.2015.2418289.
  2. Zhen Zhang and Raymond W. Yeung (1998). On Characterization of Entropy Function via Information Inequalities. IEEE Transactions on Information Theory. DOI 10.1109/18.681320.

Discussion

Find discussionStart discussion

Related problems

Sun-Jafar 11-message multiple-unicast index-coding instance SJ11

The linear-encoder symmetric capacity is known, while unrestricted nonlinear capacity remains open.

Index coding Finite alphabet Multiple unicast Non-Shannon inequalities Nonlinear coding Symmetric capacity Bounds only Linear-encoder-only result
Open \(\frac5{13}\le C_{\mathrm{sym}}\le\frac{11}{28}\)
Directed-cycle index-coding problem

Each receiver in a directed cycle knows its successor message and requests its own message.

Index coding Finite alphabet Side information Multiple unicast Nonlinear coding Symmetric capacity Exact
Solved \(C_{\mathrm{sym}}=1/(m-1)\)
Undirected five-cycle index-coding problem

Each of five receivers knows its two neighbours and asks for its own independent message.

Index coding Finite alphabet Side information Multiple unicast Nonlinear coding Symmetric capacity Exact
Solved \(C_{\mathrm{sym}}=2/5\)
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)\)