e}-\frac{\delta_{E}}{N_{0}}}\right)^{2}+\frac{\delta_{E}}{2N_{0}}\right)\right].$
(105)

We next use (105) and expurgation to derive a lower bound on $P_{e,1}$.
Indeed, we divide the codebook $\cal{C}$ with $M$ messages into two codebooks
$\mbox{$\cal{C}$}_{1}$ and $\mbox{$\cal{C}$}_{2}$ of $M/2$ messages each, such
that $\mbox{$\cal{C}$}_{1}$ contains the codewords with the smallest
probability of error $P_{e_{m}}$ and $\mbox{$\cal{C}$}_{2}$ contains the
codewords with the largest $P_{e_{m}}$. It then holds that each codeword in
$\mbox{$\cal{C}$}_{1}$ has a probability of error satisfying $P_{e_{m}}\leq
2P_{e,1}$. Consequently, the largest error probability of code
$\mbox{$\cal{C}$}_{1}$, denoted as $P_{e_{\max}}(\mbox{$\cal{C}$}_{1})$, and
the average error probability of code $\cal{C}$, denoted as
$P_{e}(\mbox{$\cal{C}$})$, satisfy

$\displaystyle
P_{e}(\mbox{$\cal{C}$})\geq\frac{1}{2}P_{e_{\max}}(\mbox{$\cal{C}$}_{1}).$
(106)

Applying (105) for $\mbox{$\cal{C}$}_{1}$, and using that the rate per unit-
energy of $\mbox{$\cal{C}$}_{1}$ satisfies $\dot{R}^{\prime}=\frac{\log
M/2}{E}=\dot{R}-\frac{1}{E}$, we obtain

$\displaystyle
P_{e_{\max}}(\mbox{$\cal{C}$}_{1})\geq\exp\left[-E\left(\left(\sqrt{\frac{1}{N_{0}}}-\sqrt{\frac{\dot{R}}{\log
e}-\frac{1}{E}-\frac{\delta_{E}}{N_{0}}}\right)^{2}+\frac{\delta_{E}}{2N_{0}}\right)\right].$

Together with (106), this yields

$\displaystyle P_{e,1}$
$\displaystyle\geq\exp\left[-E\left(\left(\sqrt{\frac{1}{N_{0}}}-\sqrt{\frac{\dot{R}}{\log
e}-\frac{1}{E}-\frac{\delta_{E}}{N_{0}}}\right)^{2}+\frac{\delta_{E}}{2N_{0}}-\frac{\ln
2}{E}\right)\right].$ (107)

Let $\delta^{\prime}_{E}\triangleq\frac{1}{E}+\frac{\delta_{E}}{N_{0}}$. Then

$\displaystyle\sqrt{\frac{\dot{R}}{\log
e}-\frac{1}{E}-\frac{\delta_{E}}{N_{0}}}$
$\displaystyle=\sqrt{\frac{\dot{R}}{\log e}-\delta^{\prime}_{E}}$
$\displaystyle=\sqrt{\frac{\dot{R}}{\log e}}+O(\delta^{\prime}_{E})$
$\displaystyle=\sqrt{\frac{\dot{R}}{\log e}}+O\left(\frac{1}{\sqrt{E}}\right)$

where the last step follows by noting that
$O(\delta^{\prime}_{E})=O(\delta_{E})=O(1/\sqrt{E})$. Further defining
$\delta^{\prime\prime}_{E}\triangleq\frac{\delta_{E}}{2N_{0}}-\frac{\ln
2}{E}$, we may write (107) as

$\displaystyle P_{e,1}$
$\displaystyle\geq\exp\left[-E\left(\left(\sqrt{\frac{1}{N_{0}}}-\sqrt{\frac{\dot{R}}{\log
e}}+O\left(\frac{1}{\sqrt{E}}\right)\right)^{2}+\delta^{\prime\prime}_{E}\right)\right]$
$\displaystyle=\exp\left[-E\left(\left(\sqrt{\frac{1}{N_{0}}}-\sqrt{\frac{\dot{R}}{\log
e}}\right)^{2}+O\left(\frac{1}{\sqrt{E}}\right)\right)\right]$ (108)

since $O(\delta^{\prime\prime}_{E})=O(\delta_{E})=O(1/\sqrt{E})$. By
substituting $E=\frac{\log M}{\dot{R}}$, (108) yields

$\displaystyle P_{e,1}$ $\displaystyle\geq\exp\left[-\frac{\ln
M}{\dot{R}}\left(\left(\sqrt{\frac{\log
e}{N_{0}}}-\sqrt{\dot{R}}\right)^{2}+O\left(\frac{1}{\sqrt{E}}\right)\right)\right].$
(109)

We can thus find a function $E\mapsto\beta^{\prime}_{E}$ of order
$O(1/\sqrt{E})$ for which the lower bound in (23) holds.

####  B-B3  Low-rate lower bound

We next derive a lower bound on the probability of error that applies to low
rates per unit-energy. This bound will then be used later to derive the lower
bound (22). To obtain this bound, we first derive a lower bound on $P_{e,1}$
that, for low rates per unit-energy, is tighter than (109). This bound is
based on the fact that for $M$ codewords of energy $E$, the minimum Euclidean
distance $d_{\min}$ between codewords is upper-bounded by $\sqrt{2EM/(M-1)}$
[16, Sec. 3.7.1]. Since, for the Gaussian channel, the maximum error
probability is lower-bounded by the largest pairwise error probability, it
follows that

$\displaystyle P_{e_{\max}}$ $\displaystyle\geq
Q\left(\frac{d_{\min}}{\sqrt{2N_{0}}}\right)$ $\displaystyle\geq
Q\left(\sqrt{\frac{EM}{N_{0}(M-1)}}\right)$
$\displaystyle\geq\left(1-\frac{1}{EM/(N_{0}(M-1))}\right)\frac{e^{-\frac{EM}{2N_{0}(M-1)}}}{\sqrt{2\pi}\sqrt{EM/(N_{0}(M-1))}}$
(110)

where the last inequality follows because [22, Prop. 19.4.2]

$\displaystyle
Q(\beta)\geq\left(1-\frac{1}{\beta^{2}}\right)\frac{e^{-\beta^{2}/2}}{\sqrt{2\pi}\beta},\quad\beta>0.$

Let $\beta_{E}\triangleq\sqrt{EM/N_{0}(M-1)}$. It follows that

$\displaystyle\sqrt{E/N_{0}}\leq\beta_{E}\leq\sqrt{2E/N_{0}},\quad M\geq 2.$
(111)

Applying (111) to (110) yields

$\displaystyle P_{e_{\max}}$
$\displaystyle\geq\frac{1}{\sqrt{2\pi}}\exp\left[-E\left(\frac{1}{2N_{0}}\left(1+\frac{1}{M-1}\right)\right)\right]\exp\left[\ln\left(\frac{1}{\beta_{E}}-\frac{1}{\beta_{E}^{3}}\right)\right]\
$
$\displaystyle\geq\frac{1}{\sqrt{2\pi}}\exp\left[-E\left(\frac{1}{2N_{0}}\left(1+\frac{1}{M-1}\right)\right)\right]\exp\left[-E\frac{\frac{3}{2}\ln(2E/N_{0})-\ln(E/N_{0}-1)}{E}\right]$
$\displaystyle=\exp\left[-E\left(\frac{1}{2N_{0}}\left(1+\frac{1}{M-1}\right)+O\left(\frac{\ln
E}{E}\right)\right)\right].$ (112)

Following similar steps of expurgation as before, we obtain from (112) the
lower bound

$\displaystyle P_{e,1}$
$\displaystyle\geq\exp\left[-E\left(\frac{1}{2N_{0}}\left(1+\frac{1}{\frac{M}{2}-1}\right)+O\left(\frac{\ln
E}{E}\right)\right)\right].$

By using that $M=2^{\dot{R}E}$, it follows that

$\displaystyle P_{e,1}$
$\displaystyle\geq\exp\left[-E\left(\frac{1}{2N_{0}}\left(1+\frac{1}{\frac{2^{\dot{R}E}}{2}-1}\right)+O\left(\frac{\ln
E}{E}\right)\right)\right]$ (113)

from which we obtain that, for any rate per unit-energy $\dot{R}>0$,

$\displaystyle P_{e,1}$
$\displaystyle\geq\exp\left[-E\left(\frac{1}{2N_{0}}+O\left(\frac{\ln
E}{E}\right)\right)\right].$ (114)

####  B-B4 Combining the high-rate and the low-rate bounds

We finally show that a combination of the lower bounds (108) and (113) yield
the lower bound in (22).

Let $P_{e}^{\bot}(E,M)$ denote the smallest probability of error that can be
achieved by an orthogonal codebook with $M$ codewords of energy $E$. We first
note that $P_{e}^{\bot}(E,M)$ is monotonically increasing in $M$. Indeed,
without loss of optimality, we can restrict ourselves to codewords of the form
(97), all having energy $E$. In this case, the probability of correctly
decoding message $m$ is given by [18, Sec. 8.2]

$\displaystyle P_{c,m}^{\bot}$
$\displaystyle=\textnormal{Pr}\biggl{(}\bigcap_{i\neq
m}\\{Y_{m}>Y_{i}\\}\biggm{|}{\bf X}={\bf x}_{m}\biggr{)}$
$\displaystyle=\frac{1}{\sqrt{\pi
N_{0}}}\int_{-\infty}^{\infty}\exp\left[\frac{(y_{m}-\sqrt{E})^{2}}{N_{0}}\right]\textnormal{Pr}\biggl{(}\bigcap_{i\neq
m}\\{Y_{i}<y_{m}\\}\biggm{|}{\bf X}={\bf x}_{m}\biggr{)}dy_{m}$
$\displaystyle=\frac{1}{\sqrt{\pi
N_{0}}}\int_{-\infty}^{\infty}\exp\left[\frac{(y_{m}-\sqrt{E})^{2}}{N_{0}}\right]\left(1-Q(y_{m})\right)^{M-1}dy_{m}$
(115)

where $Y_{i}$ denotes the $i$-th component of the received vector ${\bf Y}$.
In the last step of (115), we have used that, conditioned on ${\bf X}={\bf
x}_{m}$, the events $\\{Y_{i}<y_{m}\\}$, $i\neq m$ are independent and
$\textnormal{Pr}(Y_{i}<y_{m}|{\bf X}={\bf x}_{m})$ can be computed as
$1-Q(y_{m})$. Since $P_{c,m}^{\bot}$ is the same for all $m$, we have
$P_{e}^{\bot}(E,M)=1-P_{c,m}^{\bot}$. The claim then follows by observing that
(115) is monotonically decreasing in $M$.

Let $\tilde{M}$ be the largest power of 2 less than or equal to $M$. It
follows by the monotonicity of $P_{e}^{\bot}(E,M)$ in M that

$\displaystyle P_{e}^{\bot}(E,M)\geq P_{e}^{\bot}(E,\tilde{M}).$ (116)

We next show that, for every $E_{1}$ and $E_{2}$ satisfying $E=E_{1}+E_{2}$,
we have

$\displaystyle P_{e}^{\bot}(E,\tilde{M})\geq
P_{e}(E_{1},\tilde{M},L)P_{e}(E_{2},L+1)$ (117)

where $P_{e}(E_{1},\tilde{M},L)$ denotes the smallest probability of error
that can be achieved by a codebook with $\tilde{M}$ codewords of energy
$E_{1}$ and a list decoder of list size $L$, and $P_{e}(E_{2},L+1)$ denotes
the smallest probability of error that can be achieved by a codebook with
$L+1$ codewords of energy $E_{2}$.

To prove (117), we follow along the lines of [15], which showed the
corresponding result for codebooks of a given blocklength rather than a given
energy. Specifically, it was shown in [15, Th. 1] that, for every codebook
$\cal{C}$ with $M$ codewords of blocklength $n$, and for any $n_{1}$ and
$n_{2}$ satisfying $n=n_{1}+n_{2}$, we can lower-bound the probability of
error by

$P_{e}(\mbox{$\cal{C}$})\geq P_{e}(n_{1},M,L)P_{e}(n_{2},L+1)$ (118)

where $P_{e}(n_{1},M,L)$ denotes the smallest probability of error that can be
achieved by a codebook with $M$ codewords of blocklength $n_{1}$ and a list
decoder of list size $L$, and $P_{e}(n_{2},L+1)$ denotes the smallest
probability of error that can be achieved by a codebook with $L+1$ codewords
of blocklength $n_{2}$. This result follows by writing the codewords ${\bf
x}_{m}$ of blocklength $n$ as concatenations of the vectors

$\displaystyle{\bf x}^{\prime}_{m}=(x_{m,1},x_{m,2},\ldots,x_{m,n_{1}})$

and

$\displaystyle{\bf
x}^{\prime\prime}_{m}=(x_{m,n_{1}+1},x_{m,n_{1}+2},\ldots,x_{m,n_{1}+n_{2}})$

and, likewise, by writing the received vector ${\bf y}$ as the concatenation
of the vectors ${\bf y}^{\prime}$ and ${\bf y}^{\prime\prime}$ of length
$n_{1}$ and $n_{2}$, respectively. Defining $\Delta_{m}$ as the decoding
region for message $m$ and $\Delta^{\prime\prime}_{m}({\bf y}^{\prime})$ as
the decoding region for message $m$ when ${\bf y}^{\prime}$ was received, we
can then write $P_{e}(\mbox{$\cal{C}$})$ as

