Adeel Malik
email: ma-lik@eurecom.fr

Berksan Serbetci

Petros Elia
email: elia@eurecom.fr

Coded Caching in Networks With Heterogeneous User Activity

Keywords: Coded caching, shared caches, load balancing, heterogeneous networks, femtocaching

This work elevates coded caching networks from their purely information-theoretic framework to a stochastic setting, by exploring the effect of random user activity and by exploiting correlations in the activity patterns of different users. In particular, the work studies the K-user cache-aided broadcast channel with a limited number of cache states (i.e., the content stored at the cache of a certain user), and explores the effect of cache state association strategies in the presence of arbitrary user activity levels; a combination that strikes at the very core of the coded caching problem and its crippling subpacketization bottleneck. We first present a statistical analysis of the average worst-case delay performance of such subpacketization-constrained (state-constrained) coded caching networks, and provide computationally efficient performance bounds as well as scaling laws for any arbitrary probability distribution of the user-activity levels. The achieved performance is a result of a novel user-to-cache state association algorithm that leverages the knowledge of probabilistic user-activity levels.

We then follow a data-driven approach that exploits the prior history on user-activity levels and correlations, in order to predict interference patterns, and thus better design the caching algorithm. This optimized strategy is based on the principle that users that overlap more, interfere more, and thus have higher priority to secure complementary cache states. This strategy is proven here to be within a small constant factor from the optimal. Finally, the above analysis is validated numerically using synthetic data following the Pareto principle. To the best of our understanding, this is the first work that seeks to exploit user-activity levels and correlations, in order to map future interference and design optimized coded caching algorithms that better handle this interference.

I. INTRODUCTION

T HE volume of mobile data traffic is rapidly growing, and soon existing networks will not have enough bandwidth resources to support this dramatically increasing demand [START_REF]Cisco Annual Internet Report[END_REF]. In this context, caching offers a promising means of increasing efficiency by proactively storing part of the data at the network edge [START_REF] Shanmugam | Femtocaching: Wireless content delivery through distributed caching helpers[END_REF], including at wireless communication stations as well as on end-user devices [START_REF] Golrezaei | Basestation assisted device-to-device communications for high-throughput wireless video networks[END_REF], [START_REF] Ji | Wireless device-to-device caching networks: Basic principles and system performance[END_REF].

While generally caching is based on the idea that storing data can allow a receiving node to have easy access to its own desired file, recent work has shown the powerful effects of exploiting the existence of the aforementioned desired file at the caches of other receiving users [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF]- [START_REF]Fundamental limits of combinatorial multi-access caching[END_REF]. In interferencelimited scenarios -such as in downlink settings exemplified by the broadcast channel where each user has access to their own cache and requires their own distinct file -the findings in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] suggest that a proper use of caching can allow for single multicast transmissions to simultaneously serve many users each having their own distinct demands. This breakthrough in the way caching is perceived, is based on the ideas of index coding which tells us that when the stored content in one user's cache overlaps with other users' requests, one can design multicast transmissions (in the form of XORs or other linear combinations of desired data), that allow for rapid delivery of any possible set of demands. Index codingwhich is generally a computationally hard problem [START_REF] Langberg | On the hardness of approximating the network coding capacity[END_REF] -has received significant attention in a literature that has explored its performance limits [START_REF] Bar-Yossef | Index coding with side information[END_REF], [START_REF] Maleki | Index coding-an interference alignment perspective[END_REF], as well as its strong connections to the network coding problem [START_REF] Fragouli | Network coding fundamentals[END_REF], [START_REF] Effros | An equivalence between network coding and index coding[END_REF]. One main difference between index coding and network coding is that index coding specializes on cache-related cases in the sense that it considers receivers that benefit from side-information, which in our case can be found, for example, in the caches.

Motivated by index coding and its ability to exploit receivers' side information to create coded multicasting opportunities for users requesting different files, the seminal work in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] has introduced the concept of coded caching. This work revealed that -under some theoretical assumptions, and in the presence of a deterministic information-theoretic broadcast framework -the use of caching at the receivers can allow the simultaneous delivery of an unlimited number of userrequests, with a limited delay. This astounding conclusion was achieved by carefully designing a combinatorial clique-based cache placement algorithm, and a synergistic delivery scheme that enables transmitting independent content to multiple users at a time. In essence, coded caching associates each receiving user to its own cache state in a manner that allows for the custom design of a long sequence of high-capacity index coding problems that are served one after the other. Each cache state defines the content stored at the cache of a certain user. As we will see soon though, this requirement that each user has their own cache state, is an assumption that -in essence -cannot hold.

To see this, let us quickly recall that in its original setting, coded caching considers a unit-capacity single-stream broadcast channel (BC), where a transmitting base station (BS) has access to a library (catalog) of N unit-sized files, and serves K receiving users each equipped with a cache of size equal to the size of M files, or equivalently equal to a fraction γ = M N of the library. In this context, the work in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] provides a novel placement and delivery scheme that can serve any set of K simultaneous requests with a worst-case delivery time of T = K (1-γ) 1+Kγ ≈1-γ γ . This ability to serve a theoretically ever-increasing number of users with a bounded delay, is a direct result of exploiting the cache-enabled multicasting opportunities that allow for delivery to Kγ + 1 users at a time.

As suggested above though, coded caching has a serious Achilles' heel. In particular, for the above performance to be guaranteed, coded caching requires that each user be allocated their own specifically-designed cache state (cache content), which -without delving into the esoteric details of coded caching -effectively requires the partitioning of each libraryfile into K Kγ subpackets. This number scales exponentially in K, and thus requires files to be of truly astronomical sizes. Thus given any reasonable constraint on the file sizes, the number of cache states is effectively forced to be reduced, and the aforementioned coding gains are indeed diminished to gains that are considerably less than Kγ + 1. What this filesize constraint (also known as the subpacketization bottleneck) effectively forces is the reduction of the number of cache states 1 to some Λ ≪ K, which -under the basic principles of the clique-based cache-placement in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] -allows for a smaller subpacketization level Λ Λγ ≪ K Kγ at the expense though of a much reduced coding gain Λγ + 1 ≪ Kγ + 1 and a much larger delay T = K (1-γ) 1+Λγ which is now unbounded. As a consequence, this reflects the case of having the normalized cache size γ at the end users being typically very low, which is consistent with the common assumption considered in standard wireless cellular settings [START_REF] Shanmugam | Finite-length analysis of caching-aided coded multicasting[END_REF], [START_REF] Lampiris | Adding transmitters dramatically boosts codedcaching gains for finite file sizes[END_REF]. Even though there are several alternative solutions in the literature that deal with the subpacketization bottleneck [START_REF] Tang | Coded caching schemes with reduced subpacketization from linear block codes[END_REF], [START_REF] Malik | Stochastic coded caching with optimized shared-cache sizes and reduced subpacketization[END_REF], we consider the aforementioned setting i) for its simplicity, and ii) for its versatility, e.g., for its applicability in practical and promising coded caching enabled settings, c.f., [START_REF] Lampiris | Adding transmitters dramatically boosts codedcaching gains for finite file sizes[END_REF].

Another important -perhaps rather oversimplified-assumption that detracts coded caching from practical settings is that an overwhelming majority of aforementioned codedcaching studies solely focus on the deterministic informationtheoretic broadcast framework, which are mostly based on the assumption of deterministic topologies. We believe that it is of utmost importance to transcend this boundary, and study coded caching in more realistic wireless communication networks, which are random in nature. In this context, this work elevates coded caching from their purely information-theoretic framework to a stochastic setting where the stochasticity of the networks originates from the heterogeneity in users' request behaviors. Analyzing the coded caching in the presence of such heterogeneity can help us understand the actual gains of the coded caching in stochastic network settings. In addition, these studies are poised to play a vital role in resolving the bottlenecks of coded caching. Let us see an example of how incorporating the users' request behavior in coded caching can help us resolve the subpacketization bottleneck.

Example 1. Let us assume that we want to design a coded caching system for K = 200 cache-enabled users, each with a normalized storage capacity of γ = 0.1. Now consider that we study the users' request behavior, and find a pattern that users are divided into four groups, where each group consists of 50 distinct users, and at any given instance, only 50 users belonging to the same group request a file, while the other 150 users are inactive. With this knowledge, for each group, we can design a separate coded caching system. As at any instance only one of the groups is active, from [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF], the worstcase delivery time takes the form = 50(1-0.1) 1+5 = 45 6 = 7.5, and the required subpacketization rate is 50 5 ≈ 2.12 × 10 6 . However, if we do not exploit this knowledge, and design a single coded caching system for all K = 200 users, then at any instance, when only 50 users are requesting, from [START_REF] Yu | The exact ratememory tradeoff for caching with uncoded prefetching[END_REF], the corresponding worst-case delivery time takes the form ( In practice, users' request behavior will be stochastic, and we may not see such clear patterns as we observed in the simplistic scenario illustrated above. However, this example serves as a baseline to underline the need of exploring the user activity patterns in the design of coded caching in realistic wireless communication networks.

A. Exploiting the connection between coded caching, complementary cache states, user-activity levels and user-activity correlations

The performance of coded caching in the presence of an inevitably reduced number of cache states, has been explored in various works that include the work in [START_REF] Jin | A new order-optimal decentralized coded caching scheme with good performance in the finite file size regime[END_REF] which introduced a new scheme for this setting, and the work in [START_REF] Parrinello | Fundamental limits of coded caching with multiple antennas, shared caches and uncoded prefetching[END_REF] which established the fundamental limits of the state-limited coded caching setting, by deriving the exact optimal worstcase delivery time as a function of the user-to-cache state association profile that represents the number of users served by each cache.

As we witness in the above works, in order to maintain the ability to jointly exploit multicasting opportunities, users must be associated to complementary cache states that are carefully designed and which cannot be identical. The above findings reveal that a basic problem with the state-limited scenario (where Λ ≪ K) in coded caching is simply the fact that if two or more users are forced to share the same cache state (i.e., the same content in their caches), then these users generally do not have the ability to jointly receive a multicasting message that can be useful to all. Such statelimited scenario results in a large deterioration in performance, irrespective of the user-to-cache association policy. What we additionally learn from the work in [START_REF] Malik | Fundamental limits of stochastic shared-cache networks[END_REF] is that if the users are assigned to cache states at random, then this randomness imposes an additional unbounded performance deterioration that is a result of 'unfortunate' associations where too many users share the same cache state. That is why the task of userto-cache state association is important.

At the same time though, coded caching experiences a certain synchronization aspect, which is a direct outcome of the fact that users are expected to be partially asynchronous in their timing of requesting files. Hence, the notion of time is of essence. This asynchronicity has a negative aspect, but also a positive one; both of which we explore here. On the one hand, having only a fraction of the users appear simultaneously, implies a smaller number of users that can simultaneously participate in coded caching and thus implies potentially fewer multicasting opportunities and thus a smaller coding gain. On the other hand, such asynchronicity implies less instantaneous interference. This is where user activity levels come into the picture, and this is where user activity correlations can be exploited. In essence -as it will become clearer later on -any users that are correlated in terms of their activity in time, should be associated to different cache states, as this is essential in using caches for handling their mutual interference. Therefore, having the information of some users rarely request data at the same time, allows us to allocate them the same cache state resource. In essence, users that overlap more, interfere more, and thus have higher priority to secure complementary cache states. This optimization effort is particularly important because, as we recall, these resources are indeed scarce. By exploring user activities and learning from their history, we are able to predict interference patterns, and then we are able to assign cache states accordingly.

