We study a $K$-user coded-caching broadcast problem in a joint source-channel coding framework. The transmitter observes a database of files that are being generated at a certain rate per channel use, and each user has a cache, which can store a fixed fraction of the generated symbols. In the delivery phase, the transmitter broadcasts a message so that the users can decode their desired files using the received signal and their cache content. The communication between the transmitter and the receivers happens over a (deterministic) time-varying erasure broadcast channel, and the channel state information is only available to the users. We characterize the maximum achievable source rate for the $2$-user and the degraded $K$-user problems. We provide an upper bound for any caching strategy's achievable source rates. Finally, we present a linear programming formulation to show that the upper bound is not a sharp characterization. Closing the gap between the achievable rate and the optimum rate remains open.

§ INTRODUCTION

The number of active users of video streaming applications such as Netflix, YouTube, HBO, etc., is growing rapidly. Coded caching is a promising strategy to overcome this rapidly growing traffic load of networks during their peak traffic time by duplicating parts of the content in the caches distributed across the network. A caching system operates in two phases: (i) a placement (pre-fetching) phase, where each user has access to the database of the transmitter and stores some packets from the database during the off-load time, and (ii) a delivery (fetching) phase, during which each user demands a file from the database, and the transmitter broadcasts a signal over a (noisy) channel to all the users (receivers), such that each user is able to decode his desired file from his cache content and his received signal. Moreover, in this phase, the network is congested, and the transmitter exploits the content of users to serve their requested files.

In practice, assuming a perfect broadcast channel fails, especially for the wireless communication setup. Therefore, we are dealing with a random time-varying channel between the transmitter and the users. In this paper, to model the randomness of the channel, we consider a binary deterministic version of a time-varying memoryless fading broadcast channel when the transmitter is serving users. However, the pre-fetching phase takes over the noiseless links. We study such a caching problem in a joint source-channel coding framework and analyze the limitations of the source rate for the transmitter.

Related Works.
Coded caching schemes are proposed under the perfect channel assumption for the delivery phase and the uncoded cache placement where the placement performs on pure packets of the files for the centralized  [2] and the decentralized settings [3]. It is shown that a significant gain can be achieved by sending coded packets and simultaneously serving multiple users. A distributed source coding problem is presented in [4] to study the cache-aided networks. The database is viewed as a discrete memoryless source and the users' requests as side information that is available everywhere except at the cache encoder. The inner and outer bounds on the fundamental trade-off of cache memory size and update rate are provided. For file selection networks with uniform requests, the derived bounds recover the rates established by [2, 3]. The exact trade-off between the memory and load of delivery is characterized [5] for the uncoded placement. The coded caching problem has also been studied in various setups, including online caching [6], device-to-device caching [7, 8], caching with nonuniform demands [9, 10], coded cache placement [11, 12, 13, 14].

All of the aforementioned works assume that the delivery phase takes over a perfect channel. However, in practice, we are dealing with noisy broadcast channels, especially for wireless communication systems. For the wireless setup, various types of channel models have been studied, such as cache-aided interference channels [15, 16, 17], caching on broadcast channels [18, 19], erasure and fading channels [20, 21, 22], and channels with delayed feedback with channel state information [23, 24]. The cache-aided communications problem is modeled as a joint cache-channel coding problem in [18]. The delivery phase takes place over a memoryless erasure broadcast channel. It is shown that using unequal cache sizes and joint cache-channel coding improves system efficiency when the users experience different channel qualities. The capacity-memory trade-off of the $K$-user broadcast channel is studied when each user is equipped with a cache. It is optimal to assign all the cache memory to the weakest user for the small total cache size. On the other hand, for the large cache size, it is optimal to assign a positive portion of the cache to each user where weaker users have access to a larger cache memory than stronger users. Another wireless communication model is considered in [23] where a $K$-antenna transmitter communicates to $K$ single receiver antenna. It is shown that the combination of caching with a rate-splitting broadcast approach can reduce the need for channel state information at the transmitter.

Note that in a fast-fading environment sending the channel state information (CSI) from the receiver to the transmitter over a feedback link is difficult. So, it is more reasonable to consider broadcast channels with no CSI. The ergodic capacity region of a $K$-user binary deterministic version of the time-varying memoryless fading broadcast channel ($K$-DTVBC) introduced by [25] is studied in [26, 27]. Depending on the instantaneous channel strength, each user only receives the most significant bits of the transmit signal. Using the insight from the $K$-DTVBC model, an outer bound to the Gaussian fading BC capacity region is derived.

In this work, we study a communication model over the $K$-DTVBC for $n$ channel use where each user is equipped with a cache. The transmitter has some source rate per channel for each file in its database. A fixed fraction of each file is available in each user's cache. Here, we focus on a class of uncoded cache placement schemes. After the completion of this phase, each user demands a file. Then, the transmitter forms broadcasting messages such that each user can decode his desired file. The main challenge for the transmitter is to assign the signal levels to the (broadcasting) messages intended for each user without having access to the realization of the channels, which consists of the number of bits delivered to each user. Note that a fast-fading environment needs coding for reliable communication, where the capacity of the channel is achievable using channel codes with sufficiently large block lengths. Thus, we study the asymptotic behavior of the system, where we allow the size of messages in the pre-fetching and fetching phases will grow with the communication block length. This leads us to deal with a joint source-channel coding problem where the transmitter has a certain source rate per channel use. We characterize the maximum achievable source rate for the two-user and the degraded $K$-user problems.
Then, we provide an upper bound for the source rate. Finally, we discuss an achievable scheme with the linear programming (LP) formulation to show the looseness of the characterization for $K>2$.

Outline of the Paper. In the following, we formulate the problem in Section <ref>, and present the main results in Section <ref>, whose proofs are presented in Section <ref>-<ref>. In Section <ref>, we provide an achievable source rate through the LP formulation and then show the achieved information-theoretic bound is not tight in general. Finally, we conclude the paper in Section <ref>.

Throughout this paper, we denote the set of integers $\{1,2,\ldots,N\}$ by $[N]$ and the set of non-negative real numbers by $\mathbb{R}^{+}$. For a binary vector of length $\nB$, i.e.,  $X\in \mathbb{F}_2^\nB$, and a pair of integers $a<b$, we use the short hand notation $X(a:b)$ to denote $[X(a), X(a+1), \ldots, X(b)]$. We use $(a,b]$ to refer to the interval $(a,b]:=\{x\in \mathbb{R}: a<x\leq b\}$. For a set of real numbers $\cI$, we use $|\cI|$ to denote its Lebesgue measure, e.g., $|(a,b]|:=b-a$ denotes the  length of the interval. The all-ones and all-zeros vectors are defined as $\ones_n:=(1,1,\ldots,1)\in \mathbb{R}^{n\times 1}$ and $\zeros_n:=(0,0,\ldots,0)\in \mathbb{R}^{n\times 1}$, respectively.

§ PROBLEM FORMULATION

In this section, we first introduce the $K$-DTVBC, which is the core of this work. Then, we discuss the joint source-channel coding problem studied in this paper.

A $K$-user binary deterministic version of the time-varying memoryless fading broadcast channel. The transmitter only knows the statistics, but not the realizations of the generated i.i.d. random sequence $\{L_k[t]\}_{t=1}^{n}$.

§.§ Channel Model

We are interested in a time-varying broadcast channel, where a transmitter aims at sending one message to each of the $K$ users. We consider the $K$-DTVBC introduced by [25] as shown in Figure <ref>. The  channel is modeled by

\begin{equation}
Y_{k,t} = D^{\nB-L_k[t]}X_{t} = X_t(1:L_k[t]),\qquad k \in [K],
\label{eq:ch-model-detl}
\end{equation}

where $X_t, Y_{k,t} \in \mathbb{F}_2^\nB$ for $k\in [K]$, and $D$ is a $\nB\times \nB$  shift matrix, given by

\[
D = \begin{bmatrix}
0 & 0 & 0 & \dots & 0\\
1 & 0 & 0 & \dots & 0\\
0 & 1 & 0 & \dots & 0\\
\vdots & \ddots & \ddots & \ddots & \vdots\\
0 & \dots & 0 & 1 & 0\\
\end{bmatrix}.
\]

A transmitter containing $N$ files of size $nf$ bits each is connected through a $K$-DTVBC to users each with a cache of size $n M f$ bits.

Here $L_k[t]$ with $0\leq L_k[t]\leq \nB$ determines the number of bits delivered to user $k$ at time $t$. The channel state at user $k$, i.e.,  $\{L_k[t]: t = 1,\ldots,n\}$, is an i.i.d. random sequence generated according to some probability mass function (PMF) $P_{L_k}(\ell):= \mathbb{P}[L_k=\ell]$.  We assume that the channel state information is casually known only to the receivers. However, the transmitter only knows the channel statistics $P_{L_k}(\ell)$, but not the channel  realizations.

We denote the complementary cumulative
distribution function (CCDF)  of $L_k$ for any $\ell \in [B]$ by
\begin{align*}
\overline{F}_{L_k}(\ell):= \mathbb{P}[L_k \geq \ell].
\end{align*}

For notational simplicity, let

\begin{align*}
\bof_{L_k} :=
\begin{bmatrix}
\overline{F}_{L_k}(1) \\ \vdots \\ \overline{F}_{L_k}(\nB)
\end{bmatrix},
\end{align*}

for each user $k \in [K]$.

The random variable $L_k$ is stochastically larger than $L_v$, if $\ov{F}_{L_k}(\ell) \geq \ov{F}_{L_v}(\ell)$ for every $\ell \in [B]$ and we denote it by $L_k\geq_{\mathsf{st}} L_v $.

The capacity region of the $K$-DTVBC is derived in [27]. In this work, we focus on a cache-aided version of this problem, where the users are equipped with a cache that can pre-fetch part of the messages. In contrast to [27], where the capacity region is characterized, we are interested in the symmetric rate, as it is standard to consider equal file sizes in file delivery systems.

In the majority of the existing literature on coded caching, a perfect channel is assumed between the transmitter and the users. Hence, the focus is on minimizing the design of the placement and delivery phases to minimize the load on the perfect channel [2, 3, 7, 8, 5]. Here, we are dealing with a fast fading channel which requires coding for reliable communication. Hence, we allow for a large code length and study the asymptotic behavior of the channel. Consequently, the size of the message(s) will grow with the communication block length. This leads to a joint source-channel coding problem [28, 29, 30]. More precisely, we consider a communication scenario over $n$ channel uses, where the transmitter has a library of $N$ files, each of size $nf$ bits. Each user is equipped with a cache that can pre-fetch up to $n M f$ bits (before the actual request of the user is revealed), and the goal is to send one requested file to each user reliably. We are interested in characterizing the maximum source rate $f$ for which, and for sufficiently large block length $n$, a reliable communication scheme can be devised. A similar joint source-channel coding approach is used to study the original coded caching problem with common rate and side information in [4]. Further details of the cache model are discussed in the next section.

§.§ Joint Source-channel Coding Framework

Let us consider a communication scenario over the $K$-DTVBC for $n$ channel uses. The transmitter has some source rate $f\in \mathbb{R}^+$ per channel use that generates $N$ files, namely, $W^{(n)}_i$ for $i\in[N]$. This means the transmitter has access to a database of $N$ mutually independent files $W^{(n)}_1,\ldots, W^{(n)}_N$ each of size $nf$ bits, i.e.,

\begin{equation*}
W^{(n)}_i\in \{1,2,\ldots,2^{nf}\}, \quad i\in [N].
\end{equation*}

We assume each user $k$ is equipped with a cache, which can pre-fetch part of the files. The size of the content is proportional to the communication block length. More precisely, we assume that user $k$ has a cache $C^{(n)}_k$ of size $nMf$ bits, for $k\in[K]$. In the placement phase, the cache memory of each user is filled with uncoded bits of the files; that is, the content of the cache $C^{(n)}_k$ can be partitioned into raw (uncoded) bits of the files.

Caching Strategy.
A caching strategy $\cache$ for a normalized cache size $\mu=M/N$ and a network with $K$ users consists of $K$ collections of intervals in $(0,1]$. More precisely,  $\cache=(\bc_1,\bc_2,\dots, \bc_K)$ where

* $\bc_k = \bigcup_{\ell \in [\nn_k]} \cI_{k,\ell}$,

* $\nn_k$ is a finite positive integer number for every $k\in [K]$,

* $\cI_{k,\ell}=(a_{k,\ell}, b_{k,\ell}] \subseteq (0,1]$ where $b_{k,\ell}\leq a_{k,\ell+1}$ for every $\ell\in [K\!-\!1]$, and

* $\sum_{\ell\in[\nn_k]} |\cI_{k,\ell}| =\mu$, for every $k\in [K]$.

For a file $W=(W(1),W(2), \dots, W(F))\in \mathbb{F}_2^F$ of length $F$ bits, we define

\[W(\bc_k) := \bigcup_{\ell\in [\nn_k]} \{W(\lceil a_{k,\ell}F\rceil+1), W(\lceil a_{k,\ell}F\rceil+2), \cdots,  W(\lfloor b_{k,\ell}F\rfloor) \}.\]

Then, for a given source rate $f$, block length $n$, family of files $\left\{W_i^{(n)}\right\}$, and caching placement strategy $\cache$, the cache content of user $k\in [K]$ is given by

\begin{align}\label{eq:cache}
C^{(n)}_k :=\bigcup_{i\in [N]} C^{(n)}_{k,i} =  \bigcup_{i\in [N]} W^{(n)}_i(\bc_k)  = \bigcup_{i\in [N]} \bigcup_{\ell \in [\nn_k]} \left\{W^{(n)}_i(\lceil nf a_{k,\ell}\rceil +1),\dots, W^{(n)}_i(\lfloor nf b_{k,\ell}\rfloor) \right\}.
\end{align}

This implies that

\begin{align}
H\left(C^{(n)}_{k,i}\right) \leq  \sum_{\ell\in[\nn_k]} \left(\lfloor nf b_{k,\ell} \rfloor - \lceil nf a_{k,\ell}\rceil \right)
\leq \sum_{\ell\in[\nn_k]} nf |\cI_{k,\ell}| =  \mu nf.
\end{align}

Therefore, we get

\begin{align*}
H\left(C_k^{(n)}\right) &= H\left( C^{(n)}_{k,1}, C^{(n)}_{k,2}, \dots, C^{(n)}_{k,N}\right)\\
&\leq H\left( C^{(n)}_{k,1}\right) +H\left(C^{(n)}_{k,2}\right)+ \cdots +  H\left(C^{(n)}_{k,N}\right)\\
&\leq \sum_{i=1}^N n \mu f = nM f.
\end{align*}

Moreover, from the definition of the cache content in (<ref>) and the independence of files, we can write

\begin{align*}
& H\lp C^{(n)}_{k,i}\middle| W^{(n)}_i \rp=0,\\
& I\lp C^{(n)}_{k,j};W^{(n)}_i\rp=0, \quad j \neq i.
\end{align*}

We define $\bc_\cS:= \bigcup_{u\in \cS} \bc_u = \bigcup_{u\in \cS} \bigcup_{\ell\in [\nn_u]} \cI_{u,\ell}$ for every $\cS\subseteq [K]$ and the caching tuple $\bmu :=(\mu_{\cS}: \cS\subseteq [K])$ where $\mu_{\cS}:= |\bc_\cS|$. We also use $C^{(n)}_{\cS,i}$ to refer to the collection of all the parts of file $i$ cached by the users in the subset $\cS\subseteq [K]$, i.e.,  $C^{(n)}_{\cS,i} = \bigcup_{u\in \cS} C^{(n)}_{u,i}$. Therefore, we have

\begin{align}\label{eq:H-CS}
H\left(C^{(n)}_{\cS,i}\right) \leq \mu_\cS nf,
\end{align}

for every $i\in [N]$.
After the completion of the placement phase, each user requests one of the $N$ files, where all files are equally likely to be requested. We denote $d_k\in [N]$ as the index of the file requested by user $k\in[K]$ and the sequence of all requests by $\boldsymbol{d}=(d_1,\ldots,d_K)$.
Once the requests are revealed to the transmitter, it forms a broadcasting message ${X^{n}=(X_1,X_2,\dots, X_n)=\psi_{\boldsymbol{d}}^{(n)} \left(W^{(n)}_1,\ldots,W^{(n)}_N; C^{(n)}_{[K]}\right)}$, where

\begin{equation*}
\psi_{\boldsymbol{d}}^{(n)}: \{1,2,\ldots,2^{nf}\} ^N \times \{1,2,\dots, 2^{nMf}\}^K \rightarrow \{1,2,\ldots,2^{\nB}\}^n,
\end{equation*}

