{'fraction_non_alphanumeric': 0.051069104431360396, 'fraction_numerical': 0.014886891850015495, 'mean_word_length': 4.032185628742515, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 20, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 25, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Memory-Rate Tradeoff for Caching with Uncoded Placement under Nonuniform Random Demands

For a caching system with multiple users, we aim to characterize the memory-rate tradeoff for caching with uncoded cache placement, under nonuniform file popularity. Focusing on the modified coded caching scheme (MCCS) recently proposed by Yu, etal., we formulate the cache placement optimization problem for the MCCS to minimize the average delivery rate under nonuniform file popularity, restricting to a class of popularity-first placements. We then present two information-theoretic lower bounds on the average rate for caching with uncoded placement, one for general cache placements and the other restricted to the popularity-first placements. By comparing the average rate of the optimized MCCS with the lower bounds, we prove that the optimized MCCS attains the general lower bound for the two-user case, providing the exact memory-rate tradeoff. Furthermore, it attains the popularity-first-based lower bound for the case of general K users with distinct file requests. In these two cases, our results also reveal that the popularity-first placement is optimal for the MCCS, and zero-padding used in coded delivery incurs no loss of optimality. For the case of K users with redundant file requests, our analysis shows that there may exist a gap between the optimized MCCS and the lower bounds due to zero-padding. We next fully characterize the optimal popularity-first cache placement for the MCCS, which is shown to possess a simple file-grouping structure and can be computed via an efficient algorithm using closed-form expressions. Finally, we extend our study to accommodate both nonuniform file popularity and sizes, where we show that the optimized MCCS attains the lower bound for the two-user case, providing the exact memory-rate tradeoff. Numerical results show that, for general settings, the gap between the optimized MCCS and the lower bound only exists in limited cases and is very small.

caching scheme (CCS) that combines carefully designed uncoded cache contents with a coded multicast delivery strategy. It was shown to provide a global caching gain in addition to local caching gain to reduce the delivery rate (load) substantially, leading to the possibility of serving an infinite number of users simultaneously with finite resources. This advantage has drawn intense interests in coded caching, with extension to various transmission scenarios and network architectures, including decentralized scenarios [7], transmitter caching in mobile edge networks [8]- [10], user caching in device-to-device networks [11], transmitter and receiver caching in wireless interference networks [12], [13], hierarchical networks [14], and online caching [15]. Recently, a modified coded caching scheme (MCCS) was proposed [16] with an improved delivery strategy to remove redundancy among coded messages, resulting in further delivery rate reduction from that of the CCS. The MCCS was further applied to the device-to-device networks [17].
For understanding the fundamental limit of coded caching, many research efforts were devoted to characterizing the memory-rate tradeoff for caching with uncoded cache placement. For files of uniform popularity and sizes, this tradeoff has been studied extensively, typically by developing an achievable scheme and compare it to an information-theoretic lower bound [6], [16], [18], [19]. When the system has fewer users than files, it has been shown that the CCS with optimized cache placement achieves the minimum peak delivery rate for caching with uncoded placement, i.e., the exact memory-rate tradeoff [18], [19]. For general scenarios of arbitrary users and files with random requests, the MCCS with optimized cache placement has been shown to characterize the exact memoryrate tradeoff that minimizes both average and peak delivery rate [16] under uniform file popularity and sizes.
For files with nonuniform popularity or sizes, different cache placement strategies were proposed for the CCS to handle nonuniformity [20]- [30]. In particular, several CCSbased schemes, either for nonuniform file popularity [22], [23] or for nonuniform file sizes [28], [29], were shown to achieve an average rate that is a constant factor away from the lower bound for caching with any cache placement. However, these gaps are still large for practical concerns. Only recently, for two files of nonuniform popularity, a coded caching scheme was proposed [31], which achieves the lower bound for caching with uncoded placement. For the MCCS, existing studies are scarce, and only [32] studied the cache placement optimization under nonuniform file popularity. In general, for files with nonuniform popularity and sizes, characterizing the memory-rate tradeoff for caching with uncoded placement is challenging. How well the CCS and the MCCS perform in terms of memory-rate tradeoff under nonuniform file popularity or size remains unknown.
The cache placement is a key design issue for coded caching to maximize caching gain and minimize delivery rate. For uniform file popularity, a symmetric cache placement (i.e., identical cache placement for all files) is optimal for both the CCS [30] and the MCCS [16]. For nonuniform file popularity, the problem is much more challenging, as the cache placement may be asymmetric among files. This asymmetry introduces nonequal subfile sizes that complicate both design and analysis. For the CCS, suboptimal placement strategies [20]- [23] and optimization approaches [24]- [26], [30] were proposed to study the cache placement. In particular, the optimal cache placement structure has been entirely characterized in [26]. As the delivery strategy in the MCCS is more complicated than that in the CCS, the cache placement optimization for the MCCS was only studied in [32] through numerical methods. The optimal cache placement structure for the MCCS is still unknown. Furthermore, in the existing coded caching schemes, since subfiles may be of different sizes, zero-padding is commonly used in the coded messages to simplify the delivery [24]- [26], [30], [32]. However, the impact of zeropadding on the coded delivery (for both the CCS and the MCCS) has, to our best knowledge, never been studied or known.

A. Contributions
Our main goal in this paper is to characterize the memoryrate tradeoff for caching with uncoded placement under nonuniform file popularity. Later, we also extend our study to include nonuniform file sizes. Our approach is to first formulate the cache placement optimization problem for the MCCS to minimize the average rate. We restrict the cache placement to the class of popularity-first placements, which simplifies the optimization problem and has also been numerically shown to be optimal for the MCCS [32]. We then develop two information-theoretic lower bounds on the average rate for caching with uncoded placement, one for general cache placements and the other restricted to the popularity-first cache placements. By connecting and comparing the average rate of the optimized MCCS to the lower bounds, we characterize the memory-rate tradeoff under nonuniform file popularity.
We partition the file request scenarios into three regions to analyze, depending on the number of users K. For K = 2 users, we prove that the two lower bounds are identical. Furthermore, we show that the optimized MCCS achieves the lower bounds and is an optimal caching scheme under uncoded placement. For K > 2 users with distinct file requests, we show that the optimized MCCS is an optimal caching scheme under popularity-first placement. For the above two regions, our results for the MCCS also lead to the following two implications: 1) the popularity-first placement is optimal for the MCCS, and 2) zero-padding used in coded delivery incurs no loss of optimality. Finally, in the third region of K > 2 users with redundant file requests, we show that there may exist a gap between the optimized MCCS and the lower bounds. Through analysis, we attribute the cause of this possible loss to zero-padding used in the coded delivery and quantify the loss. Even though the optimality of the MCCS in this region is uncertain in general, we provide some special cases where the MCCS is still shown to be optimal. Our numerical results further show that the loss only exists in some limited cases and is very small in general.
The region of K > 2 users with distinct file requests also allows us to connect the MCCS and the CCS under nonuniform file popularity. This enables us to further analyze the performance of the CCS that is otherwise unknown in the literature. We show that 1) the use of zero-padding in the CCS [24]- [26], [30] incurs no loss of optimality; and 2) for distinct file requests, the optimized CCS [24]- [26], [30] is an optimal scheme for caching under popularity-first placement.
With the understanding of the optimality of the MCCS, we next characterize the optimal cache placement structure for the MCCS. By analyzing the cache placement optimization problem, we show that the possible structures for the optimal cache placement for the MCCS inherits that of the CCS obtained in [26]. Specifically, regardless of file popularity distribution, there are at most three file groups in the optimal placement, where files in each group have the same placement. The optimal placement solution under each possible file grouping structure is obtained in closed-form. The final optimal cache placement solution is obtained by an efficient simple algorithm, which only requires computing a set of candidate solutions in closed-form in parallel. The obtained optimal cache placement solution allows us to quantitatively evaluate the gap between the optimized MCCS with the lower bounds in the region of K > 2 users with redundant file requests to understand the exact memory-rate tradeoff. The optimal cache placement solution provided by our algorithm is verified through simulations. Note that although the MCCS and the CCS share the same set of candidate placement structures, the optimal placement can still be different for the two schemes, as a result of different coded delivery strategies. Numerical results demonstrate this difference in the cache placement and the performance gap between the optimized MCCS and the optimized CCS.
Lastly, we extend our study to the more general case where file popularity and sizes are both nonuniform. We formulate the cache placement optimization problem for the MCCS and propose an information-theoretical lower bound on the average rate. We show that for K = 2 users, the optimized MCCS achieves the proposed lower bound and thus characterizes the exact memory-rate tradeoff for caching with uncoded placement. For other cases, numerical results again show that the gap between the optimized MCCS and the lower bound is very small in general.

