# Scaling Laws for Gaussian Random
Many-Access Channels

Jithin Ravi and Tobias Koch J. Ravi and T. Koch have received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (Grant No. 714161). T. Koch has further
received funding from the Spanish Ministerio de Economía y Competitividad
under Grants RYC-2014-16332 and TEC2016-78434-C3-3-R (AEI/FEDER, EU). The
material in this paper was presented in part at the IEEE International
Symposium on Information Theory, Paris, France, July 2019, at the
International Zurich Seminar on Information and Communication, Zurich,
Switzerland, February 2020, and at the IEEE International Symposium on
Information Theory, Los Angeles, CA, USA, June 2020. J. Ravi and T. Koch are
with the Signal Theory and Communications Department, Universidad Carlos III
de Madrid, Spain, and with the Gregorio Marañón Health Research Institute,
Madrid, Spain (emails<EMAIL_ADDRESS>koch@tsc.uc3m.es).

###### Abstract

This paper considers a Gaussian multiple-access channel with random user
activity where the total number of users $\ell_{n}$ and the average number of
active users $k_{n}$ may grow with the blocklength $n$. For this channel, it
studies the maximum number of bits that can be transmitted reliably per unit-
energy as a function of $\ell_{n}$ and $k_{n}$. When all users are active with
probability one, i.e., $\ell_{n}=k_{n}$, it is demonstrated that if $k_{n}$ is
of an order strictly below $n/\log n$, then each user can achieve the single-
user capacity per unit-energy $(\log e)/N_{0}$ (where $N_{0}/2$ is the noise
power) by using an orthogonal-access scheme. In contrast, if $k_{n}$ is of an
order strictly above $n/\log n$, then the users cannot achieve any positive
rate per unit-energy. Consequently, there is a sharp transition between orders
of growth where interference-free communication is feasible and orders of
growth where reliable communication at a positive rate per unit-energy is
infeasible. It is further demonstrated that orthogonal-access schemes in
combination with orthogonal codebooks, which achieve the capacity per unit-
energy when the number of users is bounded, can be strictly suboptimal.

When the user activity is random, i.e., when $\ell_{n}$ and $k_{n}$ are
different, it is demonstrated that if $k_{n}\log\ell_{n}$ is sublinear in $n$,
then each user can achieve the single-user capacity per unit-energy $(\log
e)/N_{0}$. Conversely, if $k_{n}\log\ell_{n}$ is superlinear in $n$, then the
users cannot achieve any positive rate per unit-energy. Consequently, there is
again a sharp transition between orders of growth where interference-free
communication is feasible and orders of growth where reliable communication at
a positive rate is infeasible that depends on the asymptotic behaviours of
both $\ell_{n}$ and $k_{n}$. It is further demonstrated that orthogonal-access
schemes, which are optimal when all users are active with probability one, can
be strictly suboptimal in general.

##  I Introduction

Chen  _et al._ [1] introduced the many-access channel (MnAC) as a multiple-
access channel (MAC) where the number of users grows with the blocklength and
each user is active with a given probability. This model is motivated by
systems consisting of a single receiver and many transmitters, the number of
which is comparable or even larger than the blocklength. This situation may
occur, _e.g._ , in a machine-to-machine communication scenario with many
thousands of devices in a given cell that are active only sporadically. In
[1], Chen  _et al._ considered a Gaussian MnAC with $\ell_{n}$ users, each of
which is active with probability $\alpha_{n}$, and determined the number of
messages $M_{n}$ each user can transmit reliably with a codebook of average
power not exceeding $P$. Since then, MnACs have been studied in various papers
under different settings.

An example of a MAC is the uplink connection in a cellular network. Current
cellular networks follow a _grant-based_ access protocols, i.e., an active
device has to obtain permission from the base station to transmit data. In
MnACs, this will lead to a large signalling overhead. _Grant-free_ access
protocols, where active devices can access the network without a permission,
were proposed to overcome this [2]. The synchronization issues arising in such
scenarios have been studied by Shahi _et al._ [3]. In some of the MnACs, such
as sensor networks, detecting the identity of a device that sent a particular
message may not be important. This scenario was studied under the name of
_unsourced_ massive access by Polyanskiy [4], who further introduced the
notion of _per-user probability of error_. Specifically, [4] analyzed the
minimum _energy-per-bit_ required to reliably transmit a message over an
unsourced Gaussian MnAC where the number of active users grows linearly in the
blocklength and each user’s payload is fixed. Low-complexity schemes for this
setting were studied in many works [5, 6, 7, 8, 9]. Generalizations to quasi-
static fading MnACs can be found in [10, 11, 12]. Zadik _et al._ [13]
presented improved bounds on the tradeoff between user density and energy-per-
bit for the many-access channel introduced in [4].

Related to energy per-bit is the _capacity per unit-energy_ $\dot{C}$ which is
defined as the largest number of bits per unit-energy that can be transmitted
reliably over a channel. Verdú [14] showed that $\dot{C}$ can be obtained from
the capacity-cost function $C(P)$, defined as the largest number of bits per
channel use that can be transmitted reliably with average power per symbol not
exceeding $P$, as

$\displaystyle\dot{C}=\sup_{P>0}\frac{C(P)}{P}.$

For the Gaussian channel with noise power $N_{0}/2$, this is equal to
$\frac{\log e}{N_{0}}$. Verdú further showed that the capacity per unit-energy
can be achieved by a codebook that is orthogonal in the sense that the nonzero
components of different codewords do not overlap. Such a codebook corresponds
to pulse position modulation (PPM) either in time or frequency domains. In
general, we shall say that a codebook is orthogonal if the inner product
between different codewords is zero. The two-user Gaussian multiple access
channel (MAC) was also studied in [14], and it was demonstrated that both
users can achieve the single-user capacity per unit-energy by timesharing the
channel between the users, i.e., while one user transmits the other user
remains silent. This is an _orthogonal-access scheme_ in the sense that the
inner product between codewords of different users is zero.111Note, however,
that in an orthogonal-access scheme the codebooks are not required to be
orthogonal. That is, codewords of different codebooks are orthogonal to each
other, but codewords of the same codebook need not be. To summarize, in a two-
user Gaussian MAC, both users can achieve the rate per unit-energy $\frac{\log
e}{N_{0}}$ by combining an orthogonal-access scheme with orthogonal codebooks.
This result can be directly generalized to any finite number of users.

The picture changes when the number of users grows without bound with the
blocklength $n$. In this paper, we consider a setting where the total number
of users $\ell_{n}$ may grow as an arbitrary function of the blocklength and
the probability $\alpha_{n}$ that a user is active may be a function of the
blocklength, too. Contributions of this paper are as follows.

  1. 1.

First, we consider the capacity per unit-energy of the Gaussian MnAC as a
function of the order of growth of users when all users are active with
probability one. In Theorem 1, we show that, if the order of growth is above
$n/\log n$, then the capacity per unit-energy is zero, and if the order of
growth is below $n/\log n$, then each user can achieve the singe-user capacity
per unit-energy $\frac{\log e}{N_{0}}$. Thus, there is a sharp transition
between orders of growth where interference-free communication is feasible and
orders of growth where reliable communication at a positive rate is
infeasible.  We further show that, if the order of growth is proportional to
$n/\log n$, then the capacity per unit-energy is strictly between zero and
$\frac{\log e}{N_{0}}$. Finally, we show that the capacity per unit-energy can
be achieved by an orthogonal-access scheme.

  2. 2.

Since an orthogonal-access scheme in combination with orthogonal codebooks is
optimal in achieving the capacity per unit-energy for a finite number of
users, we study the performance of such a scheme for an unbounded number of
users. In particular, we characterize in Theorem 2 the largest rate per unit-
energy that can be achieved with an orthogonal-access scheme and orthogonal
codebooks. Our characterization shows that this scheme is only optimal if the
number of users grows more slowly than any positive power of $n$.

  3. 3.

We then analyze the behaviour of the capacity per unit-energy of the Gaussian
MnAC as a function of the order of growth of the number of users for the per-
user probability of error which, in this paper, we shall refer to as _average
probability of error_ (APE). In contrast, we refer to the classical
probability of error as _joint probability of error_ (JPE). We demonstrate
that, if the order of growth is sublinear, then each user can achieve the
capacity per unit-energy $\frac{\log e}{N_{0}}$ of the single-user Gaussian
channel. Conversely, if the growth is linear or above, then the capacity per
unit-energy is zero (Theorem 3). Comparing with the results in Theorem 1, we
observe that relaxing the error probability from JPE to APE shifts the
transition threshold separating the two regimes of interference-free
communication and no reliable communication from $n/\log n$ to $n$.

  4. 4.

We next consider MnACs with random user activity. As before, we consider a
setting where the total number of users $\ell_{n}$ may grow as an arbitrary
function of the blocklength. Furthermore, the probability $\alpha_{n}$ that a
user is active may be a function of the blocklength, too. Let
$k_{n}=\alpha_{n}\ell_{n}$ denote the average number of active users. We
demonstrate in Theorem 7 that, if $k_{n}\log\ell_{n}$ is sublinear in $n$,
then each user can achieve the single-user capacity per unit-energy.
Conversely, if $k_{n}\log\ell_{n}$ is superlinear in $n$, then the capacity
per unit-energy is zero. We also demonstrate that, if $k_{n}\log\ell_{n}$ is
linear in $n$, then the capacity per unit-energy is strictly between zero and
$\frac{\log e}{N_{0}}$.

  5. 5.

We further show in Theorem 8 that orthogonal-access schemes, which are optimal
when $\alpha_{n}=1$, are strictly suboptimal when $\alpha_{n}\to 0$. In
Theorem 9, we then characterize the behaviour of the random MnAC under APE.

  6. 6.

We conclude the paper with a comparison of the setting considered in this
paper and the setting proposed by Polyanskiy in [4]. Since an important aspect
of the Polyanskiy setting is that the probability of error does not vanish as
the blocklength tends to infinity, we briefly discuss the behavior of the
$\epsilon$-capacity per unit-energy, i.e., the largest rate per unit-energy
for which the error probability does not exceed a given $\epsilon$. For the
case where the users are active with probability one, we show that, for JPE
and an unbounded number of users, the $\epsilon$-capacity per unit energy
coincides with $\dot{C}$. In other words, the strong converse holds in this
case. In contrast, for APE, the $\epsilon$-capacity per unit-energy can be
strictly larger than $\dot{C}$, so the strong converse does not hold.

The rest of the paper is organized as follows. Section II introduces the
system model and the different notions of probability of error. Section III
presents our results for the case where all users are active with probability
one (“non-random MnAC"). Section IV presents our results for the case where
the user activity is random (“random MnAC").  Section V briefly discusses our
results with that obtained in [4] under non-vanishing probability of error.
Section VI concludes the paper with a summary and discussion of our results.

##  II Problem Formulation and Preliminaries

###  II-A Model and Definitions

Consider a network with $\ell$ users that, if they are active, wish to
transmit their messages $W_{i},i=1,\ldots,\ell$ to one common receiver, see
Fig. 1. The messages are assumed to be independent and uniformly distributed
on $\mbox{$\cal{M}$}_{n}^{(i)}\triangleq\\{1,\ldots,M_{n}^{(i)}\\}$. To
transmit their messages, the users send a codeword of $n$ symbols over the
channel, where $n$ is referred to as the _blocklength_. We consider a many-
access scenario where the number of users $\ell$ may grow with $n$, hence, we
denote it as $\ell_{n}$. We assume that a user is active with probability
$\alpha_{n}$.  We denote the average number of active users at blocklength $n$
by $k_{n}$, i.e., $k_{n}=\alpha_{n}\ell_{n}$.

Let $\mbox{$\cal{U}$}_{n}$ denote the set of active users at blocklength $n$,
defined as

$\displaystyle\mbox{$\cal{U}$}_{n}\triangleq\\{{\color[rgb]{0,0,0}i=1,\ldots,\ell_{n}}:\mbox{user
}i\mbox{ is active}\\}.$

We consider a Gaussian channel model where the received vector ${\bf Y}$ is
given by

$\displaystyle{\bf Y}$ $\displaystyle=\sum_{i\in\mbox{$\cal{U}$}_{n}}{\bf
x}_{i}(W_{i})+{\bf Z}.$ (1)

Here ${\bf x}_{i}(W_{i})$ is the length-$n$ transmitted codeword from user $i$
for message $W_{i}$, and ${\bf Z}$ is a vector of $n$ i.i.d. Gaussian
components $Z_{j}\sim\mbox{$\cal{N}$}(0,N_{0}/2)$ (where
$\mbox{$\cal{N}$}(\mu,\sigma^{2})$ denotes the Gaussian distribution with mean
$\mu$ and variance $\sigma^{2}$) independent of ${\bf X}_{i}\triangleq{\bf
x}_{i}(W_{i})$. The decoder produces an estimate of the users that are active
and estimates of their transmitted messages.

Figure 1: Many-access channel with $\ell_{n}$ users at blocklength $n$.

There are different ways to define the overall probability of error. Let
$\hat{\mathcal{U}}_{n}$ and $\hat{W}_{i}$ denote the decoder’s estimates of
the set of active users and the message transmitted by user $i$, respectively.
Further let $\mathcal{D}_{E}$ denote the event that the set of active users
was detected erroneously, i.e., that
$\hat{\mathcal{U}}_{n}\neq\mathcal{U}_{n}$, and let $\mathcal{M}_{E}$ denote
the event that $\hat{W}_{i}\neq W_{i}$ for some $i\in\mathcal{U}_{n}$ (where
we set $\hat{W}_{i}=0$ for every $i\notin\hat{\mathcal{U}}_{n}$). One
possibility to measure the likelihood of these two events is via the
probability of error

$P_{e}^{(n)}=\text{Pr}(\mathcal{D}_{E}\cup\mathcal{M}_{E}).$ (2)

Another possibility is to consider

$P_{\textnormal{max}}^{(n)}=\max(\text{Pr}(\mbox{$\cal{D}$}_{E}),\text{Pr}(\mbox{$\cal{M}$}_{E})).$
(3)

We have $P_{\textnormal{max}}^{(n)}\leq P_{e}^{(n)}\leq
2P_{\textnormal{max}}^{(n)}$. Indeed, the left inequality follows since
$\text{Pr}(\mbox{$\cal{D}$}_{E}\cup\mathcal{M}_{E})\geq\text{Pr}(\mbox{$\cal{D}$}_{E})$
and
$\text{Pr}(\mbox{$\cal{M}$}_{E}\cup\mbox{$\cal{M}$}_{E})\geq\text{Pr}(\mbox{$\cal{M}$}_{E})$.
The right-most inequality follows because, by the union bound,
$P_{e}^{(n)}\leq\text{Pr}(\mathcal{D}_{E})$ \+ $\text{Pr}(\mathcal{M}_{E})\leq
2P_{\textnormal{max}}^{(n)}$. So, in general, $P_{\textnormal{max}}^{(n)}$ is
more optimistic than $P_{e}^{(n)}$. However, if we wish the probability of
error to vanish as $n\to\infty$, then the two definitions are equivalent since
$P_{e}^{(n)}$ vanishes if, and only if, $P_{\textnormal{max}}^{(n)}$ vanishes.

In this paper, we will mainly consider the more pessimistic definition of
probability of error $P_{e}^{(n)}$. For this definition, one can model an
inactive user by an active user that transmits message $W_{i}=0$ and an
encoder that maps the zero message to the all-zero codeword. The decoder then
simply guesses the transmitted message, and the error probability
$P_{e}^{(n)}$ is given by the probability that the decoder’s guess
$\hat{W}_{i}$ is different from $W_{i}$. Mathematically, this can be described
as follows. We enhance the message set to

$\displaystyle\overline{\mbox{$\cal{M}$}}_{n}^{(i)}\triangleq\mbox{$\cal{M}$}_{n}^{(i)}\cup\\{0\\}$

and define the distribution of the $i$-th user’s message as

$\displaystyle\text{Pr}\\{W_{i}=w\\}=\begin{cases}1-\alpha_{n},&\quad w=0\\\
\frac{\alpha_{n}}{M_{n}^{(i)}},&\quad
w\in\\{1,\ldots,M_{n}^{(i)}\\}.\end{cases}$ (4)

We assume that the codebook is such that message $0$ is mapped to the all-zero
codeword. Then, the channel model (1) can be written as

$\displaystyle{\bf Y}$ $\displaystyle=\sum_{i=1}^{\ell_{n}}{\bf
x}_{i}(W_{i})+{\bf Z}.$

We next introduce the notion of an
$(n,\bigl{\\{}M_{n}^{(\cdot)}\bigr{\\}},\bigl{\\{}E_{n}^{(\cdot)}\bigr{\\}},\epsilon)$
code.

###### Definition 1

For $0\leq\epsilon\leq 1$, an
$(n,\bigl{\\{}M_{n}^{(\cdot)}\bigr{\\}},\bigl{\\{}E_{n}^{(\cdot)}\bigr{\\}},\epsilon)$
code for the Gaussian MnAC consists of:

  1. 1.

Encoding functions
$f_{i}:\\{0,1,\ldots,M_{n}^{(i)}\\}\rightarrow\mathbb{R}^{n}$,
$i=1,\ldots,\ell_{n}$ which map user $i$’s message to the codeword ${\bf
x}_{i}(W_{i})$, satisfying the energy constraint

$\displaystyle\sum_{j=1}^{n}x_{ij}^{2}(W_{i})\leq
E_{n}^{(i)},\quad\textnormal{ with probability one}$ (5)

where $x_{ij}(W_{i})$ is the $j$-th symbol of the transmitted codeword. We set
$x_{ij}(0)=0$, $j=1,\ldots,n$ for all users $i=1,\ldots,\ell_{n}$.

  2. 2.

Decoding function
$g:\mathbb{R}^{n}\rightarrow\\{0,1,\ldots,M_{n}^{(1)}\\}\times\ldots\times\\{0,1,\ldots,M_{n}^{(\ell_{n})}\\}$
which maps the received vector ${\bf Y}$ to the messages of all users and
whose probability of error $P_{e}^{(n)}$ satisfies

$\displaystyle P_{e}^{(n)}\triangleq\text{Pr}\\{g({\bf
Y})\neq(W_{1},\ldots,W_{\ell_{n}})\\}\leq\epsilon.$ (6)

The probability of error in (6) is equal to $P_{e}^{(n)}$ defined in (2).
Indeed, the event $g({\bf Y})\neq(W_{1},\ldots,W_{\ell_{n}})$ occurs if, and
only if, there exists at least one index $i=1,\ldots,\ell_{n}$ for which
$\hat{W_{i}}\neq W_{i}$. This in turn implies that either event
$\mbox{$\cal{D}$}_{E}$ occurs (if $W_{i}=0$) or event $\mbox{$\cal{M}$}_{E}$
occurs (if $W_{i}\neq 0$). Conversely, if the event
$\mbox{$\cal{D}$}_{E}\cup\mbox{$\cal{M}$}_{E}$ occurs, then there exists
either some $i\notin\mbox{$\cal{U}$}_{n}$ for which $\hat{W}_{i}\neq 0$ or
some $i\in\mbox{$\cal{U}$}_{n}$ for which $\hat{W}_{i}\neq W_{i}$.
Consequently, there exists at least one index $i=1,\ldots,\ell_{n}$ for which
$\hat{W_{i}}\neq W_{i}$. It follows that the events $g({\bf
Y})\neq(W_{1},\ldots,W_{\ell_{n}})$ and
$\mbox{$\cal{D}$}_{E}\cup\mbox{$\cal{M}$}_{E}$ are equivalent.

We shall say that the _codebook of user $i$ is orthogonal_ if the inner
product between ${\bf x}_{i}(w)$ and ${\bf x}_{i}(w^{\prime})$ is zero for
every $w\neq w^{\prime}$, where $w,w^{\prime}=1,\ldots,M_{n}^{(i)}$.
Similarly, we shall say that an _access scheme is orthogonal_ if, for any two
users $i$ and $j$, the inner product between ${\bf x}_{i}(w)$ and ${\bf
x}_{j}(w^{\prime})$ is zero for every $w=1,\ldots,M_{n}^{(i)}$ and
$w^{\prime}=1,\ldots,M_{n}^{(j)}$. An
$(n,\\{M_{n}^{(\cdot)}\\},\\{E_{n}^{(\cdot)}\\},\epsilon)$ code is said to be
_symmetric_ if $M_{n}^{(i)}=M_{n}$ and $E_{n}^{(i)}=E_{n}$ for all
$i=1,\ldots,\ell_{n}$. For compactness, we denote such a code by
$(n,M_{n},E_{n},\epsilon)$. In this paper, we restrict ourselves to symmetric
codes.

###### Definition 2

For a symmetric code, the rate per unit-energy $\dot{R}$ is said to be
$\epsilon$-achievable if for every $\delta>0$ there exists an $n_{0}$ such
that, if $n\geq n_{0}$, then an $(n,M_{n},E_{n},\epsilon)$ code can be found
whose rate per unit-energy satisfies $\frac{\log
M_{n}}{E_{n}}>\dot{R}-\delta$. Furthermore, $\dot{R}$ is said to be achievable
if it is $\epsilon$-achievable for all $0<\epsilon<1$. The capacity per unit-
energy $\dot{C}$ is the supremum of all achievable rates per unit-energy. The
$\epsilon$-capacity per unit-energy $\dot{C}_{\epsilon}$ is the supremum of
all $\epsilon$-achievable rates per unit-energy.

###### Remark 1

In [14, Def. 2], a rate per unit-energy $\dot{R}$ is said to be
$\epsilon$-achievable if for every $\alpha>0$ there exists an $E_{0}$ such
that, if $E\geq E_{0}$, then an $(n,M,E,\epsilon)$ code can be found whose
rate per unit-energy satisfies $\frac{\log M}{E}>\dot{R}-\alpha$. Thus, in
contrast to Definition 2, the energy $E$ is required to be larger than some
threshold, rather than the blocklength $n$. For the MnAC, where the number of
users grows with the blocklength, we believe it is more natural to impose a
threshold on $n$. Definition 2 is also consistent with the definition of
energy-per-bit in [4, 13]. Further note that, for the capacity per unit-
energy, where a vanishing error probability is required, Definition 2 is in
fact equivalent to [14, Def. 2], since $P_{e}^{(n)}\to 0$ only if
$E_{n}\to\infty$ (see Lemma 4 ahead).

###### Remark 2

Many works in the literature on many-access channels, including [4, 5, 13, 10,
11, 12], consider a _per-user probability of error_

$P_{e,A}^{(n)}\triangleq\frac{1}{\ell_{n}}\sum_{i=1}^{\ell_{n}}\textnormal{Pr}\\{\hat{W_{i}}\neq
W_{i}\\}$ (7)

rather than the probability of error in (6). In this paper, we shall refer to
(6) as _joint error probability (JPE)_ and to (7) as _average error
probability (APE)_. While we mainly consider the JPE, we also discuss the
capacity per unit-energy for APE. To this end, we define an
$(n,\\{M_{n}^{(\cdot)}\\},\\{E_{n}^{(\cdot)}\\},\epsilon)$ code for APE with
the same encoding and decoding functions described in Definition 1, but with
the probability of error (6) replaced with (7). The capacity per unit-energy
and the $\epsilon$-capacity per unit-energy for APE, denoted by $\dot{C}^{A}$
and $\dot{C}_{\epsilon}^{A}$ respectively, are then defined as in Definition
2.

###  II-B Order Notation

Let $\\{a_{n}\\}$ and $\\{b_{n}\\}$ be two sequences of nonnegative real
numbers. We write $a_{n}=O(b_{n})$ if
$\limsup_{n\to\infty}\frac{a_{n}}{b_{n}}<\infty$. Similarly, we write
$a_{n}=o(b_{n})$ if $\lim_{n\rightarrow\infty}\frac{a_{n}}{b_{n}}=0$, and
$a_{n}=\Omega(b_{n})$ if
$\liminf\limits_{n\rightarrow\infty}\frac{a_{n}}{b_{n}}>0$. The notation
$a_{n}=\Theta(b_{n})$ indicates that $a_{n}=O(b_{n})$ and
$a_{n}=\Omega(b_{n})$. Finally, we write $a_{n}=\omega(b_{n})$ if
$\lim\limits_{n\rightarrow\infty}\frac{a_{n}}{b_{n}}=\infty$.

##  III Capacity per Unit-Energy of Non-Random Many-Access Channels

In this section, we study the Gaussian MnAC under the assumption that all
users are active, i.e., $\alpha_{n}=1$ and $k_{n}=\ell_{n}$. We present our
results on the non-random MnACs in Subsection III-A. In particular, in Theorem
1, we characterize the capacity per unit-energy as a function of the order of
$k_{n}$. Then, in Theorem 2, we give a characterization of the largest rate
per unit-energy achievable using an orthogonal-access scheme with orthogonal
codebooks. Finally, in Theorem 3, we present our results on the capacity per
unit-energy for APE. The proofs of Theorems 1–3 are given in Subsections
III-B, III-C, and III-D, respectively.

###  III-A Main Results

###### Theorem 1

The capacity per unit-energy of the Gaussian non-random MnAC has the following
behaviour:

  1. 1.

If $k_{n}=o(n/\log n)$, then any rate per unit-energy satisfying
$\dot{R}<\frac{\log e}{N_{0}}$ is achievable. Moreover, this rate can be
achieved by an orthogonal-access scheme.

  2. 2.

If $k_{n}=\omega(n/\log n)$, then $\dot{C}=0$. In words, if the order of
$k_{n}$ is strictly above $n/\log n$, then no coding scheme achieves a
positive rate per unit-energy.

  3. 3.

If $k_{n}=\Theta(\frac{n}{\log n})$, then $0<\dot{C}<\frac{\log e}{N_{0}}$. In
words, if the order of $k_{n}$ is exactly $n/\log n$, then a positive rate per
unit-energy, but strictly less than $\frac{\log e}{N_{0}}$ is achievable.

###### Proof:

See Subsection III-B. ∎

Theorem 1 demonstrates that there is a sharp transition between orders of
growth of $k_{n}$ where each user can achieve the single-user capacity per
unit-energy $\frac{\log e}{N_{0}}$, i.e., where users can communicate as if
free of interference, and orders of growth where no positive rate per unit-
energy is feasible. The transition threshold separating these two regimes is
at the order of growth $n/\log n$. The capacity per unit-energy can be
achieved using an orthogonal-access scheme where each user is assigned an
exclusive time slot. As we shall show in Section IV, such an access scheme is
wasteful in terms of resources and strictly suboptimal when users are active
only sporadically. The theorem also demonstrates that, when the order of
growth of $k_{n}$ is exactly equal to $n/\log n$, the rate per unit-energy is
strictly positive, but also strictly less than $\frac{\log e}{N_{0}}$.

As mentioned in the introduction, when the number of users is finite, all
users can achieve the single-user capacity per unit-energy $\frac{\log
e}{N_{0}}$ by an orthogonal-access scheme where each user uses an orthogonal
codebook. In the following theorem, we show that this is not necessarily the
case anymore when the number of users grows with the blocklength.

###### Theorem 2

The largest rate per unit-energy $\dot{C}_{\bot\bot}$ achievable with an
orthogonal-access scheme and orthogonal codebooks has the following behaviour:

  1. 1)

If $k_{n}=o(n^{c})$ for every $c>0$, then $\dot{C}_{\bot\bot}=\frac{\log
e}{N_{0}}$.

  2. 2)