$\displaystyle P_{e}(\mbox{$\cal{C}$})$
$\displaystyle=\frac{1}{M}\sum_{m=1}^{M}\sum_{{\bf y}^{\prime}}p({\bf
y}^{\prime}|{\bf x}^{\prime}_{m})\sum_{{\bf
y}^{\prime\prime}\in\bar{\Delta}^{\prime\prime}_{m}}p({\bf
y}^{\prime\prime}|{\bf x}^{\prime\prime}_{m})$ (119)

where $\bar{\Delta}^{\prime\prime}_{m}$ denotes the complement of
$\Delta^{\prime\prime}_{m}$. Lower-bounding first the inner-most sum in (119)
and then the remaining terms, one can prove (118).

A codebook with $\tilde{M}$ codewords of the form (97) can be transmitted in
$\tilde{M}$ time instants, since in the remaining time instants all codewords
are zero. We can thus assume without loss of optimality that the codebook’s
blocklength is $\tilde{M}$. Unfortunately, when the codewords are of the form
(97), the above approach yields (117) only in the trivial cases where either
$E_{1}=0$ or $E_{2}=0$. Indeed, $E_{1}$ and $E_{2}$ correspond to the energies
of the vectors ${\bf x}^{\prime}_{m}$ and ${\bf x}^{\prime\prime}_{m}$,
respectively, and for (97) we have ${\bf x}^{\prime}_{m}=\mathbf{0}$ if
$m>n_{1}$ and ${\bf x}^{\prime\prime}_{m}=\mathbf{0}$ if $m\leq n_{1}$, where
$\mathbf{0}$ denotes the all-zero vector. We sidestep this problem by
multiplying the codewords by a normalized Hadamard matrix. The Hadamard
matrix, denoted by $H_{j}$, is a square matrix of size $j\times j$ with
entries $\pm 1$ and has the property that all rows are orthogonal. Sylvester’s
construction shows that there exists a Hadamard matrix of order $j$ if $j$ is
a power of 2. Recalling that $\tilde{M}$ is a power of $2$, we can thus find a
normalized Hadamard matrix

$\tilde{H}\triangleq\frac{1}{\sqrt{\tilde{M}}}H_{\tilde{M}}.$

Since the rows of $\tilde{H}$ are orthonormal, it follows that the matrix
$\tilde{H}$ is orthogonal. Further noting that the additive Gaussian noise
${\bf Z}$ is zero mean and has a diagonal covariance matrix, we conclude that
the set of codewords $\\{\tilde{H}{\bf x}_{m},\,m=1,\ldots,\tilde{M}\\}$
achieve the same probability of error as the set of codewords $\\{{\bf
x}_{m},\,m=1,\ldots,\tilde{M}\\}$. Thus, without loss of generality, we can
restrict ourselves to codewords of the form $\tilde{{\bf x}}_{m}=\tilde{H}{\bf
x}_{m}$, where ${\bf x}_{m}$ is as in (97). Such codewords have constant
modulus, i.e.,
$|\tilde{x}_{m,k}|=\sqrt{\frac{E}{\tilde{M}}},k=1,\ldots,\tilde{M}$. This has
the advantage that the energies of the vectors

$\displaystyle\tilde{{\bf
x}}^{\prime}_{m}=(\tilde{x}_{m,1},\tilde{x}_{m,2},\ldots,\tilde{x}_{m,n_{1}})$

and

$\displaystyle\tilde{{\bf
x}}^{\prime\prime}_{m}=(\tilde{x}_{m,n_{1}+1},\tilde{x}_{m,n_{1}+2},\ldots,\tilde{x}_{m,n_{1}+n_{2}})$

are proportional to $n_{1}$ and $n_{2}$, respectively. Thus, by emulating the
proof of (118), we can show that for every $n_{1}$ and $n_{2}$ satisfying
$\tilde{M}=n_{1}+n_{2}$ and $E_{i}=En_{i}/\tilde{M}$, $i=1,2$, we have

$P_{e}^{\bot}(E,\tilde{M})\geq
P_{e}(E_{1},n_{1},\tilde{M},L)P_{e}(E_{2},n_{2},L+1)$ (120)

where $P_{e}(E_{1},n_{1},\tilde{M},L)$ denotes the smallest probability of
error that can be achieved by a codebook with $\tilde{M}$ codewords of energy
$E_{1}$ and blocklength $n_{1}$ and a list decoder of list size $L$, and
$P_{e}(E_{2},n_{2},L+1)$ denotes the smallest probability of error that can be
achieved by a codebook with $L+1$ codewords of energy $E_{2}$ and blocklength
$n_{2}$. We then obtain (117) from (120) because

$P_{e}(E_{1},n_{1},\tilde{M},L)\geq
P_{e}(E_{1},\tilde{M},L)\quad\textnormal{and}\quad P_{e}(E_{2},n_{2},L+1)\geq
P_{e}(E_{2},L+1).$

We next give a lower bound on $P_{e}(E_{1},\tilde{M},L)$. Indeed, for list
decoding of list size $L$, the inequalities (98) and (99) can be replaced by
[16, Lemma 3.8.1]

$\displaystyle L/M$
$\displaystyle\geq\frac{1}{4}\exp\left[\mu(s)-s\mu^{\prime}(s)-s\sqrt{2\mu^{\prime\prime}(s)}\right]$
(121) $\displaystyle P_{e_{\max}}$
$\displaystyle\geq\frac{1}{4}\exp\left[\mu(s)+(1-s)\mu^{\prime}(s)-(1-s)\sqrt{2\mu^{\prime\prime}(s)}\right].$
(122)

Let $\dot{R}_{1}\triangleq\frac{\log(M/L)}{E_{1}}$ and
$\tilde{\dot{R}}_{1}\triangleq\frac{\log(\tilde{M}/L)}{E_{1}}$. From the
definition of $\tilde{M}$, we have $\tilde{M}\leq M\leq 2\tilde{M}$.
Consequently,

$\displaystyle\dot{R}_{1}-\frac{1}{E_{1}}\leq\tilde{\dot{R}}_{1}\leq\dot{R}_{1}.$
(123)

By following the steps that led to (108), we thus obtain

$\displaystyle P_{e}(E_{1},\tilde{M},L)$
$\displaystyle\geq\exp\left[-E_{1}\left(\left(\sqrt{\frac{1}{N_{0}}}-\sqrt{\frac{\tilde{\dot{R}}_{1}}{\log
e}}\right)^{2}+O\left(\frac{1}{\sqrt{E_{1}}}\right)\right)\right]$
$\displaystyle=\exp\left[-E_{1}\left(\left(\sqrt{\frac{1}{N_{0}}}-\sqrt{\frac{\dot{R}_{1}}{\log
e}}\right)^{2}+O\left(\frac{1}{\sqrt{E_{1}}}\right)\right)\right].$ (124)

To lower-bound $P_{e}(E_{2},L+1)$, we apply (113) with
$\dot{R}_{2}\triangleq\frac{\log(L+1)}{E_{2}}$. This yields

$\displaystyle P_{e}(E_{2},L+1)$
$\displaystyle\geq\exp\left[-E_{2}\left(\frac{1}{2N_{0}}\left(1+\frac{1}{\frac{2^{\dot{R}_{2}E_{2}}}{2}-1}\right)+O\left(\frac{\ln
E_{2}}{E_{2}}\right)\right)\right].$ (125)

Let

$\Xi_{1}(\dot{R}_{1})\triangleq\left(\sqrt{\frac{1}{N_{0}}}-\sqrt{\frac{\dot{R}_{1}}{\log
e}}\right)^{2}$

and

$\Xi_{2}(\dot{R}_{2})\triangleq\frac{1}{2N_{0}}\left(1+\frac{1}{\frac{2^{\dot{R}_{2}E_{2}}}{2}-1}\right).$

Then, by substituting (124) and (125) in (117), and by using (116), we get

$\displaystyle P_{e}^{\bot}(E,M)$
$\displaystyle\geq\exp\left[-E_{1}\left(\Xi_{1}(\dot{R}_{1})+O\left(\frac{1}{\sqrt{E_{1}}}\right)\right)\right]\exp\left[-E_{2}\left(\Xi_{2}(\dot{R}_{2})+O\left(\frac{\ln
E_{2}}{E_{2}}\right)\right)\right].$ (126)

Applying (126) with a clever choice of $E_{1}$ and $E_{2}$, we can show that
the error exponent of $P_{e}^{\bot}(E,M)$ is upper-bounded by a convex
combination of $\Xi_{1}(\dot{R}_{1})$ and $\Xi_{2}(\dot{R}_{2})$. Indeed, let
$\lambda\triangleq\frac{E_{1}}{E}$. Then, (126) can be written as

$\displaystyle
P_{e}^{\bot}(E,M)\geq\exp\left[-E\left(\lambda\Xi_{1}(\dot{R}_{1})+(1-\lambda)\Xi_{2}(\dot{R}_{2})+O\left(\frac{1}{\sqrt{E}}\right)\right)\right]$
(127)

and

$\displaystyle\frac{\log M}{E}$ $\displaystyle=\frac{\log(M/L)+\log L}{E}$
$\displaystyle=\lambda\frac{\log(M/L)}{E_{1}}+(1-\lambda)\frac{\log L}{E_{2}}$
$\displaystyle=\lambda\dot{R}_{1}+(1-\lambda)\dot{R}_{2}.$

Let $\dot{R}\triangleq\frac{\log M}{E}\leq\frac{\log e}{4N_{0}}$ and
$\gamma_{E}\triangleq\min\left\\{\frac{1}{\sqrt{E}},\frac{\dot{R}}{2}\right\\}$.
We conclude the proof of the lower bound in (22) by choosing in (127)

$\displaystyle\lambda_{E}=\lambda_{E}$
$\displaystyle\triangleq\frac{\dot{R}-\gamma_{E}}{\frac{\log
e}{4N_{0}}-\gamma_{E}}$

and the rates per unit-energy $\dot{R}_{1}=\frac{1}{4}\frac{\log e}{N_{0}}$
and $\dot{R}_{2}=\gamma_{E}$. It follows that

$\displaystyle P_{e}^{\bot}(E,M)$
$\displaystyle\geq\exp\left[-E\left(\frac{\lambda_{E}}{4N_{0}}+\frac{1-\lambda_{E}}{2N_{0}}+\frac{1-\lambda_{E}}{2N_{0}(\frac{2^{\gamma_{E}(1-\lambda_{E})E}}{2}-1)}+O\left(\frac{1}{\sqrt{E}}\right)\right)\right]$
$\displaystyle=\exp\left[-E\left(\frac{1}{2N_{0}}-\frac{\lambda_{E}}{4N_{0}}+\frac{1-\lambda_{E}}{2N_{0}(\frac{2^{\gamma_{E}(1-\lambda_{E})E}}{2}-1)}+O\left(\frac{1}{\sqrt{E}}\right)\right)\right].$
(128)

Noting that $\lambda_{E}=\frac{\dot{R}}{(\log
e)/4N_{0}}+O\left(\frac{1}{\sqrt{E}}\right)$, and that
$\frac{1}{2^{\gamma_{E}(1-\lambda_{E})E}}=O(1/\sqrt{E})$, (128) can be written
as

$\displaystyle
P_{e}^{\bot}(E,M)\geq\exp\left[-E\left(\frac{1}{2N_{0}}-\frac{\dot{R}}{\log
e}+O\left(\frac{1}{\sqrt{E}}\right)\right)\right],\quad
0<\dot{R}\leq\frac{1}{4}\frac{\log e}{N_{0}}.$ (129)

We can thus find a function $E\mapsto\beta_{E}$ of order $O(1/\sqrt{E})$ for
which the lower bound in (22) holds.

##  Appendix C Proof of Lemma 10

To prove Lemma 10, we treat the cases where $\ell_{n}=O(1)$ and where
$\ell_{n}=\omega(1)$ separately. In the former case, each user is assigned an
exclusive channel use to convey whether it is active or not. The probability
of a detection error $P(\mbox{$\cal{D}$})$ can then be analyzed by similar
steps as in the proof of Theorem 8. In the latter case, we proceed similarly
as in the proof of [1, Th. 2]. That is, we draw signatures i.i.d. at random
according to a zero-mean Gaussian distribution, followed by a truncation step
to ensure that the energy of each signature is upper-bounded by
$E_{n}^{\prime\prime}$. The decoder then produces a vector of length
$\ell_{n}$ with zeros and ones, where a one in the $i$-th position indicates
that user $i$ is active. To this end, it chooses the vector that, among all
zero-one vectors with not more than a predefined number of ones, approximates
the received symbols best in terms of Euclidean distance. The probability of a
detection error probability $P(\mbox{$\cal{D}$})$ can then be analyzed by
following similar steps as in the proof of [1, Th. 2].

###  C-A Bounded $\ell_{n}$

We first prove the lemma when $\ell_{n}$ is bounded in $n$. In this case, one
can employ a scheme where each user gets an exclusive channel use to convey
whether it is active or not. For such a scheme, it is easy to show that (see
the proof of Theorem 8) the probability of a detection error
$P(\mbox{$\cal{D}$})$ is upper-bounded by

$\displaystyle P(\mbox{$\cal{D}$})$
$\displaystyle\leq\ell_{n}e^{-E_{n}^{\prime\prime}t}$

for some $t>0$. Clearly, when $\ell_{n}$ is bounded, we have
$k_{n}\log\ell_{n}=o(n)$. Thus, the energy $E_{n}^{\prime\prime}$ used for
detection is given by $bc_{n}\ln\ell_{n}$ and tends to infinity since
$c_{n}\to\infty$ as $n\to\infty$. It follows that $P(\mbox{$\cal{D}$})$ tends
to zero as $n\to\infty$.

###  C-B Unbounded $\ell_{n}$