B. Related Works
With a surge of interest in caching, there are many recent works study caching with uncoded placement. For uniform file popularity and sizes, the exact memory-rate tradeoff has been fully characterized for both peak rate [16], [18], [19] and average rate [16], which is achieved by the CCS and the MCCS, respectively. Beyond uncoded placement, the average rate of the optimized MCCS was shown to be at most a factor of two away from the optimal caching with any placement considered [33].
When heterogeneity exists in the system, the characterization of the memory-rate tradeoff is generally an open problem. For nonuniform file popularity, the cache placement problem was studied for the CCS [20]- [26], [30] and the MCCS [32] to minimize the achievable delivery rate. For the CCS, to simplify the placement problem amid nonuniformity, suboptimal file-grouping-based cache placement strategies were proposed in [20]- [23]. They are shown to achieve an average rate that is a constant factor away from the lower bound for caching with any placement. Nonetheless, the gap is generally still large for practical consideration. Several works used the optimization approach to study the cache placement problem [24], [25], [30], either obtaining certain properties or devising numerical methods to solve the problem. The optimal placement structure has been completely characterized in [26], which shows inherit file grouping structure with at most three groups. For the MCCS, the complication in the improved delivery strategy adds challenges to the analysis, and the cache placement problem was studied only in [32]. However, the problem was numerically solved in that work, which cannot provide insight into the optimal cache placement structure.
Note that none of the above works [20]- [26], [30], [32] provided any lower bound for caching with uncoded placement to characterize the memory-rate tradeoff. The gap between the achievable rate of either the CCS or the MCCS and the optimal caching with uncoded placement remains unknown under nonuniform file popularity and size. Most recently, the exact memory-rate tradeoff under uncoded placement for the case of two files was characterized [31]. However, the caching scheme proposed in [31] is only designed for two files, which is not extendable to general scenarios.
When files only have nonuniform sizes, the CCS has again been shown to achieve a peak rate a constant factor away from the lower bound for caching with any placement [28], [29], where the gap may be large for practical concerns. A limited number of recent works also considered joint nonuniformity in cache size, file popularity and size [30], [34]. The cache placement optimization for the CCS was considered in [30], where simplification methods were developed for the optimization problem with well-performed numerical solutions. However, [30] focused on the optimization framework for the CCS, but did not address the optimality of the optimized CCS as compared to any information-theoretic lower bound. In [34], the memory-rate tradeoff has been characterized under general placement, in the case of full nonuniformity in cache size, file popularity and size, but only for a system of two users and two files, where a caching scheme was proposed to achieve the lower bound. Except for these recent studies, the MCCS has never been explored for files with nonuniformity in both popularity and size.

C. Organization and Notations
The rest of the paper is organized as follows. The system model is presented in Section II. In Section III, we formulate the cache placement optimization problem for the MCCS under nonuniform file popularity. In Section IV, we propose two lower bounds for caching with uncoded placement and discuss the relation of the two bounds. In Section V, we characterize the memory-rate tradeoff for caching by comparing the optimized MCCS with the two lower bounds and identify the optimality of the MCCS in certain regions. In Section VI, we derive the optimal cache placement structure for the MCCS under nonuniform file popularity. In Section VII, we extend our study to files with nonuniform popularity and size to characterize the memory-rate tradeoff. Numerical results are provided in Section VIII, followed by the conclusion in Section IX.
Notations: The cardinality of set S is denoted by |S|, and the index set for S is defined by I |S| = {1, . . . , |S|}. The size of file W is denoted by |W |. The bitwise "XOR" operation between two subfiles is denoted by ⊕. Notations ⌊·⌋ and ⌈·⌉ denote the floor and ceiling functions, respectively. Notation a 0 means vector a is element-wise non-negative. Also, we extend the definition of K l and define K l = 0, for l < 0 or l > K.

II. SYSTEM MODEL
We consider a cache-aided transmission system with a server connecting to K cache-equipped users over a shared error-free link, as shown in Fig. 1. The server has a database consisting of N files {W 1 , . . . , W N }. Each file W n is of size F bits and has probability p n of being requested. The popularity distribution of the entire N files is denoted by p [p 1 , . . . , p N ] T , with N n=1 p n = 1. The files are indexed according to the decreasing order of their popularities as p 1 ≥ p 2 ≥ · · · ≥ p N . Each user k has a local cache, whose size in the unit of file is M files, representing a cache capacity of M F bits. The size M can be an arbitrary real number within interval [0, N ]. We denote N {1, . . . , N } and K {1, . . . , K}.
The coded caching operates in the cache placement phase and the content delivery phase. In the cache placement phase, under a cache placement scheme, a portion of uncoded file contents are placed in each user's local cache. Assume each user k independently requests a file with index d k from the server. Let d [d 1 , . . . , d K ] T denote the demand vector of K users. In the content delivery phase, based on the demand vector d and the cached contents at users, the server generates coded messages containing those uncached portions of requested files and transmits these coded messages to the users. Upon receiving the coded messages, each user k reconstructs its requested file W d k from the received coded messages and its cached content. With a valid coded caching scheme, each user k is able to reconstruct its requested file for any demand vector d ∈ N K over an error-free link.

III. CACHE PLACEMENT FOR RATE MINIMIZATION
For any coded caching scheme, cache placement is a key design issue, which needs to be optimized to minimize the delivery rate. The MCCS is a coded caching scheme recently proposed [16], where the delivery strategy is improved over the original CCS [6] to reduce the delivery rate further. In this section, we formulate the rate minimization problem for the MCCS under the cache placement optimization.

A. Cache Placement
The cache placement construction for the MCCS is based on file partitioning. For K users, there are total 2 K user subsets in K, with subset sizes ranging from 0 to K (including the empty set). Grouping the user subsets based on their sizes, we form a cache subgroup that contains all user subsets of size l, defined as A l {S : |S| = l, S ⊆ K} with |A l | = K l , for l = 0, . . . , K. Partition each file W n into 2 K non-overlapping subfiles. Each subfile is for a unique user subset S ⊆ K, denoted by W n,S , and it is stored at the local cache of each user in subset S. It is possible that W n,S = ∅ for a given S, and also for S = ∅, subfile W n,∅ is only kept in the server and not stored in any user's cache. A caching scheme specifies how files are partitioned for storage. Regardless of the scheme used, each file should be able to be reconstructed by combining all its subfiles. Thus, we have There are 2 K subfile sizes to be determined for each file. To reduce the number of variables and simplify the cache placement problem for its tractability, the following condition is imposed: C1). For any file W n , the size of its subfile W n,S is the same for any S of the same size, i.e., |W n,S1 | = |W n,S2 |, for ∀ S 1 , S 2 ∈ A l , l = 0, · · · , K.
The above condition is in fact proven to be the property of the optimal cache placement for the CCS [24]. For the MCCS, although it is more difficult to prove analytically, it is numerically verified in [32] that imposing this condition results in no loss of optimality. 1 As a result, the subfiles of file W n are grouped into file subgroups according to user subset size l, each denoted by W l n = {W n,S : S ∈ A l }, for l = 0, . . . , K. Note that there are K l subfiles of the same size in W l n , and there are K + 1 file subgroups. Following this, let a n,l denote the size of subfiles in W l n as a fraction of file W n of size F bits, i.e., a n,l |W n,S |/F , for ∀S ∈ A l , l = 0, . . . , K, n ∈ N . In particular, a n,0 represents the fraction of file W n that is not stored at any user's cache but only remains in the server. Then, the file partition constraint (1) is simplified to K l=0 K l a n,l = 1, n ∈ N .
Recall that each subfile is intended for a unique user subset. For the cache placement, user k stores all the subfiles in W l n that are intended for it, i.e., {W n,S : k ∈ S and S ∈ A l+1 } ⊆ W l n , for l = 0, . . . , K − 1. Note that in each cache subgroup A l , there are K−1 l−1 different user subsets containing the same user k. Thus, there are K l=1 K−1 l−1 subfiles in each file W n that a user can store in its local cache. This means that, in total, a fraction K l=1 K−1 l−1 a n,l of file W n is cached by a user. With cache size M at each user, we have the following cache constraint For nonuniform file popularity, even with Condition C1, the cache placement is still a complicated problem. To further simplify the cache placement problem and the average rate expression, we consider the popularity-first cache placement approach described below.
Popularity-first cache placement: A popularity-first cache placement is to allocate more cache memory to a more popular file: With file popularity p 1 ≥ · · · ≥ p N , the cached subfiles satisfies a n,l ≥ a n+1,l , l ∈ K, n ∈ N \{N }.
(4) Remark 1. The popularity-first cache placement approach has been used for both the CCS [24], [30] and the MCCS [32] to simplify the cache placement problem. For the CCS, the popularity-first placement has been proven to be the property of the optimal cache placement [24]. For the MCCS, the same is difficult to prove analytically, but the optimality of the popularity-first placement has been verified numerically [32].
In Section V, we will prove the optimality of popularity-first placement in some cases.