If $k_{n}=\Theta\left({n^{c}}\right)$, then

$\dot{C}_{\bot\bot}=\begin{cases}\frac{\log
e}{N_{0}}\frac{1}{\left(1+\sqrt{\frac{c}{1-c}}\right)^{2}},\quad&\textnormal{if
$0<c\leq 1/2$}\\\ \frac{\log e}{2N_{0}}(1-c),\quad&\textnormal{if
$1/2<c<1$}.\end{cases}$

###### Proof:

See Subsection III-C. ∎

Theorem 2 shows that an orthogonal-access scheme in combination with
orthogonal codebooks is optimal only if $k_{n}$ grows more slowly than any
positive power of $n$. Part 2) of Theorem 2 gives the largest rate per unit-
energy achievable when the order of $k_{n}$ is a positive power of $n$.

###### Remark 3

Observe that the behavior of $\dot{C}_{\bot\bot}$ as a function of $c$ can be
divided into two regimes: if $1/2<c<1$, then $\dot{C}_{\bot\bot}$ decays
linearly in $c$; if $0<c\leq 1/2$, then the dependence of $\dot{C}_{\bot\bot}$
on $c$ is nonlinear. This is a consequence of the behavior of the error
exponent achievable with orthogonal codebooks. More specifically, Theorem 2
follows from lower and upper bounds on the probability of error that become
asymptotically tight as $E\to\infty$; see Lemma 6. The lower bound follows
from the sphere-packing bound [15]. The upper bound is obtained by applying
Gallager’s $\rho$-trick to improve upon the union bound [16, Sec. 2.5],
followed by an optimization over the parameter $0\leq\rho\leq 1$. When the
rate per unit-energy is smaller than $\frac{1}{4}\frac{\log e}{N_{0}}$, the
optimal value of $\rho$ is $1$, and the exponent of the upper bound depends
linearly on the rate per unit-energy. For rates per unit-energy above
$\frac{1}{4}\frac{\log e}{N_{0}}$, the optimal value of $\rho$ depends on the
rate per unit-energy, which results in a nonlinear dependence of the exponent
on the rate per unit-energy. This behavior of the error exponent as a function
of the rate per unit-energy translates to the two regimes of
$\dot{C}_{\bot\bot}$ observed in Theorem 2.

Next we discuss the behaviour of the capacity per unit-energy for APE. We show
that, if the order of growth of $k_{n}$ is sublinear, then each user can
achieve the single-user capacity per unit-energy $\frac{\log e}{N_{0}}$.
Conversely, if the growth of $k_{n}$ is linear or above, then the capacity per
unit-energy is zero. We have the following theorem.

###### Theorem 3

The capacity per unit-energy $\dot{C}^{A}$ for APE has the following behavior:

  1. 1.

If $k_{n}=o(n)$, then $\dot{C}^{A}=\frac{\log e}{N_{0}}$. Furthermore, the
capacity per unit-energy can be achieved by an orthogonal-access scheme where
each user uses an orthogonal codebook.

  2. 2.

If $k_{n}=\Omega(n)$, then $\dot{C}^{A}=0$.

###### Proof:

See Subsection III-D. ∎

Theorem 3 demonstrates that under APE the capacity per unit-energy has a
similar behaviour as under JPE. Again, there is a sharp transition between
orders of growth of $k_{n}$ where interference-free communication is possible
and orders of growth where no positive rate per unit-energy is feasible. The
main difference is that the transition threshold is shifted from $n/\log n$ to
$n$. Such an improvement on the order of growth is possible because, for the
probability of error to vanish as $n\to\infty$, the energy $E_{n}$ needs to
satisfy different necessary constraints under JPE and APE. Indeed, we show in
the proof of Theorem 1 that the JPE vanishes only if the energy $E_{n}$ scales
logarithmically in the number of users (Lemma 5), and a positive rate per
unit-energy is feasible only if the total power $k_{n}E_{n}/n$ is bounded in
$n$. No sequence $\\{E_{n}\\}$ can satisfy both these conditions if
$k_{n}=\omega(n/\log n)$. In contrast, for the APE to vanish asymptotically,
the energy $E_{n}$ does not need to grow logarithmically in the number of
users, it suffices that it tends to infinity as $n\to\infty$. We can then find
sequences $\\{E_{n}\\}$ that tend to infinity and for which $k_{n}E_{n}/n$ is
bounded if, and only if, $k_{n}$ is sublinear in $n$. Also note that, for APE,
an orthogonal-access scheme with orthogonal codebooks is optimal for all
orders of $k_{n}$, whereas for JPE it is only optimal if the order of $k_{n}$
is not a positive power of $n$.

###  III-B Proof of Theorem 1

We first give an outline of the proof of Theorem 1. To prove Part 1), we use
an orthogonal-access scheme where the total number of channel uses is divided
equally among all the users. Each user uses the same single-user code in the
assigned channel uses. The receiver decodes the message of each user
separately, which is possible because the access scheme is orthogonal. We next
express the overall probability of error in terms of the number of users
$k_{n}$ and the probability of error achieved by the single-user code in an
AWGN channel, which we then show vanishes as $n\to\infty$ if $k_{n}=o(n/\log
n)$. The proof of Part 2) hinges mainly on two facts. The first one is that
the probability of error vanishes only if the energy $E_{n}$ scales at least
logarithmically in the number of users, i.e., $E_{n}=\Omega(\log k_{n})$.222A
similar bound was presented in [17, p. 82] for the case where $M_{n}=2$. The
second one is that we have $\dot{R}>0$ only if the total power $k_{n}E_{n}/n$
is bounded as $n\to\infty$, which is a direct consequence of Fano’s
inequality. If $k_{n}=\omega(n/\log n)$, then there is no sequence
$\\{E_{n}\\}$ that simultaneously satisfies these two conditions. Part 3)
follows by revisiting the proofs of Parts 1) and 2) for the case where
$k_{n}=\Theta(n/\log n)$.

####  III-B1 Proof of Part 1)

The achievability uses an orthogonal-access scheme where, in each time step,
only one user transmits, the other users remain silent. We first note that the
probability of correct decoding of any orthogonal-access scheme is given by

$\displaystyle P_{c}^{(n)}=\prod_{i=1}^{k_{n}}\left(1-P_{e,i}\right)$

where $P_{e,i}=\text{Pr}(\hat{W}_{i}\neq W_{i})$ denotes the probability of
error in decoding user $i$’s message. In addition, if each user follows the
same coding scheme, then the probability of correct decoding is given by

$\displaystyle P_{c}^{(n)}$ $\displaystyle=\left(1-P_{e,1}\right)^{k_{n}}.$
(8)

For a Gaussian point-to-point channel with  blocklength $N$ and power
constraint $P$, i.e., $\frac{E_{N}}{N}\leq P$, there exists an encoding and
decoding scheme whose average probability of error is upper-bounded by

$\displaystyle P(\mbox{$\cal{E}$})$ $\displaystyle\leq
M_{N}^{\rho}\exp[-NE_{0}(\rho,P)],\;\mbox{ for every }0<\rho\leq 1$ (9)

where

$\displaystyle E_{0}(\rho,P)$
$\displaystyle\triangleq\frac{\rho}{2}\ln\left(1+\frac{2P}{(1+\rho)N_{0}}\right).$

This bound is due to Gallager and can be found in [18, Sec. 7.4].

Now let us consider an orthogonal-access scheme in which each user gets
$n/k_{n}$ channel uses, and we timeshare between users. Each user follows the
coding scheme that achieves (9) with power constraint
$P_{n}=\frac{E_{n}}{n/k_{n}}$. Note that this coding scheme satisfies also the
energy constraint (5).  Then, we obtain the following upper bound $P_{e,1}$
for a fixed rate per unit-energy $\dot{R}=\frac{\log M_{n}}{E_{n}}$, by
substituting in (9) $N$ by $n/k_{n}$ and $P$ by $P_{n}=\frac{E_{n}}{n/k_{n}}$:

$\displaystyle P_{e,1}$ $\displaystyle\leq
M_{n}^{\rho}\exp\left[-\frac{n}{k_{n}}E_{0}(\rho,P_{n})\right]$
$\displaystyle=\exp\left[\rho\ln
M_{n}-\frac{n}{k_{n}}\frac{\rho}{2}\ln\left(1+\frac{2E_{n}k_{n}/n}{(1+\rho)N_{0}}\right)\right]$
$\displaystyle=\exp\left[-E_{n}\rho\left(\frac{\ln(1+\frac{2E_{n}k_{n}/n}{(1+\rho)N_{0}})}{2E_{n}k_{n}/n}-\frac{\dot{R}}{\log
e}\right)\right].$ (10)

Combining (10) with (8), we obtain that the probability of correct decoding
can be lower-bounded as

$\displaystyle
1-P_{e}^{(n)}\geq\Biggl{(}1-\exp\Biggl{[}-E_{n}\rho\Biggl{(}\frac{\ln(1+\frac{2E_{n}k_{n}/n}{(1+\rho)N_{0}})}{2E_{n}k_{n}/n}-\frac{\dot{R}}{\log
e}\Biggr{)}\Biggr{]}\Biggr{)}^{k_{n}}.$ (11)

We next choose $E_{n}=c_{n}\ln n$ with
$c_{n}\triangleq\ln\bigl{(}\frac{n}{k_{n}\ln n}\bigr{)}$. Since, by
assumption, $k_{n}=o(n/\log n)$, this implies that $\frac{k_{n}E_{n}}{n}\to 0$
as $n\to\infty$. Consequently, the first term in the inner-most bracket in
(11) tends to $1/((1+\rho)N_{0})$ as $n\to\infty$. It follows that for
$\dot{R}<\frac{\log e}{N_{0}}$, there exists a sufficiently large $n_{0}$, a
$0<\rho\leq 1$, and a $\delta>0$ such that, for all $n\geq n_{0}$, the right-
hand side (RHS) of (11) is lower-bounded by
$\left(1-\exp[-E_{n}\rho\delta]\right)^{k_{n}}$. Since
$c_{n}\delta\rho\to\infty$ as $n\to\infty$, we have

$\displaystyle\left(1-\exp[-E_{n}\rho\delta]\right)^{k_{n}}$
$\displaystyle\geq\left(1-\frac{1}{n^{2}}\right)^{k_{n}}$
$\displaystyle\geq\left(1-\frac{1}{n^{2}}\right)^{\frac{n}{\log n}}$
$\displaystyle=\left[\left(1-\frac{1}{n^{2}}\right)^{n^{2}}\right]^{\frac{1}{n\log
n}}$ (12)

for $n\geq n_{0}$ and sufficiently large $n_{0}$, such that
$c_{n}\delta\rho\geq 2$ and $k_{n}\leq\frac{n}{\log n}$. Noting that
$(1-\frac{1}{n^{2}})^{n^{2}}\to 1/e$ and $\frac{1}{n\log n}\to 0$ as
$n\to\infty$, we obtain that the RHS of (12) tends to one as $n\to\infty$.
This implies that, if $k_{n}=o(n/\log n)$, then any rate per unit-energy
$\dot{R}<\frac{\log e}{N_{0}}$ is achievable.

####  III-B2 Proof of Part 2)

Let ${\bf W}$ and ${\bf\hat{W}}$ denote the vectors $(W_{1},\ldots,W_{k_{n}})$
and $(\hat{W_{1}},\ldots,\hat{W}_{k_{n}})$, respectively. Then

$\displaystyle k_{n}\log M_{n}$ $\displaystyle=H({\bf W})$
$\displaystyle=H({\bf W}|{\bf\hat{W}})+I({\bf W};{\bf\hat{W}})$
$\displaystyle\leq 1+P_{e}^{(n)}k_{n}\log M_{n}+I({\bf X};{\bf Y})$

by Fano’s inequality and the data processing inequality. By following [19,
Sec. 15.3], it can be shown that $I({\bf X};{\bf
Y})\leq\frac{n}{2}\log\left(1+\frac{2k_{n}E_{n}}{nN_{0}}\right)$.
Consequently,

$\frac{\log M_{n}}{E_{n}}\leq\frac{1}{k_{n}E_{n}}+\frac{P_{e}^{(n)}\log
M_{n}}{E_{n}}+\frac{n}{2k_{n}E_{n}}\log\left(\\!1+\frac{2k_{n}E_{n}}{nN_{0}}\\!\right)\\!.$

