CCapacity Atlas
sun-jafar-11-message-index-coding

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

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

Channel and question

Input
Eleven independent messages \(W_1,\ldots,W_{11}\) held by one broadcaster.
Output
Receiver \(j\) recovers \(W_j\) from the broadcast and its side information.
Law
The unknown interferer sets are \(\{4,5\},\{5\},\varnothing,\varnothing,\{2\},\{2,3\},\{1,3\},\{2,4\},\{3,4\},\{3,5\},\{4,6\}\).
Quantity
Nonlinear symmetric capacity \(C_{\mathrm{sym}}\), measured in message symbols per broadcast symbol.

Criterion. Zero-error symmetric multiple-unicast capacity in message symbols per broadcast symbol.

  • Messages are uniform, independent, equal-length words over one common finite alphabet.
  • Decoding error is exactly zero for every message tuple and receiver.
  • Arbitrary finite alphabets, blocklengths, and nonlinear encoders and decoders are allowed.

Current status

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

The linear-encoder symmetric capacity is exactly 5/13. The formal quantity constrains the encoder to be linear and permits arbitrary zero-error decoders; equivalence with a definition requiring linear decoders is not yet established.

Known results and bounds for Sun-Jafar 11-message multiple-unicast index-coding instance
ResultRelationMethodYear
Lower\(C_{\mathrm{sym}}\ge\frac5{13}\)Explicit vector-linear interference alignment.2015
Upper\(C_{\mathrm{sym}}\le\frac{11}{28}\)Entropic converse using a non-Shannon inequality.2015
Linear Encoder Exact\(C_{\mathrm{sym}}^{\mathrm{linear\text{-}enc}}=\frac5{13}\)Linear-encoder achievability plus an Ingleton linear-rank converse.2015
Upper\(C_{\mathrm{sym}}\le\frac25\)Best outer bound obtainable from normalized Shannon polymatroid constraints.The Zhang-Yeung inequality strictly improves this relaxation value.2015

Open question

Prove \(C_{\mathrm{sym}}=5/13\), or construct a nonlinear code above \(5/13\).

Linear-rank inequalities close the linear-encoder problem, while known entropic inequalities do not close the nonlinear gap.

Rule out a concrete nonlinear code family.

Tasks

  • doneFormalize the operational zero-error and linear-encoder capacity quantities.
  • doneMachine-check the one-based table, alignment graph, inner diamond, and internal conflict distance.
  • openFormalize the 5/13 vector-linear code.
  • openFormalize the 11/28 converse.

Formal verification

Lean coverageFormally stated

Claims

  • Unrestricted nonlinear zero-error symmetric capacity equals 5/13.
    exact-capacity · exact capacity · open · Formally stated · v2
  • Published 5/13 linear-encoder achievability bound.
    linear-achievability · achievability · solved · Formally stated · v3
  • 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 · v2
  • Unrestricted nonlinear zero-error symmetric capacity is at most 11/28.
    nonlinear-converse · converse · solved · Formally stated · v2
  • The Shannon polymatroid relaxation equals 2/5.
    shannon-relaxation-value · converse · solved · Formally stated · v2
  • Operational 2/5 outer bound derived from the Shannon relaxation.
    shannon-outer-bound · converse · solved · Formally stated · v1
  • Exact enumeration of the abstractly defined internal conflicts.
    internal-conflicts-exact · structural · test · Formally proved · v1
  • Every internal conflict has alignment-graph distance two.
    internal-conflict-distance · structural · test · Formally proved · v1
Lean declarations (9)

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 six-message groupcast index-coding instance SJ6-GC

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