B. Content Delivery
In the content delivery phase, the server multicasts coded messages to different user subsets. Each coded message corresponds to a user subset S, formed by the bitwise XOR operation of subfiles as In the original CCS [6], the server simply delivers the coded message formed by each user subset, for any demand vector d. However, under random demands, multiple users may request the same (popular) file, causing redundant coded messages transmitted separately multiple times. To address this, in the MCCS [16], a modified coded delivery strategy is proposed to remove this redundancy and reduce the average delivery rate further. Let N (d) denote the number of distinct file requests for demand vector d, where N (d) ≤ K. To describe the delivery strategy in the MCCS, we provide the following four definitions: Definition 1 (Leader group). The leader group U is a user subset of size |U| = N (d), with the users in U having exactly N (d) distinct file requests.
Definition 2 (Redundant group). Given the leader group U, any user subset S ⊆ K with S ∩ U = ∅ is called a redundant group; otherwise, S is a non-redundant group.
Definition 3 (Redundant request). A file request d k by any user k in the redundant group S is a redundant request.
Definition 4 (Redundant message). Any coded message C S corresponding to a redundant group S is a redundant message; otherwise, it is a non-redundant message.
Based on the above definitions, any user subset is either a redundant group or a non-redundant group. In the MCCS, only the non-redundant messages are multicasted to both non-redundant and redundant groups. For nonuniform file popularity, file partitioning may be different for different files, leading to different subfile sizes. In formulating the coded message C S in (5), the following technique is commonly used for the subfiles of different lengths in the XOR operation: Zero-padding: With different subfile sizes, subfiles in coded message C S are zero-padded to the size of the largest subfile in C S for transmission.
Consider zero-padding for the coded message C S for subgroup S. The size of C S in (5) is given by Remark 2. Zero-padding is a technique commonly used to form coded messages in the existing works [7], [20], [22]- [26], [30], [32]. In some proposed delivery schemes, zeropadding may be limited to coding subfiles within a file group, such as in [20], [22], [23]. Zero-padding considered in (6) for C S is general for any files requested by a user subset S. Despite being a common technique, the impact of zeropadding on coded caching has not been analyzed and is unknown. Intuitively, zero-padding introduces extra waste bits that may degrade the performance. In Section V, we will provide our findings and insight on this issue.

C. Cache Placement Optimization
Let a n [a n,0 , . . . , a n,K ] T denote the (K + 1) × 1 cache placement vector for file W n , n ∈ N , and let a [a T 1 , · · · , a T N ] T represent the entire placement for N files. For demand vector d, the delivery rate is the total size of the nonredundant messages, given by The average delivery rateR MCCS is given bȳ where E d [·] is taken with respect to d. From (4), we define the set of all popularity-first placements by Q {a : a n,l ≥ a n+1,l , l ∈ K, n ∈ N \{N }}. Here, we assume that F is large enough such that a n,l F ∈ Z. To obtain the minimum average rate for the MCCS, we optimize the cache placement a ∈ Q to minimizeR MCCS , given by 2 s.t. (2), (3), and a n 0, n ∈ N .
Note that in P0, we restricted the cache placement optimization within the set of popularity-first placements, for the reason discussed in Remark 1. In the following, we first focus on analyzing how optimal the MCCS in P0 is under nonuniform file popularity, by comparing it with the lower bounds we develop for caching with uncoded placement. Then, in Section VI, we describe the optimal cache placement solution to P0 and its inherent structure.

IV. CONVERSE BOUND FOR UNCODED PLACEMENT
In this section, we first introduce a lower bound on the average rate for any caching with uncoded placement. Then, we develop a popularity-first-based lower bound by restricting the uncoded placement to the set of popularity-first placements.
Let D denote the set of the distinct file indices in demand vector d, i.e., D = Unique(d) ⊆ N , where Unique(d) is to extract the unique elements in d. Recall the definition of index set I |D| for D is given in Section I-C. The following lemma gives a lower bound on the average rate under any uncoded placement.
Lemma 1. For the caching problem described in Section II, the following optimization problem provides a lower bound on the average rate for caching with uncoded placement: s.t. (2), (3), and (10) 2 The assumption of F being large is common in the existing works [20]- [32]. In practice, the file size typically exceeds 1 kbit or 1 Mbit, for which the formulation in P0 becomes accurate, i.e., a n,l F ∈ Z. Even in the case of very small F , P0 can be viewed as the relaxed version of the original problem with a n,l F ∈ Z. We can round the optimal solution a n,l F to P0 to the nearest integer solution. The same discussion applies to P1 and P2 in Section IV as well.
where T (D) {d : Unique(d) = D, d ∈ N K }, and R lb (D; a) is the lower bound for the distinct file set D with the placement vectors {a n , n ∈ D}, given by where π : I |D| → D is any bijective map from I |D| to D.
Proof: See Appendix A. Note that P1 is a min-max problem. It can be cast in its epigraph form by moving (12) to the constraints. The resulting equivalent problem is a linear program (LP), which can be solved by standard LP solvers.
Remark 3. Recall that to simplify the cache placement problem, the cache placement vector a for the MCCS is formed under Condition C1. Here, we point out that although P1 is w.r.t. the same cache placement vector a, the formation of R lb (D; a) in (12) does not require us to impose Condition C1). This can be seen from the derivation in the proof in Appendix A. Thus, the lower bound in P1 is not based on Condition C1, but rather the placement a that satisfies Condition C1 turns out to be optimal to P1. Remark 4. We point out a subtle yet key difference between our lower bound from the existing ones. In characterizing the caching limit, the challenge in the existing works lies in analyzing the gap between the lower bound and the specific caching scheme used. For example, it is difficult to see the connection between the lower bound obtained in [31] and any achievable scheme for comparison. Although the derivation of the lower bound in Lemma 1 is based on the approach in [31], as shown in Appendix A, we are able to transform the lower bound into an equivalent form, which satisfies Condition C1. This transformation is the result of the in-depth understanding of the cache placement optimization formulation for the MCCS. It paves the way for connecting the lower bound in P1 (and the lower bound in P2 below) to the optimized MCCS and analyze the gap.
Given that the popularity-first placement approach has been considered in the existing works under nonuniform file popularity, we also develop a popularity-first-based lower bound, by imposing the popularity-first placement constraint (4) to the placement vector a in P1, as shown below.
Lemma 2. (Popularity-first-based lower bound) For the caching problem described in Section II, the following optimization problem provides a lower bound on the average rate for caching under popularity-first cache placement: s.t. (2), (3), and (10) where R lb (D; a), for a ∈ Q, is given by where φ : I |D| → D is the bijective map in the decreasing order of file popularity, i.e., p φ(1) ≥ · · · ≥ p φ(|D|) .
Proof: See Appendix B. Note that for R lb (D; a) in (12), by restricting a ∈ Q, we can remove the max operation and simplify the expression to (14). Due to the restriction a ∈ Q in P2, the lower bound given by P1 is also a lower bound for P2. In the following theorem, we show that for K = 2 users, there is no loss of optimality by restricting to popularity-first placements. Theorem 1. For K = 2, P1 and P2 are equivalent.
Proof: See Appendix C Theorem 1 indicates that, with nonuniform file popularity, for K = 2 users, the popularity-first placement is an optimal solution to P1, regardless of the values of N , p, and M . In other words, the general lower bound for any caching with uncoded placement given by P1 is attained by some a ∈ Q. We will use this result in Section V-B to further show that the MCCS under the popularity-first placement is an optimal caching scheme under uncoded placement for K = 2 users. For K > 2 users, except for some special cases, the same conclusion turns out to be challenging to prove in general. Although the same conclusion cannot be shown analytically, we provide numerical results in Section VIII to show that the two lower bounds by P1 and P2 are equal in general, and a very small gap is observed only in some limited cases.

