gpt 6 astra pro attempt on CS-23

Capacity of the General Discrete Memoryless Relay Channel

Definitions and mathematical statement

A discrete memoryless relay channel has finite alphabets and a conditional law $W(y,y_r\mid x,x_r)$. A length-$n$ code consists of a source encoder for a uniform message $M$, causal relay encoders $x_{r,i}=f_i(y_r^{i-1})$, and a destination decoder $\widehat M=g(y^n)$. A rate $R$ is achievable when codes exist with $\liminf n^{-1}\log_2|\mathcal M_n|\ge R$ and $\Pr(\widehat M\ne M)\to0$. Define \[ C(W)=\sup\{R:R\text{ is achievable} \}. \] The problem asks for a computable exact characterization for every $W$, not this operational definition repeated as an answer. The relay cannot depend on its current or future observation. Average error, not zero error, is the criterion.

Formulation and concept references: [S1].

Short English statement

What is the exact reliable communication rate for an arbitrary finite relay channel when the relay can use only its past observations?

Research attempt

Current frontier and status of the cited claim.

Cover--El Gamal's achievable schemes and converse bounds coincide for important degraded classes, but their general inequalities do not give the requested characterization [E1]. The learning-based compress-and-forward source optimizes achievable schemes, rather than proving their optimality among all codes [S1]. The September 2026 manuscript in [S2], Theorem 4, claims a general capacity formula as a maximum of three scheme-specific quantities. Its converse uses the circuit-consistency argument developed in its Section V. That manuscript is treated here as a proof claim, not as an established theorem: I inspected the proposed characterization but have not independently verified that its converse covers every causal relay code. No assumption that all codes reduce to those three schemes enters the argument below.

Attack route.

Optimizing one-letter auxiliaries needs a converse showing that longer relay memories add no rate. Enumerating all block codes instead gives lower approximations with no automatic stopping rule. I combine these routes by isolating a quantitative finite-memory penalty. The resulting bound is sharp on a simple channel and identifies exactly the effective compactness statement that would turn the block formula into a computable answer.

Editorial note on computability.

A finite alphabet does not provide a finite encoding for arbitrary real transition probabilities. The calculations below are algorithms for rational transition laws, and extend relative to an oracle supplying certified rational approximations to the entries of $W$. This explicitly states the input representation used for the word "computable"; it does not impose a new channel law or change the strict-causality or average-error requirements. No undecidability claim is being made.

Attempt: a finite optimization, not an operational tautology.

For a fixed block length $n$, a deterministic relay policy is a finite tree $\pi=(f_i)_{i=1}^n$ with $f_i:\mathcal Y_r^{i-1}\to\mathcal X_r$. It induces the ordinary finite channel \begin{equation} W_\pi^{(n)}(y^n\mid x^n) =\sum_{y_r^n}\prod_{i=1}^n W\left(y_i,y_{r,i}\mid x_i,f_i(y_r^{i-1})\right). \end{equation} Define \begin{equation}\label{wsref-0-33-30-30-30-36-37-36-35-3a-61-6e} a_n(W)=\max_{\pi}\max_{p(x^n)}I(X^n;Y^n),\qquad a_0(W)=0. \end{equation} All logarithms in this entry are base two. The first maximum ranges over a finite set; the second is the capacity optimization of a finite discrete memoryless channel. Compactness of the input simplex and continuity of entropy give an attained maximum.

Resetting the relay between an $m$-block and an $n$-block, and using independent source block inputs, proves \begin{equation} a_{m+n}\geq a_m+a_n,\qquad 0\leq a_n\leq n\log|\mathcal Y|. \end{equation} In fact \begin{equation}\label{wsref-0-33-30-30-30-36-37-36-35-3a-6c-69-6d-69-74} C(W)=\sup_{n\geq1}\frac{a_n(W)}n =\lim_{n\to\infty}\frac{a_n(W)}n. \end{equation} Here is a proof to ensure that no forbidden current-observation relay operation has entered the formula. Fix $n$ and $\pi$. Repeating that policy with a reset makes successive $n$-blocks into independent uses of $W_\pi^{(n)}$. An ordinary outer channel code therefore achieves any rate below $I(X^n;Y^n)/n$. Padding an incomplete final block costs a vanishing fraction of the rate. This is the usual finite-channel coding theorem used in relay achievability arguments [E1].

Conversely, an arbitrary deterministic length-$N$ relay code supplies one of the policies in (30006765:an). By data processing and Fano's inequality, \begin{equation} (1-P_e)\log|\mathcal M_N|\leq I(M;Y^N)+1 \leq a_N(W)+1. \end{equation} Taking reliable code sequences gives the reverse inequality in (30006765:limit). Random code construction does not change it: a realized deterministic code with no larger average error can be fixed. The final equality follows from superadditivity, or directly by writing $N=qn+r$ and using $a_N\geq q a_n$.

For rational $W$, each $a_n$ is a computable real. Enumerate the finitely many policy trees, evaluate the induced transition matrices exactly, and optimize over a rational grid in the input simplex. A uniform continuity bound for entropy on a fixed finite alphabet controls the grid error, including boundary probabilities equal to zero. The process is extremely expensive but finite. Equation (30006765:limit) is still not the requested computable exact characterization: a supremum of computable lower approximations need not come with an effective upper-error bound. No rate of convergence has been proved yet.

Attempt: a finite-memory boundary-state bound.

