List-Decoding Capacity of the Gaussian Arbitrarily-Varying Channel ^†

Abstract

In this paper, we determine the capacity of the Gaussian arbitrarily-varying channel with a (possibly stochastic) encoder and a deterministic list-decoder under the average probability of error criterion. We assume that both the legitimate and the adversarial signals are restricted by their power constraints. We also assume that there is no path between the adversary and the legitimate user but the adversary knows the legitimate user’s code. We show that for any list size L, the capacity is equivalent to the capacity of a point-to-point Gaussian channel with noise variance increased by the adversary power, if the adversary has less power than L times the transmitter power; otherwise, the capacity is zero. In the converse proof, we show that if the adversary has enough power, then the decoder can be confounded by the adversarial superposition of several codewords while satisfying its power constraint with positive probability. The achievability proof benefits from a novel variant of the Csiszár-Narayan method for the arbitrarily-varying channel.

1. Introduction

An arbitrarily-varying channel (AVC) represents a memoryless channel including unknown parameters that are changing arbitrarily from channel use to channel use. Because these parameters (state) can change arbitrarily, we consider this to be a model for an active adversarial jammer. This adversary sends its signal to restrain the legitimate transmitter and receiver from maintaining reliable communication. In wireless channels, these unpleasant adversaries can easily enter channels, so it is of great importance to study the adversary’s effect on the channel capacity. The capacity of the AVC depends on the coding method (such as randomized coding, stochastic encoder or deterministic coding), the performance criterion (such as average or maximum error probability) and the amount of adversary’s knowledge about the transmitted signal (omniscient, myopic or oblivious adversary).

Table 1. References’ Summary.