V. MEMORY-RATE TRADEOFF CHARACTERIZATION
In this section, we compare the average rate of the optimized MCCS in P0 and that of the popularity-first-based lower bound in P2 to show the tightness of the bound and how optimal the MCCS is. Consider N files with arbitrary popularity distribution p and local cache size M . We partition the number of users K and their file requests in three possible regions to compare P0 and P2: Region 1: K = 2; Region 2: K > 2,Ñ (d) = K (no redundant file requests); Region 3: K > 2,Ñ (d) < K (with redundant file requests).
Note that Region 2 is possible only when K ≤ N , and Region 3 is when there are multiple users requesting the same file. We summarize our results below: • For both Regions 1 and 2, we prove that the popularityfirst-based lower bound in P2 is tight, i.e., the optimized MCCS in P0 attains this lower bound. In particular, in Region 1, by Theorem 1, the result further indicates the MCCS is an optimal caching scheme (with the optimized popularity-first placement) for any caching with uncoded placement. Also, the tight bound reveals that there is no loss of optimality by zero-padding in coded messages in the MCCS in Regions 1 and 2. • For Region 3, we show that there may be a performance gap between the optimized MCCS and the popularityfirst-based lower bound in P2. The loss is due to zeropadding in the coded messages in the delivery phase, which we will discuss and quantify. Nonetheless, we provide some special cases or a condition for which P0 and P2 are equivalent. Also, our numerical evaluation of the optimized MCCS and the lower bound in Section VIII show that, in general, the loss only appears in some limited scenarios and is very small. We describe the above results in detail in the following subsections. Note that the difference between P0 and P2 is only in the expression of the average rate objective function. Thus, we focus on comparingR MCCS (a) andR lb (a), for a ∈ Q. Note that for P0, R MCCS (d; a) in (7) is a function of demand vector d, while for P2, R lb (D; a) in (14) is a function of distinct file subset D. Furthermore, R MCCS (d; a) in (7) contains the max operation, while R lb (D; a) in (14) does not. Thus, it is challenging to connect and compare the two objective functions, especially given the complicated delivery scheme in the MCCS. Our first step is to reformulate the expression of R MCCS (d; a) such that we can represent the max operation in a way to connect the expression to the lower bound R lb (D; a) in the later steps.

A. Expression ofR MCCS (a)
We first rewrite the expression ofR MCCS (a) in (8) for the MCCS. Given placement vector a ∈ Q, we rewrite R MCCS (d; a) in (7) for demand vector d as where we regroup the terms in R MCCS (d; a) based on the size |S| of the non-redundant groups, and U is the leader group for d. Define ψ : I |U | → U as a bijective map from I |U | to the leader group U, such that the requested (distinct) files by the users in U are ordered in decreasing popularity, i.e., . Recall that φ : [|D|] → D defined in Lemma 2 maps the indices of distinct files with the same file popularity order. Also, from Definition 1 of the leader group U, we note that |D| = |U| =Ñ (d), for given d. Thus, by the relation of D and U, the two mappings ψ(·) and φ(·) are based on the same file popularity order, and we have d ψ(i) = φ(i), i = 1, . . . ,Ñ (d). Also, since a ∈ Q, we have To evaluate the inner max operation in (15), we partition the coded messages into different categories according to the user subsets. Recall that cache subgroup A l+1 is the set of all K l+1 user subsets with size |S| = l + 1. Among these user subsets, there are K−1 l subsets containing user ψ(1) in U. Letā ψ(1),l denote the size of the coded message corresponding to each of these K−1 l subsets containing user ψ(1). From (16), we havē Similarly, there are K−2 l user subsets in A l+1 that contain user ψ(2) but not ψ(1) in U. Denote the size of the coded message corresponding to each of these subsets asā ψ(2),l , then Following the above, in general, the number of user subsets in A l+1 that include ψ(i) but not ψ(1), . . . , ψ(i − 1) is K−i l . Letā ψ(i),l denote the size of the coded message corresponding to each of these subsets. Then, we havē Averaging (8) can be rewritten as where T (D) is defined below P1 in Lemma 1. With the expression in (21), we now can directly compare the minimum average rate in P0 with P1 or P2.

B. Region 1: K = 2
In this region, We have the following result on the optimality of the MCCS.
Theorem 2. For a caching problem of N files with popularity distribution p and local cache size M , for K = 2 users, the minimum average rate of the optimized MCCS in P0 attains the lower bound given by P1. Thus, the MCCS is optimal for caching with uncoded placement.
Proof: We first show that P0 and P2 are equivalent, i.e., R MCCS (a) =R lb (a), for a ∈ Q. Comparing the two expressions in (13) and (21), we only need to examine R MCCS (d; a) and R lb (D; a). For K = {1, 2}, we have |D| =Ñ (d) = 1 or 2. We consider these two cases separately below.
Case 1)Ñ (d) = 1: In this case, two users request the same file. Based on the relation of two mappings ψ(·) and (14) is given by Since d ψ(1) = φ(1), from (22) and (23), we have Case 2)Ñ (d) = 2: In this case, two users request two different files, i.e., D = {φ(1), φ(2)}. By the popularity-first placement in (4), we have a φ(1),l ≥ a φ(2),l , l = 1, 2. Following this, for K = 2 andÑ (d) = 2, R lb (D; a) in (14) is given by For R MCCS (d; a) in (20), we have Note that by definition,Ã 2 2 contains those user subsets of size two that include ψ(2) but not ψ(1). However, for K = 2, when excluding ψ(1), the size of the user subset can only be 1. Thus, we haveÃ 2 2 = ∅ for K = 2. In addition, we havẽ (26) is given by where the second equality is due to (16)- (18), and the third equality is because of d ψ(i) = φ(i). From (24) and (27), we conclude that for Thus, P0 and P2 are equivalent. By Theorem 1, P0 and P1 are equivalent for K = 2, and we complete the proof. For K = 2, Theorem 2 shows that the lower bound given by P1 is tight. It also indicates two types of optimality for the MCCS: 1) the optimality of the popularity-first cache placement for the MCCS; and 2) the optimality of the MCCS for caching with uncoded placement. The tight bound enables us to characterize the exact memory-rate tradeoff for caching with uncoded placement. Also, as discussed in Section III-B, zeropadding is commonly used in constructing coded messages. The optimality of the MCCS reveals that there is no loss of optimality to use zero-padding in the MCCS for the coded message.
C. Region 2: K > 2,Ñ (d) = K When K ≤ N , this region may occur if every user requests a different file, i.e., |D| = |U| =Ñ (d) = K. Note that under this condition, the probability of each file being requested has changed. Let p i|K denote the conditional probability of file i being requested, givenÑ (d) = K. Then, in this case,R lb (a) in (13) of P2 is rewritten as andR MCCS (a) in (21) for the MCCS is rewritten as Comparing the expressions in (28) and (29) in P0 and P2, respectively, we have the following result.
Theorem 3. For the caching problem of N files with distribution p and local cache size M , in Region 2, the optimized MCCS in P0 attains the popularity-first-based lower bound given by P2.
Proof: To prove the result, we only need to show that (20). Since every user requests a distinct file, the leader group includes all users and can be written as U = {ψ(1), . . . , ψ(K)}. Thus, for any user subset S, we have S ⊆ U. From the definition ofÃ l+1 i below (19), this means that for any S ∈Ã l+1 i , ψ(i) ∈ S ⊆ U, and d ψ(i) is the most popular file requested in S. By (16) (19) is given bȳ Since (20) is given by which is the same as R lb (D; a) in (14) forÑ (d) = K. Thus, we conclude thatR lb (a) =R MCCS (a) in Region 2. Following Theorem 3, we provide a few conclusions below.
1) The optimality of Condition C1: Note that in Region 2, the MCCS and the CCS are identical. Recall from Section III-B that the MCCS uses a modified coded delivery strategy: it removes the redundant coded messages in that of the CCS when there are redundant requests. In Region 2, since all file requests are distinct, there is no redundant message in the delivery phase. As a result, the MCCS is the same as the CCS.
For the CCS, Condition C1 has been proven to be the property of the optimal cache placement for the CCS [24]. Recall that we have imposed Condition C1 in Section III-A to simplify the cache placement problem for the MCCS. The above discussion, along with the result in Region 1, reveals that in Regions 1 and 2, Condition C1 in fact holds true for the optimal cache placement of the MCCS, i.e., the size of each subfile W n,S in file W n is the same for the user subset of the same size |S|. The result is summarized in the following corollary.
Corollary 1. Condition C1 is the property of the optimal cache placement for the MCCS in Regions 1 and 2.
Note that the optimality of Condition C1 for the MCCS has only been demonstrated through numerical results in [32]. We show in Corollary 1 that this property holds for the MCCS in Regions 1 and 2.
2) The optimality of popularity-first placement: Recall from Remark 1 that the popularity-first placement is proven to be optimal for the CCS. Thus, along with the result in Region 1, we have the following corollary. Corollary 2. In Regions 1 and 2, the optimal cache placement for the MCCS is a popularity-first placement, i.e., there is no loss of optimality by restricting a ∈ Q in P0.
Proof: In Region 1, the claim immediately follows Theorem 2, as discussed at the end of Section V-B. In Region 2, the MCCS is the same as the CCS. It has been shown that the optimal placement for the CCS is a popularity-first placement [24]. Thus, the claim immediately follows for the MCCS in Region 2.
3) Effect of zero-padding in coded caching: As mentioned in Remark 2, for nonuniform file popularity, zero-padding is a common technique to form the coded messages for both the CCS and the MCCS. However, its impact on the performance has never been discussed or studied. The tight lower bounds shown in Theorems 2 and 3 indicate that the use of zeropadding does not cause any loss, as stated below. Note that for Case 1 in Region 1 discussed in Section V-B, when both users request the same file, it is clear from (6) that zero-padding is not used in the coded message. However, for Case 2 in Region 1, when two users request two different files, zero-padding may be applied in the coded messages. Similarly, in Region 2, for K users requesting K different files, each coded message contains subfiles of different requested files, and thus, the message may need to be zero-padded.
4) The optimality of the CCS: The above analysis focuses on the MCCS. Since the MCCS and the CCS are the same in Region 2, the result in Theorem 3 also leads to several conclusions on the optimality of the CCS below, which has not been shown in the literature.