This implies that the rate per unit-energy $\dot{R}=(\log M_{n})/E_{n}$ is
upper-bounded by

$\displaystyle\dot{R}\leq\frac{\frac{1}{k_{n}E_{n}}+\frac{n}{2k_{n}E_{n}}\log(1+\frac{2k_{n}E_{n}}{nN_{0}})}{1-P_{e}^{(n)}}.$
(13)

We next show by contradiction that, if $k_{n}=\omega(n/\log n)$, then
$P_{e}^{(n)}\to 0$ as $n\to\infty$ only if $\dot{C}=0$. Thus, assume that
$k_{n}=\omega(n/\log n)$ and that there exists a code with rate per unit-
energy $\dot{R}>0$ such that $P_{e}^{(n)}\to 0$ as $n\to\infty$. To prove that
there is a contradiction we need the following lemma.

###### Lemma 4

If $M_{n}\geq 2$, then $P_{e}^{(n)}\to 0$ only if $E_{n}\to\infty$.

###### Proof:

See Appendix A. ∎

By the assumption $\dot{R}>0$, we have that $M_{n}\geq 2$. Since we further
assumed that $P_{e}^{(n)}\to 0$, Lemma 4 implies that $E_{n}\to\infty$.
Together with (13), this in turn implies that $\dot{R}>0$ is only possible if
$k_{n}E_{n}/n$ is bounded in $n$. Thus,

$\displaystyle E_{n}=O(n/k_{n}).$ (14)

The next lemma presents another necessary condition on the order of $E_{n}$
which contradicts (14).

###### Lemma 5

If $\dot{R}>0$ and $k_{n}\geq 5$, then $P_{e}^{(n)}\to 0$ only if
$E_{n}=\Omega(\log k_{n})$.

###### Proof:

This lemma is a special case of Lemma 12 stated in the proof of Theorem 7 in
Section IV and proven in Appendix D. ∎

We finish the proof by showing that, if $k_{n}=\omega(n/\log n)$, then there
exists no sequence $\\{E_{n}\\}$ of order $\Omega(\log k_{n})$ that satisfies
(14). Indeed, $E_{n}=\Omega(\log k_{n})$ and $k_{n}=\omega(n/\log n)$ imply
that

$\displaystyle E_{n}=\Omega(\log n)$ (15)

because the order of $E_{n}$ is lower-bounded by the order of $\log n-\log\log
n$, and $\log n-\log\log n=\Theta(\log n)$. Furthermore, (14) and
$k_{n}=\omega(n/\log n)$ imply that

$\displaystyle E_{n}$ $\displaystyle=o(\log n).$ (16)

Since no sequence $\\{E_{n}\\}$ can simultaneously satisfy (15) and (16), this
contradicts the assumption that there exists a code with a positive rate per
unit-energy such that the probability of error vanishes as $n$ tends to
infinity. Consequently, if $k_{n}=\omega(n/\log n)$, then no positive rate per
unit-energy is achievable. This proves Part 2) of Theorem 1.

####  III-B3 Proof of Part 3)

To show that $\dot{C}>0$, we use the same orthogonal-access scheme as in the
proof of Part 1) of Theorem 1. Thus, each user is assigned $n/k_{n}$ channel
uses, and only one user transmits at a time. We further assume that each user
uses energy $E_{n}=c\log n$, where $c$ is some positive constant to be
determined later. By the assumption $k_{n}=\Theta(n/\log n)$, there exist
$n_{0}>0$ and $0<a_{1}\leq a_{2}$ such that, for all $n\geq n_{0}$, we have

$a_{1}\frac{n}{\log n}\leq k_{n}\leq a_{2}\frac{n}{\log n}.$ (17)

The probability of error in decoding the first user’s message is then given by
(10), namely,

$\displaystyle P_{e,1}$
$\displaystyle\leq\exp\left[-E_{n}\rho\left(\frac{\ln\bigl{(}1+\frac{2E_{n}k_{n}/n}{(1+\rho)N_{0}}\bigr{)}}{2E_{n}k_{n}/n}-\frac{\dot{R}}{\log
e}\right)\right]$ $\displaystyle\leq\exp\left[-c\log
n\,\rho\left(\frac{\ln\bigl{(}1+\frac{2a_{2}c}{(1+\rho)N_{0}}\bigr{)}}{2a_{2}c}-\frac{\dot{R}}{\log
e}\right)\right],\quad\textnormal{for every $0<\rho\leq 1,\;n\geq n_{0}$}$
(18)

where the last inequality follows since $k_{n}E_{n}/n\leq a_{2}c$ for $n\geq
n_{0}$.

We next set

$\dot{R}=\frac{\log
e}{2}\frac{\ln\bigl{(}1+\frac{2a_{2}c}{(1+\rho)N_{0}}\bigr{)}}{2a_{2}c}$

which is clearly positive for fixed $a_{2}$, $c$, and $\rho$. The upper bound
(18) then becomes

$P_{e,1}\leq\exp\left[-\log
n\,\frac{\rho}{2}c\frac{\ln\bigl{(}1+\frac{2a_{2}c}{(1+\rho)N_{0}}\bigr{)}}{2a_{2}c}\right],\quad
n\geq n_{0}.$ (19)

For every fixed $a_{2}$ and $\rho$, the term

$\frac{\rho}{2}c\frac{\ln\bigl{(}1+\frac{2a_{2}c}{(1+\rho)N_{0}}\bigr{)}}{2a_{2}c}=\frac{\rho}{2}\frac{\ln\bigl{(}1+\frac{2a_{2}c}{(1+\rho)N_{0}}\bigr{)}}{2a_{2}}$

is a continuous, monotonically increasing, function of $c$ that is independent
of $n$ and ranges from zero to infinity. We can therefore find a $c$ such that
(19) simplifies to

$P_{e,1}\leq\exp[-\ln n]=\frac{1}{n},\quad n\geq n_{0}.$

The above scheme has a positive rate per unit-energy. It remains to show that
this rate per unit-energy is also achievable, i.e., that the overall
probability of correct decoding tends to one as $n\to\infty$. To this end, we
use (8) to obtain that

$\displaystyle 1-P_{e}^{(n)}$ $\displaystyle=(1-P_{e,1})^{k_{n}}$
$\displaystyle\geq\left(1-\frac{1}{n}\right)^{a_{2}n/\log n},\quad n\geq
n_{0}.$ (20)

Since $(1-\frac{1}{n})^{n}\to 1/e$ and $\frac{a_{2}}{\log n}\to 0$ as
$n\to\infty$, the RHS of (20) tends to one as $n\to\infty$, hence so does the
probability of correct decoding.

We next show that $\dot{C}<\frac{\log e}{N_{0}}$. Lemma 5 implies that, if
$k_{n}=\Theta(n/\log n)$, then $P_{e}^{(n)}$ vanishes only if
$E_{n}=\Omega(\log n)$. Furthermore, if $E_{n}=\omega(\log n)$, then it
follows from (13) that $\dot{C}=0$ since, in this case, $k_{n}E_{n}/n$ tends
to infinity as $n\to\infty$. Without loss of generality, we can thus assume
that $E_{n}$ must satisfy $E_{n}=\Theta(\log n)$. Thus, there exist
$n^{\prime}_{0}>0$ and $0<l_{1}\leq l_{2}$ such that, for all $n\geq
n^{\prime}_{0}$, we have $l_{1}\log n\leq E_{n}\leq l_{2}\log n$. Together
with (17), this implies that $\frac{k_{n}E_{n}}{n}\geq a_{1}l_{l}$ for all
$n\geq\max(n_{0},n^{\prime}_{0})$. The claim that $\dot{C}<\frac{\log
e}{N_{0}}$ follows then directly from (13). Indeed, using that
$\frac{\log(1+x)}{x}<\log e$ for every $x>0$, we obtain that

$\frac{n}{2k_{n}E_{n}}\log\left(1+\frac{2k_{n}E_{n}}{nN_{0}}\right)\leq\frac{1}{2a_{1}l_{1}}\log\left(1+\frac{2a_{1}l_{1}}{N_{0}}\right)<\frac{\log
e}{N_{0}},\quad n\geq\max(n_{0},n^{\prime}_{0}).$ (21)

By (13), in the limit as $P_{e}^{(n)}\to 0$ and $E_{n}\to\infty$, the rate per
unit-energy is upper-bounded by (21). It thus follows that $\dot{C}<\frac{\log
e}{N_{0}}$, which concludes the proof of Part 3) of Theorem 1.

###  III-C Proof of Theorem 2

The proof of Theorem 2 is based on the following lemma, which presents bounds
on the probability of error achievable over a Gaussian point-to-point channel
with an orthogonal codebook.

###### Lemma 6

The probability of error $P_{e,1}=\text{Pr}(\hat{W}\neq W)$ achievable over a
Gaussian point-to-point channel with an orthogonal codebook with $M$ codewords
and energy less than or equal to $E$ satisfies the following bounds:

  1. 1.

For $0<\dot{R}\leq\frac{1}{4}\frac{\log e}{N_{0}}$,

$\displaystyle\exp\left[-\frac{\ln M}{\dot{R}}\left(\frac{\log
e}{2N_{0}}-\dot{R}+\beta_{E}\right)\right]\leq P_{e,1}\leq\exp\left[-\frac{\ln
M}{\dot{R}}\left(\frac{\log e}{2N_{0}}-\dot{R}\right)\right].$ (22)

  2. 2.

For $\frac{1}{4}\frac{\log e}{N_{0}}\leq\dot{R}\leq\frac{\log e}{N_{0}}$,

$\displaystyle\exp\left[-\frac{\ln M}{\dot{R}}\left(\left(\sqrt{\frac{\log
e}{N_{0}}}-\sqrt{\dot{R}}\right)^{2}+\beta^{\prime}_{E}\right)\right]\leq
P_{e,1}\leq\exp\left[-\frac{\ln M}{\dot{R}}\left(\sqrt{\frac{\log
e}{N_{0}}}-\sqrt{\dot{R}}\right)^{2}\right].$ (23)

In (22) and (23), $\beta_{E}$ and $\beta^{\prime}_{E}$ are some constants of
order $O(\frac{1}{\sqrt{E}})$.

###### Proof:

The upper bounds in (22) and (23) are obtained by upper-bounding the
probability of error using Gallager’s $\rho$-trick to improve upon the union
bound [16, Sec. 2.5], followed by a maximization over $\rho$. For
$0<\dot{R}\leq\frac{1}{4}\frac{\log e}{N_{0}}$, the optimal $\rho$ is equal to
$1$; for $\frac{1}{4}\frac{\log e}{N_{0}}\leq\dot{R}\leq\frac{\log e}{N_{0}}$,
the optimal $\rho$ is a function of $\dot{R}$. Hence, the upper bounds in (22)
and (23) have different dependencies on $\dot{R}$. The lower bounds in (22)
and (23) follow from the sphere-packing bound by Shannon, Gallager, and
Berlekamp [15]. However, their approach to improve the sphere-packing bound at
low rates by writing codewords as concatenations of subcodewords and lower-
bounding the error exponent by the convex combination of the error exponents
of these subcodewords does not directly apply to our setting where $\log M/E$
is held fixed and $E\to\infty$ (rather than $\log M/n$ is held fixed and
$n\to\infty$). The reason is that, for some orthogonal codebooks, the energy
of one of the subcodebooks is always zero, resulting in a trivial case where
the Shannon-Gallager-Berlekamp approach cannot improve upon the original
sphere-packing bound. To sidestep this problem, we lower-bound the probability
of error by first rotating the orthogonal codebook in such a way that the
energy of each subcodeword is proportional to its blocklength, after which the
Shannon-Gallager-Berlekamp approach can be applied. For a full proof of Lemma
6, see Appendix B. ∎

Next, we define

$\displaystyle a\triangleq\left\\{\begin{array}[]{cl}\frac{\left(\frac{\log
e}{2N_{0}}-\dot{R}\right)}{\dot{R}},&\quad\mbox{if
}0<\dot{R}\leq\frac{1}{4}\frac{\log e}{N_{0}}\\\ \frac{\left(\sqrt{\frac{\log
e}{N_{0}}}-\sqrt{\dot{R}}\right)^{2}}{\dot{R}},&\quad\mbox{if
}\frac{1}{4}\frac{\log e}{N_{0}}\leq\dot{R}\leq\frac{\log
e}{N_{0}}\end{array}\right.$ (26)

and let $a_{E}\triangleq a+\max\\{\beta_{E},\beta^{\prime}_{E}\\}$. Then, the
bounds in Lemma 6 can be written as

$\displaystyle 1/M^{a_{E}}$ $\displaystyle\leq P_{e,1}\leq 1/M^{a}.$ (27)

Now let us consider the case where the users apply an orthogonal-access scheme
together with orthogonal codebooks. For such a scheme, the collection of
codewords from all users is orthogonal, hence there are at most $n$ codewords
of length $n$. Since with a symmetric code, each user transmits the same
number of messages, it follows that each user transmits $M_{n}=n/k_{n}$
messages with codewords of energy less than or equal to $E_{n}$. In this case,
we obtain from (8) and (27) that

$\displaystyle\left(1-\left(\frac{k_{n}}{n}\right)^{a}\right)^{k_{n}}\leq\left(1-P_{e,1}\right)^{k_{n}}\leq\left(1-\left(\frac{k_{n}}{n}\right)^{a_{E_{n}}}\right)^{k_{n}}$

which, denoting $a_{n}\triangleq a_{E_{n}}$, can be written as

$\displaystyle\left[\left(1-\left(\frac{k_{n}}{n}\right)^{a}\right)^{(\frac{n}{k_{n}})^{a}}\right]^{\frac{k_{n}^{1+a}}{n^{a}}}\leq\left(1-P_{e,1}\right)^{k_{n}}\leq\left[\left(1-\left(\frac{k_{n}}{n}\right)^{a_{n}}\right)^{(\frac{n}{k_{n}})^{a_{n}}}\right]^{\frac{k_{n}^{1+a_{n}}}{n^{a_{n}}}}.$
(28)

Since Theorem 2 only concerns a sublinear number of users, we have

$\displaystyle\lim\limits_{n\to\infty}\left(1-\left(\frac{k_{n}}{n}\right)^{a}\right)^{(\frac{n}{k_{n}})^{a}}$
$\displaystyle=\frac{1}{e}.$

Furthermore, if $P_{e}^{(n)}\to 0$ then, by Lemma 4, $E_{n}\to\infty$ as
$n\to\infty$. In this case, $a_{n}$ converges to the finite value $a$ as
$n\to\infty$, and we obtain

$\displaystyle\lim\limits_{n\to\infty}\left(1-\left(\frac{k_{n}}{n}\right)^{a_{n}}\right)^{(\frac{n}{k_{n}})^{a_{n}}}$
$\displaystyle=\frac{1}{e}.$

So (28) implies that $P_{e}^{(n)}\to 0$ as $n\to\infty$ if

$\displaystyle\lim\limits_{n\to\infty}{\frac{k_{n}^{1+a}}{n^{a}}}=0$ (29)

and only if

$\displaystyle\lim\limits_{n\to\infty}{\frac{k_{n}^{1+a_{n}}}{n^{a_{n}}}}=0.$
(30)

We next use these observations to prove Parts 1) and 2) of Theorem 2. We begin
with Part 1). Let $\dot{R}<\frac{\log e}{N_{0}}$. Thus, we have $a>0$ which
implies that we can find a constant $\eta<a/(1+a)$ such that
$n^{\eta(1+a)}/n^{a}\to 0$ as $n\to\infty$. Since, by assumption,
$k_{n}=o(n^{c})$ for every $c>0$, it follows that there exists an $n_{0}$ such
that, for all $n\geq n_{0}$, we have $k_{n}\leq n^{\eta(1+a)}$. This implies
that (29) is satisfied, from which Part 1) follows.

We next prove Part 2) of Theorem 2. Indeed, if
$k_{n}=\Theta\left({n^{c}}\right)$, $0<c<1$, then there exist $0<l_{1}\leq
l_{2}$ and $n_{0}$ such that, for all $n\geq n_{0}$, we have $(l_{1}n)^{c}\leq
k_{n}\leq(l_{2}n)^{c}$. Consequently,

$\displaystyle{\frac{(l_{1}n)^{c(1+a_{n})}}{n^{a_{n}}}}\leq{\frac{k_{n}^{1+a_{n}}}{n^{a_{n}}}}\leq{\frac{(l_{2}n)^{c(1+a_{n})}}{n^{a_{n}}}}.$
(31)

If $P_{e}^{(n)}\to 0$, then from (30) we have
${\frac{k_{n}^{1+a_{n}}}{n^{a_{n}}}}\to 0$. Thus, (31) implies that
$c(1+a_{n})-a_{n}$ converges to a negative value. Since $c(1+a_{n})-a_{n}$
tends to $c(1+a)-a$ as $n\to\infty$, it follows that $P_{e}^{(n)}\to 0$ only
if $c(1+a)-a<0$, which is the same as $a>c/(1-c)$. Using similar arguments, it
follows from (29) that if $a>c/(1-c)$, then $P_{e}^{(n)}\to 0$. Hence,
$P_{e}^{(n)}\to 0$ if, and only if, $a>c/(1-c)$. It can be observed from (26)
that $a$ is a monotonically decreasing function of $\dot{R}$. So for
$k_{n}=\Theta\left({n^{c}}\right),0<c<1$, the capacity per unit-energy
$\dot{C}_{\bot\bot}$ is given by

$\displaystyle\dot{C}_{\bot\bot}=\sup\\{\dot{R}\geq 0:a(\dot{R})>c/(1-c)\\}$

where we write $a(\dot{R})$ to make it clear that $a$ as defined in (26) is a
function of $\dot{R}$. This supremum can be computed as

$\dot{C}_{\bot\bot}=\begin{cases}\frac{\log
e}{N_{0}}\left(\frac{1}{1+\sqrt{\frac{c}{1-c}}}\right)^{2},&\quad\mbox{if
}0<c\leq 1/2\\\ \frac{\log e}{2N_{0}}(1-c),&\quad\mbox{if }1/2<c<1\end{cases}$

which proves Part 2) of Theorem 2.

###  III-D Proof of Theorem 3

####  III-D1 Proof of Part 1)

We first argue that $P_{e,A}^{(n)}\to 0$ only if $E_{n}\to\infty$, and that in
this case, $\dot{C}^{A}\leq\frac{\log e}{N_{0}}$. Indeed, let
$P_{e,i}\triangleq\textnormal{Pr}\\{\hat{W}_{i}\neq W_{i}\\}$ denote the
probability that message $W_{i}$ is decoded erroneously. We then have that
$P_{e,A}^{(n)}\geq\min_{i}P_{e,i}$. Furthermore, $P_{e,i}$ is lower-bounded by
the error probability of the Gaussian single-user channel, since a single-user
channel can be obtained from the MnAC if a genie informs the receiver about
the codewords transmitted by users $j\neq i$. By applying the lower bound [20,
eq. (30)] on the error probability of the Gaussian single-user channel, we
thus obtain

$P_{e,A}^{(n)}\geq Q\left(\sqrt{\frac{2E_{n}}{N_{0}}}\right),\quad M_{n}\geq
2$ (32)

where $Q$ denotes the $Q$-function, i.e., the tail distribution function of
the standard Gaussian distribution. Hence, $P_{e,A}^{(n)}\to 0$ only if
$E_{n}\to\infty$. As mentioned in Remark 1, when $E_{n}$ tends to infinity as
$n\to\infty$, the capacity per unit-energy $\dot{C}^{A}$ coincides with the
capacity per unit-energy defined in [14], which for the Gaussian single-user
channel is given by $\frac{\log e}{N_{0}}$ [14, Ex. 3]. Furthermore, if
$P_{e,A}^{(n)}\to 0$ as $n\to\infty$, then there exists at least one user $i$
for which $P_{e,i}\to 0$ as $n\to\infty$. By the above genie argument, this
user’s rate per unit-energy is upper-bounded by the capacity per unit-energy
of the Gaussian single-user channel. Since, for the class of symmetric codes
considered in this paper, each user transmits at the same rate per unit-
energy, we conclude that $\dot{C}^{A}\leq\frac{\log e}{N_{0}}$.