and transmits $X_t$ over the broadcast channel during the $t$-th channel use  of the delivery phase, for $t=1,\dots, n$. Upon receiving  $Y_k^n=(Y_{k,1},Y_{k,2}, \ldots, Y_{k,n})$, user $k\in [K]$ should be able to decode its desired file using its cache content $C^{(n)}_k$ and the received message $Y^n_k$ (see Figure <ref>), i.e.,

\begin{equation*}
\hat{W}^{(n)}_{d_k} = \phi_k^{(n)}\left(Y^n_k,C^{(n)}_k\right).
\end{equation*}

The overall decoding error probability is defined as

\begin{align*}
P_e^{(n)}:= \sum_{k=1}^{K} \mathbb{P}\left[\hat{W}^{(n)}_{d_k}\neq W^{(n)}_{d_k}\right].
\end{align*}

For a given caching strategy $\cache$ and a (distinct) request profile $\bd$, a source rate $f(\cache,\bd)$ is called achievable if there exists a sequence of  caching strategies, encoding, and decoding functions

\[
\left\{\left(\chi^{(n)}_{1,1},\ldots,\chi^{(n)}_{K,N},\psi^{(n)}, \phi_1^{(n)}, \ldots,\phi_K^{(n)}\right)\right\}_n,
\]

for which $P_e^{(n)} \rightarrow 0$ as $n$ grows.

Here, our goal is to characterize the maximum achievable source rate $f(\cache,\bd)$ for the $K$-DTVBC with channel statistics $\bof_{L_k}$. Note that the cache placement is fixed prior to the users' demands, and we are not designing the cache contents of users based on the requested files.

§ MAIN RESULTS

In this section, we present the main results of this paper.

We first characterize the maximum achievable source rate for the $2$-DTVBC.

The maximum achievable source rate of the $2$-DTVBC for $\mu\leq \frac{1}{2}$ is given by

\begin{align}\label{eq:f-2User}
\fs = \min \lc \min_{\w \geq 1}\frac{\w R_1(\w) +  R_2(\w)}{\w (1-\mu)+(1-2\mu)}, \min_{0\leq \w \leq 1}\frac{R_1(\w) + \frac{1}{\w} R_2(\w)}{(1-2\mu) + \frac{1}{\w} (1-\mu)}  \rc,
\end{align}

and for $\frac{1}{2}\leq \mu\leq 1$ is characterized by

\begin{align}\label{eq:f-2User-2}
\fs = \min \lc \frac{\sum_{\ell=1}^{B} \ov{F}_{L_1}(\ell)}{1-\mu}, \frac{\sum_{\ell=1}^{B} \ov{F}_{L_2}(\ell)}{1-\mu}\rc,
\end{align}

\begin{align}\label{eq:R1-R2}
R_1(\w):= \sum_{\ell\in \cL_1(\w)} \overline{F}_{L_{1}}(\ell),\qquad
R_2(\w) := \sum_{\ell\in \cL_2(\w) } \overline{F}_{L_{2}}(\ell),
\end{align}

$\cL_1 (\w) :=  \{\ell: \w \ov{F}_{L_1}(\ell) \geq \ov{F}_{L_2}(\ell)\}$, and $\cL_2 (\w) := \{\ell: \w \ov{F}_{L_1}(\ell) < \ov{F}_{L_2}(\ell)\}$.

The proof of Theorem <ref> is provided in Section <ref>.

We denote the cache placement strategy introduced in [2] by $\cent$ and its caching tuple by $\tcent$. Next, we provide an LP optimization problem for the maximum achievable source rate of the degraded $K$-DTVBC with the caching strategy $\cent$.

The maximum achievable source rate of the degraded $K$-DTVBC, i.e., ${L_K\geq_{\mathsf{st}}\cdots \geq_{\mathsf{st}} L_1}$ for the caching strategy $\cent$ and a (distinct) request profile $\bd$ is given by

\begin{align}\label{eq:fwKUser_degraded}
&\max_{\{\xi_k(\ell)\}} \ \bar{f},\\
&\textrm{s.t.}\quad  \lp 1-\tcents_{[k]}\rp \bar{f} \leq  \sum_{\ell=1}^{B} \xi_k(\ell)\ov{F}_{L_k}(\ell), \quad \forall k\in [K],\nonumber\\
&\phantom{\textrm{s.t.}\quad} \xi_k(\ell)  \geq  0, \quad \forall k\in [K], \forall \ell\in [B],\nonumber\\
&\phantom{\textrm{s.t.}\quad} \sum_{k=1}^{K} \xi_k(\ell) \leq  1\nonumber, \quad \forall\ell\in [B],
\end{align}

where $\tcents_{[k]} = 1-\binom{K-k}{t}/\binom{K}{t}$.

The achievability proof of Theorem <ref> is presented in Section <ref>, and its converse proof is provided in Section <ref>.

The following theorem provides an upper bound for the source rate of the $K$-DTVBC with any given caching strategy $\cache$.

Any achievable source rate of the $K$-DTVBC for a given cache placement strategy $\cache$ and a (distinct) request profile $\bd$ is upper-bounded by

\begin{align}\label{eq:fwKUser}
f(\cache,\bd) \leq \fs(\cache,\bd) := \min_{\bfw \geq 0} \frac{\sum_{\ell=1}^\nB \max_{k}  \w_{\pi(k)} \ov{F}_{L_{\pi(k)}} (\ell)}{\sum_{k=1}^{K}
\omega_{\pi(k)}\lp 1-\mu_{\pi([k])} \rp },
\end{align}

where $\bfw := (\w_1,\ldots,\w_K) \in [0,\infty)^K$, $\pi([k]):=\{\pi(1),\ldots, \pi(k)\}$, and $\pi:[K]\rightarrow [K]$ is the permutation that sorts $\bfw$ in the non-increasing order.

The proof of Theorem <ref> is presented in Section <ref>.

Note that the upper bound in the theorem is given as a min-max problem, for which the evaluation of the optimum point can be computationally challenging. In the following proposition, we show that the upper-bound  in (<ref>) can be evaluated by solving $K!$ linear programming problems (LPP), each corresponding to a permutation of users. Hence, denoting $t_{\mathsf{LP}}$ as the run time for each LPP, the complexity of evaluation of the upper-bound in (<ref>) is $K!\times t_{\mathsf{LP}}$.

The min-max problem in (<ref>) is equivalent to

\begin{align}\label{eq:LP_form}
\fs(\cache,\bd) = \min_{\pi\in \Pi} \fs_{\pi}(\cache,\bd),
\end{align}

\begin{align}\label{eq:LP_form_2}
\fs_{\pi}(\cache,\bd) := & \min_{\bx \in \mathbb{R}^{K\!+\!B}} \ [\zeros_{K},\ones_{B }]^T\bx,\\
& \textrm{s.t.}\quad \bA_{\pi} \bx \leq \zeros,\nonumber\\
& \phantom{\textrm{s.t.}\quad} \bb \bx = \ones,\nonumber\\
& \phantom{\textrm{s.t.}\quad} -\bx \leq \zeros\nonumber,
\end{align}

$\Pi$ is the set of all permutations over $[K]$, $\bA_{\pi}\in \mathbb{R}^{(KB + K\!-\!1)\times(K+B)}$, and $\bb\in \mathbb{R}^{1\times (K+B)}$ are defined as

\begin{align}
&\bA_{\pi}\!=\! \begin{bmatrix}
\begin{array}{c c  c c c|c}
\bof_{L_{\pi(1)}} & \zeros_B & \cdots & \zeros_B & \zeros_B & \lp \mu_{\pi(1)}-1\rp \!\bfI\\
\zeros_B & \bof_{L_{\pi(2)}} & \cdots & \zeros_B & \zeros_B & \lp \mu_{\pi([2])}-1\rp\!\bfI\\
\vdots & \vdots & \vdots & \vdots & \vdots &  \vdots\\
\zeros_B & \zeros_B & \cdots & \zeros_B & \bof_{L_{\pi(K)}} & \lp \mu_{\pi([K])}-1\rp\!\bfI\\
\hline
\mu_{\pi([2])}\!-\!1 &  1\!-\!\mu_{\pi(1)} & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
0 & 0 & \cdots & \mu_{\pi([K])}\!-\!1 & 1\!-\!\mu_{\pi([K\!-\!1])} & 0
\end{array}
\end{bmatrix}\!,\label{eq:Matrix-A}\\
&\bb = [\ones_K,\zeros_B]^T\label{eq:vector-b},
\end{align}

and $\bfI \in \mathbb{R}^{B\times B}$ is the identity matrix.

The proof of Proposition <ref> is provided in Section <ref>.

§ AN ACHIEVABLE SCHEME: LP FORMULATION

In this section, we provide an achievable scheme, which is based on LP. Then, in an illustrative example, we show the upper-bound in (<ref>) is not a sharp characterization for non-degraded channels with $K>2$ users.

Similar to [2], we focus on specific normalized cache sizes $\mu$ such that  $t:= K\mu =KM/N \in \mathbb{N}$. Let us assume that each user $k\in[K]$ requests file $W^{(n)}_k$. The delivery scheme of [2]  consists of broadcasting coded packets to serve multiple users simultaneously. Each coded packet is intended for a group of users $\cS\subseteq \{1,\dots, K\}$ with $|\cS|=t+1$. More precisely, we have

\begin{align*}
W^{(n)}_\mathcal{\cS} = \bigoplus_{k\in \cS} W^{(n)}_{d_k,\cS\setminus\{k\}}.
\end{align*}

We aim at sending each coded packet $W^{(n)}_\mathcal{\cS}$ to all users $k\in \cS$. To this end, we devise a bit allocation strategy $\by=\{y_{\ell,\cS}: \ell\in [\nB], \cS \subseteq [K], |\cS|=t+1\}$, where $y_{\ell,\cS}$ denotes the fraction of time that level $\ell$ is used to transmit coded message $W^{(n)}_{\cS}$.

Note that for a given source rate $\bar{f}$ for all files, the rate of $W^{(n)}_\cS$ will be $\bar{f}/\binom{K}{t}$. Then, a coded message $W^{(n)}_{\cS}$ with $k\in \cS$ is decodable at user $k$ if

\begin{align}
\sum_{\ell=1}^\nB \overline{F}_{L_k}(\ell) y_{\ell,\cS}  \geq \frac{\bar{f}}{\binom{K}{t}}.
\label{eq:LP-decode}
\end{align}

For a feasible allocation policy $\by$, in each level, the sum of time factions allocated to all coded messages should not exceed $1$, that is

\begin{align}
\sum_{\substack{\cS\subseteq [K]\\|\cS|=t+1 }}  y_{\ell,\cS} \leq 1, \qquad \forall \ell\in [\nB].
\label{eq:LP-level}
\end{align}

So, we have an optimization problem given by

\begin{align}
\begin{split}
\fl := & \max \  \bar{f}\\
& \textrm{s.t.} \  \eqref{eq:LP-decode}-\eqref{eq:LP-level}\\
&\ y_{\ell,\cS} \geq 0, \qquad \forall \ell\in [\nB], \forall \cS\subseteq [K], |\cS|=t+1.
\end{split}
\label{eq:LP}
\end{align}

We can write the optimization problem as a linear program. To this end, define a vector $\by$ of length ${\ml = \nB \binom{K}{t+1}+1}$, which is formed by stacking all variables in  $\{y_{\ell,\cS}: \ell\in [\nB], \cS\subseteq [K], |\cS| = t+1\}$ along with $f$ at the very last position. The first $\nB\binom{K}{t+1}$ entries of $\by$ are labeled by pairs $(\ell,\cS)$ and we label and set $\by_m = -\bar{f}$ for the last entry of $\by$.

To write the constraints in the matrix form, we define a matrix $\bG\in \mathbb{R}^{K\binom{K-1}{t}\times \ml}$ (for aggregation of information).
The columns of $\bG$ are labeled similar the entries of $\bx$, and each rows are labeled by a pair $(k,\cT)$ where $k\in \cS$, $\cT\subseteq [K]\setminus \{k\}$, and $|\cT|=t$. An entry at row $(k,\cT)$ and column $(\ell,\cS)$ is given by

\begin{align*}
\bG_{(k,\cT),(\ell,\cS)} &=
\begin{cases}
-\overline{F}_{L_k}(\ell)  & \textrm{if $\cS = \cT \cup \{k\}$}\\
0 & \textrm{otherwise},
\end{cases}
\end{align*}

and the entries in the $m$-th column are

\begin{align*}
\bG_{(k,\cT),m} &= \frac{1}{\binom{K}{t}}, \qquad \forall (k,\cT),
\end{align*}

which reduce the constraint (<ref>) into $\bG \by \leq \zeros$.

Similarly, the constraint in (<ref>) can be written in the matrix form, using a matrix $\bH\in \mathbb{R}^{\nB \times m}$ defined as

\begin{align*}
\bH_{\b,(\ell,\cS)} &=
\begin{cases}
1 & \textrm{if $\b=\ell$}\\
0 & \textrm{if $\b\neq\ell$},
\end{cases}\\
\bH_{\b,m} &= 0, \qquad \forall \b\in [\nB].
\end{align*}

Then we have

\begin{align}\label{eq:LP_ach_schm}
\fl = & \min \ [\zeros_{1\times (m-1)} , -1] \bx\\
& \textrm{s.t.} \quad \bG \by \leq \zeros\nonumber \\
&\phantom{\textrm{s.t.} \quad} \bH \by \leq \ones\nonumber \\
&\phantom{\textrm{s.t.} \quad} -\by \leq \zeros\nonumber.
\end{align}

Now for a non-degraded broadcast channel, we provide an example to show that the achievable source rate in (<ref>) does not meet the upper-bound in (<ref>).
[Not Degraded Channel Case]
Let us consider  a network with $K=3$ users $N=3$ files, namely $\{W_1,W_2,W_3\}$, and $\nB=3$ transmit levels. The channel statistics of the three users are given by the complementary  cumulative  distribution  functions as

\begin{align*}
&\overline{F}_{L_1} =[0.9,0.3,0.3]^T, \cr
&\overline{F}_{L_2} = [0.7,0.4,0.4]^T,\cr
&\overline{F}_{L_3} = [0.5,0.5,0.5]^T.
\end{align*}

That is, the first user receives the top level with probability $0.9$, but the bits sent over all three $\nB=3$ levels are delivered at this same user with probability $0.3$.
Consider the caching strategy $\cent$ with $\mu = 1/3$, i.e.,

\begin{align*}
\bc_1 = (0,1/3],\quad \bc_2 = (1/3, 2/3], \quad \bc_3 = (2/3,1].
\end{align*}

Hence, the placement strategy $\cent$ implies that the cached parts of the files at different users are disjoint, i.e., $W^{(n)}_{i} = \bigcup_{k=1}^{3} W^{(n)}_{i,k}$ for every $i\in [N]$ where $W^{(n)}_{i,k}$ the part of file $W^{(n)}_i$ cached exactly by user $k$.

Without loss of generality, assume user $k$ is interested in  file $W^{(n)}_k$, for $k\in\{1,2,3\}$. Then, the transmitter has to send coded messages $W^{(n)}_{\{1,2\}} = W^{(n)}_{1,2} \oplus W^{(n)}_{2,1}$, $W^{(n)}_{\{1,3\}} = W^{(n)}_{1,3} \oplus W^{(n)}_{3,1}$, and $W^{(n)}_{\{2,3\}} = W^{(n)}_{2,3} \oplus W^{(n)}_{3,2}$. The optimum solution from the linear program (<ref>) would be

\begin{align}
\begin{array}{cccccccccccc}
& \!
{\scriptstyle(1,\{1,2\})} &\! {\scriptstyle(1,\{1,3\})} &\! {\scriptstyle(1,\{2,3\})} &\! {\scriptstyle(2,\{1,2\})} &\! {\scriptstyle(2,\{1,3\})} &\! {\scriptstyle(2,\{2,3\})} &\! {\scriptstyle(3,\{1,2\})} &\! {\scriptstyle(3,\{1,3\})} &\! {\scriptstyle(3,\{2,3\})} & \!
m \\
\by = \Big[ &\!
\frac{2}{3} &
\frac{ 1}{3} &
0 &
\frac{1}{12} &
0 &
\frac{11}{12} &
0 &
\frac{2}{3} &
\frac{1}{3} &
\frac{3}{2} &
\Big]^T\!\!,
\end{array}
\label{eq:ex:LP-mu=1/3}
\end{align}

