PaperlayerView exact revision on arXiv

Source-linked AI summary

Diagnosing the Refuted Mismatched Decoding Converse for Binary-Input Channels

Jonathan Scarlett

arXiv:2609.28109v1cs.ITmath.IT

TL;DR

Balakirsky claimed the LM rate equals mismatch capacity for binary-input DMCs, but a numerical counterexample showed superposition coding can achieve a strictly higher rate. This paper examines the proof’s permutation lemma and restricted-code and selector-sequence steps, identifying specific flaws and showing the proposition that uses them is false in general.

  • Problem

    A counterexample refuted Balakirsky’s binary-input converse, but the earlier work did not identify a concrete flaw in his proof.

    Source: §1 · p. 1, §2.1 · p. 5

  • Method

    The paper diagnoses Balakirsky’s proof by examining its permutation lemma and its selector-sequence and restricted-code steps.

    Source: §1 · p. 1, §3.2 · p. 11, §4 · p. 20

  • Results

    The permutation lemma and specific restricted-code and selector-sequence steps are flawed, and the proposition containing those steps is false in general [7].

    Source: §3.2 · p. 11, §4 · p. 20

  • Takeaways & Limitations

    Balakirsky’s claimed equality between the LM rate and mismatch capacity for binary-input channels cannot hold in general [7, 8].

    Source: §2.1 · p. 5, §4 · p. 20

    The asymptotic equality used in the combinatorial-approximation argument is less clearly guaranteed for arbitrary codes at rates at or below I(P, K).

    Source: §3.4.2 · p. 19

Abstract

from arXiv · show