We next show that any rate per unit-energy $\dot{R}<\frac{\log e}{N_{0}}$ is
achievable by an orthogonal-access scheme where each user uses an orthogonal
codebook of blocklength $n/k_{n}$. To transmit message $w_{i}$, user $i$ sends
in his assigned slot the codeword ${\bf
x}(w_{i})=(x_{1}(w_{i}),\ldots,x_{n/k_{n}}(w_{i}))$, which is given by

$\displaystyle x_{j}(w_{i})=\begin{cases}\sqrt{E_{n}},&\text{ if }j=w_{i}\\\
0,&\text{ otherwise}.\end{cases}$

To show that the probability of error vanishes, we use the following bound
from Lemma 6:

$\displaystyle P_{e,i}\leq\begin{cases}\exp\left\\{-\frac{\ln
M_{n}}{\dot{R}}\left(\frac{\log e}{2N_{0}}-\dot{R}\right)\right\\},&\text{ if
}0<\dot{R}\leq\frac{1}{4}\frac{\log e}{N_{0}}\\\ \exp\left\\{-\frac{\ln
M_{n}}{\dot{R}}\left(\sqrt{\frac{\log
e}{N_{0}}}-\sqrt{\dot{R}}\right)^{2}\right\\},&\text{ if
}\frac{1}{4}\frac{\log e}{N_{0}}\leq\dot{R}\leq\frac{\log
e}{N_{0}}.\end{cases}$ (33)

It follows from (33) that, if $\dot{R}<\frac{\log e}{N_{0}}$ and
$M_{n}\to\infty$ as $n\to\infty$, then $P_{e,i},i=1,\ldots,k_{n}$ tends to
zero as $n\to\infty$. Since $k_{n}=o(n)$, it follows that $M_{n}=n/k_{n}$
tends to $\infty$, as $n\to\infty$. Thus, for any $\dot{R}<\frac{\log
e}{N_{0}}$, the probability of error $P_{e,i}$ vanishes. This implies that
also $P_{e,A}^{(n)}$ vanishes as $n\to\infty$, thus proving Part 1).

####  III-D2 Proof of Part 2)

Fano’s inequality yields that

$\log M_{n}\leq 1+P_{e,i}\log M_{n}+I(W_{i};\hat{W}_{i}),\quad\mbox{for
}i=1,\ldots,k_{n}.$

Averaging over all $i$’s then gives

$\displaystyle\log M_{n}$ $\displaystyle\leq$ $\displaystyle
1+\frac{1}{k_{n}}\sum_{i=1}^{k_{n}}P_{e,i}\log M_{n}+\frac{1}{k_{n}}I({\bf
W};{\bf\hat{W}})$ (34) $\displaystyle\leq$ $\displaystyle 1+P_{e,A}^{(n)}\log
M_{n}+\frac{1}{k_{n}}I({\bf W};{\bf Y})$ $\displaystyle\leq$ $\displaystyle
1+P_{e,A}^{(n)}\log
M_{n}+\frac{n}{2k_{n}}\log\left(1+\frac{2k_{n}E_{n}}{nN_{0}}\right)$

where the first inequality follows because the messages
$W_{i},i=1,\ldots,k_{n}$ are independent and because conditioning reduces
entropy, the second inequality follows from the definition of $P_{e,A}^{(n)}$
and the data processing inequality, and the third inequality follows by upper-
bounding $I({\bf W};{\bf Y})$ by
$\frac{n}{2}\log\bigl{(}1+\frac{2k_{n}E_{n}}{nN_{0}}\bigr{)}$.

Dividing both sides of (34) by $E_{n}$, and solving the inequality for
$\dot{R^{A}}$, we obtain the upper bound

$\dot{R^{A}}\leq\frac{\frac{1}{E_{n}}+\frac{n}{2k_{n}E_{n}}\log(1+\frac{2k_{n}E_{n}}{nN_{0}})}{1-P_{e,A}^{(n)}}.$
(35)

As argued at the beginning of the proof of Part 1), we have $P_{e,A}^{(n)}\to
0$ only if $E_{n}\to\infty$. If $k_{n}=\Omega(n)$, then this implies that
$k_{n}E_{n}/n\to\infty$ as $n\to\infty$. It thus follows from (35) that, if
$k_{n}=\Omega(n)$, then $\dot{C}^{A}=0$, which is Part 2) of Theorem 3.

##  IV Capacity per Unit-Energy of Random Many-Access Channels

In this section, we consider the case where the users’ activation probability
can be strictly smaller than $1$. In Subsection IV-A, we discuss the capacity
per unit-energy of random MnACs. In particular, we present our main result in
Theorem 7, which characterizes the capacity per unit-energy in terms of
$\ell_{n}$ and $k_{n}$. Then, in Theorem 8, we analyze the largest rate per
unit-energy achievable using an orthogonal-access scheme. Finally, in Theorem
9, we briefly discuss the behaviour of the capacity per unit-energy of random
MnAC for APE. The proofs of Theorems 7–9 are presented in Subsections IV-B,
IV-C, and IV-D, respectively.

###  IV-A Capacity per Unit-Energy of Random MnAC

Before presenting our results, we first note that the case where $k_{n}$
vanishes as $n\to\infty$ is uninteresting. Indeed, this case only happens if
$\alpha_{n}\to 0$. Then, the probability that all the users are inactive,
given by $\bigl{(}(1-\alpha_{n})^{\frac{1}{\alpha_{n}}}\bigr{)}^{k_{n}}$,
tends to one since $(1-\alpha_{n})^{\frac{1}{\alpha_{n}}}\to 1/e$ and
$k_{n}\to 0$. Consequently, if each user employs a code with $M_{n}=2$ and
$E_{n}=0$ for all $n$, and if the decoder always declares that all users are
inactive, then the probability of error $P_{e}^{(n)}$ vanishes as
$n\to\infty$. This implies that $\dot{C}=\infty$.  In the following, we avoid
this trivial case and assume that $\ell_{n}$ and $\alpha_{n}$ are such that
$k_{n}=\Omega(1)$. This implies that the inverse of $\alpha_{n}$ is upper-
bounded by the order of $\ell_{n}$, i.e., $\frac{1}{\alpha_{n}}=O(\ell_{n})$.
We have the following theorem.

###### Theorem 7

Assume that $k_{n}=\Omega(1)$. Then the capacity per unit-energy of the
Gaussian random MnAC has the following behavior:

  1. 1.

If $k_{n}\log\ell_{n}=o(n)$, then $\dot{C}=\frac{\log e}{N_{0}}$.

  2. 2.

If $k_{n}\log\ell_{n}=\omega(n)$, then $\dot{C}=0$.

  3. 3.

If $k_{n}\log\ell_{n}=\Theta(n)$, then $0<\dot{C}<\frac{\log e}{N_{0}}$.

###### Proof:

See Subsection IV-B. ∎

Theorem 7 demonstrates that there is a sharp transition between orders of
growth of $k_{n}$ where interference-free communication is feasible and orders
of growth where no positive rate per unit-energy is feasible. Recall that the
same behaviour was observed for the non-random-access case ($\alpha_{n}=1$),
where the transition threshold separating these two regimes is at the order of
growth $n/\log n$, as shown in Theorem 1. For a general $\alpha_{n}$, this
transition threshold depends both on $\ell_{n}$ and $k_{n}$. However, when
$\liminf_{n\to\infty}\alpha_{n}>0$, then $k_{n}=\Theta(\ell_{n})$ and the
order of growth of $k_{n}\log\ell_{n}$ coincides with that of both $k_{n}\log
k_{n}$ and $\ell_{n}\log\ell_{n}$. It follows that, in this case, the
transition thresholds for both $k_{n}$ and $\ell_{n}$ are also at $n/\log n$,
since $k_{n}\log k_{n}=\Theta(n)$ is equivalent to $k_{n}=\Theta(n/\log n)$.

When $\alpha_{n}\to 0$, the orders of growth of $k_{n}$ and $\ell_{n}$ are
different and the transition threshold for $\ell_{n}$ is in general larger
than $n/\log n$. For example, when $\ell_{n}=n$ and
$\alpha_{n}=\frac{1}{\sqrt{n}}$, then $k_{n}\log\ell_{n}=\sqrt{n}\log n=o(n)$,
so all users can communicate without interference. Thus, random user-activity
enables interference-free communication at an order of growth above the limit
$n/\log n$. Similarly, when $\alpha_{n}\to 0$, the transition threshold for
$k_{n}$ may be smaller than $n/\log n$, even though this is only the case if
$\ell_{n}$ is superpolynomial in $n$. For example, when $\ell_{n}=2^{n}$ and
$\alpha_{n}=\frac{\sqrt{n}}{2^{n}\log n}$, then $k_{n}=\frac{\sqrt{n}}{\log
n}=o(n/\log n)$ and $k_{n}\log\ell_{n}=\frac{n^{3/2}}{\log n}=\omega(n)$, so
no positive rate per unit-energy is feasible. This implies that treating a
random MnAC with $\ell_{n}$ users as a non-random MnAC with $k_{n}$ users may
be overly-optimistic, since it suggests that interference-free communication
is feasible at orders of growth of $k_{n}$ where actually no positive rate per
unit-energy is feasible.

In the proof of Part 1) of Theorem 1, we have shown that, when $k_{n}=o(n/\log
n)$ and $\alpha_{n}=1$, an orthogonal-access scheme achieves the capacity per
unit-energy. It turns out that this is not necessarily the case anymore when
$\alpha_{n}\to 0$, as we show in the following theorem.

###### Theorem 8

Assume that $k_{n}=\Omega(1)$. The largest rate per unit-energy
$\dot{C}_{\bot}$ achievable with an orthogonal-access scheme satisfies the
following:

  1. 1)

If $\ell_{n}=o(n/\log n)$, then $\dot{C}_{\bot}=\frac{\log e}{N_{0}}$.

  2. 2)

If $\ell_{n}=\omega(n/\log n)$, then $\dot{C}_{\bot}=0$.

  3. 3)

If $\ell_{n}=\Theta(\frac{n}{\log n})$, then $0<\dot{C}_{\bot}<\frac{\log
e}{N_{0}}$.

###### Proof:

See Subsection IV-C. ∎

Observe that there is again a sharp transition between the orders of growth of
$\ell_{n}$ where interference-free communication is feasible and orders of
growth where no positive rate per unit-energy is feasible. In contrast to the
optimal transmission scheme, the transition threshold for the orthogonal-
access schemes is located at $n/\log n$, irrespective of the behavior of
$\alpha_{n}$. Thus, by using an orthogonal-access scheme, we treat the random
MnAC as if it were a non-random MnAC. This also implies that there are orders
of growth of $\ell_{n}$ and $k_{n}$ where non-orthogonal-access schemes are
necessary to achieve the capacity per unit-energy.

Next we present our results on the behaviour of capacity per unit-energy for
APE. To this end, we first note that, if $\alpha_{n}\to 0$ as $n\to\infty$,
then $\text{Pr}\\{W_{i}=0\\}\to 1$ for all $i=1,\ldots,\ell_{n}$.
Consequently, if each user employs a code with $M_{n}=2$ and $E_{n}=0$ for all
$n$, and if the decoder always declares that all users are inactive, then the
APE vanishes as $n\to\infty$. This implies that $\dot{C}^{A}=\infty$. In the
following, we avoid this trivial case and assume that $\alpha_{n}$ is bounded
away from zero. For $\alpha_{n}=1$ (non-random-access case) and APE, we showed
in Theorem 3 that if the number of users grows sublinear in $n$, then each
user can achieve the single-user capacity per unit-energy, and if the order of
growth is linear or superlinear, then the capacity per unit-energy is zero.
Perhaps not surprisingly, the same result holds in the random-access case
since, when $\alpha_{n}$ is bounded away from zero, $k_{n}$ is of the same
order as $\ell_{n}$. We have the following theorem.

###### Theorem 9

If $\liminf_{n\to\infty}\alpha_{n}>0$, then $\dot{C}^{A}$ has the following
behavior:

  1. 1.

If $\ell_{n}=o(n)$, then $\dot{C}^{A}=\frac{\log e}{N_{0}}$.

  2. 2.

If $\ell_{n}=\Omega(n)$, then $\dot{C}^{A}=0$.

###### Proof:

See Subsection IV-D. ∎

###  IV-B Proof of Theorem 7

We first give an outline of the proof. The achievability scheme to show Part
1) is a non-orthogonal-access scheme where the codewords of all users are of
length $n$ and the codebooks of different users may be different. In each
codebook, the codewords consist of two parts. The first $n^{\prime\prime}$
symbols are a signature part that is used to convey to the receiver that the
user is active. The remaining $n-n^{\prime\prime}$ symbols are used to send
the message. The decoder follows a two-step decoding process. First, it
determines which users are active, then it decodes the messages of all users
that are estimated as active. For such a two-step decoding process, we analyze
two types of errors: the detection error and the decoding error. We show that,
if $k_{n}\log\ell_{n}$ is sublinear in $n$, then the probability of detection
error and the probability of decoding error tend to zero as $n\to\infty$. The
proof of Part 2) follows along similar lines as that of Part 2) of Theorem 1.
We first show that the probability of error vanishes only if the energy
$E_{n}$ scales at least logarithmically in the total number of users, i.e.,
$E_{n}=\Omega(\log\ell_{n})$. We then show that a positive rate per unit-
energy is achievable only if the total power of the active users, given by
$k_{n}E_{n}/n$, is bounded as $n\to\infty$. The proof of Part 2) concludes by
noting that, if $k_{n}\log\ell_{n}$ is superlinear in $n$, then there is no
$E_{n}$ that can simultaneously satisfy these two conditions. Part 3) follows
by revisiting the proofs of Parts 1) and 2) for the case where
$k_{n}\log\ell_{n}=\Theta(n)$.

####  IV-B1 Proof of Part 1)

We use an achievability scheme with a decoding process consisting of two
steps. First, the receiver determines which users are active. It then fixes an
arbitrary positive integer $\xi$, based on which it decides whether it will
decode the messages of all active users, or whether it will declare an error.
Specifically, if the number of estimated active users is less than or equal to
$\xi k_{n}$, then the receiver decodes the messages of all active users. If
the number of estimated active users is greater than $\xi k_{n}$, then it
declares an error.333The threshold $\xi k_{n}$ becomes inactive when
$\alpha_{n}$ is bounded away from zero. Indeed, the number of estimated active
users is a random variable taking value in $\\{0,\ldots,\ell_{n}\\}$. When
$\alpha_{n}$ is bounded away from zero, $\ell_{n}=k_{n}/\alpha_{n}$ is bounded
by $\xi k_{n}$ for some positive integer $\xi$. Hence, in this case we can
find a threshold $\xi$ such that the receiver will never have to declare an
error. By the union bound, the total error probability of this scheme can be
upper-bounded by

$\displaystyle P(\mbox{$\cal{D}$})+\sum_{k^{\prime}_{n}=1}^{\xi
k_{n}}\text{Pr}\\{K^{\prime}_{n}=k_{n}^{\prime}\\}P_{m}(k^{\prime}_{n})+\text{Pr}\\{K^{\prime}_{n}>\xi
k_{n}\\}$

where $K^{\prime}_{n}$ is a random variable describing the number of active
users, $P(\mbox{$\cal{D}$})$ is the probability of a detection error, and
$P_{m}(k^{\prime}_{n})$ is the probability of a decoding error when the
receiver has correctly detected that there are $k^{\prime}_{n}$ active users.
In the following, we show that these probabilities vanish as $n\to\infty$ for
any fixed, positive integer $\xi$. Furthermore, by Markov’s inequality, we
have that $\text{Pr}\\{K^{\prime}_{n}>\xi k_{n}\\}\leq 1/\xi$. It thus follows
that the total probability of error vanishes as we let first $n\to\infty$ and
then $\xi\to\infty$.

To enable user detection at the receiver, out of $n$ channel uses, each user
uses the first $n^{\prime\prime}$ channel uses to send its signature and
$n^{\prime}=n-n^{\prime\prime}$ channel uses for sending the message. The
signature uses energy $E_{n}^{\prime\prime}$ out of $E_{n}$, while the energy
used for sending message is given by
$E_{n}^{\prime}=E_{n}-E_{n}^{\prime\prime}$.

Let ${\bf s}_{i}$ denote the signature of user $i$ and $\tilde{{\bf
x}}_{i}(w_{i})$ denote the codeword of length $n^{\prime}$ for sending the
message $w_{i}$, where $w_{i}=1,\ldots,M_{n}$. Then, the codeword ${\bf
x}_{i}(w_{i})$ is given by the concatenation of ${\bf s}_{i}$ and $\tilde{{\bf
x}}_{i}(w_{i})$, denoted as

$\displaystyle{\bf x}_{i}(w_{i})=({\bf s}_{i},\tilde{{\bf x}}_{i}(w_{i})).$

For a given arbitrary $0<b<1$, we let

$n^{\prime\prime}=bn,\quad$ (36) $E_{n}^{\prime\prime}=bE_{n},\quad
E_{n}=c_{n}\ln\ell_{n}$ (37)

with $c_{n}=\ln(\frac{n}{k_{n}\ln\ell_{n}})$.444In our scheme, a fraction of
the total energy must be assigned to the signature part in order to ensure
that the detection error probability vanishes as $n\to\infty$. However, this
incurs a loss in rate per unit-energy, so this fraction will be made
arbitrarily small at the end of the proof. Alternatively, one could consider a
sequence $\\{b_{n}\\}$ that satisfies $b_{n}\to 0$ and $b_{n}c_{n}\to\infty$
as $n\to\infty$. Based on the first $n^{\prime\prime}$ received symbols, the
receiver detects which users are active. We need the following lemma to show
that the detection error probability vanishes as $n\to\infty$.

###### Lemma 10

Assume that $k_{n}\log\ell_{n}=O(n)$, and let $E_{n}=c_{n}\ln\ell_{n}$, where

$c_{n}=\begin{cases}\ln\left(\frac{n}{k_{n}\log\ell_{n}}\right),&\text{ if
}k_{n}\log\ell_{n}=o(n)\\\ c^{\prime},&\text{ if
}k_{n}\log\ell_{n}=\Theta(n)\end{cases}$

for some positive constant $c^{\prime}$ that is independent of $n$. If
$c^{\prime}$ is sufficiently large, then there exist signatures ${\bf
s}_{i},i=1,\ldots,\ell_{n}$ with $n^{\prime\prime}=bn$ channel uses and energy
$E_{n}^{\prime\prime}=bE_{n}$ such that $P(\mbox{$\cal{D}$})$ vanishes as
$n\to\infty$.

###### Proof:

The proof of Lemma 10 follows along similar lines as that of [1, Th. 2].
However, there are some differences in the settings considered. Here, the goal
is to achieve user detection with minimum energy, whereas in [1] the goal is
to achieve user detection with the minimum number of channel uses.
Furthermore, the energy we assign to the signature part is proportional to the
total energy $E_{n}$, cf. (37), whereas in [1] the energy assigned to the
signature part is proportional to the number of channel uses. These
differences have the positive effect that, in our proof, the condition [1, Eq.
(19)], namely that

$\lim_{n\to\infty}\ell_{n}e^{-\delta k_{n}}=0$

for all $\delta>0$, is not necessary. For a full proof of Lemma 10, see
Appendix C.  ∎

We next use the following lemma to show that $P_{m}(k^{\prime}_{n})$ vanishes
as $n\to\infty$ uniformly in $k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n}$, where
$\mbox{$\cal{K}$}_{n}\triangleq\\{1,\ldots,\xi k_{n}\\}$.

###### Lemma 11