where $(\ell,\cS)$ indicates the fraction of time that the transmitter assigns signal level $\ell$ to send coded messages $W^{(n)}_{\cS}$. This implies the source rate of $\fl = 3/2$ is achievable. Note that each user $k$ is able to decode its desired file $W^{(n)}_k$ by receiving two coded messages $W^{(n)}_{\cS}$ with $k\in \cS$ at the rate $\mu \fl$ (for each coded message) and its cache content. Therefore, for this source rate, the rate of each coded message is $\fl/3 = 1/2$.

The transmission scheme devised by (<ref>) suggests using the top level for $2/3$ fraction of time and the second level for $1/12$ fraction of time to send   $W^{(n)}_{\{1,2\}}$. Hence, user 1 is able to decode the message $W^{(n)}_{\{1,2\}}$ at the rate

\begin{align*}
0.9 \times \frac{2}{3} + 0.3 \times \frac{1}{12} = \frac{5}{8} \geq \frac{1}{2} = \frac{\fl}{3},
\end{align*}

and user $2$ decodes the message $W^{(n)}_{\{1,2\}}$ at the rate

\begin{align*}
0.7 \times \frac{2}{3} + 0.4 \times \frac{1}{12} = \frac{1}{2} \geq \frac{1}{2} = \frac{\fl}{3}.
\end{align*}

Therefore, both users can decode $W^{(n)}_{\{1,2\}}$. A similar argument holds for decodability of $W^{(n)}_{\{1,3\}}$ at users $1$ and $3$, as well as decodability of $W^{(n)}_{\{2,3\}}$ at users $2$ and $3$. Now we investigate the achievability of the upper-bound $\fs(\cent,\bd)$. Solving the LPP in (<ref>), we get

\begin{align*}
\htf:=\fs(\cent,\bd) = \min_{\pi\in \Pi}\fs_{\pi}(\cent,\bd) = \min \{1.66,    1.76, \textbf{1.61}, 1.62,    1.73,    1.64\} = 1.61,
\end{align*}

where the permutation corresponds to   the minimum value is $\pis = (2,3,1)$   with ${\bfw^\s=(0,1.25,1)}$. We summarize the upper-bound on the source rate for $\fs_{\pi}(\cent,\bd)$ each permutation $\pi$ in Table <ref>.

$\pi$     $\fs_{\pi}(\cent,\bd)$

$(3,2,1)$     $1.66$

$(3,1,2)$     $1.76$

$(2,3,1)$     $\textbf{1.61}$

$(2,1,3)$     $1.62$

$(1,3,2)$     $1.73$

$(1,2,3)$     $1.64$

The upper-bound on the source rate for each permutation with the caching strategy $\cent$ and the normalized cache size $\mu=1/3$.

Hence, for the permeation $\pis = (2,3,1)$, we can write

\begin{align*}
&\tcents_{\pis([1])} = \tcents_{\{2\}} = \frac{1}{3}, \\
& \tcents_{\pis([2])} =\tcents_{\{2,3\}} = \frac{2}{3},\\
& \tcents_{\pis([3])} = \tcents_{\{1,2,3\}} =1.
\end{align*}

Thus, the transmitter assigns subsets of signal levels to users 2, 3, and 1 to decode their messages at the supported rate $\lp 1\!-\!\mu_{\pis([1])} \rp \htf=1.07$, $\lp 1\!-\!\mu_{\pis([2])} \rp \htf=0.535$, and $\lp 1\!-\!\mu_{\pis([3])} \rp \htf =0$, respectively. This indicates that the transmitter requires to assign the levels to only users 2 and 3.

$k$     $\ell$      1       2     3

$1$     $\w^\s_{1}\ov{F}_{L_{1}}(\ell)$     $0$     $0$     $0$

$2$     $\w^\s_{2}\ov{F}_{L_{2}}(\ell)$     $\mathbf{0.875}$     $0.5$     $0.5$

$3$     $\w^\s_{3}\ov{F}_{L_{3}}(\ell)$     $0.5$     $0.5$     $0.5$

Comparison of $\w_k \ov{F}_{L_{k}}(\ell)$ for Example <ref>.

From Table <ref>, the transmitter assigns the signal level $\ell=1$ to user 2 and can allocate signal levels $\ell=2,3$ to users 2 or 3. More precisely, we can write

\begin{align*}
\sum_{\ell=1}^{B=3} \max_k \ws_k \ov{F}_{L_k}(\ell) & \!=\! \ws_2 \ov{F}_{L_2}(1) \!+\! \alpha  \ws_2 \ov{F}_{L_2}(2) + \beta  \ws_2 \ov{F}_{L_2}(3) + (1\!-\!\alpha)  \ws_3 \ov{F}_{L_3}(2) + (1\!-\!\beta)  \ws_3 \ov{F}_{L_3}(3) = 1.875,
\end{align*}

for any $0 \leq \alpha, \beta \leq 1$. Let us define $\R{k}{\{k,u\}}$ as the supported rate of user $k$ to decode coded messages $W^{(n)}_{\{k,u\}}$ at the source rate $\htf$.  Now we examine the achievability of the rate $\htf$. In this regard, the transmitter requires to guarantee that each user is able to decode its desired messages at rate $\htf$. We first start with user 3, who is intended to decode the message $W^{(n)}_{\{1,3\}}$. The level $3$ and $0.07$ fraction of level $2$ is assigned to user 3 i.e.,

\begin{align*}
\R{3}{\{1,3\}} = \ov{F}_{L_{3}}(3) + 0.07 \times \ov{F}_{L_{3}}(2) = 0.535.
\end{align*}

While for user 3 the supported rate to decode messages $W_{\{1,3\}}$ is given by

\begin{align*}
\R{1}{\{1,3\}} = \ov{F}_{L_{1}}(3) + 0.07 \times \ov{F}_{L_{1}}(2) = \mathbf{0.321} < 0.535.
\end{align*}

Therefore, user 3 is not able to decode his intended message $W^{(n)}_{\{1,3\}}$ at the source rate $\htf$. This implies that the upper-bound $\htf=1.61$ is not achievable with this specific type of delivery phase. Note that Theorem <ref> only provides a sharp characterization when the channel is degraded, which does not hold in this example.  $\diamond$

§ PROOF OF THEOREM <REF>

In this section, we present the proof of Theorem <ref>. To do this, we first provide the converse proof and then discuss the achievability proof.

§.§ Converse

The converse proof of Theorem <ref> is based on the result of [26]. We need to construct a degraded broadcast channel. In this regard, we replace $L_2$, the channel of User 2, with an enhanced channel $\widetilde{L}_2$. For a given $\w\geq 1$, we define

\begin{align}\label{eq:enh-2user}
\ov{F}_{\wdt{L}_2}(\ell):= \min \lb 1, \max \lb \ov{F}_{L_2}(\ell), \w \ov{F}_{L_1}(\ell) \rb\rb, \quad \ell\in [B],
\end{align}

which is the CCDF of $\widetilde{L}_2$. Moreover, we define $\wdt{Y}_2:=D^{B-\wdt{L}_2}X = X(1:\wdt{L}_2)$. Hence, we have a degraded broadcast channel, i.e., $X\leftrightarrow \wdt{Y}_2\leftrightarrow Y_{1}$.

Next, we derive an upper bound on the maximum achievable source rate for a physically degraded BC.

Consider a physically degraded memoryless BC described by $P_{Y_1,Y_2|X}$ for a given cache placement strategy $\cache$ and a distinct request profile $\bd$. The source rate $f(\cache,\bd)$ is the union over all pairs of $(U_1,X)$ such that $U_1\leftrightarrow X\leftrightarrow Y_2\leftrightarrow Y_{1}$ satisfying

\begin{align}
& f(\cache,\bd)\leq \frac{ I(U_1;Y_{1})}{1-\mu},\label{eq:f-I-2User}\\
& f(\cache,\bd)\leq  \frac{I(X;Y_2|U_1)}{1-2\mu}.\label{eq:f-I-2User-2}
\end{align}

Now, we are ready for the proof of Theorem <ref>. We can use Lemma <ref> for the degraded channel obtained by the enhancement procedure in (<ref>). Let $U_1$ be the random variable satisfying the claim of Lemma <ref>, and form a Markov chain $U_1\leftrightarrow X\leftrightarrow \wdt{Y}_2\leftrightarrow Y_{1}$. Using the fact that CSI is available at the users, for the terms in (<ref>) and (<ref>), we can write

\begin{align}\label{eq:I-U_Y1}
I(U_1;Y_1,L_1) & = I(U_1;X(1:L_1),L_1) \nonumber\\
& = \sum_{j=1}^{B}\P_{L_1}(j)I(U;X(1:j),L_1=j)\nonumber\\
& = \sum_{j=1}^{B}\lb \P_{L_1}(j)\sum_{\ell=1}^{j}I(U_1;X(\ell)|X(1:\ell-1)) \rb\nonumber\\
& =\sum_{\ell=1}^{B}\lb I(U_1;X(\ell)|X(\ell-1))\sum_{j=1}^{\ell}\P_{L_1}(j)\rb\nonumber \\
& =\sum_{\ell=1}^{B}\ov{F}_{L_1}(\ell)I(U_1;X(\ell)|X(\ell-1))\nonumber\\
& = \sum_{\ell=1}^{B}\ov{F}_{L_1}(\ell)\lb H(X(\ell)|X(1:\ell-1))-H(X(\ell)|X(1:\ell-1)),U_1)\rb
\end{align}

Similarly, we have

\begin{align}\label{eq:I-U_Y2}
I(X;\wdt{Y},\wdt{L}_2|U_1) & = I(X;X(1:\wdt{L}_2),\wdt{L}_2|U_1) \nonumber\\
& = I(X;\wdt{L}_2|U_1) + I(X;X(1:\wdt{L}_2)|U_1,\wdt{L}_2)\nonumber \\
& \stackrel{\rm (a)}{=} \sum_{j=1}^{B}\P_{\wdt{L}_2}(j)I(X;X(1:j)|U_1,\wdt{L}_2=j)\nonumber\\
& = \sum_{j=1}^{B}\lb \P_{\wdt{L}_2}(j)\sum_{\ell=1}^{j}I(X;X(\ell)|X(1:\ell-1),U_1) \rb\nonumber\\
& =\sum_{\ell=1}^{B}\lb I(X;X(\ell)|X(\ell-1),U_1)\sum_{j=1}^{\ell}\P_{\wdt{L}_2}(j)\rb\nonumber \\
& =\sum_{\ell=1}^{B}\ov{F}_{\wdt{L}_2}(\ell)I(X;X(\ell)|X(\ell-1),U_1)\nonumber\\
& = \sum_{\ell=1}^{B}\ov{F}_{\wdt{L}_2}(\ell)\lb H(X(\ell)|X(1:\ell-1),U_1)-H(X(\ell)|X,X(1:\ell-1)),U_1)\rb\nonumber\\
& = \sum_{\ell=1}^{B}\ov{F}_{\wdt{L}_2}(\ell) H(X(\ell)|X(1:\ell-1),U_1),
\end{align}

where $\rm{(a)}$ follows from the fact that $\wdt{L}_2$ is independent from $U_1$ and $X$. Therefore, from Lemma <ref>, we get

\begin{align}
\begin{split}\label{eq:f-w-2User}
& \w (1-\mu) f(\cache,\bd) \leq \w \sum_{\ell=1}^{B}\ov{F}_{L_1}(\ell)\lb H(X(\ell)|X(1:\ell-1))-H(X(\ell)|X(1:\ell-1)),U_1)\rb,\\
& (1-2\mu) f(\cache,\bd) \leq \sum_{\ell=1}^{B}\ov{F}_{\wdt{L}_2}(\ell) H(X(\ell)|X(1:\ell-1),U_1).
\end{split}
\end{align}

Taking the sum of (<ref>), we arrive at

\begin{align}\label{eq:fw-2User}
\!(\w(1\!-\!\mu) \!+\! (1\!-\!2\mu)) f(\cache,\bd)
& \!\leq\! \w \sum_{\ell=1}^B \ov{F}_{L_1}(\ell)H(X(\ell)|X(1\!:\!\ell\!-\!1)) \!+\! \sum_{\ell=1}^{B}(\tilde{g}(\ell)\!-\!\w)\ov{F}_{L_1}(\ell)H(X(\ell)|X(1\!:\!\ell\!-\!1),U_1),
\end{align}

where $\tilde{g}(\ell):=\ov{F}_{\wdt{L}_2}(\ell)/\ov{F}_{L_1}(\ell)$. The summands of the first summation in (<ref>) will be maximized by an i.i.d. Bernoulli random variable choice for $X_1,\ldots, X_{B}$. Moreover, the terms in the second summation can be maximized if

\begin{align*}
H(X(\ell)|X(1\!:\!\ell\!-\!1),U_1) =
\begin{cases}
1 & \tilde{g}(\ell)>\w,\\
0 & \tilde{g}(\ell)\leq \w,
\end{cases}
\end{align*}

which can be satisfied by an optimum choice for $U_1$, given by

\[U_1 = \{X(\ell)| \tilde{g}(\ell)\leq \w\}. \]

Hence, for (<ref>) we can write

\begin{align}\label{eq:fw-2User-1}
\!(\w(1\!-\!\mu) \!+\! (1\!-\!2\mu)) f(\cache,\bd) &\leq \w \sum_{\ell:\tilde{g}(\ell)\leq \w} \ov{F}_{L_1}(\ell) + \sum_{\ell:\tilde{g}(\ell)>\w}\tilde{g}(\ell)\ov{F}_{L_1}(\ell)\nonumber\\
& \stackrel{\rm{(a)}}{=} \w \sum_{\ell:\tilde{g}(\ell)\leq \w} \ov{F}_{L_1}(\ell) + \sum_{\ell:\tilde{g}(\ell)>\w}\ov{F}_{\wdt{L}_2}(\ell)\nonumber\\
& \stackrel{\rm{(b)}}{=}  \w \sum_{\ell:\tilde{g}(\ell)\leq \w} \ov{F}_{L_1}(\ell) + \sum_{\ell:\tilde{g}(\ell)>\w}\ov{F}_{L_2}(\ell)\nonumber\\
& = \w R_1(\w)+R_2(\w),
\end{align}

where $R_1(\w)$ and $R_2(\w)$ are defined in (<ref>). We note that in the chain of inequalities in (<ref>), the step $\rm{(a)}$ follows from ${\tilde{g}(\ell)\ov{F}_{L_1}(\ell) = \ov{F}_{L_2}(\ell)}$ and ${\{\ell|\tilde{g}(\ell)>\w\} = \{\ell|g(\ell)>\w\}}$ and $\rm{(b)}$ holds since $\ov{F}_{\wdt{L}_2}(\ell) = \ov{F}_{L_2}(\ell)$ whenever $g(\ell)>\w$.
Dividing both sides of (<ref>) by $\w(1\!-\!\mu) + (1\!-\!2\mu)$ and minimizing over all $\w\geq 1$, we arrive at the the first minimization in (<ref>).

For $0\leq \w \leq 1$, we can repeat the steps in (<ref>) through (<ref>)
by swapping the labels of the users and replacing $\w$ by $\frac{1}{\w}$. Under these reversed labels, we now enhance the channel of User 1 and get the second minimization in (<ref>).

Finally, we characterize the maximum achievable source rate when $\mu>\frac{1}{2}$. Starting (<ref>) and using (<ref>), we can write

\begin{align}\label{eq:f-mu-2}
(1-\mu) f(\cache,\bd) & \leq I(U_1;Y_1,L_1)\nonumber\\
& = \sum_{\ell=1}^{B}\ov{F}_{L_1}(\ell)\lb H(X(\ell)|X(1:\ell-1))-H(X(\ell)|X(1:\ell-1)),U_1)\rb\nonumber\\
& \leq \sum_{\ell=1}^{B}\ov{F}_{L_1}(\ell).
\end{align}

Similarly, by swapping the labels of the users, we can repeat the steps in (<ref>) that leads us to

\begin{align*}
(1-\mu)f(\cache,\bd) \leq \sum_{\ell=1}^{B}\ov{F}_{L_2}(\ell).
\end{align*}

This completes the converse proof.

§.§ Achievability

The achievability proof of Theorem <ref> is based on a linear scheme in which the transmitter only broadcasts a raw and linear combination of the messages. To show that $\fs$ is achievable, we split the messages into three messages, including two private messages (one for each user) and a common message, which is intended for both users. Then, we allocate the (signal) levels in $[B]$ to each of these messages and prove that both users can decode their desired file.

Without loss of generality, we assume the source rate $\fs$ is obtained by the first minimization in (<ref>) and (<ref>) for $0\leq \mu \leq\frac{1}{2}$ and $\frac{1}{2}\leq\mu \leq 1$, respectively. Now, we present the achievability proof for each regime of $\mu$.