4.i) Zero-padding:
Note that the delivery strategy of the CCS does not distinguish whether file requests are the same or different, i.e., it treats all the requested files as distinct files to form the coded messages. 3 This means that for any demand vector d, the CCS is effectively equivalent to the case wheñ N (d) = K for the MCCS in Region 2, where all users request different files. In other words, the average rate of the CCS (averaged over all d's) is equal to that of the MCCS in Region 2. 4 Assuming all files are treated as distinct in the delivery phase, we can also construct a lower bound under popularityfirst placement. Given how P2 in Region 2 is formulated, this lower bound is equivalent to P2. By Theorem 3, it follows that the average rate of the CCS attains the popularity-first-based lower bound, assuming all files are treated as distinct. Since the popularity-first placement is optimal for the CCS under nonuniform file popularity [24], this tight lower bound also means that zero-padding used in the CCS incurs no loss. We state this conclusion below. Corollary 4. Using zero-padding for the CCS incurs no loss of optimality under nonuniform file popularity.

4.ii) The optimality of Condition C1:
Following the discussion above, the tight lower bound also implies that Condition C1 is the property of the optimal cache placement for the CCS. This is by the similar argument used in the zeropadding discussion. Although this optimality has been proven in [24], the method used there is more involved. Our results in Theorem 3 provides a simpler alternative proof of this result.

4.iii)
The optimality of the CCS: Following the discussion in a), since the CCS attains the lower bound given by P2, we also conclude that the CCS is optimal in terms of the average rate for caching under popularity-first placement, if all file requests are distinct (i.e., the worst-case). Note that in the literature of caching with uncoded placement, for uniform file popularity, the optimality of the CCS in terms of the worstcase peak rate in the case of K ≤ N has been proven [18], [19]. For nonuniform file popularity, although many existing works study the cache placement for the CCS [20]- [26], [30], the optimality of the CCS in this case has never been studied or known. Our result sheds some light on the optimality of the CCS under nonuniform file popularity.  (14), we see that they contain the same number of coded messages, which is The only difference between R MCCS (d; a) and R lb (D; a) is the size of each coded message |C S |, i.e.,ā S ψ(i),l and a φ(i),l . Thus, we need to examine whetherā S ψ(i),l is the same as a φ(i),l , for any S. To better explain our result, in the following, we first use an example to show thatā S ψ(i),l and a φ(i),l may be different, which is due to zero-padding.
Example: Assume that two users request file φ(1), the most popular file in the requests. One user is in the leader group U, denoted by ψ(1) and the other from a redundant group, (14), for all K−2 l user subsets that include user ψ(2) but not user ψ(1), the size of coded messages corresponding to these subsets is always a φ(2),l (d ϕ(2) = φ(2)). Now, for R MCCS (d; a) in (20), consider user subset S that includes users ψ(2) and k ′ but not user ψ(1). From (18), the size of coded messages for S isā S ψ(2),l = a d k ′ ,l = a φ(1),l , due to zero-padding. Since a φ(1),l ≥ a φ(2),l , in this case, zero-padding by the MCCS results in a longer coded message for user subsets that include user k ′ but not the leader user ψ(1), as it always zero-pads the subfile to the longest one in the subset. Similar to the above example, in general,ā S ψ(i),l and a φ(i),l may be different for a coded message corresponding to user subset S, where S includes a user from a redundant group who requests a file that is more popular than the rest requested by all other users in S. For the MCCS using the popularity-first placement in (4), the coded message is zero-padded to the size of the subfile requested by that user from the redundant group (the largest). In contrast, for the lower bound R lb (D; a), the size of the coded message is that of the subfile of the most popular file (φ(i), for some i) among files requested by those users in the leader group, i.e., S ∩ U. This mismatch between R MCCS (d; a) and R lb (D; a) leads to a possible gap between the average rate of the optimized MCCS and the lower bound in P2. To further quantify the difference between R MCCS (d; a) and R lb (D; a), we re-express R MCCS (d; a) in the following lemma.  (20) can be rewritten as  (14) for P2 are equivalent, given by Following this, (32) is given by Based on the above, we conclude that in fact P0, P1 and P2 are all equivalent in this case. To explain this result, note that as discussed below Corollary 3, when only one file is requested by all the users, zero-padding is not used in the coded message. As a result, zero-padding is avoided, and the optimized MCCS remains to be optimal in this case.
Case ii):N (i) = 0, i = 1, . . . ,Ñ (d) − 1. In this case, only file φ(Ñ (d)), i.e., the least popular file in D, has redundant requests. In other words, all the users in the redundant group request file φ(Ñ (d)). From (32) and (14), for a ∈ Q, it is straightforward to show that Thus, P0 and P2 are equivalent in this case. To explain this, we see that in this case, the redundant file requests are "controlled," i.e., the redundant requests are for the least popular file φ(Ñ (d)) in D. By the popularity-first placement condition in (4), we have a 1,l ≥ a 2,l ≥ . . . ≥ a φ(Ñ(d)),l for l = 1, . . . , K. As a result, the size of the coded message |C S |, for any user subset S, is always the size of the subfile of the most popular file requested by the users in S that belong to the leader group U, i.e., S ∩ U. Thus, (19) is given bȳ We see from the above that although zero-padding is used, the size of the coded messageā S ψ(i),l is the same as a φ(i),l for any S. As a result, there is no loss of optimality caused by zero-padding in this case.
Finally, we point out that althoughR MCCS (a) andR lb (a) are generally not the same due to the existence of redundant requests as discussed above, the optimal placement solution a * to P0, P1, and P2 can still be the same for some values of M and p. This also leads to the following case wherē R MCCS (a) =R lb (a): Case iii): If P0, P1 and P2 result in the same optimal solution a * that satisfies a * 1 = · · · = a * N , thenR MCCS (a * ) = R lb (a * ). In this case, since a * 1,l = . . . = a * N,l , for any l, all the subfiles in a coded message C S in (4) for user subset S have the same size. Thus, there is no zero-padding and no potential waste. One obvious example is the special case of uniform file popularity, where the optimal a * n 's are all identical and the same for P0, P1, and P2. In this case, the same result R MCCS (a * ) =R lb (a * ) has been shown in [16]. Below, we provide a simple proof of our statement.
Since (20) is written as Similarly, R lb (D; a) in (12) of P1 and (14) of P2 can both be rewritten as Thus, from (11) and (21), we conclude that for a * 1 = . . . = a * N , Remark 5. In Region 3, as discussed earlier, when there are redundant file requests, zero-padding the message to the largest subfile may lead to a loss in the average rate, and the optimality of the MCCS is uncertain. Despite this, we have identified three special cases where the optimized MCCS still achieves the lower bounds. In these cases, either zeropadding is avoided, or the redundant file requests are carefully controlled, such that the potential loss by zero-padding is eliminated. These findings may further guide us in designing caching schemes to reduce the loss caused by zero-padding. One possible solution is to create as many subfiles of equal size as possible during the placement phase. Coincidentally, such an approach was also exploited in [31] for N = 2 files, where a placement scheme was proposed to create equal subfile size and was shown to be an optimal caching scheme with uncoded placement for two files.

VI. OPTIMAL CACHE PLACEMENT FOR THE MCCS
Due to the more complicated delivery scheme by the MCCS, finding the optimal cache placement for the MCCS under nonuniform file popularity is challenging, and the problem has not been solved. The optimal cache placement for the CCS under nonuniform file popularity has recently been obtained in [26]. In this section, through reformulating P0, we show that the cache placement problem has a similar structure to that for the CCS. As a result, the optimal cache placement structure for the MCCS inherits that for the CCS characterized in [26]. Extending the results from the CCS, we present a simple algorithm to compute the optimal cache placement solution for the MCCS. In the following, we first reformulate P0 and then describe the optimal cache placement solution structure.