Recently, [START_REF] Liao | Fundamental rate-memory tradeoff for coded caching in presence of user inactivity[END_REF] presented a work to find the optimal cache placement and delivery strategies in the presence of user inactivity. This work considers identical inactivity levels for all users, i.e., at any transmission instance, each user is inactive with the same constant probability, and the placement strategy follows standard centralized and decentralized policies. The work in [START_REF] Liao | Fundamental rate-memory tradeoff for coded caching in presence of user inactivity[END_REF] provides an optimization-oriented delivery scheme, and compares the proposed scheme with the standard and genie-aided (i.e., assuming full knowledge of user activity in the placement phase) scheme presented in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF]. Differently from [START_REF] Liao | Fundamental rate-memory tradeoff for coded caching in presence of user inactivity[END_REF], our work focuses on both identical and arbitrary activity levels, and also considers a data-driven approach for user activities. We consider the subpacketizationconstrained uncoded cache placement scheme, and we provide the fundamental bounds, and characterize the scaling laws of the average delay. In a nutshell, our work, to the best of our knowledge, is the first work that seeks to exploit arbitrary user-activity levels and correlations, in order to map future interference and provide optimized caching algorithms that better handle this interference by presenting the fundamental bounds and the scaling laws of the problem.

B. Notations

Throughout this paper, for n a positive integer, we use the notation [n] ≜ [1, 2, . . . , n] , ∀n ∈ Z + . We use A/B to denote the difference set that consists of all the elements of set A not in set B. Unless otherwise stated, logarithms are assumed to have base 2. We also use the following asymptotic notation: i) f (x) = O(g(x)) will mean that there exist constants a Active User Inactive User Cache BS BC-link Library and c such that

f (x) ≤ ag(x), ∀x > c, ii) f (x) = o(g(x)) will mean that lim x→∞ f (x) g(x) = 0, iii) f (x) = Ω(g(x)) will be used if g(x) = O(f (x)), iv) f (x) = ω(g(x)) will mean that lim x→∞ g(x)
f (x) = 0, and finally v) f (x) = Θ(g(x)) will be used if f (x) = O(g(x)) and f (x) = Ω(g(x)). We use the term polylog(x) to denote the class of functions k≥1 O((log x) k ) that are polynomial in log x.

II. SYSTEM MODEL & MAIN CONTRIBUTION

In this section, we present the system model and the communication process that consists of placement and delivery phases in detail. We then propose our metrics of interest, and finally wrap up the section by listing our contributions.

A. Network setting

We consider a cache-aided wireless network, which consists of a base station and K cache-enabled receiving users. The base station (BS) has access to a library of N equisized files F = [F 1 , F 2 , . . . , F N ] and delivers content via a broadcast link to K receiving users. Each user k ∈ [K] is equipped with a cache of normalized storage capacity of γ ≜ M N ∈ [0, 1], and requests a file from the content library with probability p k . We use p = [p 1 , p 2 , . . . , p K ] to denote the users activity level vector. At any instance, if a user k is requesting a file, then we say that the user k ∈ [K] is an active user. Naturally K p = K k=1 p k is the expected number of active users. Figure 1 depicts an instance of our cache-aided wireless network.

The communication process consists of two phases; the placement phase and the delivery phase. During the placement phase, each user's cache is filled with the content from the library, and this phase is oblivious to the upcoming number of users in the delivery phase, as well as is oblivious to the upcoming file demands. The delivery phase begins with the active users simultaneously requesting one file each, and continues with the BS delivering this content to the users. This phase is naturally aware of the demands of the active users, as well as is aware of the content cached at each user. Placement phase: We consider the subpacketizationconstrained uncoded cache placement scheme based on [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF]. The placement phase consists of two parts. In the first part, we generate the cache states based on the maximum allowable subpacketization B max of a file. Each cache state defines the content stored in the cache of a certain user. For a maximum allowable subpacketization B max of a file, we define the maximum number of cache states as follows

Λ = arg max k≤K k kγ ≤ B max .
Two users assigned to the same cache state must store the exact same content in their caches. We will see later that having fewer cache states generally implies a smaller DoF. Given the number of cache states Λ, each file F i ∈ F is partitioned into Λ t distinct equisized subpackets, where t ≜ Λγ, and where t ∈ [Λ] holds 2 . Then we index each subpacket of a file by a distinct subset τ ⊆ [Λ] of size t. The set of indexed subpackets corresponding to file F i ∈ F is given by

{F i,τ : τ ⊆ [Λ], |τ | = t}. The content corresponding to each cache state λ ∈ [Λ] is then given by C λ = {F i,τ : i ∈ [N ], λ ∈ τ, τ ⊆ [Λ], |τ | = t} ,
where each cache state consists of |C λ | = N Λ-1 t-1 subpackets, which abides by the cache-size constraint since N

( Λ-1 t-1 ) ( Λ t ) = M .
In the second part, each user's cache is filled with the content of one of the cache states λ ∈ [Λ]. The employed user-tocache state association is defined by a matrix G = [0, 1] Λ×K , of which the (λ, k) element g λ,k takes the value 1 if user k is storing the content of cache state λ ∈ [Λ], else g λ,k = 0. We denote by G λ the set of users caching the content of cache state λ ∈ [Λ]. Delivery phase: The delivery phase commences with each active user requesting a single file from the content library. In line with the common assumptions in coded caching, we assume that requests are generated simultaneously by active users, and that each active user requests a different file. During this phase, the BS is aware of the user-to-cache state association matrix G. Once the BS receives the users' requests, it commences delivery of the coded subpackets over a unit-capacity 3 error-free broadcast link. Here, together with the aforementioned optimal placement, we also consider the optimal 4 multi-round delivery scheme of [START_REF] Jin | A new order-optimal decentralized coded caching scheme with good performance in the finite file size regime[END_REF], [START_REF] Parrinello | Fundamental limits of coded caching with multiple antennas, shared caches and uncoded prefetching[END_REF]. At any instance of the problem, the cache load vector given the userto-cache state association G is denoted by

V = [v 1 , . . . , v Λ ],
where v λ represents the number of active users that are associated with cache state λ ∈ [Λ]. Additionally, we use L = [l 1 , . . . , l Λ ] = sort(V) to be the profile vector, which is the sorted (in descending order) version of the cache load vector V.

For any cache load vector V such that sort(V) = L, multiround delivery scheme in [START_REF] Jin | A new order-optimal decentralized coded caching scheme with good performance in the finite file size regime[END_REF], [START_REF] Parrinello | Fundamental limits of coded caching with multiple antennas, shared caches and uncoded prefetching[END_REF] proposes to complete the delivery in l 1 rounds, where the content is delivered to at most one user from each cache state λ ∈ [Λ] in each round. The delivery time corresponding to each round j ∈ [l 1 ] is given as

( Λ t+1 )-( Λ-A j ) t+1 ) ( Λ t )
, where A j denotes the number of users being 2 In this work t = Λγ is a function of maximum allowable subpacketization Bmax of a file and it represents the reduced achievable coded caching gain of t + 1 = Λγ + 1 as compared to Kγ + 1 of conventional coded caching setting with no limit on the subpacketization of a file. 3 Here the capacity is measured in units of file. 4 Optimality here refers to the performance of the scheme over the traditional (deterministic) coded caching problem with constant user activity. served in delivery round j. Then, for any cache load vector V such that sort(V) = L, the delivery time takes the form l1 j=1

( Λ t+1 )-( Λ-A j ) t+1 ) ( Λ t )
.

Example 2. For K = 7, Λ = 4, and γ = 0.5, each file is divided into Λ Λγ = 4 2 = 6 subpackets. The set of indexed subpackets corresponding to each file F i ∈ F is given by F i,(1,2) , F i, [START_REF]Cisco Annual Internet Report[END_REF][START_REF] Golrezaei | Basestation assisted device-to-device communications for high-throughput wireless video networks[END_REF] , F i, [START_REF]Cisco Annual Internet Report[END_REF][START_REF] Ji | Wireless device-to-device caching networks: Basic principles and system performance[END_REF] , F i,(2,3) , F i, [START_REF] Shanmugam | Femtocaching: Wireless content delivery through distributed caching helpers[END_REF][START_REF] Ji | Wireless device-to-device caching networks: Basic principles and system performance[END_REF] , F i, [START_REF] Golrezaei | Basestation assisted device-to-device communications for high-throughput wireless video networks[END_REF][START_REF] Ji | Wireless device-to-device caching networks: Basic principles and system performance[END_REF] .

The content corresponding to each cache state is given by

C 1 = {F i,τ : τ ∈ [(1, 2),(1, 3),(1, 4)], i ∈ [N ]} , C 2 = {F i,τ : τ ∈ [(1, 2),(2, 3),(2, 4)], i ∈ [N ]} , C 3 = {F i,τ : τ ∈ [(1, 3),(2, 3),(3, 4)], i ∈ [N ]} , C 4 = {F i,τ : τ ∈ [(1, 4),(2, 4),(3, 4)], i ∈ [N ]} .
Now, let us move to the content delivery phase. Let us consider the case of V = [3, 2, 1, 1], i.e., the case where users 1, 2 and 3 are associated to cache state 1, and request the content F 1 , F 2 , and F 3 , respectively; users 4 and 5 are associated to cache state 2, and request F 4 and F 5 , respectively; user 6 is associated to cache state 3, and requests F 6 ; and user 7 is associated to cache state 4, and requests F 7 . Following the multi-round delivery scheme of [START_REF] Jin | A new order-optimal decentralized coded caching scheme with good performance in the finite file size regime[END_REF], [START_REF] Parrinello | Fundamental limits of coded caching with multiple antennas, shared caches and uncoded prefetching[END_REF], the BS delivers the content in three rounds.

In the first round of delivery, the BS serves user 1 associated to cache state 1, user 4 associated to cache state 2, user 6 associated to cache state 3, and user 7 associated to cache state 4. For this round, the BS transmits the following four subpackets. [START_REF] Shanmugam | Femtocaching: Wireless content delivery through distributed caching helpers[END_REF][START_REF] Golrezaei | Basestation assisted device-to-device communications for high-throughput wireless video networks[END_REF] .

F 1,(2,3) ⊕ F 4,(1,3) ⊕ F 6,(1,2) , F 1,(2,4) ⊕ F 4,(1,4) ⊕ F 7,(1,2) , F 1,(3,4) ⊕ F 6,(1,4) ⊕ F 7,(1,3) , F 4,(3,4) ⊕ F 6,(2,4) ⊕ F 7,
After this round user 1, 4, 6, and 7 can successfully decode their requested files using the content received from the BS and the content stored in their own caches. The delivery time corresponding to this round is