Next we prove Lemma 10 for the case where $\ell_{n}\to\infty$ as $n\to\infty$.
To this end, we closely follow the proof of [1, Th. 2], but with the power
constraint replaced by an energy constraint. Specifically, we analyze
$P(\mbox{$\cal{D}$})$ for the user-detection scheme given in [1], where
signatures are drawn i.i.d. according to a zero-mean Gaussian distribution.
Note that the proof in [1] assumes that

$\displaystyle\lim\limits_{n\to\infty}\ell_{n}e^{-\delta k_{n}}=0$ (130)

for all $\delta>0$. However, in our case this assumption is not necessary.

To show that all signatures satisfy the energy constraint, we follow the
technique used in the proof of Lemma 11. Similar to Lemma 11, we denote by
$\tilde{q}(\cdot)$ the probability density function of a zero-mean Gaussian
random variable with variance $E_{n}^{\prime\prime}/(2n^{\prime\prime})$. We
further let

$\displaystyle\tilde{{\bf q}}({\bf u})$
$\displaystyle=\prod_{i=1}^{n^{\prime\prime}}\tilde{q}(u_{i}),\quad{\bf
u}=(u_{1},\ldots,u_{n^{\prime\prime}})$

and

$\displaystyle{\bf q}({\bf u})$ $\displaystyle=\frac{1}{\mu}\mathbf{1}(\|{\bf
u}\|^{2}\leq E_{n}^{\prime\prime})\tilde{{\bf q}}({\bf u})$

where

$\displaystyle\mu$ $\displaystyle=\int\mathbf{1}(\|{\bf u}\|^{2}\leq
E_{n}^{\prime\prime})\;\tilde{{\bf q}}({\bf u})d{\bf u}$

is a normalizing constant. Clearly, any vector ${\bf S}_{i}$ distributed
according to ${\bf q}(\cdot)$ satisfies the energy constraint
$E^{\prime\prime}_{n}$ with probability one. For any index set
$\mbox{$\cal{I}$}\subseteq\\{1,\ldots,\ell_{n}\\}$, let the matrices
$\underline{{\bf S}}_{\mbox{$\cal{I}$}}$ and $\tilde{\underline{{\bf
S}}}_{\mbox{$\cal{I}$}}$ denote the set of signatures for the users in
$\cal{I}$ that are distributed respectively as

$\displaystyle\underline{{\bf S}}_{\mbox{$\cal{I}$}}$
$\displaystyle\sim\prod_{i\in I}{\bf q}({\bf S}_{i})$

and

$\displaystyle\tilde{\underline{{\bf S}}}_{\mbox{$\cal{I}$}}$
$\displaystyle\sim\prod_{i\in I}\tilde{{\bf q}}({\bf S}_{i}).$

As noted in the proof of Lemma 11, we have

$\displaystyle{\bf q}({\bf s}_{i})$ $\displaystyle\leq\frac{1}{\mu}\tilde{{\bf
q}}({\bf s}_{i}).$ (131)

To analyze the detection error probability, we first define the
$\ell_{n}$-length vector ${\bf D}^{a}$ as

$\displaystyle{\bf D}^{a}\triangleq(\mathbf{1}(W_{1}\neq
0),\ldots,\mathbf{1}(W_{\ell_{n}}\neq 0)).$

For some $c^{\prime\prime}>0$, let

$\displaystyle v_{n}\triangleq k_{n}(1+c^{\prime\prime}).$

Further let

$\displaystyle\mbox{$\cal{B}$}^{n}(v_{n})\triangleq\\{{\bf
d}\in\\{0,1\\}^{\ell_{n}}:1\leq|{\bf d}|\leq v_{n}\\}$

where $|{\bf d}|$ denotes the number of $1$’s in ${\bf d}$. We denote by ${\bf
S}^{a}$ the matrix of signatures of all users, which are generated
independently according to ${\bf q}(\cdot)$, and we denote by $\mathbf{Y}^{a}$
the first $n^{\prime\prime}$ received symbols, based on which the receiver
performs user detection. The receiver outputs the $\hat{{\bf d}}$ given by

$\displaystyle\hat{{\bf d}}=\mathrm{arg\,min}_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\|{\bf Y}^{a}-{\bf S}^{a}{\bf d}\|$ (132)

as a length-$\ell_{n}$ vector guessing the set of active users. By the union
bound, the probability of a detection error $P(\mbox{$\cal{D}$})$ is upper-
bounded by

$\displaystyle P(\mbox{$\cal{D}$})$ $\displaystyle\leq\text{Pr}(|{\bf
D}^{a}|>v_{n})+\sum_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\text{Pr}(\mbox{$\cal{E}$}_{d}|{\bf
D}^{a}={\bf d})\text{Pr}({\bf D}^{a}={\bf
d})+\text{Pr}(\mbox{$\cal{E}$}_{d}||{\bf D}^{a}|=0)\text{Pr}(|{\bf D}^{a}|=0)$
(133)

where $|{\bf D}^{a}|$ denotes the number of $1$’s in ${\bf D}^{a}$ and
$\mbox{$\cal{E}$}_{d}$ denotes the event that there is a detection error.
Next, we show that each term on the RHS of (133) vanishes as $n\to\infty$.

Using the Chernoff bound for the binomial distribution, we have

$\displaystyle\text{Pr}(|{\bf D}^{a}|>v_{n})$
$\displaystyle\leq\exp(-k_{n}c^{\prime\prime}/3)$ (134)

which vanishes as $n\to\infty$ if $k_{n}$ is unbounded. For bounded $k_{n}$,
this probability of error vanishes by first letting $n\to\infty$ and then
letting $c^{\prime\prime}\to\infty$.

We continue with the term $\text{Pr}(\mbox{$\cal{E}$}_{d}|{\bf D}^{a}={\bf
d})$. For a given ${\bf D}^{a}={\bf d}$, let $\kappa_{1}$ and $\kappa_{2}$
denote the number of miss detections and false alarms, respectively, i.e.,

$\displaystyle\kappa_{1}$ $\displaystyle=|\\{j:d_{j}\neq 0,\hat{d}_{j}=0\\}|$
$\displaystyle\kappa_{2}$ $\displaystyle=|\\{j:d_{j}=0,\hat{d}_{j}\neq 0\\}|$

where $d_{j}$ and $\hat{d}_{j}$ denote the $j$-th components of the vectors
${\bf d}$ and $\hat{{\bf d}}$, respectively. An error happens only if either
$\kappa_{1}$, or $\kappa_{2}$, or both are strictly positive. The number of
users that are either active or are declared as active by the receiver
satisfies $|{\bf d}|+\kappa_{2}=|\hat{{\bf d}}|+\kappa_{1}$, so

$\displaystyle|{\bf d}|+\kappa_{2}$ $\displaystyle\leq v_{n}+\kappa_{1}$

since $|\hat{{\bf d}}|$ is upper-bounded by $v_{n}$ by the decoding rule
(132). So, the pair $(\kappa_{1},\kappa_{2})$ belongs to the following set:

$\displaystyle\mbox{$\cal{W}$}^{\ell_{n}}_{{\bf d}}=$
$\displaystyle\left\\{(\kappa_{1},\kappa_{2}):\kappa_{1}\in\\{0,1,\ldots,|{\bf
d}|\\},\kappa_{2}\in\\{0,1,\ldots,v_{n}\\},\kappa_{1}+\kappa_{2}\geq 1,|{\bf
d}|+\kappa_{2}\leq v_{n}+\kappa_{1}\right\\}.$ (135)

Let $\text{Pr}(\mbox{$\cal{E}$}_{\kappa_{1},\kappa_{2}}|{\bf D}^{a}={\bf d})$
be the probability of having exactly $\kappa_{1}$ miss detections and
$\kappa_{2}$ false alarms when ${\bf D}^{a}={\bf d}$. For given ${\bf d}$ and
$\hat{{\bf d}}$, let $\mbox{$\cal{A}$}^{*}\triangleq\\{j:d_{j}\neq 0\\}$ and
$\mbox{$\cal{A}$}\triangleq\\{j:\hat{d}_{j}\neq 0\\}$. We further define
$\mbox{$\cal{A}$}_{1}\triangleq\mbox{$\cal{A}$}^{*}\setminus\mbox{$\cal{A}$}$,
$\mbox{$\cal{A}$}_{2}\triangleq\mbox{$\cal{A}$}\setminus\mbox{$\cal{A}$}^{*}$,
and

$\displaystyle T_{\mbox{$\cal{A}$}}$ $\displaystyle\triangleq\|{\bf
Y}^{a}-\sum_{j\in\mbox{$\cal{A}$}}{\bf S}_{j}\|^{2}-\|{\bf
Y}^{a}-\sum_{j\in\mbox{$\cal{A}$}^{*}}{\bf S}_{j}\|^{2}.$

Using the analysis that led to [1, eq. (67)], we obtain

$\displaystyle\text{Pr}(\mbox{$\cal{E}$}_{\kappa_{1},\kappa_{2}}|{\bf
D}^{a}={\bf d})$
$\displaystyle\leq\binom{|\mbox{$\cal{A}$}^{*}|}{\kappa_{1}}\binom{\ell_{n}}{\kappa_{2}}\mathrm{E}_{\underline{{\bf
S}}_{\mbox{$\cal{A}$}^{*}},{\bf Y}}\\{[\mathrm{E}_{\underline{{\bf
S}}_{\mbox{$\cal{A}$}_{2}}}\\{\mathbf{1}(T_{\mbox{$\cal{A}$}}\leq
0)|\underline{{\bf S}}_{\mbox{$\cal{A}$}^{*}},{\bf Y}\\}]^{\rho}|\\}$
$\displaystyle\leq\binom{|\mbox{$\cal{A}$}^{*}|}{\kappa_{1}}\binom{\ell_{n}}{\kappa_{2}}\left(\frac{1}{\mu}\right)^{\rho\kappa_{2}}\mathrm{E}_{\underline{{\bf
S}}_{\mbox{$\cal{A}$}^{*}},{\bf Y}}\\{[\mathrm{E}_{\underline{\tilde{{\bf
S}}}_{\mbox{$\cal{A}$}_{2}}}\\{\mathbf{1}(T_{\mbox{$\cal{A}$}}\leq
0)|\underline{{\bf S}}_{\mbox{$\cal{A}$}^{*}},{\bf Y}\\}]^{\rho}\\}$
$\displaystyle\leq\binom{|\mbox{$\cal{A}$}^{*}|}{\kappa_{1}}\binom{\ell_{n}}{\kappa_{2}}\left(\frac{1}{\mu}\right)^{|\mbox{$\cal{A}$}^{*}|}\left(\frac{1}{\mu}\right)^{\rho\kappa_{2}}\mathrm{E}_{\underline{\tilde{{\bf
S}}}_{\mbox{$\cal{A}$}^{*}},{\bf Y}}\\{[\mathrm{E}_{\underline{\tilde{{\bf
S}}}_{\mbox{$\cal{A}$}_{2}}}\\{\mathbf{1}(T_{\mbox{$\cal{A}$}}\leq
0)|\underline{\tilde{{\bf S}}}_{\mbox{$\cal{A}$}^{*}},{\bf Y}\\}]^{\rho}\\}$
(136)

where in the second inequality we used that

$\displaystyle{\bf q}(\underline{{\bf
s}}_{\mbox{$\cal{A}$}_{2}})\leq\left(\frac{1}{\mu}\right)^{\kappa_{2}}\prod_{i\in\mbox{$\cal{A}$}_{2}}\tilde{{\bf
q}}({\bf s}_{i})$ (137)

and in the third inequality we used that

$\displaystyle{\bf q}(\underline{{\bf
s}}_{\mbox{$\cal{A}$}^{*}})\leq\left(\frac{1}{\mu}\right)^{|\mbox{$\cal{A}$}^{*}|}\prod_{i\in\mbox{$\cal{A}$}^{*}}\tilde{{\bf
q}}({\bf s}_{i}).$ (138)

Here, (137) and (138) follow from (131).

For every $\rho\in[0,1]$ and $\lambda\geq 0$, we obtain from [1, eq. (78)]
that

$\displaystyle\binom{|\mbox{$\cal{A}$}^{*}|}{\kappa_{1}}\binom{\ell_{n}}{\kappa_{2}}\mathrm{E}_{\underline{\tilde{{\bf
S}}}_{\mbox{$\cal{A}$}^{*}},{\bf Y}}\\{[\mathrm{E}_{\underline{\tilde{{\bf
S}}}_{\mbox{$\cal{A}$}_{2}}}\\{\mathbf{1}(T_{\mbox{$\cal{A}$}}\leq
0)|\underline{\tilde{{\bf S}}}_{\mbox{$\cal{A}$}^{*}},{\bf Y}\\}]^{\rho}\\}$
$\displaystyle\leq\exp[-\tilde{E}_{n}g^{n}_{\lambda,\rho}(\kappa_{1},\kappa_{2},{\bf
d})]$ (139)

where

$\displaystyle\tilde{E}_{n}\triangleq$ $\displaystyle E_{n}^{\prime\prime}/2,$
$\displaystyle g^{n}_{\lambda,\rho}(\kappa_{1},\kappa_{2},{\bf d})\triangleq$
$\displaystyle-\frac{(1-\rho)n^{\prime\prime}}{2\tilde{E}_{n}}\log(1+\lambda\kappa_{2}\tilde{E}_{n}/n^{\prime\prime})+\frac{n^{\prime\prime}}{2\tilde{E}_{n}}\log\left(1+\lambda(1-\lambda\rho)\kappa_{2}\tilde{E}_{n}/n^{\prime\prime}+\lambda\rho(1-\lambda\rho)\kappa_{1}\tilde{E}_{n}/n^{\prime\prime}\right)$
$\displaystyle-\frac{|{\bf
d}|}{\tilde{E}_{n}}H_{2}\left(\frac{\kappa_{1}}{|{\bf
d}|}\right)-\frac{\rho\ell_{n}}{\tilde{E}_{n}}H_{2}\left(\frac{\kappa_{2}}{\ell_{n}}\right).$
(140)