A. Reformulation of P0
It is straightforward to see that at the optimum, the cache memory is fully utilized, and the local cache constraint (3) is attained with equality, which can be replaced by N n=1 K l=1 K − 1 l − 1 a n,l = M.
Finally, for a ∈ Q, the expression of the average ratē R MCCS (a) in (8) can be simplified as [32] where P i,u,n is the joint probability of i) having u distinct file requests; and ii) file W n being the i-th least popular file among 5 The expression in (8) can be simplified to (41) by utilizing the properties of the popularity-first placement with ordered a n,l 's to eliminate the max operation in (8). The expression ofR MCCS (a) in (41) can be evaluated in polynomial time instead of the exponential time required in (8), which simplifies P0.
files requested by all the users that are not in the leader group {d k : k ∈ K\U}. The expression of P i,u,n is derived in [32], which is lengthy and non-essential in developing our results. Therefore, we omit it here but only point out that P i,u,n is not a function of a.
The expression ofR MCCS (a) in (41) is a weighted sum of a n,l 's. Define g n [g n,0 , . . . , g n,K ] T , with Also, from (2) and (39) b T a n = 1, n ∈ N , N n=1 c T a n = M.
1) Connection to the cache placement problem for the CCS: As described in Section III-B, the MCCS only delivers the non-redundant messages, while the CCS delivers the coded messages corresponding to all the user subsets. The expression ofR MCCS (a) in (41) explicitly shows this difference by grouping all the messages into the first term and the redundant messages into the second term. The cache placement optimization problem for the CCS was formulated in [26, problem P2]. It essentially minimizes the first term in (41), with all the constraints on a being the same as in P3, except that the expression of g n is different. Based on this structural similarity, the structural properties of the placement obtained for the CCS can be straightforwardly extended to P3 for the MCCS.
Since the cache placement result is the direct extension from that of the CCS in [26], in the following, we focus on describing the placement structure and omit the details of derivations or proofs.

B. Optimal Cache Placement: Solution Structure
A major challenge in solving P3 is that the placement vectors in the optimal cache placement a can be all different, depending on the file popularity distribution. It turns out that the number of distinct placement vectors in the optimal a is limited to at most three. We first define file group below.
Definition 5 (File group). A file group is a subset of N that contains all files with the same cache placement vector, i.e., for any two files W n and W n ′ , if their placement vectors a n = a n ′ , then they belong to the same file group.
The first structural property, in terms of file groups, of the optimal cache placement for the MCCS is provided in the following theorem. Theorem 4. For N files with any file popularity distribution p, and for any K and M ≤ N , there are at most three file groups under the optimal cache placement {a n } for P3.
Proof: The only differences between P3 and the the cache placement optimization problem for the CCS in [26] are the expressions of g n , which does not affect the arguments used in the proof of [26,Theorem 1]. Thus, the same result straightforwardly applies to the optimal solution of P3 for the MCCS.
Theorem 4 indicates that, regardless of N , p, and M , there are at most three unique values among the optimal placement vectors {a n }. This leads to three possible cases: one, two, or three file groups. In the following, we provide the optimal placement solution {a n } for each case.
1) One file group: In this case, the optimal cache placement vectors are identical for all files, i.e., a 1 = · · · = a N . Under this structure, the cache placement problem is reduced to that under uniform file popularity (i.e., all files have the same cache placement vector), of which the optimal solution has been obtained in closed-form [46], which is identical to that for the CCS under uniform file popularity [30]. Specifically, the optimal placement a n , for any file n ∈ N , has at most two nonzero elements, which is given as follows: , a n,lo+1 = v−⌊v⌋ ( K ⌈v⌉ ) , l o = ⌊v⌋ a n,l = 0, ∀ l = l o or l o + 1 (45) where v MK N . In particular, when v is an integer, the optimal a n has only one nonzero element: a lo = 1/ K lo for l o = M K/N , and a l = 0, ∀ l = l o .
2) Two file groups: In this case, there are only two unique placement vectors in {a n }, i.e., a 1 = · · · = a no = a no+1 = · · · = a N , for some n o ∈ {1, . . . , N − 1}. We use a no and a no+1 to represent the two unique placement vectors for the first and the second file group, respectively. Definē a n [a n,1 , . . . , a n,K ] T as the sub-placement vector in a n . It specifies the subfiles stored in the local cache, and a n,0 specifies the subfile kept at the server. Letā n 1 0 denote that there is only one positive element inā n , and the rest are all 0's.
There are several structural properties of the optimal placement in the two-file-group case. They are all direct extensions from the optimal cache placement of the CCS [26]. We summarize them below. Following the properties in Proposition 1, the optimal placement solution for P3 can be one of the following two structures: 1)ā no+1 = 0; 2)ā no+1 1 0. For the completeness, we briefly present the optimal placement solutions below, referring the derivation details to [26].
Case 1:ā no+1 = 0. This condition means that no cache is allocated to the files in the second group. By (2), we have a no+1 = [1, 0, 0, . . .] T . To determine a no for the first group, we treat the first n o files as a new database. Then, the cache placement problem is reduced to the one in the one-file-group case in Section VI-B1. Therefore, the solution is the same as in (45), except that N is replaced by n o , and thus, v = M K/n o .
Note that this two-file-group case and the one-file-group case in Section VI-B1 can be combined as follows: The optimal a no is given by (45), for v = M K/n o with n o ∈ N . The optimal n * o depends on (N, p, M, K), which can be determined via a 1-D search over n o that gives the minimum R MCCS (a), whereR MCCS (a) is computed using the closedform expression in (41). For the overall algorithm, please refer to [26,Algorithm 1], with the only exception that the average rate is computed usingR MCCS (a) in (41).
Case 2:ā no+1 1 0. In this case, only one element in a no+1 is nonzero. Assume a no+1,lo > 0, for some l o ∈ K, and a no+1,l = 0, ∀l = l o , l ∈ K. By Property 2 in Proposition 1, the element that is different betweenā no andā no+1 can be either at index l o or some l 1 , for l 1 = l o . Thus, for a ∈ Q, there are only two possible cases for (a no , a no+1 ): 2.i) a no,lo > a no+1,lo > 0; or 2.ii) a no,l1 > a no+1,l1 = 0, for some l 1 = l o , l 1 ∈ K. We present the solution in each of these two cases: Case 2.i) a no,lo > a no+1,lo > 0: In this case, the only different element betweenā no andā no+1 is at position l o , i.e., the nonzero element a no+1,lo inā no+1 . Also, by Property 3 in Proposition 1, a no,lo is the only nonzero element in a no , and a no,l = a no+1,l = 0, for ∀l = l o , l ∈ K. Forā no+1 , there are two unknown nonzero elements a no+1,0 and a no+1,lo . Solving the unknown elements in a no and a no+1 using constraints (43) and (44), the optimal (a no , a no+1 ) is given by where n o ∈ {1, . . . , N − 1}, and the nonzero element position Case 2.ii) a no,l1 > a no+1,l1 = 0, l 1 = l o : In this case, the only different element betweenā no andā no+1 is at position l 1 , which is one of the zero elements inā no+1 . It follows that a no,lo = a no+1,lo > 0. Since a no,0 = 0 (by Property 3 in Proposition 1), a no has two nonzero elements, a no,lo and a no,l1 , and the rest are all 0's. For a no+1 , there are two unknown nonzero elements, a no+1,0 and a no+1,lo = a no,lo, and the rest are all 0's. Thus, we have three unknown elements a no,lo = a no+1,lo , a no,l1 , and a no+1,0 to determine in a no and a no+1 . Solving these unknown elements using constraints (43) and (44), the optimal (a no , a no+1 ) is given by Remark 6. We have shown two different structures of the optimal placement in Cases 1 and 2 for the two file groups. In Case 1, all the cache is allocated to the first group. For each file in this group, all its subfiles are cached at different users, and the cache placement is identical for these files, regardless of their popularity. In the existing works, the twofile-group strategies proposed in [22], [23] coincide with this structure, although they are proposed for a decentralized cache placement, and the methods to determine n o are heuristic or suboptimal. In Case 2, each file in the second group is partially cached at the users and partially remains at the server. This placement structure has never been proposed in the literature. For this placement structure, coding opportunity between the two file groups is explored to minimize the average rate.
3) Three file groups: Under this structure, there are three unique placement vectors in {a n }, i.e., a 1 = . . . = a no = a no+1 = . . . = a n1 = a n1+1 = . . . = a N , for 1 ≤ n o < n 1 ≤ N − 1. We use a no , a no+1 and a n1+1 to represent the three unique cache placement vectors for the first, second, and the third file group, respectively. Following the proof of [26,Proposition 4], it is straightforward to show the same result in the following holds for the MCCS as well: All the memory is allocated to the first two file groups and the optimal cache placement vector for the third group is a n1+1 = [1, 0, 0, . . .] T .
Following the above, we treat those n 1 files in the first two groups as a new database. The cache placement problem for these first two groups is essentially reduced to the previous two-file-group case. Since a no+1 = a n1+1 , we haveā no+1 = a n1+1 = 0. This means thatā no+1 includes at least one nonzero element. Therefore, the cache placement (a no , a no+1 ) belongs to the case of two file groups withā no+1 1 0 (for the second group) in Case 2 of Section VI-B2. For given n 1 , the optimal solution for (a no , a no+1 ) can be obtained from (46) or (47), except that N is replaced by n 1 ∈ {2, . . . , N }.
The final optimal {a n } is obtained by searching over all possible values of n 1 ∈ {2, . . . , N }, 6 n o ∈ {1, . . . , n 1 − 1}, and l o , l 1 ∈ K for the optimal tuple (n o , n 1, l o , l 1 ) that results in minimumR MCCS . For the overall algorithm, please refer to [26,Algorithm 3]. The algorithm simply computesR MCCS using a closed-form expression for at most (N −1)(N −2)K 2 /2 times with different values of (n o , n 1 , l o , l 1 ), which can be computed efficiently in parallel.
Remark 7. Note that the three-file-group structure for cache placement described above has never been proposed in the literature for coded caching. Although [23] has considered three file groups as a choice in a mixed caching scheme, this three-file-group cache placement is only used with uncoded delivery and is only invoked in some rare cases, which is different from coded caching. In contrast, for the three-filegroup structure of the optimal cache placement described above, coding opportunity among three file groups is explored to minimize the average rate.