( 4 3 )-( (4-4)
3 ) ( 42 ) = 4 6 . Then, in the second round of delivery, the BS serves user 2 associated to cache state 1, user 5 associated to cache state 2. As there is no active user associated to cache states 3 and 4, for this round, the BS transmits the following four subpackets [START_REF] Golrezaei | Basestation assisted device-to-device communications for high-throughput wireless video networks[END_REF][START_REF] Ji | Wireless device-to-device caching networks: Basic principles and system performance[END_REF] .

F 2,(2,3) ⊕ F 5,(1,3) , F 2,(3,4) , F 2,(2,4) ⊕ F 5,(1,4) , F 5,
After this round user 2 and 5 can successfully decode their required file using the content received from the BS and the content stored in their own caches. The delivery time corresponding to this round is

( 4 3 )-( (4-2)
3 ) ( 42 )

= 4 6
Then, in the final round of delivery, the BS only serves user 3 associated to cache state 1. As there is no active user associated to cache states 2, 3, and 4, for this round, the BS transmits the following three subpackets F 3,(2,3) , F 3,(2,4) , F 3, [START_REF] Golrezaei | Basestation assisted device-to-device communications for high-throughput wireless video networks[END_REF][START_REF] Ji | Wireless device-to-device caching networks: Basic principles and system performance[END_REF] .

After this round user 1 can successfully decode the required file using the content received from the BS and the content stored in their own cache. The delivery time corresponding to this round is

( 4 3 )-( (4-1)
3 ) ( 42 ) = 3 6 . This completes the content delivery phase, which results in a delivery time of 11 6 .

Remark 1. For the case where multiple users request common files, a reduced delivery time can be obtained by using the delivery strategy proposed in [START_REF] Yu | The exact ratememory tradeoff for caching with uncoded prefetching[END_REF] at each delivery round.

B. Metrics of interest

To capture the randomness in user activity, we considerfor any given user-to-cache state association matrix G -the averaging metric

T (G) ≜ E V [T (V)] = V P (V)T (V), (1)
where P (V) is the probability of V given the user-to-cache state association G, and where T (V) is the delivery time5 needed to complete the delivery of requested files given a certain cache load vector V associated to matrix G. For any cache load vector V such that sort(V) = L, the informationtheoretically optimal delivery time -achieved with the multiround delivery scheme [START_REF] Jin | A new order-optimal decentralized coded caching scheme with good performance in the finite file size regime[END_REF], [START_REF] Parrinello | Fundamental limits of coded caching with multiple antennas, shared caches and uncoded prefetching[END_REF] -takes the form

T (L) = Λ-t λ=1 l λ Λ-λ t Λ t . (2)
Thus, the average delay takes the form

T (G) = L∈L P (L)T (L) = Λ-t λ=1 L∈L P (L)l λ Λ-λ t Λ t = Λ-t λ=1 E[l λ ] Λ-λ t Λ t , (3)
where L describes the set of all possible profile vectors L, where P (L) is the probability of a profile vector L given the user-to-cache state association G, and where E[l λ ] is the expected number of active users in the λ-th most loaded cache, again given G.

Our interest is in finding the optimal user-to-cache association that minimizes the average delay. This corresponds to the following optimization problem.

Problem II.1:

min G T (G) (4) subject to Λ i=1 g i,k = 1 ∀k ∈ [K]. (5)

C. Our contribution

In this work, we analyze a state-constrained coded caching network of K cache-aided users with Λ cache states, when users have different activity levels, and the association between users and cache states is subject to an arbitrary grouping strategy G. Our aim is to provide analytical bounds on the performance. We will do so either in a manner that is numerically tractable, or in the form of asymptotic approximations that offer direct insight. The following are our contributions, step by step.

• In Section III-A, for any arbitrary user activity level vector p and any arbitrary user-to-cache state association G, -We derive upper and lower bounds on the average delay T (G). These bounds can be evaluated in a computationally efficient manner. -We characterize the scaling laws of T (G) which take clear and insightful forms. -Based on the insights from the derived bounds, we

propose a new user-to-cache association algorithm that seeks to minimize the average delay.

• In Section III-B, we analyze the special case of uniform user activity statistics, and uniform user-to-cache state association G. For this setting, we provide analytical upper and lower bounds on the performance, and show that the bounds have a bounded gap between them and thus a bounded gap to the optimal. Then, we proceed to characterize the exact scaling laws of T (G). • In Section IV, we extend our analysis to the data-driven setting, where -in designing the caching policywe are able to learn from the past S different demand vectors. Using this bounded-depth user-request history, we propose a heuristic user-to-cache state association algorithm which is simple to implement and which we prove here to be at most at a factor of log S log log S from the optimal. This factor, as we argue later below, remains less than 3-4 for any reasonable scenario 6 , which is validated numerically using synthetic data following the Pareto principle.

• In Section V, we perform extensive numerical evaluations that validate our analysis.

III. MAIN RESULTS: STATISTICAL APPROACH

In this section, we present our main results on the performance of a coded caching network of K cache-aided users and Λ cache states, where the user-activity levels follow an arbitrary probability distribution p and where the association between users and cache states is subject to an arbitrary association strategy G.

We can see from (3) that for any given user-to-cache state association G and user-activity statistics p, the exact evaluation of (3) is computationally expensive especially for large system parameters, as the creation of L is an integer partition problem, and the cardinality of L is known to be growing exponentially with system parameters K and Λ [START_REF] Stojmenović | Fast algorithms for generating integer partitions[END_REF].

Motivated by this complexity, we here proceed to provide computationally efficient bounds on the performance. After doing so, we resort to asymptotic analysis of the impact of G and p on the performance, and provide an insightful characterization of the scaling laws of this performance. Finally, based on the insights from these scaling laws, we propose a heuristic user-to-cache state association algorithm that aims to minimize the worst-case delivery time.

A. Performance analysis with arbitrary activity levels

In this subsection, we present the statistical analysis of our problem for the general setting of an arbitrary user-to-cache state association strategy G and an arbitrary activity level vector p. Crucial to our analysis for this setting will be the mean µ λ = k∈G λ p k and the variance σ 2 λ = k∈G λ p k (1 -p k ) of the number of active users that are caching the content of cache state λ ∈ [Λ]. Now we proceed to present our first result which is the characterization of faster-to-compute analytical bounds on the performance.

Theorem 1. In a state-constrained coded caching network of Λ cache states, K cache-aided users with normalized cache capacity γ and activity level vector p, the average delay T (G) for a given user-to-cache state association strategy G is bounded as follows

T (G) ≤ Λ-t 1+t A- A-1 x=0 max 0, 1-Λ+ Λ λ=1 F 1 (λ, x) , (6)
T (G) ≥ Λ -t 1 + t t Λ -1 A - A-1 x=0 Λ λ=1 F 2 (λ, x) Λ + Λ -t 1 + t K p Λ Λ -t -1 Λ -1 , ( 7
)
where t = Λγ, A = max {|G λ |} Λ λ=1
, where G λ is the set of users caching the content of cache state λ,

F 1 (λ, x) =        0 if 0 ≤ x ≤ µ λ -1 F bin |G λ |, µ λ |G λ | , x if µ λ ≤ x ≤ |G λ | 1 if x > |G λ |, (8)
F 2 (λ, x) = F bin |G λ |, µ λ |G λ | , x if 0 ≤ x ≤ µ λ -1 1 if x > µ λ -1, (9)
where F bin (n, q, x) = x i=0 n i q i (1 -q) n-i and where

µ λ = k∈G λ p k .
Proof. The proof is deferred to Appendix A.

Remark 2. The bounds in Theorem 1 can be computed in a computationally-efficient manner, as for each λ ∈ [Λ], their evaluation only requires to compute the binomial cumulative distribution function

F bin |G λ |, µ λ |G λ | , x for all x ∈ [0, 1, 2, • • • , |G λ |] of a random variable with |G λ |
independent trials and µ λ |G λ | success probability 7 . Next, we proceed to our next result, which provides the asymptotic analysis of the average delay T (G), in the limit of large Λ and K. Let us quickly recall that µ λ = k∈G λ p k and σ 2 λ = k∈G λ p k (1 -p k ) are respectively the mean and variance of the number of active users that are associated with cache state λ.

Theorem 2. In a state-constrained coded caching network of Λ cache states, K cache-aided users with normalized cache capacity γ and activity level vector p, the average delay T (G) for a given association strategy G scales as

T (G) = O     K p Λ + Λ i=1 (σ 2 i + (µ i -µ) 2 )   Λ -t 1 + t   , (10) and
T (G) = Ω K p Λ Λ -t 1 + t , (11)
where

µ = 1 Λ Λ λ=1 µ λ = Kp Λ . Proof. This proof is deferred to Appendix B.
Furthermore we have the following.

Corollary 1. Any association strategy G that satisfies

Λ i=1 (σ 2 i + (µ i -µ) 2 ) = O Kp Λ
is order-optimal.

Proof. Since the lower bound in ( 11) is independent of the association strategy G, this implies that the optimal average delay T * (corresponding to an optimal association Ĝ) is lower bounded by

T * = Ω K p (1 -γ) 1 + t . ( 12
)
Therefore any association G for which the gap factor

Λ i=1 (σ 2 i + (µ i -µ) 2 ) scales as O Kp Λ
would be order optimal as the scaling order of (10) yields O

Kp(1-γ) 1+t
, thus, giving the exact scaling law of

T (G) = Θ Kp(1-γ) 1+t
.

Following the insights from Corollary 1, we now propose an algorithm that solves Problem II.1.

1) Algorithm 1:

The algorithm aims to heuristically minimize

Λ i=1 (σ 2 i + (µ i -µ) 2
), and it works in K iterations, where for each iteration the algorithm finds a user and cache state pair ( k, λ) in accordance to step 02 of this algorithm. Consequently user k is assigned cache state λ. 7 In theory, F bin |G λ |, µ λ |G λ | , x needs to be calculated for all values of x ∈ [0, |G λ |]. However, it is known that there exists a x ∈ [0, |G λ |], where

F bin |G λ |, µ λ |G λ | , x ≈ 1.
By De Moivre-Laplace Theorem, it is known that binomial distribution can be approximated by the normal distribution in the limit of large |G λ |, and the well-known 68-95-99.7 rule states that

x << |G λ |. Since F bin |G λ |, µ λ |G λ | , x ≈ 1 for any x ≥ x, both (8)
and ( 9), and consequently ( 6) and ( 7) can be quickly evaluated with high accuracy.

Algorithm 1

Input: p, K, and Λ Output:

G Initialization: G ← 0; K ← [K] Step 01: while K ̸ = ∅ do Step 02: [ λ, k]← arg min λ∈[Λ],k∈K Λ i=1 (σ 2 i + (µ i -µ) 2 )
Step 03: g λ, k ← 1

Step 04: K ← K\ k Step 05: end while