It thus follows from (136) and (139) that

$\displaystyle\text{Pr}(\mbox{$\cal{E}$}_{\kappa_{1},\kappa_{2}}|{\bf
D}^{a}={\bf d})$
$\displaystyle\leq\left(\frac{1}{\mu}\right)^{|\mbox{$\cal{A}$}^{*}|+\rho\kappa_{2}}\exp[-\tilde{E}_{n}g^{n}_{\lambda,\rho}(\kappa_{1},\kappa_{2},{\bf
d})].$ (141)

We next show that the RHS of (141) vanishes as $n\to\infty$. To this end, we
first show that
$\left(\frac{1}{\mu}\right)^{|\mbox{$\cal{A}$}^{*}|+\rho\kappa_{2}}\to 1$ as
$n\to\infty$ uniformly in
$(\kappa_{1},\kappa_{2})\in\mbox{$\cal{W}$}^{\ell_{n}}_{{\bf d}}$ and ${\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})$. From the definition of $\mu$, we have

$\displaystyle\mu$ $\displaystyle=1-\text{Pr}\left(\|\tilde{{\bf
S}}_{1}\|_{2}^{2}>E_{n}^{\prime\prime}\right).$

Furthermore, by defining $\tilde{{\bf
S}}_{0}\triangleq\frac{2n^{\prime\prime}}{E_{n}^{\prime\prime}}\|\tilde{{\bf
S}}_{1}\|_{2}^{2}$ and following the steps that led to (44), we obtain that,
for $(\kappa_{1},\kappa_{2})\in\mbox{$\cal{W}$}^{\ell_{n}}_{{\bf d}}$ and
${\bf d}\in\mbox{$\cal{B}$}^{n}(v_{n})$,

$\displaystyle 1$
$\displaystyle\leq\left(\frac{1}{\mu}\right)^{|\mbox{$\cal{A}$}^{*}|+\rho\kappa_{2}}$
$\displaystyle\leq{\color[rgb]{0,0,0}\left(\frac{1}{\mu}\right)^{2v_{n}}}$
$\displaystyle\leq{\color[rgb]{0,0,0}\left(1-\exp\left[-\frac{n^{\prime\prime}}{2}\tau\right]\right)^{-2v_{n}}}$
(142)

where $\tau=(1-\ln 2)$. Here, in the second inequality we used that
$|\mbox{$\cal{A}$}^{*}|=|{\bf d}|\leq v_{n}$ and $\rho\kappa_{2}\leq v_{n}$.
Since $k_{n}\log\ell_{n}=O(n)$, we have $k_{n}=o(n)$. This implies that, for
every fixed $c^{\prime\prime}>0$, we have $v_{n}=o(n)$ because
$v_{n}=\Theta(k_{n})$. Furthermore, $n^{\prime\prime}=\Theta(n)$. As noted
before, for any two non-negative sequences $\\{a_{n}\\}$ and $\\{b_{n}\\}$
satisfying $a_{n}\to 0$ and $a_{n}b_{n}\to 0$ as $n\to\infty$, it holds that
$(1-a_{n})^{-b_{n}}\to 1$ as $n\to\infty$. It follows that the RHS of (142)
tends to one as $n\to\infty$ uniformly in
$(\kappa_{1},\kappa_{2})\in\mbox{$\cal{W}$}_{{\bf d}}^{\ell_{n}}$ and ${\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})$. Consequently, there exists a positive
constant $n_{0}$ that is independent of $\kappa_{1}$, $\kappa_{2}$, and ${\bf
d}$ and satisfies

$\displaystyle\left(\frac{1}{\mu}\right)^{|\mbox{$\cal{A}$}^{*}|+\rho\kappa_{2}}$
$\displaystyle\leq 2,\quad(\kappa_{1},\kappa_{2})\in\mbox{$\cal{W}$}_{{\bf
d}}^{\ell_{n}},{\bf d}\in\mbox{$\cal{B}$}^{n}(v_{n}),n\geq n_{0}.$ (143)

To bound the exponential term on the RHS of (141), we need the following
lemma.

###### Lemma 14

If $k_{n}\log\ell_{n}=O(n)$, and if $c^{\prime}$ and $c^{\prime\prime}$ are
sufficiently large, then there exist two positive constants $\gamma>0$ and
$n^{\prime}_{0}$ such that
$g^{n}_{\frac{2}{3},\frac{3}{4}}(\kappa_{1},\kappa_{2},{\bf d})$, i.e., (140)
evaluated at $\lambda=2/3$ and $\rho=3/4$, satisfies

$\displaystyle\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{(\kappa_{1},\kappa_{2})\in\mbox{$\cal{W}$}^{\ell_{n}}_{{\bf
d}}}g^{n}_{\frac{2}{3},\frac{3}{4}}(\kappa_{1},\kappa_{2},{\bf
d})\geq\gamma,\quad n\geq n^{\prime}_{0}.$ (144)

###### Proof:

See Appendix C-C. ∎

Lemma 14 implies that $\text{Pr}(\mbox{$\cal{E}$}_{\kappa_{1},\kappa_{2}}|{\bf
D}^{a}=\ {\bf d})$ vanishes as $n\to\infty$ uniformly in ${\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})$. Indeed, if ${\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})$, then $|{\bf d}|\leq v_{n}$, which implies
that $\kappa_{1}\leq v_{n}$. Furthermore, since the decoder outputs a vector
in $\mbox{$\cal{B}$}^{n}(v_{n})$, we also have $\kappa_{2}\leq v_{n}$. It thus
follows from (141), (143), and (144) that

$\displaystyle\text{Pr}(\mbox{$\cal{E}$}_{d}|{\bf D}^{a}=\ {\bf d})$
$\displaystyle=\sum_{(\kappa_{1},\kappa_{2})\in\mathcal{W}_{d}^{\ell_{n}}}\text{Pr}(\mbox{$\cal{E}$}_{\kappa_{1},\kappa_{2}}|{\bf
D}^{a}=\ {\bf d})$ $\displaystyle\leq 2v_{n}^{2}\exp[-\tilde{E}_{n}\gamma]$
$\displaystyle=2\exp\left[-\tilde{E}_{n}\left(\gamma-\frac{2\ln
v_{n}}{\tilde{E}_{n}}\right)\right],\quad{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n}),n\geq\max(n_{0},n^{\prime}_{0}).$ (145)

By the definition of $v_{n}$ and $\tilde{E}_{n}$,

$\frac{2\ln
v_{n}}{\tilde{E}_{n}}=\frac{4\ln(1+c^{\prime\prime})}{bc_{n}\ln\ell_{n}}+\frac{4\ln
k_{n}}{bc_{n}\ln\ell_{n}}.$ (146)

The first term on the RHS of (146) vanishes as $n\to\infty$ since $\ell_{n}$
is unbounded. The second term on the RHS of (146) is upper-bounded by
$4/(bc_{n})$ since $\ln k_{n}\leq\ln\ell_{n}$. This vanishes as
$c_{n}\to\infty$ (which is the case when $k_{n}\log\ell_{n}=o(n)$), or it can
be made arbitrarily small by choosing $c_{n}=c^{\prime}$ sufficiently large
(when $k_{n}\log\ell_{n}=\Theta(n)$). Consequently, we obtain that $\frac{2\ln
v_{n}}{\tilde{E}_{n}}<\gamma$ for sufficiently large $n$ and $c_{n}$, which
implies that the RHS of (145) tends to zero as $n\to\infty$.

We finish the proof of Lemma 10 by analyzing the third term on the RHS of
(133), namely, $\text{Pr}(\mbox{$\cal{E}$}_{d}||{\bf D}^{a}|=0)\text{Pr}(|{\bf
D}^{a}|=0)$. Since $\text{Pr}(|{\bf
D}^{a}|=0)=\left((1-\alpha_{n})^{\frac{1}{\alpha_{n}}}\right)^{k_{n}}$, this
term is given by

$\displaystyle\text{Pr}(\mbox{$\cal{E}$}_{d}||{\bf
D}^{a}|=0)\left((1-\alpha_{n})^{\frac{1}{\alpha_{n}}}\right)^{k_{n}}$

and vanishes if $k_{n}$ is unbounded. Next we show that this term also
vanishes when $k_{n}$ is bounded. When $|{\bf D}^{a}|=0$, an error occurs only
if there are false alarms. For $\kappa_{2}$ false alarms, let $\bar{{\bf
S}}\triangleq\sum_{j=1}^{\kappa_{2}}{\bf S}_{j}$, and let $S^{\prime}_{i}$
denote the $i$-th component of $\bar{{\bf S}}$. From [1, eq. (303)], we obtain
the following upper bound on the probability that there are $\kappa_{2}$ false
alarms when $|{\bf D}^{a}|=0$:

$\displaystyle P(\mbox{$\cal{E}$}_{\kappa_{2}}||{\bf d}|=0)$
$\displaystyle\leq\binom{\ell_{n}}{\kappa_{2}}\mathrm{E}_{\underline{{\bf
S}}_{\mbox{$\cal{A}$}_{2}}}\left[\text{Pr}\left\\{\sum_{i=1}^{n^{\prime\prime}}Z_{i}S^{\prime}_{i}\geq\frac{1}{2}\|\bar{{\bf
S}}\|^{2}\right\\}\bigg{|}\bar{{\bf S}}\right]$
$\displaystyle\leq\left(\frac{1}{\mu}\right)^{\kappa_{2}}\binom{\ell_{n}}{\kappa_{2}}\mathrm{E}_{\tilde{\underline{{\bf
S}}}_{\mbox{$\cal{A}$}_{2}}}\left[\text{Pr}\left\\{\sum_{i=1}^{n^{\prime\prime}}Z_{i}S^{\prime}_{i}\geq\frac{1}{2}\|\bar{{\bf
S}}\|^{2}\right\\}\bigg{|}\bar{{\bf S}}\right]$

where in the last inequality we used (131). By following the analysis that led
to [1, eq. (309)], we obtain

$\displaystyle P(\mbox{$\cal{E}$}_{\kappa_{2}}||{\bf d}|=0)$
$\displaystyle\leq\left(\frac{1}{\mu}\right)^{\kappa_{2}}\exp\left[-\tilde{E}_{n}(q^{\prime}_{n}(\kappa_{2})-u_{n}^{\prime}(\kappa_{2}))\right]$

where

$\displaystyle q^{\prime}_{n}(\kappa_{2})$
$\displaystyle\triangleq\frac{n^{\prime\prime}}{2\tilde{E}_{n}}\log\left(1+\frac{\kappa_{2}\tilde{E}_{n}}{4n^{\prime\prime}}\right)$

and

$\displaystyle u^{\prime}_{n}(\kappa_{2})$
$\displaystyle\triangleq\frac{\ell_{n}}{\tilde{E}_{n}}H_{2}\left(\frac{\kappa_{2}}{\ell_{n}}\right).$

As in (143), we upper-bound $\left(\frac{1}{\mu}\right)^{\kappa_{2}}\leq 2$
uniformly in $\kappa_{2}$ for $n\geq n_{0}$. Furthermore, we observe that the
behaviours of $q^{\prime}_{n}(\kappa_{2})$ and $u^{\prime}_{n}(\kappa_{2})$
are similar to $q_{n}(\kappa_{2})$ and $v_{n}(\kappa_{2})$ given later in
(170) and in (172), respectively. So by following those steps, we can show
that

$\displaystyle\liminf_{n\to\infty}\min_{1\leq\kappa_{2}\leq
v_{n}}q^{\prime}_{n}(\kappa_{2})>0$

and

$\displaystyle\lim_{n\to\infty}\min_{1\leq\kappa_{2}\leq
v_{n}}\frac{u^{\prime}_{n}(\kappa_{2})}{q^{\prime}_{n}(\kappa_{2})}<1.$

It follows that there exist positive constants $\tau^{\prime}$ and
$\tilde{n}_{0}$ such that

$\displaystyle P(\mbox{$\cal{E}$}_{d}||{\bf d}|=0)$
$\displaystyle=\sum_{\kappa_{2}=1}^{v_{n}}P(\mbox{$\cal{E}$}_{\kappa_{2}}||{\bf
d}|=0)$ (147) $\displaystyle\leq
2v_{n}\exp\left[-\tilde{E}_{n}\tau^{\prime}\right],\quad
n\geq\max(n_{0},\tilde{n}_{0}).$

We have already shown that $v_{n}^{2}\exp[-\tilde{E}_{n}\tau^{\prime}]$
vanishes as $n\to\infty$ (cf. (145)–(146)), which implies that
$2v_{n}\exp[-\tilde{E}_{n}\tau^{\prime}]$ vanishes, too as $n\to\infty$. It
thus follows that $P(\mbox{$\cal{E}$}_{d}||{\bf d}|=0)$ tends to zero as
$n\to\infty$. This was the last step required to prove Lemma 10.

###  C-C Proof of Lemma 14

We first note that