4) The Optimal Cache Placement Solution:
In summary, by exploring optimization techniques and the structural properties of the solution, we can obtain the optimal cache placement solution for the MCCS in P0. By Theorem 4, the optimal cache placement problem P3 is reduced to a search among three possible file grouping structures (from one to three file groups). From Sections VI-B1 to VI-B3, using the closed-form expressions for {a n } andR MCCS (a), we obtain the candidate optimal placement for each file-group case. The final optimal placement is the one in these three solutions that results in the minimumR MCCS (a). Since the overall algorithm only involves parallel evaluations of closed-form expressions, the algorithm is very simple with low computational complexity.
Beyond the analytical solution, our results also bring important insight into cache placement under nonuniform file popularity. We have fully characterized the inherent file grouping structure of the optimal cache placement solution for the MCCS. Theorem 4 shows that regardless of the file popularity distribution, there are at most three file groups in the optimal cache placement, with files in the same group having the same cache placement. We categorize these three groups as "most popular," "moderately popular," and "non-popular" files. The result indicates that despite different file popularities, the caching method only distinguishes files in these three categories to determine the cache placement strategies. In other words, these three categories reflect the caching strategies: for the "most popular" file group, cache all their subfiles; for the "moderately popular" file group, each file is cached only partially, and the rest is stored at the server; and for "nonpopular" file group, the files are not cached but solely stored at the server. How many file groups and for which category, i.e., the mapping of files to the three categories, depend on the file popularity distribution p and the ratio of total cache size among users to the server database size KM/N . In our numerical results, we will demonstrate these file group structures in cache placement in Table IV as the cache size varies. This can be determined by the optimal cache placement solution via our algorithm above.
Finally, we note that the optimal cache placement solution for the MCCS obtained in this section allows us to quantitatively evaluate the gap between the optimized MCCS and the lower bounds in P1 and P2 in Region 3 discussed in Section V-D.
Remark 8. We point out that, for nonuniform file popularity, although the MCCS and the CCS have the same set of candidate optimal cache placement structures and solutions, the final optimal cache placement for the two schemes may be different due to different expressions of the average rate (e.g., R MCCS (a) in P0). We will demonstrate this in our numerical studies in Section VIII. Note that this is in contrast to uniform file popularity, where the optimal cache placements of the MCCS [16] and the CCS [30] are exactly the same.

VII. MEMORY-RATE TRADEOFF FOR NONUNIFORM FILE POPULARITY AND SIZE
In the previous sections, we have focused on files of equal size. 7 In this section, we extend our study on the memory-rate tradeoff in caching to the more general case where both file popularity and size are nonuniform among files. We extend the cache placement optimization formulation in Section III to this case and propose a lower bound for caching with uncoded placement. By comparing the average rates of the optimized MCCS and the lower bound, we characterize the exact memory-rate tradeoff for K = 2 users.

A. The Optimized MCCS
Consider each file of different size. We assume that file W n has F n bits. Recall in Section II that, for uniform file size, subfile size a n,l and cache size M are normalized by the file size and defined in the unit of file. For files with different sizes, we remove this normalization. Instead, for each file n ∈ N , we define the size of each subfile in bits: a n,l |W n,S |, for |S| = l. Likewise, the cache size M is now defined in bits. Accordingly, we rewrite file partition constraint (2) as K l=0 K l a n,l = F n , n ∈ N .
With the above redefinitions of a n,l and M , the expressions of the cache size constraint (3) and the average delivery ratē R MCCS (a) in (8) still remain the same under the nonuniform file popularity and size. The cache placement optimization problem for the MCCS to minimizeR MCCS (a) under nonuniform file popularity and size is formulated as follows:  (48) whereR MCCS (a) is given in (8), and the objective and constraint functions are now all expressed in bits. 7 In practice, files with nonuniform sizes could also be tailored into files with uniform size which are treated separately with different popularities [15], [47], [48].
Note that different from P0, which is restricted to the popularity-first placement a ∈ Q, the problem size of P4 grows exponentially with K. We will not further study the simplification of P4 and its performance in this paper. For the CCS, a similar problem under nonuniform file popularity and size has been studied, and tractable techniques have been developed to simplify the optimization problem with good performances [30]. The techniques can be adopted here for P4 for the MCCS, due to the similarity between the two caching schemes. In the following, we focus on the characterization of the memory-rate tradeoff under nonuniform file popularity and size, which is unknown in the literature.

B. Memory-Rate Tradeoff Characterization
To characterize the memory-rate tradeoff for nonuniform file popularity and size, we first propose a lower bound on average rate under uncoded placement. The lower bound is a straightforward extension of the lower bound in P1 by considering nonuniform file popularity and size, instead of nonuniform file popularity only.
Recall that for nonuniform file popularity and size, a n,l and M are defined in bits in Section VII-A. For a given a, the expression of the lower bound on the average ratē R lb (a) in (11) remains unchanged (except that it is in bits). Since constraints (3), (10), and (48) remain the same, we can formulate an optimization problem to minimizeR lb (a) to obtain the lower bound for caching with uncoded placement under nonuniform file popularity and size. The result is given by the following lemma.  (48) whereR lb (a) is given in (11), and the objective and constraints are all in bits.
Comparing P4 and P5, we obtain the following result on the optimized MCCS for the two-user case.
Theorem 5. For the caching problem of N files with nonuniform file popularity and size, for K = 2 users, the minimum average rate for the optimized MCCS in P4 attains the lower bound given by P5.
Proof: See Appendix E.
Remark 9. The tight lower bound shown in Theorem 5 shows the optimality of the optimized MCCS for K = 2 users. It enables us to characterize the exact memory-rate tradeoff for K = 2 users under nonuniform file popularity and size. The optimality of the MCCS also indicates that there is no loss of optimality by zero-padding. For the general case of K > 2 users, our numerical studies in Section VIII will show that the gap between the optimized MCCS (P4) and the lower bound (P5) is very small in general. RLFU-GCC [22] Mixed Grouping [23] Optimized CCS [26] Optimized MCCS Lower Bound, P2 Lower Bound, P1