In Section V, we will verify that the bounds presented in Theorem 1 are valid for any user-to-cache state association strategy. We will also show that Algorithm 1 provides an efficient user-to-cache state association that yields a performance very close to the performance of optimal user-to-cache state association.

B. Performance analysis with uniform activity level

In this subsection, we analyze a special setting where users have a uniform activity level p, corresponding to the equiprobable case of

p 1 = p 2 • • • = p K = p.
As is common, we will also assume that I ≜ K Λ is an integer 8 . Lemma 1. In the presence of uniform activity level probabilities p, the optimal user-to-cache state association policy is the uniform one where each cache state is allocated to K/Λ users.

Proof. We first note that (3) implies that the average delay is minimized when [E[l 1 ], E[l 2 ], . . . , E[l Λ ]] is uniform. In the case where we have uniform activity levels, setting |G λ | = I ∀λ ∈ [Λ] provides uniformity.

We now proceed to provide computationally efficient analytical bounds on the average delay T (G) achieved by the uniform association policy, and subsequently to provide the exact scaling laws of this policy.

Theorem 3. In a state-constrained coded caching network of Λ cache states, K cache-aided users with normalized cache capacity γ and activity level of p, the average delay T (G) corresponding to the uniform user-to-cache state association strategy G is bounded by

T (G) ≤ Λ -t 1 + t E[l 1 ] (13)
and

T (G) ≥ Λ -t 1 + t E[l 1 ]t Λ -1 + Kp Λ Λ -t -1 Λ -1 (14)
where

E[l 1 ] = I - I-1 j=0 j i=0 I i p i (1 -p) I-i Λ . ( 15
)
Proof. The proof is deferred to Appendix C. 8 In the case where K Λ is not an integer, it was shown in [START_REF] Parrinello | Fundamental limits of coded caching with multiple antennas, shared caches and uncoded prefetching[END_REF] that the optimal strategy is to set I = ⌊ K Λ ⌋, and associate the remaining K -IΛ user cache states randomly (without replacement), with the expense of an additional delivery round.

Furthermore, the following shows that the bounds remain relatively close to the exact T (G).

Corollary 2. For any fixed γ ≤ 1 -1 Λ , the multiplicative gap between the analytical upper bound (AUB) in [START_REF] Serbetci | Multitransmitter coded caching networks with transmitter-side knowledge of file popularity[END_REF] and the analytical lower bound (ALB) in [START_REF] Zhao | Wireless coded caching can overcome the worst-user bottleneck by exploiting finite file sizes[END_REF], is at most Λ-1 t < 1/γ. This allows us to identify the exact T (G) within a factor that is independent of both Λ as well as K.

Proof. The proof follows directly from the fact that

Λ-t 1+t E[l1]t Λ-1 ≤ T (G) ≤ Λ-t 1+t E[l 1 ]. Remark 3.
We note that the range of γ ≤ 1 -1 Λ covers in essence the entire range of γ and most certainly covers the range of pertinent γ values.

Our proposed bounds in Theorem 3 identify that E[l 1 ] plays the main role in defining the performance of the system. Therefore, it is sufficient to characterize the exact scaling laws of E[l 1 ] in order to obtain the exact scaling laws of the average delay. We now proceed to exploit the bounds in Theorem 3, in order to provide in a simple and insightful form, the exact scaling laws of performance. The following theorem provides the asymptotic analysis of the average delay T (G), in the limit of large Λ and K.

Theorem 4. In a coded caching setting with Λ cache states and K cache-aided users with equal cache size γ and activity level p, the average delay T (G) corresponding to the uniform association strategy G scales as

T (G) =      Θ Kp(1-γ) 1+Λγ if Ip = Ω (log Λ) Θ Kp(1-γ) log Λ (1+Λγ)Ip log log Λ Ip if Ip ∈ Ω 1 polylogΛ ,o(logΛ) . ( 16
)
Proof. The proof is deferred to Appendix D.

In identifying the exact scaling laws of the problem, Theorem 4 nicely captures the following points.

• It highlights that randomness in users activity can bring an additional reduction in the coding caching gain. • It reveals that coding caching gain of 1 + Λγ, which is already less than 1 + Kγ due to subpacketization bottleneck, is only achievable when Kp Λ = Ω (log Λ).

• It shows that when Kp Λ = o(logΛ), we expect an additional reduction in the coding caching gain. The extent of this reduction can now be readily computed by using [START_REF]Fundamental limits of combinatorial multi-access caching[END_REF]. For example, it scales as Θ (1+Λγ) log log Λ log Λ at Kp = Θ (Λ), and as Kp increases, the coding caching gradually increases, and ceases to scale when Kp = Ω (Λ log Λ).

IV. MAIN RESULTS: DATA-DRIVEN APPROACH

In this section, we will extend our analysis to the datadriven setting. Unlike in the previous section where we used a predetermined set of statistics p, we will now exploit the users' content request histories to define the user activity levels as well as correlations. To proceed with our analysis we need to define the time scales involved. In our setting, the entire time horizon is equal to the time it takes between two user-to-cache associations. This time horizon will be here subdivided into S independent time slots, where one time slot corresponds to the amount of time that elapses from the appearance of one demand vector to the next demand vector. This dynamic time refinement captures the amount of memory of the system, and will capture how far back in history we can learn from regarding user activities.

Example 3. In a scenario where users are assigned cache states once a week, then the time frame is equal to one week which is equal to 10080 minutes. In this same example, if we assume that independent demand vectors appear once every 10 minutes, then the number of independent time slots S is simply S = 10080 10 = 1008. The main assumption in our data-driven approach is that each user's activity is predictable using their content request history as user's activity is highly correlated in time. For example let us suppose that we record the content request history of an office worker, and find out that the user is mostly active from 1pm to 2pm (i.e., lunch break) in the week days. Then, we conclude that we expect a similar activity pattern in the upcoming weeks from this user. Consequently, our aim will be to associate users to one of the cache states based on this prior user activity data.

In our setting, users' requests are served simultaneously, starting at the very beginning of each time slot. Any content request received during a time slot is put on hold, to be served in the beginning of the next time slot. This justifies the use of the term dynamic duration of each time slot s ∈ [S], where this duration will be equal to the time needed to transmit all files that were requested during the previous time slot from the BS to the users. We can now proceed with the details of our data-driven approach.

Let D ∈ [0, 1] S×K denote the user activity matrix, of which the (s, k) element d s,k is equal to 1 if user k requests content at time slot s, else d s,k = 0. Then, for a given user-to-cache state association G, the cache load vector for time slot s ∈ [S] is denoted as V s = [v s,1 , . . . , v s,Λ ], where v s,λ = K k=1 g λ,k d s,k is the number of active users at time slot s that are storing the content of cache state λ ∈ [Λ]. The profile vector at time slot s is denoted as L s = [l s,1 , . . . , l s,Λ ], which is the sorted version of the cache load vector V s in descending order. The average delay for a given user-to-cache state association G and a given user activity matrix D, is given by

T (G) ≜ 1 S S s=1 Λ-t λ=1 l s,λ Λ-λ t Λ t . ( 17
)
Unlike in the statistical approach of Section III, where an enormous number of possible profile vectors rendered the exact calculation of T (G) computationally intractable, in this current data-driven setting, the calculation of T (G) is direct even for large system parameters. This will allow us to design an algorithm that will find a user-to-cache association policy that is provably order-optimal.

An additional difference of the proposed data-driven problem formulation is that now this formulation inherits a crucial property of exploiting users' activity correlation in time. As previously discussed, users with similar request patterns will be associated with different cache states as this would guarantee more multicasting opportunities during the delivery phase. On the other hand, users that rarely request files at the same time, can be allocated the same cache state without any performance deterioration.

We now proceed to find an order-optimal user-to-cache state association Ĝ corresponding to Problem II.1. At this point we note that it is computationally intractable to brute-force solve Problem II.1 for large system parameters K, Λ and S, since there are Λ K possible user-to-cache state associations, corresponding to an exhaustive-search computational complexity of O SΛ K+1 . Under these circumstances, the most common approach is to use computationally efficient algorithms to obtain an approximate solution that is away from the optimal solution within provable gaps. In the following subsection, we will present two such computationally efficient algorithms.

A. Computationally efficient algorithms & bounds on the performance

We start with the following lemma which lower bounds the optimal average delay T * , optimized over all policies G.

Lemma 2. The optimal average delay, optimized over all association policies, is lower bounded by

T * ≥ 1 S s∈[S] d s Λ + 1 Λ -t 1 + t - 1 S s∈S2 Λ-As t+1 Λ t , (18)
where

d s = k∈[K] d s,k , A s = d s -Λ ds Λ
, and where S 2 ⊆ [S] is the set of time slots for which A s < Λ -t.

Proof. The proof is deferred to Appendix E.

The bound provided in Lemma 2 will serve as a benchmark for numerical performance evaluation of various user-to-cache state association algorithms.

We now proceed to present our computationally efficient algorithms. In the following, G will denote the set form of the user-to-cache state association matrix G, where (λ, k) ∈ G if g λ,k = 1. Similarly, G (λ) = {k : (λ, k) ∈ G} will denote the set of users that are storing the content of cache state λ ∈ [Λ]. Note that there is a direct correspondence between G and G, and the two terms can be used interchangeably.

1) Algorithm 2:

Problem II.1 belongs to the family of well-known vector scheduling problems [START_REF] Chekuri | On multidimensional packing problems[END_REF], [START_REF] Im | Tight bounds for online vector scheduling[END_REF], whose aim is to optimally assign each of the S-dimensional K jobs (i.e., the S-dimensional K vectors that are drawn from the columns of the user activity matrix D) to one of the machines λ ∈ [Λ] (i.e., cache states) with the objective of minimizing the maximum machine load (i.e., max s∈[S] l s,1 ), or with the objective of minimizing the norm of the machine loads. One can see that the vector scheduling problem is the generalization of a classical load balancing problem, where each job has a vector load instead of a scalar load.

We adopt the vector scheduling algorithm of [31, Section II-B3] to find the optimal user-to-cache state association within provable gaps. Algorithm 2 consists of three parts. The first part is the data transformation, where the user activity matrix D is scaled according to step 00. The second part (steps 01 to 08) is the deterministic user-to-cache state association, where for each user k ∈ [K], we find the cache state λ ∈ [Λ] according to step 02. If the scaled load (cf. step 03) of cache λ after the assignment of user k is less than 30 log S log log S + 1 for all time slots s ∈ [S], then user k is assigned to cache state λ. Otherwise user k is not assigned to any of the cache states, and is instead added to a set of residual users denoted by K r , and will be associated to a cache state later in the third part of Algorithm 2. The outcome of the second part is the userto-cache state association G 1 for users in [K]/K r . Next, the third part (steps 09 to 13) completes the association of the residual users in K r . Each user k ∈ K r is assigned to cache λ ∈ [Λ] according to step 11. The outcome of this part is the user-to-cache state association G 2 for users in K r . The final user-to-cache state association strategy for all users is then given by G = G 1 ∪ G 2 .

Algorithm 2

Input: D, K, Λ, and S Output:

G Initialization: G 1 ← ∅; G 2 ← ∅; K r ← ∅; α = 10 log S log log S
Step 00: ds,k ← min

Λ d s,k i∈[K] ds,i , 1 ∀ s ∈ [S], k ∈ [K]
Step 01: for k from 1 to K do

Step 02: λ ← argmin

λ∈[Λ] S s=1 Λ λ=1 1 α α Λ i∈(G 1 ∪(λ,k)) ds,i- j∈(G 1 ∪(λ,k)) λ ds,j
Step 03:

if k∈(G1∪( λ,k)) λ ds,k < 3α + 1 ∀ s ∈ [S]
Step 04:

G 1 ← G 1 ∪ ( λ,
T (G) = O log S log log S T * , ( 19
)
which proves that Algorithm 2 is at most a factor O log S log log S from the optimal.

Proof. The proof is deferred to Appendix F.

Proposition 1. The time complexity of Algorithm 2 is O(Λ 2 KS).
Proof. The first part of Algorithm 2 runs for K iterations and in each iteration, the evaluation at step 02 takes at most Λ 2 S basic operations. Then, the second part of Algorithm 2 runs for at most K iterations and in each iteration, the evaluation at step 11 takes at most ΛS basic operations. Thus the time complexity of Algorithm 2 is O(Λ 2 KS).

Directly from above, we can see that Algorithm 2 is significantly faster than the exhaustive search algorithm for which as we recall the time complexity was O SΛ K+1 .

2) Algorithm 3:

The main intuition behind Algorithm 3 is to exploit the fact that both Λ-λ t and l s,λ are non-increasing with λ; a fact that directly follows from [START_REF] Langberg | On the hardness of approximating the network coding capacity[END_REF]. Thus, the optimal userto-cache state association strategy is the one that minimizes the variances of the cache load vectors V s over all time slots. Algorithm 3 aims to heuristically minimize the sum of squares of cache populations over all time slots, which is equivalent to minimizing the sum of variances of the cache load vectors over all time slots. Algorithm 3 works in K iterations. At each iteration, it finds a pair of a user k and a cache state λ according to step 02 of Algorithm 3 and assigns user k to cache state λ.

Algorithm 3

Input: D, K, and Λ Output:

G Initialization: G ← ∅; K ← [K] Step 01: while K ̸ = ∅ do Step 02: [ λ, k]← arg min λ∈[Λ],k∈K s∈[S] i∈[Λ] j∈(G∪(λ,k)) (i) d s,j 2
Step 03: G ← G ∪ ( λ, k)

Step 04: K ← K\ k Step 05: end while Proposition 2. The time complexity of Algorithm 3 is O(Λ 2 K 2 S).

Proof. Algorithm 3 runs for K iterations and in each iteration, the evaluation at step 02 takes at most KΛ 2 S basic operations. Thus the time complexity of Algorithm 3 is O(Λ 2 K 2 S).

We can see that the time complexity of Algorithm 3 is K times higher than the time complexity of Algorithm 2. However, in Section V we numerically show that Algorithm 3 performs better than Algorithm 2.

V. NUMERICAL VALIDATION

In this section, we numerically validate our analytical bounds, and evaluate the performance of the different proposed user-to-cache state association algorithms.

A. Statistical approach

We first evaluate our proposed analytical bounds in Theorem 1 and Theorem 3 for the statistical setting using the sampling-based numerical (SBN) approximation method, where for any given G, we generate a sufficiently large set L 1 of randomly generated profile vectors L based on user activity vector p and where we subsequently approximate T (G) as where T (L) is defined in (2). For our evaluations involving an arbitrary user activity level vector p, we adopt the Pareto principle to generate the synthetic user activity level vector p. According to the Pareto principle, 80% of consequences (content requests) come from 20% of causes (users). To be exact, each user k ∈ [K] has a request with probability

T (G) ≈ 1 |L 1 | L∈L1 T (L), (20)
p k =                  1 5 i=1 i -2.7 if k = [1, 2, • • • , 0.2K] 2 -2.7 5 i=1 i -2.7 if k = [0.2K + 1, 0.2K + 2, • • • , 0.4K] 3 -2.7 5 i=1 i -2.7 if k = [0.4K + 1, 0.4K + 2, • • • , 0.6K] 4 -2.7 5 i=1 i -2.7 if k = [0.6K + 1, 0.6K + 2, • • • , 0.8K] 5 -2.7 5 i=1 i -2.7 if k = [0.8K + 1, 0.8K + 2, • • • , K]. (21)
The intuition behind [START_REF] Effros | An equivalence between network coding and index coding[END_REF] is that users are divided into 5 equipopulated groups, and the users that belong to the same group have the same activity levels.

The activity levels corresponding to these 5 groups then follow the Power law with parameter α = 2.7, and with these carefully selected parameters, the user activity pattern satisfies the Pareto principle (80/20 rule) [START_REF] Newman | Power laws, pareto distributions and zipf's law[END_REF].

In Figure 2, we compare the analytical bounds in ( 6) and ( 7) for an arbitrary activity level vector p, where this comparison uses the sampling-based numerical (SBN) approximation which is done for |L 1 | = 20000 and random user-to-cache state association. Subsequently, Figure 3 compares the analytical bounds in ( 13) and [START_REF] Zhao | Wireless coded caching can overcome the worst-user bottleneck by exploiting finite file sizes[END_REF] for uniform user activity level, where again the comparison is with sampling-based numerical (SBN) approximation which is done for |L 1 | = 20000 and uniform user-to-cache state association. Both figures reveal the proposed analytical bounds to be very tight, where in particular, analytical upper bounds are indeed very close to the exact performance.

Next, we evaluate the performance of our first proposed user-to-cache state association algorithm (Algorithm 1) by comparing it with the numerical lower bound (NLB) on the delay T * corresponding to the optimal user-to-cache state association Ĝ of Lemma 2. Figure 4 compares SBN approximation (once again done for |L 1 | = 20000) for the user- to-cache state association obtained from Algorithm 1 with the numerical lower bound (NLB) on T * in [START_REF] Bar-Yossef | Index coding with side information[END_REF]. Again we observe that the performance corresponding to the user-tocache state association G obtained from Algorithm 1 is very close to NLB for T * .

Figure 5 emphasizes on how the knowing and exploiting the user activity can play a positive role in dealing with the subpacketization bottleneck of the coded caching. Figure 5 compares sampling-based numerical (SBN) approximation in [START_REF] Fragouli | Network coding fundamentals[END_REF] (for |L 1 | = 20000 and uniform user-to-cache state association) for several user activity levels. As expected, reducing the number of cache states leads to the increase in the average delay. An important observation that we can draw from this result is that the actual deterioration due to the limit on subpacketization is significant when the user activity level is high. For example when p = 1 (i.e., MAN setting), reducing the number of cache states from Λ = 1500 (required subpacketization of ≈ 10 210 ) to Λ = 50 (required subpacketization of ≈ 10 6 ) increases the delay by 25.16 times 9 . However, when p = 0.2, a similar reduction in the number of cache states increases the delay by only 7.4 times. This highlights the importance of analyzing the coded caching in the presence of such heterogeneity in order to understand the actual gains of the coded caching.

B. Data-driven approach

For the approach, we synthetically generate a user activity matrix D following the Pareto principle. To be exact, we assume that user k ∈ [K] develops a request (i.e., is active) with probability p k as in [START_REF] Effros | An equivalence between network coding and index coding[END_REF] at each time slot s ∈ [S]. Then, for each time slot s ∈ [S], we pick a random number r k between 0 and 1 for each user k ∈ [K], and set d s,k = 1 if r k ≤ p k , and d s,k = 0 if r k > p k , which yields a user activity matrix D satisfying the Pareto principle [START_REF] Newman | Power laws, pareto distributions and zipf's law[END_REF].

In Figure 6, we compare the average delay T (G) in ( 17) corresponding to the user-to-cache state association obtained from Algorithm 2 and Algorithm 3 with the lower bound (LB) on T * in [START_REF] Bar-Yossef | Index coding with side information[END_REF]. It turns out that both algorithms yield performances that are over close to the optimal LB on T * , with Algorithm 3 having a slight advantage over Algorithm 2.

In Figure 7, we highlight the importance of exploiting the user-activity patterns and finding an efficient user-to-cache state association. Figure 7 compares T (G) values for random user-to-cache state association, and the user-to-cache state associations obtained from Algorithm 2 and Algorithm 3, where the lower bound (LB) of ( 18) serves as a benchmark. It turns out that both algorithms outperform random user-tocache state association, and the corresponding delay performances perform very close to the optimal LB on T * . If the time horizon S is subdivided into a small number of independent time slots, Algorithm 3 further outperforms Algorithm 2.

As the time complexity of Algorithm 2 is O(Λ 2 KS), and the time complexity of Algorithm 3 is O(Λ 2 K 2 S), one can perceive a trade-off between the number of users and the reduction in the delay by adopting Algorithm 3 instead of Algorithm 2. Let us also note that increasing S to reflect having more frequent information on the dynamics of the user activity patterns, diminishes the performance gap between the two algorithms. In a nutshell, in the expense of an increase by a factor of K in the time complexity, it is worth adopting Algorithm 3 over Algorithm 2 when the time horizon is divided into a smaller number of independent time slots.

In our final evaluation, we validate our assumption that designing the user-to-cache state associations using past data can achieve similar performance superiority over random user-tocache state association. For the following results, we generate two user activity matrices D train and D test following the same Pareto principle approach defined above. We use D train to obtain the user-to-cache state associations from Algorithm 2 and Algorithm 3. Then, we use D test to calculate the performance. Figure 8 compares T (G) values for random user-to-cache state association, and the user-to-cache state associations obtained from Algorithm 2 and Algorithm 3. We can see that both algorithms outperform random user-tocache state association, with once again Algorithm 3 having a slight advantage over Algorithm 2.

VI. CONCLUSIONS

In this work we analyzed coded caching networks with finite number of cache states and a user-to-cache state association subject to a grouping strategy in the presence of heterogeneous user activity. Even though coded caching techniques rely on the assumption of having enough number of users to provide its theoretically promised gains, all the earlier works ignored the fact of heterogeneity in user activities, which in our opinion has direct practical ramifications, as it captures practical wireless networks more accurately.

We first presented a statistical analysis of the average worst-case delivery performance of state-constrained coded caching networks, and provided bounds and scaling laws under the assumption of probabilistic user-activity levels. We also proposed a heuristic user-to-cache state association algorithm with the ultimate goal of minimizing the average delay.

Next, we extended our analysis to the data-driven setting, where we were able to learn from the past S different demand vectors in designing the caching policy. By exploiting this bounded-depth user request history, the emphasis then was placed on finding the optimal user-to-cache state association, as computing the average delay for any given data is trivial. We proposed two algorithms for finding the optimal user-to-cache state association strategy, with the first algorithm providing the optimal within a constant gap, and with the second algorithm numerically outperforming the first one.