$\displaystyle\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{(\kappa_{1},\kappa_{2})\in\mbox{$\cal{W}$}^{\ell_{n}}_{{\bf
d}}}g^{n}_{\lambda,\rho}(\kappa_{1},\kappa_{2},{\bf d})$
$\displaystyle=\min\\{\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{1\leq\kappa_{1}\leq
v_{n}}g^{n}_{\lambda,\rho}(\kappa_{1},0,{\bf d}),\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{1\leq\kappa_{2}\leq
v_{n}}g^{n}_{\lambda,\rho}(0,\kappa_{2},{\bf d}),$
$\displaystyle\qquad\qquad\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{\begin{subarray}{c}1\leq\kappa_{1}\leq
v_{n}\\\ 1\leq\kappa_{2}\leq
v_{n}\end{subarray}}g^{n}_{\lambda,\rho}(\kappa_{1},\kappa_{2},{\bf d})\\}.$
(148)

Then, we show that, for $\lambda=2/3$ and $\rho=3/4$,

$\displaystyle\liminf_{n\rightarrow\infty}\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{1\leq\kappa_{1}\leq
v_{n}}g^{n}_{\lambda,\rho}(\kappa_{1},0,{\bf d})$ $\displaystyle>0$ (149)
$\displaystyle\liminf_{n\rightarrow\infty}\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{1\leq\kappa_{2}\leq
v_{n}}g^{n}_{\lambda,\rho}(0,\kappa_{2},{\bf d})$ $\displaystyle>0$ (150)
$\displaystyle\liminf_{n\rightarrow\infty}\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{\begin{subarray}{c}1\leq\kappa_{1}\leq
v_{n}\\\ 1\leq\kappa_{2}\leq
v_{n}\end{subarray}}g^{n}_{\lambda,\rho}(\kappa_{1},\kappa_{2},{\bf d})$
$\displaystyle>0$ (151)

from which Lemma 14 follows.

In order to prove (149)–(151), we first lower-bound
$g^{n}_{\lambda,\rho}(\kappa_{1},\kappa_{2},{\bf d})$ by using that, for
$0\leq\lambda\rho\leq 1$, we have

$\displaystyle
2\log\left(1+\lambda(1-\lambda\rho)\kappa_{2}\tilde{E}_{n}/n^{\prime\prime}+\lambda\rho(1-\lambda\rho)\kappa_{1}\tilde{E}_{n}/n^{\prime\prime}\right)$
$\displaystyle\qquad\qquad\geq\log\left(1+\lambda(1-\lambda\rho)\kappa_{2}\tilde{E}_{n}/n^{\prime\prime}\right)+\log\left(1+\lambda\rho(1-\lambda\rho)\kappa_{1}\tilde{E}_{n}/n^{\prime\prime}\right).$
(152)

Using (152) in the second term on the RHS of (140), we obtain that

$\displaystyle g^{n}_{\lambda,\rho}(\kappa_{1},\kappa_{2},{\bf d})$
$\displaystyle\geq a^{n}_{\lambda,\rho}(\kappa_{1},{\bf
d})+b^{n}_{\lambda,\rho}(\kappa_{2})$ (153)

where

$\displaystyle a^{n}_{\lambda,\rho}(\kappa_{1},{\bf
d})\triangleq\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda\rho(1-\lambda\rho)\kappa_{1}\tilde{E}_{n}/n^{\prime\prime}\right)-\frac{|{\bf
d}|}{\tilde{E}_{n}}H_{2}\left(\frac{\kappa_{1}}{|{\bf d}|}\right)$

and

$\displaystyle
b^{n}_{\lambda,\rho}(\kappa_{2})\triangleq\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda(1-\lambda\rho)\kappa_{2}\tilde{E}_{n}/n^{\prime\prime}\right)-\frac{(1-\rho)}{2\tilde{E}_{n}}\log(1+\lambda\kappa_{2}\tilde{E}_{n}/n^{\prime\prime})-\frac{\rho\ell_{n}}{\tilde{E}_{n}}H_{2}\left(\frac{\kappa_{2}}{\ell_{n}}\right).$

####  C-C1 Proof of (149)

We have

$\displaystyle g^{n}_{\lambda,\rho}(\kappa_{1},0,{\bf d})$ $\displaystyle\geq
a^{n}_{\lambda,\rho}(\kappa_{1},{\bf d})+b^{n}_{\lambda,\rho}(0)$
$\displaystyle\geq a^{n}_{\lambda,\rho}(\kappa_{1},{\bf d})$ (154)

by (153) and because $b^{n}_{\lambda,\rho}(0)=0$. Consequently,

$\displaystyle\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{1\leq\kappa_{1}\leq
v_{n}}g^{n}_{\lambda,\rho}(\kappa_{1},0,{\bf d})$ $\displaystyle\geq\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{1\leq\kappa_{1}\leq
v_{n}}a^{n}_{\lambda,\rho}(\kappa_{1},{\bf d})$

and (149) follows by showing that

$\displaystyle\liminf_{n\rightarrow\infty}\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{1\leq\kappa_{1}\leq
v_{n}}a^{n}_{\lambda,\rho}(\kappa_{1},{\bf d})>0.$ (155)

To this end, let

$\displaystyle i_{n}(\kappa_{1})$
$\displaystyle\triangleq\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda\rho(1-\lambda\rho)\kappa_{1}\tilde{E}_{n}/n^{\prime\prime}\right)$
$\displaystyle j_{n}(\kappa_{1},{\bf d})$ $\displaystyle\triangleq\frac{|{\bf
d}|}{\tilde{E}_{n}}H_{2}\left(\frac{\kappa_{1}}{|{\bf d}|}\right)$

so that

$\displaystyle a^{n}_{\lambda,\rho}(\kappa_{1},{\bf
d})=i_{n}(\kappa_{1})\left(1-\frac{j_{n}(\kappa_{1},{\bf
d})}{i_{n}(\kappa_{1})}\right).$ (156)

Note that

$i_{n}(\kappa_{1})\geq\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda\rho(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right),\quad
1\leq\kappa_{1}\leq v_{n}$ (157)

and

$\displaystyle\frac{j_{n}(\kappa_{1},{\bf d})}{i_{n}(\kappa_{1})}$
$\displaystyle=\frac{4|{\bf d}|H_{2}\left(\frac{\kappa_{1}}{|{\bf
d}|}\right)}{n^{\prime\prime}\log\left(1+\lambda\rho(1-\lambda\rho)\kappa_{1}\tilde{E}_{n}/n^{\prime\prime}\right)}$
$\displaystyle=\frac{4\kappa_{1}\log(|{\bf d}|/\kappa_{1})+4|{\bf
d}|(\kappa_{1}/|{\bf d}|-1)\log(1-\kappa_{1}/|{\bf
d}|)}{n^{\prime\prime}\log\left(1+\lambda\rho(1-\lambda\rho)\kappa_{1}\tilde{E}_{n}/n^{\prime\prime}\right)}.$
(158)

Next, we upper-bound $(\kappa_{1}/|{\bf d}|-1)\log(1-\kappa_{1}/|{\bf d}|)$.
To this end, we note that the function $f(p)=p-(p-1)\ln(1-p)$, $0\leq p\leq 1$
satisfies $f(0)=0$ and is monotonically increasing in $p$. It follows that
$(p-1)\ln(1-p)\leq p$, $0\leq p\leq 1$, which for $p=\kappa_{1}/|{\bf d}|$
gives

$\displaystyle(\kappa_{1}/|{\bf d}|-1)\log(1-\kappa_{1}/|{\bf d}|)\leq(\log
e)\kappa_{1}/|{\bf d}|.$ (159)

Using (159) in (158), we obtain that