Let
$A_{k^{\prime}_{n}}\triangleq\frac{1}{k_{n}^{\prime}}\sum_{i=1}^{k_{n}^{\prime}}\mathbf{1}(\hat{W}_{i}\neq
W_{i})$ and
$\mbox{$\cal{A}$}_{k^{\prime}_{n}}\triangleq\\{1/k_{n}^{\prime},\ldots,1\\}$,
where $\mathbf{1}(\cdot)$ denotes the indicator function. Then, for any
arbitrary $0<\rho\leq 1$, we have

$\textnormal{Pr}\\{A_{k^{\prime}_{n}}=a\\}\leq\left(\frac{1}{\mu}\right)^{2k^{\prime}_{n}}{k_{n}^{\prime}\choose
ak_{n}^{\prime}}M_{n}^{ak_{n}^{\prime}\rho}e^{-n^{\prime}E_{0,k_{n}^{\prime}}(a,\rho,n)},\quad
a\in\mbox{$\cal{A}$}_{k^{\prime}_{n}}$ (38)

where

$\displaystyle
E_{0,k_{n}^{\prime}}(a,\rho,n)\triangleq\frac{\rho}{2}\ln\left(1+\frac{a2k_{n}^{\prime}E_{n}^{\prime}}{n^{\prime}(\rho+1)N_{0}}\right)$
(39)

and

$\displaystyle\mu$ $\displaystyle\triangleq\int\mathbf{1}(\|{\bf v}\|^{2}\leq
E_{n}^{\prime})\prod_{i=1}^{n^{\prime}}\tilde{q}(v_{i})d{\bf v}$ (40)

is a normalizing constant. In (40), $\tilde{q}(\cdot)$ denotes the probability
density function of a zero-mean Gaussian random variable with variance
$E_{n}^{\prime}/(2n^{\prime})$ and ${\bf
v}=(v_{1},v_{2},\ldots,v_{n^{\prime}})$.

###### Proof:

The upper bound in (38) without the factor $(1/\mu)^{2k^{\prime}_{n}}$ can be
obtained using random coding with i.i.d. Gaussian inputs [21, Th. 2]. However,
while i.i.d. Gaussian codebooks satisfy the energy constraint on average
(averaged over all codewords), there may be some codewords in the codebook
that violate it. We therefore need to adapt the proof of [21, Th. 2] as
follows. Let

$\displaystyle\tilde{{\bf q}}({\bf v})$
$\displaystyle=\prod_{i=1}^{n^{\prime}}\tilde{q}(v_{i}).$

For codewords $\tilde{{\bf X}}_{i},i=1,\ldots,k^{\prime}_{n}$ which are
distributed according to $\tilde{{\bf q}}(\cdot)$, the probability
$\text{Pr}(A_{k^{\prime}_{n}}=a)$ can be upper-bounded as [21, Th. 2]

$\displaystyle\text{Pr}(A_{k^{\prime}_{n}}=a)$
$\displaystyle\leq{k_{n}^{\prime}\choose
ak_{n}^{\prime}}M_{n}^{ak_{n}^{\prime}\rho}\int\tilde{{\bf q}}(\tilde{{\bf
x}}_{ak^{\prime}_{n}+1})\cdots\tilde{{\bf q}}(\tilde{{\bf
x}}_{k^{\prime}_{n}})\;G^{1+\rho}\;d\tilde{{\bf x}}_{ak^{\prime}_{n}+1}\cdots
d\tilde{{\bf x}}_{k^{\prime}_{n}}\;d\tilde{{\bf y}}$ (41)

where

$\displaystyle G$ $\displaystyle=\int\tilde{{\bf q}}(\tilde{{\bf
x}}_{1})\cdots\tilde{{\bf q}}(\tilde{{\bf
x}}_{ak^{\prime}_{n}})\left(p(\tilde{{\bf y}}\mid\tilde{{\bf
x}}_{1},\cdots,\tilde{{\bf x}}_{k^{\prime}_{n}})\right)^{1/1+\rho}d\tilde{{\bf
x}}_{1}\cdots d\tilde{{\bf x}}_{ak^{\prime}_{n}}.$

Using the fact that the channel is memoryless, the RHS of (38) without the
factor $(1/\mu)^{2k^{\prime}_{n}}$ follows from (41). The case of
$k^{\prime}_{n}=2$ was analyzed in [21, Eq. (2.33)].

Now suppose that all codewords are generated according to the distribution

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

Clearly, such codewords satisfy the energy constraint $E^{\prime}_{n}$ with
probability one. Furthermore,

$\displaystyle{\bf q}({\bf v})$ $\displaystyle\leq\frac{1}{\mu}\tilde{{\bf
q}}({\bf v}).$ (42)

By replacing $\tilde{{\bf q}}(\cdot)$ in (41) by ${\bf q}(\cdot)$, and upper-
bounding ${\bf q}(\cdot)$ by (42), we obtain that

$\displaystyle\textnormal{Pr}\\{A_{k^{\prime}_{n}}=a\\}\leq\left(\frac{1}{\mu}\right)^{(1+\rho)(ak^{\prime}_{n})}\left(\frac{1}{\mu}\right)^{k^{\prime}_{n}-ak^{\prime}_{n}}{k_{n}^{\prime}\choose
ak_{n}^{\prime}}M_{n}^{ak_{n}^{\prime}\rho}e^{-n^{\prime}E_{0,k_{n}^{\prime}}(a,\rho,n)},\quad
a\in\mbox{$\cal{A}$}_{k^{\prime}_{n}}.$ (43)

From the definition of $\mu$, we have that $0<\mu\leq 1$. Since we further
have $\rho\leq 1$ and $a\leq 1$, it follows that
$(1/\mu)^{(1+\rho)(ak^{\prime}_{n})}\leq(1/\mu)^{ak_{n}^{\prime}+k_{n}^{\prime}}$.
Using this bound in (43), we obtain (38). ∎

Next, we show that $\left(\frac{1}{\mu}\right)^{2k^{\prime}_{n}}\to 1$ as
$n\to\infty$ uniformly in $k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n}$. Let ${\bf
H}$ be a Gaussian vector which is distributed according to $\tilde{{\bf
q}}(\cdot)$. Then, by the definition of $\mu$, we have

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

so $(1/\mu)^{2k^{\prime}_{n}}\geq 1$. Let us consider ${\bf
H}_{0}\triangleq\frac{2n^{\prime}}{E_{n}^{\prime}}\|{\bf H}_{1}\|_{2}^{2}$,
which has a central chi-square distribution with $n^{\prime}$ degrees of
freedom. Then,

$\displaystyle\text{Pr}\left(\|{\bf H}_{1}\|_{2}^{2}>E_{n}^{\prime}\right)$
$\displaystyle=\text{Pr}({\bf H}_{0}>2n^{\prime}).$

So, from the Chernoff bound we obtain that

$\displaystyle\text{Pr}({\bf H}_{0}>a)$ $\displaystyle\leq\frac{E(e^{t{\bf
H}_{0}})}{e^{ta}}$ $\displaystyle=\frac{(1-2t)^{-n^{\prime}/2}}{e^{ta}}$

for every $t>0$. By choosing $a=2n^{\prime}$ and $t=\frac{1}{4}$, this yields

$\displaystyle\text{Pr}({\bf H}_{0}>2n^{\prime})$
$\displaystyle\leq\frac{\left(\frac{1}{2}\right)^{-n^{\prime}/2}}{\exp(n^{\prime}/2)}$
$\displaystyle=\exp\left[-\frac{n^{\prime}}{2}\tau\right]$

where $\tau\triangleq\left(1-\ln 2\right)$ is strictly positive. Thus,

$\displaystyle 1$
$\displaystyle\leq\left(\frac{1}{\mu}\right)^{2k^{\prime}_{n}}$
$\displaystyle\leq\left(\frac{1}{\mu}\right)^{2\xi k_{n}}$
$\displaystyle\leq\left(1-\exp\left[-\frac{n^{\prime}}{2}\tau\right]\right)^{-(2\xi
k_{n})},\quad k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n}.$ (44)

By assumption, we have that $k_{n}=o(n)$ and $n^{\prime}=\Theta(n)$. Since 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$, we obtain that the RHS of (44)
tends to one as $n\to\infty$ uniformly in
$k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n}$. So there exists a positive constant
$n_{0}$ that is independent of $k^{\prime}_{n}$ and satisfies

$\displaystyle\left(\frac{1}{\mu}\right)^{2k^{\prime}_{n}}\leq 2,\quad
k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n},n\geq n_{0}.$ (45)

The probability of error $P_{m}(k^{\prime}_{n})$ can be written as

$P_{m}(k^{\prime}_{n})=\sum\limits_{a\in\mbox{$\cal{A}$}_{k^{\prime}_{n}}}\textnormal{Pr}\\{A_{k^{\prime}_{n}}=a\\}.$
(46)

From Lemma 11 and (45), we obtain

$\displaystyle\textnormal{Pr}\\{A_{k^{\prime}_{n}}=a\\}$ $\displaystyle\leq
2{k_{n}^{\prime}\choose
ak_{n}^{\prime}}M_{n}^{ak_{n}^{\prime}\rho}\exp[-n^{\prime}E_{0,k_{n}^{\prime}}(a,\rho,n)]$
$\displaystyle\leq 2\exp\left[k_{n}^{\prime}H_{2}(a)+a\rho k_{n}^{\prime}\log
M_{n}-n^{\prime}E_{0,k_{n}^{\prime}}(a,\rho,n)\right]$
$\displaystyle=2\exp\left[-E_{n}^{\prime}f_{k^{\prime}_{n}}(a,\rho,n)\right],\quad
n\geq n_{0}$ (47)

where $H_{2}(\cdot)$ denotes the binary entropy function, and

$\displaystyle
f_{k^{\prime}_{n}}(a,\rho,n)\triangleq\frac{n^{\prime}E_{0,k_{n}^{\prime}}(a,\rho,n)}{E_{n}^{\prime}}-\frac{a\rho
k_{n}^{\prime}\log
M_{n}}{E_{n}^{\prime}}-\frac{k_{n}^{\prime}H_{2}(a)}{E_{n}^{\prime}}.$ (48)

We next show that, for sufficiently large $n$, we have

$\displaystyle\textnormal{Pr}\\{A_{k^{\prime}_{n}}=a\\}\leq
2\exp\left[-E_{n}^{\prime}f_{\xi k_{n}}(1/(\xi k_{n}),\rho,n)\right],\quad
a\in\mbox{$\cal{A}$}_{k^{\prime}_{n}},k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n}.$
(49)

To this end, we lower-bound

$\displaystyle\frac{df_{k^{\prime}_{n}}(a,\rho,n)}{da}$ $\displaystyle\geq\rho
k^{\prime}_{n}\left[\frac{1}{1+\frac{2k^{\prime}_{n}E^{\prime}_{n}}{n^{\prime}(\rho+1)N_{0}}}\frac{1}{(1+\rho)N_{0}}-\frac{\dot{R}}{(1-b)\log
e}\right]$ $\displaystyle\geq\rho\left[\frac{1}{1+\frac{2\xi
k_{n}E^{\prime}_{n}}{n^{\prime}(\rho+1)N_{0}}}\frac{1}{(1+\rho)N_{0}}-\frac{\dot{R}}{(1-b)\log
e}\right]$ (50)

by using simple algebra. This implies that for any fixed value of $\rho$ and
our choices of $E_{n}^{\prime}$ and $\dot{R}=\frac{(1-b)\log
e}{(1+\rho)N_{0}}-\delta$ (for some arbitrary $0<\delta<\frac{(1-b)\log
e}{(1+\rho)N_{0}}$),

$\liminf_{n\to\infty}\min_{k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n}}\min_{a\in\mbox{$\cal{A}$}_{k^{\prime}_{n}}}\frac{df_{k^{\prime}_{n}}(a,\rho,n)}{da}>0.$

Indeed, the RHS of (50) is independent of $a$ and $k^{\prime}_{n}$ and tends
to $\rho\delta$ as $n\to\infty$, since
$\frac{k_{n}E_{n}^{\prime}}{n^{\prime}}\to 0$ by our choice of
$E_{n}^{\prime}$ and because $k_{n}=o(n/\log n)$. Thus, for sufficiently large
$n$ and a given $\rho$, the function $a\mapsto f_{k^{\prime}_{n}}(a,\rho,n)$
is monotonically increasing on $\mbox{$\cal{A}$}_{k^{\prime}_{n}}$ for every
$k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n}$. It follows that there exists a
positive constant $n^{\prime}_{0}$ that is independent of $k^{\prime}_{n}$ and
satisfies

$\min_{a\in\mbox{$\cal{A}$}_{k^{\prime}_{n}}}f_{k^{\prime}_{n}}(a,\rho,n)=f_{k^{\prime}_{n}}(1/k^{\prime}_{n},\rho,n),\quad
k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n},n\geq n^{\prime}_{0}.$

It further follows from the definition of $f_{k^{\prime}_{n}}(a,\rho,n)$ in
(48) that, for $a=1/k^{\prime}_{n}$ and a given $\rho$,
$f_{k^{\prime}_{n}}(a,\rho,n^{\prime})$ is decreasing in $k^{\prime}_{n}$,
since in this case the first two terms on the RHS of (48) are independent of
$k^{\prime}_{n}$ and the third term is increasing in $k^{\prime}_{n}$. Hence,
we can further lower-bound

$\min_{a\in\mbox{$\cal{A}$}_{k^{\prime}_{n}}}f_{k^{\prime}_{n}}(a,\rho,n)\geq
f_{\xi k_{n}}(1/(\xi k_{n}),\rho,n),\quad
k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n},n\geq n^{\prime}_{0}.$

Next, we show that, for our choice of $E_{n}^{\prime}$ and $\dot{R}$, we have

$\liminf_{n\rightarrow\infty}f_{\xi k_{n}}(1/(\xi k_{n}),\rho,n)>0.$ (51)

Let

$\displaystyle i_{n}(\rho)$ $\displaystyle\triangleq$
$\displaystyle\frac{n^{\prime}E_{0,\xi k_{n}}(1/(\xi
k_{n}),\rho,n)}{E_{n}^{\prime}}$ (52) $\displaystyle j(\rho)$
$\displaystyle\triangleq$ $\displaystyle\frac{\rho\dot{R}}{(1-b)\log e}$ (53)
$\displaystyle h_{n}(1/(\xi k_{n}))$ $\displaystyle\triangleq$
$\displaystyle\frac{\xi k_{n}H_{2}(1/(\xi k_{n}))}{E_{n}^{\prime}}.$ (54)

Note that $\frac{h_{n}(1/(\xi k_{n}))}{j(\rho)}$ vanishes as $n\to\infty$ for
our choice of $E_{n}^{\prime}$. Consequently,

$\displaystyle\liminf_{n\rightarrow\infty}f_{\xi k_{n}}(1/(\xi k_{n}),\rho,n)$
$\displaystyle=$ $\displaystyle
j(\rho)\biggl{\\{}\liminf_{n\to\infty}\frac{i_{n}(\rho)}{j(\rho)}-1\biggr{\\}}.$

The term $j(\rho)=\rho\dot{R}/(1-b)\log e$ is bounded away from zero for our
choice of $\dot{R}$ and $\delta<\frac{(1-b)\log e}{(1+\rho)N_{0}}$.
Furthermore, since $E_{n}^{\prime}/n^{\prime}\to 0$, we get

$\lim_{n\to\infty}\frac{i_{n}(\rho)}{j(\rho)}=\frac{(1-b)\log
e}{(1+\rho)N_{0}\dot{R}}$ (55)

which is strictly larger than $1$ for our choice of $\dot{R}$. So, (51)
follows.

We conclude that there exist two positive constants $\gamma$ and
$n^{\prime\prime}_{0}\geq\max(n_{0},n_{0}^{\prime})$ that are independent of
$k^{\prime}_{n}$ and satisfy $f_{k^{\prime}_{n}}(a,\rho,n)\geq\gamma$ for
$a\in\mbox{$\cal{A}$}_{k^{\prime}_{n}}$,
$k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n}$, and $n\geq n^{\prime\prime}_{0}$.
Consequently, it follows from (47) that, for $n\geq n^{\prime\prime}_{0}$,

$\displaystyle\textnormal{Pr}\\{A_{k^{\prime}_{n}}=a\\}\leq
2e^{-E_{n}^{\prime}\gamma},\quad
a\in\mbox{$\cal{A}$}_{k^{\prime}_{n}},k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n}.$
(56)

Since $|\mbox{$\cal{A}$}_{k^{\prime}_{n}}|=k_{n}^{\prime}$, (46) and (56)
yield that

$\displaystyle P_{m}(k^{\prime}_{n})\leq
k_{n}^{\prime}2e^{-E_{n}^{\prime}\gamma},\quad
k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n},n\geq n^{\prime\prime}_{0}.$

Further upper-bounding $k^{\prime}_{n}\leq\xi k_{n}$, this implies that

$\displaystyle\sum_{k^{\prime}_{n}=1}^{\xi
k_{n}}\text{Pr}\\{K^{\prime}_{n}=k_{n}^{\prime}\\}P_{m}(k^{\prime}_{n})$
$\displaystyle\leq\xi k_{n}2e^{-E_{n}^{\prime}\gamma},\quad n\geq
n^{\prime\prime}_{0}.$ (57)

Since $E_{n}^{\prime}=(1-b)c_{n}\ln\ell_{n}$ and $k_{n}=O(\ell_{n})$, it
follows that the RHS of (57) tends to 0 as $n\to\infty$ for our choice of
$\dot{R}=\frac{(1-b)\log e}{(1+\rho)N_{0}}-\delta$. Since $\rho,\delta,$ and
$b$ are arbitrary, any rate $\dot{R}<\frac{\log e}{N_{0}}$ is thus achievable.
This proves Part 1) of Theorem 7.

####  IV-B2 Proof of Part 2)

Let $\hat{W}_{i}$ denote the receiver’s estimate of $W_{i}$, and denote by
${\bf W}$ and ${\bf\hat{W}}$ the vectors $(W_{1},\ldots,W_{\ell_{n}})$ and
$(\hat{W_{1}},\ldots,\hat{W}_{\ell_{n}})$, respectively. The messages
$W_{1},\ldots,W_{\ell_{n}}$ are independent, so it follows from (4) that

$\displaystyle H({\bf W})=\ell_{n}H({\bf
W}_{1})=\ell_{n}\left(H_{2}(\alpha_{n})+\alpha_{n}\log M_{n}\right).$

Since $H({\bf W})=H({\bf W}|{\bf Y})+I({\bf W};{\bf Y})$, we obtain

$\displaystyle\ell_{n}\left(H_{2}(\alpha_{n})+\alpha_{n}\log M_{n}\right)$
$\displaystyle=H({\bf W}|{\bf Y})+I({\bf W};{\bf Y}).$ (58)

To bound $H({\bf W})$, we use the upper bounds [1, Lemma 2]

$\displaystyle H({\bf W}|{\bf Y})\leq$ $\displaystyle\log
4+4P_{e}^{(n)}\big{(}k_{n}\log M_{n}+k_{n}+\ell_{n}H_{2}(\alpha_{n})+\log
M_{n}\big{)}$ (59)

and [1, Lemma 1]

$\displaystyle I({\bf W};{\bf
Y})\leq\frac{n}{2}\log\left(1+\frac{2k_{n}E_{n}}{nN_{0}}\right).$ (60)

Using (59) and (60) in (58), rearranging terms, and dividing by $k_{n}E_{n}$,
yields

$\displaystyle\left(1-4P_{e}^{(n)}(1+1/k_{n})\right)\dot{R}$
$\displaystyle\leq$ $\displaystyle\frac{\log
4}{k_{n}E_{n}}+\frac{H_{2}(\alpha_{n})}{\alpha_{n}E_{n}}\\!\left(4P_{e}^{(n)}-1\right)$
(61)
$\displaystyle{}+4P_{e}^{(n)}(1/E_{n}+1/k_{n})+\frac{n}{2k_{n}E_{n}}\log\left(1+\frac{2k_{n}E_{n}}{nN_{0}}\right).$

