Two General Capacity Theorems for Finite Channels

XSci (AI review)

October 28, 2026

Summary

The manuscript proves two capacity theorems for finite channels. The first (Theorem 2.1) determines the capacity of an arbitrary finite noisy permutation channel, where a memoryless $W$ acts on a length-$n$ word and the receiver sees only the output histogram: $C_{\mathrm{perm}}(W)=\max_{\emptyset\neq S}(r(S)+b(S)-2)/2$, with $r(S)$ the rank of the submatrix of rows $S$ and $b(S)$ the number of connected components of its support graph, together with the two-sided estimate (8) and a strong converse. The second (Theorem 3.1) treats block kernels whose conditional marginals on every set of at most $k_n=o(n)$ coordinates equal the product channel exactly, and shows their optimal zero-error rate is $\max_P\min\{H_2(P),H_2(PW),I(P,W)+d\}$, where $d$ bounds the per-symbol divergence from $W^{\otimes n}$. Appendix A proves an additive special case; Appendix B sharpens the remainder in (8) to $O(1)$ for nonsingular square matrices with at most two positive entries per row.

Contribution and Significance

The substantial contribution is Theorem 2.1. Tang and Polyanskiy established $(\mathrm{rank}\,W-1)/2$ for strictly positive matrices with a weak converse, and listed general non-strictly-positive matrices and strong converses as open; their Appendix D leaves a gap for the zigzag channel between the achievability $(q-1)/2$ and an upper bound no better than $3(q-1)/4$. Theorem 2.1 closes all of this at once. The formula is a finite combinatorial invariant, the maximization over input subsets is shown to be necessary by the explicit matrix (3), and the converse is strong. The mechanism behind it — equation (27) — is the real advance: a type may approach several faces of the input simplex at different powers of $n$, and the authors show that the resulting determinant exponent is an average over nested active subsets $S_s$ and therefore cannot exceed the maximum over single subsets. That is exactly the obstruction that blocked earlier converses, and it is settled in a page.