$0\leq \mu \leq\frac{1}{2}:$

We first define $g(\ell):= \overline{F}_{L_2}(\ell)/\overline{F}_{L_1}(\ell)$ for each level $\ell\in [B]$, and sort all the $B$ levels of the channel in an non-decreasing order according to $g(\cdot)$. Therefore,
we have a one-to-one mapping  $\lambda :[B]\rightarrow [B]$ that sorts the level, and thus,

\begin{align*}
g(\lambda(1)) \leq g(\lambda(2)) \leq \cdots \leq g(\lambda(K-1)) \leq g(\lambda(K)).
\end{align*}

For notational simplicity, we define $\gamma_{\ell}: = g(\lambda(\ell))$ for every $\ell \in [B]$ and ${G(\w):=\w R_1(\w) + R_2(\w)}$ for any $\w \geq 1$, where $R_1(\w)$ and $R_2(\w)$ are defined in (<ref>).
In the next lemma, we show that $\gamma_m$ is a minimizer for the first minimization in (<ref>) for some $m \in [B]$ whose proof is presented in Appendix.

For some $m \in [B]$, we have

\begin{align}\label{eq:G-k}
\gamma_m (1-\mu)f^\s  + (1-2\mu)f^\s =  G(\gamma_m).
\end{align}

Note that we have

\begin{align*}
G(\gamma_{j+1}) - G(\gamma_{j}) & = \gamma_{j+1} R_1(\gamma_{j+1}) + R_2(\gamma_{j+1}) - \gamma_{j} R_1(\gamma_{j}) - R_2(\gamma_{j})\\
& = \gamma_{j+1} \left(R_1(\gamma_{j}) + \overline{F}_{L_1}(\lambda(j+1))\right) + R_2(\gamma_{j}) - \overline{F}_{L_2}(\lambda(j+1))- \gamma_{j} R_1(\gamma_{j}) - R_2(\gamma_{j})\\
& = \gamma_{j+1}\overline{F}_{L_1}(\lambda(j+1)) + (\gamma_{j+1}-\gamma_{j}) R_1(\gamma_{j}) - \overline{F}_{L_2}(\lambda(j+1)) = (\gamma_{j+1}-\gamma_{j}) R_1(\gamma_{j}),
\end{align*}

for every $j\in [B-1]$. Moreover, optimality of $\fs$ implies $ \gamma_{m+1} (1-\mu) \fs + (1-2\mu)\fs   \leq G(\gamma_{m+1})$, which together with (<ref>) implies

\begin{align}
(\gamma_{m+1}-\gamma_{m}) (1-\mu) \fs &\leq G(\gamma_{m+1}) - G(\gamma_{m})= (\gamma_{m+1}-\gamma_{m}) R_1(\gamma_{m}).
\label{eq:fp2-1}
\end{align}

Similarly, from $ \gamma_{m-1} (1-\mu) \fs + (1-2\mu)\fs  \leq G(\gamma_{m-1})$ and (<ref>) we get

\begin{align}
(\gamma_{m}-\gamma_{m-1}) (1-\mu) \fs &\geq G(\gamma_{m}) - G(\gamma_{m-1}) = (\gamma_{m}-\gamma_{m-1}) R_1(\gamma_{m-1}).
\label{eq:fp2-2}
\end{align}

From (<ref>) and (<ref>) we  conclude
$R_1(\gamma_{m-1})  \leq (1-\mu) \fs \leq  R_1(\gamma_{m})$, which implies

\begin{align}
(1-\mu)\fs &= R_1(\gamma_{m}) - \alpha \ov{F}_{L_1}(\lambda(m))= \sum_{\ell=1}^{m-1} \ov{F}_{L_1}(\lambda(\ell)) + (1-\alpha) \ov{F}_{L_1} (\lambda(m)),
\label{eq:1-mu}
\end{align}

for some $\alpha\in [0,1]$. Then, from $(1-2\mu) \fs \leq (1-\mu)\fs$, we can conclude existence of some $v\leq m$ and $\beta\in [0,1]$ such that

\begin{align}
(1-2\mu)\fs = \sum_{\ell=1}^{v-1} \ov{F}_{L_1}(\lambda(\ell)) + \beta \ov{F}_{L_1}(\lambda(v)),
\label{eq:alloc-p1}
\end{align}

Moreover, plugging (<ref>) into (<ref>) we get

\begin{align}
(1-2\mu)\fs &= G(\gamma_{m}) - \gamma_{m} R_1(\gamma_{m}) + \gamma_{m} \alpha \overline{F}_{L_1}(\lambda(m))\nonumber \\
&= R_2(\gamma_{m}) + \gamma_{m} \alpha \ov{F}_{L_1}(\lambda(m))\nonumber\\
& = R_2(\gamma_{m}) +  \alpha \ov{F}_{L_2}(\lambda(m))\nonumber\\
& = \sum_{\ell= m+1}^{B} \ov{F}_{L_2}(\lambda(\ell)) + \alpha \ov{F}_{L_2} (\lambda(m)).
\label{eq:alloc-p2}
\end{align}

We define the rate supported for User $k$ for multicasting the common message as

\begin{align*}
R^c_k := \sum_{\ell=v+1}^{m-1} \ov{F}_{L_k}(\lambda(\ell)) + (1- \alpha) \ov{F}_{L_k}(\lambda(m))+ (1-\beta) \ov{F}_{L_k}(\lambda(v)).
\end{align*}

From (<ref>) and (<ref>), we have

\begin{align*}
\mu \fs & = \sum_{\ell=1}^{m-1} \ov{F}_{L_1}(\lambda(\ell)) + (1-\alpha) \ov{F}_{L_1}(\lambda(m)) - \sum_{\ell=1}^{v-1} \ov{F}_{L_1}(\lambda(\ell)) - \beta \ov{F}_{L_1}(\lambda(v))\\
& = \sum_{\ell=v+1}^{m-1} \ov{F}_{L_1}(\lambda(\ell)) +(1- \alpha) \ov{F}_{L_1}(\lambda(m)) + (1-\beta) \ov{F}_{L_1}(\lambda(v)) =  R^c_1.
\end{align*}

The final step for the achievability proof is to show that ${R^c_2 \geq \mu \fs = R^c_1}$.
Note that

\begin{align*}
G(\gamma_v)  &=  \gamma_{v} \left[\sum_{\ell=1}^{v-1} \ov{F}_{L_1}(\lambda(\ell)) + \beta \ov{F}_{L_1}(\lambda(v)) \right]+ \gamma_{v} (1-\beta) \ov{F}_{L_1}(\lambda(v)) \\
&\phantom{=} +  \left[ \sum_{\ell=v+1}^{m-1} \ov{F}_{L_2}(\lambda(\ell)) + (1- \alpha) \ov{F}_{L_2}(\lambda(m)) \right]+ \left[\alpha \ov{F}_{L_2}(\lambda(m)) + \sum_{\ell=m+1}^{B} \ov{F}_{L_2}(\lambda(\ell))\right] \\
& \stackrel{\rm{(a)}}{=} \gamma_v (1-2\mu)\fs + \gamma_v(1-\beta) \ov{F}_{L_1}(\lambda(v)) +\left[ \sum_{\ell=v+1}^{m-1} \ov{F}_{L_2}(\lambda(\ell)) + (1- \alpha) \ov{F}_{L_2}(\lambda(m)) \right] + (1-2\mu)\fs \\
&\stackrel{\rm{(b)}}{=} (1+\gamma_{v})(1-2\mu)\fs + R_2^c,
\end{align*}

where $\rm{(a)}$ follows from (<ref>) and (<ref>) and $\rm{(b)}$ holds since $\gamma_{v}  \overline{F}_{L_1}(\lambda(v)) =  \overline{F}_{L_2}(\lambda(v))$.
Then recall that $\fs$ the minimum value obtained by (<ref>). We can distinguish the following two cases.

(i) $\gamma_{v} \geq 1$: In this case from the first term in (<ref>) we can write

\begin{align*}
\fs \leq \frac{\gamma_{v} R_1(\gamma_{v}) +  R_2(\gamma_{v})}{(1-2\mu) + \gamma_{v} (1-\mu)} = \frac{(1+\gamma_{v})(1-2\mu)\fs + R_2^c}{(1-2\mu) + \gamma_{v} (1-\mu)},
\end{align*}

which implies $R_2^c \geq \gamma_{v} \mu \fs \geq \mu \fs$.

(ii) $\gamma_{v} \leq 1$: Alternatively, from the second term in (<ref>) we have

\begin{align}
\fs \leq \frac{R_1(\gamma_{v}) + \frac{1}{\gamma_v} R_2(\gamma_v)}{(1-2\mu) + \frac{1}{\gamma_{v}} (1-\mu)}
\frac{\gamma_v R_1(\gamma_{v}) +  R_2(\gamma_v)}{\gamma_{v} (1-2\mu) +  (1-\mu)}
\frac{(1+\gamma_{v})(1-2\mu)\fs + R_2^c}{\gamma_{v}(1-2\mu) +  (1-\mu)},\nonumber
\end{align}

which implies $R_2^c \geq \mu \fs$.

$\frac{1}{2}\leq \mu \leq 1:$

We need to show that the first minimization in (<ref>) is achievable. Upon receiving the vector $\bd =(d_1,d_2)$, the transmitter needs to only multicast a common message $W_{d_1,2} \oplus W_{d_2,1}$ to both users over the  signal levels in $[B]$. The size of this common message is $\left(1-\mu\right)\fs$ for each channel use. Hence, the maximum achievable source rate is given the capacity of the channel of the weak user, User 1, which is

\begin{align*}
\fs = \frac{\sum_{\ell=1}^{B}\ov{F}_{L_1}(\ell)}{1-\mu}.
\end{align*}

This completes the proof of the theorem.

§ ACHIEVABILITY PROOF OF THEOREM <REF>

The achievability proof of Theorem <ref> is based on the achievable scheme in Section <ref>.

Consider a group of users $\cS\subseteq [K]$ with $|\cS| = t\!+\!1$. Since $L_K\geq_{\mathsf{st}}\cdots \geq_{\mathsf{st}} L_1$, the constrain in (<ref>) reduces to

\begin{align*}
\sum_{\ell=1}^\nB \overline{F}_{L_{\kw}}(\ell) y_{\ell,\cS}  \geq \frac{\bar{f}}{\binom{K}{t}},
\end{align*}

where $\kw := \min_{k\in \cS} k$.
Therefore, for every $k\in [K]$ we need only to satisfy

\begin{align}\label{eq:deg-LP}
\sum_{\ell=1}^\nB \overline{F}_{L_k}(\ell) y_{\ell,{\cT\cup \{k\}}}  \geq \frac{\bar{f}}{\binom{K}{t}},
\end{align}

for all $\cT \subseteq [K]\setminus [k]$ with $|\cT| = t$. Summing up (<ref>) over all $\cT$, we get

\begin{align*}
\sum_{\ell=1}^\nB \overline{F}_{L_k}(\ell) z_{\ell,k}  \geq \frac{\binom{K-k}{t}}{\binom{K}{t}} \bar{f},
\end{align*}

where $z_{\ell,k} := \sum_{\substack{\cT\subseteq [K]\setminus [k] \\|\cT|=t }} y_{\ell,{\cT\cup \{k\}}}$. Note that from (<ref>) we have

\begin{align*}
\sum_{k=1}^K z_{\ell,{k}}  = \sum_{k=1}^K \sum_{\substack{\cT\subseteq [K]\setminus [k]\\|\cT|=t }}  y_{\ell,{\cT\cup \{k\}}} = \sum_{\substack{\cS\subseteq [K]\\|\cS|=t+1 }}  y_{\ell,\cS} \leq 1, \qquad \forall \ell\in [\nB].
\end{align*}

Hence, the LP problem in (<ref>) reduces to

\begin{align}\label{eq:degraded-ach-f}
\begin{split}
& \max \ \bar{f}\\
& \textrm{s.t.} \quad \lp 1-\tcents_{[k]}\rp \bar{f} \leq  \sum_{\ell=1}^\nB \overline{F}_{L_{k}}(\ell) z_{\ell,{k}}, \quad  \forall k\in [K],\\
& \phantom{\textrm{s.t.}} \quad\sum_{k=1}^K z_{\ell,{k}} \leq 1, \quad \forall\ell\in [B],\\
& \phantom{\textrm{s.t.}} \quad z_{\ell,{k}}\geq 0, \quad  \forall k\in [K],\ \forall\ell\in [B].
\end{split}
\end{align}

where in the first constraint we used the fact $ \tcents_{[k]} = 1-\binom{K-k}{t}/\binom{K}{t}$. This completes the achievability proof of Theorem <ref>.

§ PROOF OF THEOREM <REF> AND PROPOSITION <REF>

In this section, we provide the proof of Theorem <ref> and Proposition <ref>. First, we present some auxiliary lemmas whose proofs are provided in Appendix.

§.§ Preliminary results

The proof of Theorem <ref> is built based on the result of [27], in which the rate region of an erasure $K$-user broadcast channel is characterized. We first need to enhance the channels to convert the network to a degraded broadcast channel. To this end, we will replace $L_k$, the channel of User $k$, by a stronger channel $\widetilde{L}_k$,  so that the channel of user $k$ statistically degrades that of user $k-1$, for $k=2,3,\dots, K$. More precisely, for a given weight vector ${\bfw = (\omega_1,\ldots,\omega_K) \in [0,\infty)^K}$ with sorted entries ${\w_1\geq \w_2\geq \cdots \geq \w_K}$, we define

\begin{equation}\label{eq:chnl_ench}
\overline{F}_{\widetilde{L}_{k}}(\ell):=\min\left[1,\max\left(\overline{F}_{L_{k}}(\ell),\frac{\omega_{{k-1}}}{\omega_{k}}\overline{F}_{\widetilde{L}_{{k-1}}}(\ell)\right)\right],\qquad \ell\in [B],\quad k\in \{2,3,\dots, K\},
\end{equation}

with an initialization given by $\overline{F}_{\widetilde{L}_{1}}(\ell) = \overline{F}_{{L}_{1}}(\ell)$,
for every $\ell \in [B]$.

The following lemma demonstrates some of the properties of the enhanced channel, which will be useful in the proof of Theorem <ref>.

The CCDF of $\wdt{L}_{k}$ providing in (<ref>) has the following properties

* If $\overline{F}_{\widetilde{L}_{k}}(\ell) =1$, then

\begin{align*}
\overline{F}_{\widetilde{L}_{u}}(\ell) =1,
\end{align*}

for every $ u\geq k$.

* If $\omega_{k} \overline{F}_{\widetilde{L}_{k}}(\ell)> \omega_{k-1}\overline{F}_{\widetilde{L}_{k-1}}(\ell)$, then

\begin{align*}
\w_k \overline{F}_{L_{k}}(\ell) = \w_k \overline{F}_{\wdt{L}_{k}}(\ell)  > \w_{k-1}\ov{F}_{\wdt{L}_{k-1}}(\ell) \geq \cdots \geq \w_{1}\ov{F}_{\wdt{L}_{1}}(\ell).
\end{align*}

* If $\omega_{k} \overline{F}_{\widetilde{L}_{k}}(\ell) < \omega_{k-1} \overline{F}_{\widetilde{L}_{k-1}}(\ell)$, then

\begin{align*}
\w_K \ov{F}_{\wdt{L}_K}(\ell) \leq \cdots \leq \w_k \ov{F}_{\wdt{L}_k}(\ell) < \w_{k-1} \ov{F}_{\wdt{L}_{k-1}}(\ell).
\end{align*}

* The maximum of the weighted returns satisfies

\begin{align*}
\max_k \w_k \ov{F}_{\wdt{L}_k}(\ell) = \max_k \omega_k \overline{F}_{{L}_{k}}(\ell),
\end{align*}

for every $\ell \in [B]$.

We can summarize the discussed properties in Lemma <ref> in the following corollary.

Let us denote $k^\s := \min \arg \max_k \w_k \ov{F}_{\wdt{L}_k}(\ell)$ and $u^\s := \max \arg \max_k \w_k \ov{F}_{\wdt{L}_k}(\ell)$ for any given $\ell \in[B]$. We decompose the set of users $[K]$ into the following non-overlapping subsets

\begin{align*}
[K] = \{1,\ldots,k^\s\!-\!1\} \cup \{k^\s,\ldots,u^\s\} \cup \{u^\s\!+\!1,\ldots, K\}.
\end{align*}

Then, we arrive at the below properties

* The sequence $\{\w_{k} \overline{F}_{L_{k}}(\ell)\}_{k=1}^{k^\s\!-\!1}$ is non-decreasing, i.e.,