We next show that, if $k_{n}\log\ell_{n}=\omega(n)$, then the RHS of (61)
tends to a non-positive value. To this end, we need the following lemma.

###### Lemma 12

If $\dot{R}>0$ and $\ell_{n}\geq 5$, then $P_{e}^{(n)}$ vanishes as
$n\to\infty$ only if $E_{n}=\Omega(\log\ell_{n})$.

###### Proof:

See Appendix D. ∎

Part 2) of Theorem 7 follows now by contradiction. Indeed, let us assume that
$k_{n}\log\ell_{n}=\omega(n)$, $P_{e}^{(n)}\to 0$, and $\dot{R}>0$. The
assumption $k_{n}\log\ell_{n}=\omega(n)$ implies that $\ell_{n}\to\infty$ as
$n\to\infty$. Then, Lemma 12 together with the assumption that
$k_{n}=\Omega(1)$ implies that $E_{n}\to\infty$ and $k_{n}E_{n}=\omega(n)$. It
follows that the last term on the RHS of (61) tends to zero as $n\to\infty$.
Furthermore, together with the assumption that $k_{n}=\Omega(1)$, and since
$P_{e}^{(n)}$ tends to zero as $n\to\infty$, this implies that the first and
third term on the RHS of (61) vanish as $n\to\infty$. Finally,
$\frac{H_{2}(\alpha_{n})}{\alpha_{n}E_{n}}$ is a sequence of non-negative
numbers and $(4P_{e}^{(n)}-1)\to-1$ as $n\to\infty$, so the second term
converges to a non-positive value. Noting that, by the assumption
$k_{n}=\Omega(1)$, the term $(1-4P_{e}^{(n)}(1+1/k_{n}))$ tends to one as
$P_{e}^{(n)}\to 0$, we thus obtain from (61) that $\dot{R}$ tends to a non-
positive value as $n\to\infty$. This contradicts the assumption $\dot{R}>0$,
so Part 2) of Theorem 7 follows.

####  IV-B3 Proof of Part 3)

To show that $\dot{C}>0$ when $k_{n}\log\ell_{n}=\Theta(n)$, we use the same
achievability scheme and follow the same analysis as in the proof of Part 1)
of Theorem 7. That is, each user uses $n^{\prime\prime}=bn$ channel uses for
sending a signature and $n^{\prime}=n-n^{\prime\prime}$ channel uses for
sending the message. Furthermore, the decoding process consists of two steps.
First, the receiver determines which users are active. If the number of
estimated active users is less than or equal to $\xi k_{n}$, for some
arbitrary positive integer $\xi$, then the receiver decodes in a second step
the messages of all active users. If the number of estimated active users is
greater than $\xi k_{n}$, then the receiver declares an error. We set
$E_{n}=c^{\prime}\ln\ell_{n}$ for some $c^{\prime}>0$ chosen sufficiently
large so that, by Lemma 10, the probability of a detection error vanishes as
$n\to\infty$. We next show that there exists an $\dot{R}>0$ such that the
probability of a decoding error also vanishes as $n\to\infty$. To this end, we
first argue that, if $k_{n}\log\ell_{n}=\Theta(n)$, then we can find an
$\dot{R}>0$ such that $f_{k^{\prime}_{n}}(a,\rho,n)$ defined in (48) satisfies

$\displaystyle\liminf_{n\to\infty}\min_{k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n}}\min_{a\in\mbox{$\cal{A}$}_{k^{\prime}_{n}}}f_{k^{\prime}_{n}}(a,\rho,n)$
$\displaystyle>0.$ (62)

In Part 1) of Theorem 7, we proved (62) by first showing that there exists a
positive constant $n^{\prime}_{0}$ such that

$\displaystyle\min_{k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n}}\min_{a\in\mbox{$\cal{A}$}_{k^{\prime}_{n}}}f_{k^{\prime}_{n}}(a,\rho,n)\geq
f_{\xi k_{n}}(1/(\xi k_{n}),\rho,n),\quad n\geq n^{\prime}_{0}$ (63)

and then

$\displaystyle\liminf_{n\rightarrow\infty}f_{\xi k_{n}}(1/(\xi
k_{n}),\rho,n)>0.$ (64)

We follow the same steps here, too. Since, by assumption,
$k_{n}E^{\prime}_{n}=k_{n}(1-b)c^{\prime}\ln\ell_{n}=\Theta(n)$ for every
fixed $c^{\prime}>0$ and $n^{\prime}=\Theta(n)$, there exist $r_{1}>0$ and
$\tilde{n}_{0}>0$ such that

$\displaystyle\frac{k_{n}E^{\prime}_{n}}{n^{\prime}}$ $\displaystyle\leq
r_{1},\quad n\geq\tilde{n}_{0}.$

It then follows from (50) that, for every

$\displaystyle 0<\dot{R}<\frac{(1-b)\log e}{(\rho+1)N_{0}+2\xi r_{1}}$ (65)

we have that

$\displaystyle\liminf_{n\to\infty}\min_{k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n}}\min_{a\in\mbox{$\cal{A}$}_{k^{\prime}_{n}}}\frac{df_{k^{\prime}_{n}}(a,\rho,n)}{da}>0.$

Thus, for sufficiently large $n$ and a given $\rho$, the function $a\mapsto
f_{k^{\prime}_{n}}(a,\rho,n)$ is monotonically increasing on
$\mbox{$\cal{A}$}_{k^{\prime}_{n}}$ for every
$k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n}$. This gives (63).

To prove (64), we write

$f_{\xi k_{n}}(1/(\xi
k_{n}),\rho,n)=j(\rho)\left(\frac{i_{n}(\rho)}{j(\rho)}-1-\frac{h_{n}(1/(\xi
k_{n}))}{j(\rho)}\right)$ (66)

where $i_{n}(\rho)$, $j(\rho)$, and $h_{n}(1/(\xi k_{n}))$ are defined in
(52), (53), and (54), respectively. We consider two cases:

#### Case 1—$k_{n}$ is unbounded

In this case, the assumption $k_{n}\log\ell_{n}=\Theta(n)$ implies that
$\Theta(\log\ell_{n})=o(n)$. Since $E_{n}^{\prime}=\Theta(\log\ell_{n})$ for
every fixed $c^{\prime}>0$, it follows that $E^{\prime}_{n}/n^{\prime}\to 0$.
We thus get (55), namely

$\lim_{n\to\infty}\frac{i_{n}(\rho)}{j(\rho)}=\frac{(1-b)\log
e}{\dot{R}(\rho+1)N_{0}}.$

If $\dot{R}$ satisfies (65), then this is strictly larger than $1$.
Furthermore, if $k_{n}$ is unbounded, then we can make $\frac{h_{n}(1/(\xi
k_{n}))}{j(\rho)}$ arbitrarily small by choosing $c^{\prime}$ sufficiently
large. Since $j(\rho)$ is bounded away from zero for every positive $\rho$ and
$\dot{R}$, we then obtain (64) from (66).

#### Case 2—$k_{n}$ is bounded

In this case, $\Theta(\log\ell_{n})=\Theta(k_{n}\log\ell_{n})=\Theta(n)$, so
for every fixed $c^{\prime}>0$ we have $E^{\prime}_{n}=\Theta(n)$. It follows
that we can find $r_{2}>0$ and $\tilde{n}^{\prime}_{0}$ such that

$\frac{2E^{\prime}_{n}}{n^{\prime}(1+\rho)N_{0}}\leq r_{2},\quad
n\geq\tilde{n}^{\prime}_{0}.$

If we choose

$\dot{R}<\frac{\ln(1+r_{2})}{r_{2}}\frac{(1-b)\log e}{(\rho+1)N_{0}}$ (67)

then

$\displaystyle\lim_{n\to\infty}\frac{i_{n}(\rho)}{j(\rho)}>1.$ (68)

Furthermore, if $k_{n}$ is bounded, then $h_{n}(1/(\xi k_{n}))$ vanishes as
$n\to\infty$, since $\xi k_{n}$ is bounded and $E^{\prime}_{n}\to\infty$.
Recalling that $j(\rho)$ is bounded away from zero for every positive $\rho$
and $\dot{R}$, we then again obtain (64) from (66).

From (63) and (64), it follows that, for every positive $\dot{R}$ satisfying
both (65) and (67), there exist two positive constants $\gamma$ and
$n_{0}^{\prime\prime}\geq\max(n_{0},n_{0}^{\prime},\tilde{n}_{0}^{\prime})$
(where $n_{0}$ is as in (47)) that are independent of $k^{\prime}_{n}$ and
satisfy $f_{k^{\prime}_{n}}(a,\rho,n)\geq\gamma$ for
$a\in\mbox{$\cal{A}$}_{k^{\prime}_{n}}$,
$k^{\prime}_{n}\in\mbox{$\cal{K}$}_{n}$, and $n\geq n^{\prime\prime}_{0}$. It
follows from (47) that

$\displaystyle\sum_{k^{\prime}_{n}=1}^{\xi
k_{n}}\text{Pr}\\{K^{\prime}_{n}=k_{n}^{\prime}\\}P_{m}(k^{\prime}_{n})$
$\displaystyle\leq\xi k_{n}2e^{-E_{n}^{\prime}\gamma}$
$\displaystyle=2\xi\exp\left[-E_{n}^{\prime}\left(\gamma-\frac{\ln
k_{n}}{E_{n}^{\prime}}\right)\right],\quad n\geq n_{0}^{\prime\prime}.$ (69)

The term

$\displaystyle\frac{\ln k_{n}}{E^{\prime}_{n}}$ $\displaystyle=\frac{\ln
k_{n}}{(1-b)c^{\prime}\ln\ell_{n}}$

can be made arbitrarily small by choosing $c^{\prime}$ sufficiently large
since $\ln k_{n}\leq\ln\ell_{n}$. We thus have that $\frac{\ln
k_{n}}{E^{\prime}_{n}}<\gamma$ for sufficiently large $c^{\prime}$, in which
case the RHS of (69) vanishes as $n\to\infty$. Since, by Markov’s inequality,
we further have that $\text{Pr}\\{K_{n}^{\prime}>\xi k_{n}\\}\leq 1/\xi$, we
conclude that the probability of a decoding error vanishes as we let first
$n\to\infty$ and then $\xi\to\infty$. Consequently, if
$k_{n}\log\ell_{n}=\Theta(n)$, then $\dot{C}>0$.

To prove that $\dot{C}<\frac{\log e}{N_{0}}$, we first note that the
assumption $k_{n}\log\ell_{n}=\Theta(n)$ implies that $\ell_{n}\to\infty$ as
$n\to\infty$. Then, Lemma 12 shows that $P_{e}^{(n)}$ vanishes as $n\to\infty$
only if $E_{n}=\Omega(\log\ell_{n})$. This further implies that
$P_{e}^{(n)}\to 0$ only if $k_{n}E_{n}=\Omega(n)$. If $k_{n}E_{n}=\omega(n)$,
then it follows from the proof of Part 2) of Theorem 7 that $\dot{C}=0$. We
can thus assume without loss of optimality that $k_{n}E_{n}=\Theta(n)$. In
this case, by following the arguments given in the proof of Part 2) of Theorem
7, we obtain that the first and the third term on the RHS of (61) vanish as
$n\to\infty$. Furthermore, the second term tends to a non-positive value, and
the factor $(1-4P_{e}^{(n)}(1+1/k_{n}))$ tends to one. It then follows from
(61) that

$\dot{R}\leq\limsup_{n\to\infty}\frac{n}{2k_{n}E_{n}}\log\left(1+\frac{2k_{n}E_{n}}{nN_{0}}\right).$
(70)

Since $k_{n}E_{n}=\Theta(n)$, there exist $n_{0}>0$ and $l_{1}>0$ such that,
for $n\geq n_{0}$, we have $\frac{k_{n}E_{n}}{n}\geq l_{1}$. By noting that
$\frac{\log(1+x)}{x}<\log e$ for every $x>0$, we thus obtain that the RHS of
(70) is strictly less than $\frac{\log e}{N_{0}}$ for $n\geq n_{0}$. Hence
$\dot{C}<\frac{\log e}{N_{0}}$, which concludes the proof of Part 3) of
Theorem 7.

###  IV-C Proof of Theorem 8

####  IV-C1 Proof of Part 1)

To prove Part 1) of Theorem 8, we present a scheme that is similar to the one
used in the proof of Part 1) of Theorem 1. Specifically, each user is assigned
$n/\ell_{n}$ channel uses, out of which the first one is used for sending a
pilot signal and the rest are used for sending the message. Out of the
available energy $E_{n}$, $tE_{n}$ (for some arbitrary $0<t<1$ to be
determined later) is used for the pilot signal and $(1-t)E_{n}$ is used for
sending the message. Let $\tilde{{\bf x}}(w)$ denote the codeword of length
$\frac{n}{\ell_{n}}-1$ for sending message $w$. Then, user $i$ sends in his
assigned slot the codeword

$\displaystyle{\bf x}(w_{i})=\left(\sqrt{tE_{n}},\tilde{{\bf
x}}(w_{i})\right).$

The receiver first detects from the pilot signal whether user $i$ is active or
not. If the user is estimated as active, then the receiver decodes the user’s
message. Let $P_{e,i}=\textnormal{Pr}\\{\hat{W_{i}}\neq W_{i}\\}$ denote the
probability that user $i$’s message is decoded erroneously. Since all users
follow the same coding scheme, the probability of correct decoding is given by

$\displaystyle P_{c}^{(n)}=\left(1-P_{e,1}\right)^{\ell_{n}}.$ (71)

By employing the transmission scheme that was used to prove Theorem 1, we get
an upper bound on the probability of error $P_{e,1}$ as follows. Let ${\bf
Y}_{1}$ denote the received vector of length $n/\ell_{n}$ corresponding to
user 1 in the orthogonal-access scheme. From the pilot signal, which is the
first symbol $Y_{11}$ of ${\bf Y}_{1}$, the receiver guesses whether user 1 is
active or not. Specifically, the user is estimated as active if
$Y_{11}>\frac{\sqrt{tE_{n}}}{2}$ and as inactive otherwise. If the user is
declared as active, then the receiver decodes the message from the rest of
${\bf Y}_{1}$. Let $\text{Pr}(\hat{W}_{1}\neq w|W_{1}=w)$ denote the decoding
error probability when message $w,w=0,\ldots,M_{n}$ was transmitted. Then,
$P_{e,1}$ is given by

$\displaystyle P_{e,1}$ $\displaystyle=(1-\alpha_{n})\text{Pr}(\hat{W}_{1}\neq
0|W_{1}=0)+\frac{\alpha_{n}}{M_{n}}\sum_{w=1}^{M_{n}}\text{Pr}(\hat{W}_{1}\neq
w|W_{1}=w)$ $\displaystyle\leq\text{Pr}(\hat{W}_{1}\neq
0|W_{1}=0)+\frac{1}{M_{n}}\sum_{w=1}^{M_{n}}\text{Pr}(\hat{W}_{1}\neq
w|W_{1}=w).$ (72)

If $W_{1}=0$, then an error occurs if $Y_{11}>\frac{\sqrt{tE_{n}}}{2}$. So, we
have

$\displaystyle\text{Pr}(\hat{W}_{1}\neq 0|W_{1}=0)$
$\displaystyle=Q\left(\frac{\sqrt{tE_{n}}}{2}\right).$ (73)

If $w=1,\ldots,M_{n}$, then an error happens either by declaring the user as
inactive or by erroneously decoding the message. An active user is declared as
inactive if $Y_{11}<\frac{\sqrt{tE_{n}}}{2}$. So, by the union bound

$\displaystyle\frac{1}{M_{n}}\sum_{w=1}^{M_{n}}\text{Pr}(\hat{W}_{1}\neq
w|W_{1}=w)$ $\displaystyle\leq
Q\left(\frac{\sqrt{tE_{n}}}{2}\right)+{\color[rgb]{0,0,0}P_{m}}$ (74)

where $P_{m}$ is the probability that the decoder correctly declares user 1 as
active but erroneously decodes its message. It then follows from (72) and (73)
that

$\displaystyle P_{e,1}$ $\displaystyle\leq
2Q\left(\frac{\sqrt{tE_{n}}}{2}\right)+{\color[rgb]{0,0,0}P_{m}}.$ (75)

By choosing $E_{n}=c_{n}\ln n$ with $c_{n}=\ln\left(\frac{n}{\ln n}\right)$,
we can upper-bound $P_{m}$ by following the steps that led to (12). Thus, for
every $\dot{R}<\frac{\log e}{N_{0}}$, there exists a sufficiently large
$n_{0}$ and a $0<t<1$ such that

$\displaystyle P_{m}$ $\displaystyle\leq\frac{1}{n^{2}},\quad n\geq n_{0}.$
(76)

Furthermore, for the above choice of $E_{n}$, there exists a sufficiently
large $n_{0}^{\prime}$ such that

$\displaystyle 2Q\left(\frac{\sqrt{tE_{n}}}{2}\right)$
$\displaystyle\leq\frac{1}{n^{2}},\quad n\geq n^{\prime}_{0}.$ (77)

Using (76) and (77) in (75), we then obtain from (71) that

$\displaystyle P_{c}^{(n)}$
$\displaystyle\geq\left(1-\frac{2}{n^{2}}\right)^{\ell_{n}}$
$\displaystyle\geq\left(1-\frac{2}{n^{2}}\right)^{\frac{n}{\log
n}},\quad{\color[rgb]{0,0,0}n\geq\max(n_{0},n^{\prime}_{0})}$

which tends to one as $n\to\infty$. This proves Part 1) of Theorem 8.

####  IV-C2 Proof of Part 2)

Recall that we consider symmetric codes, i.e., the pair $(M_{n},E_{n})$ is the
same for all users. However, each user may be assigned different numbers of
channel uses. Let $n_{i}$ denote the number of channel uses assigned to user
$i$. For an orthogonal-access scheme, if $\ell_{n}=\omega(n/\log n)$, then
there exists at least one user, say $i=1$, such that $n_{i}=o(\log n)$. Using
that $H(W_{1}|W_{1}\neq 0)=\log M_{n}$, it follows from Fano’s inequality that

$\displaystyle\log M_{n}$ $\displaystyle\leq 1+P_{e,1}\log
M_{n}+\frac{n_{1}}{2}\log\left(1+\frac{2E_{n}}{n_{1}N_{0}}\right).$

This implies that the rate per unit-energy $\dot{R}=(\log M_{n})/E_{n}$ for
user 1 is upper-bounded by

$\displaystyle\dot{R}\leq\frac{\frac{1}{E_{n}}+\frac{n_{1}}{2E_{n}}\log\left(1+\frac{2E_{n}}{n_{1}N_{0}}\right)}{1-P_{e,1}}.$
(78)

Since $\ell_{n}=\omega(n/\log n)$, it follows from Lemma 12 that $P_{e}^{(n)}$
goes to zero only if

$\displaystyle E_{n}=\Omega(\log n).$ (79)

Furthermore, (78) implies that $\dot{R}>0$ only if $E_{n}=O(n_{1})$. Since
$n_{1}=o(\log n)$, this further implies that

$\displaystyle E_{n}=o(\log n).$ (80)

No sequence $\\{E_{n}\\}$ can satisfy both (80) and (79) simultaneously. We
thus obtain that if $\ell_{n}=\omega(n/\log n)$, then the capacity per unit-
energy is zero. This is Part 2) of Theorem 8.

####  IV-C3 Proof of Part 3)