We revisit the claimed converse theorem for mismatched decoding over binary-input discrete memoryless channels (Balakirsky, 1995) and the subsequent work refuting this converse via a numerical counter-example (Scarlett, Somekh-Baruch, Martinez, and Guill\'en i F\`abregas, 2015). A notable gap in the existing understanding is that no concrete flaw was identified in Balakirsky's analysis. In this paper, Balakirsky's proof is "diagnosed", and it is demonstrated that (i) his permutation lemma is flawed regardless of the correctness of his combinatorial approximation lemma; (ii) there are at least two specific incorrect steps regarding restricted codes and selector sequences, and these appear to be unlikely to admit a local repair; and (iii) the proposition in which these incorrect steps are used is false in general.

1 Introduction

The paper revisits Balakirsky’s claimed binary-input converse after a numerical counterexample showed that superposition coding can exceed the LM rate. It diagnoses specific failures in the proof, against a background of limited early converse results and ongoing work on improved achievable rates.

1 Introduction

  • Balakirsky’s claimed converse was a notable early exception to the scarcity of single-letter upper bounds, asserting that the LM rate is tight for binary-input DMCs.Earlier mismatched-decoding work largely focused on achievable rates, including the GMI and LM rate.Source: §1 · p. 1

1.1 Problem Setup

  • The mismatched-decoding setup fixes a possibly suboptimal decoding rule; the LM rate is an achievable rate obtained using constant-composition random codes.The optimized LM rate is bounded above by mismatch capacity.Source: §1 · p. 1, §1.1 · p. 2

1 Introduction

  • The numerical counterexample showed an achievable superposition-coding rate strictly above the LM rate, but did not identify where Balakirsky’s argument failed.The paper takes up that proof-level gap.Source: §1 · p. 1
  • The paper identifies incorrect steps involving selector sequences and restricted codes, and argues that they are unlikely to admit a local repair [7, Eqs. (75) and (76)].The introduction also says the proposition containing those steps is false in general [7, Proposition 6.5].Source: §1 · pp. 1–2

1.2 Related Work

  • The related work describes product-channel and multi-user coding as distinct routes to improve on the LM rate, with superposition coding able to exceed it.The product-channel conjecture remains open for the standard maximum-metric decoder, while it holds for erasures-only metrics.Source: §1.2 · p. 4

2 Claimed Converse and Counter-Example

Balakirsky’s claimed converse combines combinatorial approximation and permutation lemmas with a weak converse for an auxiliary channel to assert the LM-rate bound. The counterexample uses superposition coding and an auxiliary channel satisfying the stated constraints.

2.1 Summary of Claimed Converse

  • Balakirsky’s argument claims a composition-dependent rate bound equal to the LM rate, and then a claimed capacity equality after optimizing over input compositions.The argument combines the combinatorial approximation lemma and permutation lemma with the weak converse for V.Source: §2.1 · p. 5

2.2 Summary of the Counter-Example

  • Superposition coding on the product channel (W^2, q^2), with auxiliary alphabet U = {0, 1}, supplies the improved achievable rate used in the counterexample.An achievable rate for the product channel gives half that rate for (W, q).Source: §2.2 · p. 6

2.3 Further Useful Observations

  • The cited passage states that the rate pair (R0, R1) = (0.0356005, 0.2403966) lies in the achievable superposition coding region, established in [8, Eq. (51)] (see also for the code).For the diagnosis below, it is convenient to back off slightly.Source: §2.3 · p. 6
  • Because the pair is strictly inside the achievable region, expurgation yields maximal error tending to zero under W while preserving composition and asymptotic rate [10, 11].The auxiliary channel V is chosen to satisfy the marginal and metric constraints defining the LM rate, with d(P, V) < d(P, W).Source: §2.3 · pp. 6–7

3 Diagnosing the Claimed Converse

The analysis shows that the permutation lemma fails independently of the combinatorial approximation lemma, then identifies two incorrect selector-sequence steps in Balakirsky’s Proposition 6.5 [7].

3.1 Failure of the Permutation Lemma

  • At rate approaching 0.1375, a constant-composition code sequence has positive maximal error under V_n, contradicting the permutation lemma’s claimed implication [7].The argument does not require the combinatorial approximation lemma to establish this failure.Source: §3.1 · p. 8

3.2 Two Specific Incorrect Steps in [7, Proposition 6.5]

  • Balakirsky’s restricted-code argument replaces an (x, y)-dependent selector with a y-only selector, where the restriction depends on relative empirical frequencies rather than selected-coordinate count [7].The proposed justification relies on the y-only selector having higher selection probabilities, but that does not make the restriction monotone.Source: §3.2 · pp. 9–10
  • A channel-metric pair and code provide a counterexample to the claimed selector-replacement inequality, even when the stated conditions are satisfied [7].The paper says this is unlikely to admit a local repair.Source: §3.2 · pp. 8, 10
  • For the paper’s counterexample parameters, the transmitted word eventually never belongs to the restricted code under the y-only selector, so the claimed probability limit fails [7].The original (x, y)-dependent selector enforces the relevant empirical frequencies by construction; under the y-only selector, the probability eventually becomes exactly zero.Source: §3.2 · pp. 11–12

3.3 Failure of [7, Proposition 6.5] Itself

The paper refutes Proposition 6.5 by constructing codes whose restricted error tends to zero while their ordinary exact-type error stays bounded away from zero. The proof controls same-cloud and wrong-cloud competitors separately.

3.3 Failure of [7, Proposition 6.5] Itself

  • A constant-composition code sequence makes the claimed identity in Proposition 6.5 false for every admissible tolerance sequence [7].The construction has restricted error tending to zero, while ordinary exact-type error is bounded away from zero.Source: §3.3 · p. 13, §3.3.5 · p. 17

3.3.1 Useful technical definitions

  • The exact-type channel S fixes the conditional type of (Y, Z) given X, has Y-marginal V, and links the paired-symbol statistic to the restriction condition [7].For sufficiently large block lengths, the full restriction can be relaxed to a fixed positive tolerance without increasing the restricted error bound.Source: §3.3.1 · pp. 14–15

3.3.2 Method of types analysis

  • A method-of-types bound upper-bounds the probability that a same-cloud competitor survives the restriction and is favored by the maximum-metric decoder [7].The bound is combined with a union bound over the satellites in the transmitted cloud.Source: §3.3.2 · p. 16

3.3.3 Exponential decay via a dual certificate

  • An explicit lower bound and dual certificate establish the optimization inequality needed to make the restricted same-cloud error decay exponentially [7].For sufficiently small fixed α*, the resulting bound is strictly above R1.Source: §3.3.3 · p. 16

3.3.4 Wrong-cloud errors

  • The ordinary wrong-cloud error under V^2 tends to zero exponentially, and conditioning on the exact type and imposing the restriction preserve that conclusion [7].The section uses the cloud-rate dual formula to bound this error.Source: §3.3.4 · p. 17

3.3.5 Completion of the argument

  • A deterministic superposition-code sequence can be expurgated to a P-constant-composition sequence whose maximal restricted error tends to zero, while its ordinary exact-type V2m error stays bounded away from zero.Together, these findings contradict the claim in (65) and establish Lemma 4.Source: §3.3.5 · p. 17

3.4 Other Potential Gaps in the Analysis

This section examines additional potential gaps in Balakirsky’s proof, including issues in Proposition 6.7 and in the combinatorial approximation lemma. The authors distinguish concrete counterexamples from concerns that may be confined to particular regimes or amenable to repair.

3.4.1 Issues in the proof of [7, Proposition 6.7]

  • The concentration step in [7, Proposition 6.7] is unjustified as stated: k_ab may remain small, so its √k_ab fluctuations need not be dominated by the tolerance.For arbitrary deterministic codebooks, relevant positive k_ab values need not grow with n and can equal 1; expurgation is suggested, but the error-causing competitor may depend on the realized output and selector.Source: §3.4.1 · p. 18
  • A separate step in [7, Proposition 6.7] leaves the boundary d(P,V)=d(P,W) uncovered when α_n is set to zero, unless the same sequence also satisfies (102).The authors describe this as seemingly minor and suggest perturbation or continuity as possible repairs.Source: §3.4.1 · p. 18

3.4.2 Combinatorial approximation lemma [7, Lemma 4.4] and its proof

  • The claimed nearest-output implication is false: the correction can lower a competitor’s distortion, and a nearest output can tie, which counts as an error.The paper gives an example with an output of exact conditional type V and minimum possible distance, yet the nearest output creates a tie.Source: §3.4.2 · p. 19
  • The nearby-channel converse step is justified when the fixed rate exceeds I(P,K), but its claimed asymptotic equality is less clear for arbitrary codes at rates at or below I(P,K).At those rates, the argument may require robustness to perturbations whose size depends on n.Source: §3.4.2 · p. 19
  • At the capacity boundary, matched decoding error can be at least 1/2−o(1) for positive-dispersion channels while combinatorial-channel error may approach zero.The authors call this a highly degenerate example and say it does not rule out a lemma version sufficient for the proof’s application.Source: §3.4.2 · p. 19
  • The authors expect [7, Lemma 4.4] to be less general than claimed, while allowing that it may hold in the generality needed for its application.The rate restriction I(P,V)<R<I(P,W) appears to ease the concern on the V side, but not on the W side; a suitable amendment to [7, Eq. (42)] is still needed.Source: §3.4.2 · p. 19

4 Conclusion

The earlier counterexample refuted Balakirsky’s claimed converse [7] but left the proof’s flaw unidentified. This paper identifies false steps in the proof and shows that the conclusion of Proposition 6.5 is false for the same counterexample.

4 Conclusion

  • The permutation lemma is itself false, as shown using the superposition-coding counterexample from.The paper establishes this regardless of the correctness of the combinatorial approximation lemma.Source: §4 · p. 20
  • Two specific steps in [7, Proposition 6.5] concerning selector sequences and restricted codes are false.The authors suggest these steps may not be locally repairable.Source: §4 · p. 20
  • The conclusion of [7, Proposition 6.5] is false for the superposition-coding counterexample used in.The authors also note that the identified flaws may not be exhaustive.Source: §4 · p. 20
  • The paper also raises other potential issues, which may be locally repairable.The authors do not claim their identified flaws are exhaustive.Source: §4 · p. 20

A A Correction to [8, Lemma 1]

The paper corrects a continuity bound used in [8, Lemma 1]. The correction accounts for distributions approaching the simplex boundary and leaves the stated counterexample conclusion unchanged.

A A Correction to [8, Lemma 1]

  • When Q moves toward the simplex boundary, the stated bound can fail: the example gives 0.17532 on the left and 0.13863 on the right.The issue arises when the bound uses a lower bound on Q′ without accounting for Q.Source: A A Correction to [8, Lemma 1] · p. 20
  • The corrected bound uses qmin = min over x of min{Q(x), Q′(x)}, the smallest coordinate across both distributions.Every point on the segment between Q and Q′ has both coordinates at least qmin.Source: A A Correction to [8, Lemma 1] · p. 20
  • At qmin = 0.042, the continuity penalty changes from 9.8153412 × 10−5 to 9.8154034 × 10−5, while CLM ≤ 0.136900 remains unchanged.The corrected bound does not affect the counterexample.Source: A A Correction to [8, Lemma 1] · p. 20

B Proof of Lemma 2 (Counter-Example to [7, Eq. (75)])

A constructed example contradicts the claim in [7, Eq. (75)] by showing that the restricted-error comparison goes in the opposite direction. The proof contrasts how two selector choices constrain a competing codeword.

B Proof of Lemma 2 (Counter-Example to [7, Eq. (75)])

C.1 Proof of Lemma 5 (Relation Between gb and Restriction Condition)

The proof relates a sum over pair positions to the restriction condition. It uses the support of the relevant distribution to simplify the condition and show that two constraints are identical.

C.1 Proof of Lemma 5 (Relation Between gb and Restriction Condition)

  • On the support of S2m, the condition Xj = 0 is redundant and can be removed from the expression.The support property used is that S(y, 1|1) = 0 for y in {1, 2}.Source: §C.1 · p. 25
  • Substituting the identities for the two sums into (144) gives (78), relating the sum of gb terms to the restriction condition.The identities follow from the definitions of kab(y) and the relevant symbol sets.Source: §C.1 · p. 25
  • The absolute-value constraints for y = 1 and y = 2 are identical.This follows from k0b = k0b(1) + k0b(2) and ∆V0(2) = 1 − ∆V0(1).Source: §C.1 · p. 25

C.2 Proof of Lemma 6 (Method of Types Analysis)

This proof bounds the contribution of competing sequences by analyzing compatible joint types and then summing over them. Conditioning on the actual pair channel changes the bound by only a polynomial factor for types satisfying (89).

C.2 Proof of Lemma 6 (Method of Types Analysis)

  • The transmitted pair (U, X†) has exact type Q_UX2, while the competitor X† has conditional type Q_X2|U given U.The analysis conditions on a specified realization of (U, X†, Y†, Z†) and draws the competitor uniformly from its conditional type class.Source: §C.2 · p. 26
  • Conditioning on the exact single-coordinate conditional type of (Y, Z) given X changes (148) by only a polynomial factor for types satisfying (89).This affects only the O(log m) term in (148).Source: §C.2 · p. 26
  • For each compatible joint type, the two exponents sum to D(eP_AX†∥B), using the KL chain rule and matching (U, X†) marginals.The conditional type-class bounds are compared with bounds for a memoryless pair channel; the cited analogues are [21, Eq. (A.12)] and [21, Eq. (A.17)].Source: §C.2 · p. 26
  • Summing the bound over polynomially many compatible pair types satisfying (90)–(91) proves (94).The types also satisfy (87)–(89) by construction.Source: §C.2 · p. 26

C.3 Proof of Lemma 7 (Dual Certificate)

The proof derives a variational lower bound from the constraints defining F_α∗, then evaluates explicit choices of its certificate functions and parameters. This establishes (96) with a numerical lower bound on E_α∗.

C.3 Proof of Lemma 7 (Dual Certificate)

  • The argument invokes a variational inequality that holds for any real-valued function F.The passage cites [22, Theorem 4.6].Source: §C.3 · p. 26
  • The constraints defining F_α∗ imply a lower bound on E_P[F] by reducing its first three terms via equality constraints and bounding the remaining terms.The ψ term is nonnegative by (90), while the restriction constraints bound μ_bE_P[g_b] below by −2α∗|μ_b| for b ∈ {0, 1}; minimizing yields (155).Source: §C.3 · p. 27
  • The certificate uses explicit choices for the auxiliary cost functions a and ā, the h function, and the remaining scalar parameters.Entries marked by a dash have zero probability under Q_UX2 and are irrelevant.Source: §C.3 · p. 27
  • E_α∗ ≥ 0.35870725 − 60.444α∗, establishing (96).The evaluation of (155) is numerically verified in.Source: §C.3 · p. 27

AI Declaration

The author set out to identify a significant incorrect step in Balakirsky’s proof, then focused on the steps in Section 3.2 as stronger candidates for major flaws. AI assisted with initial arguments and code, while the sole author takes responsibility for the paper’s claims and code.

AI Declaration

  • The author’s goal was to identify an incorrect step in significant enough to be unlikely to admit a local repair.The issue in Section 3.4.1 was initially identified with substantial AI assistance, but the author was convinced only of its incorrectness, not its significance; later discussion made the Section 3.2 steps stronger candidates for major flaws.Source: AI Declaration · p. 27
  • AI generated initial versions of several mathematical arguments and accompanying code, which the author then checked, edited, expanded, and rewrote.The author states that, as sole author, they take responsibility for all claims and their correctness, and for the code.Source: AI Declaration · p. 28
Loading 2609.28109v1…