Reference	Discrete/Gaussian	Shared Randomness	Cost Constraints	Max/Avg	List Decoding	Adversarial Model	Capacity or Notes
[1]	Discrete	✓	✗	Avg	✗	Oblivious	Blackwell et al. introduced AVC.
[3]	Discrete	✓	✗	Max and Avg	✗	Oblivious	Capacity remains the same for Max. error Probability.
[4]	Discrete	✗	✗	Max and Avg	✗	Oblivious	Studied deterministic capacity in a dichotomy theorem.
[5]	Discrete	✓	✗	Avg	✗	Oblivious	Found the necessary condition for the positive deterministic capacity by defining symmetrizability.
[6]	Discrete	✗	✓	Avg	✗	Oblivious	$\left\{\begin{array}{cccc}{\displaystyle \underset{\begin{array}{c}P:g\left(P\right)\le \Gamma \\ {\mathsf{\Lambda }}_0\left(P\right)\ge \mathsf{\Lambda }\end{array}}{max}}& {\displaystyle \underset{\begin{array}{c}Y:P_{YXS}\in {\mathcal{C}}_0\mathrm{for}\\ \mathrm{some}S,\mathrm{with}P\left(X\right)=P\end{array}}{min}}& I(X;Y),& {\displaystyle \underset{P:g\left(P\right)\le \Gamma }{max}}{\mathsf{\Lambda }}_0\left(P\right)>\mathsf{\Lambda }\\ 0,& & & {\displaystyle \underset{P:g\left(P\right)\le \Gamma }{max}}{\mathsf{\Lambda }}_0\left(P\right)<\mathsf{\Lambda }.\end{array}\right.$
[6]	Discrete	✗	✗	Avg	✗	Oblivious	${\displaystyle \underset{P}{max}}{\displaystyle \underset{\begin{array}{c}Y:P_{YXS}\in {\mathcal{C}}_0\mathrm{for}\\ \mathrm{some}S,\mathrm{with}P\left(X\right)=P\end{array}}{min}}I(X;Y)$ if and only if $C>0$
[7]	Discrete	✓	✓	Avg	✗	Oblivious	${\displaystyle \underset{X:\mathbb{E}g\left(X\right)\le \Gamma }{max}}{\displaystyle \underset{S:\mathbb{E}S\le \mathsf{\Lambda }}{min}}I(X;Y_{X,S})$
[8]	Discrete	✗	✓	Avg	✗	Oblivious	Capacity with general alphabets and states.
[9]	Discrete	✓	✗	Max	✗	Myopic	${\displaystyle \underset{P\left(x\right)}{max}}{\displaystyle \underset{V\in W}{min}}I(P,V)$ W is a set of transition matrices from X to Y
[10]	Discrete	✓	✓	Max	✗	Delay	${\displaystyle \underset{P\left(x\right)}{max}}{\displaystyle \underset{Q\in \mathcal{Q}}{min}}I(P,W_Q)$ $\mathcal{Q}$ is a set of transition matrices from X to Y
[11]	Discrete	✗	✓	Max and Avg	✗	Causal	Upper bounds on the capacity
[19]	Discrete	✗	✗	Avg	✓	Oblivious	$\left\{\begin{array}{cccc}{\displaystyle \underset{P}{max}}& {\displaystyle \underset{\begin{array}{c}{P}_{YXS}:P_{YXS}\in {\mathcal{C}}_0\mathrm{for}\\ \mathrm{some}S,\mathrm{with}P\left(X\right)=P\end{array}}{min}}& I(X;Y),& L>M\\ 0,& & & L\le M.\end{array}\right.$
[20]	Discrete	✓	✓	Max	✓	Oblivious	${\displaystyle \underset{P\in \mathcal{P}\left(\mathcal{X}\right)}{max}}{\displaystyle \underset{U\in \mathcal{U}(P,\mathsf{\Lambda })}{min}}I(P,\sum W(y,x,s)U\left(s\right|x))$
[20]	Discrete	✗	✓	Avg	✓	Oblivious	Upper and lower bounds on the capacity
[21]	Gaussian	✓	✓	Max	✗	Oblivious	$C\left(\frac{P}{\mathsf{\Lambda }+{\sigma }^2}\right)$
[22]	Gaussian	✗	✓	Avg	✗	Oblivious	$\left\{\begin{array}{cc}C\left(\frac{P}{\mathsf{\Lambda }+{\sigma }^2}\right),\hfill & P>\mathsf{\Lambda }\hfill \\ 0,\hfill & P\le \mathsf{\Lambda }.\hfill \end{array}\right.$
This Paper	Gaussian	✗	✓	Avg	✓	Oblivious	$\left\{\begin{array}{cc}C\left(\frac{P}{\mathsf{\Lambda }+{\sigma }^2}\right),\hfill & L>\frac{\mathsf{\Lambda }}{P}\hfill \\ 0,\hfill & L<\frac{\mathsf{\Lambda }}{P}.\hfill \end{array}\right.$

provides a summary of various models appearing in the literature, including the one considered here.

Blackwell et al. introduced AVC in Reference [1] and under the average error probability criterion they found the capacity of the discrete memoryless AVC to be given by a min-max expression over the mutual information of input and output. They employed randomized coding that is, common randomness between the encoder and the decoder and assumed the jammer to be oblivious that is, the jammer does not have any information about the transmitted signal except the code. In Reference [2], it is shown that the min-max expression is equivalent to the corresponding max-min one. Further, in Reference [3], the authors examined that this capacity remains the same even for the maximum error probability criterion, again provided access to common randomness. The case without common randomness between the transmitter and the receiver is referred to as the deterministic code setting. Ahlswede in a notable paper [4] characterized the deterministic capacity of a discrete AVC under the average probability of error through a dichotomy theorem. He proved that the capacity either corresponds to the AVC randomized code capacity or else it equals zero but he did not state any necessary or sufficient condition for which of the two cases prevails. Ericson, in Reference [5], found the necessary condition for the positive alternative by defining symmetrizability. A symmetrizable AVC is an AVC in which the adversary can mimic the transmitted signal in order to prevent the decoder from distinguishing between the true message and an adversarial imitation. Thus, he showed that if the deterministic code capacity of an AVC is positive then the channel should be nonsymmetrizable. Later, in Reference [6], a sufficient condition was provided by Csiszár and Narayen stating that if the AVC is nonsymmetrizable then the deterministic code capacity is not zero. Therefore, considering both conditions, the deterministic code capacity of an AVC is positive if and only if the channel is nonsymmetrizable.

The capacity of discrete AVC is also investigated under input and state (or adversarial signal) constraints. Restricted by peak or average input and state cost constraints, the random code capacity of discrete AVC is studied in Reference [7] using the average probability of error as the performance criterion. Furthermore, the second part of Csiszár and Narayan work in Reference [6] focuses on the deterministic code capacity of AVC under input and state constraints for the same performance criterion. They proved that in this case if the capacity is positive then it is less than or equal to the corresponding random code capacity. In particular, with input and state constraints, the capacity can be positive but strictly less than the random code capacity. Note that this does not occur without cost constraints. Csiszár, in Reference [8], extended this result to general input and output alphabets and state sets rather than only finite alphabets and state sets.

There is a wide variety of research on different versions of AVCs under various adversaries model, including References [9,10,11]. Sarwate, in [9], considered a myopic adversary in which there is a discrete memoryless channel (DMC) between the legitimate user and the jammer and the jammer chooses its signal based on this noisy version of the user’s codeword. He found the capacity by minimizing over all DMCs that the jammer can applied by its worst strategies. In Reference [10], single letter characterizations of capacity is obtained in the presence of a delayed adversary which can observe the transmitted signal after a delay. By assuming randomization at the encoder, the capacity is corresponding to the randomized code capacity. B. K. Dey et al., in Reference [11], obtained upper bounds on the capacity of binary channel in the presence of a causal adversary for both maximal and average error probabilities.

On the other hand, AVCs are also studied in network settings throughout [12,13,14,15,16,17,18], such as multiple-access and broadcast channels. The authors in Reference [12,13,14] investigated the capacity of arbitrarily varying multiple-access channels (AVMACs). In Reference [13], it is proved that symmetrizability, which is defined for the two-user AVC, is a sufficient condition for an AVMAC to have empty interior for its deterministic code capacity region. Moreover, throughout [15,16,17,18], the capacity of arbitrarily varying wiretap channels (AVWCs) are determined.

This paper focuses on the Gaussian AVC (GAVC), wherein all alphabets are continuous rather than discrete. Initially, Ahlswede, in Reference [23], studied the capacity of a GAVC in which the adversary chooses the noise variance rather than an additive signal. Hughes and Narayan in Reference [21] determined the randomized code capacity of GAVC under the peak power input and state constraints. They further extended their result in Reference [24] for a vector GAVC. The deterministic code capacity of the GAVC, for the average probability of error, was found in Reference [22]. The authors showed that if the adversary’s power is greater than the legitimate transmitter’s power, then symmetrizability occurs causing the capacity to drop to zero. Note that for a discrete AVC with no cost constraint non-symmetrizability makes the deterministic capacity positive and equal to the randomized capacity [6] (Theorem 1). It is further proved in [6] (Theorem 3) that under input and state cost constraints, non-symmetrizability only results in positive deterministic capacity but it is sometimes strictly less than the randomized capacity. In the Gaussian case, even though there are input and state cost constraints, the behavior is like that of a discrete AVC with no cost constraint, in that if the channel is non-symmetrizable, then its deterministic capacity is positive and equal to the randomized capacity [22].

For the first time, in Reference [19], Hughes showed that using list-decoding, in which the decoder can decode to a small (and bounded) list rather than a unique message estimate, causes positive capacity for most symmetrizable discrete-memoryless AVCs. Intuitively, list-decoding combats the symmetrizing attack by allowing the list to contain the true message as well as the counterfeit(s) generated by the adversary; thus, the receiver can successfully decode even if it cannot specify the correct message. Furthermore, the authors in Reference [20] extended the list-decoding result to the discrete-memoryless AVCs with state constraints. They determined upper and lower bounds on the capacity by introducing two notions of symmetrizability for this channel.

The capacity of AVMAC was also studied with list-decoding in References [25,26]. Sirin Nitinawarat in Reference [25] introduced symmetrizability of an AVMAC and showed that the capacity region for deterministic codes with fixed list-size is empty if the list size is less than the symmetrizability $\mathsf{\Omega }$. He obtained that the capacity corresponds to the random code capacity if the list size is greater than ${(1+\mathsf{\Omega })}^2$. H. Boche and R.F. Schaefer in Reference [26] obtained the list capacity region of AVMAC with conferencing encoders which is proved for large list size to be equal to the common randomness assisted capacity region. Moreover, in Reference [27], the authors found the deterministic code and random code capacity regions of arbitrarily varying broadcast channel with receiver side information. By defining a concept of symmetrizability for the channel, they characterized deterministic list codes capacity region as either identical to the random code capacity region or empty.

In this paper, we characterize the capacity of GAVC in Reference [22], using list-decoding for any list size and almost all power values of the transmitter and adversary, a similar result to that of Hughes in Reference [19] which obtained the list capacity for the discrete-memoryless AVC, for which the capacity was determined in Reference [6]. We assume that the encoder may be stochastic—that is, the encoder has access to private randomness—and a deterministic list decoder with constant list size L. Under the average probability of error criterion and without common randomness, we obtain the capacity of GAVC with list decoding to be equal to the corresponding randomized code capacity if the list size is greater than the power ratio of the jammer to the legitimate user; otherwise, the capacity is zero. Generally, our problem is a generalized version of the multiple packing of spherical caps problem in Reference [28] with Gaussian noise; although, they assumed maximal probability of error as the performance criterion. Their upper bound, which is only calculated for the noiseless case, depends on the list size L even in the asymptotic case. However, we only have list size in our symmetrizability conditions rather than the capacity itself.

In our converse proof (in Section 4), the adversary focuses on two possible strategies, one of which is simply sending Gaussian noise which causes the channel to act as a standard Gaussian channel with increased noise variance. The second strategy for the adversary is to transmit the superposition of some random (counterfeit) codewords, which is shown to be possible with positive probability if its power is large enough. In our achievability proof (in Section 5), we employ Gaussian codewords with a particular version of minimum distance list-decoding based on typicality. We extend the scheme of Reference [22] to show that with high probability a random Gaussian codebook has desirable properties to make the probability of error zero. However, our achievability proof originates from the idea of Reference Reference [6] based on typical sets, rather than the geometric approach of Reference [22]. This scheme allows us for simpler characterizations of codebook constraints. It is worth mentioning that we prove the achievability for the deterministic encoder since it suffices to achieve a rate even by a deterministic code, that is any deterministic code is a realistic value of a stochastic code. Our converse and achievability proofs apply for any list size; our previous work [29] provided proofs only for list size $L=2$.

Notations: Upper case letters denote random variables while lower case letters specify a deterministic value or the realization of a random variable. Bold letters denotes n-length vectors. We indicate inner product and 2-norm by $\langle ·,·\rangle$ and $\parallel ·\parallel$, respectively. We use ${|·|}^{+}$ and $\mathbb{E}[·]$ to denote the positive-part function and the expectation, respectively. Also, for an integer N, notation $\left[N\right]$ represents the set $\{1,2,3,\dots ,N\}$. Notation ${\mathbf{I}}_n$ and ${\mathbf{1}}_n$ stand for the identity matrix of size n and a vector of size n with n ones elements, respectively. For a vector $\mathbf{v}$, we use superscript ${\mathbf{v}}^T$ to denote its transpose. Both $log(·)$ and $exp(·)$ functions has base 2, so we define the Gaussian channel capacity function $C\left(x\right)=\frac{1}{2}log(1+x)$.

2. Problem Statement

A GAVC is a modified standard point-to-point Gaussian channel in the presence of an additive arbitrarily chosen adversary signal. Both transmitter and receiver do not know anything about the adversary signal and the adversary do not have any information about the transmitted signal except the codebooks. The received signal is given by

$$\begin{array}{c}\hfill \begin{array}{c}\hfill \mathbf{Y}=\mathbf{x}+\mathbf{s}+\mathbf{V}\end{array}\end{array}$$

(1)

where the n-length vector $\mathbf{x}$ is the legitimate transmitter’s signal, $\mathbf{s}$ represents the independent adversary signal and noise $\mathbf{V}$ is a sequence of n-length i.i.d. zero mean Gaussian random variables with variance ${\sigma }^2$, independent of $\mathbf{x}$ and $\mathbf{s}$.

We have the assumption of peak power constraints for the transmitter and adversary signals respectively as ${\parallel \mathbf{x}\parallel }^2\le nP$ and ${\parallel \mathbf{s}\parallel }^2\le n\mathsf{\Lambda }$. In addition, the transmitter and receiver are assumed to know the three parameters P, $\mathsf{\Lambda }$ and ${\sigma }^2$.

An $\left(n,N,N_r,L\right)$ stochastic list code for the GAVC is given by:

• Message set $\mathcal{M}=\left[N\right]$ and encoder private randomness set $\mathcal{K}=\left[N_r\right]$,
• Stochastic encoding function $\mathbf{x}(M,K):\mathcal{M}\times \mathcal{K}\to {\mathbb{R}}^n$,
• List decoding function $\varphi \left(\mathbf{y}\right):{\mathbb{R}}^n\to {\mathcal{D}}_L=\{\mathcal{L}:\mathcal{L}\subset \left[N\right],|\mathcal{L}|\le L\}$,

where the rate of the code is $R=\frac{1}{n}log(N/L)$. The transmitter encodes the message M and its private randomness K to $\mathbf{x}(M,K)$ where M and K are chosen uniformly respectively from sets $\mathcal{M}$ and $\mathcal{K}$. At the receiver, signal $\mathbf{Y}$ is decoded by a deterministic function $\varphi$ to the set ${\mathcal{D}}_L$ which is the set of all subsets of $\left[N\right]$ with cardinality at most L. In other words, L is the size of the list decoder.

First, define the probability of error $e(\mathbf{s},i)$ for a specific message $i\in \left[N\right]$ in the presence of a specific adversary signal $\mathbf{s}\in {\mathbb{R}}^n$ as the probability that $i\notin \varphi \left(\mathbf{y}\right)$. Therefore, the average probability of error for $\mathbf{s}$ is given by

$$\begin{array}{c}\hfill \overline{e}\left(\mathbf{s}\right)=\frac{1}{N}\sum _{i=1}^{N}e(\mathbf{s},i).\end{array}$$

(2)

Finally, the overall probability of error $P_e^{\left(n\right)}$ is obtained by maximizing over all possible choices of jammers’ sequences $\mathbf{s}$ satisfying peak power constraint ${\parallel \mathbf{s}\parallel }^2\le n\mathsf{\Lambda }$. Suppose r is rate of private randomness. Given L and r, rate R is achievable if there exists a sequence of $\left(n,L{2}^{nR},2^{nr},L\right)$ codes such that ${\displaystyle \underset{n\to \infty }{lim}}{P}_e^{\left(n\right)}=0$. The list-code capacity $\mathcal{C}(L,r)$ is the supremum of all achievable rates given L and r.

3. Main Results

Theorem 1.

The list-code capacity of GAVC is given by

$$\begin{array}{c}\hfill \mathcal{C}(L,r)=\left\{\begin{array}{cc}C\left(\frac{P}{\mathsf{\Lambda }+{\sigma }^2}\right),\hfill & L>\frac{\mathsf{\Lambda }}{P}\hfill \\ 0,\hfill & L<\frac{\mathsf{\Lambda }}{P}.\hfill \end{array}\right.\end{array}$$

(3)

Note that the capacity for$\mathsf{\Lambda }=LP$is unsolved.

Remark 1.

Note that this result holds for all r, including$r=0$which corresponds to a deterministic encoder. That is, the capacity does not depend on the amount of private randomness.

Remark 2.

The condition on the ratio$\frac{\mathsf{\Lambda }}{P}$determines whether it is possible for the adversary to launch a symmetrizing attack, wherein it transmits a superposition of codewords. Since each codeword has power P, the most codewords that the adversary can superpose while obeying its power constraint of Λ is the $\lfloor \frac{\mathsf{\Lambda }}{P}\rfloor$. Thus, if the allowable list size is greater than $\frac{\mathsf{\Lambda }}{P}$, then even under this attack the decoder can output a list made up of the true message and the superposed codewords selected by the adversary. Of course, the decoder does not know which is which but it can still guarantee that the true message is in the list. Thus, the worst the adversary can do is to act as an extra additive Gaussian noise with variance Λ, so the capacity is equal to the capacity of a standard Gaussian channel with increased noise variance as in $C\left(\frac{P}{\mathsf{\Lambda }+{\sigma }^2}\right)$. However, if the allowable list size is less than $\frac{\mathsf{\Lambda }}{P}$, then there are too many possibilities for the decoder to decode correctly, so the capacity is zero. Note that none of this depends on the channel noise, so ${\sigma }^2$ does not come into play in the condition on L.

Remark 3.

For the achievability proof, we make no assumptions about what the adversary does. However, for the converse proof, it is allowable to weaken the adversary by making certain assumptions about its behavior, because doing so can only increase the achievable rates. Since the converse is an upper bound on achievable rates, weakening the adversary in this manner still yields a valid upper bound.

In our proofs in Section 4 and Section 5, without loss of generality we restrict ourselves to the transmitter’s power $P=1$ which can be done by scaling the output signal.

4. Converse Proof

Without loss of generality, suppose $P=1$. For the first case where $\mathsf{\Lambda }<L$, we assume that we have a code $(n,L{2}^{nR},2^{nr},L)$ with vanishing probability of error. Since these codes must function for arbitrary jamming signals, we may derive an outer bound by assuming the adversary transmits Gaussian noise with variance $\mathsf{\Lambda }-\gamma$ for any $\gamma >0$ or $\mathbf{0}$ if Gaussian realization has power greater than $\mathsf{\Lambda }$. By the law of large numbers, with high probability the resulting channel is equivalent to a standard Gaussian channel with noise variance ${\sigma }^2+\mathsf{\Lambda }-\gamma$. Thus, since $\gamma$ can be chosen arbitrarily small, from the capacity of a non-adversarial Gaussian channel,

$$\mathcal{C}(L,r)\le C\left(\frac{1}{{\sigma }^2+\mathsf{\Lambda }}\right).$$

(4)

Now, assume the symmetrizable case where $\mathsf{\Lambda }>L$. In order to show $\mathcal{C}(L,r)=0$, first consider a sequence of stochastic codebooks and probability of error $P_e^{\left(n\right)}$. We claim that if $R>0$ and the jammer has the following strategy, then $P_e^{\left(n\right)}$ is bounded away from zero for sufficiently large n: The jammer randomly and uniformly chooses L messages $M_1,\dots ,M_L$ from $\left[L{2}^{nR}\right]$ and also L private keys $K_1,\dots ,K_L$ from $\left[2^{nr}\right]$ where $M_i$ and $K_i$ are independent. Note that the jammer knows the transmitted codebook. The jammer then constructs

$$\mathbf{Z}=\mathbf{x}(M_1,K_1)+\dots +\mathbf{x}(M_L,K_L)-L\mu$$

(5)

where $\mu \in {\mathbb{R}}^n$ is a constant vector that we will choose later. The jammer transmits $\mathbf{S}=\mathbf{Z}$ if ${\parallel \mathbf{Z}\parallel }^2\le n\mathsf{\Lambda }$ or else transmits $\mathbf{S}=\mathbf{0}$. In the former case, the received signal is

$$\begin{array}{cc}\hfill \mathbf{Y}& =\mathbf{x}(M_0,K_0)+\mathbf{x}(M_1,K_1)+\dots +\mathbf{x}(M_L,K_L)-L\mu +\mathbf{V}\hfill \end{array}$$

(6)

$$\begin{array}{c}=\mu +\sum _{i=0}^L(\mathbf{x}(M_i,K_i)-\mu )+\mathbf{V}\hfill \end{array}$$

(7)

where $M_0$ is the true message. If $M_0,M_1,\dots ,M_L$ are all different and for all sets $D\subset \{0,1,\dots ,L\}$ with $\left|D\right|=L$,

$${∥\sum _{i\in D}\mathbf{x}(M_i,K_i)-L\mu ∥}^2\le n\mathsf{\Lambda },$$

(8)

then from the decoder’s perspective, any L of the $L+1$ messages might have been forged by the adversary. Therefore, the list decoder with list size at most L has a probability of error at least $\frac{1}{L+1}$; that is, the probability that the decoder chooses L from the $L+1$ messages that does not contain the true message $M_0$. That is,

$$\begin{array}{l}{P}_e^{\left(n\right)}\ge \frac{1}{L+1}\mathbb{P}({∥{\displaystyle \sum _{i\in D}}\mathbf{x}(M_i,K_i)-L\mu ∥}^2\le n\mathsf{\Lambda }\\ \mathrm{for}\mathrm{all}D\subset \{0,1,\dots ,L\}\mathrm{with}\left|D\right|=L,\mathrm{and}{M}_0,M_1,\dots ,M_L\mathrm{are}\mathrm{distinct})\end{array}$$

(9)

$$\begin{array}{l}\ge \frac{1}{L+1}[\mathbb{P}\left({∥{\displaystyle \sum _{i\in D}}{\mathbf{X}}_i-L\mu ∥}^2\le n\mathsf{\Lambda }\mathrm{for}\mathrm{all}D\subset \{0,1,\dots ,L\}\mathrm{with}\left|D\right|=L\right)\\ -\left(1-\frac{L{2}^{nR}-1}{L{2}^{nR}}·\frac{L{2}^{nR}-2}{L{2}^{nR}}\cdots \frac{L{2}^{nR}-L}{L{2}^{nR}}\right)]\hfill \end{array}$$

(10)

where ${\mathbf{X}}_i=\mathbf{x}(M_i,K_i)$ and the second term in (10) shows the probability of messages $M_0,\dots ,M_L$ not being distinct which tends to zero as $n\to \infty$. Note that ${\mathbf{X}}_0,{\mathbf{X}}_1,\dots ,{\mathbf{X}}_L$ are independent and each distributed as a transmitted sequence from the code. We proceed to show that there exists a choice of $\mu$ based only on the codebook such that (10) is bounded away from zero for sufficiently large n if $R>0$.

Let

$${\alpha }^{\star }=inf\left\{\alpha :\underset{n\to \infty }{lim\; inf}\underset{\mu \in {\mathbb{R}}^n}{max}\mathbb{P}(\parallel {\mathbf{X}}_0-\mu {\parallel }^2\le n\alpha )>0\right\}.$$

(11)

Note that ${\alpha }^{\star }\le 1$, since by the power constraint we always have $\mathbb{P}(\parallel {\mathbf{X}}_0{\parallel }^2\le n)=1$. Fix any $\delta >0$ and let $\alpha ={\alpha }^{\star }+\delta /2$. Let

$$\gamma =\underset{n\to \infty }{lim\; inf}\underset{\mu \in {\mathbb{R}}^n}{max}\mathbb{P}(\parallel {\mathbf{X}}_0-\mu {\parallel }^2\le n\alpha ).$$

(12)

Since $\alpha >{\alpha }^{\star }$ we have $\gamma >0$. Thus for n sufficiently large, there exists $\mu \in {\mathbb{R}}^n$ such that

$$\mathbb{P}(\parallel {\mathbf{X}}_0-\mu {\parallel }^2\le n\alpha )\ge \gamma -\delta .$$

(13)

This $\mu$ is the one to be used by the jammer in (5). Let ${\mathcal{B}}_n$ be the set of all $\mathbf{x}$ that satisfy ${\parallel \mathbf{x}-\mu \parallel }^2\le n\alpha$. Note that $\mathbb{P}({\mathbf{X}}_0\in {\mathcal{B}}_n)\ge \gamma -\delta$.

Since $\alpha -\delta <{\alpha }^{\star }$, by the definition of ${\alpha }^{\star }$,

$$\underset{n\to \infty }{lim\; inf}\underset{{\mu }^{\prime }\in \mathbb{R}}{max}\mathbb{P}(\parallel {\mathbf{X}}_0-{\mu }^{\prime }{\parallel }^2\le n(\alpha -\delta ))=0.$$

(14)

Specifically, there exists n sufficiently large so that for all ${\mu }^{\prime }\in {\mathbb{R}}^n$,

$$\mathbb{P}(\parallel {\mathbf{X}}_0-{\mu }^{\prime }{\parallel }^2\le n(\alpha -\delta ))\le \delta .$$

(15)

Fix any ${\mathbf{x}}_1\in {\mathcal{B}}_n$ and consider those $\mathbf{x}\in {\mathcal{B}}_n$ such that

$$\langle \mathbf{x}-\mu ,{\mathbf{x}}_1-\mu \rangle >n\sqrt{\delta \alpha }$$

(16)

which implies

$$\begin{array}{cc}\hfill {∥\mu +\sqrt{\delta {\alpha }^{-1}}({\mathbf{x}}_1-\mu )-\mathbf{x}∥}^2& ={\parallel \mathbf{x}-\mu \parallel }^2+\delta {\alpha }^{-1}{\parallel {\mathbf{x}}_1-\mu \parallel }^2-2\sqrt{\delta {\alpha }^{-1}}\langle \mathbf{x}-\mu ,{\mathbf{x}}_1-\mu \rangle \hfill \end{array}$$

(17)

$$\begin{array}{c}<n\alpha +n\delta -n2\delta \hfill \end{array}$$

(18)

$$\begin{array}{c}=n(\alpha -\delta ).\hfill \end{array}$$

(19)

Thus, we obtain the following by applying (15) with ${\mu }^{\prime }=\mu +\sqrt{\delta {\alpha }^{-1}}({\mathbf{x}}_1-\mu )$ as

$$\begin{array}{c}\hfill \mathbb{P}(\langle {\mathbf{X}}_0-\mu ,{\mathbf{X}}_1-\mu \rangle >n\sqrt{\delta \alpha },{\mathbf{X}}_0,{\mathbf{X}}_1\in {\mathcal{B}}_n)\le \underset{{\mathbf{x}}_1\in {\mathcal{B}}_n}{max}\mathbb{P}(\langle {\mathbf{X}}_0-\mu ,{\mathbf{x}}_1-\mu \rangle >n\sqrt{\delta \alpha },{\mathbf{X}}_0\in {\mathcal{B}}_n)\le \delta .\end{array}$$

(20)

Moreover, if ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_L\in {\mathcal{B}}_n$ satisfy $\langle {\mathbf{x}}_i-\mu ,{\mathbf{x}}_j-\mu \rangle \le n\sqrt{\delta \alpha }$ for all $i\ne j\in \{1,\dots ,L\}$, then

$$\begin{array}{cc}\hfill \parallel {\mathbf{x}}_1+\dots +{\mathbf{x}}_L{-L\mu \parallel }^2& =\sum _{i=0}^{L-1}{\parallel {\mathbf{x}}_i-\mu \parallel }^2+2\sum _{i=0}^{L-2}\sum _{j=i+1}^{L-1}\langle {\mathbf{x}}_i-\mu ,{\mathbf{x}}_j-\mu \rangle \hfill \end{array}$$

(21)

$$\begin{array}{c}\le n\left(L\alpha +L(L-1)\sqrt{\delta \alpha }\right)\hfill \end{array}$$

(22)

$$\begin{array}{c}\le n\left(L+L\delta +L(L-1)\sqrt{\delta \alpha }\right)\hfill \end{array}$$

(23)

$$\begin{array}{c}<n\mathsf{\Lambda }\hfill \end{array}$$

(24)

where (23) holds since $\alpha <{\alpha }^{\star }+\delta \le 1+\delta$ and (24) holds for sufficiently small $\delta$ and by assumption $\mathsf{\Lambda }>L$. Now we have

$$\begin{array}{c}\mathbb{P}\left({∥\sum _{i\in D}{\mathbf{X}}_i-L\mu ∥}^2\le n\mathsf{\Lambda }\mathrm{for}\mathrm{all}\mathrm{distinct}\mathrm{set}D\subset \{0,1,\dots ,L\}\mathrm{with}\left|D\right|=L\right)\hfill \\ \ge \mathbb{P}\left(\langle {\mathbf{X}}_i-\mu ,{\mathbf{X}}_j-\mu \rangle \le n\sqrt{\delta \alpha }\mathrm{for}\mathrm{all}i,j\in \{0,1,\dots ,L\},i\ne j,{\mathbf{X}}_0,{\mathbf{X}}_1,\dots ,{\mathbf{X}}_L\in {\mathcal{B}}_n\right)\hfill \end{array}$$

(25)

$$\begin{array}{c}\ge \mathbb{P}{({\mathbf{X}}_0\in {\mathcal{B}}_n)}^{(L+1)}-\frac{L(L+1)}{2}\mathbb{P}(\langle {\mathbf{X}}_0-\mu ,{\mathbf{X}}_1-\mu \rangle >n\sqrt{\delta \alpha },{\mathbf{X}}_0,{\mathbf{X}}_1\in {\mathcal{B}}_n)\hfill \end{array}$$

(26)

$$\begin{array}{c}\ge {(\gamma -\delta )}^{(L+1)}-\frac{L(L+1)\delta }{2}\hfill \end{array}$$

(27)

where (25) follows from the analysis leading to (24), (26) follows from the union bound and the fact that ${\mathbf{X}}_0,{\mathbf{X}}_1,\dots ,{\mathbf{X}}_L$ are independent and (27) follows from the lower bound on the probability of ${\mathcal{B}}_n$ and (20). For sufficiently small $\delta$, (27) is bounded away from zero, so by (10), $P_e^{\left(n\right)}$ is also bounded away from zero for sufficiently large n if $R>0$.

5. Achievability Proof

Before proceeding to the proof, let define the typical set for Gaussian random variables $X_1,\dots ,X_k$ as:

$$\begin{array}{c}\hfill {\mathcal{T}}_{ϵ}^{\left(n\right)}(X_1,\dots ,X_k)=\left\{({\mathbf{x}}_1,\dots ,{\mathbf{x}}_k):\mathbb{E}\left(X_i{X}_j\right)-ϵ\le \frac{1}{n}\langle {\mathbf{x}}_i,{\mathbf{x}}_j\rangle \le \mathbb{E}\left(X_i{X}_j\right)+ϵ\mathrm{for}\mathrm{all}i,j\in [1:k]\right\}.\end{array}$$

(28)

Without loss of generality, assume $P=1$, $r=0$ and

$$\begin{array}{c}\mathsf{\Lambda }<L,\hfill \end{array}$$

(29)

$$\begin{array}{c}R<C\left(\frac{1}{\mathsf{\Lambda }+{\sigma }^2}\right).\hfill \end{array}$$

(30)

Note that assuming $r=0$ makes the code deterministic. Thus, it suffices to achieve the list-code capacity by a $(n,L{2}^{nR},L)$ deterministic code construction as follows:

Codebook generation: Fix $ϵ>{ϵ}^{\prime }>\gamma >0$. We generate $L{2}^{nR}$ i.i.d zero mean Gaussian sequences $\mathbf{X}\left(m\right)$ with variance $(1-\gamma )$ for each $m\in \left[L{2}^{nR}\right]$.

Encoding: The transmitter sends $\mathbf{X}=\mathbf{X}\left(m\right)$ if its power is less than 1, otherwise it sends zero.

Decoding: First, given $\mathbf{y}$, for $1\le \ell \le L$ let set ${\mathcal{S}}_{\ell }$ be the set of ℓ-tuple messages $(m_1,\dots ,m_{\ell })$ that $(\mathbf{x}\left(m_1\right),\dots ,\mathbf{x}\left(m_{\ell }\right),\mathbf{y})\in {\mathcal{T}}_{ϵ}^{\left(n\right)}(X_1,\dots ,X_{\ell },Y)$ for any set of zero-mean Gaussian variables $(X_1,\dots ,X_{\ell },Y)$ such that

$$Cov(X_1,\dots ,X_{\ell },Y)={\left[\begin{array}{cc}{\mathbf{I}}_{\ell }& {\mathbf{1}}_{\ell }^T\\ {\mathbf{1}}_{\ell }& A\end{array}\right]}_{(\ell +1)\times (\ell +1)}$$

(31)

and $1\le A\le 1+{\sigma }^2+\mathsf{\Lambda }$.

Now we define the decoding function as

$$\begin{array}{c}\hfill \varphi \left(\mathbf{y}\right)=\underset{\mathcal{L}\in {\bigcup }_{\ell =1}^L{\mathcal{S}}_{\ell }}{arg\; min}∥\mathbf{y}-\sum _{m\in \mathcal{L}}\mathbf{x}\left(m\right)∥.\end{array}$$

(32)

where we choose between multiple minimizing $\mathcal{L}$ arbitrarily.

Analysis of the probability of error: To prove that the constructed code is achievable meaning that the probability of error tends to zero as $n\to \infty$, we utilize several lemmas including the following. We provide some necessary codebook properties that hold with high probability in Lemma 1, the proof for which is in the Appendix A.

Lemma 1.

Let$\mathbf{X}\left(m\right)$for$m\in \left[N\right]$,$N=L{2}^{nR}$, be the Gaussian codebook described above. With probability approaching 1 as$n\to \infty$, the codebook satisfies the following, for any$\mathbf{x},\mathbf{s}$where${\parallel \mathbf{s}\parallel }^2\le n\mathsf{\Lambda }$and any zero-mean jointly Gaussian random vector$(X,X_1,\dots ,X_{\ell },S)$with positive definite covariance matrices with diagonals at most$(1,1,\dots ,1,\mathsf{\Lambda })$for all$1\le \ell \le L$:

$$\begin{array}{c}\frac{1}{N}\left|\left\{m:(\mathbf{x}\left(m\right),\mathbf{s})\notin \bigcup _{\begin{array}{c}(X,S)\mathit{independent}:\\ E{X}^2=1,E{S}^2\le \mathsf{\Lambda }\end{array}}{\mathcal{T}}_{{ϵ}^{\prime }}^{\left(n\right)}(X,S)\right\}\right|\le exp(-n\delta \left(ϵ\right)),\hfill \end{array}$$

(33)

$$\begin{array}{c}\left|\left\{m_1:(\mathbf{x},\mathbf{x}\left(m_1\right),\mathbf{s})\in {\mathcal{T}}_{ϵ}^{\left(n\right)}(X,X_1,S)\right\}\right|\le exp\left\{n\left[|R-I(X_1;XS){|}^{+}+\delta \left(ϵ\right)\right]\right\},\hfill \end{array}$$

(34)

$$\begin{array}{c}\frac{1}{N}\left|\left\{m:(\mathbf{x}\left(m\right),\mathbf{x}\left(m_1\right),\mathbf{s})\in {\mathcal{T}}_{ϵ}^{\left(n\right)}(X,X_1,S)\mathit{for}\mathit{some}{m}_1\ne m\right\}\right|\le 2exp\{-n\delta \left(ϵ\right)/2\},\hfill \\ ifI(X;X_{1}S)\ge {|R-I(X_1;S)|}^{+}+\delta \left(ϵ\right),\hfill \end{array}$$

(35)

$$\begin{array}{c}\left|\left\{(m_1,\dots ,m_{\ell }):(\mathbf{x},\mathbf{x}\left(m_1\right),\dots ,\mathbf{x}\left(m_{\ell }\right),\mathbf{s})\in {\mathcal{T}}_{ϵ}^{\left(n\right)}(X,X_1,\dots ,X_{\ell },S)\right\}\right|\le exp\left\{n\delta \left(ϵ\right)\right\}\hfill \\ ifR<\underset{k\in \{1,\dots ,\ell \}}{min}I(X_k;S),\hfill \end{array}$$

(36)

$$\begin{array}{c}\frac{1}{N}\left|\left\{m:(\mathbf{x}\left(m\right),\mathbf{x}\left(m_1\right),\dots ,\mathbf{x}\left(m_{\ell }\right),\mathbf{s})\in {\mathcal{T}}_{ϵ}^{\left(n\right)}(X,X_1,\dots ,X_{\ell },S)forsome{m}_1,\dots ,m_{\ell }\ne m\right\}\right|\hfill \\ \le exp\{-n\delta \left(ϵ\right)/2\},ifI(X;X_1\dots X_{\ell }S)\ge \delta \left(ϵ\right)andR<\underset{k\in \{1,\dots ,\ell \}}{min}I(X_k;S).\hfill \end{array}$$

(37)

The following lemmas can be easily generalized for Gaussian random variables by following the corresponding lemmas in Reference [30] for discrete memoryless random variables.

Conditional Typicality Lemma: Let $(X,Y)\sim f(x,y)$ be jointly Gaussian random variables. Suppose that $\mathbf{x}\in {\mathcal{T}}_{ϵ}^{\left(n\right)}\left(X\right)$ and $\mathbf{Y}\sim f\left(\mathbf{y}\right|\mathbf{x})={\prod }_{i=1}^n{f}_{Y|X}\left(y_i\right|x_i)$. Then, for every $ϵ>{ϵ}^{\prime }$,

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}\mathbb{P}\{(\mathbf{x},\mathbf{Y})\in {\mathcal{T}}_{ϵ}^{\left(n\right)}(X,Y)\}=1.\end{array}$$

(38)

Joint Typicality Lemma: Let $(X,Y,Z)\sim f(x,y,z)$ be jointly Gaussian random variables. If $(\tilde{\mathbf{x}},\tilde{\mathbf{y}})$ is a pair of arbitrary sequences and $\tilde{\mathbf{Z}}\sim {\prod }_{i=1}^n{f}_{Z|X}\left({\tilde{z}}_i\right|{\tilde{x}}_i)$ then there exists $\delta \left(ϵ\right)>0$ that tends to zero as $ϵ\to 0$ such that

$$\begin{array}{c}\hfill \mathbb{P}\{(\tilde{\mathbf{x}},\tilde{\mathbf{y}},\tilde{\mathbf{Z}})\in {\mathcal{T}}_{ϵ}^{\left(n\right)}(X,Y,Z)\}\le exp(-n(I(Y;Z|X)-\delta \left(ϵ\right))).\end{array}$$

(39)

Assume that the legitimate user transmits message M. Then, the probability of error is upper bounded by the sum of the following L error events probabilities:

$$\begin{array}{l}{P}_{\ell }=\mathbb{P}\{\parallel \mathbf{Y}-\mathbf{x}\left(m_1\right)-\dots -\mathbf{x}\left(m_{\ell }\right){\parallel }^2\le {\displaystyle \underset{\begin{array}{c}{\widehat{m}}_1,\dots ,{\widehat{m}}_{\ell }:\\ (M,{\widehat{m}}_1,\dots ,{\widehat{m}}_{\ell })\in {\mathcal{S}}_{\ell +1}\end{array}}{min}}\parallel \mathbf{Y}-\mathbf{x}\left(M\right)-\mathbf{x}\left({\widehat{m}}_1\right)-\dots -\mathbf{x}\left({\widehat{m}}_{\ell }\right){\parallel }^2\\ \mathrm{for}\mathrm{some}(m_1,\dots ,m_{\ell })\in {\mathcal{S}}_{\ell },m_i\ne M\mathrm{for}\mathrm{all}i\in [\ell ]\}\mathrm{for}1\le \ell <L,\end{array}$$

(40)

$$\begin{array}{cc}\hfill P_L& =\mathbb{P}\left\{\exists (m_1,\dots ,m_L)\in {\mathcal{S}}_L:m_{\ell }\ne M,\mathrm{for}\mathrm{all}\ell \in \left[L\right]\right\}.\hfill \end{array}$$

(41)

By Lemma 1, we may assume we have a deterministic codebook that satisfies (33)–(37). Consider any state sequence $\mathbf{s}$. By (33), with high probability $(\mathbf{x}\left(M\right),\mathbf{s})\in {\mathcal{T}}_{{ϵ}^{\prime }}^{\left(n\right)}(X,S)$ where $(X,S)$ are independent and $\mathbb{E}{X}^2=1,\mathbb{E}{S}^2\le \mathsf{\Lambda }$ (33). Thus, by the conditional typicality lemma, for every $ϵ>{ϵ}^{\prime }$ with high probability $({\mathbf{x}}_i,\mathbf{s},\mathbf{V})\in {\mathcal{T}}_{ϵ}^{\left(n\right)}(X,S,V)$ where $(X,S,V)$ are mutually independent and $\mathbb{E}{V}^2={\sigma }^2$.

We first bound probability event $P_{\ell }$ for $1\le \ell <L$. Define the shorthand ${\overrightarrow{X}}_{\ell }=(X{X}_1\dots X_{\ell }SV)$. Let ${\mathcal{V}}_{\ell }$ denote a finite set of Gaussian distributions of ${\overrightarrow{X}}_{\ell }$ that is $ϵ$-dense in the set of all Gaussian distributions of ${\overrightarrow{X}}_{\ell }$ with variances at most $(1,1,\dots ,1,\mathsf{\Lambda },{\sigma }^2)$. Note that the cardinality of ${\mathcal{V}}_{\ell }$ does not depend on n. We may upper bound $P_{\ell }$ by

$$\sum _{{\overrightarrow{X}}_{\ell }\in {\mathcal{V}}_{\ell }}\frac{1}{N}\sum _{m=1}^N{e}_{{\overrightarrow{X}}_{\ell }}(m,\mathbf{s})$$

(42)

where

$$\begin{array}{c}{e}_{{\overrightarrow{X}}_{\ell }}(m,\mathbf{s})=\mathbb{P}\{(\mathbf{x}\left(m\right),\mathbf{x}\left(m_1\right),\dots ,\mathbf{x}\left(m_{\ell }\right),\mathbf{s},\mathbf{V})\in {\mathcal{T}}_{ϵ}^{\left(n\right)}\left({\overrightarrow{X}}_{\ell }\right),\hfill \\ \parallel \mathbf{x}\left(m\right)+\mathbf{s}+\mathbf{V}-\mathbf{x}\left(m_1\right)-\dots -\mathbf{x}\left(m_{\ell }\right){\parallel }^2\le \underset{\begin{array}{c}{\widehat{m}}_1,\dots ,{\widehat{m}}_{\ell }:\\ (m,{\widehat{m}}_1,\dots ,{\widehat{m}}_{\ell })\in {\mathcal{S}}_{\ell +1}\end{array}}{min}{\parallel \mathbf{s}+\mathbf{V}-\mathbf{x}\left({\widehat{m}}_1\right)-\dots -\mathbf{x}\left({\widehat{m}}_{\ell }\right)\parallel }^2\\ \hfill \mathrm{for}\mathrm{some}(m_1,\dots ,m_{\ell })\in {\mathcal{S}}_{\ell }\mathrm{and}{m}_i\ne m\mathrm{for}\mathrm{all}i\in [\ell ]\}.\end{array}$$

(43)

We will show that $\frac{1}{N}{\sum }_{m=1}^N{e}_{{\overrightarrow{X}}_{\ell }}(m,\mathbf{s})\to 0$ for all Gaussian vectors ${\overrightarrow{X}}_{\ell }$ (whether or not they are in ${\mathcal{V}}_{\ell }$). We may restrict ourselves to ${\overrightarrow{X}}_{\ell }$ where

$$\begin{array}{c}(X,S,V)\mathrm{are}\mathrm{mutually}\mathrm{independent},\end{array}$$

(44)

$$\begin{array}{c}\mathbb{E}{X}^2=\mathbb{E}{X}_1^2=\dots =\mathbb{E}{X}_{\ell }^2=1,\mathbb{E}{V}^2={\sigma }^2,\mathbb{E}{S}^2\le \mathsf{\Lambda }\end{array}$$

(45)

$$\begin{array}{c}(X_i,X+S+V-X_i)\mathrm{are}\mathrm{independent}\mathrm{for}\mathrm{all}i\in [\ell ],\end{array}$$

(46)

$$\begin{array}{c}\mathbb{E}{(X+S+V-X_i)}^2\le \mathsf{\Lambda }+{\sigma }^2\mathrm{for}\mathrm{all}i\in [\ell ],\end{array}$$

(47)

where (44) holds since the legitimate transmitter, the jammer and the noise are independently generated, (45) follows from the assumptions for ${\overrightarrow{X}}_{\ell }$, (46) corresponds to $\mathbb{E}{X}_i(Y-X_i)=0$ following from (31) and the assumption that $(m_1,\dots ,m_{\ell })\in {\mathcal{S}}_{\ell }$ and (47) is obtained by (31) as follows:

$$\begin{array}{cc}\hfill \mathbb{E}{(X+S+V-X_i)}^2& =\mathbb{E}{(Y-X_i)}^2\hfill \end{array}$$

(48)

$$\begin{array}{c}=\mathbb{E}{Y}^2+\mathbb{E}{X}_i^2-2\mathbb{E}Y{X}_i\hfill \end{array}$$

(49)

$$\begin{array}{c}\le 1+{\sigma }^2+\mathsf{\Lambda }+1-2\hfill \end{array}$$

(50)

$$\begin{array}{c}=\mathsf{\Lambda }+{\sigma }^2.\hfill \end{array}$$

(51)

Now, suppose

$$I(XV;S{X}_1\dots X_{\ell })=0.$$

(52)

Then we would have $\mathbb{E}X{X}_i=0$ for all $i\in [\ell ]$. Thus, $(X,X_1,\dots ,X_{\ell },S+V-X_1-\dots -X_{\ell })$ are mutually independent since

$$\begin{array}{c}\hfill \mathbb{E}X(S+V-X_1-\dots -X_{\ell })=\mathbb{E}X(S+V)=0,\end{array}$$

(53)

and

$$\begin{array}{cc}\hfill \mathbb{E}{X}_i(S+V-X_1-\dots -X_{\ell })& =\mathbb{E}{X}_i(Y-X-X_1-\dots -X_{\ell })\hfill \end{array}$$

(54)

$$\begin{array}{c}=\mathbb{E}{X}_i(Y-X_i)\hfill \end{array}$$

(55)

$$\begin{array}{c}=0,\mathrm{for}\mathrm{all}i\in [\ell ],\hfill \end{array}$$

(56)

where (53) follows from (44), (55) and (56) follow from (31) and $\mathbb{E}X{X}_i=0$. Hence, if the message $(m_1,\dots ,m_{\ell })$ satisfies the conditions in the probability in (43), then $(m,m_1,\dots ,m_{\ell })\in {\mathcal{S}}_{\ell +1}$. This implies that $({\widehat{m}}_1,\dots ,{\widehat{m}}_{\ell })$ takes on the value $(m_1,\dots ,m_{\ell })$ in the minimum, so $\parallel \mathbf{Y}-\mathbf{x}\left(m_1\right)-\dots -\mathbf{x}\left(m_{\ell }\right){\parallel }^2\le {\parallel \mathbf{Y}-\mathbf{x}\left(m_1\right)-\dots -\mathbf{x}\left(m_{\ell }\right)-\mathbf{x}\left(M\right)\parallel }^2$ and so we must have

$$\mathbb{E}{(X+S+V-X_1-\dots -X_{\ell })}^2\le \mathbb{E}{(S+V-X_1-\dots -X_{\ell })}^2.$$

(57)

However, this contradicts the assumptions that X is independent from $S,X_1,\dots ,X_{\ell },V$, since

$$\begin{array}{cc}\hfill \mathbb{E}{(X+S+V-X_1-\dots ,X_{\ell })}^2& =\mathbb{E}{X}^2+\mathbb{E}{(S+V-X_1-\dots ,X_{\ell })}^2\hfill \end{array}$$

(58)

$$\begin{array}{c}=1+\mathbb{E}{(S+V-X_1-\dots ,X_{\ell })}^2.\hfill \end{array}$$

(59)

Therefore, the assumption in (52) is false and there exists $\eta >0$ such that

$$\eta \le I(XV;S{X}_1\dots X_{\ell })=I(XV;X_1\dots X_{\ell }|S).$$

(60)

Now, consider the following two cases.

Case (a): $R<min\{I(X_1;S),\dots ,I(X_{\ell };S)\}$. By (37), we only need to consider distributions where

$$I(X;X_1\dots X_{\ell }S)<\delta \left(ϵ\right).$$

(61)

Then for any $m,\mathbf{s}$

$$\begin{array}{cc}\hfill e_{{\overrightarrow{X}}_{\ell }}(m,\mathbf{s})& \le \sum _{\begin{array}{c}{m}_1,\dots ,m_{\ell }\end{array}}\mathbb{P}\left\{(\mathbf{x}\left(m\right),\mathbf{x}\left(m_1\right),\dots ,\mathbf{x}\left(m_{\ell }\right),\mathbf{s},\mathbf{V})\in {\mathcal{T}}_{ϵ}^{\left(n\right)}(X,X_1,\dots ,X_{\ell },S,V)\right\}\hfill \end{array}$$

(62)

$$\begin{array}{c}\le exp\left\{-n\left(I(V;X_1\dots X_{\ell }|XS)-\delta \left(ϵ\right)\right)\right\}\hfill \end{array}$$

(63)

$$\begin{array}{c}=exp\{-n(I(XV;X_1\dots X_{\ell }|S)-I(X;X_1\dots X_{\ell }|S)-\delta \left(ϵ\right))\}\hfill \end{array}$$

(64)

$$\begin{array}{c}\le exp\{-n(\eta -2\delta \left(ϵ\right)\left)\right\}\hfill \end{array}$$

(65)

where in (62) the sum is over all $m_1,\dots ,m_{\ell }:(\mathbf{x}\left(m\right),\mathbf{x}\left(m_1\right),\dots ,\mathbf{x}\left(m_{\ell }\right),\mathbf{s})\in {\mathcal{T}}_{ϵ}^{\left(n\right)}(X,X_1,\dots ,X_{\ell },S)$, in (63) we use (36), the joint typicality lemma and $I(V;XS)=0$ and (65) follows from (60) and (61). Thus, (65) tends to zero exponentially fast for sufficiently small $\delta \left(ϵ\right)$.

Case (b): $R\ge min\{I(X_1;S),\dots ,I(X_{\ell };S)\}$. We may assume without loss of generality that $R\ge I(X_1;S)$. Now, we upper bound (43) by

$$\begin{array}{c}\hfill e_{\overrightarrow{X_{\ell }}}(m,\mathbf{s})\le \sum _{\widehat{m}:(\mathbf{x}\left(m\right),\mathbf{x}\left(\widehat{m}\right),\mathbf{s})\in {\mathcal{T}}_{ϵ}^{\left(n\right)}(X,X_1,S)}\mathbb{P}\left\{(\mathbf{x}\left(m\right),\mathbf{x}\left(\widehat{m}\right),\mathbf{s},\mathbf{V})\in {\mathcal{T}}_{ϵ}^{\left(n\right)}(X,X_1,S,V)\right\}.\end{array}$$

(66)

Note that by (35), we may narrow the distributions to those with

$$I(X;X_{1}S)<R-I(X_1;S)+\delta \left(ϵ\right).$$

(67)

Therefore,

$$\begin{array}{cc}\hfill e_{{\overrightarrow{X}}_{\ell }}(m,\mathbf{s})& \le exp\{n\left[|R-I(X_1;XS){|}^{+}-I(V;X_1|XS)+2\delta \left(ϵ\right)\right]\hfill \end{array}$$

(68)

$$\begin{array}{c}\le exp\left(n\left[R-I(X_1;XS)-I(V;X_1|XS)+2\delta \left(ϵ\right)\right]\right)\hfill \end{array}$$

(69)

$$\begin{array}{c}=exp\left(n[R-I(X_1;XSV)+2\delta \left(ϵ\right)]\right)\hfill \end{array}$$

(70)

where (68) follows from (34) and the joint typicality lemma, (69) follows since by $R\ge I(X_1;S)$ and (67) we have

$$\begin{array}{cc}\hfill R& >I(X;X_{1}S)+I(X_1;S)-\delta \left(ϵ\right)\hfill \end{array}$$

(71)

$$\begin{array}{c}=I(X;X_1|S)+I(X_1;S)-\delta \left(ϵ\right)\hfill \end{array}$$

(72)

$$\begin{array}{c}=I(X_1;XS)-\delta \left(ϵ\right).\hfill \end{array}$$

(73)

Let $Z=X+S+V-X_1$. From (46)–(47), we get

$$\begin{array}{cc}\hfill I(X_1;XSV)& \ge I(X_1;X_1+Z)\hfill \end{array}$$

(74)

$$\begin{array}{c}=C\left(\frac{1}{\mathbb{E}{Z}^2}\right)\hfill \end{array}$$

(75)

$$\begin{array}{c}\ge C\left(\frac{1}{\mathsf{\Lambda }+{\sigma }^2}\right)\hfill \end{array}$$

(76)

Using this result in (70), we obtain

$$e_{{\overrightarrow{X}}_{\ell }}(m,\mathbf{s})\le exp\left\{n\left[R-C\left(\frac{1}{\mathsf{\Lambda }+{\sigma }^2}\right)+2\delta \left(ϵ\right)\right]\right\}$$

(77)

meaning that $e_{{\overrightarrow{X}}_{\ell }}(m,\mathbf{s})$ is exponentially vanishing if $\delta \left(ϵ\right)$ is sufficiently small and the rate condition in (30) holds.

Now, we consider error probability $P_L$. Define ${\overrightarrow{X}}_L=(X{X}_1{X}_2\dots X_{L}SV)$. Let ${\mathcal{V}}_L$ denote a finite $ϵ$-dense subset of Gaussian vectors ${\overrightarrow{X}}_L$ with variances at most $1,1,1,\dots ,1,\mathsf{\Lambda },{\sigma }^2$. Thus, $P_L$ can be upper bounded by

$$\sum _{{\overrightarrow{X}}_L\in {\mathcal{V}}_L}\frac{1}{N}\sum _{m=1}^N{e}_{{\overrightarrow{X}}_L}(m,\mathbf{s})$$

(78)

where

$$\begin{array}{c}{e}_{{\overrightarrow{X}}_L}(m,\mathbf{s})=\mathbb{P}\{(\mathbf{x}\left(m\right),\mathbf{x}\left(m_1\right),\dots ,\mathbf{x}\left(m_L\right),\mathbf{s},\mathbf{V})\in {\mathcal{T}}_{ϵ}^{\left(n\right)}\left({\overrightarrow{X}}_L\right),\hfill \\ \hfill \mathrm{for}\mathrm{some}(m_1,\dots ,m_L)\in {\mathcal{S}}_L\mathrm{and}{m}_{\ell }\ne m\mathrm{for}\mathrm{all}\ell \in \left[L\right]\}.\end{array}$$

(79)

Thus, we need to show that $\frac{1}{N}{\sum }_{m=1}^N{e}_{{\overrightarrow{X}}_L}(m,\mathbf{s})$ vanishes as $n\to \infty$ for all Gaussian vectors ${\overrightarrow{X}}_L$ that satisfy (44)–(47) for all $\ell \in \left[L\right]$ and

$$\begin{array}{c}\mathbb{E}{X}_L^2=1,(X_1,\dots ,X_L)\mathrm{are}\mathrm{independent},\end{array}$$

(80)

where (80) follows from (31) in which $Cov\left(X_i{X}_j\right)=0$ for all $i\ne j\in \left[L\right]$.

Observe that if $I(XV;S{X}_1\dots X_L)=0$, then we would have for all $\ell \in \left[L\right]$

$$\begin{array}{cc}\hfill 0& =\mathbb{E}{X}_{\ell }(X+S+V-X_{\ell })\hfill \end{array}$$

(81)

$$\begin{array}{c}=\mathbb{E}{X}_{\ell }(S-X_{\ell })\hfill \end{array}$$

(82)

$$\begin{array}{c}=\mathbb{E}{X}_{\ell }S-1,\hfill \end{array}$$

(83)

where (83) follows from (31).

Since $\mathbb{E}{X}_i{X}_j=0$ for all $i,j\in \left[L\right]$ and $i\ne j$, the covariance matrix of $(S,X_1,\dots ,X_L)$ is equal to

$$\begin{array}{c}\hfill \left[\begin{array}{cc}\mathbb{E}{S}^2& {\mathbf{1}}_L^T\\ {\mathbf{1}}_L& {\mathbf{I}}_L\end{array}\right]\end{array}$$

(84)

which has the determinant of $\mathbb{E}{S}^2-L$. This determinant should be positive since the covariance matrix $Cov(S,X_1,\dots ,X_L)$ is positive definite. However, since $\mathbb{E}{S}^2\le \mathsf{\Lambda }$, this assumption contradicts the assumption that $\mathsf{\Lambda }<L$ in (29). Thus, there exists $\eta >0$ such that

$$\eta \le I(XV;S{X}_1\dots X_L)=I(XV;X_1\dots X_L|S)$$

(85)

where we have used the fact that $I(XV;S)=0$.

Now, we may consider two cases $R<min\{I(X_1;S),\dots ,I(X_L;S)\}$ and $R\ge min\{I(X_1;S),\dots ,I(X_L;S)\}$. Therefore, using an identical argument as in the cases (a) and (b) for $P_{\ell }$, it follows that $e_{{\overrightarrow{X}}_L}$ is also exponentially vanishing.