\begin{align*}
\w_{k^\s} \overline{F}_{\wdt{L}_{k^\s}}(\ell)  > \w_{k^\s-1}\ov{F}_{\wdt{L}_{k^\s-1}}(\ell) \geq \cdots \geq \w_{1}\ov{F}_{\wdt{L}_{1}}(\ell).
\end{align*}

* The sequence $\{\w_{k} \overline{F}_{L_{k}}(\ell)\}_{k=k^\s}^{u^\s}$ satisfies

\begin{align*}
\w_{k^\s} \overline{F}_{L_{k^\s}}(\ell) = \w_{k^\s} \overline{F}_{\wdt{L}_{k^\s}}(\ell) = \cdots = \w_{u^\s} \overline{F}_{\wdt{L}_{u^\s}}(\ell).
\end{align*}

* The sequence $\{\w_{k} \overline{F}_{L_{k}}(\ell)\}_{k=u^\s\!+1}^{K}$ is non-increasing, i.e.,

\begin{align*}
\w_{u^\s} \ov{F}_{\wdt{L}_{u^\s}}(\ell) > \w_{u^\s\!+1} \ov{F}_{\wdt{L}_{u^\s\!+1}}(\ell) \geq \cdots \geq
\w_K \ov{F}_{\wdt{L}_K}(\ell).
\end{align*}

Using the discussed properties in Corollary <ref>, we visualize the behaviour of the weighted return $\w_k \ov{F}_{\wdt{L}_k}(\ell)$ in Figure <ref>.

The weighted returns $\w_k \ov{F}_{\wdt{L}_k}(\ell)$ for the enhanced deterministic broadcast channel.

In the next lemma, we provide an important property of the cache placement strategy.

For a given caching strategy and mutually independent files $W^{(n)}_1,\ldots,W^{(n)}_N$, we get

\begin{align}\label{eq:I-f}
I\lp W_i;C^{(n)}_\cS\rp \leq n\mu_{\cS}f,\quad \cS\subseteq[K].
\end{align}

Finally, we provide the extension of Lemma <ref> to the $K$-users system in the following result.

If a source rate $f(\cache,\bd)$ for a given caching strategy $\cache$ and a distinct request profile $\bd$ is achievable on a physically degraded broadcast channel, i.e.,

\[
X\leftrightarrow Y_{K}\leftrightarrow\cdots\leftrightarrow Y_{1},
\]

then $f(\cache,\bd)$ satisfies

\begin{align}
& f(\cache,\bd)\leq \frac{ I(U_{1};Y_{1})}{1-\mu_{1}}  ,\label{eq:lm:f_upper_1}\\
& f(\cache,\bd) \leq  \frac{ I(U_{k};Y_{k}|U_{k-1})}{1-\mu_{[k]}},\quad k\in[2:K-1]\label{eq:lm:f_upper_k}\\
& f(\cache,\bd)\leq  \frac{I(X;Y_{K}|U_{K-1})}{1-\mu_{[K]}},\label{eq:lm:f_upper_K}
\end{align}

for some random variables $(U_{1},U_{2},\ldots,U_{K-1})$ that form a Markov chain

\[
X\leftrightarrow U_{K-1}\leftrightarrow\cdots\leftrightarrow U_{1}.
\]

The proof of Lemma <ref> is presented in Appendix.

The global capacity of a broadcast channel  depends on the underlying transition probability  $\P(Y_1,\ldots,Y_K|X)$ only through its marginal conditional probabilities $\P(Y_1|X),\ldots,\P(Y_K|X)$. Therefore, the claim of Lemma <ref> also applies to stochastically degraded BCs.

Now, we are ready to present the proof of Theorem <ref>.

§.§ An upper-bound on the achievable source rate

The main steps of the proof of Theorem <ref> are twofold:
We first enhance and replace the arbitrary $L_1,\ldots,L_K$ by the degraded $\wdt{L}_1,\ldots,\wdt{L}_K$ and then by exploiting Lemma <ref>, we derive an upper-bound on the achievable source rate.

We first note that for arbitrary channels $L_1,\ldots,L_K$, the $K$-DTVBC is not degraded. Hence, we recursively enhance the channel of the users to obtain a set of degraded channels. In this regard, we consider a weight vector ${\bfw = (\omega_1,\ldots,\omega_K) \in [0,\infty)^K}$ with sorted entries ${\w_1\geq \w_2\geq \cdots \geq \w_K}$. We define the enhanced channel output of user $k$ as $\widetilde{Y}_{k}=D^{\nB-\widetilde{L}_{k}}X=X(1:\widetilde{L}_{k})$ where $\widetilde{L}_{k}$ is a random variable drawn according to $\overline{F}_{\widetilde{L}_{k}}$, given by (<ref>), independent of all other users. Since $\w_{k-1} \geq \w_{k}$, from (<ref>) we have $\overline{F}_{\widetilde{L}_{k}}(\ell) \geq \overline{F}_{\widetilde{L}_{k-1}}(\ell)$. Thus, from <cit.>, we can conclude that the enhanced broadcast channel is (stochastically) degraded.
Now, we can use  Lemma <ref> for the degraded channel obtained by the enhancement procedure. Let $U_1,\ldots,U_{K-1}$ be the random variables satisfying the claim of the lemma, and form a Markov chain $X\leftrightarrow U_{K-1}\leftrightarrow\cdots\leftrightarrow U_{1}$.
Then, given the fact that CSI is available at the receivers, the terms in Lemma <ref> for the deterministic channel of interest will be simplified to

\begin{align}\label{eq:I_bnd}
I(U_{k};\widetilde{Y}_{k},\widetilde{L}_{k}| U_{{k-1}})
& = I(U_{k};X(1 : \widetilde{L}_{k}),\widetilde{L}_{k}|U_{{k-1}})\nonumber\\
&= I(U_{k}; \widetilde{L}_{k}|U_{{k-1}})+ I(U_{k};X(1 : \widetilde{L}_{k}),|U_{{k-1}}, \widetilde{L}_{k})\nonumber\\
&\stackrel{\rm (a)}{=}  \sum_{j=1}^\nB  \P_{\widetilde{L}_{k}}\!(j)  I(U_{k};X(1:j)|U_{{k-1}}, \widetilde{L}_{k} = j)\nonumber\\
&= \sum_{j=1}^\nB \left[ \P_{\widetilde{L}_{k}}\!(j) \sum_{\ell=1}^j I(U_{k};X(\ell) | X(1:\ell-1), U_{{k-1}})   \right]\nonumber\\
&= \sum_{\ell=1}^\nB \left[ I\left(U_{k};X(\ell) | X(1 :\ell-1), U_{{k-1}}\right)  \cdot \sum_{j=\ell}^\nB  \P_{\widetilde{L}_{k}}\!(j)\right]\nonumber\\
&= \sum\nolimits_{\ell=1}^\nB \overline{F}_{\widetilde{L}_{k}}(\ell) I(U_{k};X(\ell) | X(1\!:\!\ell\!-\!1)|U_{{k-1}})\nonumber\\
&=  \sum_{\ell=1}^\nB \overline{F}_{\widetilde{L}_{k}}\!(\ell) \left[H\left(X(\ell) | X(1\!:\! \ell\!-\!1),U_{{k-)}}\hspace{-1pt}\right)- H\left(X(\ell)|X(1\!:\! \ell\!-\!1) ,U_{{k-1}},U_{k}\right) \right]\nonumber\\
&\stackrel{\rm(b)}{=}  \sum_{\ell=1}^\nB \overline{F}_{\widetilde{L}_{k}}\!(\ell) \left[H\hspace{-1pt}(\hspace{-1pt}X(\ell) | X(1\!:\! \ell\!-\!1\hspace{-1pt}),U_{{k-1}}\hspace{-1pt})\!-\! H\hspace{-1pt}(\hspace{-1pt}X(\ell)|X(1\!:\! \ell\!-\!1)\hspace{-1pt},U_{k}) \right]\nonumber\\
& =  \sum_{\ell=1}^\nB \overline{F}_{\widetilde{L}_{k}}(\ell) Q_{\ell,{k}},
\end{align}

where $\rm{(a)}$ follows from the fact that $\widetilde{L}_{k}$ is independent from $U_{k-1}$ and $U_k$, $\rm{(b)}$ holds due to the Markov chain $U_{{k-1}}\leftrightarrow U_{k}\leftrightarrow X(\ell)$ and $Q_{\ell,{k}} := H\left(\hspace{-1pt}X(\ell) | X(1\!:\! \ell\!-\!1\hspace{-1pt}),U_{{k-1}}\right)- H\left(\hspace{-1pt}X(\ell)|X(1\!\!:\! \ell\!-\!1)\hspace{-1pt},U_{k}\right)$. Therefore, from Lemma <ref> we have

\begin{align}\label{eq:lm:Kuser-deg-BC:simplified}
f(\cache,\bd) \cdot \lp 1-\mu_{[k]} \rp \leq I(U_{k}; \widetilde{Y}_{k}, \widetilde{L}_{k} | U_{k-1})=\sum_{\ell=1}^\nB \overline{F}_{\widetilde{L}_{k}}(\ell) Q_{\ell,{k}},
\end{align}

for $k\in [K]$.
Taking a weighted sum of (<ref>) with coefficients $\{\w_k\}$, we arrive at

\begin{align}\label{eq:thm2_0}
\omega_{k}\lp 1-\mu_{[k]} \rp
\leq \sum_{k=1}^{K}\sum_{\ell=1}^{\nB}\w_{k}\overline{F}_{\widetilde{L}_{k}}(\ell)\cdot Q_{\ell,{k}} = \sum_{\ell=1}^{\nB} \sum_{k=1}^{K}\w_{k}\overline{F}_{\widetilde{L}_{k}}(\ell)\cdot Q_{\ell,{k}}.
\end{align}

Note that for each $\ell\in[B]$ we have

\begin{align}\label{eq:sum_Q}
\sum_{k=1}^K Q_{\ell,{k}} &= \sum_{k=1}^K \left[H\left(\hspace{-1pt}X(\ell) | X(1\!:\! \ell\!-\!1\hspace{-1pt}),U_{{k-1}}\right)- H\left(\hspace{-1pt}X(\ell)|X(1\!\!:\! \ell\!-\!1)\hspace{-1pt},U_{k}\right)\right] \nonumber\\
&= H\left(\hspace{-1pt}X(\ell) | X(1\!:\! \ell\!-\!1\hspace{-1pt}),U_{{0}}\right)- H\left(\hspace{-1pt}X(\ell)|X(1\!\!:\! \ell\!-\!1)\hspace{-1pt},U_{K}\right)\nonumber\\
&\leq H(X(\ell)) \leq 1,
\end{align}

where we define $U_{0} = \varnothing$ to be a dummy variable and $U_{K}=X$.
Therefore, using (<ref>) for each $\ell\in[B]$ we can write

\begin{align}\label{eq:thm2:1}
\sum_{k=1}^{K} \w_{k}\overline{F}_{\widetilde{L}_{k}}(\ell) \cdot Q_{\ell,k} \leq \left(\max_{k} \w_{k}\overline{F}_{\widetilde{L}_{k}}(\ell)\right) \cdot \sum_{k=1}^K Q_{\ell,k}\leq \max_{k} \w_{k}\overline{F}_{\widetilde{L}_{k}}(\ell).
\end{align}

Thus, plugging (<ref>) into (<ref>) we get

\begin{align}\label{eq:f_bnd_w}
\omega_{k}\sum_{k=1}^K \!\w_{k}\! \lp 1- \mu_{[k]}\rp\leq
\max_{k} \sum_{\ell=1}^\nB \max_{k}  \w_{k}\overline{F}_{\widetilde{L}_{k}}(\ell)
& = \sum_{\ell=1}^\nB \max_{k}  \w_{k}\overline{F}_{L_{k}}(\ell),
\end{align}

where the last equality follows from Lemma <ref>-(iv).
Dividing both sides of (<ref>) by $\sum_{k=1}^K \!\w_{k}\! \lp 1- \mu_{[k]}\rp$, we arrive at

\begin{align}\label{eq:f_idnty_per}
f(\cache,\bd) \leq \frac{\sum_{\ell=1}^\nB \max_{k}  \w_{k}\overline{F}_{L_{k}}(\ell)}{\sum_{k=1}^K \!\w_{k}\! \lp 1- \mu_{[k]}\rp}.
\end{align}

Now we return to examine the upper bound for an arbitrary weight vector ${\bfw=(\w_1,\ldots,\w_k) \in [0,\infty)^K}$. Let $\pi$ be a permutation that  sorts the vector $\bfw$ in a non-increasing order, i.e., ${\w_{\pi(1)}\!\geq\! \cdots \!\geq\! \w_{\pi(K)}}$. Now, applying the enhancement in (<ref>), we arrive at a set of (statistically) degraded channels,

\[
X\leftrightarrow \wdt{Y}_{\pi(K)}\leftrightarrow \wdt{Y}_{\pi(K-1)}\leftrightarrow \cdots
\leftrightarrow \wdt{Y}_{\pi(2)}
\leftrightarrow \wdt{Y}_{\pi(1)}.
\]

Repeating the argument above, we arrive at (<ref>) for a permuted version of the variables, that is,

\begin{align}\label{eq:fstar_v_1}
f(\cache,\bd) \leq \frac{\sum_{\ell=1}^\nB \max_{k}  \w_{\pi(k)}\overline{F}_{L_{\pi(k)}}(\ell)}{\sum_{k=1}^{K}
\w_{\pi(k)}\! \lp 1 - \mu_{\pi([k])}\rp}.
\end{align}

By minimizing the right hand side of (<ref>) over all non-negative vectors $\bfw$, we get the desired bound, i.e.,

\begin{align}\label{eq:fstar_v_2}
f(\cache,\bd) \leq \fs(\cache,\bd) = \min_{\bfw \geq 0} \frac{\sum_{\ell=1}^\nB \max_{k}  \w_{\pi(k)}\overline{F}_{L_{\pi(k)}}(\ell)}{\sum_{k=1}^{K}
\w_{\pi(k)}\! \lp 1 - \mu_{\pi([k])}\rp}.
\end{align}

This completes the proof of the theorem.

§.§ An LP Representation

The main step in the proof of Proposition <ref> is to define a new weight vector $\bfs$, which allows us to transform the upper-bound in (<ref>) into a linear form.

Using this fact that ${\w_{\pi(1)}\! \geq \cdots \geq \!\w_{\pi(K)} \geq 0}$ and starting from (<ref>), we can write

\begin{align}\label{eq:f_LP_1}
\fs(\cache,\bd) & =\min_{\bfw \geq 0} \frac{\sum_{\ell=1}^\nB \max_{k}  \w_{\pi(k)}\overline{F}_{L_{\pi(k)}}(\ell)}{\sum_{k=1}^{K} \w_{\pi(k)}\! \lp 1 - \mu_{\pi([k])}\rp}\nonumber\\
& = \min_{\pi \in \Pi} \min_{\bfw\in \Omega_\pi} \frac{\sum_{\ell=1}^\nB \max_{k}  \w_{\pi(k)}\overline{F}_{L_{\pi(k)}}(\ell)}{\sum_{k=1}^{K} \w_{\pi(k)}\! \lp 1 - \mu_{\pi([k])}\rp},
\end{align}

where $\Omega_\pi:= \left\{\bfw: \w_{\pi(1)} \geq \cdots \geq \w_{\pi(K)}\geq 0 \right\}$.
Let us define ${\sigma_k := \w_{\pi(k)} \lp 1 - \mu_{\pi([k])}\rp/\sum_{u=1}^K \w_{\pi(u)} \lp 1 - \mu_{\pi([u])}\rp}$ for every $k \in [K]$. We note that the vector $\bfs:=(\sigma_1,\ldots,\sigma_K)$ satisfies the following conditions

* Since $\w_{\pi(k)} \geq 0$ and $\mu_{\pi([k])}\leq 1$ for every $k\in [K]$, we have $\sigma_k \geq 0$ for every $k\in[K]$;

* We have

\begin{align*}
\sum_{k=1}^{K} \sigma_k = \sum_{k=1}^{K} \frac{\w_{\pi(k)} \lp 1 - \mu_{\pi([k])}\rp}{\sum_{u=1}^K \w_{\pi(u)} \lp 1 - \mu_{\pi([u])}\rp } = 1;
\end{align*}

* Using $\w_{\pi(k-1)} \geq \w_{\pi(k)}$, we get

\begin{align*}
\frac{\sigma_{k-1}}{1 - \mu_{\pi([k-1]),}} \geq \frac{\sigma_{k}}{1 - \mu_{\pi([k])}} ,
\end{align*}

or equivalently,