For both aforementioned settings, the results highlighted the essence of exploiting the user activity level, and the importance of carefully associating users to cache states based on their activity patterns.

APPENDIX

A. Proof of Theorem 1

Exploiting the fact that in (3), both Λ-λ t and E[l λ ] are non-increasing with λ, the average delay T (G) is bounded by

T (G) ≤ Λ-t λ=1 E[l 1 ] Λ-λ t Λ t (a) = E[l 1 ] Λ t+1 Λ t = E[l 1 ] Λ -t 1 + t , (22)
and

T (G) (b) ≥ E[l 1 ] Λ-1 t + Λ-t λ=2 Kp-E[l1] Λ-1 Λ-λ t Λ t (c) = E[l 1 ] Λ-1 t Λ t + K p -E[l 1 ] Λ -1 Λ-1 t+1 Λ t = Λ -t 1 + t E[l 1 ]t Λ -1 + K p Λ Λ -t -1 Λ -1 , (23)
where in steps (a) and (c), we inherit the the column-sum property of Pascal's triangle yielding n k=0 k t = n+1 t+1 , while in step (b), we have 10 K p = Λ λ=1 E[l λ ], and the fact that uniformity in L leads to the minimum T (G).

Next, to complete the proof, we proceed to derive the expected number of active users that are storing the content of the most loaded cache state (i.e., E[l 1 ]), which is given by

E[l 1 ] = A-1 x=0 P [l 1 > x] = A-1 x=0 (1 -P [l 1 ≤ x]) , (24)
where A = max {|G λ |} Λ λ=1 , G λ is the set of users caching the content of cache state λ, and P [l 1 ≤ x] is the probability that number of active users storing the content of the most loaded cache state are less than or equal to x. From [33, Proposition 3], we have

P [l 1 ≤ x] ≥ max 0, 1 -Λ + Λ λ=1 F v λ (x) (25)
and

P [l 1 ≤ x] ≤ Λ λ=1 F v λ (x) Λ , (26)
where F v λ (x) is the probability that no more than x users that are caching the content of cache state λ ∈ [Λ] are active (i.e.,

P [v λ ≤ x]). Then E[l 1 ] is bounded by E[l 1 ] ≤ A - A-1 x=0 max 0, 1 -Λ + Λ λ=1 F v λ (x) (27)
and

E[l 1 ] ≥ A - A-1 x=0 Λ λ=1 F v λ (x) Λ . (28)
For each cache state λ ∈ [Λ], the corresponding random variable v λ follows the Poisson binomial distribution. Using Hoeffding's inequalities [34, Theorem 2.1], F vi (x) is bounded by

F v λ (x) ≥ 0 for 0 ≤ x ≤ µ λ -1 F bin |G λ |, µ λ |G λ | , x for µ λ ≤ x ≤ |G λ | (29)
and

F v λ (x) ≤ F bin |G λ |, µ λ |G λ | , x for 0 ≤ x ≤ µ λ -1 1. for x > µ λ -1, (30)
where µ λ = k∈G λ p k is the expected number active users that are storing the content of cache state λ ∈ [Λ] and F bin (n, q, x) = x i=0 n i q i (1 -q) n-i is the Binomial cumulative distribution function.

Finally, the upper bound in (6) can be obtained from ( 22), [START_REF] Malik | Fundamental limits of stochastic shared-cache networks[END_REF], and (29); and the lower bound in (7) can be obtained from ( 23), [START_REF] Liao | Fundamental rate-memory tradeoff for coded caching in presence of user inactivity[END_REF], and (30). 10 It straightforward to see that

λ∈[Λ] E[l λ ] = K i=0 L∈L:i= j∈[Λ] l j λ∈[Λ] l λ P (L) = K i=0 L∈L:i= j∈[Λ] l j iP (L) = Kp.
B. Proof of Theorem 2

From ( 22) and ( 23), we have,

T (G) = O E[l 1 ] Λ -t 1 + t , (31)
and

T (G) = Ω Λ -t 1 + t E[l 1 ]t Λ -1 . (32)
As t Λ-1 ≈ γ is a constant, we get the exact scaling law of T (G), which is given by

T (G) = Θ E[l 1 ] Λ -t 1 + t . (33)
We know from [35, Proposition 1] that E[l 1 ] is bounded by

1 Λ Λ λ=1 µ λ ≤ E[l 1 ] ≤ 1 Λ Λ λ=1 µ λ + Λ-1 Λ Λ λ=1   σ 2 λ + µ λ - 1 Λ Λ λ=1 µ λ 2   , (34)
where µ λ = k∈G λ p k and σ 2 λ = k∈G λ p k (1 -p k ) are the mean and the variance of the number of active users that are caching the content of cache state λ ∈ [Λ] respectively. After defining a new parameter µ = 1 Λ Λ λ=1 µ λ , we have

T (G) = O     µ + Λ i=1 [σ 2 i + (µ i -µ) 2 ]   Λ -t 1 + t   , (35)
and

T (G) = Ω µ Λ -t 1 + t . (36)
This concludes the proof of Theorem 2.

C. Proof of Theorem 3

We start our proof by deriving the expected number of active users that are storing the content of the most loaded cache state (i.e., E[l 1 ]). Assuming that each user independently requests a content with probability p, the probability that no more than x out of I users are active and storing the content of cache state λ ∈ [Λ] is given by

F v λ (x) = x i=0 I i p i (1 -p) I-i . (37)
Then, the probability that l 1 (i.e., max(V), the maximum number of active users among all caches) is less than or equal to j, is equal to the probability of the event v λ ≤ j, ∀ λ ∈ [Λ], and given by

P [l 1 ≤ x] = Λ λ=1 F v λ (x) = x i=0 I i p i (1 -p) I-i Λ . (38) Now, we can characterize E[l 1 ] as follows E[l 1 ] = I-1 x=0 (1-P [l 1 ≤ x]) = I - I-1 x=0 x i=0 I i p i (1-p) I-i Λ .
(39) Finally, we obtain the upper and lower bounds in Theorem 3 by combining ( 22) and ( 23) with (39), respectively.

D. Proof of Theorem 4

To prove Theorem 4, we will follow a similar approach as in [START_REF] Raab | Balls into bins -A simple and tight analysis[END_REF]. For each cache state λ ∈ [Λ], we denote Y λ to be an indicator random variable, which is equal to From [36, Section 2], we inherit the following properties that are drawn from the outcomes of Markov's inequality and Chebyshev's inequality

1 if v λ ≥ k α ,
P [Y = 0] = 1 -o(1) if log(E[Y ]) → -∞ o(1) if log(E[Y ]) → ∞. (41)
Consequently, the probability that there exists at least one cache state λ for which the number of active users v λ is at least k α is given by

P [Y ≥ 1] = o(1) if log(E[Y ]) → -∞ 1 -o(1) if log(E[Y ]) → ∞. ( 42
)
We now proceed with the following results which are crucial for the derivation of the asymptotics of E[l 1 ]. Lemma 4. In a K-user Λ-cache state setting where each user requests a content with probability p, the probability that the maximum number of active users among all caches is less than or equal to k α , takes the form

P [l 1 ≥ k α ] = o (1) if α > 1 1 -o (1) if 0 < α < 1, (45)
for (46)

k α =                Ip + 2αIp(1 -p) log(Λ), if Ip = ω (log Λ)
Proof. We begin the proof for the case of Ip = ω (log Λ) (62) This concludes the proof of Theorem 4.

E. Proof of Lemma 2

From (17), we know that l s,λ and Λ-λ t are non-increasing with λ, which implies that for each time slot s ∈ [S], the profile vector L s , which minimizes the delay has components of the form

where d s = k∈[K] d s,k , and A s ≜ d s -Λ ds Λ . Consequently, when A s ≥ Λ -t, the corresponding best-case delay T s for time slot s ∈ [S] is given by

T s = Λ-t λ=1 d s Λ + 1 Λ-λ t Λ t = d s Λ + 1 Λ -t 1 + t , (64)
while when A s < Λ -t, this is given as

T s = As λ=1 d s Λ + 1 Λ-λ t Λ t + Λ-t λ=As+1 d s Λ Λ-λ t Λ t = d s Λ Λ-t λ=1 Λ-λ t Λ t + As λ=1 Λ-λ t Λ t = d s Λ + 1 Λ-t λ=1 Λ-λ t Λ t - Λ-t λ=A+1 Λ-λ t Λ t = d s Λ + 1 Λ t+1 Λ t - Λ-As t+1 Λ t = d s Λ + 1 Λ -t 1 + t - Λ-As t+1 Λ t . ( 65
)
We denote S 2 ⊆ [S] to be the set of time slots for which A s < Λ -t. Then, the average delay corresponding to the optimal user-to-cache state association Ĝ is lower bounded by

T
d s Λ + 1 Λ -t 1 + t - 1 S s∈[S2] Λ-As t+1 Λ t . (66)
This concludes the proof of Lemma 2.

F. Proof of Theorem 5

We denote v G1 s,λ , v G2 s,λ , and v G s,λ to be the scaled loads calculated using transformed user demand matrix D (Step 00 of Algorithm 2) of each cache state λ ∈ [Λ] at time slot s ∈ [S] following the user-to-cache state association given by G 1 , G 2 , and G respectively. It is straightforward to see from step 03 of Algorithm 2 that v G1

We also have from (66) that

T * = Ω   1 S s∈[S] k∈[K] d s,k Λ Λ -t 1 + t   . (69)
This concludes the proof of Lemma 2.

Fig. 1 :

 1 Fig. 1: An instance of a cache-aided wireless network.

2 Theorem 5 .

 25 k) Step 05: else Step 06: K r ← K r ∪ k Step 07: end if Step 08: end for Step 09: for c from 1 to |K r | do Step 10: k = K r (c) Step 11: λ ← argmin λ∈[Λ] max s∈[S] j∈(G2∪(λ,k)) λ ds,j Step 12: G 2 ← G 2 ∪ ( λ, k) Step 13: end for Step 14: G ← G 1 ∪ G When there are at least Λ requests at each time slot s ∈ [S], the average delay T (G) corresponding to the user-to-cache state association G obtained from Algorithm 2 is bounded by

Fig. 2 :

 2 Fig.2: Analytical upper bound (AUB) from (6) vs. analytical lower bound (ALB) from (7) vs. sampling-based numerical (SBN) approximation in[START_REF] Fragouli | Network coding fundamentals[END_REF] (for |L1| = 20000, p in[START_REF] Effros | An equivalence between network coding and index coding[END_REF], and random user-tocache state association).

Fig. 3 :

 3 Fig.3: Analytical upper bound (AUB) from (13) vs. analytical lower bound (ALB) from (14) vs. sampling-based numerical (SBN) approximation in[START_REF] Fragouli | Network coding fundamentals[END_REF] (for |L1| = 20000 and uniform user-to-cache state association).

Fig. 4 :

 4 Fig. 4: SBN from (20) of Algorithm 1 vs. Numerical lower bound (NLB) on T * from (18) (for |L1| = 20000 and p in (21) ).