VIII. NUMERICAL RESULTS
In this section, we provide numerically studies on the optimized MCCS and the lower bounds obtained for caching with uncoded placement. We first consider files of the same size but with nonuniform popularity. We study the performance of the optimized MCCS (under the optimal cache placement obtained in Section VI), the lower bound in P1, and the popularity-first-based lower bound in P2. For comparison, we also consider a few existing strategies proposed for the CCS, including i) the optimized CCS [26], ii) a two-file-group scheme named RLFU-GCC [22], and iii) the mixed caching strategy [23].
LetR denote the average rate obtained by different schemes or the lower bound. Fig. 2 shows the average rateR vs. M for N = 7 and K = 4. We generate the file popularities using the Zipf distribution with p n = n −θ / N i=1 i −θ , where θ is the Zipf parameter. We set θ = 0.56 (used in [30], [49], [50]). We see that, among all the caching strategies, the optimized MCCS results in the lowest average rate for all values of M . The two lower bounds in P1 and P2 are numerically identical, indicating the optimality of popularityfirst placement. Comparing the optimized MCCS with the lower bounds, we see that the gap between them is very small and only appears at a small range of cache size values M ∈ [2.5, 3.5]. The gap between the average rates of the optimized MCCS and the optimized CCS mainly exists for small cache size M ∈ [0, 2] and shrinks as M increases.
As discussed in Section VI-B, although the candidate solutions of the optimal cache placement for the MCCS and the CCS are the same, the optimal placements may be different for the two schemes. To see this difference, for the same setting considered in Fig. 2, we show the optimal {a n } for the two schemes for M = 1, 2, 6 in Tables I, II, and III, respectively, representing small, moderate, and large cache size. For a small cache size (M = 1), the optimal placements for the MCCS and the CCS in Table I      into subfiles of two sizes, with one stored at the server (a n,0 ) and the rest in each user's local cache. In contrast, for the CCS, files {W 5 , W 6 , W 7 } are solely stored at the server, and files {W 1 , · · · , W 4 } are stored in each user's local cache. This difference on the placement is the main cause of the performance gap between the MCCS and the CCS in Fig. 2. For moderate to large cache size (M = 2, 6), Tables II and  III show that the optimal cache placements are the same for the MCCS and the CCS. However, we see from Fig. 2 that for M = 2, there is a small observable gap between the average rates of the two schemes, with that of the MCCS being lower; and for M = 6, the average rates of the two are nearly identical. The explanation for this trend is that there exist more redundant messages for M = 2 with the placement in Table II than those for M = 6 with the placement in Table III. To elaborate more on this, note that for given demand d, the number of redundant groups in cache subgroup , which decreases with l. They determine the number of redundant messages. The indices of the nonzero elements in a n are l = 1, 2 for M = 2, and l = 3, 4 for RLFU-GCC [22] Mixed Grouping [23] Optimized CCS [26] Optimized   2] indicates that, at a small cache size, coded caching is more sensitive to the cache placement to achieve the largest caching gain.
To evaluate the performance with other file popularity distribution, we consider the case studied in [23] with N = 12, K = 5, and a step-function for file popularity distribution: p 1 = 7/12, p n = 1/18, n = 2, . . . , 7, and p n = 1/60, n = 8, . . . , 12.   We choose a small cache size M = 1 to show clearly the performance gap between the caching schemes and lower bounds. The optimized MCCS always performs the best among all the caching strategies for any θ. The lower bound in P1 and the popularity-first-based lower bound in P2 are numerically identical. Also, we observe that the gap between the average rates of the optimized MCCS and the lower bounds only exists at a moderate range of θ and is very small in general. In contrast, the gap between the MCCS and the CCS is obvious at all values of θ. This demonstrates the advantage of the MCCS over other caching schemes at a small value of M . We now verify the structure of the optimal cache placement for the MCCS described in Section VI-B. We generate file popularity using Zipf distribution with θ = 1.2. We obtain the optimal placement solution {a n } using our proposed algorithm and verify that it matches the optimal solution obtained by solving P0 numerically. As an example, for N = 9 and K = 4, Table IV shows the optimal {a n } that is obtained by solving P0 numerically, for M = 3, 4, 7. For M = 3, we see that there are two file groups {W 1 , . . . , W 4 } and {W 5 , . . . , W 9 } under the optimal placement. This structure matches Case 1 in Section VI-B2, where the cache is entirely allocated to the first file group with the most popular files, and the files in the second file group are only stored at the server (a 5,0 = . . . = a 9,0 = 1). The optimal a n 's for the first group are identical with only one nonzero element. This means those files are partitioned into subfiles of the same size and are stored at users' local caches. With a small cache size, this placement result is intuitive: only a few popular files are cached, and the rest remain in the server; thus, the optimal cache placement results in two file groups. For M = 4, a different cache placement strategy is shown, where the files are divided into three file groups. The optimal {a n } is as described in Section VI-B3 for the three-file-group case: no cache is allocated to the third file group {W 7 , W 8 , W 9 }, and a portion of the file is cached for W 6 in the second file group; for the first file group, Optimized CCS [30] Optimized MCCS, P4 Lower Bound, P5 files are partitioned into subfiles of a single size and are all stored at different users. For M = 7, the optimal placement has only a single file group, where all the files have the same placement as discussed in Section VI-B1. From Table IV, we see that the file popularity differences are more critical for the placement when the case size M is limited (relative to the total files in the database). As M becomes large, all the files tend to have the same placement into the user caches.
The file sizes are set as [F 1 , . . . , F N ] = [9/6, 8/6, 7/6, 6/6, 5/6, 4/6, 3/6] kbits. The file size and popularity combinations are chosen similar to those used in [30], which simulate a practical scenario where file popularity and size are relatively uncorrelated. In Fig. 5, we compare the optimized MCCS in P4, the lower bound in P5, and the optimized CCS [30]. The gap between the optimized MCCS and the lower bound only exists for M ∈ [1,3] and is very small. Moreover, the optimized MCCS outperforms the optimized CCS. The gap between the two again is obvious at small values of M , and it reduces to zero as M becomes large.

IX. CONCLUSION
In this paper, for a caching system with nonuniform file popularity, we characterized the memory-rate tradeoff for caching with uncoded placement. We focused on the MCCS with cache placement optimized in the class of popularity-first placement for average rate minimization. We then provided a general lower bound and a popularity-first-based lower bound for caching with uncoded placement. For K = 2 users, the two lower bounds are shown to be identical, and the optimized MCCS attains the bounds, providing the exact memory-rate tradeoff. For K > 2 users with distinct requests, the optimized MCCS attains the popularity-first-based lower bound. Additionally, the results in these two regions reveal the following results for the MCCS unavailable in the literature: The popularity-first placement is optimal, and zero-padding used in coded delivery incurs no loss of optimality. For K > 2 users with redundant requests, our analysis showed that a gap might exist between the optimized MCCS and the lower bounds due to zero-padding. However, numerical results show that such loss only exists in some limited cases and is very small in general.
We next characterized the optimal solution structure of the popularity-first cache placement for the MCCS under nonuniform file popularity. It was shown to have a simple file-grouping structure of at most three file groups, depending on the relative cache size to the database size. We obtained the closed-form placement solution for each candidate structure, which enabled us to compute the optimal solution through a simple algorithm. Finally, we extended our study of memoryrate tradeoff to the case where files are nonuniform in both popularity and size. We showed that the optimized MCCS attains the lower bound for K = 2 users and characterizes the exact memory-rate tradeoff. Numerical results again showed that, for general settings, the gap between the optimized MCCS and the lower bound exists in limited cases and is very small.
whereǎ π(i),l is the total number of bits from file π(i) ∈ D cached by exactly l users. In our definition of a π(i),l , subscript l refers to the user subset size |S| = l in a cache subgroup A l , which is identical to that inǎ π(i),l . Following the definitions ofǎ π(i),l and a π(i),l , we have a π(i),l =ǎ π(i),l / K l , since there are K l user subsets in A l . Thus, for given a, we can equivalently express (49) as Using the above expression, by averaging R lb (D; a) over all possible D ⊆ N , we obtain the general lower boundR lb (a) the average rate w.r.t a in (11). The final lower bound on average rate is obtained by optimizing a to minimizeR lb (a), which is shown in P1.

APPENDIX B PROOF OF LEMMA 2
Proof: The popularity-first-based lower bound is essentially a simplification of P1 in Lemma 1, by restricting to the set of popularity-first placement vectors: a ∈ Q. We need to show that R lb (D; a) in (12) can be simplified into (14) for a ∈ Q. For ∀D ⊆ N , since φ(·) is such that p φ(1) ≥ · · · ≥ p φ(|D|) , by the definition of popularity-first placement in (4), for a ∈ Q, we have a φ(i),l ≥ a φ(i+1),l , l ∈ K, i = 1, . . . , |D| − 1. (51) Since K−i l is a decreasing function of i, for a ∈ Q, we have Thus, we remove the max operation in (12) to arrive at the simplified expression in (14), for a ∈ Q.

APPENDIX C PROOF OF THEOREM 1
Proof: For P1, consider a feasible cache placement vector a and any l o ∈ K. Define ϕ : I |N | → N as a bijective map for a such thatâ ϕ(1),lo ≥ . . . ≥â ϕ(N ),lo . Note that ϕ(·) depends onâ and l o .
Based on the above four categories of D, we rewriteR lb (a) in (11)   We now evaluate the differences between R lb (D;â) and R lb (D;ã), for l o = 1, 2.
By (55), the sum of the first two terms in (73) is the same for a andã. By (69), the third term in (73) is identical forâ and a. Thus, we have R lb (D;â) − R lb (D;ã) = 0, D ∈ D 3 .

APPENDIX E PROOF OF THEOREM 5
Proof: To show that P4 and P5 are equivalent for K = 2, we will show thatR lb (a) =R MCCS (a), for any given a. To do so, we only need to compare R MCCS (d; a) and R lb (D; a). For K = {1, 2}, we have |D| = 1 or 2. We consider the two cases separately below.
Since two users request different files, we have the leader group U = {1, 2}.