\begin{align*}
\sigma_{k-1}\cdot \lp 1 - \mu_{\pi([k])}\rp \geq \sigma_k\cdot \lp 1 - \mu_{\pi([k-1])}\rp,
\end{align*}

for every $k \in \{2,\cdots, K \}$.

Having these three properties, we define

\begin{align}\label{eq:Si}
\Sigma_{\pi}: = \left\{ (\sigma_{1},\ldots,\sigma_{K}): \sigma_k \geq 0,\ \sum_{k=1}^{K} \sigma_k = 1,\ \sigma_{k-1} \lp 1 - \mu_{\pi([k])}\rp \geq \sigma_k \lp 1 - \mu_{\pi([k-1])}\rp \right\}.
\end{align}

Note that for every vector $\bfw\in \Omega_{\pi}$, there is a vector $\bfs \in \Sigma_{\pi}$ and vice versa. This along with (<ref>) leads us to

\begin{align}\label{eq:f_LP_2}
\fs(\cache,\bd) & = \min_{\pi \in \Pi} \min_{\bfw\in \Omega_\pi} \sum_{\ell=1}^B \max_k \frac{\w_{\pi(k)} \lp 1 - \mu_{\pi([k])}\rp}{\sum_{u=1}^K \w_{\pi(u)} \lp 1 - \mu_{\pi([u])}\rp}\frac{\ov{F}_{L_{\pi(k)}}(\ell)}{ 1 - \mu_{\pi([k])}}
\nonumber\\
& = \min_{\pi \in \Pi} \min_{\bfs\in \Sigma_{\pi}} \sum_{\ell=1}^B \max_k \sigma_k \frac{\ov{F}_{L_{\pi(k)}}(\ell)}{ 1 - \mu_{\pi([k])}}.
\end{align}

Let us consider each summand in (<ref>). For a given $\pi\in\Pi$ and $\bfs\in \Sigma_\pi$, the $\ell$-th term in the summation is

\begin{align}\label{eq:op-theta-1}
\max_k \sigma_k \frac{\ov{F}_{L_{\pi(k)}}(\ell)}{ 1 - \mu_{\pi([k])}} = \min \left\{\theta_\ell : \theta_\ell \geq \sigma_k \frac{\ov{F}_{L_{\pi(k)}}(\ell)}{1 - \mu_{\pi([k])}}, k\in[K] \right\}.
\end{align}

Note that the sum of the minimum of distinct variables $\{\theta_{\ell}\}_{\ell=1}^B$ is the minimum of a sum of them, i.e.,

\begin{align}\label{eq:op-theta-2}
\min_{\bft \in \Theta_{\pi}} \sum_{\ell=1}^B \theta_{\ell} = \sum_{\ell=1}^B \min \left\{\theta_\ell : \theta_\ell \geq \sigma_k \frac{\ov{F}_{L_{\pi(k)}}(\ell)}{1 - \mu_{\pi([k])}},\ k\in[K] \right\},
\end{align}

\begin{align}\label{eq:Theta}
\Theta_{\pi} := \left\{\bft=(\theta_1,\dots, \theta_B): \theta_\ell \geq \sigma_k\frac{\ov{F}_{L_{\pi(k)}}(\ell)}{1 - \mu_{\pi([k])}}, k\in[K]\right\}.
\end{align}

Plugging (<ref>) into (<ref>), we arrive at

\begin{align}\label{eq:op-theta-3}
\sum_{\ell=1}^B \max_k \sigma_k \frac{\ov{F}_{L_{\pi(k)}}(\ell)}{1 - \mu_{\pi([k])}} = \min_{\bft \in \Theta_{\pi}} \sum_{\ell=1}^B \theta_{\ell}.
\end{align}

From (<ref>), (<ref>), we get

\begin{align}\label{eq:f_LP_3}
\fs(\cache,\bd) = \min_{\pi \in \Pi}\min_{\bfs\in \Sigma_{\pi}, \bft \in \Theta_{\pi}} \sum_{\ell=1}^B \theta_{\ell}.
\end{align}

Let $\bx := [\bfs,\bft]^T$. Hence, the optimization problem  in (<ref>) with constraints (<ref>) and (<ref>) can be written in the matrix format that is given by

\begin{align*}
\fs(\cache,\bd) =\ & \min_{\pi \in \Pi} \min_{\bx \in \mathbb{R}^{K\!+\!B}} \ [\zeros_{K},\ones_{ B }]^T \bx,\\
& \textrm{s.t.} \ \bA_{\pi} \bx \leq \zeros,\nonumber\\
&\phantom{\textrm{s.t.}} \ \bb \bx = \ones,\nonumber\\
&\phantom{\textrm{s.t.}}\ -\bx \leq \zeros\nonumber,
\end{align*}

where $\bA_{\pi}$ and $\bb$ are defined in (<ref>) and (<ref>), respectively. This completes the proof of the proposition.

§ CONVERSE PROOF OF THEOREM <REF>

The converse proof of Theorem <ref> is derived directly from the proof of Theorem <ref> where no channel enhancement is required, i.e., $\wdt{L}_k = L_k$ for every $k\in [K]$.
Since $L_K\geq_{\mathsf{st}}\cdots \geq_{\mathsf{st}} L_1$ the $K$-DTVBC is degraded, we can repeat the steps (<ref>) in through (<ref>) with no further channel enhancement, i.e., $\ov{F}_{\wdt{L}_k}(\ell) = \ov{F}_{L_k}(\ell)$ for every $k\in [K]$ and $\ell\in [B]$. Hence, for the cache placement strategy $\cent$ and its caching tuple $\tcent$ we can write

\begin{align}\label{eq:deg_f_0}
f(\cache,\bd) \cdot \lp 1 - \tcents_{[k]}\rp \leq \sum_{\ell=1}^\nB \overline{F}_{L_{k}}(\ell) Q_{\ell,{k}}, \quad \forall k\in [K],
\end{align}

where $Q_{\ell,{k}} = H\left(X(\ell) \md   X(1\!:\! \ell\!-\!1),U_{{k-1}}\right)- H\left(X(\ell)\md  X(1\!\!:\! \ell\!-\!1),U_{k}\right)$ for the Markov chain $U_{{k-1}}\leftrightarrow U_{k}\leftrightarrow X(\ell)$. It is easy to verify that $Q_{\ell,{k}} \geq 0$. Moreover, from (<ref>), we have

\begin{align}\label{eq:const_degraded}
\sum_{k=1}^K Q_{\ell,{k}} \leq 1, \quad \forall \ell\in [B].
\end{align}

From (<ref>) and (<ref>), we can write

\begin{align}
\begin{split}\label{eq:degraded-conv-f}
f(\cache,\bd) \leq \ & \max \ \bar{f} \\
& \textrm{s.t.} \quad \bar{f}\cdot \lp 1 - \tcents_{[k]}\rp \leq \sum_{\ell=1}^\nB \overline{F}_{L_{k}}(\ell) Q_{\ell,{k}}, \quad \forall k\in [K],\\
&\phantom{\textrm{s.t.}\quad} \sum_{k=1}^K Q_{\ell,{k}} \leq 1, \quad \forall\ell\in [B].
\end{split}
\end{align}

Noting the LP problems in (<ref>) and (<ref>) are equivalent, we arrive at the claim of Theorem <ref>. This completes the proof of the theorem.

§ CONCLUSION

In this work, we studied a $K$-user coded-caching problem in a joint source-channel coding framework by providing each user a cache. The transmitter has a certain rate for all files per channel use, and a fraction of the bits/symbols are available in each user's cache. After this, each user requests a file from the database where the transmitter needs to satisfy users' demands over the $K$-DTVBC. The receivers have only access to the channel state information. We characterized the maximum achievable source rate for the $2$-DTVBC and the degraded $K$-DTVBC. Then, we provided an upper bound for the source rate with any caching strategy $\cache$. Finally, we presented an achievable scheme with the LP formulation to show that the upper bound is not a sharp characterization.

Several avenues are left for future research, including closing the gap between the achievable and optimum rates and studying the similar coded-caching problem over the Gaussian fading BC with (un-)coded cache placement schemes.

§ APPENDIX: PROOF OF LEMMAS

In this section, we provide the proofs of lemmas. Note that we provide the proof of Lemma <ref> after the proof of Lemma <ref>.

We first recall $\gamma_{\ell} = g(\lambda(\ell)) = \ov{F}_{L_2}(\lambda(\ell))/\ov{F}_{L_1}(\lambda(\ell))$ where $g(\lambda(\ell)) \leq g(\lambda(\ell+1))$ for any $\ell \in [B\!-\!1]$, or equivalently

\begin{align*}
\frac{\ov{F}_{L_2}(\lambda(1))}{\ov{F}_{L_1}(\lambda(1))}\leq \cdots \leq \frac{\ov{F}_{L_2}(\lambda(s))}{\ov{F}_{L_1}(\lambda(s))} \leq \w <\frac{\ov{F}_{L_2}(\lambda(s\!+\!1))}{\ov{F}_{L_1}(\lambda(s\!+\!1))} \leq \cdots \leq \frac{\ov{F}_{L_2}(\lambda(B))}{\ov{F}_{L_1}(\lambda(B))},
\end{align*}

for any $\w\in [\gamma_{s},\gamma_{s+1})$ and $s\in [B\!-\!1]$. Moreover, we get

\begin{align*}
&\cL_1 (\w) = \{\ell: \w \ov{F}_{L_1}(\ell) \geq \ov{F}_{L_2}(\ell) \} = \{\lambda(1),\lambda(2),\ldots,\lambda(s) \},\\
&\cL_2 (\w) = \{\ell: \w \ov{F}_{L_1}(\ell) < \ov{F}_{L_2}(\ell) \} = \{\lambda(s\!+\!1),\lambda(s\!+\!2),\ldots,\lambda(B) \},
\end{align*}

which implies $\cL_1 (\w)$ and $\cL_2 (\w)$ remain constant over the interval $[\gamma_{s},\gamma_{s+1})$. Note that for any $\w\geq 1$ there exists some $s\in [B-1]$ such that $ \gamma_s \leq \w < \gamma_{s+1}$. Now, let us consider $1\leq\gamma_{s}\leq\w^\s\!\leq \gamma_{s+1}$ as a minimizer of the first minimization in (<ref>) for some $s\in [B-1]$. Since $\cL_1 (\w)$ and $\cL_2 (\w)$ remain constant over the interval $[\gamma_{s},\gamma_{s+1})$, we can denote $R_1(\w)$ and $ R_2(\w)$ by constants $P$ and $Q$, respectively. Therefore, from the first minimization in (<ref>) we get

\begin{align*}
\fs & = \min_{\w \in [\gamma_{s},\gamma_{s+1})} \frac{\w R_1(\w) + R_2(\w)}{\w(1-\mu)+(1-2\mu)}\\
& = \min_{\w \in [\gamma_{s},\gamma_{s+1})} \frac{\w P + Q}{\w(1-\mu) + 1-2\mu}.
\end{align*}

Next, we consider the function $h(\w) := \frac{\w P + Q}{\w(1-\mu) + 1-2\mu}$ over the interval $[\gamma_{s},\gamma_{s+1})$ in two separate cases:

(i) if $P(1-2\mu)\neq Q(1-\mu)$, then $h(\w)$ is a monotonic function, and hence we either have ${ \w^\s=\gamma_{s}}$ or ${\w^\s=\gamma_{s+1}}$ implying either $m=s$ or $m = s\!+\!1$,

(ii) if $P(1-2\mu) =  Q(1-\mu)$, thus $h(\w)$ is constant indicating ${h(\gamma_{s}) = h(\w^\s) = h(\gamma_{s+1})}$. So, we can either pick $m=s$ or $m = s\!+\!1$. This completes the proof of the lemma.

In order to prove (i), we show that  $\ov{F}_{\wdt{L}_{k}}(\ell)=1$ implies $\ov{F}_{\wdt{L}_{k+1}}(\ell)=1$.  From (<ref>), we have

\begin{align*}
\overline{F}_{\widetilde{L}_{k+1}}(\ell)&=\min\left[1,\max\left(\overline{F}_{L_{k+1}}(\ell),\frac{\w_k}{\omega_{k+1}}\overline{F}_{\widetilde{L}_{{k}}}(\ell)\right)\right]\\
& =
\min\left[1,\max\left(\overline{F}_{L_{k+1}}(\ell),\frac{\omega_{{k}}}{\omega_{k+1}}\right)\right]\\
& \stackrel{\rm (a)}{=} \min\left[1,\frac{\omega_{{k}}}{\omega_{k+1}}\right] \stackrel{\rm (b)}{=}1,
\end{align*}

where $\rm(a)$ and $\rm (b)$ hold because $\ov{F}_{L_{k+1}}(\ell)\leq 1\leq \frac{\omega_{k}}{\omega_{k+1}}$, for a non-increasing sequence $\omega_1\geq \omega_2 \geq \cdots \geq \omega_K$.
This implies that $\ov{F}_{\wdt{L}_{u}}(\ell)=1$ for every $u\geq k$.

Next, in order to prove (ii), we consider two cases, namely, (ii-a)
$\w_{k} \ov{F}_{L_{k}}(\ell) <  \w_{k-1}\ov{F}_{\wdt{L}_{k-1}}(\ell)$ and (ii-b) $\w_{k} \ov{F}_{L_{k}}(\ell)\geq  \w_{k-1}\ov{F}_{\wdt{L}_{k-1}}(\ell)$. Under case (ii-a), we have

\begin{align*}
\overline{F}_{\widetilde{L}_{k}}(\ell)  &= \min\left[1,\max\left(\overline{F}_{L_{k}}(\ell),\frac{\omega_{{k-1}}}{\omega_{k}}\overline{F}_{\widetilde{L}_{{k-1}}}(\ell)\right)\right]\\
&\leq \max\left(\overline{F}_{L_{k}}(\ell),\frac{\omega_{{k-1}}}{\omega_{k}}\overline{F}_{\widetilde{L}_{{k-1}}}(\ell)\right) =  \frac{\w_{k-1}}{\w_{k}}\ov{F}_{\wdt{L}_{k-1}}(\ell),
\end{align*}

which implies $\w_k \overline{F}_{\widetilde{L}_{k}}(\ell) \leq  \w_{k-1}\overline{F}_{\widetilde{L}_{k-1}}(\ell)$ contradicting with the assumption in (ii). Hence, we arrive at (ii-b). This together with (<ref>) leads to

\begin{align*}
\overline{F}_{\widetilde{L}_{k}}(\ell)&=\min\left[1,\max\left(\overline{F}_{L_{k}}(\ell),\frac{\omega_{{k-1}}}{\w_k}\overline{F}_{\widetilde{L}_{{k-1}}}(\ell)\right)\right]\\
& = \min \left [1, \ov{F}_{L_{k}}(\ell)\right] =  \ov{F}_{L_{k}}(\ell),
\end{align*}

where the last equality follows from $\ov{F}_{L_{k}}(\ell)\leq 1$. Now we prove the second claim of part (ii). We consider two cases, namely (ii-c) $\ov{F}_{\wdt{L}_{u}}(\ell) = 1$ for some $u<k$ and (ii-d) $\ov{F}_{\wdt{L}_{u}}(\ell) < 1$ for every $u<k$. Under case (ii-c), from part (i), we get

\begin{align*}
\ov{F}_{\wdt{L}_u}(\ell)  =\cdots= \ov{F}_{\wdt{L}_{k-1}}(\ell) =\ov{F}_{\wdt{L}_{k}}(\ell)=1.
\end{align*}

This together with $\w_{k-1}\geq \w_{k}$ arrive at
$\w_{k-1}\ov{F}_{\wdt{L}_{k-1}}(\ell)\geq \w_{k}\ov{F}_{\wdt{L}_{k}}(\ell)$ which contradicts with the assumption in (ii). Hence, we have $\overline{F}_{\widetilde{L}_{u}}(\ell)<1$ for every $u<k$. Using this fact, we get

\begin{align*}
\ov{F}_{\wdt{L}_{u}}(\ell) &= \min\left[1,\max\left(\overline{F}_{L_{u}}(\ell),\frac{\omega_{{u-1}}}{\omega_{u}}\overline{F}_{\widetilde{L}_{{u-1}}}(\ell)\right)\right]\nonumber\\
& = \max \left(\ov{F}_{L_{u}}(\ell), \frac{\w_{u-1}}{\w_{u}}\ov{F}_{\wdt{L}_{u-1}}(\ell)\right),
\end{align*}

which results in $\w_{u}\ov{F}_{\wdt{L}_{u}}(\ell) \geq \w_{u-1}\ov{F}_{\wdt{L}_{u-1}}(\ell)$ for every $u<k$, or equivalently