Relative to the closest prior work, the genuinely new ingredients are the subset maximization with the component correction (Tang and Polyanskiy's block-diagonal result $(\mathrm{rank}\,W+\beta-2)/2$ is the special case in which all blocks are strictly positive and no maximization is needed), the strong converse, and the two supporting lemmas. The second theorem is a weaker contribution than the manuscript implies, for the reason given under Major Concern 1.

Strengths

• Lemma 2.3 bounds $\sup_y P_k(Y=y)$ by $(q+1)^{(q-1)/2}/\sqrt{\det(I_q+\Sigma(k))}$ uniformly in the input type, via a maximizing-forest bound on the characteristic function combined with Cauchy–Binet. It replaces a local CLT, is uniform at zero counts, and handles disconnected supports and deterministic rows without case analysis. I verified each step.
• Lemma 2.5 is a clean identity: $\dim U_S=r(S)-1$ and $\dim(U_S\cap V_S)=r(S)-b(S)$. It is what converts the determinant exponents of Lemma 2.4 into $r(S)+b(S)-2$, and it explains why rank and support geometry enter in the combination they do.
• The achievability in Section 2.10 is matched exactly to the converse: $b(S)-1$ component totals read off without error at scale $n$, and $(r(S)-b(S))/2$ internal dimensions on a $\sqrt{n}$ grid, giving (31).
• The finite certificates in Sections 4.2 and 4.5 are self-contained and correct. I recomputed the eight-bit Z-channel certificate: $K(w)$ in (85) is indeed the sum of the 37 Walsh features, $256-37=219$, the density range $[72/73,80/73]$ is right, and $D_2(Q\|P)=0.006102471\ldots$ bits together with the bounds $0.005646563$ and $0.006572951$ all reproduce. The repetition-code table in Section 4.5 ($\varepsilon=3.3624888\times10^{-5}$, $B_{15,2}=8641$, $\varepsilon B=0.2905527$) also reproduces exactly.

Recommendation

Major Revision for IEEE Transactions on Information Theory. Theorem 2.1 is a Transactions-grade result and, as far as I could verify the proof, correct. What stands in the way is not the mathematics of Section 2 but the manuscript around it: the second theorem is an unmotivated and much weaker contribution occupying half the text, the survey of prior work omits the paper that created the problem, and one proof hypothesis is absent from the page. I would also urge the authors to split the manuscript; the two halves share no model, no technique and no application.

Major Concerns

1. The second theorem's operational content (Sections 1.4, 3.1–3.8, Appendix A). Zero-error capacity depends on a channel's row supports and nothing else. The calibration constraint (35) restricts only marginals on $o(n)$ coordinates at a time, and such marginals cannot see the global support: a law supported on an exponentially small subset of $\mathcal{Y}^n$ can have every $k_n$-coordinate marginal equal to a full-support product law. Theorem 3.4 then follows from deleting a decoding-failure event of exponentially small probability and repairing the moments, at vanishing divergence cost. The authors prove the complementary statement themselves — Proposition A.9 shows a linearly growing $k_n$ does bite — which confirms that the force of the result lies in the sublinearity of the constraint rather than in the channel.

   Sections 3.8 and A.10 then withdraw nearly every physical reading of the construction: the family is not projectively consistent, not stationary, not causal, not efficient, and by (137) any contamination $\eta>0$ destroys it. What remains is a design problem that no stated application requires. The revision should either supply a scenario in which a designer may choose $V_n$ subject to (35) and is charged by (36), or say plainly that this is an abstract synthesis problem and identify which part of (37) is surprising; the input-independent example (78) and the Z-channel frontier (82) are the strongest arguments the authors have and should lead the section.

2. Positioning and attribution (Section 1.3, reference list). The account of the state of the art rests on three references and omits A. Makur, "Coding theorems for noisy permutation channels," IEEE Transactions on Information Theory, vol. 66, no. 11, pp. 6723–6748, 2020, which introduced this channel model and the $\log M/\log n$ normalization, proved $C_{\mathrm{perm}}\geq(\mathrm{rank}\,W-1)/2$ for every DMC by a count-grid argument close to that of Section 2.10, and posed the conjecture [1] settled. A reader cannot assess the novelty claim of Section 1.3 without it. Second, the title given for [3] is not the title of arXiv:2605.25699, which is "Volume-Refined Achievability and Converse Approximations for Noisy Permutation Channels"; Section 1.3 uses that citation to fix the boundary of prior work, so please correct it. Third, Section 3 and Appendix A are about zero-error capacity yet cite nothing from that literature: not C. E. Shannon, "The zero error capacity of a noisy channel," IRE Transactions on Information Theory, vol. 2, no. 3, pp. 8–19, 1956, whose feedback formula $\max_P\min_y\log 1/P(S_y)$ has the same max–min shape as (37), and not T. S. Cubitt, D. Leung, W. Matthews and A. Winter, "Zero-error channel capacity and simulation assisted by non-local correlations," IEEE Transactions on Information Theory, vol. 57, no. 8, pp. 5509–5523, 2011, the standard precedent for a correlation budget giving a closed-form zero-error rate.

3. An incomplete proof and unlocatable evidence. In the proof of Lemma 3.5, "Fix a sufficiently small $\delta>0$ such that" is followed by the display (61), which is empty. Everything downstream depends on it: that the parenthesis in (68) is at most $2^{-\delta n}$, and that the exponent in (72) tends to $H_2(PW)-R-4\delta>0$. Since Lemma 3.5 carries the achievability of (37) above $I(P,W)$, a central claim is unproved as printed; please supply the condition and recheck the $\delta$ bookkeeping. Separately, Section 4 states that "the full source, audit code, machine-readable results, and editable figures accompany the manuscript," but no repository or supplement is identified, Sections 4.1, 4.3 and 4.4 give only aggregate counts (28 matrices, 7,711 Cauchy–Binet bases) without the instances, and Figures 1 and 2 appear as captions with no figure.

Minor Comments

1. The manuscript is around fifty pages with duplicated machinery — Lemma B.3 restates (22), and the converse (154) restates (29) — so publication as two papers would serve both results better.
2. Equation (12) is skipped: the display in Section 2.2 is numbered (13).
3. Theorem 2.1 states the $-O(1)$ lower bound of (8) alongside "explicit count-grid codes attaining it with vanishing maximal error," but Section 2.10 shows vanishing maximal error costs a further $O_W(\log\log n)$.
4. Please say whether the $(p-1)\log\log(n+2)$ term in (8) is believed to be real or an artifact of the dyadic cover, since Appendix B removes it for one class.
5. Section 2.11 declines to claim a polynomial-time algorithm for $\gamma(W)$; is the maximization over independent row subsets NP-hard when $p$ and $q$ grow?
6. Section 2.12 checks the formula against the strictly positive, block-diagonal and erasure results of [1] but not against its Z-channel value $1/2$.
7. Appendix B's advance over Theorem 2.1 is confined to the $O(1)$ remainder for one class, and eleven pages is a great deal for that.
8. Section A.9 leaves the frontier for $k_n/n\to\alpha>0$ open with only the bound (136); some indication of what the authors expect would help.
9. No bound is given on the cost of the constructions of Section 3 beyond the remark that they "may require exponential resources."
10. A comparison of (8) against the finite-blocklength bounds of [2] and [3] on a shared example would show what the new converse buys at moderate $n$.
11. A permutation-channel paper should cite M. Kovačević and V. Y. F. Tan, "Codes in the space of multisets," IEEE Transactions on Information Theory, vol. 64, no. 7, pp. 5156–5169, 2018; and [6] also appeared at ISIT 2020, pp. 2108–2113.
12. In the proof of Lemma 3.5, "Write $a=|\chi|$" should read $a=|\mathcal{X}|$, as the use in (64) and (66) makes clear.