$\displaystyle\frac{j_{n}(\kappa_{1},{\bf d})}{i_{n}(\kappa_{1})}$
$\displaystyle\leq\frac{4\log(|{\bf d}|/\kappa_{1})+4\log
e}{n^{\prime\prime}\log\left(1+\lambda\rho(1-\lambda\rho)\kappa_{1}\tilde{E}_{n}/n^{\prime\prime}\right)/\kappa_{1}}$
$\displaystyle\leq\frac{4\log(|{\bf d}|/\kappa_{1})+4\log
e}{n^{\prime\prime}\log\left(1+\lambda\rho(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)/v_{n}}$
$\displaystyle{\color[rgb]{0,0,0}\leq\frac{v_{n}(4\log(v_{n})+4\log
e)}{n^{\prime\prime}\log\left(1+\lambda\rho(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)}}$
(160) $\displaystyle=\frac{4\log v_{n}+4\log
e}{\tilde{E}_{n}\frac{\log\left(1+\lambda\rho(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)}{v_{n}\tilde{E}_{n}/n^{\prime\prime}}}$
(161)

where the second inequality follows because $\frac{\log(1+x)}{x}$ is
monotonically decreasing in $x>0$, and the subsequent inequality follows
because $|{\bf d}|\leq v_{n}$ and $1\leq\kappa_{1}\leq v_{n}$. Combining
(156), (157), and (161), $a^{n}_{\lambda,\rho}(\kappa_{1},{\bf d})$ can thus
be lower-bounded by

$\displaystyle a^{n}_{\lambda,\rho}(\kappa_{1},{\bf d})$
$\displaystyle\geq\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda\rho(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)\left(1-\frac{4\log
v_{n}+4\log
e}{\tilde{E}_{n}\frac{\log\left(1+\lambda\rho(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)}{v_{n}\tilde{E}_{n}/n^{\prime\prime}}}\right).$
(162)

Note that the RHS of (162) is independent of $\kappa_{1}$ and ${\bf d}$. To
show (155), we consider the following two cases:

#### Case 1—$k_{n}\log\ell_{n}=o(n)$

Recall that if $k_{n}\log\ell_{n}=o(n)$, then
$\tilde{E}_{n}=bc_{n}\ln\ell_{n}/2$.  It follows that the term

$\displaystyle\frac{v_{n}\tilde{E}_{n}}{n^{\prime\prime}}$
$\displaystyle=\frac{(1+c^{\prime\prime})}{2}c_{n}\frac{k_{n}\ln\ell_{n}}{n}$
(163)

tends to zero as $n\to\infty$ since
$c_{n}=\ln\left(\frac{n}{k_{n}\ln\ell_{n}}\right)$ and
$\frac{k_{n}\ln\ell_{n}}{n}=o(1)$ by assumption. This also implies that
$\tilde{E}_{n}/n^{\prime\prime}\to 0$ as $n\to\infty$ since $v_{n}=\Omega(1)$.
We further have that $\tilde{E}_{n}\to\infty$ and $\frac{\log
v_{n}}{\tilde{E}_{n}}\to 0$ as $n\to\infty$ since $v_{n}=\Theta(k_{n})$ and
$\tilde{E}_{n}=\omega(\log\ell_{n})$. It follows that

$\displaystyle\liminf_{n\to\infty}\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{1\leq\kappa_{1}\leq
v_{n}}a^{n}_{\lambda,\rho}(\kappa_{1},{\bf d})$
$\displaystyle\qquad\qquad\geq\lim_{n\to\infty}\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda\rho(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)\lim_{n\to\infty}\left(1-\frac{4\log
v_{n}+4\log
e}{\tilde{E}_{n}\frac{\log\left(1+\lambda\rho(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)}{v_{n}\tilde{E}_{n}/n^{\prime\prime}}}\right)$
$\displaystyle\qquad\qquad=\frac{(\log e)\;\lambda\rho(1-\lambda\rho)}{4}$
(164)

which for $\lambda=2/3$ and $\rho=3/4$ is equal to $(\log e)/16$.

#### Case 2—$k_{n}\log\ell_{n}=\Theta(n)$

To analyze this case, we first note that, by the definition of $v_{n}$, and
because $\log k_{n}\leq\log\ell_{n}$, the numerator in (160) satisfies
$v_{n}(4\log(v_{n})+4\log e)=O(k_{n}\log\ell_{n})$. Since
$k_{n}\log\ell_{n}=\Theta(n)$, and since $n^{\prime\prime}=\Theta(n)$, this
further implies that there exist $a_{2}>0$ and $\tilde{n}^{\prime}_{0}>0$ such
that

$\displaystyle\frac{v_{n}(4\log(v_{n})+4\log e)}{n^{\prime\prime}}\leq
a_{2},\quad n\geq\tilde{n}^{\prime}_{0}.$ (165)

We have

$\displaystyle a^{n}_{\lambda,\rho}(\kappa_{1},{\bf d})$
$\displaystyle\geq\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda\rho(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)\left(1-\frac{v_{n}(4\log(v_{n})+4\log
e)}{n^{\prime\prime}\log\left(1+\lambda\rho(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)}\right).$
(166)

The RHS of (166) is independent of $\kappa_{1}$ and ${\bf d}$. We next show
that it is bounded away from zero.

Recall that, if $k_{n}\log\ell_{n}=\Theta(n)$, then
$\tilde{E}_{n}=bc^{\prime}\ln\ell_{n}/2$. We then choose $c^{\prime}$
sufficiently large such that, for some
$\tilde{n}^{\prime\prime}_{0}\geq\tilde{n}_{0}^{\prime}$,

$\log\left(1+\lambda\rho(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)>a_{2},\quad
n\geq\tilde{n}^{\prime\prime}_{0}.$ (167)

Such a choice is possible since we have

$\frac{v_{n}\tilde{E}_{n}}{n^{\prime\prime}}=\frac{1+c^{\prime\prime}}{2}c^{\prime}\frac{k_{n}\ln\ell_{n}}{n}$

and, by assumption, $\frac{k_{n}\ln\ell_{n}}{n}=\Theta(1)$. Consequently, for
sufficiently large $n$, $v_{n}\tilde{E}_{n}/n^{\prime\prime}$ is monotonically
increasing in $c^{\prime}$ and ranges from zero to infinity. Combining (167)
with (165) implies that the expression inside the large parentheses on the RHS
of (166) is bounded away from zero for $n\geq\tilde{n}^{\prime\prime}_{0}$.

We next consider the remaining term on the RHS of (166). To this end, we note
that, if $k_{n}$ is unbounded, then the assumption
$k_{n}\log\ell_{n}=\Theta(n)$ implies that $\ln\ell_{n}=o(n)$. It follows that
$\frac{\tilde{E}_{n}}{n^{\prime\prime}}=c^{\prime}\frac{\ln\ell_{n}}{2n}\to 0$
as $n\to\infty$. If $k_{n}$ is bounded, then $\ln\ell_{n}=\Theta(n)$, so
$\frac{\tilde{E}_{n}}{n^{\prime\prime}}$ is bounded. In both cases,
$\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log(1+\lambda\rho(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime})$
tends to a positive value as $n\to\infty$.

Applying the above lines of argument to (166), we obtain that

$\displaystyle\liminf_{n\to\infty}\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{1\leq\kappa_{1}\leq
v_{n}}a^{n}_{\lambda,\rho}(\kappa_{1},{\bf d})>0$ (168)

which concludes the analysis of the second case.

The claim (149) follows now by combining the above two cases, i.e., (164) and
(168).

####  C-C2 Proof of (150)

Since $a^{n}_{\lambda,\rho}(0,{\bf d})=0$, we have that

$\displaystyle\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{1\leq\kappa_{2}\leq
v_{n}}g^{n}_{\lambda,\rho}(0,\kappa_{2},{\bf d})$
$\displaystyle\geq\min_{1\leq\kappa_{2}\leq
v_{n}}b^{n}_{\lambda,\rho}(\kappa_{2}).$

Thus, (150) follows by showing that

$\displaystyle\liminf_{n\rightarrow\infty}\min_{1\leq\kappa_{2}\leq
v_{n}}b^{n}_{\lambda,\rho}(\kappa_{2})>0.$ (169)

To prove (169), we define

$\displaystyle q_{n}(\kappa_{2})$
$\displaystyle\triangleq\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda(1-\lambda\rho)\kappa_{2}\tilde{E}_{n}/n^{\prime\prime}\right)$
(170) $\displaystyle r_{n}(\kappa_{2})$
$\displaystyle\triangleq\frac{(1-\rho)}{2\tilde{E}_{n}}\log(1+\lambda\kappa_{2}\tilde{E}_{n}/n^{\prime\prime})$
(171) $\displaystyle u_{n}(\kappa_{2})$
$\displaystyle\triangleq\frac{\rho\ell_{n}}{\tilde{E}_{n}}H_{2}\left(\frac{\kappa_{2}}{\ell_{n}}\right).$
(172)

Then,

$\displaystyle b^{n}_{\lambda,\rho}(\kappa_{1})$
$\displaystyle=q_{n}(\kappa_{2})\left(1-\frac{r_{n}(\kappa_{2})}{q_{n}(\kappa_{2})}-\frac{u_{n}(\kappa_{2})}{q_{n}(\kappa_{2})}\right).$
(173)

Note that

$q_{n}(\kappa_{2})\geq\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right),\quad
1\leq\kappa_{2}\leq v_{n}.$ (174)

Furthermore,

$\displaystyle\frac{r_{n}(\kappa_{2})}{q_{n}(\kappa_{2})}$
$\displaystyle=\frac{\frac{(1-\rho)}{2\tilde{E}_{n}}\log(1+\lambda\kappa_{2}\tilde{E}_{n}/n^{\prime\prime})}{\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda(1-\lambda\rho)\kappa_{2}\tilde{E}_{n}/n^{\prime\prime}\right)}$
$\displaystyle\leq\frac{\frac{(1-\rho)}{2\tilde{E}_{n}}\log(1+\lambda
v_{n}\tilde{E}_{n}/n^{\prime\prime})}{\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)}$
$\displaystyle=\frac{\frac{(1-\rho)v_{n}}{2n^{\prime\prime}}\frac{\log(1+\lambda
v_{n}\tilde{E}_{n}/n^{\prime\prime})}{\tilde{E}_{n}v_{n}/n^{\prime\prime}}}{\frac{\log\left(1+\lambda(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)}{4\tilde{E}_{n}/n^{\prime\prime}}},\quad
1\leq\kappa_{2}\leq v_{n}.$ (175)

Finally,

$\displaystyle\frac{u_{n}(\kappa_{2})}{q_{n}(\kappa_{2})}$
$\displaystyle=\frac{4\rho\ell_{n}H_{2}\left(\frac{\kappa_{2}}{\ell_{n}}\right)}{n^{\prime\prime}\log\left(1+\lambda(1-\lambda\rho)\kappa_{2}\tilde{E}_{n}/n^{\prime\prime}\right)}$
$\displaystyle=\frac{4\rho\left[\kappa_{2}\log(\ell_{n}/\kappa_{2})+\ell_{n}(\kappa_{2}/\ell_{n}-1)\log(1-\kappa_{2}/\ell_{n})\right]}{n^{\prime\prime}\log\left(1+\lambda(1-\lambda\rho)\kappa_{2}\tilde{E}_{n}/n^{\prime\prime}\right)}$
$\displaystyle\leq\frac{4\rho\left[\kappa_{2}\log(\ell_{n}/\kappa_{2})+\kappa_{2}\log
e\right]}{n^{\prime\prime}\log\left(1+\lambda(1-\lambda\rho)\kappa_{2}\tilde{E}_{n}/n^{\prime\prime}\right)}$
$\displaystyle\leq{\color[rgb]{0,0,0}\frac{4\rho v_{n}\left[\log\ell_{n}+\log
e\right]}{n^{\prime\prime}\log\left(1+\lambda(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)}}$
(176) $\displaystyle=\frac{4\rho\left[\log\ell_{n}+\log
e\right]}{\tilde{E}_{n}\frac{\log\left(1+\lambda(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)}{v_{n}\tilde{E}_{n}/n^{\prime\prime}}},\quad
1\leq\kappa_{2}\leq v_{n}$ (177)

where the first inequality follows from (159). Combining (174)–(177) with
(173) yields the lower bound

$\displaystyle b^{n}_{\lambda,\rho}(\kappa_{2})$
$\displaystyle\geq\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)\left(1-\frac{\frac{(1-\rho)v_{n}}{2n^{\prime\prime}}\frac{\log(1+\lambda
v_{n}\tilde{E}_{n}/n^{\prime\prime})}{\tilde{E}_{n}v_{n}/n^{\prime\prime}}}{\frac{\log\left(1+\lambda(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)}{4\tilde{E}_{n}/n^{\prime\prime}}}-\frac{4\rho\left[\log\ell_{n}+\log
e\right]}{\tilde{E}_{n}\frac{\log\left(1+\lambda(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)}{v_{n}\tilde{E}_{n}/n^{\prime\prime}}}\right)$
(178)

which is independent of $\kappa_{2}$ and ${\bf d}$.

To prove (169), we first note that, since $k_{n}=\Omega(1)$, we have
$v_{n}\geq 1-\lambda\rho$ for $c^{\prime\prime}$ sufficiently large. Thus, by
the monotonicity of $x\mapsto\frac{\log(1+x)}{x}$,

$\frac{\frac{\log(1+\lambda
v_{n}\tilde{E}_{n}/n^{\prime\prime})}{\tilde{E}_{n}v_{n}/n^{\prime\prime}}}{\frac{\log\left(1+\lambda(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)}{\tilde{E}_{n}/n^{\prime\prime}}}\leq\frac{1}{1-\lambda\rho},\quad
v_{n}\geq 1-\lambda\rho.$ (179)

Furthermore, the term

$\displaystyle\frac{2(1-\rho)v_{n}}{n^{\prime\prime}}$
$\displaystyle=\frac{2(1-\rho)k_{n}(1+c^{\prime\prime})}{bn}$ (180)

vanishes as $n\to\infty$ since $k_{n}=o(n)$ by the lemma’s assumption that
$k_{n}\log\ell_{n}=O(n)$. Consequently, the RHS of (175) tends to zero as
$n\to\infty$. It follows that

$\liminf_{n\rightarrow\infty}\min_{1\leq\kappa_{2}\leq
v_{n}}b^{n}_{\lambda,\rho}(\kappa_{2})\geq\lim_{n\to\infty}\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)\left(1-\limsup_{n\to\infty}\frac{4\rho\left[\log\ell_{n}+\log
e\right]}{\tilde{E}_{n}\frac{\log\left(1+\lambda(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)}{v_{n}\tilde{E}_{n}/n^{\prime\prime}}}\right).$
(181)

To show that the RHS of (181) is positive, we consider the following two
cases:

#### Case 1—$k_{n}\log\ell_{n}=o(n)$

Recall that, in this case, $\tilde{E}_{n}=bc_{n}\ln\ell_{n}/2$ and
$c_{n}\to\infty$ as $n\to\infty$. This implies that $\tilde{E}_{n}\to\infty$,
$\frac{\log\ell_{n}}{\tilde{E}_{n}}\to 0$, and
$v_{n}\tilde{E}_{n}/n^{\prime\prime}\to 0$ as $n\to\infty$. It follows that
the RHS of (177) vanishes as $n\to\infty$, so (181) becomes

$\displaystyle\liminf_{n\rightarrow\infty}\min_{1\leq\kappa_{2}\leq
v_{n}}b^{n}_{\lambda,\rho}(\kappa_{2})$
$\displaystyle\geq\lim_{n\to\infty}\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)$
$\displaystyle=\frac{(\log e)\;\lambda(1-\lambda\rho)}{4}$ (182)

which for $\lambda=2/3$ and $\rho=3/4$ is equal to $(\log e)/12$. Here, the
last step follows by noting that $v_{n}\tilde{E}_{n}/n^{\prime\prime}\to 0$
implies that $\tilde{E}_{n}/n^{\prime\prime}\to 0$ since $v_{n}=\Omega(1)$.

#### Case 2—$k_{n}\log\ell_{n}=\Theta(n)$

We first note that, in this case, $4\rho v_{n}\left[\log\ell_{n}+\log
e\right]=\Theta(n)$. Thus, there exist two positive constants $a_{3}$ and
$\tilde{n}^{\prime\prime\prime}_{0}$ such that

$\displaystyle\frac{4\rho v_{n}\left[\log\ell_{n}+\log
e\right]}{n^{\prime\prime}}$ $\displaystyle\leq a_{3},\quad
n\geq\tilde{n}^{\prime\prime\prime}_{0}$

By the same arguments that demonstrate (167), we can show that $c^{\prime}$
can be chosen sufficiently large so that, for some
$\bar{n}_{0}\geq\tilde{n}^{\prime\prime\prime}_{0}$,

$\log\left(1+\lambda\rho(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)>a_{3},\quad
n\geq\bar{n}_{0}.$

For such a $c^{\prime}$, the RHS of (176) is strictly less than one.
Consequently, the expression inside the large parentheses on the RHS of (181)
is bounded away from zero for $n\geq\bar{n}_{0}$. Furthermore, as noted in the
proof of (149), when $k_{n}\log\ell_{n}=\Theta(n)$, the expression
$\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log(1+\lambda\rho(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime})$
tends to a positive value as $n\to\infty$. It follows that

$\displaystyle\liminf_{n\rightarrow\infty}\min_{1\leq\kappa_{2}\leq
v_{n}}b^{n}_{\lambda,\rho}(\kappa_{2})$ $\displaystyle>0$ (183)

which concludes the analysis of the second case.

The claim (150) follows now by combining the above two cases, i.e., (182) and
(183).

####  C-C3 Proof of (151)

We use (153), (162), and (178) to lower-bound

$\displaystyle g^{n}_{\lambda,\rho}(\kappa_{1},\kappa_{2},{\bf d})$
$\displaystyle\geq\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda\rho(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)\left(1-\frac{4\log
v_{n}+4\log
e}{\tilde{E}_{n}\frac{\log\left(1+\lambda\rho(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)}{v_{n}\tilde{E}_{n}/n^{\prime\prime}}}\right)$
$\displaystyle+\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)\left(1-\frac{\frac{(1-\rho)v_{n}}{2n^{\prime\prime}}\frac{\log(1+\lambda
v_{n}\tilde{E}_{n}/n^{\prime\prime})}{\tilde{E}_{n}v_{n}/n^{\prime\prime}}}{\frac{\log\left(1+\lambda(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)}{4\tilde{E}_{n}/n^{\prime\prime}}}-\frac{4\rho\left[\log\ell_{n}+\log
e\right]}{\tilde{E}_{n}\frac{\log\left(1+\lambda(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)}{v_{n}\tilde{E}_{n}/n^{\prime\prime}}}\right)$

which is independent of $\kappa_{1},\kappa_{2}$, and ${\bf d}$. It follows
that

$\liminf_{n\to\infty}\min_{{\bf
d}\in\mbox{$\cal{B}$}^{n}(v_{n})}\min_{\begin{subarray}{c}1\leq\kappa_{1}\leq
v_{n}\\\ 1\leq\kappa_{2}\leq
v_{n}\end{subarray}}g^{n}_{\lambda,\rho}(\kappa_{1},\kappa_{2},{\bf
d})\geq\underline{a}+\underline{b}$

where

$\underline{a}\triangleq\liminf_{n\to\infty}\left\\{\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda\rho(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)\left(1-\frac{4\log
v_{n}+4\log
e}{\tilde{E}_{n}\frac{\log\left(1+\lambda\rho(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)}{v_{n}\tilde{E}_{n}/n^{\prime\prime}}}\right)\right\\}$

and

$\underline{b}\triangleq\liminf_{n\to\infty}\left\\{\frac{n^{\prime\prime}}{4\tilde{E}_{n}}\log\left(1+\lambda(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)\left(1-\frac{\frac{(1-\rho)v_{n}}{2n^{\prime\prime}}\frac{\log(1+\lambda
v_{n}\tilde{E}_{n}/n^{\prime\prime})}{\tilde{E}_{n}v_{n}/n^{\prime\prime}}}{\frac{\log\left(1+\lambda(1-\lambda\rho)\tilde{E}_{n}/n^{\prime\prime}\right)}{4\tilde{E}_{n}/n^{\prime\prime}}}-\frac{4\rho\left[\log\ell_{n}+\log
e\right]}{\tilde{E}_{n}\frac{\log\left(1+\lambda(1-\lambda\rho)v_{n}\tilde{E}_{n}/n^{\prime\prime}\right)}{v_{n}\tilde{E}_{n}/n^{\prime\prime}}}\right)\right\\}.$

We then obtain (151) by noting that it was shown in the proof of (149) that
$\underline{a}>0$, and in the proof of (150) that $\underline{b}>0$.

Since (149)–(151) prove Lemma 14, this concludes the proof.

##  Appendix D Proof of Lemma 12

Let $\cal{W}$ denote the set of the $(M_{n}+1)^{\ell_{n}}$ messages of all
users. To prove Lemma 12, we represent each ${\bf w}\in\mbox{$\cal{W}$}$ using
an length-$\ell_{n}$ vector such that the $i$-th position of the vector is set
to $j$ if user $i$ has message $j$. The Hamming distance $d_{H}$ between two
messages ${\bf w}=(w_{1},\ldots,w_{\ell_{n}})$ and ${\bf
w}^{\prime}=(w^{\prime}_{1},\ldots,w^{\prime}_{\ell_{n}})$ is defined as the
number of positions at which ${\bf w}$ differs from ${\bf w}^{\prime}$, i.e.,
$d_{H}({\bf w},{\bf w}^{\prime})\triangleq\left|\\{i:w_{i}\neq
w^{\prime}_{i}\\}\right|$.

We first group the set $\cal{W}$ into $\ell_{n}+1$ subgroups. Two messages
${\bf w},{\bf w}^{\prime}\in\mbox{$\cal{W}$}$ belong to the same subgroup if
they have the same number of zeros. Note that all the messages in a subgroup
have the same probability, since the probability of a message ${\bf w}$ is
determined by the number of zeros in it.

Let $\mbox{$\cal{T}$}_{t}$ denote the set of messages ${\bf
w}\in\mbox{$\cal{W}$}$ with $t$ non-zero entries, where $t=0,\ldots,\ell_{n}$.
Further let

$\displaystyle\text{Pr}(\mbox{$\cal{T}$}_{t})\triangleq\text{Pr}({\bf
W}\in\mbox{$\cal{T}$}_{t})$

which can be evaluated as

$\text{Pr}(\mbox{$\cal{T}$}_{t})=(1-\alpha_{n})^{\ell_{n}-t}\left(\frac{\alpha_{n}}{M_{n}}\right)^{t}|\mbox{$\cal{T}$}_{t}|.$
(184)

We define

$\displaystyle
P_{e}(\mbox{$\cal{T}$}_{t})\triangleq\frac{1}{|\mbox{$\cal{T}$}_{t}|}\sum_{{\bf
w}\in\mbox{$\cal{T}$}_{t}}P_{e}({\bf w})$ (185)

where $P_{e}({\bf w})$ denotes the probability of error in decoding the set of
messages ${\bf w}=(w_{1},\ldots,w_{\ell_{n}})$. It follows that

$\displaystyle P_{e}^{(n)}$ $\displaystyle=\sum_{{\bf
w}\in\mbox{$\cal{W}$}}\text{Pr}({\bf W}={\bf w})P_{e}({\bf w})$
$\displaystyle=\sum_{t=0}^{\ell_{n}}\sum_{{\bf
w}\in\mbox{$\cal{T}$}_{t}}(1-\alpha_{n})^{\ell_{n}-t}\left(\frac{\alpha_{n}}{M_{n}}\right)^{t}|\mbox{$\cal{T}$}_{t}|\frac{1}{|\mbox{$\cal{T}$}_{t}|}P_{e}({\bf
w})$
$\displaystyle=\sum_{t=0}^{\ell_{n}}\text{Pr}(\mbox{$\cal{T}$}_{t})\frac{1}{|\mbox{$\cal{T}$}_{t}|}\sum_{w\in\mbox{$\cal{T}$}_{t}}P_{e}({\bf
w})$
$\displaystyle=\sum_{t=0}^{\ell_{n}}\text{Pr}(\mbox{$\cal{T}$}_{t})P_{e}(\mbox{$\cal{T}$}_{t})$
$\displaystyle\geq\sum_{t=1}^{\ell_{n}}\text{Pr}(\mbox{$\cal{T}$}_{t})P_{e}(\mbox{$\cal{T}$}_{t})$
(186)

where we have used (184) and the definition of $P_{e}(\mbox{$\cal{T}$}_{t})$
in (185). To prove Lemma 12, we next show that

$\displaystyle P_{e}(\mbox{$\cal{T}$}_{t})\geq 1-\frac{256E_{n}/N_{0}+\log
2}{\log\ell_{n}},\quad t=1,\ldots,\ell_{n}.$ (187)

To this end, we partition each $\mbox{$\cal{T}$}_{t},t=1,\ldots,\ell_{n}$ into
$D_{t}$ sets $\mbox{$\cal{S}$}_{d}^{t}$. For every $t=1,\ldots,\ell_{n}$, we
then show that this partition satisfies

$\displaystyle\frac{1}{|\mbox{$\cal{S}$}_{d}^{t}|}\sum_{{\bf
w}\in\mbox{$\cal{S}$}_{d}^{t}}P_{e}({\bf w})\geq 1-\frac{256E_{n}/N_{0}+\log
2}{\log\ell_{n}}.$ (188)

This yields (187) since

$\displaystyle P_{e}(\mbox{$\cal{T}$}_{t})$
$\displaystyle=\sum_{d=1}^{D_{t}}\frac{|\mbox{$\cal{S}$}_{d}^{t}|}{|\mbox{$\cal{T}$}_{t}|}\frac{1}{|\mbox{$\cal{S}$}_{d}^{t}|}\sum_{{\bf
w}\in\mbox{$\cal{S}$}_{d}^{t}}P_{e}({\bf w}).$ (189)

Before we continue by defining the sets $\mathcal{S}_{d}^{t}$, we note that

$\displaystyle M_{n}\geq 2$ (190)

since $M_{n}=1$ would contradict the lemma’s first assumption that
$\dot{R}>0$. We further have that

$\displaystyle\ell_{n}\geq 5$ (191)

by the lemma’s second assumption.

We next define a partition of $\mbox{$\cal{T}$}_{t},t=1,\ldots,\ell_{n}$ that
satisfies the following:

$\displaystyle|\mbox{$\cal{S}$}_{d}^{t}|\geq\ell_{n}+1,\quad d=1,\ldots,D_{t}$
(192)

and

$\displaystyle d_{H}({\bf w},{\bf w}^{\prime})\leq 8,\quad{\bf w},{\bf
w}^{\prime}\in\mbox{$\cal{S}$}_{d}^{t}.$ (193)

To this end, we consider the following four cases:

#### Case 1—$t=1$

For $t=1$, we do not partition the set, i.e.,
$\mbox{$\cal{S}$}_{1}^{1}=\mbox{$\cal{T}$}_{1}$. Thus, we have
$|\mbox{$\cal{S}$}_{1}^{1}|=\ell_{n}M_{n}$. From (190) and (191), it follows
that $|\mbox{$\cal{S}$}_{1}^{1}|\geq\ell_{n}+1$. Since any two messages ${\bf
w},{\bf w}^{\prime}\in\mbox{$\cal{T}$}_{1}$ have only one non-zero entry, we
further have that $d_{H}({\bf w},{\bf w}^{\prime})\leq 2$. Consequently, (192)
and (193) are satisfied.

#### Case 2—$t=2,\ldots,\ell_{n}-2$

In this case, we obtain a partition by finding a code $\mbox{$\cal{C}$}_{t}$
in $\mbox{$\cal{T}$}_{t}$ that has minimum Hamming distance $5$, and for every
${\bf w}\in\mbox{$\cal{T}$}_{t}$, there exists at least one codeword in
$\mbox{$\cal{C}$}_{t}$ which is at most at Hamming distance 4 from it. Such a
code exists because, if for some ${\bf w}\in\mbox{$\cal{T}$}_{t}$ all
codewords were at Hamming distance 5 or more, then we could add ${\bf w}$ to
$\mbox{$\cal{C}$}_{t}$ without affecting its minimum distance. Thus, for all
${\bf w}\notin\mbox{$\cal{C}$}_{t}$, there exists at least one index $j$ such
that $d_{H}({\bf w},{\bf c}_{t}(j))\leq 4$, where ${\bf c}_{t}(1),\ldots,{\bf
c}_{t}(|\mbox{$\cal{C}$}_{t}|)$ denote the codewords of the code
$\mbox{$\cal{C}$}_{t}$. With this code $\mathcal{C}_{t}$, we partition
$\mbox{$\cal{T}$}_{t}$ into the sets $\mathcal{S}_{d}^{t}$, $d=1,\ldots,D_{t}$
with $D_{t}=|\mbox{$\cal{C}$}_{t}|$ the following procedure:

  1. 1.

For a given $d=1,\ldots,D_{t}$, we assign ${\bf c}_{t}(d)$ to
$\mbox{$\cal{S}$}_{d}^{t}$ as well as all ${\bf w}\in\mbox{$\cal{T}$}_{t}$
that satisfy $d_{H}({\bf w},{\bf c}_{t}(d))\leq 2$. These assignments are
unique since the code $\mbox{$\cal{C}$}_{t}$ has minimum Hamming distance 5.

  2. 2.

We then consider all ${\bf w}\in\mbox{$\cal{T}$}_{t}$ for which there is no
codeword ${\bf c}_{t}(1),\ldots,{\bf c}_{t}(|\mbox{$\cal{C}$}_{t}|)$
satisfying $d_{H}({\bf w},{\bf c}_{t}(d))\leq 2$ and assign them to the set
$\mbox{$\cal{S}$}_{d}^{t}$ with index $d=\min\\{j=1,\ldots,D_{t}:d_{H}({\bf
w},{\bf c}_{t}(j))\leq 4\\}$.

Like this, we obtain a partition of $\mbox{$\cal{T}$}_{t}$. Since any two
${\bf w},{\bf w}^{\prime}\in\mbox{$\cal{S}$}_{d}^{t}$ are at most at a Hamming
distance 4 from the codeword ${\bf c}_{t}(d)$, we have that $d_{H}({\bf
w},{\bf w}^{\prime})\leq 8$. Consequently, (193) is satisfied.

To show that (192) is satisfied, too, we use the following fact:

$\displaystyle\text{For two natural numbers }a\text{ and }b,\text{ if }a\geq
4\text{ and }2\leq b\leq a-2,\text{ then }b(a-b)\geq a.$ (194)

This fact follows since $b(a-b)$ is increasing in $b$ from $b=2$ to $b=\lfloor
a/2\rfloor$ and is decreasing in $b$ from $b=\lfloor a/2\rfloor$ to $b=a-2$.
So $b(a-b)$ is minimized at $b=2$ and $b=a-2$, where it has the value $2a-4$.
For $a\geq 4$, this value is greater than or equal to $a$, hence the claim
follows.

From (194), it follows that, if $|\mbox{$\cal{S}$}_{d}^{t}|\geq
1+t(\ell_{n}-t)$, then $|\mbox{$\cal{S}$}_{d}^{t}|\geq 1+\ell_{n}$. It thus
remains to show that $|\mbox{$\cal{S}$}_{d}^{t}|\geq 1+t(\ell_{n}-t)$. To this
end, for every codeword ${\bf c}_{t}(d)$, consider all sequences in
$\mbox{$\cal{T}$}_{t}$ which differ exactly in one non-zero position and in
one zero position from ${\bf c}_{t}(d)$. There are $t(\ell_{n}-t)M_{n}$ such
sequences in $\mbox{$\cal{T}$}_{t}$, which can be lower-bounded as

$\displaystyle t(\ell_{n}-t)M_{n}$ $\displaystyle\geq t(\ell_{n}-t)$
$\displaystyle\geq\ell_{n}$ (195)

by (190), (191), and (194). Since the codeword ${\bf c}_{t}(d)$ also belongs
to $S_{d}^{t}$, it follows from (195) that

$\displaystyle|\mbox{$\cal{S}$}_{d}^{t}|$ $\displaystyle\geq\ell_{n}+1.$

#### Case 3—$t=\ell_{n}-1$

We obtain a partition by defining a code $\mbox{$\cal{C}$}_{t}$ in
$\mbox{$\cal{T}$}_{\ell_{n}-1}$ that has the same properties as the code used
for Case 2. We then use the same procedure as in Case 2 to assign messages in
${\bf w}\in\mbox{$\cal{T}$}_{\ell_{n}-1}$ to the sets
$\mbox{$\cal{S}$}_{d}^{t}$, $d=1,\ldots,D_{t}$. This gives a partition of
$\mbox{$\cal{T}$}_{\ell_{n}-1}$ where any two ${\bf w},{\bf
w}^{\prime}\in\mbox{$\cal{S}$}_{d}^{t}$ satisfy
$d_{H}(\mathbf{w},\mathbf{w}^{\prime})\leq 8$. Consequently, this partition
satisfies (193).

We next show that this partition also satisfies (192). To this end, for every
codeword ${\bf c}_{t}(d)$, consider all the sequences which differ exactly in
two non-zero positions from ${\bf c}_{t}(d)$. There are
$\binom{\ell_{n}-1}{2}(M_{n}-1)^{2}$ such sequences in
$\mbox{$\cal{T}$}_{\ell_{n}-1}$. Since $\mbox{$\cal{S}$}_{d}^{t}$ also
contains the codeword ${\bf c}_{t}(d)$, we obtain that

$\displaystyle|\mbox{$\cal{S}$}_{d}^{t}|$
$\displaystyle\geq\binom{\ell_{n}-1}{2}(M_{n}-1)^{2}+1$
$\displaystyle\geq\binom{\ell_{n}-1}{2}+1$ $\displaystyle\geq\ell_{n}+1$

by (190) and (191).

#### Case 4—$t=\ell_{n}$

We obtain a partition by defining a code $\mathcal{C}_{t}$ in
$\mbox{$\cal{T}$}_{\ell_{n}-1}$ that has the same properties as the code used
in Case 2. We then use the same procedure as in Case 2 to assign messages in
$\mathbf{w}\in\mbox{$\cal{T}$}_{t}$ to the sets $\mathcal{S}_{d}^{t}$,
$d=1,\ldots,D_{t}$. This gives a partition of $\mbox{$\cal{T}$}_{t}$ where any
two $\mathbf{w},\mathbf{w}^{\prime}\in\mathcal{S}_{d}^{t}$ satisfy
$d_{H}(\mathbf{w},\mathbf{w}^{\prime})\leq 8$. Consequently, this partition
satisfies (193).

We next show that this partition also satisfies (192). To this end, for every
codeword ${\bf c}_{t}(d)$, consider all sequences which are at Hamming
distance $1$ from ${\bf c}_{t}(d)$. There are $\ell_{n}(M_{n}-1)$ such
sequences. Since $\mbox{$\cal{S}$}_{d}^{t}$ also contains the codeword, we
have

$\displaystyle|\mbox{$\cal{S}$}_{d}^{t}|$ $\displaystyle\geq
1+\ell_{n}(M_{n}-1)$ $\displaystyle\geq 1+\ell_{n}$

by (190).

Having obtained a partition of $\mbox{$\cal{T}$}_{t}$ that satisfies (192) and
(193), we next derive the lower bound (188). To this end, we use a stronger
form of Fano’s inequality known as Birgé’s inequality.

######  Lemma 15 (Birgé’s inequality)

Let $(\mbox{$\cal{Y}$},\mbox{$\cal{B}$})$ be a measurable space with a
$\sigma$-field, and let $P_{1},\ldots,P_{N}$ be probability measures defined
on $\cal{B}$. Further let $\mbox{$\cal{A}$}_{i}$, $i=1,\ldots,N$ denote $N$
events defined on $\cal{Y}$, where $N\geq 2$. Then

$\displaystyle\frac{1}{N}\sum_{i=1}^{N}P_{i}(\mbox{$\cal{A}$}_{i})\leq\frac{\frac{1}{N^{2}}\sum_{i,j}D(P_{i}\|P_{j})+\log
2}{\log(N-1)}.$

###### Proof:

See [23] and references therein. ∎

To apply Lemma 15 to the problem at hand, we set
$N=|\mbox{$\cal{S}$}_{d}^{t}|$ and $P_{j}=P_{{\bf Y}|{\bf X}}(\cdot|{\bf
x}(j))$, where ${\bf x}(j)$ denotes the set of codewords transmitted to convey
the set of messages $j\in\mbox{$\cal{S}$}_{d}^{t}$. We further define
$\mbox{$\cal{A}$}_{j}$ as the subset of $\mbox{$\cal{Y}$}^{n}$ for which the
decoder declares the set of messages $j\in\mbox{$\cal{S}$}_{d}^{t}$. Then, the
probability of error in decoding messages $j\in\mbox{$\cal{S}$}_{d}^{t}$ is
given by $P_{e}(j)=1-P_{j}(\mbox{$\cal{A}$}_{j})$, and
$\frac{1}{|\mbox{$\cal{S}$}_{d}^{t}|}\sum_{j\in\mbox{$\cal{S}$}_{d}^{t}}P_{j}(\mbox{$\cal{A}$}_{j})$
denotes the average probability of correctly decoding a set of messages in
$\mbox{$\cal{S}$}_{d}^{t}$.

For two multivariate Gaussian distributions ${\bf
Z}_{1}\sim\mbox{$\cal{N}$}(\boldsymbol{\mu_{1}},\frac{N_{0}}{2}I)$ and ${\bf
Z}_{2}\sim\mbox{$\cal{N}$}(\boldsymbol{\mu_{2}},\frac{N_{0}}{2}I)$ (where $I$
denotes the identity matrix), the relative entropy $D({\bf Z}_{1}\|{\bf
Z}_{2})$ is given by $\frac{||\boldsymbol{\mu_{1}-\mu_{2}}||^{2}}{N_{0}}$. We
next note that $P_{{\bf w}}=\mbox{$\cal{N}$}(\overline{{\bf x}}({\bf
w}),\frac{N_{0}}{2}I)$ and $P_{{\bf
w}^{\prime}}=\mbox{$\cal{N}$}(\overline{{\bf x}}({\bf
w}^{\prime}),\frac{N_{0}}{2}I)$, where $\overline{{\bf x}}(j)$ denotes the sum
of codewords contained in ${\bf x}(j)$. By construction, any two messages
${\bf w},{\bf w}^{\prime}\in\mbox{$\cal{S}$}_{d}^{t}$ are at a Hamming
distance of at most 8. Without loss of generality, let us assume that
$w_{j}=w^{\prime}_{j}$ for $j=9,\ldots,\ell_{n}$. Then

$\displaystyle\big{\|}\sum_{j=1}^{\ell_{n}}{\bf
x}_{j}(w_{j})-\sum_{i=1}^{\ell_{n}}{\bf x}_{j}(w^{\prime}_{j})\big{\|}^{2}$
$\displaystyle=\big{\|}\sum_{i=1}^{8}{\bf x}_{j}(w_{j})-{\bf
x}_{j}(w^{\prime}_{j})\big{\|}^{2}$
$\displaystyle\leq\big{\|}\sum_{j=1}^{8}|{\bf x}_{j}(w_{j})-{\bf
x}_{j}(w^{\prime}_{j})|\big{\|}^{2}$ $\displaystyle\leq(8\times
2\sqrt{E_{n}})^{2}$ $\displaystyle=256E_{n}$

where we have used the triangle inequality and that the energy of a codeword
for any user is upper-bounded by $E_{n}$. Thus, $D(P_{{\bf w}}\|P_{{\bf
w}^{\prime}})\leq 256E_{n}/N_{0}$.

It follows from Birgé’s inequality that

$\displaystyle\frac{1}{|\mbox{$\cal{S}$}_{d}^{t}|}\sum_{{\bf
w}\in\mbox{$\cal{S}$}_{d}^{t}}P_{e}({\bf w})$ $\displaystyle\geq
1-\frac{256E_{n}/N_{0}+\log 2}{\log(|\mbox{$\cal{S}$}_{d}^{t}|-1)}$
$\displaystyle\geq 1-\frac{256E_{n}/N_{0}+\log 2}{\log\ell_{n}}$ (196)

where the last step holds because $|\mbox{$\cal{S}$}_{d}^{t}|-1\geq\ell_{n}$.
This proves (188) and hence also (187).

Combining (187) and (186), we obtain

$\displaystyle P_{e}^{(n)}$
$\displaystyle\geq\left(1-\frac{256E_{n}/N_{0}+\log
2}{\log\ell_{n}}\right)\sum_{i=1}^{\ell_{n}}\text{Pr}(\mbox{$\cal{T}$}_{i})$
$\displaystyle=\left(1-\frac{256E_{n}/N_{0}+\log
2}{\log\ell_{n}}\right)(1-\text{Pr}(\mbox{$\cal{T}$}_{0})).$

The probability
$\textnormal{Pr}(\mathcal{T}_{0})=\left((1-\alpha_{n})^{\frac{1}{\alpha_{n}}}\right)^{k_{n}}$
is upper-bounded by $e^{-k_{n}}$ so, by the lemma’s assumption
$k_{n}=\Omega(1)$,

$\limsup_{n\to\infty}\textnormal{Pr}(\mathcal{T}_{0})<1.$

Consequently, $P_{e}^{(n)}$ may tend to zero as $n\to\infty$ only if

$\displaystyle E_{n}$ $\displaystyle=\Omega\left(\log\ell_{n}\right).$

This proves Lemma 12.

## Acknowledgment

The authors wish to thank the Associate Editor A. Anastasopoulos and the
anonymous referees for their valuable comments.

## References

  * [1] X. Chen, T. Y. Chen, and D. Guo, “Capacity of Gaussian many-access channels,” _IEEE Transactions on Information Theory_ , vol. 63, no. 6, pp. 3516–3539, June 2017.
  * [2] L. Liu, E. G. Larsson, W. Yu, P. Popovski, C. Stefanovic, and E. de Carvalho, “Sparse signal processing for grant-free massive connectivity: A future paradigm for random access protocols in the internet of things,” _IEEE Signal Processing Magazine_ , vol. 35, no. 5, pp. 88–99, September 2018\.
  * [3] S. Shahi, D. Tuninetti, and N. Devroye, “The strongly asynchronous massive access channel,” arXiv: 1807.09934 [cs.IT], July 2018.
  * [4] Y. Polyanskiy, “A perspective on massive random-access,” in _IEEE International Symposium on Information Theory (ISIT)_ , Aachen, Germany, June 2017, pp. 2523–2527.
  * [5] O. Ordentlich and Y. Polyanskiy, “Low complexity schemes for the random access gaussian channel,” in _2017 IEEE International Symposium on Information Theory (ISIT)_ , Aachen, Germany, June 2017, pp. 2528–2532.
  * [6] A. Vem, K. R. Narayanan, J. Chamberland, and J. Cheng, “A user-independent successive interference cancellation based coding scheme for the unsourced random access Gaussian channel,” _IEEE Transactions on Communications_ , vol. 67, no. 12, pp. 8258–8272, December 2019.
  * [7] V. K. Amalladinne, J. F. Chamberland, and K. R. Narayanan, “A coded compressed sensing scheme for unsourced multiple access,” _IEEE Transactions on Information Theory_ , vol. 66, no. 10, pp. 6509–6533, October 2020\.
  * [8] A. Fengler, P. Jung, and G. Caire, “SPARCs and AMP for unsourced random access,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , Paris, France, July 2019, pp. 2843–2847.
  * [9] ——, “Unsourced multiuser sparse regression codes achieve the symmetric MAC capacity,” in _2020 IEEE International Symposium on Information Theory (ISIT)_ , Los Angeles, USA, June 2020, pp. 3001–3006.
  * [10] S. S. Kowshik and Y. Polyanskiy, “Quasi-static fading MAC with many users and finite payload,” in _IEEE International Symposium on Information Theory (ISIT)_ , Paris, France, July 2019, pp. 440–444.
  * [11] ——, “Fundamental limits of many-user MAC with finite payloads and fading,” arXiv: 1901.06732 [cs.IT], 2019.
  * [12] S. S. Kowshik, K. Andreev, A. Frolov, and Y. Polyanskiy, “Energy efficient coded random access for the wireless uplink,” _IEEE Transactions on Communications_ , vol. 68, no. 8, pp. 4694–4708, August 2020.
  * [13] I. Zadik, Y. Polyanskiy, and C. Thrampoulidis, “Improved bounds on Gaussian MAC and sparse regression via Gaussian inequalities,” in _IEEE International Symposium on Information Theory (ISIT)_ , Paris, France, July 2019, pp. 430–434.
  * [14] S. Verdú, “On channel capacity per unit cost,” _IEEE Transactions on Information Theory_ , vol. 36, no. 5, pp. 1019–1030, September 1990.
  * [15] C. E. Shannon, R. G. Gallager, and E. R. Berlekamp, “Lower bounds to error probability for coding on discrete memoryless channels I,” _Information and Control_ , vol. 10, pp. 65–103, January 1967.
  * [16] A. J. Viterbi and J. K. Omura, _Principles of Digital Communication and Coding_ , 1st ed. New York, NY, USA: McGraw-Hill Book Company, 1979.
  * [17] Y. Polyanskiy, “Information theoretic perspective on massive multiple-access,” http://people.lids.mit.edu/yp/homepage/data/NASIT18-MAC-tutorial.pdf, June 2018\.
  * [18] R. G. Gallager, _Information Theory and Reliable Communication_ , 1st ed. New York, NY, USA: John Wiley & Sons, 1968.
  * [19] T. Cover and J. Thomas, _Elements of Information Theory_ , 2nd ed. New York, NY, USA: Wiley-Interscience, 2006.
  * [20] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Minimum energy to send $k$ bits through the Gaussian channel with and without feedback,” _IEEE Transactions on Information Theory_ , vol. 57, no. 8, pp. 4880–4902, August 2011\.
  * [21] R. Gallager, “A perspective on multiaccess channels,” _IEEE Transactions on Information Theory_ , vol. 31, no. 2, pp. 124–142, March 1985.
  * [22] A. Lapidoth, _A Foundation in Digital Communication_ , 2nd ed. Cambridge, UK: Cambridge University Press, 2017.
  * [23] Y. G. Yatracos, “A lower bound on the error in nonparametric regression type problems,” _The Annals of Statistics_ , vol. 16, no. 3, pp. 1180–1187, September 1988.