\begin{align}\label{eq:lm_ii}
\w_{k}\ov{F}_{\wdt{L}_{k}}(\ell)  > \w_{k-1}\ov{F}_{\wdt{L}_{k-1}}(\ell) \geq \w_{k-2}\ov{F}_{\wdt{L}_{k-2}}(\ell)\geq \cdots \geq \w_{1}\ov{F}_{\wdt{L}_{1}}(\ell).
\end{align}

Plugging $\w_k \overline{F}_{L_{k}}(\ell) = \w_k \overline{F}_{\wdt{L}_{k}}(\ell)$ into (<ref>) completes the proof of (ii).

(iii) From (<ref>), we consider two separate cases, namely (iii-a) ${\ov{F}_{\wdt{L}_{k}}(\ell) = \max \left(\ov{F}_{L_{k}}(\ell), \frac{\w_{k-1}}{\w_{k}}\ov{F}_{\wdt{L}_{k-1}}(\ell)\right)}$ and (iii-b) ${\ov{F}_{\wdt{L}_{k}}(\ell) = 1}$. Under case (iii-a), we get

\begin{align*}
\w_{k}\ov{F}_{\wdt{L}_{k}}(\ell) \geq \w_{k-1} \ov{F}_{\wdt{L}_{k-1}}(\ell),
\end{align*}

which contradicts the assumption in (iii).
Hence, ${\ov{F}_{\wdt{L}_{k}}(\ell)=1}$. From part (i) of the lemma, we get

\begin{align*}
\ov{F}_{\wdt{L}_{u}}(\ell)=1, \quad u \geq k.
\end{align*}

This along with $\w_{1}\geq \cdots \geq \w_K$ leads to

\begin{align*}
\w_K \ov{F}_{\wdt{L}_K}(\ell) \leq \cdots \leq \w_k \ov{F}_{\wdt{L}_k}(\ell) < \w_{k-1} \ov{F}_{\wdt{L}_{k-1}}(\ell).
\end{align*}

(iv) Let us denote $s^\s:=\max \left\{j:  \w_{j+1}\ov{F}_{\wdt{L}_{j+1}}(\ell) \!<\! \w_{j}\ov{F}_{\wdt{L}_{j}}(\ell)\right\}$ for a given $\ell \in [B]$. In the following, we show that

\[ \w_{s^\s}\ov{F}_{\wdt{L}_{s^\s}}(\ell)= \max_k \w_{k}\ov{F}_{\wdt{L}_{k}}(\ell).\]

Since $\w_{s^\s}\ov{F}_{\wdt{L}_{s^\s}}(\ell) > \w_{s^\s+1} \ov{F}_{\wdt{L}_{s^\s+1}}(\ell)$, from part (iii) of the lemma we arrive at

\begin{align}\label{eq:lm_iv_0}
\w_K\ov{F}_{\wdt{L}_{K}}(\ell) \leq \cdots \leq \w_{s^\s+1} \ov{F}_{\wdt{L}_{s^\s+1}}(\ell) < \w_{s^\s}\ov{F}_{\wdt{L}_{s^\s}}(\ell).
\end{align}

Note that for some $u<s^\s$ we have

\begin{align}\label{eq:F_u_s}
\w_{u}\ov{F}_{\wdt{L}_{u}}(\ell)\!<\!\w_{u+1}\ov{F}_{\wdt{L}_{u+1}}(\ell) \!=\! \cdots \!=\! \w_{s^\s}\ov{F}_{\wdt{L}_{s^\s}}(\ell).
\end{align}

Since ${\w_{u}\ov{F}_{\wdt{L}_{u}}(\ell) < \w_{u+1} \ov{F}_{\wdt{L}_{u+1}}(\ell)}$, by using part (ii) of the lemma, we have

\begin{align}\label{eq:ss_2}
w_{u+1} \ov{F}_{\wdt{L}_{u+1}}(\ell)> \w_{u}\ov{F}_{\wdt{L}_{u}}(\ell)  \geq \w_{u\!-\!1}\ov{F}_{\wdt{L}_{u\!-\!1}}(\ell)\geq \cdots \geq \w_{1}\ov{F}_{\wdt{L}_{1}}(\ell),
\end{align}

and $\w_{u+1} \ov{F}_{L_{u+1}}(\ell) = \w_{u+1} \ov{F}_{\wdt{L}_{u+1}}(\ell)$. Combing (<ref>), (<ref>), and (<ref>), we get

\begin{align*}
\w_{s^\s}\ov{F}_{\wdt{L}_{s^\s}}(\ell)= \max_k \w_{k}\ov{F}_{\wdt{L}_{k}}(\ell).
\end{align*}

Using $\w_{s^\s}\ov{F}_{\wdt{L}_{s^\s}}(\ell) = \w_{u+1} \ov{F}_{\wdt{L}_{u+1}}(\ell)$ and $\w_{u+1} \ov{F}_{L_{u+1}}(\ell) = \w_{u+1} \ov{F}_{\wdt{L}_{u+1}}(\ell)$, we arrive at

\begin{align}
\w_{u+1} \ov{F}_{L_{u+1}}(\ell) = \w_{s^\s}\ov{F}_{\wdt{L}_{s^\s}}(\ell)= \max_k \w_{k}\ov{F}_{\wdt{L}_{k}}(\ell).
\end{align}

Note that $\w_{u+1} \ov{F}_{L_{u+1}}(\ell)  \leq \max_k \w_k \ov{F}_{L_k}(\ell)$ which results in

\[\max_k \w_k \ov{F}_{\wdt{L}_k}(\ell) \leq \max_k \w_k \ov{F}_{L_k}(\ell).\]

Using ${ \max_k \w_k \ov{F}_{\wdt{L}_k}(\ell) \geq \max_k \w_k \ov{F}_{L_k}(\ell)}$, we arrive at the desired result. This completes the proof of the lemma.

We first prove that

\[I\lp W^{(n)}_i;C^{(n)}_\cS \rp = H \lp C^{(n)}_{\cS,i} \rp.\]

To this end, we show $I\lp W^{(n)}_i;C^{(n)}_\cS \rp \!\geq\! H \lp C^{(n)}_{\cS,i} \rp$ and $I\lp W^{(n)}_i;C^{(n)}_\cS \rp \!\leq\! H \lp C^{(n)}_{\cS,i} \rp$. For the first inequality, we can write

\begin{align}\label{eq:ind-0}
I\lp W^{(n)}_i;C^{(n)}_\cS \rp & = H\lp C^{(n)}_\cS \rp - H\lp C^{(n)}_\cS \md W^{(n)}_i \rp \nonumber\\
& \geq H\lp C^{(n)}_\cS \rp\nonumber\\
& = H\lp C^{(n)}_{\cS,i}, C^{(n)}_{\cS,[N]\setminus\{i\}} \rp \nonumber\\
& \geq H\lp C^{(n)}_{\cS,i} \rp,
\end{align}

where $C^{(n)}_{\cS,i}:= \lp C^{(n)}_{k,i} \rp_{k\in \cS}$ and $C^{(n)}_{\cS,[N]\setminus\{i\}}:=\lp C^{(n)}_{k,1},\ldots, C^{(n)}_{k,i-1},C^{(n)}_{k,i},\ldots,C^{(n)}_{k,N} \rp_{k\in \cS}$. On the other hand, we have

\begin{align}\label{eq:ind-1}
I\lp W^{(n)}_i;C^{(n)}_\cS \rp & = I\lp W^{(n)}_i; C^{(n)}_{\cS,i}, C^{(n)}_{\cS,[N]\setminus\{i\}} \rp \nonumber\\
& = I\lp W^{(n)}_i; C^{(n)}_{\cS,[N]\setminus\{i\}} \rp + I\lp W^{(n)}_i; C^{(n)}_{\cS,i} \md C^{(n)}_{\cS,[N]\setminus\{i\}} \rp \nonumber\\
& \leq I\lp W^{(n)}_i; W^{(n)}_{[N]\setminus \{i\} } \rp  +  I\lp W^{(n)}_i; C^{(n)}_{\cS,i} \md C^{(n)}_{\cS,[N]\setminus\{i\}} \rp\nonumber\\
& \stackrel{\rm (a)}{=} I\lp W^{(n)}_i; C^{(n)}_{\cS,i} \md C^{(n)}_{\cS,[N]\setminus\{i\}} \rp \nonumber\\
& = H \lp C^{(n)}_{\cS,i} \md C^{(n)}_{\cS,[N]\setminus\{i\}} \rp  - H \lp C^{(n)}_{\cS,i} \md C^{(n)}_{\cS,[N]\setminus\{i\}}, W^{(n)}_i \rp \nonumber\\
& = H \lp C^{(n)}_{\cS,i} \md C^{(n)}_{\cS,[N]\setminus\{i\}} \rp\nonumber\\
& \leq H \lp C^{(n)}_{\cS,i} \rp,
\end{align}

where $\rm{(a)}$ follows since files $W^{(n)}_1,\ldots, W^{(n)}_N$ are mutually independent. Hence, using (<ref>), (<ref>), and (<ref>), we arrive at

\begin{align*}
I\lp W^{(n)}_i;C^{(n)}_\cS \rp & = H \lp C^{(n)}_{\cS,i} \rp\\
& \leq n\mu_{\cS}f.
\end{align*}

This completes the proof of the lemma.

Let $\boldsymbol{d}=(d_1,\ldots,d_K)$ be the demand vector. First, note that since user $k$ is capable of decoding its requested file $W^{(n)}_{d_k}$ from its received signal and cache content $C^{(n)}_k$, there should exist some family of caching strategies, encoding, and decoding functions with block length $n$ and decoding error probability $\epsilon_n$ where $\epsilon_n\rightarrow 0$ as $n\rightarrow\infty$. From Fano's inequality, we have

\begin{align*}
H \lp W^{(n)}_{d_k}\md Y^n_k,C^{(n)}_k \rp\leq n\epsilon_n,\quad k\in[K].
\end{align*}

Then, we can write

\begin{align}
nf(\cache,\bd)-n\epsilon_n \leq H\lp W^{(n)}_{d_1}\rp -n\epsilon_n &\leq I\lp W^{(n)}_{d_1};Y^n_1,C^{(n)}_1\rp \nonumber\\
&= I\lp W^{(n)}_{d_1};Y^n_1\md C^{(n)}_1\rp+I\lp W^{(n)}_{d_1};C^{(n)}_1\rp \nonumber\\
&=\sum_{i=1}^{n}I\lp W^{(n)}_{d_1};Y_{1,i}\md Y^{i-1}_1,C^{(n)}_1\rp+I\lp W^{(n)}_{d_1};C^{(n)}_1\rp\nonumber\\
&\stackrel{\rm (a)}{\leq} \sum_{i=1}^{n}I\lp W^{(n)}_{d_1},Y^{i-1}_1;Y_{1,i}\md C^{(n)}_1\rp+I\lp W^{(n)}_{d_1};C^{(n)}_1 \rp \nonumber\\
&\stackrel{\rm (b)}{=} \sum_{i=1}^n I\lp W^{(n)}_{d_1},Y^{Q-1}_1;Y_{1,Q}\md C^{(n)}_1,Q=i\rp+I\lp W^{(n)}_{d_1};C^{(n)}_1\rp \nonumber\\
&= n \sum_{i=1}^n I\lp W^{(n)}_{d_1},Y^{Q-1}_1;Y_{1,Q}\md C^{(n)}_1,Q=i\rp\mathbb{P}(Q=i)+I\lp W^{(n)}_{d_1};C^{(n)}_1\rp\nonumber\\
&= n \sum_{i=1}^n I\lp W^{(n)}_{d_1},Y^{Q-1}_1;Y_{1,Q}\md C^{(n)}_1, Q\rp + I\lp W^{(n)}_{d_1};C^{(n)}_1\rp\nonumber\\
\leq nI\lp W^{(n)}_{d_1},C^{(n)}_1, Y^{Q-1}_1, Q;Y_{1,Q}\rp + I\lp W^{(n)}_{d_1};C^{(n)}_1\rp \nonumber\\
\stackrel{\rm (c)}{=} nI(U_1;Y_{1,Q})+I\lp W^{(n)}_{d_1};C^{(n)}_1\rp\nonumber\\
& = nI(U_1;Y_1)+I\lp W^{(n)}_{d_1};C^{(n)}_1\rp \nonumber\\
& \stackrel{\rm (d)}{\leq} nI(U_1;Y_1)+ n\mu_{\{1\}}f(\cache,\bd),\label{eq:nf1_K}
\end{align}

where $\rm{(a)}$ holds since ${I\lp W^{(n)}_{d_1},Y^{i-1}_1;Y_{1,i}\md  C^{(n)}_1\rp = I\lp Y^{i-1}_1;Y_{1,i}\md  C^{(n)}_1\rp + I\lp W^{(n)}_{d_1};Y_{1,i}\md  Y^{i-1}_1, C^{(n)}_1\rp}$, in $\rm{(b)}$
$Q$ is a random variable independent of all other random variables which are uniformly distributed over $[n]$, in $\rm{(c)}$ we define ${U_1:= \left(W^{(n)}_{d_1},C^{(n)}_1, Y^{Q-1}_1 ,Q\right)}$, and in $\rm{(d)}$ we used (<ref>). This implies  inequality in (<ref>).

Similarly, for $k\in[2:K-1]$, we have

\begin{align}
nf(\cache,\bd)-n\epsilon_n &=H\lp W^{(n)}_{d_k} \rp-n\epsilon_n \nonumber\\
& \leq I\lp W^{(n)}_{d_k};Y^n_k,C^{(n)}_k\rp \nonumber\\
&= I\lp W^{(n)}_{d_k};Y^n_k\md C^{(n)}_k\rp +I\lp W^{(n)}_{d_k};C^{(n)}_k \rp\nonumber\\
\leq I\lp W^{(n)}_{d_k};Y^n_k,W^{(n)}_{\{d_1,\ldots,d_{k-1}\}},C^{(n)}_{[k-1]}\md C^{(n)}_k \rp +I\lp W^{(n)}_{d_k};C^{(n)}_k\rp \nonumber\\
= I\lp W^{(n)}_{d_k};C^{(n)}_{[k-1]}\md  C^{(n)}_k \rp +I\lp W^{(n)}_{d_k};W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}\md C^{(n)}_{[k]} \rp\nonumber\\
&\phantom{=}+I\lp W^{(n)}_{d_k};Y^n_k\md  W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k]}\rp +I\lp W^{(n)}_{d_k};C^{(n)}_k\rp\nonumber\\
&\stackrel{\rm (a)}{=}
I\lp W^{(n)}_{d_k};Y^n_k\md  W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k]}\rp+I\lp W^{(n)}_{d_k};C^{(n)}_{[k]}\rp\nonumber\\
\sum_{i=1}^{n}I\lp W^{(n)}_{d_k};Y_{k,i}\md  W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k]} ,Y_k^{i-1}\rp
+I\lp W^{(n)}_{d_k};C^{(n)}_{[k]}\rp \nonumber\\
\sum_{i=1}^{n}I\lp W^{(n)}_{d_k};Y_{k,i}, Y_{[k-1]}^{i-1}\md  W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k]} ,Y_k^{i-1}\rp\hspace{-2pt}+\hspace{-2pt}I\lp W^{(n)}_{d_k};C^{(n)}_{[k]}\rp\nonumber\\
&\stackrel{\rm (b)}{=}\sum_{i=1}^{n}I\lp W^{(n)}_{d_k};Y_{k,i}\md  W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k]},\!Y_{[k]}^{i-1}\rp\hspace{-2pt}+\hspace{-2pt}I\lp W^{(n)}_{d_k};C^{(n)}_{[k]}\rp\nonumber\\
\sum_{i=1}^{n}\!I\lp W^{(n)}_{d_k},\!C^{(n)}_k,Y_k^{i-1};\!Y_{k,i}\md  W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k-1]},\!Y_{[k-1]}^{i-1}\rp\!+\! I\lp W^{(n)}_{d_k};C^{(n)}_{[k]}\rp\nonumber\\
&\stackrel{\rm (c)}{=}
\sum_{i=1}^{n}\!I\lp W^{(n)}_{d_k},\!C^{(n)}_k,Y_k^{Q-1};\!Y_{k,Q}\md  W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k-1]},\!Y_{[k-1]}^{Q-1}, Q=i\rp\!+\! I\lp W^{(n)}_{d_k};C^{(n)}_{[k]}\rp \nonumber\\
& =
nI\hspace{-1pt}\lp W^{(n)}_{d_k},\!C^{(n)}_k,\!Y^{Q-1}_k\!;\! Y_{k,Q}\md W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k-1]},\!Y_{[k-1]}^{Q-1}, Q\rp\!+\!I\lp W^{(n)}_{d_k};C^{(n)}_{[k]}\rp\label{eq:nf_3}\\
& \stackrel{\rm(d)}{=} nI(U_{k};Y_{k,Q}| U_{k-1})\!+\!I\lp W^{(n)}_{d_k};C^{(n)}_{[k]}\rp\nonumber\\
&= nI(U_k;Y_k| U_{k-1})\hspace{-2pt}+\hspace{-2pt}I\lp W^{(n)}_{d_k};C^{(n)}_{[k]}\rp,\nonumber\\
& \stackrel{\rm(e)}{\leq} nI(U_k;Y_k| U_{k-1})\hspace{-2pt}+\hspace{-2pt}n\mu_{[k]}f(\cache,\bd),\label{eq:nf2_K}
\end{align}

