An arXiv preprint reports a finite two-receiver broadcast channel for which Marton’s one-letter inner bound falls short of what can be achieved with a two-letter construction. In the paper’s terms, the complete one-letter Marton region is strictly contained in that channel’s capacity region.
The paper asks whether Marton’s inner bound always reaches the capacity region for general discrete memoryless broadcast channels. It compares a one-letter evaluation with a two-letter extension in the private-message case, setting the common-message rate R0 to zero and seeking a strict improvement in the maximum private-message sum-rate.
To build the example, the authors shape a concave fixed-input objective and use a receiver-revealed mixture to remove the input constraint while preserving a gain across multiple channel uses. The search is iterative and structure-driven, using elimination geometry and guidance from earlier counterexamples. Numerical inequalities for the explicit instance are certified with exact rational arithmetic and outward-rounded MPFR calculations.
The decisive gaps are tiny
The base model is a ternary-input, ternary-output broadcast channel: X, Y and Z each take the values 0, 1 and 2. At the specified input distribution, its three coordinates are approximately 0.7045, 0.1726 and 0.1229.
The reported unrestricted optimizer gives a nonzero value for I(U;V|X), the quantity used here to test a Markov condition: about 0.066768 nats. The unrestricted optimum was also approximately 8.742 × 10−5 nats above the optimum found when that condition was imposed.
A separate fixed-input calculation found a positive two-letter gain of at least 2.8275 × 10−6 nats. The gain was supported by an explicit rational joint distribution whose two input-coordinate marginals both equal the prescribed input distribution.
Removing the input restriction produced the main existence result: a finite channel with a two-letter Marton value greater than twice its one-letter value. That strict inequality means the complete one-letter Marton region is strictly contained in the channel’s capacity region.
For one explicit finite realization, directed-rounding calculations put the one-letter upper bound at no more than 0.3008418661 nats and the two-letter lower bound at no less than 0.6016856143 nats. After doubling the one-letter bound, the reported separation still exceeded 1.8821 × 10−6 nats. The channel has no input cost, fixed-composition constraint or encoder-side restriction.
A counterexample with clear limits
The result is an existence claim for a finite channel, not a characterization of which channels are sub-optimal. The analysis is confined to private messages and a maximum sum-rate separation rather than a full calculation of the capacity region, and the authors leave the tightness of Marton’s bound for binary-input channels open.
The work is a mathematical construction based on finite channel models, auxiliary distributions and numerical certificates, not empirical participant data. The demonstrated gaps are very small, and the explicit inequalities are certified numerically.
The authors state that code for reproducing the numerical computations is available.
Paper data and sources
Original title: Sub-optimality of Marton's Inner Bound for the Two-Receiver Broadcast Channel
Authors: Mian Huang, Yanxiao Liu, Yi Liu
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text