To show that $\dot{C}_{\bot}>0$, we use the same achievability scheme given in
the proof of Part 1) of Theorem 8. That is, each user is assigned $n/\ell_{n}$
channel uses, out of which one is used for sending a pilot signal and the rest
are used for sending the message. Out of the available energy $E_{n}$,
$tE_{n}$ (for some arbitrary $0<t<1$ to be determined later) is used for the
pilot signal and $(1-t)E_{n}$ is used for sending the message. We choose
$E_{n}=c^{\prime}\log n$, where $c^{\prime}=\frac{c}{1-t}$ and $c$ is chosen
as in the proof of Part 3) of Theorem 1. The probability of error in decoding
user 1’s message is then upper-bounded by (75), namely,

$\displaystyle P_{e,1}$ $\displaystyle\leq
2Q\left(\frac{\sqrt{tE_{n}}}{2}\right)+P_{m}$ (81)

where $P_{m}$ denotes the probability that the decoder correctly declares user
1 as active but makes an error in decoding its message.

By the assumption $\ell_{n}=\Theta(n/\log n)$, there exist $n_{0}>0$ and
$0<a_{1}\leq a_{2}$ such that, for $n\geq n_{0}$, we have $a_{1}\frac{n}{\log
n}\leq\ell_{n}\leq a_{2}\frac{n}{\log n}$. Since $\alpha_{n}\leq 1$, it
follows that $k_{n}\leq a_{2}\frac{n}{\log n}$ for $n\geq n_{0}$. By following
the proof of Part 3) of Theorem 1, we then obtain that one can set

$\dot{R}=(1-t)\frac{\log
e}{2}\frac{\ln\bigl{(}1+\frac{2a_{2}c}{(1+\rho)N_{0}}\bigr{)}}{2a_{2}c}$

(for an arbitrary $0<\rho\leq 1$) and find a $c$ independent of $n$ and $t$
such that

$\displaystyle P_{m}$ $\displaystyle\leq\frac{1}{n},\quad n\geq n_{0}.$ (82)

Furthermore, for $E_{n}=c^{\prime}\log n$, the upper bound
$Q(x)\leq\frac{1}{2}e^{-x^{2}/2}$, $x\geq 0$ yields that

$2Q\left(\frac{\sqrt{tE_{n}}}{2}\right)\leq\exp\left[-\log
n\frac{t}{1-t}\frac{c}{8}\right].$

For every fixed $c$, the term $\frac{t}{1-t}\frac{c}{8}$ is a continuous,
monotonically increasing, function of $t$ that is independent of $n$ and
ranges from zero to infinity. We can therefore find a $0<t<1$ such that

$\displaystyle 2Q\left(\frac{\sqrt{tE_{n}}}{2}\right)$
$\displaystyle\leq\frac{1}{n}.$

Together with (81) and (82), this implies that

$\displaystyle P_{e,1}$ $\displaystyle\leq\frac{2}{n},\quad n\geq n_{0}.$ (83)

The above scheme has a positive rate per unit-energy. It remains to show that
this rate per unit-energy is also achievable. To this end, we note that, for
an orthogonal-access scheme, the probability of correct decoding is given by
$P_{c}^{(n)}=(1-P_{e,1})^{\ell_{n}}$. It therefore follows from (83) that

$\displaystyle P_{c}^{(n)}$
$\displaystyle\geq\left(1-\frac{2}{n}\right)^{a_{2}\frac{n}{\log n}},\quad
n\geq n_{0}.$ (84)

Since $\left(1-\frac{2}{n}\right)^{n/2}\to 1/e$ and $\frac{2a_{2}}{\log n}\to
0$ as $n\to\infty$, the RHS of (84) tends to one as $n\to\infty$. This implies
that the probability of correct decoding tends to one as $n\to\infty$, hence
the rate per unit-energy is indeed achievable. Thus, if
$\ell_{n}=\Theta(n/\log n)$, then $\dot{C}_{\bot}>0$.

We next show that $\dot{C}_{\bot}<\frac{\log e}{N_{0}}$. To this end, we first
note that, if $\ell_{n}=\Theta(\frac{n}{\log n})$, and if we employ an
orthogonal-access scheme, then there exists at least one user, say $i=1$, such
that $n_{1}=O(\log n)$. That is, there exist $n_{0}>0$ and $a>0$ such that,
for all $n\geq n_{0}$, we have $n_{1}\leq a\log n$. Furthermore, Lemma 12
implies that, if $\ell_{n}=\Theta(n/\log n)$, then $P_{e}^{(n)}$ vanishes only
if $E_{n}=\Omega(\log n)$. If $E_{n}=\omega(\log n)$, then it follows from
(78) that a positive $\dot{R}$ is achievable only if $n_{1}=\omega(\log n)$,
which contradicts the fact that $n_{1}=O(\log n)$. We can thus assume without
loss of optimality that $E_{n}=\Theta(\log n)$, i.e., there exist
$n^{\prime}_{0}>0$ and $0<l_{1}\leq l_{2}$ such that, for all $n\geq
n^{\prime}_{0}$, we have $l_{1}\log n\leq E_{n}\leq l_{2}\log n$.
Consequently, $\frac{E_{n}}{n_{1}}\geq\frac{l_{1}}{a}$ for
$n\geq\max(n_{0},n_{0}^{\prime})$. The claim that $\dot{C}_{\bot}<\frac{\log
e}{N_{0}}$ follows then directly from (78). Indeed, using that
$\frac{\log(1+x)}{x}<\log e$ for every $x>0$, we obtain that

$\displaystyle\frac{n_{1}}{2E_{n}}\log\left(1+\frac{2E_{n}}{n_{1}N_{0}}\right)$
$\displaystyle\leq\frac{a}{2l_{1}}\log\left(1+\frac{2l_{1}}{aN_{0}}\right)<\frac{\log
e}{N_{0}},\quad n\geq\max(n_{0},n_{0}^{\prime}).$ (85)

By (78), in the limit as $P_{e,1}\to 0$ and $E_{n}\to\infty$, the rate per
unit-energy is upper-bounded by (85). It thus follows that
$\dot{C}_{\bot}<\frac{\log e}{N_{0}}$, which concludes the proof of Part 3) of
Theorem 8.

###  IV-D Proof of Theorem 9

The proofs of Part 1) and Part 2) follow along the similar lines as those of
Part 1) and Part 2) of Theorem 3, respectively.

####  IV-D1 Proof of Part 1)

We first argue that $P_{e,A}^{(n)}\to 0$ only if $E_{n}\to\infty$, and that in
this case $\dot{C}^{A}\leq\frac{\log e}{N_{0}}$. Indeed, we have

$\displaystyle P_{e,A}^{(n)}$
$\displaystyle\geq\min_{i}\text{Pr}\\{\hat{W}_{i}\neq W_{i}\\}$
$\displaystyle\geq\alpha_{n}\text{Pr}(\hat{W_{i}}\neq W_{i}|W_{i}\neq
0)\;\text{ for some }i.$

Since $\liminf_{n\to\infty}\alpha_{n}>0$, this implies that $P_{e,A}^{(n)}$
vanishes only if $\text{Pr}(\hat{W_{i}}\neq W_{i}|W_{i}\neq 0)$ vanishes. We
next note that $\text{Pr}(\hat{W_{i}}\neq W_{i}|W_{i}\neq 0)$ is lower-bounded
by the error probability of the Gaussian single-user channel. By following the
arguments presented at the beginning of the proof of Theorem 3, we obtain that
$P_{e,A}^{(n)}\to 0$ only if $E_{n}\to\infty$, which also implies that
$\dot{C}^{A}\leq\frac{\log e}{N_{0}}$.

For the achievability in Part 1), we use an orthogonal-access scheme where
each user uses an orthogonal codebook of blocklength $n/\ell_{n}$. Out of
these $n/\ell_{n}$ channel uses, the first one is used for sending a pilot
signal to convey that the user is active, and the remaining channel uses are
used to send the message. Specifically, the codeword ${\bf x}_{i}(j)$ sent by
user $i$ to convey message $j$ is given by

$\displaystyle x_{ik}(j)=\begin{cases}\sqrt{tE_{n}},&\text{ if }k=1\\\
\sqrt{(1-t)E_{n}},&\text{ if }k=j+1\\\ 0,&\text{ otherwise}\end{cases}$

for some arbitrary $0<t<1$. From the pilot signal, the receiver first detects
whether the user is active or not. For this detection method, as noted before,
the probability of detection error is given by
$2Q\left(\frac{\sqrt{tE_{n}}}{2}\right)$. Since

$E_{n}=\frac{\log M_{n}}{\dot{R}}=\frac{\log(\frac{n}{\ell_{n}}-1)}{\dot{R}}$

and since $\ell_{n}$ is sublinear in $n$, $E_{n}$ tends to infinity as
$n\to\infty$. This implies that the detection error vanishes as $n\to\infty$.
If $\dot{R}<\frac{\log e}{N_{0}}$, then the probability of erroneously
decoding the message also vanishes for this code, which follows from the proof
of Theorem 3. This proves Part 1) of Theorem 9.

####  IV-D2 Proof of Part 2)

Fano’s inequality yields that $H(\hat{W}_{i}|W_{i})\leq 1+P_{e,i}\log M_{n}$.
Since $H(W_{i})=H_{2}(\alpha_{n})+\alpha_{n}\log M_{n}$, we have

$H_{2}(\alpha_{n})+\alpha_{n}\log M_{n}\leq 1+P_{e,i}\log
M_{n}+I(W_{i};\hat{W}_{i})$

for $i=1,\ldots,\ell_{n}$. Averaging over all $i$’s then gives

$\displaystyle H_{2}(\alpha_{n})+\alpha_{n}\log M_{n}$ $\displaystyle\leq
1+\frac{1}{\ell_{n}}\sum_{i=1}^{\ell_{n}}P_{e,i}\log
M_{n}+\frac{1}{\ell_{n}}I({\bf W};{\bf\hat{W}})$ $\displaystyle\leq
1+P_{e,A}^{(n)}\log M_{n}+\frac{1}{\ell_{n}}I({\bf W};{\bf Y})$
$\displaystyle\leq 1+P_{e,A}^{(n)}\log
M_{n}+\frac{n}{2\ell_{n}}\log\left(1+\frac{2k_{n}E_{n}}{nN_{0}}\right).$ (86)

Here, the first inequality follows because the messages
$W_{i},i=1,\ldots,\ell_{n}$ are independent and because conditioning reduces
entropy, the second inequality follows from the definition of $P_{e,A}^{(n)}$
and the data processing inequality, and the third inequality follows from
(60).

Dividing both sides of (86) by $E_{n}$, and rearranging terms, yields the
following upper-bound on the rate per unit-energy $\dot{R}^{A}$:

$\dot{R^{A}}\leq\frac{\frac{1-H_{2}(\alpha_{n})}{E_{n}}+\frac{n}{2\ell_{n}E_{n}}\log(1+\frac{2k_{n}E_{n}}{nN_{0}})}{\alpha_{n}-P_{e,A}^{(n)}}.$
(87)

As noted before, $P_{e,A}^{(n)}\to 0$ only if $E_{n}\to\infty$. It follows
that $\frac{1-H_{2}(\alpha_{n})}{E_{n}}$ vanishes as $n\to\infty$.
Furthermore, together with the assumptions $\ell_{n}=\Omega(n)$ and
$\liminf_{n\to\infty}\alpha_{n}>0$, $E_{n}\to\infty$ implies that
$k_{n}E_{n}/n=\alpha_{n}\ell_{n}E_{n}/n$ tends to infinity as $n\to\infty$.
This in turn implies that

$\frac{n}{2\ell_{n}E_{n}}\log\left(1+\frac{2k_{n}E_{n}}{nN_{0}}\right)=\frac{n\alpha_{n}}{2k_{n}E_{n}}\log\left(1+\frac{2k_{n}E_{n}}{nN_{0}}\right)$

vanishes as $n\to\infty$. It thus follows from (87) that $\dot{R}^{A}$
vanishes as $n\to\infty$, thereby proving Part 2) of Theorem 9.

##  V Comparison With the Polyanskiy Setting of Many-Access Channels

In this paper, we basically follow the setting of the MnAC introduced Chen _et
al._ [1]. That is, we assume that each user has a different codebook and
require the probability of error to vanish as $n\to\infty$. By Lemma 4, the
latter requirement can only be satisfied if $E_{n}\to\infty$ as $n\to\infty$,
which for a fixed rate per unit-energy implies that $M_{n}\to\infty$. In other
words, the payload of the user tends to infinity as $n\to\infty$.

In an attempt to introduce a notion of a random-access code that is appealing
to the different communities interested in the multiple-access problem,
Polyanskiy [4] proposed a different setting, where

  1. 1.

all encoders use the same codebook;

  2. 2.

the decoding is up to permutations of messages;

  3. 3.

the probability of error is not required to vanish as $n\to\infty$.

He further introduced the per-user probability of error

$\frac{1}{k_{n}}\sum_{i=1}^{k_{n}}\text{Pr}\bigl{(}\\{\hat{W}_{i}\neq
W_{i}\\}\cup\\{\text{$W_{j}=W_{i}$ for some $j\neq i$}\\}\bigr{)}.$ (88)

As argued in [4], the probability that two messages are equal is typically
small, in which case the event

$\\{\text{$W_{j}=W_{i}$ for some $j\neq i$}\\}$

can be ignored and (88) is essentially equivalent to the APE defined in (7).

The setting where all encoders use the same codebook and decoding is up to
permutations of messages is sometimes also referred to as _unsourced multiple-
access_. Unsourced multiple-access has two benefits: it may be more practical
in scenarios with a large number of users, and many popular schemes, such as
slotted ALOHA and coded slotted ALOHA, become achievability bounds and can be
compared against each other and against information-theoretic benchmarks. By
not requiring the probability of error to vanish as $n\to\infty$, it is not
necessary to let $M_{n}\to\infty$ with the blocklength. So, in the above
setting, the payload can be of fixed size, which may be appealing from a
practical perspective.

In [4], Polyanskiy presented a random-coding achievability bound and used it
as a benchmark for the performance of practical schemes, including coded
slotted ALOHA, treating intereference as noise, and time-division multiple-
access. He further studied the minimum energy-per-bit that can be achieved by
an $(n,M_{n},E_{n},\epsilon)$ code for APE when each user has a different
codebook, the payload $M_{n}$ and the probability of error $\epsilon$ are
fixed, and the number of users grows linearly with the blocklength, i.e.,
$k_{n}=\mu n$ for some $0<\mu\ll 1$. The bounds obtained in [4] and in the
follow-up work [13] suggest that, whenever $\mu$ is below some critical value,
the minimum energy-per-bit is independent of $\mu$. In other words, there
exists a critical density of users below which interference-free communication
is feasible. This is consistent with the conclusions we drew from Theorems 1
and 7 for JPE, and from Theorems 3 and 9 for APE. However, these theorems also
demonstrate that there is an important difference: According to Theorems 1 and
3, a linear growth of the number of users in $n$ implies that the capacity per
unit-energy $\dot{C}$ is zero, irrespective of the value of $\mu$, and
irrespective of whether JPE or APE is considered. Since rate per unit-energy
is the reciprocal of energy-per-bit, this implies that the minimum energy-per-
bit is infinite. In contrast, the bounds presented in [4] and [13] show that
the minimum energy-per-bit for a fixed probability of error $\epsilon$ is
finite or, equivalently, that the $\epsilon$-capacity per unit-energy
$\dot{C}_{\epsilon}$ is strictly positive. Thus, the capacity per unit-energy
is strictly smaller than the $\epsilon$-capacity per unit-energy, which
implies that, for APE, the strong converse does not hold.

In order to explore this point further, we discuss in the rest of this section
how the largest achievable rate per unit-energy changes if we allow for a non-
vanishing error probability. For the sake of simplicity, we shall assume
throughout the section that users are active with probability one, i.e.,
$\alpha_{n}=1$.

We first argue that, when the number of users is bounded in $n$, then a simple
orthogonal-access scheme achieves an $\epsilon$-capacity per unit-energy that
can even be larger than the single-user capacity per unit-energy $\frac{\log
e}{N_{0}}$, irrespective of whether JPE or APE is assumed. We shall do so by
means of the following example.

###### Example 1

Consider a $k$-user Gaussian MAC with normalized noise variance $N_{0}/2=1$
and where the number of users is independent of $n$. Suppose that each user
has two messages to transmit using energy $E_{n}=1$. Consider an orthogonal-
access scheme where each user gets one channel use and remains silent in the
remaining channel uses. In this channel use, each user transmits either $+1$
or $-1$ to convey its message. Since the access scheme is orthogonal, the
receiver can perform independent decoding for each user, which yields
$\text{Pr}(\hat{W}_{i}\neq W_{i})=Q(1)$. Consequently, we can achieve the rate
per unit-energy $\frac{\log M_{n}}{E_{n}}=1$ at APE $P_{e,A}^{(n)}=Q(1)$ and
at JPE $P_{e}^{(n)}=1-(1-Q(1))^{k}$. Since $\frac{\log e}{N_{0}}=\frac{\log
e}{2}\approx 0.7213$, we conclude that, if $\epsilon\geq Q(1)$ (for APE) or
$\epsilon\geq 1-(1-Q(1))^{k}$ (for JPE), then the $\epsilon$-capacity per
unit-energy exceeds the single-user capacity per unit-energy.

###### Remark 4

A crucial ingredient in the above scheme is that the energy $E_{n}$ is bounded
in $n$. Indeed, it follows from [20, Th. 3] that, if $E_{n}\to\infty$ as
$n\to\infty$, as required, e.g., in [14, Def. 2] (See Remark 1), then the
$\epsilon$-capacity per unit-energy of the Gaussian single-user channel is
equal to $\frac{\log e}{N_{0}}$, irrespective of $0<\epsilon<1$. The genie
argument provided at the beginning of the proof of Theorem 3 then yields that
the same is true for the Gaussian MnAC.

In the following two subsections, we discuss the $\epsilon$-capacity per unit-
energy when the number of users $k_{n}$ tends to infinity as $n$ tends to
infinity. Specifically, in Subsection V-A we demonstrate that, irrespective of
the order of growth of $k_{n}$, the $\epsilon$-capacity per unit-energy for
JPE is the same as $\dot{C}$, i.e., the strong converse holds in this case. In
Subsection V-B, we consider the case where $k_{n}=\mu n$ and show by means of
a simple example that, for some fixed payload $M_{n}$ and sufficiently small
$\mu$, the $\epsilon$-capacity per unit-energy for APE is indeed independent
of $\mu$, as suggested by the bounds in [4] and [13].

###  V-A Non-Vanishing JPE

The following theorem characterizes the behavior of the $\epsilon$-capacity
per unit-energy for JPE and an unbounded number of users.

###### Theorem 13

The $\epsilon$-capacity per unit-energy $\dot{C}_{\epsilon}$ of the non-random
MnAC with JPE has the following behavior:

  1. 1.

If $k_{n}=\omega(1)$ and $k_{n}=o(n/\log n)$, then
$\dot{C}_{\epsilon}=\frac{\log e}{N_{0}}$ for every $0<\epsilon<1$.

  2. 2.

If $k_{n}=\omega(n/\log n)$, then $\dot{C}_{\epsilon}=0$ for every
$0<\epsilon<1$.

###### Proof:

We first prove Part 1). It follows from (187) in the proof of Lemma 12 that,
for $M_{n}\geq 2$ and $k_{n}\geq 5$,

$P_{e}^{(n)}\geq 1-\frac{256E_{n}/N_{0}+\log 2}{\log k_{n}}.$ (89)

This implies that $P_{e}^{(n)}$ tends to one unless $E_{n}=\Omega(\log
k_{n})$. Since, by the theorem’s assumption, we have $k_{n}=\omega(1)$, it
follows that $E_{n}\to\infty$ is necessary to achieve a JPE strictly smaller
than one. As argued in Remark 4 (see also Remark 1), if $E_{n}\to\infty$ as
$n\to\infty$, then the $\epsilon$-capacity per unit-energy of the Gaussian
MnAC cannot exceed the single-user capacity per unit-energy $\frac{\log
e}{N_{0}}$. Furthermore, by Theorem 3, if $k_{n}=o(n/\log n)$, then any rate
per unit-energy satisfying $\dot{R}<\frac{\log e}{N_{0}}$ is achievable, hence
it is also $\epsilon$-achievable. We thus conclude that, if $k_{n}=\omega(1)$
and $k_{n}=o(n/\log n)$, then $\dot{C}_{\epsilon}=\frac{\log e}{N_{0}}$ for
every $0<\epsilon<1$.