where $\rm{(a)}$ holds since, for an uncoded caching strategy and mutually independent files, we have

\begin{align*}
I\lp W^{(n)}_{d_k};W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}\md C^{(n)}_{[k]}\rp & = I\lp W^{(n)}_{d_k};W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}\md  C_{[k],d_k}, C^{(n)}_{[k],\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k], [N]\setminus\{d_1,\ldots,d_{k}\}}\rp\\
H\lp W^{(n)}_{d_k}, C^{(n)}_{[k],d_k}, C^{(n)}_{[k],\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k], [N]\setminus\{d_1,\ldots,d_{k}\}}\rp \\
+ H\lp W^{(n)}_{\{d_1,\ldots,d_{k-1}\}},C^{(n)}_{[k],d_k}, C^{(n)}_{[k],\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k], [N]\setminus\{d_1,\ldots,d_{k}\}}\rp\nonumber\\
&\phantom{=} - H\lp W^{(n)}_{d_k},W^{(n)}_{\{d_1,\ldots,d_{k-1}\}},C^{(n)}_{[k],d_k}, C^{(n)}_{[k],\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k], [N]\setminus\{d_1,\ldots,d_{k}\}}\rp \\
- H\lp C^{(n)}_{[k],d_k}, C^{(n)}_{[k],\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k], [N]\setminus\{d_1,\ldots,d_{k}\}}\rp \\
H\lp W^{(n)}_{d_k},  C^{(n)}_{[k],\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k], [N]\setminus\{d_1,\ldots,d_{k}\}}\rp \\
+ H\lp W^{(n)}_{\{d_1,\ldots,d_{k-1}\}},C^{(n)}_{[k],d_k},  C^{(n)}_{[k], [N]\setminus\{d_1,\ldots,d_{k}\}}\rp \nonumber\\
&\phantom{=} - H\lp W^{(n)}_{d_k},W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k], [N]\setminus\{d_1,\ldots,d_{k}\}}\rp \\
- H\lp C^{(n)}_{[k],d_k}, C^{(n)}_{[k],\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k], [N]\setminus\{d_1,\ldots,d_{k}\}}\rp \\
H\lp W^{(n)}_{d_k}\rp + H\lp C^{(n)}_{[k],\{d_1,\ldots,d_{k-1}\}}\rp + H\lp C^{(n)}_{[k], [N]\setminus\{d_1,\ldots,d_{k}\}}\rp \\
+ H\lp W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}\rp +H\lp C^{(n)}_{[k],d_k}\rp +H\lp C^{(n)}_{[k], [N]\setminus\{d_1,\ldots,d_{k}\}}\rp \nonumber\\
&\phantom{=} - H\lp W^{(n)}_{d_k}\rp -H\lp W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}\rp -H\lp C^{(n)}_{[k], [N]\setminus\{d_1,\ldots,d_{k}\}}\rp \\
- H\lp C^{(n)}_{[k],d_k}\rp -H\lp C^{(n)}_{[k],\{d_1,\ldots,d_{k-1}\}}\rp -H\lp C^{(n)}_{[k], [N]\setminus\{d_1,\ldots,d_{k}\}}\rp\\
\end{align*}

Moreover, $\rm{(b)}$ follows from the degradedness of the channel, which implies that for any time instance $i$,  conditioned on $Y_{k,i}$, all channel outputs $\{Y_{u,i}: u<k\}$ are independent of the channel input and hence from the files and cache contents. More precisely, from  $\lp W^{(n)}_{\{1,\ldots, N\}}, C^{(n)}_{[K]}\rp \leftrightarrow X_i  \leftrightarrow   Y_{K,i} \leftrightarrow \cdots \leftrightarrow Y_{1,i}$ we have

\begin{align*}
I\lp W^{(n)}_{d_k};Y_{
[k-1]}^{i-1}\md W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k]},\!Y^{i-1}_{k}\rp
&\!=\! H\lp Y_{[k-1]}^{i-1}\md  W^{(n)}_{\{d_1,\ldots,d_{k-1}\}}, C^{(n)}_{[k]},\!Y^{i-1}_{k}\rp \! \\
& \phantom{=} -\! H\lp Y_{[k-1]}^{i-1}\md W^{(n)}_{\{d_1,\ldots,d_{k}\}}, C^{(n)}_{[k]},\!Y^{i-1}_{k}\rp \\
&= H\lp Y_{[k-1]}^{i-1}\md Y^{i-1}_{k}\rp\hspace{-2pt}-\hspace{-2pt} H\lp Y_{[k-1]}^{i-1}\md Y^{i-1}_{k}\rp\\
& = 0.
\end{align*}

Furthermore, in the equality marked by $\rm{(c)}$, the random variable $Q$ is independent of all other random variables and admits a uniform distribution over $[n]$. In the step $\rm{(d)}$ we have

\[{U_k := \left(U_{k-1},W^{(n)}_{d_k},C^{(n)}_k,Y^{Q-1}_{k}\right) = \left( W^{(n)}_{\{d_1,\ldots d_k\}}, C^{(n)}_{[k]}, Y_{[k]}^{Q-1}, Q\right)}.\]

Finally, in the inequality $\rm{(e)}$ we used (<ref>).
Dividing both sides of (<ref>) by $n$ and letting $n\rightarrow\infty$, we arrive at (<ref>), claimed in the lemma.

Finally, we can use a similar argument for the $K$-th and reach to (<ref>). Continuing from there, we  can write

\begin{align}
nf(\cache,\bd)-n\epsilon_n & \leq
nI\hspace{-1pt}\lp W^{(n)}_{d_K},\!C^{(n)}_K,\!Y^{Q-1}_K\!;\! Y_{K,Q}\md W^{(n)}_{\{d_1,\ldots,d_{K-1}\}}, C^{(n)}_{[K-1]},\!Y_{[K-1]}^{Q-1},Q\rp + I\lp W^{(n)}_{d_K};C^{(n)}_{[K]}\rp\nonumber\\
& \stackrel{\rm (a)}{=} nI\hspace{-1pt}\lp X_Q,W^{(n)}_{d_K},\!C^{(n)}_K,\!Y^{Q-1}_K\!;\! Y_{K,Q}\md  U_{K-1}\rp + I\lp W^{(n)}_{d_K};C^{(n)}_{[K]}\rp\nonumber\\
& \stackrel{\rm (b)}{=} nI\hspace{-1pt}\lp X_Q;\! Y_{K,Q}\md U_{K-1}\rp + I\lp W^{(n)}_{d_K};C^{(n)}_{[K]}\rp \nonumber\\
& = nI\lp X;Y_K\md U_{K-1} \rp + I\lp W^{(n)}_{d_K};C^{(n)}_{[K]}\rp\nonumber\\
& \stackrel{\rm (c)}{\leq } nI\lp X;Y_K\md U_{K-1} \rp + n\mu_{[K]}f(\cache,\bd),\label{eq:nf_4}
\end{align}

where $\rm{(a)}$ holds since the channel input $X_Q$ is deterministically determined by the files and cache contents, $\rm{(b)}$
holds since condition on $X_Q$, the channel output $Y_{K,Q}$ is independent of all other variables, and $\rm{(c)}$ follows from (<ref>). The last inequality in (<ref>) can be obtained from (<ref>).

It remains to show that the random variables $U_1,\ldots, U_{K-1}$ form a Markov chain. This is immediately implied by the recursive construction of $U_k$ and the fact that $U_{k-1}$ is deterministically known once $U_k$ is given. This completes the proof of the lemma.

The proof of Lemma <ref> is derived directly from the proof of Lemma <ref>. From (<ref>) and (<ref>), we have

\begin{align}
& nf(\cache,\bd)-n\epsilon_n \leq nI(U_1;Y_1)+n \mu_{\{1\}} f(\cache,\bd),\label{eq:f2-1}\\
& nf(\cache,\bd)-n\epsilon_n \leq nI\lp X;Y_2\md U_1 \rp + n \mu_{\{1,2\}} f(\cache,\bd)\label{eq:f2-2},
\end{align}

For the last term in (<ref>), we can write

\begin{align}\label{eq:I2-1}
\mu_{\{1\}} & = \Big|\bigcup_{\ell\in [\nn_1]} \cI_{1,\ell} \Big| \leq \sum_{\ell\in[\nn_1]} |\cI_{1,\ell}| =  \mu.
\end{align}

Similarly, for the last term in (<ref>) we get

\begin{align}\label{eq:I2-2}
\mu_{\{1,2\}} & = \Big|\bigcup_{u\in \{1,2\}} \bigcup_{\ell\in [\nn_u]} \cI_{u,\ell} \Big|\nonumber\\
& \leq \sum_{u\in \{1,2\}}\sum_{\ell\in[\nn_u]} |\cI_{u,\ell}|\nonumber\\
& = \sum_{\ell\in[\nn_1]} |\cI_{1,\ell}| + \sum_{\ell\in[\nn_2]} |\cI_{2,\ell}| = 2\mu.
\end{align}

Plugging (<ref>) and (<ref>) into (<ref>) and (<ref>), respectively, we arrive at the desired inequalities. This completes the proof of the lemma.

[1]
H. Reisizadeh, M. A. Maddah-Ali, and S. Mohajer, “Cache-aided two-user
broadcast channels with state information at receivers,” in 2019 IEEE
International Symposium on Information Theory (ISIT).1em plus 0.5em
minus 0.4emIEEE, 2019, pp. 16–20.

[2]
M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE
Transactions on Information Theory, vol. 60, no. 5, pp. 2856–2867, 2014.

[3]
——, “Decentralized coded caching attains order-optimal memory-rate
tradeoff,” IEEE/ACM Transactions On Networking, vol. 23, no. 4, pp.
1029–1040, 2014.

[4]
S. H. Lim, C.-Y. Wang, and M. Gastpar, “Information-theoretic caching: The
multi-user case,” IEEE Transactions on Information Theory, vol. 63,
no. 11, pp. 7018–7037, 2017.

[5]
Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “The exact rate-memory tradeoff
for caching with uncoded prefetching,” IEEE Transactions on
Information Theory, vol. 64, no. 2, pp. 1281–1296, 2018.

[6]
R. Pedarsani, M. A. Maddah-Ali, and U. Niesen, “Online coded caching,”
IEEE/ACM Transactions on Networking, vol. 24, no. 2, pp. 836–845,

[7]
M. Ji, G. Caire, and A. F. Molisch, “Wireless device-to-device caching
networks: Basic principles and system performance,” IEEE Journal on
Selected Areas in Communications, vol. 34, no. 1, pp. 176–189, 2015.

[8]
——, “Fundamental limits of caching in wireless d2d networks,” IEEE
Transactions on Information Theory, vol. 62, no. 2, pp. 849–869, 2015.

[9]
U. Niesen and M. A. Maddah-Ali, “Coded caching with nonuniform demands,”
IEEE Transactions on Information Theory, vol. 63, no. 2, pp.
1146–1158, 2016.

[10]
J. Zhang, X. Lin, and X. Wang, “Coded caching under arbitrary popularity
distributions,” IEEE Transactions on Information Theory, vol. 64,
no. 1, pp. 349–366, 2017.

[11]
H. Reisizadeh, M. A. Maddah-Ali, and S. Mohajer, “Erasure coding for
decentralized coded caching,” in 2018 IEEE International Symposium on
Information Theory (ISIT).1em plus 0.5em minus 0.4emIEEE,
2018, pp. 1715–1719.

[12]
——, “Subspace coding for coded caching: Decentralized and centralized
placements meet for three users,” in 2019 IEEE International Symposium
on Information Theory (ISIT).1em plus 0.5em minus 0.4emIEEE,
2019, pp. 677–681.

[13]
Z. Chen, P. Fan, and K. B. Letaief, “Fundamental limits of caching: Improved
bounds for small buffer users,” arXiv preprint arXiv:1407.1935, 2014.

[14]
Y.-P. Wei and S. Ulukus, “Novel decentralized coded caching through coded
prefetching,” in 2017 IEEE Information Theory Workshop (ITW).1em plus 0.5em minus 0.4emIEEE, 2017, pp. 1–5.

[15]
M. A. Maddah-Ali and U. Niesen, “Cache-aided interference channels,”
IEEE Transactions on Information Theory, vol. 65, no. 3, pp.
1714–1724, 2019.

[16]
N. Naderializadeh, M. A. Maddah-Ali, and A. S. Avestimehr, “Fundamental limits
of cache-aided interference management,” IEEE Transactions on
Information Theory, vol. 63, no. 5, pp. 3092–3107, 2017.

[17]
J. Hachem, U. Niesen, and S. Diggavi, “A layered caching architecture for the
interference channel,” in 2016 IEEE International Symposium on
Information Theory (ISIT).1em plus 0.5em minus 0.4emIEEE,
2016, pp. 415–419.

[18]
R. Timo and M. Wigger, “Joint cache-channel coding over erasure broadcast
channels,” in 2015 International Symposium on Wireless Communication
Systems (ISWCS).1em plus 0.5em minus 0.4emIEEE, 2015, pp.

[19]
S. S. Bidokhti, M. Wigger, and R. Timo, “Erasure broadcast networks with
receiver caching,” in 2016 IEEE International Symposium on Information
Theory (ISIT).1em plus 0.5em minus 0.4emIEEE, 2016, pp.

[20]
S. S. Bidokhti, M. Wigger, and A. Yener, “Benefits of cache assignment on
degraded broadcast channels,” in Information Theory (ISIT), 2017 IEEE
International Symposium on.1em plus 0.5em minus 0.4emIEEE,
2017, pp. 1222–1226.

[21]
M. M. Amiri and D. Gündüz, “Cache-aided content delivery over erasure
broadcast channels,” IEEE Transactions on Communications, vol. 66,
no. 1, pp. 370–381, 2018.

[22]
K.-H. Ngo, S. Yang, and M. Kobayashi, “Scalable content delivery with coded
caching in multi-antenna fading channels,” IEEE Transactions on
Wireless Communications, vol. 17, no. 1, pp. 548–562, 2018.

[23]
J. Zhang, F. Engelmann, and P. Elia, “Coded caching for reducing csit-feedback
in wireless communications,” in 2015 53rd Annual Allerton Conference
on Communication, Control, and Computing (Allerton).1em plus 0.5em
minus 0.4emIEEE, 2015, pp. 1099–1105.

[24]
J. Zhang and P. Elia, “Fundamental limits of cache-aided wireless bc:
Interplay of coded-caching and csit feedback,” IEEE Transactions on
Information Theory, vol. 63, no. 5, pp. 3142–3160, 2017.

[25]
A. S. Avestimehr, S. N. Diggavi, and N. David, “Wireless network information
flow: A deterministic approach,” IEEE Transactions on Information
theory, vol. 57, no. 4, pp. 1872–1905, 2011.

[26]
N. David and R. D. Yates, “Fading broadcast channels with state information at
the receivers,” IEEE Transactions on Information Theory, vol. 58,
no. 6, pp. 3453–3471, 2012.

[27]
R. D. Yates and D. Tse, “K user fading broadcast channels with csi at the
receivers,” in 2011 Information Theory and Applications
Workshop.1em plus 0.5em minus 0.4emIEEE, 2011, pp. 1–6.

[28]
C. E. Shannon et al., “Coding theorems for a discrete source with a
fidelity criterion,” IRE Nat. Conv. Rec, vol. 4, no. 142-163, p. 1,

[29]
R. M. Gray and A. D. Wyner, “Source coding for a simple network,” Bell
System Technical Journal, vol. 53, no. 9, pp. 1681–1721, 1974.

[30]
M. Gastpar, B. Rimoldi, and M. Vetterli, “To code, or not to code: Lossy
source-channel communication revisited,” IEEE Transactions on
Information Theory, vol. 49, no. 5, pp. 1147–1158, 2003.