Let $C_K(W)$ denote the supremum of achievable rates when the relay has an internal state in a set of at most $K$ elements at every time. Its output and state-update functions may depend on the time index; the public clock is free. The source code is otherwise unrestricted. This is a restricted class used only for a reduction, not a replacement for the original channel model.

Boundary-state lemma. For every $K,n\geq1$, \begin{equation}\label{wsref-0-33-30-30-30-36-37-36-35-3a-6d-65-6d-6f-72-79} C_K(W)\leq\frac{a_n(W)+\log K}{n}. \end{equation} Proof. Partition a long $K$-state code into consecutive blocks of length $n$. Let $S_j$ be the relay state at the start of block $j$, and let $Y^{<j}$ denote earlier destination observations. For the output $Y_j$ of this block, \begin{align} I(M;Y_j\mid Y^{<j}) &\leq I(M;S_j,Y_j\mid Y^{<j})\notag\\ &\leq\log K+I(M;Y_j\mid Y^{<j},S_j). \end{align} After conditioning on a value of $(Y^{<j},S_j)$, the relay's next $n$ steps form an admissible deterministic policy with fixed starting state. The source has no feedback, so its block input is determined by $M$, and the future channel noises are independent of the past conditional on the block inputs. Thus data processing for this induced finite channel bounds the last conditional mutual information by $a_n(W)$, for every value of the conditioning variables. Summing over blocks and bounding the incomplete block by $n\log|\mathcal Y|$ gives (30006765:memory) after Fano's inequality and the long-code limit. $\square$

The conditioning step is important: discarding the boundary state without paying $\log K$ would be wrong because it can contain message information learned in earlier blocks.

The exact missing effective-memory statement.

Suppose there is a computable function $K(W,\delta)$, on the chosen representation of $W$ and positive rational $\delta$, such that \begin{equation}\label{wsref-0-33-30-30-30-36-37-36-35-3a-6d-6f-64-75-6c-75-73} C(W)\leq C_{K(W,\delta)}(W)+\delta. \end{equation} Take an integer $n$ with $\log K(W,\delta)/n\leq\delta$. Combining (30006765:limit) and (30006765:memory) gives the rigorous bracket \begin{equation} \frac{a_n(W)}n\leq C(W) \leq\frac{a_n(W)}n+2\delta. \end{equation} Computing $a_n/n$ to an additional error $\delta$ would then compute capacity to arbitrary prescribed accuracy. The function need not be polynomial-time, small, or uniform over different alphabet sizes; mere effective finiteness would suffice.

There is also a useful warning in the reverse direction. If capacity were already computable uniformly in this representation, enumerate certified approximations to $a_n/n$ and $C$ until $a_n/n>C-\delta$ is certified. Such an $n$ exists by (30006765:limit). Any length-$n$ policy can be implemented, with resets, by storing its within-block observation history, using at most \begin{equation} K_n=\sum_{i=0}^{n-1}|\mathcal Y_r|^i \end{equation} states. Therefore $C_{K_n}\geq a_n/n>C-\delta$. This constructs an effective $K$ from a capacity algorithm. So the proposed effective-memory principle is genuinely tied to the computability issue, not a theorem following from the qualitative existence of finite good codes. The forward bound (30006765:memory) is useful, but it does not evade the central difficulty by renaming it.

An exact sharpness test with strict one-step delay.

Consider the binary deterministic channel \begin{equation} Y_{r,i}=X_i,\qquad Y_i=X_{r,i}. \end{equation} The relay can send $X_{i-1}$ at time $i$, achieving asymptotic rate one with two states. In an isolated $n$-block its first output is fixed, and the remaining $n-1$ binary outputs give at most $n-1$ bits of mutual information. The delay policy attains this value, so \begin{equation} a_n=n-1,\qquad C=C_2=1, \qquad C_2-\frac{a_n}{n}=\frac{\log2}{n}. \end{equation} Thus the $\log K/n$ penalty in (30006765:memory) cannot generally be removed or replaced by zero. The checking script verifies the output counts for $1\leq n\leq8$; the preceding argument proves the formula for every $n$. Instantaneous relaying would incorrectly predict $a_1=1$, so this also tests the catalogue's strict causality convention.

Stress test and outcome.

Outcome: Conditional reduction.

The block optimization is exact but not automatically computable in its limit. The proved boundary-state inequality is sharp, and an effective finite-memory approximation bound would give an algorithm with certified two-sided errors. Conversely such an effective bound can be recovered from an already available capacity algorithm, so its existence has not been established by compactness or by enumeration. The missing step is to prove an effective memory bound directly from $W$, or supply another valid universal converse with a stopping rule. No claim in the current status preprint has been treated as that missing proof, and no noncomputability result or general capacity formula with a proved effective convergence rate is asserted here.

Sources

• S1 Ozyilkan, Carpi, Garg and Erkip, Learning-Based Compress-and-Forward Schemes for the Relay Channel. https://arxiv.org/html/2405.09534v3. Catalogue formulation source.
• S2 Status source for Capacity of the General Discrete Memoryless Relay Channel. https://arxiv.org/html/2609.15709v1. Catalogue research/status reference; not a proof endorsement.
• E1 Thomas M. Cover and Abbas A. El Gamal, "Capacity Theorems for the Relay Channel," IEEE Trans. Inform. Theory 25 $1979$, no. 5, 572--584. Channel model, degraded-channel capacity theorems, general bounds and coding arguments. https://www-isl.stanford.edu/groups/elgamal/abbas_publications/J003.pdf. Established relay coding foundation; the notebook supplies its own finite-block and boundary-state deductions.