To prove Part 2), we use the upper bound (13), namely

$\dot{R}\leq\frac{\frac{1}{k_{n}E_{n}}+\frac{n}{2k_{n}E_{n}}\log(1+\frac{2k_{n}E_{n}}{nN_{0}})}{1-P_{e}^{(n)}}.$
(90)

By (89), $P_{e}^{(n)}$ tends to one unless $E_{n}=\Omega(\log k_{n})$. For
$k_{n}=\omega(n/\log n)$, this implies that $k_{n}E_{n}/n\to\infty$ as
$n\to\infty$, so the RHS of (90) vanishes as $n$ tends to infinity. We thus
conclude that, if $k_{n}=\omega(n/\log n)$, then $\dot{C}_{\epsilon}=0$ for
every $0<\epsilon<1$. ∎

Theorems 1 and 13 demonstrate that $\dot{C}_{\epsilon}=\dot{C}$ for every
$0<\epsilon<1$, provided that the number of users is unbounded in $n$.
Consequently, the strong converse holds for JPE. As argued in the proof of
Theorem 13, this result hinges on the fact that the probability of error can
be strictly smaller than one only if the energy tends to infinity as
$n\to\infty$. As explained in Remarks 1 and 4, in this case the capacity per
unit-energy cannot exceed $\frac{\log e}{N_{0}}$. As we shall see in the next
subsection, an APE strictly smaller than one can also be achieved at a
positive rate per unit-energy if the energy is bounded in $n$. This allows for
a positive $\epsilon$-capacity per unit-energy for APE when $k_{n}$ grows
linearly in $n$.

###  V-B Non-Vanishing APE

In this subsection, we focus on the case where $k_{n}=\mu n$ and show that,
when the payload of each user is $1$ bit and $\mu\leq 1$, the
$\epsilon$-capacity per unit-energy for APE is indeed independent of $\mu$.
This supports the conjecture in [13] that there exists a critical density of
users below which interference-free communication is feasible.

Let $\mbox{$\cal{E}$}^{*}(M,\mu,\epsilon)$ denote the minimum energy-per-bit
required to send $M$ messages at an APE not exceeding $\epsilon$ when the
number of users is given by $k_{n}=\mu n$. While it is difficult to obtain the
exact closed form expression of $\mbox{$\cal{E}$}^{*}(M,\mu,\epsilon)$ for
general $M,\mu$ and $\epsilon$, tight upper and lower bounds of
$\mbox{$\cal{E}$}^{*}(M,\mu,\epsilon)$ were derived in [4, 13]. Furthermore,
as we shall argue next, if the payload of each user is 1 bit and $\mu\leq 1$,
then $\mbox{$\cal{E}$}^{*}(M,\mu,\epsilon)$ can be evaluated in closed form.

For simplicity, assume that $N_{0}/2=1$. Then,

$\mbox{$\cal{E}$}^{*}(2,\mu,\epsilon)=\left(\max\\{0,Q^{-1}(\epsilon)\\}\right)^{2},\quad
0<\mu\leq 1$ (91)

where $Q^{-1}$ denotes the inverse of $Q$ function. Indeed, that
$\mbox{$\cal{E}$}^{*}(2,\mu,\epsilon)\geq(\max\\{0,Q^{-1}(\epsilon)\\})^{2}$
follows from (32). Furthermore, if $\mu\leq 1$, then we can assign each user
one channel use. Following the orthogonal-access scheme presented in Example
1, but where each user transmits either $+\sqrt{E}$ or $-\sqrt{E}$ (instead of
$+1$ or $-1$) with energy $E=(\max\\{0,Q^{-1}(\epsilon)\\})^{2}$, we can
achieve $P_{e,A}^{(n)}\leq\epsilon$. Thus, with energy (91) we can send $2$
messages at an APE not exceeding $\epsilon$.

Observe that the RHS of (91) does not depend on $\mu$ and agrees with the
minimum energy-per-bit required to send one bit over the Gaussian single-user
channel with error probability $\epsilon$. Thus, when $\mu\leq 1$, we can send
one bit free of interference. Further observe that (91) is finite for every
positive $\epsilon$. Consequently, the $\epsilon$-capacity per unit-energy,
which is given by the reciprocal of (91), is strictly positive. This is in
contrast to the capacity per unit-energy which, by Part 2) of Theorem 3, is
zero. Thus, the strong converse does not hold for APE when the number of users
grows linearly in $n$.

As mentioned in the previous subsection, to achieve a positive rate per unit-
energy, it is crucial that the energy $E_{n}$ and payload $\log M_{n}$ are
bounded in $n$. Indeed, for $k_{n}=\mu n$, the RHS of (35) vanishes as $E_{n}$
tends to infinity, in which case no positive rate per unit-energy is
$\epsilon$-achievable. Moreover, for $k_{n}=\mu n$ and a bounded $E_{n}$, (34)
implies that the payload $\log M_{n}$ is bounded, too. We conclude that the
arguably most common assumptions in the literature on MnACs—linear growth of
the number of users, a non-vanishing APE, and a fixed payload—are the only set
of assumptions under which a positive rate per unit-energy is achievable,
unless we consider sublinear growths of $k_{n}$.

##  VI Conclusion

In this work, we analyzed scaling laws of a Gaussian random MnAC where the
total number of users as well as the average number of active users may grow
with the blocklength. In particular, we characterized the behaviour of the
capacity per unit-energy as a function of the order of growth of the number of
users for two notions of probability of error: the classical JPE and the APE
proposed by Polyanskiy in [4]. For both cases, we demonstrated that there is a
sharp transition between orders of growth where all users can achieve the
single-user capacity per unit-energy and orders of growth where no positive
rate per unit-energy is feasible. When all users are active with probability
one, we showed that the transition threshold separating the two regimes is at
the order of growth $n/\log n$ for JPE, and at the order of growth $n$ for
APE. While the qualitative behaviour of the capacity per unit-energy remains
the same in both cases, there are some interesting differences between JPE and
APE in some other aspects. For example, we showed that an orthogonal-access
scheme together with orthogonal codebooks is optimal for APE, but it is
suboptimal for JPE. Furthermore, when the number of users is unbounded in $n$,
the strong converse holds for JPE, but it does not hold for APE. For MnACs
where the number of users grows linearly in $n$ and APE—the most common
assumptions in the literature—our results imply that a positive rate per unit-
energy is infeasible if we require the APE to vanish asymptotically. In
contrast, due to the absence of a strong converse, a positive $\epsilon$-rate
per unit-energy is feasible. To this end, however, it is necessary that the
energy $E_{n}$ and the payload $\log M_{n}$ are bounded in $n$.

For the case of random user activity and JPE, we characterized the behaviour
of the capacity per unit-energy in terms of the total number of users
$\ell_{n}$ and the average number of active users $k_{n}$. We showed that, if
$k_{n}\log\ell_{n}$ is sublinear in $n$, then all users can achieve the
single-user capacity per unit-energy, and if $k_{n}\log\ell_{n}$ is
superlinear in $n$, then the capacity per unit-energy is zero. Consequently,
there is again a sharp transition between orders of growth where interference-
free communication is feasible and orders of growth where no positive rate per
unit-energy is feasible, and the transition threshold separating these two
regimes depends in this case on the orders of growth of both $\ell_{n}$ and
$k_{n}$. _Inter alia_ , this result recovers our characterization of the non-
random-access case ($\alpha_{n}=1$), since $k_{n}\log k_{n}=\Theta(n)$ is
equivalent to $k_{n}=\Theta(n/\log n)$. Our result further implies that the
orders of growth of $\ell_{n}$ for which interference-free communication is
feasible are in general larger than $n/\log n$, and the orders of growth of
$k_{n}$ for which interference-free communication is feasible may be smaller
than $n/\log n$. This suggests that treating a random MnAC with total number
of users $\ell_{n}$ and average number of users $k_{n}$ as a non-random MnAC
with $k_{n}$ users may be overly-optimistic.

We finally showed that, under JPE, orthogonal-access schemes achieve the
single-user capacity per unit-energy when the order of growth of $\ell_{n}$ is
strictly below $n/\log n$, and they cannot achieve a positive rate per unit-
energy when the order of growth of $\ell_{n}$ is strictly above $n/\log n$,
irrespective of the behaviour of $k_{n}$. Intuitively, by using an orthogonal-
access scheme, we treat the random MnAC as if it were non-random. We conclude
that orthogonal-access schemes are optimal when all users are active with
probability one. However, for general $\alpha_{n}$, non-orthogonal-access
schemes are necessary to achieve the capacity per unit-energy.

##  Appendix A Proof of Lemma 4

The probability of error of the Gaussian MnAC cannot be smaller than that of
the Gaussian point-to-point channel. Indeed, suppose a genie informs the
receiver about all transmitted codewords except that of user $i$. Then the
receiver can subtract the known codewords from the received vector, resulting
in a point-to-point Gaussian channel. Since access to additional information
does not increase the probability of error, the claim follows.

We next note that, for a Gaussian point-to-point channel, any
$(n,M_{n},E_{n},\epsilon)$-code satisfies [20, Th. 2]

$\displaystyle\frac{1}{M_{n}}\geq
Q\left(\sqrt{\frac{2E_{n}}{N_{0}}}+Q^{-1}(1-\epsilon)\right).$ (92)

Solving (92) for $\epsilon$ yields

$\displaystyle\epsilon$ $\displaystyle\geq
1-Q\left(Q^{-1}\left(\frac{1}{M_{n}}\right)-\sqrt{\frac{2E_{n}}{N_{0}}}\right).$

It follows that the probability of error tends to zero as $n\to\infty$ only if
$Q^{-1}\left(1/M_{n}\right)-\sqrt{\frac{2E_{n}}{N_{0}}}\rightarrow-\infty$.
Since $Q^{-1}\left(1/M_{n}\right)\geq 0$ for $M_{n}\geq 2$, this in turn is
only the case if $E_{n}\rightarrow\infty$. This proves Lemma 4.

##  Appendix B Proof of Lemma 6

The upper bounds on the probability of error presented in (22) and (23) are
proved in Appendix B-A. The lower bounds are proved in Appendix B-B.

###  B-A Upper bounds

An upper bound on the probability of error for $M$ orthogonal codewords of
maximum energy $E$ can be found in [16, Sec. 2.5]:

$\displaystyle P_{e,1}$
$\displaystyle\leq(M-1)^{\rho}\exp\left[-\frac{E}{N_{0}}\left(\frac{\rho}{\rho+1}\right)\right]$
$\displaystyle\leq\exp\left[-\frac{E}{N_{0}}\left(\frac{\rho}{\rho+1}\right)+\rho\ln
M\right],\quad\mbox{for }0\leq\rho\leq 1.$ (93)

For the rate per unit-energy $\dot{R}=\frac{\log M}{E}$, it follows from (93)
that

$\displaystyle P_{e,1}$
$\displaystyle\leq\exp[-EE_{0}(\rho,\dot{R})],\quad\mbox{for }0\leq\rho\leq 1$
(94)

where

$\displaystyle E_{0}(\rho,\dot{R})$
$\displaystyle\triangleq\left(\frac{1}{N_{0}}\frac{\rho}{\rho+1}-\frac{\rho\dot{R}}{\log
e}\right).$ (95)

When $0<\dot{R}\leq\frac{1}{4}\frac{\log e}{N_{0}}$, the maximum of
$E_{0}(\rho,\dot{R})$ over all $0\leq\rho\leq 1$ is achieved for $\rho=1$.
When $\frac{1}{4}\frac{\log e}{N_{0}}\leq\dot{R}\leq\frac{\log e}{N_{0}}$, the
maximum of $E_{0}(\rho,\dot{R})$ is achieved for $\rho=\sqrt{\frac{\log
e}{N_{0}}\frac{1}{\dot{R}}}-1\in[0,1]$. So we have

$\displaystyle\max_{0\leq\rho\leq
1}E_{0}(\rho,\dot{R})=\begin{cases}\frac{1}{2N_{0}}-\frac{\dot{R}}{\log
e},&0<\dot{R}\leq\frac{1}{4}\frac{\log e}{N_{0}}\\\
\left(\sqrt{\frac{1}{N_{0}}}-\sqrt{\frac{\dot{R}}{\log
e}}\right)^{2},&\frac{1}{4}\frac{\log e}{N_{0}}\leq\dot{R}\leq\frac{\log
e}{N_{0}}.\end{cases}$ (96)

Since $E=\frac{\log M}{\dot{R}}$, we obtain from (94) and (96) that

$\displaystyle P_{e,1}\leq$ $\displaystyle\exp\left[-\frac{\ln
M}{\dot{R}}\left(\frac{\log e}{2N_{0}}-\dot{R}\right)\right],\quad\text{if
}0<\dot{R}\leq\frac{1}{4}\frac{\log e}{N_{0}}$

and

$\displaystyle P_{e,1}\leq$ $\displaystyle\exp\left[-\frac{\ln
M}{\dot{R}}\left(\sqrt{\frac{\log
e}{N_{0}}}-\sqrt{\dot{R}}\right)^{2}\right],\quad\text{if
}\frac{1}{4}\frac{\log e}{N_{0}}\leq\dot{R}\leq\frac{\log e}{N_{0}}.$

This proves the upper bounds on the probability of error in (22) and (23).

###  B-B Lower bounds

To prove the lower bounds on the probability of error presented in (22) and
(23), we first argue that, for an orthogonal codebook, the optimal probability
of error is achieved by codewords of equal energy. Then, for any given
$\dot{R}$ and an orthogonal codebook where all codewords have equal energy, we
derive the lower bound in (23), which is optimal at high rates. We further
obtain an improved lower bound on the probability of error for low rates.
Finally, the lower bound in (22) follows by showing that a combination of the
two lower bounds yields a lower bound, too.

####  B-B1 Equal-energy codewords are optimal

We shall argue that, for an orthogonal code with energy upper-bounded by
$E_{n}$, there is no loss in optimality in assuming that all codewords have
energy $E_{n}$. To this end, we first note that, without loss of generality,
we can restrict ourselves to codewords of the form

$\displaystyle{\bf x}_{m}=(0,\ldots,\sqrt{E_{{\bf x}_{m}}},\ldots,0),\quad
m=1,\ldots,M$ (97)

where $E_{{\bf x}_{m}}\leq E_{n}$ denotes the energy of codeword ${\bf
x}_{m}$. Indeed, any orthogonal codebook can be multiplied by an orthogonal
matrix to obtain this form. Since the additive Gaussian noise ${\bf Z}$ is
zero mean and has a diagonal covariance matrix, this does not change the
probability of error.

To argue that equal energy codewords are optimal, let us consider a code
$\cal{C}$ for which some codewords have energy strictly less than $E_{n}$.
From $\cal{C}$, we can construct a new code $\mbox{$\cal{C}$}^{\prime}$ by
multiplying each codeword ${\bf x}_{m}$ by $\sqrt{E_{n}/E_{{\bf x}_{m}}}$.
Clearly, each codeword in $\mbox{$\cal{C}$}^{\prime}$ has energy $E_{n}$. Let
${\bf Y}$ and ${\bf Y}^{\prime}$ denote the channel outputs when we transmit
codewords from $\cal{C}$ and $\mbox{$\cal{C}$}^{\prime}$, respectively, and
let $P_{e}(\mbox{$\cal{C}$})$ and $P_{e}(\mbox{$\cal{C}$}^{\prime})$ denote
the corresponding minimum probabilities of error. By multiplying each
dimension of the channel output ${\bf Y}^{\prime}$ by $\sqrt{E_{{\bf
x}_{m}}/E_{n}}$ and adding Gaussian noise of zero mean and variance
$E_{n}/E_{{\bf x}_{m}}$, we can construct a new channel output $\tilde{{\bf
Y}}$ that has the same distribution as ${\bf Y}$. Consequently,
$\mbox{$\cal{C}$}^{\prime}$ can achieve the same probability of error as
$\cal{C}$ by applying the decoding rule of $\cal{C}$ to $\tilde{{\bf Y}}$. It
follows that $P_{e}(\mbox{$\cal{C}$}^{\prime})\leq P_{e}(\mbox{$\cal{C}$})$.
We conclude that, in order to find lower bounds on the probability of error,
it suffices to consider codes whose codewords all have energy $E_{n}$.

####  B-B2 High-rate lower bound

We next derive lower bound (23), which applies to high rates per unit-energy.
To obtain this bound, we follow the analysis given in [15] (see also [16, Sec.
3.6.1]). To this end, we shall first derive a lower bound on the maximum
probability of error

$\displaystyle P_{e_{\max}}$ $\displaystyle\triangleq\max_{m}P_{e_{m}}$

where $P_{e_{m}}$ denotes the probability of error in decoding message $m$. In
a second step, we derive from this bound a lower bound on the average
probability of error $P_{e,1}$ by means of expurgation. For $P_{e_{\max}}$, it
was shown that at least one of the following two inequalities is always
satisfied [16, Sec. 3.6.1]:

$\displaystyle 1/M$
$\displaystyle\geq\frac{1}{4}\exp\left[\mu(s)-s\mu^{\prime}(s)-s\sqrt{2\mu^{\prime\prime}(s)}\right]$
(98) $\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]$
(99)

for all $0\leq s\leq 1$, where

$\displaystyle\mu(s)$ $\displaystyle=-\frac{E}{N_{0}}s(1-s),$ (100)
$\displaystyle\mu^{\prime}(s)$ $\displaystyle=-\frac{E}{N_{0}}(1-2s),$ (101)
$\displaystyle\mu^{\prime\prime}(s)$ $\displaystyle=\frac{2E}{N_{0}}.$ (102)

By substituting these values in (98), we obtain

$\displaystyle\ln
M\leq\frac{E}{N_{0}}\left[s^{2}+\frac{2s}{\sqrt{E/N_{0}}}+\frac{\ln
4}{E/N_{0}}\right].$

Using that $0\leq s\leq 1$ and that $E=\frac{\log M}{\dot{R}}$, this yields

$\displaystyle\dot{R}$ $\displaystyle\leq\frac{\log
e}{N_{0}}\left[s^{2}+\frac{2}{\sqrt{E/N_{0}}}+\frac{\ln 4}{E/N_{0}}\right].$
(103)

Similarly, substituting (100)-(102) in (99) yields

$\displaystyle P_{e_{\max}}$
$\displaystyle\geq\exp\left[-\frac{E}{N_{0}}(1-s)^{2}-2(1-s)\sqrt{\frac{E}{N_{0}}}-\ln
4\right]$
$\displaystyle\geq\exp\left[-\frac{E}{N_{0}}\left((1-s)^{2}+\frac{2}{\sqrt{E/N_{0}}}+\frac{\ln
4}{E/N_{0}}\right)\right].$ (104)

For a given $E$, let $\delta_{E}$ be defined as $\delta_{E}\triangleq
2\left(\frac{2}{\sqrt{E/N_{0}}}+\frac{\ln 4}{E/N_{0}}\right)$, and let
$s_{E}\triangleq\sqrt{\dot{R}\frac{N_{0}}{\log e}-\delta_{E}}$. For $s=s_{E}$,
the bound (103), and hence also (98), is violated which implies that (104)
must be satisfied for $s=s_{E}$. By substituting $s=s_{E}$ in (104), we obtain

$\displaystyle
P_{e_{\max}}\geq\exp\left[-E\left(\left(\sqrt{\frac{1}{N_{0}}}-\sqrt{\frac{\dot{R}}{\log