Capacity and Reliability of Mismatched Decoding

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

For a memoryless channel $W(y\mid x)$, a mismatched decoder ranks codewords by a prescribed metric $q$ instead of the channel likelihood; in the product-metric formulation it maximizes $\prod_{t=1}^n q(x_t,y_t)$. Mismatched capacity is the supremum of rates achievable with vanishing decoding error for this fixed metric. At rate $R$, the reliability function measures the best attainable exponent $\liminf_{n\to\infty}-n^{-1}\log P_e^{(n)}$. A single-letter characterization uses distributions on one-use variables rather than a limit over block lengths.

Statement recorded in the supplied source.

Find a single-letter characterization of mismatched decoding capacity, and determine the exact reliability function for mismatched decoding. [S2]

Scope qualification.

Tie breaking, input constraints, alphabet and average/maximum error conventions are those of the cited problem. The metric is fixed, so optimizing it into maximum-likelihood decoding would change the question.

Source status.

The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

Determine achievable rates and optimal error-decay exponents when a decoder uses the wrong scoring metric.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30005062 (OWR-9790365-012). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 New Mathematical Techniques in Information Theory $2023$, Oberwolfach Reports, DOI 10.4171/owr/2022/14, pp. 683--707 https://doi.org/10.4171/owr/2022/14.
• S3 Somekh-Baruch, single-letter upper bound https://doi.org/10.1109/TIT.2022.3146308. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30005062 and source code OWR-9790365-012 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

The primary report, p. 699, asks for general single-letter capacity and reliability formulas while keeping the additive decoding metric fixed. The preserved definition uses a product metric. Below the additive score $s(x,y)=\mathbf1\{x\ne y\}$ is equivalent to the positive product metric $q(x,y)=\exp(s(x,y))$. This distinction matters: a product of zero-one mismatch indicators would define a different decoder.

Research attempt: A reverse-Hamming metric with a uniform error floor

Consider a binary symmetric channel with crossover $p\in[0,1/2]$, and a decoder maximizing total Hamming distance from the received word. Let two distinct codewords $x,x'$ have distance $d\geq1$. When $x$ is transmitted, let $K$ be the number of channel flips among the $d$ coordinates on which the codewords differ. Coordinates on which they agree contribute equally to their scores. On the differing coordinates, the scores of $x$ and $x'$ are $K$ and $d-K$. Hence $K<d/2$ forces the wrong word to score strictly above the true word, regardless of all other codewords and all tie conventions.

Using independent uniform random variables $U_j$, the representation $K_p=\sum_{j=1}^d\mathbf1\{U_j\leq p\}$ couples $K_p\leq K_{1/2}$. Therefore \[ \Pr\{K_p<d/2\}\geq\Pr\{K_{1/2}<d/2\}\geq\tfrac14. \tag{3} \] For odd $d$, symmetry makes the middle probability $1/2$. For $d=2l\geq2$, it is \[ {1\over2}\left(1-\binom{2l}{l}4^{-l}\right)\geq\tfrac14. \] Indeed the central probability equals $1/2$ at $l=1$, and the ratio of its value at $l+1$ to that at $l$ is $(2l+1)/(2l+2)<1$. This proves $3$, including the worst small-distance boundary.

In any code with at least two distinct codewords, fix one competitor for each transmitted word and apply $3$. Every message then has conditional error at least $1/4$, and so does the average. Consequently the mismatched capacity of this channel-metric pair is zero. At every positive rate for which code sequences are considered, $P_e\geq1/4$ implies $0\leq-n^{-1}\log P_e\leq n^{-1}\log4\to0$; its achievable reliability exponent is therefore zero. Rate zero with a one-message code is excluded from this last assertion.

At the sharper boundary $p=0$, every different codeword has strictly greater score than the transmitted word, so the error is one whenever there is a competitor. Yet the same noiseless physical channel with maximum-likelihood decoding can transmit all $2^n$ binary words with zero error. This exhibits the exact obstruction to replacing a fixed mismatched metric by an optimized likelihood metric.

Verification and adversarial audit

The event used in $3$ gives a strict score inequality, so even favorable ties do not invalidate the lower bound. The cases $d=1$, $d=2$, $p=0$, and $p=1/2$ are explicit. Codewords are distinct as in ordinary block codes; repeating them cannot supply a positive reliable rate. The product/additive conversion uses exponentiation, not a zero-one product.

Audit corrections.

The additive metric was translated correctly into the retained product convention. Zero-rate one-message behavior and positive-rate error exponents are separated.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

This proves an elementary capacity and exponent statement for one deliberately adverse metric. It provides no general single-letter characterization, and it does not determine the low-rate matched reliability function included in the report's broader discussion.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46950 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.