Fig. 5 :

 5 Fig. 5: Sampling-based numerical (SBN) approximation in (20) (for |L1| = 20000 and uniform user-to-cache state association).

Fig. 6 :

 6 Fig. 6: T (G) of Algorithm 2 and Algorithm 3 from (17) vs. lower bound (LB) on T * from (18).

Fig. 7 :

 7 Fig.7: T (G) of random user-to-cache state association, the user-tocache state associations obtained from Algorithm 2, and Algorithm 3 from (17), and the lower bound (LB) of[START_REF] Bar-Yossef | Index coding with side information[END_REF].

Fig. 8 :

 8 Fig.8: T (G) of random user-to-cache state association, the user-tocache state associations obtained from Algorithm 2, and Algorithm 3 from (17).

  and it is equal to 0 otherwise. It immediately follows thatE[Y λ ] = P [v λ ≥ k α ], ∀λ ∈ [Λ]. Let Y = Λ λ=1Y λ be the sum of the indicators over all cache states. Then, we haveE[Y ] = E Λ λ=1 Y λ = Λ λ=1 E [Y λ ] = ΛP [v λ ≥ k α ]. (40)

Lemma 3 ( [ 36 ,P 2 2

 3362 Lemma 2] -adaptation). For a positive constant c, if Ip + 1 ≤ x ≤ (log I) c , then P [v λ ≥ x] = e x(log Ip-log x+1)-Ip+O(log (2) I)(43)and if x = Ip + o (p(1 -p)I) [v λ ≥ x] = e -zThe result comes directly from [36,Lemma 2].

3 1+α 2

 32 log Λ Ip Ip, if Ip ∈ [ω(logΛ) ,O(polylogΛ)] (α + e -1) Ip, if Ip = Θ (log Λ)

1 polylogΛ

 1 ,o(logΛ) .

3 . 2 -

 32 Let k α = Ip + 2αIp(1-p) log Λ, then from (40) and (44), we havelog(E[Y ]) = log Λ -z 2 log z -log √ 2π + o(1)= log Λ 1-α -log2α + log(2)

  l s,λ = ds Λ + 1 for λ ∈ [1, 2, . . . , A s ] ds Λ for λ ∈ [A s + 1, A s + 2, . . . , Λ] ,

  s,λ = O log S log log S ∀s ∈ [S], λ ∈ [Λ]. By combining Lemma 15 and Lemma 18 of [31], we have v G2 s,λ = O (1) ∀s ∈ [S], λ ∈ [Λ]. Thus, the combined scaled load of each cache λ ∈ [Λ] at each time slot s ∈ [S] is given by v G s,λ = O log S log log S . To complete the proof, we now proceed to convert the scaled load of each cache λ ∈ [Λ] at time slot s ∈ [S] to the actual load. Based on the assumption that for each time slot s ∈ [S], k∈[K] d s,k ≥ Λ, we have ds,k = minΛ d s,k i∈[K] ds,i , 1 = Λ d s,k i∈[K] ds,i ∀ s ∈ [S], k ∈ [K].Then, the actual load corresponding to user-to-cache state association G is given byv s,λ = k∈[K] d s,k Λ v G s,λ = O k∈[K] d s,k Λ log S log log S ∀ s ∈ [S], λ ∈ [Λ]. Consequently, from[START_REF] Langberg | On the hardness of approximating the network coding capacity[END_REF], we have

  10 27 . We can see that exploiting the users' request behavior allows us to not only reduce the delivery time, but also reduce the required subpacketization rate by a factor of 7.6 × 10 20 .

	200 21 )-( 150 21 ) ( 200 20 ) be 200 20 ≈ 1.61 × = 8.558, and the required subpacketization would

This simply means that even though there are K different users, each with their own physical cache, in essence, there can only exist Λ distinct caches, that must be shared among the users. This effectively means that groups of users are forced to have identical, rather than complementary, cache contents.

The time scale is normalized such that a unit of time corresponds to the optimal amount of time needed to send a single file from the BS to the user, had there been no caching and no interference.

If we consider a scenario where we assign caches to users once a day, and assuming that independent demand vectors appear once every 30 minutes, then the number S is at most 2 × 24 = 48 which implies a gap of approximately 2.3. If instead we assign caches once a week, S becomes

× 2 × 24 = 336 and the gap is approximately 2.7. If this depth changes to a much larger S = 12 × 336 corresponding to a history window of 4 weeks, and a demand vector -for those same K co-located users -every 10 minutes, then the gap is bounded at 3.3.

Note that this is equal to the ratio between the DoFs, i.e., 151/6.

The work is supported by the European Research Council under the EU Horizon 2020 research and innovation program / ERC grant agreement no. 725929 (project DUALITY).

Using (42), we conclude the proof for this case as for Λ → ∞, we have

Next, we proceed with the case of Ip ∈ [ω (log Λ) , O(polylog(Λ))]. We first define g ≜ O (polylog(Λ)). Then, assuming that k α = 1 + α 2 g Ip and Ip = g log(Λ), from (40) and (43), we have

where in step (a), we used the Maclaurin series expansion of the logarithm function, i.e., log(1 + x) = x -0.5x 2 + o(x 2 ). Using (42), we conclude the proof for this case as for Λ → ∞, log(E[Y ]) converges to (1-α 2 ) log Λ, and we obtain

Now, we proceed with the case of Ip = Θ (log Λ). Assuming that k α = (α + e -1) Ip and Ip = log Λ, from (40) and (43), we obtain

(51) Using (42), we conclude the proof for this case as for Λ → ∞, we have

We first define

and Ip = log(Λ) g , from (40) and (43), we obtain

log (2) g log g +1 -log(Λ) g +O log (2)

= logΛ+k α 1-logg+log (2) g-α log (2)

g log (2) g +O log (2) I log g log Λ log (2) g + α 2 log (2) g (log g) 2 -0.5+0.5 α log (2) g log g

where in step (a), we used the Maclaurin series expansion of the logarithm function, i.e., log(1 + x) = x -0.5x 2 + o(x 2 ). Using (42), we conclude the proof for this case as for Λ → ∞, log(E[Y ]) converges to log Λ log (2) g log g

(1 -α), and we obtain

This concludes the proof of Lemma 4.

With Lemma 4 at hand, we proceed to characterize E[l 1 ]. Let us first consider the case of α > 1, for which we have

where in step (a), we use the fact that

Similarly, for 0 < α < 1, we have

where in step (a), we use the fact that 46), (55), and (56), we have

(57) From ( 13) and ( 14), we have,

and

As t Λ-1 ≈ γ is a constant, we get the exact scaling law of T (G), which is given by


Nicolas Chauvin
email: nicolas.chauvin@insa-lyon.fr

Amaury Mavel

Ali Jaffal

Gilles Patriarche

Michel Gendry

Determination of the spin orbit coupling and crystal field splitting in wurtzite InP by polarization resolved photoluminescence

teaching and research institutions in France or abroad, or from public or private research centers.   Determination of the spin orbit coupling and crystal field splitting in wurtzite InP by polarization resolved photoluminescence

In recent years, several groups have experimentally investigated the band structure properties of wurtzite (Wz) InP nanowires (NWs) to gain access to parameters such as the bandgap and Varshni parameters, 1 the effective masses, 2 the deformation potentials, 3 the dipole orientation 4 or the Young modulus. 5 However some band structure parameters are still not very well-known. In the Wz phase, the degeneracy of the first three valence bands (usually labeled A, B and C bands) is lifted (Figure 1.a). Within the quasi-cubic approximation these valence band splittings are a consequence of the spin orbit coupling (∆SO) and the crystal field splitting (∆CR).

One of the open questions is to determine if the spin orbit coupling (∆SO) parameter is bigger or smaller than the crystal field splitting (∆CR). In the literature, the experimental values of these two parameters are usually deduced from optical measurements such as photoluminescence (PL) or PL excitation (PLE). The A, B and C transitions of InP Wz are identified and the ∆SO and ∆CR are deduced from the energy levels of these transitions using the equations 6 :

CR SO CR SO CR SO AB E   -        +  -  +  =  3 2 2 2 2 (1) CR SO CR SO CR SO AC E   -        +  +  +  =  3 2 2 2 2 (2)
where ∆EAB (∆EAC) is the energy difference between A and B (A and C) transitions. The main concern with this method is the fact that the two equations are symmetric in regards of the ∆SO and ∆CR values. As a consequence, a couple of numbers can be extracted but an assumption, ∆CR > ∆SO or the opposite one, has to be chosen to attribute the experimental values to the intrinsic parameters of the material. As a consequence, some published works, such as in the work of M.H. 7 have considered that ∆CR is bigger than ∆SO whereas the opposite choice has been taken in the work of S. Perera et al. 8 To conclude on this issue, we have to focus on properties related to ∆SO and ∆CR but not on a symmetrical way. One interesting possibility is to investigate the polarization resolved PL of Wz InP NWs. The ratio of PL intensity polarized parallel to the NW axis (z axis) over the perpendicular one (x axis) is equal to

Hadj Alouane et al,

2 0 2 0 x z x z d d I I  = where 2 0 2 0 x z d d
is the ratio of internal dipole moments squared and  is a parameter taking into account the impact of the NW on the PL emission. The emission of the A band is expected to be perpendicular to the c-axis, i.e. to the NW axis 6 . The situation is different for the B band where no dipole orientation is forbidden. 9 Table 1: Interband momentum-matrix elements for polarization parallel and perpendicular to the c axis. 6 The interband momentum-matrix elements of the A, B and C bands are given in Table 1 where a, b, Epz and Epx are related to the following equations (from Ref 6):

2 3 2 2 2 2 + = E E a , 2 3
2 2 3 2 2  +  = E b (3) ( )( ) 2 2 3 2 2 0 2 2 2 1  +  -  +  +  +         - = g g CR g z e pz E E E m m E (4) ( )( )   ( )( ) 2 3 2 2 2 3 2 2 0 2 2 1  -  +  +  +  -  +  +  +         - = g CR g g CR g g t e px E E E E E m m E (5)
with Eg the band gap, ( )

3 2 4 6 2 2 2 SO CR SO CR SO CR E   -  +  +  -  = , 3 3 2 SO  =  =  , t e m
and z e m the transverse and longitudinal electron effective masses, respectively. The experimental values m z e=0.078 and m t e=0.093, recently obtained in Ref 2, are used for the calculations. As far as the B transition is concerned, the ratio of the interband momentum-matrix elements, parallel over perpendicular to the c-axis, is equal to

px pz x z E a E b d d 2 2 2 0 2 0 2 =
, is related to the ∆CR and ∆SO values and not on a symmetrical way. This ratio has been calculated for the B transition as a Numerous groups have reported experimental 1,7,8,10,11 or theoretical 9,12,13 values of ∆CR and ∆SO.

E A E B E C // c-axis c-axis ┴ 0       pz E m b 2 0 2       pz E m a 2 0 2       px E m a 4 0 2       px E m b 4 0 2
These values are reported in Fig.

 x z d d
, whereas

