\documentclass[11pt,a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern,amsmath,amssymb,amsthm,mathtools,booktabs,array,graphicx,microtype}
\usepackage[margin=1in]{geometry}
\usepackage[hidelinks]{hyperref}
\usepackage{enumitem}
\setlist{itemsep=3pt,topsep=5pt}
\setlength{\emergencystretch}{2em}
\setlength{\parskip}{3pt}
\urlstyle{same}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}\newtheorem{remark}[theorem]{Remark}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\TD}{TD}
\DeclareMathOperator{\supp}{supp}
\newcommand{\id}{I}
\newcommand{\cD}{\mathcal D}
\newcommand{\Sraw}{S_{\mathrm{raw}}}
\newcommand{\hbin}{h_2}
\title{\LARGE The Shared Randomness Cost of Optimal\\ One Use Loop Communication}
\author{Daniel A. Pyle\\\normalsize Independent Researcher\\\small\href{https://orcid.org/0009-0005-6456-1370}{ORCID 0009-0005-6456-1370}}
\date{Preprint\\31 October 2026}
\hypersetup{pdftitle={The Shared Randomness Cost of Optimal One Use Loop Communication},pdfauthor={Daniel A. Pyle},pdfsubject={Exact raw seed support and entropy in a stipulated normalized-loop model}}
\begin{document}
\maketitle
\begin{abstract}
We determine the minimum support and Shannon entropy of a shared classical seed needed to attain optimal worst-message success in a specified one-use normalized-loop model. The loop contains a backward binary symmetric channel with crossover $0<p<1/2$ and a fixed finite-dimensional forward quantum channel. Seed branches are mixed as unnormalized weights before one normalization for each message. For qubit output and interior forward trace-distance diameter, equality at the known unrestricted optimum forces every supported seed to activate exactly two message labels. The seed-cost problem becomes a fractional perfect matching problem: even message counts are optimally covered by disjoint pairs, while odd counts require a triangle and disjoint pairs. We give separate exact formulas at zero and unit diameter, prove a sufficient higher-dimensional extension of the interior result, and exhibit an erasure-channel counterexample to diameter-only seed costs in general dimension. Explicit near-optimal constructions show how the exact-attainment cost discontinuities can be avoided at finite tolerance. Compactness also gives a strict performance gap below the minimum seed support. A complete exact-certificate calculation determines the two-seed classical optimum for three messages at backward and forward crossover $1/10$. These are resource-specific mathematical results, not a physical backward-communication protocol or an asymptotic capacity theorem.
\end{abstract}

\section{Introduction}
A communication protocol that normalizes its outcome weights can use common randomness differently from an ordinary stochastic protocol. When seed branches are combined before normalization, their posterior weights can depend on the transmitted message. It is therefore important to specify both the stage at which a seed is independent and the resource charged for that seed.

The backward channel is assumed throughout; no mechanism for producing one is proposed. An earlier draft derives an exact worst-message success formula for a single backward binary symmetric channel, a fixed noisy forward carrier, and an unrestricted finite shared seed \cite{PyleRaw}. Its cyclic attaining construction uses as many seed values as messages, but does not establish that this many are necessary. This paper answers the exact-attainment resource question for qubit-output forward channels. The minimum seed support and entropy depend on the parity of the message count and change at zero and unit forward diameter. The principal step is an equality analysis that applies to arbitrary mixed decoder instruments; an extreme-decoder upper bound alone would not justify a seed-cost lower bound.

For an interior diameter, each seed must select one ordered pair of active labels. Balancing worst-message success then imposes equal weighted graph degrees. This reduces the resource optimization to a standard fractional perfect matching polytope. Its odd-cycle structure gives the parity effect. At unit diameter a seed may instead select a singleton, and at zero diameter each decoder row may distribute its output among several labels. We analyze both degeneracies directly. We also show why the qubit hypothesis matters: a larger forward carrier can transmit a decoder-generated flag, reducing the common seed cost while keeping the same channel diameter and unrestricted success.

The normalized decoder--memory--encoder architecture and conditional error criteria belong to an established literature \cite{JLW,JRW}. Trace-distance contraction coefficients and the graph-polytope facts used here are also established \cite{FMS,HR,Behrend}. The contribution proposed here is their connection through equality in this particular resource-restricted optimization, together with exact endpoint and dimension analyses. A bounded literature screen is not an originality guarantee. The earlier raw-seed and seedless manuscripts are unpublished research manuscripts \cite{PyleRaw,PyleSeedless}; their submission to Hexagon is author-reported.

\section{Model and the unrestricted optimum}\label{sec:model}
Let $\Phi:\mathcal L(\mathcal H_A)\to\mathcal L(\mathcal H_B)$ be a completely positive trace-preserving map between finite-dimensional operator spaces. There are $M\ge2$ classical messages, labeled by $\mathbb Z_M$. The backward binary channel is stipulated to be
\begin{equation}
 N_p(b\mid a)=\begin{cases}1-p,&b=a,\\p,&b\ne a,\end{cases}
 \qquad 0<p<\tfrac12,\qquad A=1-p,\quad k=1-2p.\label{eq:bsc}
\end{equation}
This assumption does not establish the physical availability of a backward channel.

A finite seed has raw probabilities $\pi_s\ge0$, $\sum_s\pi_s=1$, independent of the selected message and of $b$. Both devices know its value. For each $s,b$, the decoder outputs $y$ and prepares a subnormalized forward state
\begin{equation}
 \tau^s_{yb}\succeq0,\qquad \sum_y\Tr\tau^s_{yb}=1.\label{eq:decoder}
\end{equation}
The forward carrier undergoes $\Phi$. Knowing $m,s$, the encoder uses $0\preceq E^s_m\preceq\id$, with $E^s_{0\mid m}=E^s_m$ and $E^s_{1\mid m}=\id-E^s_m$. The weights and normalizers are
\begin{align}
 w^s_m(y)&=\sum_{a,b=0}^1N_p(b\mid a)\Tr\!\left[E^s_{a\mid m}\Phi(\tau^s_{yb})\right],\label{eq:weights}\\
 Z^s_m&=\sum_yw^s_m(y).\label{eq:z}
\end{align}
No output label or retained side register is forwarded to the encoder. There is no shared entanglement or additional channel use. Local private randomness and a fixed public codebook are allowed. The seed is an additional resource, not part of the forward carrier dimension.

The defining convention is raw mixing followed by a single per-message normalization:
\begin{equation}
 P(m\mid m)=\frac{\overline w_m(m)}{\overline Z_m},\qquad
 \overline w_m(y)=\sum_s\pi_sw^s_m(y),\quad
 \overline Z_m=\sum_s\pi_sZ^s_m.\label{eq:raw}
\end{equation}
We maximize $\min_mP(m\mid m)$ after marginalizing the seed. This differs from externally mixing individually normalized branches, $\sum_s\pi_sw^s_m(y)/Z^s_m$, and from demanding a success guarantee for every seed. In \eqref{eq:raw}, the posterior seed probabilities are
\begin{equation}
 \Pr_{\mathrm{norm}}(s\mid m)=\frac{\pi_sZ^s_m}{\overline Z_m},\label{eq:posterior}
\end{equation}
which may depend on $m$. Entropy in this paper always concerns the raw law $\pi$, not \eqref{eq:posterior}.

Define the forward output trace-distance diameter
\begin{equation}
 \delta=\max_{\rho_0,\rho_1\in\cD(\mathcal H_A)}
 \tfrac12\|\Phi(\rho_0)-\Phi(\rho_1)\|_1\in[0,1].\label{eq:diameter}
\end{equation}
Here $\cD(\mathcal H)$ denotes the density operators and $\TD(\rho,\sigma)=\tfrac12\|\rho-\sigma\|_1$. The quantity $\delta$ is the established trace-distance contraction coefficient \cite{FMS,HR}. Indeed, the Jordan decomposition of $\rho-\sigma$ writes it as $r(\omega_+-\omega_-)$ with orthogonal-support states and $r=\TD(\rho,\sigma)$. The contraction ratio is at most \eqref{eq:diameter}; conversely $r\le1$ bounds every unscaled output distance by its ratio. Compactness gives a diameter-attaining pair. Convexity of trace norm permits pure inputs, orthogonal when the input dimension is at least two. In dimension one, the unique state may be used twice. For a qubit affine Bloch map $\boldsymbol{x}\mapsto T\boldsymbol{x}+\boldsymbol{t}$, $\delta$ is the largest singular value of $T$; the translation cancels.

Set $\rho^s_b=\sum_y\tau^s_{yb}$ and $\Delta^s=\Phi(\rho^s_0)-\Phi(\rho^s_1)$. Direct expansion gives
\begin{equation}
 Z^s_m=1+k\Tr(E^s_m\Delta^s),\qquad
 1-k\delta\le Z^s_m\le1+k\delta.\label{eq:normalizer}
\end{equation}
In particular $2p\le Z^s_m\le2A$, so all denominators are positive. The noiseless backward endpoint $p=0$, which needs additional admissibility rules, is not covered by this paper.

\subsection{A self contained proof of the success bound}
We restate and prove the needed result from \cite{PyleRaw}; its equality conditions will be essential.

\begin{theorem}[Unrestricted raw-seed success]\label{thm:raw}
For every finite-dimensional $\Phi$, $M\ge2$, and $0<p<1/2$,
\begin{equation}
 \Sraw(\Phi,p,M)=t_*:=\frac{2A}{M-(M-2)k\delta}.\label{eq:rawopt}
\end{equation}
The maximum is attained with a uniform $M$-valued seed. For $M=2$, no seed is needed.
\end{theorem}
\begin{proof}
Put $D_s=\sum_mw^s_m(m)$, $Q_s=\sum_mZ^s_m$, $D=\sum_s\pi_sD_s$, and $Q=\sum_s\pi_sQ_s$. Two positive weighted-average identities give
\begin{equation}
 \min_mP(m\mid m)\le\frac DQ
 =\sum_s\frac{\pi_sQ_s}{Q}\frac{D_s}{Q_s}
 \le\sup_{\tau,E}\frac{\sum_mw_m(m)}{\sum_mZ_m}.\label{eq:aggregate}
\end{equation}
For fixed encoder effects, each decoder factor in \eqref{eq:decoder} is a compact convex set of block-positive unit-trace operators. Its extreme points have one nonzero label block, equal to a pure state. A product extreme decoder therefore chooses a deterministic label $y_b$ and pure preparation $\rho_b$ for each $b$. Decomposing a decoder into such product extremes makes its aggregate ratio a positive-denominator weighted average. It is enough to bound the extreme ratios.

Write $\sigma_b=\Phi(\rho_b)$, $\Delta=\sigma_0-\sigma_1$, and $d=\tfrac12\|\Delta\|_1\le\delta$. Then $1-kd\le Z_m\le1+kd$. If the two labels are distinct, relabel them $u,v$. For $t\in[0,1]$,
\begin{align}
 w_u(u)-tZ_u
 &=p-t+k\Tr E_u[(1-t)\sigma_0+t\sigma_1]\le A-t,\label{eq:activeu}\\
 w_v(v)-tZ_v
 &=A-t-k\Tr E_v[t\sigma_0+(1-t)\sigma_1]\le A-t.\label{eq:activev}
\end{align}
The bracketed matrices are positive and have trace one. Every inactive message contributes at most $-t(1-kd)$. Substituting
\begin{equation}
 R_2(d)=\frac{2A}{2+(M-2)(1-kd)}\label{eq:R2}
\end{equation}
for $t$ makes the sum of these upper bounds zero, proving that the aggregate ratio is at most $R_2(d)\le R_2(\delta)$. Equality is attained by $E_u=\id$, $E_v=0$, and a negative spectral projector of $\Delta$ at every inactive message.

If the decoder labels coincide at $u$, only that message can succeed and its correct weight is its whole normalizer. The ratio is at most
\begin{equation}
 R_1(d)=\frac{1+kd}{(1+kd)+(M-1)(1-kd)}
 =\frac{1+kd}{M-(M-2)kd}\le R_2(d).\label{eq:R1}
\end{equation}
This proves the upper bound.

For attainment choose a diameter-attaining pair and an effect $H_-$ with $\Tr[H_-(\sigma_0-\sigma_1)]=-\delta$. Let $s$ be uniform modulo $M$. At $b=0$ output $s$ and prepare $\rho_0$; at $b=1$ output $s+1$ and prepare $\rho_1$. Set $E^s_m=\id$ for $m=s$, $E^s_m=0$ for $m=s+1$, and $E^s_m=H_-$ otherwise. Each message has two active branches, each with correct weight $A$ and normalizer one; its $M-2$ other branches have correct weight zero and normalizer $1-k\delta$. Their averaged ratio is \eqref{eq:rawopt}. For $M=2$ the same two active labels and constant encoders work in a single seed.
\end{proof}

\section{Exact seed resources}\label{sec:resources}
\begin{definition}
The support of the raw seed is $K(\pi)=|\{s:\pi_s>0\}|$, and its Shannon entropy in bits is $H(\pi)=-\sum_{s:\pi_s>0}\pi_s\log_2\pi_s$. Let $K_*$ and $H_*$ be their respective minima among protocols attaining $t_*$ in \eqref{eq:rawopt}.
\end{definition}
Seed support counts positive seed probabilities, not decoder outcomes or local random choices. A seed with support $K$ can be stored using $\lceil\log_2K\rceil$ binary memory cells. Its entropy is not an exact single-trial fair-bit sampling cost; exact sampling may require a variable number of fair bits. No claim equating these different resources is made.

\begin{theorem}[Minimum support and entropy]\label{thm:cost}
Let $M\ge3$, $0<p<1/2$, and $\dim\mathcal H_B=2$. The exact minimum raw seed support and entropy at the unrestricted optimum are
\begin{center}
\renewcommand{\arraystretch}{1.25}
\begin{tabular}{@{}llcc@{}}
\toprule
Forward diameter & Message count & $K_*$ & $H_*$ in bits\\
\midrule
$0<\delta<1$ & even & $M/2$ & $\log_2M-1$\\
$0<\delta<1$ & odd & $(M+3)/2$ & $\log_2M-1+3/M$\\
$\delta=1$ & even & $M/2$ & $\log_2M-1$\\
$\delta=1$ & odd & $(M+1)/2$ & $\log_2M-1+1/M$\\
$\delta=0$ & even & $1$ & $0$\\
$\delta=0$ & odd & $2$ & $\hbin(1/M)$\\
\bottomrule
\end{tabular}
\end{center}
Here $\hbin(x)=-x\log_2x-(1-x)\log_2(1-x)$. The support and entropy minima can be attained simultaneously. For $M=2$, $K_*=1$ and $H_*=0$ for every $\delta$.

The $\delta=0$ statement holds in every finite dimension. For $0<\delta<1$, the same formulas hold in arbitrary finite output dimension under the sufficient condition that every diameter-attaining output pair has joint support equal to $\mathcal H_B$. In particular, it is sufficient that every channel output is positive definite. No general higher-dimensional lower bound is asserted at $\delta=1$.
\end{theorem}

\subsection{Why arbitrary decoder mixing cannot hide the seed cost}
The next lemma closes the gap between an extreme-point bound on aggregate performance and a resource bound on an arbitrary optimal minimax strategy.

\begin{lemma}[Equality forces one label pair per seed]\label{lem:equality}
Under the interior hypotheses of Theorem~\ref{thm:cost}, every supported seed of an optimal strategy has one deterministic ordered output-label pair $(u,v)$, with $u\ne v$. Its correct weights and normalizers necessarily have the pattern
\begin{equation}
 (w_m(m),Z_m)=
 \begin{cases}(A,1),&m\in\{u,v\},\\(0,1-k\delta),&m\notin\{u,v\}.
 \end{cases}\label{eq:pairpattern}
\end{equation}
The forward preparations themselves need not be pure.
\end{lemma}
\begin{proof}
An optimal strategy makes both inequalities in \eqref{eq:aggregate} equalities. Thus every message succeeds with probability $t_*$ and every supported seed satisfies $D_s=t_*Q_s$. Fix one seed and its encoder effects. Decompose its decoder into a finite convex combination of product extreme points, as in Theorem~\ref{thm:raw}. All extreme ratios are at most $t_*$, and all aggregate denominators are positive. Every positive component must therefore attain $t_*$ as well.

When $0<\delta<1$, \eqref{eq:R1} is strictly smaller than $t_*$, so each component has two distinct labels. Since $M>2$ and $k>0$, \eqref{eq:R2} is strictly increasing in $d$, forcing $d=\delta$. Also $0<t_*<1$. Equality in \eqref{eq:activeu}--\eqref{eq:activev} requires
\begin{align}
 \Tr[(\id-E_u)((1-t_*)\sigma_0+t_*\sigma_1)]&=0,\label{eq:equalityu}\\
 \Tr[E_v(t_*\sigma_0+(1-t_*)\sigma_1)]&=0.\label{eq:equalityv}
\end{align}
Two distinct qubit density operators have full joint support: otherwise both would occupy the same one-dimensional subspace and coincide. Both positive convex combinations in \eqref{eq:equalityu}--\eqref{eq:equalityv} are therefore positive definite. A positive operator with zero trace against a positive definite operator must be zero. Hence $E_u=\id$ and $E_v=0$. Every inactive effect obeys $\Tr(E_m\Delta)=-\delta<0$, so is neither $0$ nor $\id$.

These effects are fixed throughout the decoder decomposition for this seed. Another optimal component cannot change the first active label, the second active label, or their order: doing so would require one fixed effect to be both constant and nonconstant, or both $0$ and $\id$. Thus every component has the same ordered label pair. Each has exactly the pattern \eqref{eq:pairpattern}, which is preserved by averaging. The same proof applies in higher dimension under the stated full-joint-support hypothesis.
\end{proof}

\subsection{The fractional matching reduction}
Let $\ell=1-k\delta>0$. Associate each seed with an edge between its two active labels and give it weight $\pi_s$. Parallel edges can be merged: a standard diameter-pair construction with their summed probability has the same pattern \eqref{eq:pairpattern}. Merging cannot increase support or entropy. If $a_m$ is the total probability of edges incident with message $m$, then
\begin{equation}
 P(m\mid m)=\frac{Aa_m}{\ell+(1-\ell)a_m}.\label{eq:degree}
\end{equation}
This is strictly increasing in $a_m$, and $\sum_ma_m=2$. Equality with $t_*$ for every message is equivalent to
\begin{equation}
 a_m=\frac2M\quad\text{for every }m.\label{eq:degrees}
\end{equation}
Conversely, any weighted graph obeying \eqref{eq:degrees} gives an optimum by using the same diameter-attaining pair on each edge. Rescale $x_e=M\pi_e/2$. The entire seed-resource problem is now
\begin{equation}
 x_e\ge0,\qquad \sum_{e\ni m}x_e=1\quad(m\in\mathbb Z_M),\label{eq:fpm}
\end{equation}
the loopless fractional perfect matching polytope. Its graph-theoretic structure is standard \cite{Behrend}; we include the needed special-case proof.

\subsection{Minimum support in the interior}
Every message must lie on an edge, so at least $M/2$ edges are required. For even $M$, disjoint pairs of weight $2/M$ attain that bound. For odd $M$, a degree-one vertex forces its unique edge to have probability $2/M$, which saturates its neighbor's degree too. Such vertices therefore form isolated pairs. Remove all such pairs. The remaining graph has minimum degree at least two and, because the original number of vertices was odd, contains at least three vertices. If it has $L$ vertices, it has at least $L$ edges, while the removed pairs contribute $(M-L)/2$. Thus
\begin{equation}
 K\ge\frac{M+L}{2}\ge\frac{M+3}{2}.\label{eq:Kodd}
\end{equation}
A triangle whose three edges each have probability $1/M$, together with $(M-3)/2$ disjoint edges of probability $2/M$, attains this lower bound.

\subsection{Minimum entropy in the interior}
Entropy is continuous and concave on the compact polytope \eqref{eq:fpm}, so a minimum is attained at an extreme point. Its support components are isolated edges with $x_e=1$ and odd cycles with $x_e=1/2$. To verify this structure, first remove leaf components, which as above are isolated pairs. Any remaining connected component has minimum degree two. If it had more edges than vertices, its unsigned incidence columns would be linearly dependent, giving a nonzero signed perturbation that preserves the constraints and, for sufficiently small magnitude, nonnegativity. It would not be extreme. Hence it is a cycle. An even cycle admits an alternating perturbation; an odd cycle has the unique solution $x_e=1/2$. Conversely, these isolated-edge and odd-cycle components each have a unique supported solution.

If $L$ vertices lie on odd cycles, the seed probabilities are $(M-L)/2$ entries of $2/M$ and $L$ entries of $1/M$. Their entropy is
\begin{equation}
 H=\log_2M-1+\frac LM.\label{eq:entropyL}
\end{equation}
For even $M$, $L=0$ is possible and optimal. For odd $M$, the minimum is $L=3$. The constructions minimizing support thus minimize entropy too. This proves the interior rows of Theorem~\ref{thm:cost}.

\section{The two diameter endpoints}\label{sec:endpoints}
The interior equality argument uses both $\delta>0$ and $\delta<1$. Their failures correspond to different feasible decoder structures, not failures of the success formula.

\subsection{Perfect distinguishability}\label{sec:perfect}
Suppose $\delta=1$ and the output is a qubit. The common-label bound \eqref{eq:R1} may now attain $t_*$. Any attaining extreme component uses outputs at distance one, which are orthogonal pure qubit states. Let $H_+,H_-$ be their complementary rank-one projectors, with $\Tr(H_\pm\Delta)=\pm1$.

A distinct-label component still uses $\id,0$ at its two active labels and $H_-$ elsewhere. A common-label component at $u$ uses $H_+$ at $u$ and $H_-$ at every other message. No two different optimal label patterns can coexist in one seed's extreme decomposition. Two distinct pair patterns conflict as in Lemma~\ref{lem:equality}. A pair and a singleton conflict because the pair has constant active effects but the singleton has only rank-one effects. Two singleton patterns at different labels also conflict: because $M\ge3$, a third label is inactive in both and fixes their $H_-$ to be the same; the first active label would then need to have both complementary projectors. Thus each supported seed is a single pair or a single singleton.

Represent a singleton at $m$ by a loop and count that loop twice in its weighted degree. This loop convention is stated explicitly; it differs from the once-counted convention used in \cite{Behrend}. If $a_m$ is the weighted degree, the averaged correct weight and normalizer are
\begin{equation}
 \overline w_m(m)=Aa_m,\qquad
 \overline Z_m=(1-k)+ka_m.\label{eq:perfectdegrees}
\end{equation}
A singleton of weight $\pi$ contributes correct weight $\pi(1+k)=2A\pi$ and increases the normalizer above its inactive value by $2k\pi$, which explains the double counting. Optimality again requires $a_m=2/M$.

At least $\lceil M/2\rceil$ seeds are needed to cover all messages. Disjoint pairs, with one singleton when $M$ is odd, attain this count. Every pair probability is at most $2/M$ and every singleton probability at most $1/M$. Among all probability vectors with atom cap $2/M$, entropy is minimized by filling as many atoms to that cap as possible and placing any residual in one atom. This follows, for example, by transferring mass from a smaller nonzero atom to a larger unsaturated atom: concavity of $-x\log_2x$ makes entropy nonincreasing. The resulting vector is $M/2$ entries of $2/M$ for even $M$, or $(M-1)/2$ entries of $2/M$ and one of $1/M$ for odd $M$. The matching-plus-singleton construction realizes it, proving the unit-diameter rows of Theorem~\ref{thm:cost}.

\subsection{Complete erasure of distinguishability}\label{sec:zero}
If $\delta=0$, the channel is a replacer: for a fixed state $\sigma$, $\Phi(\tau)=\Tr(\tau)\sigma$. Put $q_{yb}=\Tr\tau_{yb}$ and $e_m=\Tr(E_m\sigma)$. Every normalizer is one, and
\begin{equation}
 w_m(m)=(p+ke_m)q_{m0}+(A-ke_m)q_{m1}.\label{eq:replacer}
\end{equation}
The sum of correct weights is at most $2A$. Equality forces $e_m=1$ whenever $q_{m0}>0$ and $e_m=0$ whenever $q_{m1}>0$. Thus the two row label distributions have nonempty disjoint supports. Conversely, any two such distributions with these constant effects attain aggregate correct weight $2A$.

At the unrestricted optimum $2A/M$, every supported seed must attain that aggregate bound. Consider a seed of probability $\pi$. Its row supports have sizes $r_0,r_1$ with $r_0+r_1\le M$. One support has at most $\lfloor M/2\rfloor$ labels and receives total correct weight $\pi A$ from this seed. Its total correct weight from all seeds is $2A$ times its size divided by $M$. Hence
\begin{equation}
 \pi\le\frac{2\lfloor M/2\rfloor}{M}.\label{eq:zerocap}
\end{equation}
For even $M$, one seed suffices: split the messages into equal groups and make each row uniform on its group. For odd $M$, \eqref{eq:zerocap} gives the cap $(M-1)/M<1$, so at least two seeds are required and entropy is at least $\hbin(1/M)$ by the same mass-transfer argument.

For an explicit attaining odd construction, write $M=2r+1$. Partition the labels into $U$ of size $r$ and $V$ of size $r+1$, and choose distinct $v_1,v_2\in V$. In a dominant seed of probability $2r/M$, let $q_{\cdot0}$ be uniform on $U$. Let $q_{\cdot1}$ assign probability $1/(2r)$ to each of $v_1,v_2$ and $1/r$ to each other member of $V$. In a second seed of probability $1/M$, concentrate row zero at $v_1$ and row one at $v_2$. Each seed has disjoint row supports. Each message's averaged $q_{m0}+q_{m1}$ equals $2/M$, and its success is $2A/M$. This attains both lower bounds. No dimensional assumption was used, completing Theorem~\ref{thm:cost}.

\section{Why output dimension matters}\label{sec:dimension}
The full-joint-support extension in Theorem~\ref{thm:cost} is sufficient, not asserted necessary. Without an appropriate support condition, the forward output can retain information about the decoder's private random choice. Then several extreme label patterns may coexist within one seed without forcing contradictory encoder effects.

\begin{proposition}[Same diameter and different seed cost]\label{prop:dimension}
For every $0<d<1$, there is a finite-dimensional forward channel of diameter $d$ for which four messages attain the unrestricted raw optimum without a seed. A qubit-output channel of the same diameter requires two seed values and one bit of raw seed entropy.
\end{proposition}
\begin{proof}
Use four orthogonal inputs $|x_1\rangle,\ldots,|x_4\rangle$ and an erasure channel
\begin{equation}
 \Phi_d(\rho)=d\rho\oplus(1-d)\Tr(\rho)|e\rangle\langle e|,\label{eq:erasure}
\end{equation}
with a fifth orthogonal erasure flag. Its output trace distance is $d$ times the input trace distance, so its diameter is $d$.

Use one seed. At $b=0$, output and prepare labels $1,2$ with probability $1/2$ each; at $b=1$, use labels $3,4$ similarly. In coordinates $(e,x_1,x_2,x_3,x_4)$ choose the diagonal effects
\begin{equation}
\begin{aligned}
 E_1&=\operatorname{diag}(1,1,0,1,1),&
 E_2&=\operatorname{diag}(1,0,1,1,1),\\
 E_3&=\operatorname{diag}(0,0,0,0,1),&
 E_4&=\operatorname{diag}(0,0,0,1,0).
\end{aligned}\label{eq:eraser-effects}
\end{equation}
Direct contraction in \eqref{eq:weights} gives every message correct weight $A/2$ and normalizer $1-kd/2$. Its success is
\begin{equation}
 \frac{A}{2-kd}=\frac{2A}{4-2kd},
\end{equation}
the unrestricted four-message optimum. The qubit comparison follows from the interior even row of Theorem~\ref{thm:cost}.
\end{proof}

Thus the diameter determines unrestricted success but not common seed cost in general dimension. The extra carrier dimension in this counterexample is not free shared randomness. It is a distinct communication resource excluded from the qubit comparison.

\section{Approximate optimality and restricted seeds}\label{sec:approx}
Assume $M\ge3$ throughout this section; the $M=2$ optimum already needs no seed. The exact-attainment costs have discontinuities at the diameter endpoints, while the success value \eqref{eq:rawopt} is continuous. The following constructions quantify how small performance losses can avoid those cost jumps. Write
\begin{equation}
 D=M-(M-2)k\delta,\qquad t_*=2A/D.\label{eq:D}
\end{equation}
A protocol is $\varepsilon$-relative-optimal when its worst-message success is at least $(1-\varepsilon)t_*$.

\subsection{Ignoring weak forward distinguishability}
Choose the same forward input for every decoder branch and implement the zero-diameter construction from Section~\ref{sec:zero}. This works for every actual forward channel and achieves
\begin{equation}
 S_{\mathrm{ignore}}=\frac{2A}{M}\label{eq:ignore}
\end{equation}
with support one for even $M$, and support two and entropy $\hbin(1/M)$ for odd $M$. Its absolute and relative losses are exactly
\begin{equation}
 t_*-S_{\mathrm{ignore}}=\frac{2A(M-2)k\delta}{MD},\qquad
 1-\frac{S_{\mathrm{ignore}}}{t_*}=\frac{(M-2)k\delta}{M}.\label{eq:zeroloss}
\end{equation}
Hence it is $\varepsilon$-relative-optimal whenever $\delta\le\varepsilon M/[(M-2)k]$. If the right side is at least one, the condition holds for every diameter. This is an achievable resource saving, not an optimal approximate-entropy formula.

\subsection{Replacing a triangle by a singleton near unit diameter}
Let $M=2r+1$ be odd. Use $r$ disjoint pair seeds, each of probability $2/M$, and one singleton seed of probability $1/M$. All preparations use a diameter-attaining pair. Pair seeds use the constant active effects and $H_-$ elsewhere. In the singleton seed use an effect $H_+$ attaining $\Tr(H_+\Delta)=\delta$ at its one active label and $H_-$ at all others.

Every message has averaged normalizer $D/M$. Pair-covered messages have correct weight $2A/M$, while the singleton message has $(1+k\delta)/M$. The worst-message success is therefore
\begin{equation}
 S_{\mathrm{single}}=\frac{1+k\delta}{D},\qquad
 t_*-S_{\mathrm{single}}=\frac{k(1-\delta)}D,\qquad
 1-\frac{S_{\mathrm{single}}}{t_*}=\frac{k(1-\delta)}{1+k}.\label{eq:singletonloss}
\end{equation}
This code has support $(M+1)/2$ and entropy $\log_2M-1+1/M$, saving one seed value and $2/M$ entropy bits relative to exact interior attainment. It is $\varepsilon$-relative-optimal whenever $k(1-\delta)/(1+k)\le\varepsilon$. Reweighting its seeds can improve performance; \eqref{eq:singletonloss} is the value of the stated construction, not the general fixed-support optimum.

\begin{figure}[t]
\centering
% BEGIN GENERATED ANALYTIC FIGURE
\setlength{\unitlength}{1pt}
\begin{picture}(435,205)
\small
\linethickness{0.4pt}
\put(50,40){\line(1,0){330}}
\put(50,40){\line(0,1){145}}
\put(50.000,40){\line(0,-1){3}}
\put(38.000,25){\makebox(24,10){0.0}}
\put(116.000,40){\line(0,-1){3}}
\put(104.000,25){\makebox(24,10){0.2}}
\put(182.000,40){\line(0,-1){3}}
\put(170.000,25){\makebox(24,10){0.4}}
\put(248.000,40){\line(0,-1){3}}
\put(236.000,25){\makebox(24,10){0.6}}
\put(314.000,40){\line(0,-1){3}}
\put(302.000,25){\makebox(24,10){0.8}}
\put(380.000,40){\line(0,-1){3}}
\put(368.000,25){\makebox(24,10){1.0}}
\put(50,53.182){\line(-1,0){3}}
\put(18,48.182){\makebox(26,10)[r]{0.2}}
\put(50,79.545){\line(-1,0){3}}
\put(18,74.545){\makebox(26,10)[r]{0.3}}
\put(50,105.909){\line(-1,0){3}}
\put(18,100.909){\makebox(26,10)[r]{0.4}}
\put(50,132.273){\line(-1,0){3}}
\put(18,127.273){\makebox(26,10)[r]{0.5}}
\put(50,158.636){\line(-1,0){3}}
\put(18,153.636){\makebox(26,10)[r]{0.6}}
\put(50,185.000){\line(-1,0){3}}
\put(18,180.000){\makebox(26,10)[r]{0.7}}
\put(179,5){\makebox(100,12){Forward diameter $\delta$}}
\put(17,189){\makebox(60,12)[l]{Success}}
\linethickness{0.9pt}
\qbezier(50.000,95.364)(51.375,95.554)(52.750,95.745)
\qbezier(52.750,95.745)(54.125,95.937)(55.500,96.129)
\qbezier(55.500,96.129)(56.875,96.323)(58.250,96.516)
\qbezier(58.250,96.516)(59.625,96.712)(61.000,96.907)
\qbezier(61.000,96.907)(62.375,97.104)(63.750,97.301)
\qbezier(63.750,97.301)(65.125,97.499)(66.500,97.697)
\qbezier(66.500,97.697)(67.875,97.898)(69.250,98.098)
\qbezier(69.250,98.098)(70.625,98.299)(72.000,98.501)
\qbezier(72.000,98.501)(73.375,98.705)(74.750,98.908)
\qbezier(74.750,98.908)(76.125,99.113)(77.500,99.318)
\qbezier(77.500,99.318)(78.875,99.525)(80.250,99.732)
\qbezier(80.250,99.732)(81.625,99.940)(83.000,100.149)
\qbezier(83.000,100.149)(84.375,100.359)(85.750,100.570)
\qbezier(85.750,100.570)(87.125,100.782)(88.500,100.994)
\qbezier(88.500,100.994)(89.875,101.208)(91.250,101.422)
\qbezier(91.250,101.422)(92.625,101.637)(94.000,101.853)
\qbezier(94.000,101.853)(95.375,102.071)(96.750,102.288)
\qbezier(96.750,102.288)(98.125,102.508)(99.500,102.727)
\qbezier(99.500,102.727)(100.875,102.949)(102.250,103.170)
\qbezier(102.250,103.170)(103.625,103.393)(105.000,103.617)
\qbezier(105.000,103.617)(106.375,103.842)(107.750,104.067)
\qbezier(107.750,104.067)(109.125,104.294)(110.500,104.522)
\qbezier(110.500,104.522)(111.875,104.751)(113.250,104.980)
\qbezier(113.250,104.980)(114.625,105.211)(116.000,105.442)
\qbezier(116.000,105.442)(117.375,105.676)(118.750,105.909)
\qbezier(118.750,105.909)(120.125,106.144)(121.500,106.380)
\qbezier(121.500,106.380)(122.875,106.617)(124.250,106.855)
\qbezier(124.250,106.855)(125.625,107.095)(127.000,107.334)
\qbezier(127.000,107.334)(128.375,107.576)(129.750,107.818)
\qbezier(129.750,107.818)(131.125,108.062)(132.500,108.306)
\qbezier(132.500,108.306)(133.875,108.552)(135.250,108.798)
\qbezier(135.250,108.798)(136.625,109.047)(138.000,109.295)
\qbezier(138.000,109.295)(139.375,109.546)(140.750,109.797)
\qbezier(140.750,109.797)(142.125,110.050)(143.500,110.303)
\qbezier(143.500,110.303)(144.875,110.558)(146.250,110.814)
\qbezier(146.250,110.814)(147.625,111.072)(149.000,111.330)
\qbezier(149.000,111.330)(150.375,111.590)(151.750,111.850)
\qbezier(151.750,111.850)(153.125,112.113)(154.500,112.376)
\qbezier(154.500,112.376)(155.875,112.641)(157.250,112.906)
\qbezier(157.250,112.906)(158.625,113.174)(160.000,113.442)
\qbezier(160.000,113.442)(161.375,113.712)(162.750,113.982)
\qbezier(162.750,113.982)(164.125,114.255)(165.500,114.528)
\qbezier(165.500,114.528)(166.875,114.804)(168.250,115.079)
\qbezier(168.250,115.079)(169.625,115.357)(171.000,115.635)
\qbezier(171.000,115.635)(172.375,115.916)(173.750,116.197)
\qbezier(173.750,116.197)(175.125,116.481)(176.500,116.765)
\qbezier(176.500,116.765)(177.875,117.051)(179.250,117.338)
\qbezier(179.250,117.338)(180.625,117.627)(182.000,117.916)
\qbezier(182.000,117.916)(183.375,118.208)(184.750,118.501)
\qbezier(184.750,118.501)(186.125,118.796)(187.500,119.091)
\qbezier(187.500,119.091)(188.875,119.389)(190.250,119.687)
\qbezier(190.250,119.687)(191.625,119.988)(193.000,120.289)
\qbezier(193.000,120.289)(194.375,120.593)(195.750,120.898)
\qbezier(195.750,120.898)(197.125,121.205)(198.500,121.512)
\qbezier(198.500,121.512)(199.875,121.822)(201.250,122.133)
\qbezier(201.250,122.133)(202.625,122.446)(204.000,122.760)
\qbezier(204.000,122.760)(205.375,123.077)(206.750,123.394)
\qbezier(206.750,123.394)(208.125,123.714)(209.500,124.034)
\qbezier(209.500,124.034)(210.875,124.358)(212.250,124.681)
\qbezier(212.250,124.681)(213.625,125.008)(215.000,125.335)
\qbezier(215.000,125.335)(216.375,125.665)(217.750,125.996)
\qbezier(217.750,125.996)(219.125,126.330)(220.500,126.663)
\qbezier(220.500,126.663)(221.875,127.001)(223.250,127.338)
\qbezier(223.250,127.338)(224.625,127.679)(226.000,128.021)
\qbezier(226.000,128.021)(227.375,128.365)(228.750,128.710)
\qbezier(228.750,128.710)(230.125,129.059)(231.500,129.407)
\qbezier(231.500,129.407)(232.875,129.759)(234.250,130.112)
\qbezier(234.250,130.112)(235.625,130.468)(237.000,130.824)
\qbezier(237.000,130.824)(238.375,131.184)(239.750,131.544)
\qbezier(239.750,131.544)(241.125,131.909)(242.500,132.273)
\qbezier(242.500,132.273)(243.875,132.641)(245.250,133.009)
\qbezier(245.250,133.009)(246.625,133.381)(248.000,133.754)
\qbezier(248.000,133.754)(249.375,134.130)(250.750,134.507)
\qbezier(250.750,134.507)(252.125,134.888)(253.500,135.269)
\qbezier(253.500,135.269)(254.875,135.654)(256.250,136.039)
\qbezier(256.250,136.039)(257.625,136.429)(259.000,136.818)
\qbezier(259.000,136.818)(260.375,137.212)(261.750,137.606)
\qbezier(261.750,137.606)(263.125,138.005)(264.500,138.404)
\qbezier(264.500,138.404)(265.875,138.807)(267.250,139.211)
\qbezier(267.250,139.211)(268.625,139.619)(270.000,140.027)
\qbezier(270.000,140.027)(271.375,140.440)(272.750,140.853)
\qbezier(272.750,140.853)(274.125,141.270)(275.500,141.688)
\qbezier(275.500,141.688)(276.875,142.111)(278.250,142.534)
\qbezier(278.250,142.534)(279.625,142.962)(281.000,143.390)
\qbezier(281.000,143.390)(282.375,143.823)(283.750,144.256)
\qbezier(283.750,144.256)(285.125,144.695)(286.500,145.133)
\qbezier(286.500,145.133)(287.875,145.577)(289.250,146.021)
\qbezier(289.250,146.021)(290.625,146.470)(292.000,146.919)
\qbezier(292.000,146.919)(293.375,147.374)(294.750,147.829)
\qbezier(294.750,147.829)(296.125,148.289)(297.500,148.750)
\qbezier(297.500,148.750)(298.875,149.216)(300.250,149.683)
\qbezier(300.250,149.683)(301.625,150.155)(303.000,150.627)
\qbezier(303.000,150.627)(304.375,151.105)(305.750,151.584)
\qbezier(305.750,151.584)(307.125,152.068)(308.500,152.552)
\qbezier(308.500,152.552)(309.875,153.043)(311.250,153.534)
\qbezier(311.250,153.534)(312.625,154.031)(314.000,154.528)
\qbezier(314.000,154.528)(315.375,155.031)(316.750,155.535)
\qbezier(316.750,155.535)(318.125,156.045)(319.500,156.555)
\qbezier(319.500,156.555)(320.875,157.072)(322.250,157.589)
\qbezier(322.250,157.589)(323.625,158.113)(325.000,158.636)
\qbezier(325.000,158.636)(326.375,159.167)(327.750,159.698)
\qbezier(327.750,159.698)(329.125,160.236)(330.500,160.774)
\qbezier(330.500,160.774)(331.875,161.319)(333.250,161.865)
\qbezier(333.250,161.865)(334.625,162.417)(336.000,162.970)
\qbezier(336.000,162.970)(337.375,163.531)(338.750,164.091)
\qbezier(338.750,164.091)(340.125,164.659)(341.500,165.227)
\qbezier(341.500,165.227)(342.875,165.803)(344.250,166.380)
\qbezier(344.250,166.380)(345.625,166.964)(347.000,167.548)
\qbezier(347.000,167.548)(348.375,168.141)(349.750,168.733)
\qbezier(349.750,168.733)(351.125,169.334)(352.500,169.935)
\qbezier(352.500,169.935)(353.875,170.545)(355.250,171.154)
\qbezier(355.250,171.154)(356.625,171.773)(358.000,172.391)
\qbezier(358.000,172.391)(359.375,173.019)(360.750,173.646)
\qbezier(360.750,173.646)(362.125,174.283)(363.500,174.920)
\qbezier(363.500,174.920)(364.875,175.566)(366.250,176.212)
\qbezier(366.250,176.212)(367.625,176.868)(369.000,177.524)
\qbezier(369.000,177.524)(370.375,178.189)(371.750,178.855)
\qbezier(371.750,178.855)(373.125,179.531)(374.500,180.207)
\qbezier(374.500,180.207)(375.875,180.893)(377.250,181.579)
\qbezier(377.250,181.579)(378.625,182.275)(380.000,182.972)
\linethickness{0.6pt}
\qbezier(50.000,53.182)(51.375,53.464)(52.750,53.747)
\qbezier(52.750,53.747)(54.125,54.031)(55.500,54.316)
\qbezier(58.250,54.890)(59.625,55.179)(61.000,55.468)
\qbezier(61.000,55.468)(62.375,55.760)(63.750,56.051)
\qbezier(66.500,56.639)(67.875,56.936)(69.250,57.232)
\qbezier(69.250,57.232)(70.625,57.531)(72.000,57.830)
\qbezier(74.750,58.433)(76.125,58.737)(77.500,59.040)
\qbezier(77.500,59.040)(78.875,59.347)(80.250,59.653)
\qbezier(83.000,60.271)(84.375,60.583)(85.750,60.894)
\qbezier(85.750,60.894)(87.125,61.209)(88.500,61.523)
\qbezier(91.250,62.157)(92.625,62.476)(94.000,62.796)
\qbezier(94.000,62.796)(95.375,63.118)(96.750,63.441)
\qbezier(99.500,64.091)(100.875,64.419)(102.250,64.747)
\qbezier(102.250,64.747)(103.625,65.078)(105.000,65.408)
\qbezier(107.750,66.076)(109.125,66.412)(110.500,66.749)
\qbezier(110.500,66.749)(111.875,67.089)(113.250,67.428)
\qbezier(116.000,68.113)(117.375,68.459)(118.750,68.805)
\qbezier(118.750,68.805)(120.125,69.153)(121.500,69.502)
\qbezier(124.250,70.206)(125.625,70.561)(127.000,70.916)
\qbezier(127.000,70.916)(128.375,71.274)(129.750,71.632)
\qbezier(132.500,72.355)(133.875,72.720)(135.250,73.085)
\qbezier(135.250,73.085)(136.625,73.453)(138.000,73.821)
\qbezier(140.750,74.564)(142.125,74.939)(143.500,75.314)
\qbezier(143.500,75.314)(144.875,75.693)(146.250,76.071)
\qbezier(149.000,76.835)(150.375,77.221)(151.750,77.606)
\qbezier(151.750,77.606)(153.125,77.996)(154.500,78.385)
\qbezier(157.250,79.171)(158.625,79.567)(160.000,79.964)
\qbezier(160.000,79.964)(161.375,80.364)(162.750,80.765)
\qbezier(165.500,81.573)(166.875,81.982)(168.250,82.390)
\qbezier(168.250,82.390)(169.625,82.802)(171.000,83.214)
\qbezier(173.750,84.047)(175.125,84.467)(176.500,84.887)
\qbezier(176.500,84.887)(177.875,85.312)(179.250,85.736)
\qbezier(182.000,86.593)(183.375,87.026)(184.750,87.459)
\qbezier(184.750,87.459)(186.125,87.896)(187.500,88.333)
\qbezier(190.250,89.217)(191.625,89.663)(193.000,90.109)
\qbezier(193.000,90.109)(194.375,90.559)(195.750,91.010)
\qbezier(198.500,91.920)(199.875,92.380)(201.250,92.840)
\qbezier(201.250,92.840)(202.625,93.305)(204.000,93.769)
\qbezier(206.750,94.708)(208.125,95.182)(209.500,95.657)
\qbezier(209.500,95.657)(210.875,96.136)(212.250,96.615)
\qbezier(215.000,97.584)(216.375,98.073)(217.750,98.563)
\qbezier(217.750,98.563)(219.125,99.057)(220.500,99.552)
\qbezier(223.250,100.552)(224.625,101.057)(226.000,101.562)
\qbezier(226.000,101.562)(227.375,102.073)(228.750,102.584)
\qbezier(231.500,103.617)(232.875,104.139)(234.250,104.661)
\qbezier(234.250,104.661)(235.625,105.188)(237.000,105.716)
\qbezier(239.750,106.783)(241.125,107.322)(242.500,107.862)
\qbezier(242.500,107.862)(243.875,108.407)(245.250,108.953)
\qbezier(248.000,110.056)(249.375,110.614)(250.750,111.172)
\qbezier(250.750,111.172)(252.125,111.736)(253.500,112.300)
\qbezier(256.250,113.442)(257.625,114.019)(259.000,114.596)
\qbezier(259.000,114.596)(260.375,115.180)(261.750,115.764)
\qbezier(264.500,116.945)(265.875,117.543)(267.250,118.140)
\qbezier(267.250,118.140)(268.625,118.745)(270.000,119.349)
\qbezier(272.750,120.573)(274.125,121.192)(275.500,121.811)
\qbezier(275.500,121.811)(276.875,122.437)(278.250,123.064)
\qbezier(281.000,124.332)(282.375,124.974)(283.750,125.615)
\qbezier(283.750,125.615)(285.125,126.265)(286.500,126.914)
\qbezier(289.250,128.229)(290.625,128.895)(292.000,129.560)
\qbezier(292.000,129.560)(293.375,130.234)(294.750,130.908)
\qbezier(297.500,132.273)(298.875,132.964)(300.250,133.654)
\qbezier(300.250,133.654)(301.625,134.354)(303.000,135.054)
\qbezier(305.750,136.471)(307.125,137.188)(308.500,137.906)
\qbezier(308.500,137.906)(309.875,138.633)(311.250,139.360)
\qbezier(314.000,140.832)(315.375,141.578)(316.750,142.324)
\qbezier(316.750,142.324)(318.125,143.080)(319.500,143.836)
\qbezier(322.250,145.367)(323.625,146.143)(325.000,146.919)
\qbezier(325.000,146.919)(326.375,147.706)(327.750,148.492)
\qbezier(330.500,150.086)(331.875,150.894)(333.250,151.702)
\qbezier(333.250,151.702)(334.625,152.521)(336.000,153.340)
\qbezier(338.750,155.000)(340.125,155.842)(341.500,156.684)
\qbezier(341.500,156.684)(342.875,157.537)(344.250,158.391)
\qbezier(347.000,160.122)(348.375,160.999)(349.750,161.877)
\qbezier(349.750,161.877)(351.125,162.768)(352.500,163.658)
\qbezier(355.250,165.464)(356.625,166.381)(358.000,167.297)
\qbezier(358.000,167.297)(359.375,168.227)(360.750,169.156)
\qbezier(363.500,171.043)(364.875,172.000)(366.250,172.957)
\qbezier(366.250,172.957)(367.625,173.929)(369.000,174.900)
\qbezier(371.750,176.873)(373.125,177.874)(374.500,178.875)
\qbezier(374.500,178.875)(375.875,179.892)(377.250,180.908)
\linethickness{0.5pt}
\multiput(50,95.364)(12,0){27}{\line(1,0){7}}
\linethickness{0.9pt}
\put(73,172){\line(1,0){23}}
\put(103,167){\makebox(180,10)[l]{Unrestricted optimum}}
\linethickness{0.6pt}
\multiput(73,156)(6,0){4}{\line(1,0){4}}
\put(103,151){\makebox(200,10)[l]{Pair plus singleton construction}}
\linethickness{0.5pt}
\multiput(73,140)(12,0){2}{\line(1,0){7}}
\put(103,135){\makebox(200,10)[l]{Ignore the forward channel}}
\end{picture}
% END GENERATED ANALYTIC FIGURE
\caption{Analytically evaluated success for $M=5$ and $p=1/10$. The unrestricted optimum needs four seed values at every interior diameter for qubit output. Ignoring the forward channel uses two seed values; the fixed-weight pair-plus-singleton construction uses three. They approach the optimum at opposite endpoints. The curves are attaining constructions, not upper bounds for the full two- or three-seed optimization.}\label{fig:approx}
\end{figure}

\subsection{A strict gap below the exact support threshold}
\begin{proposition}\label{prop:compact}
Fix finite input and output dimensions, $0<p<1/2$, a forward channel, and an integer $K$. The maximum raw success over protocols with at most $K$ seed values is attained. Consequently, whenever Theorem~\ref{thm:cost} gives $K<K_*$, that maximum is strictly below $t_*$.
\end{proposition}
\begin{proof}
Allow exactly $K$ indexed seed slots, including zero-probability slots. The seed simplex, decoder block sets, and effect intervals are compact in finite-dimensional spaces. Their product is compact. Equation~\eqref{eq:normalizer} bounds every averaged denominator below by $2p$, so the worst-message success is continuous. Its maximum is attained. If that maximum equaled $t_*$ with $K<K_*$, it would contradict the definition and value of $K_*$.
\end{proof}
This argument gives a strictly positive gap for each fixed channel and insufficient $K$, but neither its magnitude nor a uniform lower bound as the channel approaches an endpoint. Figure~\ref{fig:approx} explains why such endpoint limits need care.

\section{An exact two seed classical benchmark}\label{sec:finiteK}
The complete fixed-seed performance frontier is not determined by Theorem~\ref{thm:cost}. A finite certificate calculation gives one nontrivial subthreshold value. This section concerns a \emph{classical} forward binary symmetric channel only; it does not assert equality with a two-seed qubit protocol.

\begin{theorem}[Computer-assisted classical benchmark]\label{thm:finiteK}
For three messages, backward and forward crossover probabilities $p=q=1/10$, and at most two raw seed values, the exact classical optimum is
\begin{equation}
 T_2=\frac{3895-\sqrt{1237585}}{3776}
 =0.7368993704800834\ldots.\label{eq:T2}
\end{equation}
Here $\delta=1-2q=4/5$. The unrestricted value is $45/59$, approximately $0.7627118644$, and requires three seed values. The absolute loss is approximately $0.02581249393$.
\end{theorem}
\begin{proof}[Proof and exact certificate specification]
For a fixed decoder, raw seed law, and target $t$, each inequality $\overline w_m(m)-t\overline Z_m\ge0$ is linear in each encoder response coordinate. A response for one message appears in no other message's inequality. Maximizing each coordinate's contribution independently therefore yields deterministic encoders without increasing the seed support. There are four deterministic functions $a(c)$ of the received forward bit $c$. Encode a function by $2a(0)+a(1)$, so the four types are constant zero, identity, bit flip, and constant one. A seed has $4^3=64$ profiles, and seed exchange leaves $64\cdot65/2=2080$ unordered profile pairs to consider, including identical profiles and zero-probability seeds.

For a profile pair $P_s$, set
\[
 x_{sbyd}=\pi_sD_s(y,d\mid b)\ge0,\qquad
 W_{smbd}=\sum_cN_q(c\mid d)N_p(b\mid a_{sm}(c)).
\]
The decoder constraints are $\sum_{y,d}x_{s0yd}=\sum_{y,d}x_{s1yd}=\pi_s$ and $\sum_s\pi_s=1$. Correct weights and normalizers are
\[
 C_m=\sum_{s,b,d}x_{sbmd}W_{smbd},\qquad
 Z_m=\sum_{s,b,y,d}x_{sbyd}W_{smbd}.
\]
For nonnegative multipliers $\mu_m$ summing to one, define
\begin{equation}
 g_{sbyd}=\sum_m\mu_m(t-\mathbf1_{y=m})W_{smbd}.\label{eq:certg}
\end{equation}
Every allowed decoder obeys
\begin{equation}
 \sum_m\mu_m(tZ_m-C_m)
 \ge\min_s\left[\min_{y,d}g_{s0yd}+\min_{y,d}g_{s1yd}\right].\label{eq:certbound}
\end{equation}
A strictly positive right side rules out target $t$ for those profiles. A nonnegative bound with strictly positive $\mu_m$ rules out success strictly greater than $t$ for every message.

For achievability take
\begin{equation}
 x=\frac{1271-\sqrt{1237585}}{256},\qquad y=1-x.\label{eq:xy}
\end{equation}
Both probabilities are positive. Seed one is a pair on messages $0,2$, with profile $(0,1,3)$: it outputs message zero and forward bit one at $b=0$, and message two and forward bit zero at $b=1$. Seed two is a singleton on message one with profile $(1,2,1)$, preparing forward bit one at $b=0$ and bit zero at $b=1$. Put $b_*=k\delta=16/25$ and $\ell_*=1-b_*=9/25$. The pair-message and singleton-message successes are respectively
\begin{equation}
 \frac{Ax}{\ell_*+b_*x},\qquad
 \frac{(1+b_*)y}{\ell_*+2b_*y},\label{eq:finiteattain}
\end{equation}
both equal to \eqref{eq:T2}. Equivalently, $T_2$ is the smaller root of $1888T_2^2-3895T_2+1845=0$.

For the winning profile pair, choose $t=T_2$ and $\mu=(x/2,y,x/2)$. Exact arithmetic in $\mathbb Q(\sqrt{1237585})$ verifies $g_{sbyd}\ge0$ for every index, giving the matching upper bound. Simultaneous forward-bit relabeling, simultaneous backward-bit relabeling, global message permutation, and seed exchange preserve the problem. Forward and backward relabelings can be chosen independently in each seed. Explicitly enumerating the winning orbit yields 24 profile pairs. For each of the other 2056 pairs, the companion certificate file gives rational $\mu$ for which \eqref{eq:certbound} is strictly positive at $t_0=7368993/10000000<T_2$.

The standalone verifier reconstructs all 2080 pairs, the 24-element orbit, and every coefficient in \eqref{eq:certg}. It checks the exact winning construction and upper bound, positivity of the probabilities, and all 2056 rational exclusions, with no floating-point operations or optimization solver. Complete coverage therefore proves the global classical bound; numerical optimization was used only to discover certificates.
\end{proof}

\section{Relation to previous work and remaining questions}\label{sec:discussion}
Theorem~\ref{thm:cost} addresses the raw common seed required to attain a performance optimum, not exact synthesis of a prescribed joint distribution. Minimum entropy of a shared variable is already a standard resource in exact common information: Kumar, Li, and El Gamal minimize $H(W)$ subject to a fixed law and conditional independence \cite{KLE}. Their setting also distinguishes entropy from expected description length. Applying such a theorem here would require a fixed-target-law and cost-preserving reduction, including the message-dependent normalization. None is assumed.

Similarly, Ji, Lloyd, and Wilde's normalized retrocausal framework includes shared randomness and forward registers beyond the fixed carrier allowed here \cite{JLW}. Their general noisy-memory rate tradeoff is not solved by a one-use seed-cost theorem. Ji, Regula, and Wilde already use a worst-message ratio of correct conclusive weight to total conclusive weight in postselected communication \cite{JRW}; the present contribution is not the conditional error criterion. A postselected simulation alone does not establish a resource-preserving equivalence to their entanglement- or nonsignalling-assisted optimizations.

The earlier seedless result \cite{PyleSeedless} is also a different resource problem. Under matched binary symmetric and depolarizing memories, three messages have equal classical and quantum seedless optima, while a rational four-message qubit protocol can exceed a universal classical ceiling of $1/2$. Adding raw seed assistance equalizes their unrestricted optima through their matched diameter, but Theorem~\ref{thm:finiteK} does not equalize their subthreshold finite-seed curves. If success is required for every supported seed, the optimum equals the seedless minimax exactly: each branch is an admissible seedless protocol, and a one-valued seed attains that optimum. Thus no advantage follows from common randomness under a worst-seed requirement.

Several questions remain open in this work. The full function of allowed support $K$ is unknown even for matched bit and qubit memories; the exact benchmark in Section~\ref{sec:finiteK} is one classical instance. The minimum entropy at a prescribed suboptimal success is also unknown. In higher dimension, a channel invariant richer than diameter may be needed to characterize exact seed resources. Asymmetric backward channels, larger backward alphabets, and multiple uses require separate equality analyses. Finally, changing the order of mixing and normalization changes the optimization and cannot be handled by silently reusing these seed-cost formulas.

The model assumes a backward channel and studies coding and resources conditional on that assumption. It supplies no mechanism for creating such a channel. In particular, correlations obtained by postselection do not, by themselves, provide an earlier readable record of a freely chosen later message. Physical implementation would require a separate model and evidence absent from this paper.

\section{Computational verification and provenance}\label{sec:repro}
The analytic statements in Sections~\ref{sec:model}--\ref{sec:approx} are proved above. Computations supplement their proofs: the main suite checks 1434 exact-rational construction identities and 114 floating-point entropy values, and samples 1000 fractional-matching vertices using linear objectives; a separately implemented suite checks 672 rational construction cases and 16 direct erasure-channel contractions. These counts describe distinct cases within the named suites, not independent discoveries or accumulated rerun counts. The vertex sampling is a numerical consistency test, not a proof of the graph theorem.

Section~\ref{sec:finiteK} is explicitly computer-assisted. Its upper bound uses a complete finite set of exact certificates, not sampled protocols or an optimizer's convergence claim. The reader-facing archive includes the certificate specification, complete machine-readable certificate data, a solver-free verifier using integer and rational quadratic-field arithmetic, and optional numerical discovery scripts. A fresh verification run and its environment record accompany the archive.

\paragraph{Availability and version history}
Verification code and complete certificates are supplied in the companion archive \texttt{seed\_cost\_reproducibility.zip}; editable manuscript source is supplied separately. The project repository, \url{https://github.com/dapyle11/normalized-loop-memory}, hosts related earlier material, including the raw-seed reproducibility archive identified in \cite{PyleRaw}. The earlier submitted files are preserved unchanged.

\paragraph{AI assistance and review status}
Lyra, an OpenAI AI assistant, performed technical derivation, proof checking, code development and verification, bounded literature screening, and manuscript drafting in an AI-assisted workflow directed by Daniel A. Pyle. Separate AI checking passes were used; they are not independent human peer review. The assistant is disclosed as a tool, not a coauthor. Independent human review of the model, proofs, computer-assisted certificates, bibliography, and originality remains pending.

\begin{thebibliography}{10}
\raggedright
\bibitem{PyleRaw}
D. A. Pyle, ``Shared randomness and normalization in one-use loop communication,'' unpublished research manuscript, 30 October 2026. Earlier computational material: \url{https://github.com/dapyle11/normalized-loop-memory}, archive \texttt{shared\_seed\_loop\_reproducibility (1).zip}.

\bibitem{PyleSeedless}
D. A. Pyle, ``Finite alphabet communication with noisy forward memory in a normalized loop,'' unpublished research manuscript, 30 October 2026. Related materials: \url{https://github.com/dapyle11/normalized-loop-memory}.

\bibitem{JLW}
K. Ji, S. Lloyd, and M. M. Wilde, ``Retrocausal capacity of a quantum channel: Communicating through noisy closed timelike curves,'' \emph{Physical Review Letters} \textbf{136}, 230801 (2026). \href{https://doi.org/10.1103/znyd-npk5}{doi:10.1103/znyd-npk5}. \href{https://arxiv.org/abs/2509.08965v3}{arXiv:2509.08965v3}.

\bibitem{JRW}
K. Ji, B. Regula, and M. M. Wilde, ``Postselected communication over quantum channels,'' \emph{International Journal of Quantum Information} \textbf{22}(5), 2440012 (2024). \href{https://doi.org/10.1142/S0219749924400124}{doi:10.1142/S0219749924400124}. \href{https://arxiv.org/abs/2308.02583v3}{arXiv:2308.02583v3}.

\bibitem{FMS}
O. Fawzi, A. M\"uller-Hermes, and A. Shayeghi, ``A lower bound on the space overhead of fault-tolerant quantum computation,'' in \emph{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, LIPIcs \textbf{215}, 68:1--68:20 (2022). \href{https://doi.org/10.4230/LIPIcs.ITCS.2022.68}{doi:10.4230/LIPIcs.ITCS.2022.68}.

\bibitem{HR}
F. Hiai and M. B. Ruskai, ``Contraction coefficients for noisy quantum channels,'' \emph{Journal of Mathematical Physics} \textbf{57}(1), 015211 (2016). \href{https://doi.org/10.1063/1.4936215}{doi:10.1063/1.4936215}.

\bibitem{Behrend}
R. E. Behrend, ``Fractional perfect $b$-matching polytopes. I: General theory,'' arXiv:1301.7356 (2013), especially Section 7, Theorem 22. \url{https://arxiv.org/abs/1301.7356}.

\bibitem{KLE}
G. R. Kumar, C. T. Li, and A. El Gamal, ``Exact common information,'' arXiv:1402.0062 (2014), especially Sections II and V. \url{https://arxiv.org/abs/1402.0062}.
\end{thebibliography}
\end{document}