1 2 0 2 0  x z d d is expected if ∆CR>∆SO. As a consequence
the determination of this ratio by polarized PL will conclude on the good assumption: ∆CR > ∆SO or ∆SO > ∆CR. We would like to highlight that a strategy to determine the correct solution of equation ( 1) and ( 2) would be to assume that the ∆SO value is comparable to the known bulk zincblende (ZB) InP ∆SO value of 108 meV (from Ref 14) and attribute the second value to ∆CR. procedure is to induce the growth of a field of vertical Wz InP NWs as detailed in Reference. 15 Two growth steps were performed at different substrate temperatures to obtain the NWs. First, the NWs were grown during 10 minutes at 380°C with an indium flux corresponding to an InP 2D layer equivalent growth rate of 1 ML/s and with a PV/PIII beam equivalent pressure (BEP) ratio equal to 20 in order to produce pure Wz InP NWs. 7 To increase the NW diameter, a second growth step of 10 minutes was performed at a lower temperature (340°C) to favor the NW radial growth.

However, as shown in

The sample is composed of vertical 800 nm  50 nm long NWs with a constant diameter (without tapering) of 90 nm  5 nm and a NW density of ≈ 7 NWs per µm² (Fig. 2.a). InP NWs have been investigated by high-resolution transmission electron microscopy (HRTEM). The sample is characterized in a PL setup composed of a close cycled helium cooled cryostat, a 532 nm continuous wave (cw) diode-pumped solid-state laser and a nitrogen cooled silicon CCD detector coupled to a monochromator. The low temperature PL spectrum revealed a sharp emission at 1.492 eV, the transition energy of the A exciton in Wz InP (Figure 3). 1 At room temperature a peak (at 1.426 eV) and one shoulder (at ≈ 1.46 eV) are observed and are related to To perform this study, a micro-photoluminescence (micro-PL) setup is build using a 671 nm continuous wave (cw) diode-pumped solid-state laser as the excitation source (laser spot size of 20 µm) and an InGaAs cooled silicon CCD detector coupled to a monochromator for the detection.

The micro-PL is performed on the as-grown sample with separate excitation and analysis arms:

the NWs are optically pumped from the top while the collection is performed from the side of the sample using a 0.4 numerical aperture objective microscope and a polarizer. Due to the verticality of the InP NWs grown on the substrate, the collection from the side of the sample allows to investigate the orientation of the light emission as a function of the NW axis. A low resolution grating is used to decrease the polarization dependence of the setup. Moreover, correction functions are done with a tungsten lamp to remove any polarization dependence of the setup. (perpendicular to the NW axis) to 180° going through 90° (parallel to the NW axis). Each spectrum consists of two peaks related to the A and B band to band transitions and is fitted using the equation [START_REF] Grundmann | The Physics of Semiconductors[END_REF] :

( )         - -  - - + - = kT E E E E I E E I I g AB g B g A exp ( 6
)
where the values Eg=1406 meV, ∆AB=36 meV and kT=39 meV are identical to fit all the experimental data. The high carrier temperature is probably the consequence of long lived hot carriers in small diameter NWs. A carrier temperature of 43 meV was recently reported for 72 nmdiameter Wz InP NWs during room temperature µ-PL measurements. [START_REF] Tedeschi | [END_REF] The 36 meV splitting between the A and B bands at room temperature is also in agreement with other experimental results. 1 The intensities IA and IB are reported in Fig. 4.b. To be able to fit these experimental results a precise analysis has to performed. The extraction of the real dipole ratio of the B transition from the experimental study is a complex problem for two reasons: 1) the emission is not localized at a specific position in the NWs and 2)

the InP NWs have to be seen as a photonic structure with emission tailored through guiding and leaky modes. As a consequence the measured ratio is not the intrinsic one and the impact of the NWs on the emission has to be understood to recover the real ratio. The 90 nm-diameter InP NW field corresponds to a HE11 monomode structure 18 with a strong inhibition expected for the dipole oriented perpendicularly to the NW axis. The strong interest of this situation is that the screening of the dipole is independent of the dipole position in the NW plane as already shown in Ref 19 for GaAs NWs. As a consequence, the recombination rate of the dipole is independent of its in-plane position. A modification of the dipole spontaneous emission is possible along the NW axis due to the presence of the high refractive index silicon substrate. As a consequence, Finite Difference Time Domain (FDTD) calculations are performed as a function of the dipole orientation (perpendicular or parallel to the NW axis) and the dipole position along the z axis. Calculations are performed on a 800 nm long NW represented by a 90 nm in diameter cylinder on a silicon substrate. Refractive indexes of 3.42 and 3.64 are used for InP 18 and for the silicon substrate, respectively. Calculations are performed using the Opti-FDTD software. 20 Figure 5: Schematic of the photonic structure used for the FDTD calculations.

It is also known that the far field is strongly impacted by the dipole orientation as compared to the NW axis. 18,21 This is a key issue to take into account: a modification of the far field can induce a modification of the collection efficiency in our NA=0.4 microscope objective and a wrong estimation of the intrinsic dipole ratio. The far field radiative power is calculated using the method detailed in Ref 22 . Fig. 5 shows a schematic of the calculation: z is the NW growth axis, the polarization of the emission is investigated in the x-z plane for a dipole aligned along the NW axis (z-polarized) or perpendicular to the NW axis (x-polarized). There is also a dipole oriented perpendicularly to the NW axis along the y axis but the probability to collect photons emitted by this dipole orientation is weak as a consequence of the NA=0.4 numerical aperture. 23 The total averaged power emitted by the x-polarized (z-polarized) dipole and collected by the microscope objective is equal to 22

( ) ( ) ( )           + = NA k k z x x z z x z x E FT H FT dk dk k P // 2 2 2 2 2 2 2 ) ( 1 ) ( . 8 2     ( 7
)
where kNA is determined by the numerical aperture of the microscope objective, This approximation is very usual in the literature. But to confirm that this choice has not a too strong impact on the value of  , we have also performed the same FDTD calculations with the theoretical values published by De and Pryor (using nz=3.35 and nx= ny=3.83) to take into account the anisotropy of the Wz material. 24 A value 28 =  is obtained from the simulation for a 90 nm diameter NW. As a consequence, we will assume that 10 30  =  . The experimental results are fitted with the equation: the literature, a majority of Wz III-V semiconductors have a ∆CR which is smaller than ∆SO. 9 However, the condition ∆CR > ∆SO is not exceptional and is predicted for several Wz III-V semiconductors such as GaN, GaP and InN. 9 This result allows us to confirm from our former PLE measurements that ∆CR≈ 145 meV and ∆SO≈ 74 meV. 7 These results lead to a ∆SO value which is clearly smaller in Wz InP (74 meV) than in ZB InP (108 meV). This observation is in contradiction with the theoretical calculations of ∆SO in InP polytypes where a variation of a few percent is predicted between two different crystallographic phases. 9,12,13 In both WZ and ZB configurations the nearest neighbors are tetahedrally bonded. To explain a modification of the ∆SO value between the two phases, we have to assume that the interactions with the second or third nearest neighbors are not negligible. 11 The knowledge of these values is an important information to be able to perform accurate band structure calculations when ∆CR and ∆SO do not act on a symmetrical way.

𝐼(𝜃) = 𝐼 0 [𝑐𝑜𝑠 2 (𝜃) + 𝑑 𝑧0 2 𝑑 𝑥0 2 𝛽𝑠𝑖𝑛 2 (𝜃)] (8)
Moreover the experimental method proposed in this paper could be used for other Wz materials once the configurations ∆CR > ∆SO and ∆CR < ∆SO provide strongly different

4 0

 4 function of ∆CR and ∆SO in the case of Wz InP. These results are reported in Fig 1 where black lines represent different values of

  1.b. Due to the symmetric nature of the equations (1) and (2), for each experimental study, two points are reported. Fig 1 reveals that the two possible solutions of equations (1) (2) provide strongly different

  Fig 1.b, both solutions of the equations (1) (2) lead to values which are relatively far from the known ∆SO value of bulk ZB InP. As a consequence, it is difficult to use such a strategy in the present situation.

Figure 1 :

 1 Figure 1: a) band structure of Wz InP. b) Theoretical

Figure 2 .

 2 b shows the dark field TEM image of a typical InP NW oriented along the[11-20] Wz zone axis. In this orientation, Wz and ZB crystal structures show two different diffraction patterns in which the spots belonging to one phase are well separated from those of the other. Therefore, a good contrast can be obtained between the two phases by selecting the spots of one of the two phases. The NW shown has a 770 nm length and a 90 nm diameter. The NW has a perfect Wz crystallographic structure during the first 620 nm length. This length corresponds to the typical size of the InP NWs after the initial 10 mn axial growth at 380°C. Then, few ZB insertions are observed in the upper part of the NW. This part is related to the axial growth of the NWs during the second growth step at 340°C. This second step is required to increase the NW diameter: the NWs have usually a 50-60 nm diameter after the first growth step.

Figure 2 :

 2 Figure 2: (a) SEM Image of the InP NWs. (b) Dark field TEM image of an InP NW.

A

  and B transitions, respectively. The B transition is observed due to the thermal activation of the holes from the A to the B band. These results are the usual features on Wz InP NWs and confirm the Wz crystallographic phase of the NWs. The observation of the B transition at room temperature allows us to investigate its polarization resolved emission.

Figure 3 :

 3 Figure 3: Normalized PL spectra of the sample at low and room temperature.

Fig. 4 .

 4 Fig. 4.a shows the µ-PL emission of a NW ensemble as a function of the polarizer angle from 0°

Figure 4 :

 4 Figure 4: (a) PL spectra of the NW sample as a function of the polarization angle. PL spectra were offseted for clarity. Red curves are the fitting using Equation (3). (b) PL integrated intensity of the A and B bands as a function of the polarizer angle. NWs are aligned along the 90°-270° axis of the polarizer

  integration is performed over the 0.4 numerical aperture of the experimental setup. The ratio value of 32 is obtained. This high value of  is explained by the strong inhibition of the dipole oriented perpendicularly to the NW axis. To take into account the NW diameter distribution observed in our sample, the same FDTD calculations are performed for NW diameters of 85 nm and 95 nm and  values of 35 and 20 are obtained, respectively. Another source of error for  could be related to the refractive index chosen in the FDTD calculations. There are no experimental value available for the Wz InP refractive index and the value of the ZB InP is used.

.

  for the A and B bands and values of 0.01 and 0.17±0.06 are obtained, respectively. As a far as the A band is concerned, the value is very close to the theoretical one, i.e. a dipole oriented perpendicularly to the NW axis due to a forbidden transition for the polarization oriented parallel to the NW axis. Concerning the B band the most important one. The dashed red line in Fig.1.It means that ∆CR is bigger than ∆SO for Wz InP, in agreement with the calculated values published in Ref 12 and in Ref 13 but in contradiction with Ref 9 . If we refer to

ACKNOWLEDGMENT This work has been supported by the Agence Nationale pour la Recherche project INSCOOP (ANR-11-NANO-012). Authors are gratefully acknowledging facilities and technological staffs from Nanolyon platform.