Introduction
Coded caching [1 ] studies a server with N N N files connected through a shared link to K K K users with caches of size M M M files. We call a system classical if all the users that take part in the placement phase also take part in the delivery phase, and hotplug if only A A A of the K > A K > A K > A users that took part in the placement phase are active in the delivery phase, where the set of active users is unknown at the time of placement.
The hotplug model was introduced by Ma and Tuninetti [10 ] , who proposed schemes with a placement phase based on Maximum Distance Separable (MDS) codes. In all regimes where these schemes could be shown to be optimal, the optimal tradeoff of the hotplug model coincides with that of a classical system with A A A users; in particular, it does not depend on K K K . Whether this holds in general was posed as an open question [10 , 11 ] , and it remains open.
To make progress on this open question, in [12 ] we showed that, under uncoded placement, this is not the case: the optimal scheme under uncoded placement is the natural extension of the scheme of Yu, Maddah-Ali and Avestimehr (YMA) [2 ] , in which the offline users are assigned the demands of active users, and its load is strictly larger than that of a classical system with A A A users at intermediate memory sizes. Hence, to attain the classical load in the hotplug model, coded placement is needed in general. The coded placement schemes in [12 ] cover the small memory regime A M ≤ N AM \le N A M ≤ N , where a classical system with A A A users admits row-wise placements (RWP), meaning that each file is split into A A A rows, and the cache of user a ∈ [ A ] a \in[A] a ∈ [ A ] is a function of row a a a of every file. Any such classical RWP scheme can be embedded in a Reed–Solomon code: in the hotplug model, user k ∈ [ K ] k \in[K] k ∈ [ K ] caches the same function of a coded row, namely the evaluation at a point α k \alpha_k α k of the polynomial whose coefficients are the rows; once the active users are known, their coded rows are the rows of an invertible transformation of the library, and the classical delivery applies [12 Theorem 2] . Thus, both the scheme of Gómez-Vilardebó (GV) [6 ] and the YMA point with A M = N AM = N A M = N (i.e., one cached row per file) are achievable in the hotplug model for every K ≥ A K \ge A K ≥ A . This note shows that something similar can be done at larger memory sizes.
Contributions
We give three results:
First, an explicit construction: every YMA point of a classical system with A A A users can be embedded in the hotplug model by means of a Reed–Muller code (Theorem 4); hence, the YMA tradeoff for A A A users is achievable in the hotplug model for every K ≥ A K \ge A K ≥ A .
Second, an existence result: on top of the same construction, a generic linear compression of the MAN cached data embeds every classical scheme whose cache is a linear compression of a MAN cache and whose correctness holds for generic coefficients (Theorem 5); this includes the IE scheme [7 ] . As a consequence, the hotplug tradeoff with 4 active users and 2 files equals the classical one wherever the latter is known (Corollary 4).
Finally, for A = N = 3 A = N = 3 A = N = 3 , we give a placement, row-wise up to one common subfile per file, that attains the point ( 3 5 , 3 2 ) \left(\frac{3}{5}, \frac{3}{2}\right) ( 5 3 , 2 3 ) of Cao and Xu [9 ] and embeds via the Reed–Solomon code (Proposition 1); to the best of our knowledge, no scheme that attains this point is known for other values of N N N and A A A . As a consequence, under linear coding in both placement and delivery, the hotplug tradeoff with 3 active users and 3 files equals the classical one for every K ≥ 3 K \ge3 K ≥ 3 (Proposition 1).
Paper organization
We first state the hotplug model and existing results (§ 2 ) and summarize novel results (§ 3 ), then explain the explicit construction by examples (§ 4 and § 5 ). We then prove Theorem 4 (§ 6 ) for projective Reed–Muller codes, and also give an equivalent description in terms of symmetric polynomials. We then explain why an exact embedding is limiting and prove Theorem 5 (§ 7 ). Finally, we settle the linear-optimal point ( M , R ) = ( 3 5 , 3 2 ) (M, R) = \left(\frac{3}{5}, \frac{3}{2}\right) ( M , R ) = ( 5 3 , 2 3 ) for A = N = 3 A = N = 3 A = N = 3 (§ 8 ).
Notation
Calligraphic symbols denote sets, bold symbols vectors and matrices, and sans-serif symbols system parameters. ( a b ) = 0 \binom{a}{b} = 0 ( b a ) = 0 unless a ≥ b ≥ 0 a \ge b \ge0 a ≥ b ≥ 0 . For integers a ≤ b a \le b a ≤ b , [ a : b ] : = { a , … , b } [a:b] := \{a,\ldots,b\} [ a : b ] := { a , … , b } and [ b ] : = [ 1 : b ] [b] := [1:b] [ b ] := [ 1 : b ] . For a set G \mathcal{G} G , Ω t G : = { T ⊆ G : ∣ T ∣ = t } \Omega_t^{\mathcal{G}} := \{T \subseteq\mathcal{G} : |T| = t\} Ω t G := { T ⊆ G : ∣ T ∣ = t } . For a set I ⊆ N \mathcal{I} \subseteq\mathbb{N} I ⊆ N , X I : = ( X n : n ∈ I ) X_{\mathcal{I}} := (X_n : n \in\mathcal{I}) X I := ( X n : n ∈ I ) , and d [ I ] \mathbf{d}[\mathcal{I}] d [ I ] is the sub-vector of d \mathbf{d} d restricted by I \mathcal{I} I .
Model and Known Results
Hotplug model
A server has N N N independent files F 1 , … , F N F_1,\ldots,F_N F 1 , … , F N , each of B B B i.i.d. uniform symbols over a finite field F q \mathbb{F}_q F q ; for entropies, logarithms are in base q q q . In the placement phase, user k ∈ [ K ] k \in[K] k ∈ [ K ] stores Z k Z_k Z k , a function of the files, with H ( Z k ∣ F [ N ] ) = 0 H(Z_k \mid F_{[N]}) = 0 H ( Z k ∣ F [ N ] ) = 0 and H ( Z k ) ≤ M B H(Z_k) \leq MB H ( Z k ) ≤ M B . In the delivery phase, the users in I ∈ Ω [ K ] A \mathcal{I} \in\Omega_{[K]}^{A} I ∈ Ω [ K ] A are active, and active user k k k requests file d k ∈ [ N ] d_k \in[N] d k ∈ [ N ] ; the server sends X X X , with H ( X ∣ F [ N ] , I , d [ I ] ) = 0 H(X \mid F_{[N]}, \mathcal{I}, d[\mathcal{I}]) = 0 H ( X ∣ F [ N ] , I , d [ I ]) = 0 and H ( X ) ≤ R B H(X) \leq RB H ( X ) ≤ R B , and every active user decodes its requested file as H ( F d k ∣ X , Z k , I , d [ I ] ) = 0 H(F_{d_k} \mid X, Z_k, \mathcal{I}, d[\mathcal{I}]) = 0 H ( F d k ∣ X , Z k , I , d [ I ]) = 0 for all k ∈ I k \in\mathcal{I} k ∈ I . The pair ( M , R ) (M, R) ( M , R ) is achievable if there is a scheme, for some B B B and q q q , that satisfies these constraints for every I ∈ Ω [ K ] A \mathcal{I} \in\Omega_{[K]}^{A} I ∈ Ω [ K ] A and every d [ I ] ∈ [ N ] A d[\mathcal{I}] \in[N]^{A} d [ I ] ∈ [ N ] A . We denote by R ( A , K , N ) ⋆ ( M ) R^{\star}_{(A,K,N)}(M) R ( A , K , N ) ⋆ ( M ) the optimal hotplug worst-case load, i.e., the infimum of R R R over achievable pairs ( M , R ) (M, R) ( M , R ) . The case K = A K = A K = A is the classical coded caching model.
A placement is uncoded if each user stores a subset of the symbols of the files, without coding. We denote by R u ( A , K , N ) ⋆ ( M ) R^{\star}_{u(A,K,N)}(M) R u ( A , K , N ) ⋆ ( M ) the optimal hotplug worst-case load under uncoded placement.
A scheme is linear if every cache Z k Z_k Z k , k ∈ [ K ] k \in[K] k ∈ [ K ] , and every transmission X X X , for every I \mathcal{I} I and d [ I ] d[\mathcal{I}] d [ I ] , is a linear function of ( F 1 , … , F N ) (F_1,\ldots,F_N) ( F 1 , … , F N ) over F q \mathbb{F}_q F q , i.e., placement and delivery are both linear codes. We denote by R l c ( A , K , N ) ⋆ ( M ) R^{\star}_{\mathrm{lc}(A,K,N)}(M) R lc ( A , K , N ) ⋆ ( M ) the optimal hotplug worst-case load over linear schemes, over all B B B and q q q .
Since uncoded placement is linear, and the optimal delivery under uncoded placement is linear (Theorem 2), we have R ( A , K , N ) ⋆ ≤ R l c ( A , K , N ) ⋆ ≤ R u ( A , K , N ) ⋆ ≤ r : = min ( A , N ) R^{\star}_{(A,K,N)} \leq R^{\star}_{\mathrm{lc}(A,K,N)} \leq R^{\star}_{u(A,K,N)} \leq r := \min(A,N) R ( A , K , N ) ⋆ ≤ R lc ( A , K , N ) ⋆ ≤ R u ( A , K , N ) ⋆ ≤ r := min ( A , N ) .
Known Results for classical coded caching
The YMA scheme for classical coded caching
For a classical system with A A A users and t ∈ [ 0 : A ] t \in[0:A] t ∈ [ 0 : A ] , the placement of Maddah-Ali and Niesen (MAN) [1 ] splits each file into ( A t ) \binom{A}{t} ( t A ) subfiles, F n = ( F n , W : W ∈ Ω [ A ] t ) F_n = (F_{n,\mathcal{W}} : \mathcal{W} \in\Omega_{[A]}^{t}) F n = ( F n , W : W ∈ Ω [ A ] t ) , and user a a a stores F n , W F_{n,\mathcal{W}} F n , W for all n n n and all W ∋ a \mathcal{W} \ni a W ∋ a . With the delivery of [2 ] , this achieves
( M t Y M A , R t Y M A ) = ( N t A , ( A t + 1 ) − ( A − r t + 1 ) ( A t ) ) , t ∈ [ 0 : A ] , r : = min ( A , N ) , (1) \left(M_t^{\mathrm{YMA}},R_t^{\mathrm{YMA}}\right)=\left(\frac{Nt}{A},\frac{\binom{A}{t+1}-\binom{A-r}{t+1}}{\binom{A}{t}}\right),\quad t\in[0:A],\quad r:=\min(A,N), \tag*{(1)} ( M t YMA , R t YMA ) = ( A N t , ( t A ) ( t + 1 A ) − ( t + 1 A − r ) ) , t ∈ [ 0 : A ] , r := min ( A , N ) , (1)
and the lower convex envelope of these points is optimal under uncoded placement [2 , 4 ] .
The GV scheme for classical coded caching
The GV scheme [6 ] for A A A users has a RWP: it further splits each row into pieces indexed by the g g g -subsets of [ N ] [N] [ N ] and caches sums of pieces of g g g distinct files of the same row; it achieves the lower convex envelope of ( 0 , r ) (0,r) ( 0 , r ) and the points
( M g G V , R g G V ) = ( N A g , r − N ( r + 1 ) A ( g + 1 ) ( r g ) ( N g ) ) , g ∈ [ N ] , r : = min ( A , N ) . (2) \left(M_g^{\mathrm{GV}},R_g^{\mathrm{GV}}\right)=\left(\frac{N}{A^g},r-\frac{N(r+1)}{A(g+1)}\frac{\binom{r}{g}}{\binom{N}{g}}\right),\quad g\in[N],\quad r:=\min(A,N). \tag*{(2)} ( M g GV , R g GV ) = ( A g N , r − A ( g + 1 ) N ( r + 1 ) ( g N ) ( g r ) ) , g ∈ [ N ] , r := min ( A , N ) . (2)
For g = N ≤ A g=N\leq A g = N ≤ A , this is the CFL point ( 1 A , N ( 1 − 1 A ) ) \left(\frac{1}{A},N\left(1-\frac{1}{A}\right)\right) ( A 1 , N ( 1 − A 1 ) ) [5 ] , which caches ∑ n F n , k \sum_n F_{n,k} ∑ n F n , k . For g = 1 g=1 g = 1 , this is the YMA point with t = 1 t=1 t = 1 , ( N A , r − r ( r + 1 ) 2 A ) \left(\frac{N}{A},r-\frac{r(r+1)}{2A}\right) ( A N , r − 2 A r ( r + 1 ) ) , which caches the row itself. The line through ( 0 , N ) (0,N) ( 0 , N ) and the CFL point is optimal for N ≤ A N\leq A N ≤ A [5 ] . The line through the CFL point and the GV point with g = N − 1 g=N-1 g = N − 1 , i.e., M = N A ( N − 1 ) M=\frac{N}{A(N-1)} M = A ( N − 1 ) N , is optimal for ⌈ ( A + 1 ) / 2 ⌉ ≤ N ≤ A \lceil(A+1)/2\rceil\leq N\leq A ⌈( A + 1 ) /2 ⌉ ≤ N ≤ A [15 ] ; for N = A N=A N = A , the optimality of that GV point was shown in [6 ] .
The IE scheme for classical coded caching
For a classical system with A A A users, N ≤ A N \le A N ≤ A and t ∈ [ 0 : A ] t \in[0:A] t ∈ [ 0 : A ] , the IE scheme uses the same split as the MAN placement, F n = ( F n , W : W ∈ Ω [ A ] t ) F_n = (F_{n,\mathcal{W}}:\mathcal{W} \in\Omega_{[A]}^t) F n = ( F n , W : W ∈ Ω [ A ] t ) , but user a a a does not store its P : = N ( A − 1 t − 1 ) P := N\binom{A-1}{t-1} P := N ( t − 1 A − 1 ) subfiles ( F n , W : n ∈ [ N ] , W ∋ a ) (F_{n,\mathcal{W}}:n \in[N],\mathcal{W} \ni a) ( F n , W : n ∈ [ N ] , W ∋ a ) ; it stores fewer linear combinations of them, namely the parity symbols of a systematic code (a rank-metric code in [7 ] ) that encodes them. These combinations mix subfiles of different files and with different indices W \mathcal{W} W . In the delivery, the server sends uncoded the subfiles that are not present at any user requesting the same file, together with parity symbols of MDS codes that encode groups of subfiles of the same file; each user first uses the received symbols to eliminate, from its cached combinations, the subfiles of the files it does not request (the interference), and then decodes the subfiles of its requested file. This achieves
( M t I E , R t I E ) = ( t [ ( N − 1 ) t + A − N ] A ( A − 1 ) , N ( A − t ) A ) , t ∈ [ 0 : A ] . (3) \left(M_t^{\mathrm{IE}},R_t^{\mathrm{IE}}\right)=\left(\frac{t\left[(N-1)t+A-N\right]}{A(A-1)},\frac{N(A-t)}{A}\right),\quad t\in[0:A]. \tag*{(3)} ( M t IE , R t IE ) = ( A ( A − 1 ) t [ ( N − 1 ) t + A − N ] , A N ( A − t ) ) , t ∈ [ 0 : A ] . (3)
Correctness reduces to the full rank of certain matrices, whose determinants are polynomials in the coefficients of the cached combinations; these polynomials are not identically zero, and generic coefficients over a sufficiently large field can replace the rank-metric code, with the same MDS codes in the delivery [7 Section VI-D] .
IE improves on YMA at small memory sizes; for t = 1 t=1 t = 1 it is the point of Chen, Fan and Letaief (CFL) [5 ] , and for ( A , N ) = ( 4 , 2 ) (A,N)=(4,2) ( A , N ) = ( 4 , 2 ) and t = 2 t=2 t = 2 it is ( 2 3 , 1 ) (\frac{2}{3},1) ( 3 2 , 1 ) , which is optimal [8 ] .
Known Results for hotplug coded caching
Our past work showed that the following points of a classical system with A A A users are achievable in the hotplug model for every K ≥ A K\ge A K ≥ A : the CFL point for A ≥ N A\ge N A ≥ N [10 Scheme new2] (HT2 in [11 ] ), the YMA point with t = 1 t=1 t = 1 [10 Scheme new1] (HT1 with t = 1 t=1 t = 1 in [11 ] ), and the YMA point with t = A − 1 t=A-1 t = A − 1 for A ≥ 3 A\ge3 A ≥ 3 [11 Scheme HT3] . In [10 Scheme new1] we also added an MDS layer to the MAN placement with t ≥ 2 t\ge2 t ≥ 2 , which attains the YMA load of a classical system with A A A users, but with a memory size that depends on both A A A and K K K .
In particular, the YMA+ scheme [10 ] uses the MAN placement for K K K users with parameter t ∈ [ 0 : K ] t\in[0:K] t ∈ [ 0 : K ] and the YMA delivery for K K K users, in which each offline user is assigned the demand of an active user; it achieves
( M t Y M A + , R t Y M A + ) = ( N t K , ( K t + 1 ) − ( K − r t + 1 ) ( K t ) ) , t ∈ [ 0 : K ] , r : = min ( A , N ) , (4) \left(M_t^{\mathrm{YMA+}},R_t^{\mathrm{YMA+}}\right)=\left(\frac{Nt}{K},\frac{\binom{K}{t+1}-\binom{K-r}{t+1}}{\binom{K}{t}}\right),\quad t\in[0:K],\quad r:=\min(A,N), \tag*{(4)} ( M t YMA + , R t YMA + ) = ( K N t , ( t K ) ( t + 1 K ) − ( t + 1 K − r ) ) , t ∈ [ 0 : K ] , r := min ( A , N ) , (4)
and we denote by R ( A , K , N ) ( Y M A + ) ( M ) R_{(A,K,N)}^{(\mathrm{YMA+})}(M) R ( A , K , N ) ( YMA + ) ( M ) the lower convex envelope of these points.
Theorem 1 (Optimality of YMA+ to within a factor of two [10 , 11 ] ). For an ( A , K , N ) (A,K,N) ( A , K , N ) hotplug model,
R ( A , N ) ( d e c ) 2.00884 ≤ ( i ) R ( A , A , N ) ∗ ≤ R ( A , K , N ) ∗ ≤ ( i i ) R ( A , K , N ) ( Y M A + ) ≤ R ( A , N ) ( d e c ) , (5) \frac{R_{(A,N)}^{(\mathrm{dec})}}{2.00884}\mathrel{\leq}^{(i)}R_{(A,A,N)}^*\leq R_{(A,K,N)}^*\mathrel{\leq}^{(ii)}R_{(A,K,N)}^{(\mathrm{YMA+})}\leq R_{(A,N)}^{(\mathrm{dec})}, \tag*{(5)} 2.00884 R ( A , N ) ( dec ) ≤ ( i ) R ( A , A , N ) ∗ ≤ R ( A , K , N ) ∗ ≤ ( ii ) R ( A , K , N ) ( YMA + ) ≤ R ( A , N ) ( dec ) , (5) where the lower bounds depend only on A A A , the inequalities marked as ( i ) (i) ( i ) and ( i i ) (ii) ( ii ) are from [3 ] , and
R ( A , N ) ( d e c ) = lim K → ∞ R ( A , K , N ) ( Y M A + ) = 1 − μ μ ( 1 − ( 1 − μ ) r ) , μ = M / N , (6) R_{(A,N)}^{(\mathrm{dec})}=\lim_{K\to\infty}R_{(A,K,N)}^{(\mathrm{YMA+})}=\frac{1-\mu}{\mu}\left(1-(1-\mu)^r\right),\quad\mu=M/N, \tag*{(6)} R ( A , N ) ( dec ) = K → ∞ lim R ( A , K , N ) ( YMA + ) = μ 1 − μ ( 1 − ( 1 − μ ) r ) , μ = M / N , (6) is the load with decentralized placement. The chain of inequalities in (5) shows that YMA+ is optimal to within a factor of two [11 ] .
Theorem 2 (Optimality of YMA+ under uncoded placement [12 ] ). For an ( A , K , N ) (A,K,N) ( A , K , N ) hotplug model, R ( A , K , N ) ∗ ( M ) = R ( A , K , N ) ( Y M A + ) ( M ) R^*_{(A,K,N)}(M) = R^{(\mathrm{YMA+})}_{(A,K,N)}(M) R ( A , K , N ) ∗ ( M ) = R ( A , K , N ) ( YMA + ) ( M ) for all M ∈ [ 0 , N ] M \in[0,N] M ∈ [ 0 , N ] .
Theorem 3 (Reed–Solomon embedding of row-wise placement schemes [12 ] ). Let a classical scheme for A A A users with RWP, over a field F q 0 \mathbb{F}_{q_0} F q 0 , achieve ( M , R ) (M,R) ( M , R ) , with possibly nonlinear cache placement and delivery functions. Then ( M , R ) (M,R) ( M , R ) is also achievable in the ( A , K , N ) (A,K,N) ( A , K , N ) hotplug model for every K ≥ A K \ge A K ≥ A , over any extension field F q \mathbb{F}_q F q of F q 0 \mathbb{F}_{q_0} F q 0 with q ≥ K − 1 q \ge K-1 q ≥ K − 1 .
Corollary 1 (Application of Theorem 3: GV in the hotplug model). For every K ≥ A K \ge A K ≥ A , the lower convex envelope of the GV points (2) of a classical system with A A A users is achievable in the hotplug model with A A A active users out of K K K . This also includes YMA for t = 1 t=1 t = 1 , which is the GV point for g = 1 g=1 g = 1 .
Main Results
Part 1: exact embedding
We consider the following class of placements, which contains the MAN placement and the GV placement.
Definition 1 (Linear t t t -subset placement). For a classical system with A A A users, fix t ∈ [ A ] t \in[A] t ∈ [ A ] . Each file is split into ( A t ) \binom{A}{t} ( t A ) subfiles of equal size as F n = ( F n , W : W ∈ Ω [ A ] t ) F_n=(F_{n,\mathcal{W}}:\mathcal{W}\in\Omega^{t}_{[A]}) F n = ( F n , W : W ∈ Ω [ A ] t ) with F n , W ∈ F q 1 × B / ( A t ) F_{n,\mathcal{W}}\in\mathbb{F}_q^{1\times B/\binom{A}{t}} F n , W ∈ F q 1 × B / ( t A ) ; define f W : = [ F 1 , W , … , F N , W ] ∈ F q 1 × N B / ( A t ) \mathbf{f}_{\mathcal{W}} := [F_{1,\mathcal{W}},\ldots,F_{N,\mathcal{W}}]\in\mathbb{F}_q^{1\times NB/\binom{A}{t}} f W := [ F 1 , W , … , F N , W ] ∈ F q 1 × N B / ( t A ) as the concatenation of the subfiles indexed by W \mathcal{W} W of all files. A placement is a linear t t t -subset placement if
Z a = ( L [ f W ] : W ∈ Ω [ A ] t , W ∋ a ) , a ∈ [ A ] , (7) Z_a=\left(\mathcal{L}[\mathbf{f}_{\mathcal{W}}]:\mathcal{W}\in\Omega^t_{[A]},\ \mathcal{W}\ni a\right),\quad a\in[A], \tag*{(7)} Z a = ( L [ f W ] : W ∈ Ω [ A ] t , W ∋ a ) , a ∈ [ A ] , (7)
where L : F q 1 × N B / ( A t ) → F q 1 × M B / ( A − 1 t − 1 ) \mathcal{L}:\mathbb{F}_q^{1\times NB/\binom{A}{t}}\to\mathbb{F}_q^{1\times MB/\binom{A-1}{t-1}} L : F q 1 × N B / ( t A ) → F q 1 × M B / ( t − 1 A − 1 ) is a linear operator, the same for every W \mathcal{W} W and every user; hence the cache size is M B MB M B .
Definition 1 does not allow combinations of subfiles with different indices W \mathcal{W} W ; these are considered in Definition 2. The MAN placement is the case where L \mathcal{L} L is the identity, i.e., M = N t / A M=Nt/A M = N t / A . The CFL placement [5 ] , in which user a a a stores ∑ n F n , { a } \sum_n F_{n,\{a\}} ∑ n F n , { a } , is the case t = 1 t=1 t = 1 and L [ x 1 , … , x N ] = x 1 + ⋯ + x N \mathcal{L}[x_1,\ldots,x_N]=x_1+\cdots+x_N L [ x 1 , … , x N ] = x 1 + ⋯ + x N , i.e., M = 1 / A M=1/A M = 1/ A .
Note: the placement of Proposition 1 in § 8 for A = N = 3 A=N=3 A = N = 3 and M = 3 5 M=\frac{3}{5} M = 5 3 is not of the form of Definition 1, because each cached symbol combines private subfiles of one user (t = 1 t=1 t = 1 ) with a subfile common to all users (t = 3 t=3 t = 3 ).
Theorem 4 (Reed–Muller embedding). Let a classical scheme for A A A users with a linear t t t -subset placement, over a field F q 0 \mathbb{F}_{q_0} F q 0 , achieve ( M , R ) (M,R) ( M , R ) , with a possibly nonlinear delivery. Then ( M , R ) (M,R) ( M , R ) is also achievable in the hotplug model with A A A active users out of K K K , for every K ≥ A K \ge A K ≥ A , over any extension field F q \mathbb{F}_q F q of F q 0 \mathbb{F}_{q_0} F q 0 with q ≥ K − 1 q \ge K-1 q ≥ K − 1 .
Corollary 2 (Application of Theorem 4: YMA in the hotplug model). For every K ≥ A K \ge A K ≥ A , the lower convex envelope of the YMA points (1) of a classical system with A A A users is achievable in the hotplug model with A A A active users out of K K K .
Proof of Corollary 2. The point ( 0 , r ) (0,r) ( 0 , r ) is trivial. For t ∈ [ A ] t\in[A] t ∈ [ A ] , apply Theorem 4 to the MAN placement with parameter t t t . Finally, use memory sharing, which is compatible with the hotplug model since the placements do not depend on the active users. The subpacketization is the same as in the classical scheme. ∩ევნ
Remark 1 (Relation to the Reed–Solomon embedding). For t = 1 t = 1 t = 1 , Theorem 4 recovers [12 Theorem 2] for row-wise placements with a linear cache function . The latter is more general: since for t = 1 t = 1 t = 1 the restriction to the user’s hyperplane is a single coded row, the cache may be any function of it, linear or not. For t ≥ 2 t \ge2 t ≥ 2 , the restriction determines the classical subfiles only after the active users are known, so the cache must be computable from the restriction without knowing them; the linearity in Definition 1 guarantees this. Hence the results of this note do not supersede [12 Theorem 2] .
Remark 2. Corollary 2, together with [12 Corollary 1] , shows that at every memory size M = N t / A M = Nt/A M = N t / A , t ∈ [ A − 1 ] t \in[A - 1] t ∈ [ A − 1 ] , with min ( A , N ) ≥ 2 \min(A, N) \ge2 min ( A , N ) ≥ 2 and K > A K > A K > A , coded placement attains a load that no uncoded placement can attain in the hotplug model. For example, for ( A , K , N ) = ( 4 , 5 , 3 ) (A,K,N) = (4,5,3) ( A , K , N ) = ( 4 , 5 , 3 ) and M = 3 2 M = \frac{3}{2} M = 2 3 (i.e., t = 2 t = 2 t = 2 ), every uncoded placement has load at least 3 4 \frac{3}{4} 4 3 (memory sharing between the YMA+ points ( 6 5 , 1 ) (\frac{6}{5},1) ( 5 6 , 1 ) and ( 9 5 , 1 2 ) (\frac{9}{5},\frac{1}{2}) ( 5 9 , 2 1 ) [12 ] ), whereas Corollary 2 attains 2 3 \frac{2}{3} 3 2 . Theorem 4 also recovers the MDS-based schemes of [10 , 11 ] that attain YMA points, t = 1 t = 1 t = 1 and t = A − 1 t = A - 1 t = A − 1 (HT3, see § 4.3 ), and, for t ≥ 2 t \ge2 t ≥ 2 , it attains the YMA load of [10 Scheme new1] with the memory size of the classical system, rather than one that depends on K K K . Combined with the Reed–Solomon embedding of GV [12 Theorem 2] , the hotplug model attains the lower convex envelope of the GV and YMA points of a classical system with A A A users, for every K ≥ A K \ge A K ≥ A .
Part 2: generic embedding
In Definition 1, the same linear map acts on each subset separately. Some classical schemes with coded placement, such as the IE scheme, instead compress the whole MAN cache of a user jointly, mixing different files and different subsets.
Definition 2 (Linear MAN-compression placement, generic correctness). For a classical system with A A A users, fix t ∈ [ A ] t \in[A] t ∈ [ A ] , split each file as in Definition 1, and let
s a : = ( F n , W : n ∈ [ N ] , W ∈ Ω [ A ] t , W ∋ a ) ∈ F q 1 × B N t A (8) s_a := (F_{n,W}: n \in[N],\ W \in\Omega_{[A]}^t,\ W \ni a) \in\mathbb{F}_q^{1 \times B\frac{N_t}{A}} \tag*{(8)} s a := ( F n , W : n ∈ [ N ] , W ∈ Ω [ A ] t , W ∋ a ) ∈ F q 1 × B A N t (8)
be the MAN cache of user a a a , i.e., the concatenation of its N ( A − 1 t − 1 ) N\binom{A-1}{t-1} N ( t − 1 A − 1 ) subfiles in a fixed order. A placement is a linear MAN-compression placement if
Z a = L a [ s a ] , a ∈ [ A ] , (9) Z_a = \mathcal{L}_a[s_a],\quad a \in[A], \tag*{(9)} Z a = L a [ s a ] , a ∈ [ A ] , (9)
where L a : F q 1 × B N t A → F q 1 × B M \mathcal{L}_a : \mathbb{F}_q^{1 \times B\frac{N_t}{A}} \to\mathbb{F}_q^{1 \times BM} L a : F q 1 × B A N t → F q 1 × B M is a linear operator, possibly different for each user. A classical scheme with such a placement and with a linear delivery is generically correct with load R R R if there are a field F q 0 \mathbb{F}_{q_0} F q 0 , a linear transmission X d = D d [ F 1 , … , F N ] X_{\mathbf d} = \mathcal{D}_{\mathbf d}[F_1,\ldots,F_N] X d = D d [ F 1 , … , F N ] of R B RB R B symbols with coefficients in F q 0 \mathbb{F}_{q_0} F q 0 for every demand vector d \mathbf d d , not depending on ( L 1 , … , L A ) (\mathcal{L}_1,\ldots,\mathcal{L}_A) ( L 1 , … , L A ) , and a polynomial g ≠ 0 g \ne0 g = 0 with coefficients in F q 0 \mathbb{F}_{q_0} F q 0 in the entries of the matrices of L 1 , … , L A \mathcal{L}_1,\ldots,\mathcal{L}_A L 1 , … , L A , such that, over every extension field F q \mathbb{F}_q F q of F q 0 \mathbb{F}_{q_0} F q 0 and for all operators L 1 , … , L A \mathcal{L}_1,\ldots,\mathcal{L}_A L 1 , … , L A over F q \mathbb{F}_q F q with g ( L 1 , … , L A ) ≠ 0 g(\mathcal{L}_1,\ldots,\mathcal{L}_A) \ne0 g ( L 1 , … , L A ) = 0 , every user decodes its demanded file for every d \mathbf d d .
The MAN placement is the case in which L a \mathcal{L}_a L a is the identity, i.e., M = N t / A M = Nt/A M = N t / A , and the placement of Definition 1 is the case in which L a \mathcal{L}_a L a applies L \mathcal{L} L to each subset W ∋ a W \ni a W ∋ a separately, the same for every user.
Theorem 5 (Generic Reed–Muller embedding). Let a classical scheme for A A A users with a linear MAN-compression placement be generically correct with load R R R , with F q 0 \mathbb{F}_{q_0} F q 0 and g g g as in Definition 2. Then ( M , R ) (M,R) ( M , R ) is achievable in the hotplug model with A A A active users out of K K K , for every K ≥ A K \ge A K ≥ A , over every extension field F q \mathbb{F}_q F q of F q 0 \mathbb{F}_{q_0} F q 0 with q ≥ K − 1 q \ge K - 1 q ≥ K − 1 and q > ( K A ) deg ( g ) q > \binom{K}{A}\deg(g) q > ( A K ) deg ( g ) .
Corollary 3 (Application of Theorem 5: IE in the hotplug model). Let N ≤ A N \le A N ≤ A . For every K ≥ A K \ge A K ≥ A , the lower convex envelope of the IE points (3) of a classical system with A A A users is achievable in the hotplug model with A A A active users out of K K K .
Proof of Corollary 3. The point ( 0 , N ) (0,N) ( 0 , N ) , i.e., t = 0 t=0 t = 0 , is trivial. For t ∈ [ A ] t \in[A] t ∈ [ A ] , the IE placement is a linear MAN-compression placement with L a \mathcal{L}_a L a the parity part of the systematic code that user a a a applies to s a \mathbf{s}_a s a , and its delivery uses fixed MDS codes; by [7 Section VI-D] , the scheme is generically correct. Apply Theorem 5, and use memory sharing as in Corollary 2. The subpacketization is the same as in the classical scheme. □
Consequences
Corollary 4 (Combination of Corollaries 1, 2, and 3: the hotplug case of A = 4 A=4 A = 4 active users and N = 2 N=2 N = 2 files). For every K ≥ A = 4 K \ge A=4 K ≥ A = 4 , R ( 4 , K , 2 ) ( M ) = R ( 4 , 4 , 2 ) ( M ) R_{(4,K,2)}(M)=R_{(4,4,2)}(M) R ( 4 , K , 2 ) ( M ) = R ( 4 , 4 , 2 ) ( M ) for M ∈ [ 0 , 1 4 ] ∪ [ 2 3 , 2 ] M \in[0,\frac{1}{4}] \cup[\frac{2}{3},2] M ∈ [ 0 , 4 1 ] ∪ [ 3 2 , 2 ] , i.e., wherever the classical optimal tradeoff with 4 users and 2 files is known.
Proof of Corollary 4. On [ 0 , 1 4 ] [0,\frac{1}{4}] [ 0 , 4 1 ] , the classical tradeoff is the line through ( 0 , 2 ) (0,2) ( 0 , 2 ) and the CFL point ( 1 4 , 3 2 ) (\frac{1}{4},\frac{3}{2}) ( 4 1 , 2 3 ) [5 ] , achievable for every K ≥ 4 K \ge4 K ≥ 4 by Corollary 1. On [ 2 3 , 2 ] [\frac{2}{3},2] [ 3 2 , 2 ] , its corner points are ( 2 3 , 1 ) (\frac{2}{3},1) ( 3 2 , 1 ) , attained by the IE scheme with t = 2 t=2 t = 2 and meeting the converse of [8 ] , and the YMA points ( 1 , 2 3 ) (1,\frac{2}{3}) ( 1 , 3 2 ) , ( 3 2 , 1 4 ) (\frac{3}{2},\frac{1}{4}) ( 2 3 , 4 1 ) and ( 2 , 0 ) (2,0) ( 2 , 0 ) [8 ] ; they are achievable for every K ≥ 4 K \ge4 K ≥ 4 by Corollaries 3 and 2. □
Example N = A = 3 N=A=3 N = A = 3
Consider N = 3 N=3 N = 3 files, A A A , B B B and C C C , and A = 3 A=3 A = 3 active users out of K ≥ 3 K \ge3 K ≥ 3 . Let a 1 , … , a K ∈ F q a_1,\ldots,a_K \in\mathbb{F}_q a 1 , … , a K ∈ F q be distinct, which requires q ≥ K q \ge K q ≥ K (the point at infinity, discussed below, allows q ≥ K − 1 q \ge K-1 q ≥ K − 1 ), and let the active users be I = { i 1 , i 2 , i 3 } \mathcal{I}=\{i_1,i_2,i_3\} I = { i 1 , i 2 , i 3 } , requesting A A A , B B B and C C C , respectively. Indices of subfiles refer to the positions j ∈ [ 3 ] j \in[3] j ∈ [ 3 ] of the active users in I \mathcal{I} I .
t = 1 t=1 t = 1 : Reed–Solomon embedding from [12 ]
The YMA point with t = 1 t=1 t = 1 is ( M , R ) = ( 1 , 1 ) (M,R)=(1,1) ( M , R ) = ( 1 , 1 ) . Split each file into three rows, A = ( A 0 , A 1 , A 2 ) A=(A_0,A_1,A_2) A = ( A 0 , A 1 , A 2 ) , and so on. In the classical system, user j ∈ [ 3 ] j \in[3] j ∈ [ 3 ] caches row j − 1 j-1 j − 1 of every file (we enumerated the subfile starting from 0), a row-wise placement. In the hotplug model, user k ∈ [ K ] k \in[K] k ∈ [ K ] caches
Z k = ( p A ( a k ) , p B ( a k ) , p C ( a k ) ) , p A ( z ) : = A 0 + A 1 z + A 2 z 2 , (10) Z_k=\left(p_A(a_k),p_B(a_k),p_C(a_k)\right),\qquad p_A(z):=A_0+A_1z+A_2z^2, \tag*{(10)} Z k = ( p A ( a k ) , p B ( a k ) , p C ( a k ) ) , p A ( z ) := A 0 + A 1 z + A 2 z 2 , (10)
and similarly for p B ( z ) p_B(z) p B ( z ) and p C ( z ) p_C(z) p C ( z ) ; each user caches one coded row per file, so that M = 1 M=1 M = 1 . The vector ( p A ( a k ) : k ∈ [ K ] ) (p_A(a_k):k \in[K]) ( p A ( a k ) : k ∈ [ K ]) is a codeword of a [ K , 3 ] [K,3] [ K , 3 ] Reed–Solomon code. Once I = { i 1 , i 2 , i 3 } \mathcal{I}=\{i_1,i_2,i_3\} I = { i 1 , i 2 , i 3 } is known, define the new library
A j ′ : = p A ( a i j ) , B j ′ : = p B ( a i j ) , C j ′ : = p C ( a i j ) , j ∈ [ 3 ] . (11) A'_j:=p_A(a_{i_j}),\qquad B'_j:=p_B(a_{i_j}),\qquad C'_j:=p_C(a_{i_j}),\qquad j \in[3]. \tag*{(11)} A j ′ := p A ( a i j ) , B j ′ := p B ( a i j ) , C j ′ := p C ( a i j ) , j ∈ [ 3 ] . (11)
The map ( A 0 , A 1 , A 2 ) ↦ ( A 1 ′ , A 2 ′ , A 3 ′ ) (A_0,A_1,A_2)\mapsto(A'_1,A'_2,A'_3) ( A 0 , A 1 , A 2 ) ↦ ( A 1 ′ , A 2 ′ , A 3 ′ ) is given by a 3 × 3 3 \times3 3 × 3 Vandermonde matrix with distinct nodes, hence it is invertible. User i j i_j i j caches exactly ( A j ′ , B j ′ , C j ′ ) (A'_j,B'_j,C'_j) ( A j ′ , B j ′ , C j ′ ) , i.e., the cache of classical user j j j for the new library. The server sends the classical delivery for the new library
A 2 ′ + B 1 ′ , A 3 ′ + C 1 ′ , B 3 ′ + C 2 ′ (12) A'_2+B'_1,\qquad A'_3+C'_1,\qquad B'_3+C'_2 \tag*{(12)} A 2 ′ + B 1 ′ , A 3 ′ + C 1 ′ , B 3 ′ + C 2 ′ (12)
of load R = 1 R=1 R = 1 . User i 1 i_1 i 1 , for example, obtains A 2 ′ A'_2 A 2 ′ and A 3 ′ A'_3 A 3 ′ from the first two transmissions, recovers ( A 1 ′ , A 2 ′ , A 3 ′ ) (A'_1,A'_2,A'_3) ( A 1 ′ , A 2 ′ , A 3 ′ ) , and inverts the Vandermonde matrix to obtain A A A .
t=1 revisited: the projective view
The scheme in Section 4.1 can be described geometrically, in a way that extends to t ≥ 2 t \ge2 t ≥ 2 . Associate with user k k k the normal vector h k : = ( 1 , a k ) ∈ F q 2 \mathbf{h}_k := (1,a_k) \in\mathbb{F}_q^2 h k := ( 1 , a k ) ∈ F q 2 and the hyperplane H k : = { x ∈ F q 2 : h k ⋅ x = 0 } H_k := \{\mathbf{x} \in\mathbb{F}_q^2 : \mathbf{h}_k \cdot\mathbf{x} = 0\} H k := { x ∈ F q 2 : h k ⋅ x = 0 } , which is the one-dimensional subspace spanned by p { k } : = ( − a k , 1 ) \mathbf{p}_{\{k\}} := (-a_k,1) p { k } := ( − a k , 1 ) , a point of the projective line. Write file A A A as a homogeneous polynomial of degree A − t = 2 A-t=2 A − t = 2 in t + 1 = 2 t+1=2 t + 1 = 2 variables,
f A ( x 0 , x 1 ) : = A 2 x 0 2 − A 1 x 0 x 1 + A 0 x 1 2 ; (13) f_A(x_0,x_1) := A_2x_0^2 - A_1x_0x_1 + A_0x_1^2; \tag*{(13)} f A ( x 0 , x 1 ) := A 2 x 0 2 − A 1 x 0 x 1 + A 0 x 1 2 ; (13)
note that f A ( p { k } ) = p A ( a k ) f_A(\mathbf{p}_{\{k\}}) = p_A(a_k) f A ( p { k } ) = p A ( a k ) with p A ( z ) p_A(z) p A ( z ) defined in (10) . User k k k caches the restriction of f A f_A f A to H k H_k H k , i.e., its value at p { k } \mathbf{p}_{\{k\}} p { k } , as the hyperplane H k H_k H k is one-dimensional. Once I = { i 1 , i 2 , i 3 } \mathcal{I} = \{i_1,i_2,i_3\} I = { i 1 , i 2 , i 3 } is known, the subfiles of the new library are the values at the points p { j } \mathbf{p}_{\{j\}} p { j } , j ∈ I j \in\mathcal{I} j ∈ I . The normal vector h = ( 0 , 1 ) \mathbf{h} = (0,1) h = ( 0 , 1 ) , i.e., the point p = ( 1 , 0 ) \mathbf{p} = (1,0) p = ( 1 , 0 ) “at infinity”, gives f A ( 1 , 0 ) = A 2 f_A(1,0) = A_2 f A ( 1 , 0 ) = A 2 , and allows one more user, K = q + 1 K=q+1 K = q + 1 .
t=2: Reed–Muller embedding recovering scheme HT3 in [11 ]
The YMA point with t = 2 t=2 t = 2 is ( M , R ) = ( 2 , 1 3 ) (M,R) = (2,\frac{1}{3}) ( M , R ) = ( 2 , 3 1 ) . Associate with user k k k the plane H k : = { x ∈ F q 3 : h k ⋅ x = 0 } H_k := \{\mathbf{x} \in\mathbb{F}_q^3 : \mathbf{h}_k \cdot\mathbf{x} = 0\} H k := { x ∈ F q 3 : h k ⋅ x = 0 } with normal vector h k : = ( 1 , a k , a k 2 ) \mathbf{h}_k := (1,a_k,a_k^2) h k := ( 1 , a k , a k 2 ) . Any three of these normal vectors are linearly independent (Vandermonde), so any two planes meet in a line, spanned by
p { k , l } : = ( a k a l , − ( a k + a l ) , 1 ) , (14) \mathbf{p}_{\{k,l\}} := (a_ka_l,-(a_k+a_l),1), \tag*{(14)} p { k , l } := ( a k a l , − ( a k + a l ) , 1 ) , (14)
the coefficient vector of ( z − a k ) ( z − a l ) (z-a_k)(z-a_l) ( z − a k ) ( z − a l ) ; indeed h k ⋅ p { k , l } = a k a l − a k ( a k + a l ) + a k 2 = 0 = h l ⋅ p { k , l } \mathbf{h}_k \cdot\mathbf{p}_{\{k,l\}} = a_ka_l-a_k(a_k+a_l)+a_k^2=0=\mathbf{h}_l \cdot\mathbf{p}_{\{k,l\}} h k ⋅ p { k , l } = a k a l − a k ( a k + a l ) + a k 2 = 0 = h l ⋅ p { k , l } , while h j ⋅ p { k , l } = ( a j − a k ) ( a j − a l ) ≠ 0 \mathbf{h}_j \cdot\mathbf{p}_{\{k,l\}}=(a_j-a_k)(a_j-a_l)\ne0 h j ⋅ p { k , l } = ( a j − a k ) ( a j − a l ) = 0 for j ∉ { k , l } j \notin\{k,l\} j ∈ / { k , l } .
Split each file into ( 3 2 ) = 3 \binom{3}{2}=3 ( 2 3 ) = 3 subfiles and write it as a homogeneous polynomial of degree A − t = 1 A-t=1 A − t = 1 in t + 1 = 3 t+1=3 t + 1 = 3 variables, i.e., a linear form,
f A ( x ) : = A 0 x 0 + A 1 x 1 + A 2 x 2 , x = ( x 0 , x 1 , x 2 ) , (15) f_A(\mathbf{x}) := A_0x_0+A_1x_1+A_2x_2,\quad\mathbf{x}=(x_0,x_1,x_2), \tag*{(15)} f A ( x ) := A 0 x 0 + A 1 x 1 + A 2 x 2 , x = ( x 0 , x 1 , x 2 ) , (15)
and similarly for B B B and C C C . User k k k caches the restriction of f A f_A f A to its plane H k H_k H k , which is spanned by u k , 1 : = ( − a k , 1 , 0 ) \mathbf{u}_{k,1}:=(-a_k,1,0) u k , 1 := ( − a k , 1 , 0 ) and u k , 2 : = ( 0 , − a k , 1 ) \mathbf{u}_{k,2}:=(0,-a_k,1) u k , 2 := ( 0 , − a k , 1 ) (the coefficient vectors of z − a k z-a_k z − a k and z ( z − a k ) z(z-a_k) z ( z − a k ) ); that is, user k k k caches
f A ( u k , 1 ) = A 1 − a k A 0 , f A ( u k , 2 ) = A 2 − a k A 1 , (16) f_A(\mathbf{u}_{k,1})=A_1-a_kA_0,\qquad f_A(\mathbf{u}_{k,2})=A_2-a_kA_1, \tag*{(16)} f A ( u k , 1 ) = A 1 − a k A 0 , f A ( u k , 2 ) = A 2 − a k A 1 , (16)
and similarly for B B B and C C C , so that M = 3 ⋅ 2 3 = 2 M=3\cdot\frac{2}{3}=2 M = 3 ⋅ 3 2 = 2 . This is the scheme HT3 of [11 ] , in which user k k k stores the projection of each file onto a plane.
Once I = { i 1 , i 2 , i 3 } \mathcal{I}=\{i_1,i_2,i_3\} I = { i 1 , i 2 , i 3 } is known, the subfiles of the new library are the values at the intersection points of the active planes,
A { j , l } ′ : = f A ( p { i j , i l } ) , { j , l } ∈ Ω [ 3 ] 2 . (17) A'_{\{j,l\}} := f_A(\mathbf{p}_{\{i_j,i_l\}}),\qquad\{j,l\}\in\Omega^2_{[3]}. \tag*{(17)} A { j , l } ′ := f A ( p { i j , i l } ) , { j , l } ∈ Ω [ 3 ] 2 . (17)
User i 1 i_1 i 1 knows A 12 ′ A'_{12} A 12 ′ and A 13 ′ A'_{13} A 13 ′ : since p { k , l } = − a l u k , 1 + u k , 2 \mathbf{p}_{\{k,l\}}=-a_l\mathbf{u}_{k,1}+\mathbf{u}_{k,2} p { k , l } = − a l u k , 1 + u k , 2 , it computes f A ( p { k , l } ) = − a l f A ( u k , 1 ) + f A ( u k , 2 ) f_A(\mathbf{p}_{\{k,l\}})=-a_lf_A(\mathbf{u}_{k,1})+f_A(\mathbf{u}_{k,2}) f A ( p { k , l } ) = − a l f A ( u k , 1 ) + f A ( u k , 2 ) with k = i 1 k=i_1 k = i 1 (here everything is linear). Conversely, these two values determine the restriction of f A f_A f A to H i 1 H_{i_1} H i 1 , since p { i 1 , i 2 } \mathbf{p}_{\{i_1,i_2\}} p { i 1 , i 2 } and p { i 1 , i 3 } \mathbf{p}_{\{i_1,i_3\}} p { i 1 , i 3 } are independent vectors of H i 1 H_{i_1} H i 1 . Hence the cache of user i j i_j i j is equivalent to the MAN cache of classical user j j j with t = 2 t=2 t = 2 for the new library: both describe the restriction of the files to H i j H_{i_j} H i j , in two different bases. With b j : = a i j b_j:=a_{i_j} b j := a i j , j ∈ [ 3 ] j\in[3] j ∈ [ 3 ] , the map ( A 0 , A 1 , A 2 ) ↦ ( A 12 ′ , A 13 ′ , A 23 ′ ) (A_0,A_1,A_2)\mapsto(A'_{12},A'_{13},A'_{23}) ( A 0 , A 1 , A 2 ) ↦ ( A 12 ′ , A 13 ′ , A 23 ′ ) has matrix
\begin{pmatrix}
b_1b_2 & -(b_1+b_2) & 1\\
b_1b_3 & -(b_1+b_3) & 1\\
b_2b_3 & -(b_2+b_3) & 1
\end{pmatrix},
\qquad\text{with determinant}\quad-(b_1-b_2)(b_1-b_3)(b_2-b_3)\ne0, \tag*{(18)}\end{pmatrix}
so the new files are obtained from an invertible mapping. The server sends the classical delivery for the new library
A 23 ′ + B 13 ′ + C 12 ′ , (19) A'_{23}+B'_{13}+C'_{12}, \tag*{(19)} A 23 ′ + B 13 ′ + C 12 ′ , (19)
of load R = 1 3 R=\frac{1}{3} R = 3 1 . User i 1 i_1 i 1 knows B 13 ′ B'_{13} B 13 ′ and C 12 ′ C'_{12} C 12 ′ , decodes A 23 ′ A'_{23} A 23 ′ , recovers ( A 12 ′ , A 13 ′ , A 23 ′ ) (A'_{12},A'_{13},A'_{23}) ( A 12 ′ , A 13 ′ , A 23 ′ ) , and inverts the matrix above to obtain A A A .
Conclusion for the case of three active users and three files
For t = 0 t=0 t = 0 and t = 3 t=3 t = 3 , the YMA points ( 0 , 3 ) (0,3) ( 0 , 3 ) and ( 3 , 0 ) (3,0) ( 3 , 0 ) are trivially achievable. Hence the YMA tradeoff of the classical system with 3 users and 3 files is achievable in the hotplug model for every K ≥ 3 K \ge3 K ≥ 3 . While this example is easy to describe, it gives no new scheme compared to the state of the art [11 ] .
Example N = 3 N=3 N = 3 , A = 4 A=4 A = 4
For the cases in § 4 , the files are represented as linear forms. For A ≥ 4 A \ge4 A ≥ 4 and 2 ≤ t ≤ A − 2 2 \le t \le A-2 2 ≤ t ≤ A − 2 , the files are homogeneous polynomials of degree A − t ≥ 2 A-t \ge2 A − t ≥ 2 in t + 1 ≥ 3 t+1 \ge3 t + 1 ≥ 3 variables, and the restriction of a file to a hyperplane is itself a polynomial of the same degree in t t t variables (aka one less variable); these are the cases that were not covered by previous hotplug schemes at the memory size of the classical system. The smallest such case follows.
Case t = 2 t=2 t = 2 : a new point
The YMA point with A = 4 A=4 A = 4 , N = 3 N=3 N = 3 and t = 2 t=2 t = 2 is ( M , R ) = ( 3 2 , 2 3 ) (M,R)=\left(\frac{3}{2},\frac{2}{3}\right) ( M , R ) = ( 2 3 , 3 2 ) . Associate with each user k k k a distinct element a k a_k a k of the field, which requires q ≥ K q \ge K q ≥ K , and the normal vector h k : = ( 1 , a k , a k 2 ) \mathbf{h}_k := (1,a_k,a_k^2) h k := ( 1 , a k , a k 2 ) ; any three of these vectors are linearly independent (Vandermonde). The plane H k : = { x ∈ F q 3 : h k ⋅ x = 0 } H_k := \{\mathbf{x} \in\mathbb{F}_q^3 : \mathbf{h}_k \cdot\mathbf{x}=0\} H k := { x ∈ F q 3 : h k ⋅ x = 0 } is spanned by u k , 1 : = ( − a k , 1 , 0 ) \mathbf{u}_{k,1}:=(-a_k,1,0) u k , 1 := ( − a k , 1 , 0 ) and u k , 2 : = ( 0 , − a k , 1 ) \mathbf{u}_{k,2}:=(0,-a_k,1) u k , 2 := ( 0 , − a k , 1 ) , and two planes H k H_k H k and H l H_l H l meet in the line spanned by
p { k , l } : = ( a k a l , − ( a k + a l ) , 1 ) = − a l u k , 1 + u k , 2 = − a k u l , 1 + u l , 2 , (20) \mathbf{p}_{\{k,l\}} := (a_k a_l,-(a_k+a_l),1)=-a_l\mathbf{u}_{k,1}+\mathbf{u}_{k,2}=-a_k\mathbf{u}_{l,1}+\mathbf{u}_{l,2}, \tag*{(20)} p { k , l } := ( a k a l , − ( a k + a l ) , 1 ) = − a l u k , 1 + u k , 2 = − a k u l , 1 + u l , 2 , (20)
as in § 4.3 .
Split each file into ( 4 2 ) = 6 \binom{4}{2}=6 ( 2 4 ) = 6 subfiles and write it as a quadratic form in three variables, symbol by symbol,
f A ( x ) : = A 00 x 0 2 + A 01 x 0 x 1 + A 02 x 0 x 2 + A 11 x 1 2 + A 12 x 1 x 2 + A 22 x 2 2 , x = ( x 0 , x 1 , x 2 ) , (21) f_A(\mathbf{x}) := A_{00}x_0^2+A_{01}x_0x_1+A_{02}x_0x_2+A_{11}x_1^2+A_{12}x_1x_2+A_{22}x_2^2,\qquad\mathbf{x}=(x_0,x_1,x_2), \tag*{(21)} f A ( x ) := A 00 x 0 2 + A 01 x 0 x 1 + A 02 x 0 x 2 + A 11 x 1 2 + A 12 x 1 x 2 + A 22 x 2 2 , x = ( x 0 , x 1 , x 2 ) , (21)
and similarly for B B B and C C C . User k k k caches the restriction of f A f_A f A to H k H_k H k , that is,
f ~ A ( λ , μ ; a k ) : = f A ( λ u k , 1 + μ u k , 2 ) = ( a k 2 A 00 − a k A 01 + A 11 ) λ 2 + ( a k 2 A 01 − a k [ A 02 + 2 A 11 ] + A 12 ) λ μ + ( a k 2 A 11 − a k A 12 + A 22 ) μ 2 , ( λ , μ ) ∈ F q 2 . (22) \begin{aligned}
\widetilde{f}_A(\lambda,\mu;a_k) := f_A(\lambda\mathbf{u}_{k,1}+\mu\mathbf{u}_{k,2})
&=(a_k^2A_{00}-a_kA_{01}+A_{11})\lambda^2 \\
&\quad+(a_k^2A_{01}-a_k[A_{02}+2A_{11}]+A_{12})\lambda\mu\\
&\quad+(a_k^2A_{11}-a_kA_{12}+A_{22})\mu^2,\qquad(\lambda,\mu)\in\mathbb{F}_q^2. \tag*{(22)}
\end{aligned} f A ( λ , μ ; a k ) := f A ( λ u k , 1 + μ u k , 2 ) = ( a k 2 A 00 − a k A 01 + A 11 ) λ 2 + ( a k 2 A 01 − a k [ A 02 + 2 A 11 ] + A 12 ) λ μ + ( a k 2 A 11 − a k A 12 + A 22 ) μ 2 , ( λ , μ ) ∈ F q 2 . (22)
a binary quadratic form, i.e., a homogeneous polynomial of degree two in two variables: one variable fewer than f A f_A f A , and the same degree. Each coefficient in (22) is a linear combination of the subfiles of A A A . Unlike the linear forms of § 4.3 , the restriction f ~ A ( λ , μ ; a k ) \widetilde{f}_A(\lambda,\mu;a_k) f A ( λ , μ ; a k ) is not determined by its values at the basis vectors u k , 1 \mathbf{u}_{k,1} u k , 1 and u k , 2 \mathbf{u}_{k,2} u k , 2 ; so, user k k k stores its three coefficients in (22), and similarly for B B B and C C C ; with three subfiles per file the cache size is M = 3 ⋅ 3 6 = 3 2 M=3\cdot\frac{3}{6}=\frac{3}{2} M = 3 ⋅ 6 3 = 2 3 .
Once the set I = { i 1 , i 2 , i 3 , i 4 } \mathcal{I}=\{i_1,i_2,i_3,i_4\} I = { i 1 , i 2 , i 3 , i 4 } of four active users is known, the six subfiles of the new library are
A { k , l } ′ : = f A ( p { k , l } ) = f A ( a k a l , − ( a k + a l ) , 1 ) (23) A'_{\{k,l\}}:=f_A(\mathbf{p}_{\{k,l\}})=f_A(a_k a_l,-(a_k+a_l),1) \tag*{(23)} A { k , l } ′ := f A ( p { k , l } ) = f A ( a k a l , − ( a k + a l ) , 1 ) (23)
= f ~ A ( − a l , 1 ; a k ) (24) =\widetilde{f}_A(-a_l,1;a_k) \tag*{(24)} = f A ( − a l , 1 ; a k ) (24)
= f ~ A ( − a k , 1 ; a l ) , { k , l } ∈ Ω I 2 . (25) =\widetilde{f}_A(-a_k,1;a_l),\qquad\{k,l\}\in\Omega_{\mathcal{I}}^2. \tag*{(25)} = f A ( − a k , 1 ; a l ) , { k , l } ∈ Ω I 2 . (25)
and similarly for B ′ B' B ′ and C ′ C' C ′ . Since the planes H k H_k H k are “in general position,” the map A ↦ A ′ A\mapsto A' A ↦ A ′ is invertible by Lemma 2 below. Hence user k ∈ I k\in\mathcal{I} k ∈ I obtains the three subfiles A { k , l } ′ A'_{\{k,l\}} A { k , l } ′ , l ∈ I ∖ { k } l\in\mathcal{I}\setminus\{k\} l ∈ I ∖ { k } , by evaluating its cached form f ~ A ( ⋅ , ⋅ ; a k ) \widetilde{f}_A(\cdot,\cdot;a_k) f A ( ⋅ , ⋅ ; a k ) at ( − a l , 1 ) (-a_l,1) ( − a l , 1 ) , and similarly for B ′ B' B ′ and C ′ C' C ′ ; by the equality f ~ A ( − a l , 1 ; a k ) = f ~ A ( − a k , 1 ; a l ) \widetilde{f}_A(-a_l,1;a_k)=\widetilde{f}_A(-a_k,1;a_l) f A ( − a l , 1 ; a k ) = f A ( − a k , 1 ; a l ) , users k k k and l l l obtain the same subfile A { k , l } ′ A'_{\{k,l\}} A { k , l } ′ , each from its own cache. Hence the active users hold the MAN placement with t = 2 t=2 t = 2 for the new library, and the YMA delivery for four users and three files sends ( 4 3 ) − ( 1 3 ) = 4 \binom{4}{3}-\binom{1}{3}=4 ( 3 4 ) − ( 3 1 ) = 4 messages of size 1 6 \frac{1}{6} 6 1 , i.e., R = 2 3 R=\frac{2}{3} R = 3 2 . For example, for users ( i 1 , i 2 , i 3 , i 4 ) = ( 1 , 2 , 3 , 4 ) (i_1,i_2,i_3,i_4)=(1,2,3,4) ( i 1 , i 2 , i 3 , i 4 ) = ( 1 , 2 , 3 , 4 ) with demand ( A , B , C , A ) (A,B,C,A) ( A , B , C , A ) , the server sends
X 123 = A 23 ′ + B 13 ′ + C 12 ′ , (26) X_{123}=A'_{23}+B'_{13}+C'_{12}, \tag*{(26)} X 123 = A 23 ′ + B 13 ′ + C 12 ′ , (26)
X 124 = A 24 ′ + B 14 ′ + A 12 ′ , (27) X_{124}=A'_{24}+B'_{14}+A'_{12}, \tag*{(27)} X 124 = A 24 ′ + B 14 ′ + A 12 ′ , (27)
X 134 = A 34 ′ + C 14 ′ + A 13 ′ , (28) X_{134}=A'_{34}+C'_{14}+A'_{13}, \tag*{(28)} X 134 = A 34 ′ + C 14 ′ + A 13 ′ , (28)
X 234 = B 34 ′ + C 24 ′ + A 23 ′ . (29) X_{234}=B'_{34}+C'_{24}+A'_{23}. \tag*{(29)} X 234 = B 34 ′ + C 24 ′ + A 23 ′ . (29)
Comparison with other schemes
For A = 4 A=4 A = 4 active users, N = 3 N=3 N = 3 files and memory size M = 3 2 M=\frac{3}{2} M = 2 3 , Table 1 compares the load of the Reed–Muller embedding with that of other hotplug schemes and with the cut-set bound, for K = 5 K=5 K = 5 .
Table 1. Loads at M = 3 2 M=\frac{3}{2} M = 2 3 for ( A , K , N ) = ( 4 , 5 , 3 ) (A,K,N)=(4,5,3) ( A , K , N ) = ( 4 , 5 , 3 ) .
The Reed–Muller embedding attains R = 2 3 R=\frac{2}{3} R = 3 2 for every K ≥ 4 K\geq4 K ≥ 4 . In contrast, the two other schemes in Table 1 degrade as K K K grows: the optimal load under uncoded placement grows with K K K toward the decentralized load 7 8 \frac{7}{8} 8 7 ; and the MDS layer of [10 Scheme new1] attains the load 2 3 \frac{2}{3} 3 2 only at memory size N ( K − 1 1 ) / ( K 2 ) = K − 1 2 N\binom{K-1}{1}/\binom{K}{2}=\frac{K-1}{2} N ( 1 K − 1 ) / ( 2 K ) = 2 K − 1 . Finally, the scheme HT3 [11 ] attains ( 9 4 , 1 4 ) (\frac{9}{4},\frac{1}{4}) ( 4 9 , 4 1 ) , at a larger memory size, and the Reed–Solomon embedding of [12 ] applies only for M ≤ 3 4 M\leq\frac{3}{4} M ≤ 4 3 .
Proof of Theorem 4
Background on hyperplanes and their intersection points
Definition 3 (Hyperplanes in general position). For s ≥ 1 s\geq1 s ≥ 1 and a nonzero h ∈ F q s + 1 \mathbf{h}\in\mathbb{F}_q^{s+1} h ∈ F q s + 1 , let H : = { x ∈ F q s + 1 : h ⋅ x = 0 } H:=\{\mathbf{x}\in\mathbb{F}_q^{s+1}:\mathbf{h}\cdot\mathbf{x}=0\} H := { x ∈ F q s + 1 : h ⋅ x = 0 } , an s s s -dimensional subspace (a hyperplane of the projective space of dimension s s s ) with normal vector h \mathbf{h} h . A family of hyperplanes { H k : k ∈ S } \{H_k:k\in\mathcal{S}\} { H k : k ∈ S } is said to be in general position if any min ( s + 1 , ∣ S ∣ ) \min(s+1,|\mathcal{S}|) min ( s + 1 , ∣ S ∣ ) of the normal vectors are linearly independent.
Example of explicit construction: Let a 1 , … , a K − 1 ∈ F q a_1,\ldots,a_{K-1}\in\mathbb{F}_q a 1 , … , a K − 1 ∈ F q be distinct, which requires q ≥ K − 1 q\ge K-1 q ≥ K − 1 , and, for s ≥ 1 s\ge1 s ≥ 1 ,
h k : = ( 1 , a k , … , a k s ) , k ∈ [ K − 1 ] , h K : = ( 0 , … , 0 , 1 ) . (30) \mathbf{h}_k := (1,a_k,\ldots,a_k^s),\ k\in[K-1],\qquad\mathbf{h}_K := (0,\ldots,0,1). \tag*{(30)} h k := ( 1 , a k , … , a k s ) , k ∈ [ K − 1 ] , h K := ( 0 , … , 0 , 1 ) . (30)
For every s ≥ 1 s\ge1 s ≥ 1 , the corresponding hyperplanes are in general position, i.e., any min ( s + 1 , K ) \min(s+1,K) min ( s + 1 , K ) of these vectors are linearly independent: for m m m vectors with k < K k<K k < K , their first m m m coordinates form a nonsingular Vandermonde matrix, and if h K \mathbf{h}_K h K is included, the minor on the first m − 1 m-1 m − 1 coordinates and the last coordinate, expanded along h K \mathbf{h}_K h K , leaves a Vandermonde determinant of order m − 1 m-1 m − 1 . The field size does not depend on s s s .
The following Lemma is an elementary linear algebra fact.
Lemma 1 (General position). Let { H k } k ∈ S \{H_k\}_{k\in S} { H k } k ∈ S be in general position in F q s + 1 \mathbb{F}_q^{s+1} F q s + 1 , with ∣ S ∣ ≥ s |S|\ge s ∣ S ∣ ≥ s .
(a) For T ∈ Ω S s T\in\Omega_S^s T ∈ Ω S s , ⋂ k ∈ T H k \bigcap_{k\in T}H_k ⋂ k ∈ T H k is one-dimensional, spanned by a vector p T \mathbf{p}_T p T ; moreover, h ℓ ⋅ p T ≠ 0 \mathbf{h}_\ell\cdot\mathbf{p}_T\ne0 h ℓ ⋅ p T = 0 for ℓ ∈ S ∖ T \ell\in S\setminus T ℓ ∈ S ∖ T , and the points p T \mathbf{p}_T p T are distinct.
(b) If s ≥ 2 s\ge2 s ≥ 2 and j ∈ S j\in S j ∈ S , then { H k ∩ H j : k ∈ S ∖ { j } } \{H_k\cap H_j:k\in S\setminus\{j\}\} { H k ∩ H j : k ∈ S ∖ { j }} are hyperplanes of H j H_j H j in general position, and for T ∈ Ω S ∖ { j } s − 1 T\in\Omega_{S\setminus\{j\}}^{s-1} T ∈ Ω S ∖ { j } s − 1 their intersection is spanned by p T ∪ { j } \mathbf{p}_{T\cup\{j\}} p T ∪ { j } .
Proof of Lemma 1. (a) The s s s vectors { h k : k ∈ T } \{\mathbf{h}_k:k\in T\} { h k : k ∈ T } are linearly independent, so their common orthogonal complement is one-dimensional. If h k ⋅ p T = 0 \mathbf{h}_k\cdot\mathbf{p}_T=0 h k ⋅ p T = 0 with k ∉ T k\notin T k ∈ / T , then the nonzero p T \mathbf{p}_T p T would be orthogonal to s + 1 s+1 s + 1 independent vectors. If p T \mathbf{p}_T p T and p T ′ \mathbf{p}_{T'} p T ′ were proportional with T ≠ T ′ T\ne T' T = T ′ , then p T ∈ H k \mathbf{p}_T\in H_k p T ∈ H k for some k ∈ T ′ ∖ T k\in T'\setminus T k ∈ T ′ ∖ T , a contradiction.
(b) Linear forms on H j H_j H j are restrictions of linear forms on F q s + 1 \mathbb{F}_q^{s+1} F q s + 1 , and two such forms have the same restriction if and only if their normal vectors differ by a multiple of h j \mathbf{h}_j h j . Hence the restrictions of h k ⋅ x \mathbf{h}_k\cdot\mathbf{x} h k ⋅ x , k ≠ j k\ne j k = j , are nonzero, and any min ( s , ∣ S ∣ − 1 ) \min(s,|S|-1) min ( s , ∣ S ∣ − 1 ) of them are independent if and only if the corresponding h k \mathbf{h}_k h k , together with h j \mathbf{h}_j h j , are independent, which holds. Finally, ⋂ k ∈ T ( H k ∩ H j ) = ⋂ k ∈ T ∪ { j } H k \bigcap_{k\in T}(H_k\cap H_j)=\bigcap_{k\in T\cup\{j\}}H_k ⋂ k ∈ T ( H k ∩ H j ) = ⋂ k ∈ T ∪ { j } H k .
For s ≥ 0 s\ge0 s ≥ 0 and δ ≥ 0 \delta\ge0 δ ≥ 0 , let P s + 1 , δ P_{s+1,\delta} P s + 1 , δ be the F q \mathbb{F}_q F q -vector space of homogeneous polynomials of degree δ \delta δ in s + 1 s+1 s + 1 variables (including the zero polynomial). Its dimension is the number of monomials of degree δ \delta δ in s + 1 s+1 s + 1 variables, that is,
dim P s + 1 , δ = ( δ + s s ) ; (31) \dim P_{s+1,\delta}=\binom{\delta+s}{s}; \tag*{(31)} dim P s + 1 , δ = ( s δ + s ) ; (31)
in particular, dim P t + 1 , A − t = ( A t ) \dim P_{t+1,A-t}=\binom{A}{t} dim P t + 1 , A − t = ( t A ) and dim P t , A − t = ( A − 1 t − 1 ) \dim P_{t,A-t}=\binom{A-1}{t-1} dim P t , A − t = ( t − 1 A − 1 ) .
Lemma 2 (Interpolation at intersection points). Let { H k : k ∈ S } \{H_k:k\in S\} { H k : k ∈ S } be in general position in F q s + 1 \mathbb{F}_q^{s+1} F q s + 1 , with n : = ∣ S ∣ ≥ s ≥ 1 n:=|S|\ge s\ge1 n := ∣ S ∣ ≥ s ≥ 1 . Then the evaluation map
P s + 1 , n − s → F q ( n s ) : f ↦ ( f ( p T ) : T ∈ Ω S s ) (32) P_{s+1,n-s}\to\mathbb{F}_q^{\binom{n}{s}}: f\mapsto\bigl(f(\mathbf{p}_T):T\in\Omega_S^s\bigr) \tag*{(32)} P s + 1 , n − s → F q ( s n ) : f ↦ ( f ( p T ) : T ∈ Ω S s ) (32) is a linear bijection.
Proof of Lemma 2. By (28), both spaces have dimension ( n s ) \binom{n}{s} ( s n ) , so it suffices to show that if f ( p T ) = 0 f(\mathbf{p}_T)=0 f ( p T ) = 0 for all T ∈ Ω S s T\in\Omega_S^s T ∈ Ω S s , then f f f is the zero polynomial. Indeed, a linear map between spaces of equal finite dimension is bijective if and only if it is injective. It is injective if and only if its kernel is { 0 } \{0\} { 0 } , and the kernel consists of the f f f with f ( p T ) = 0 f(\mathbf{p}_T)=0 f ( p T ) = 0 for all T T T . So it is enough to show that only the zero polynomial vanishes at all the points.
We proceed by induction on n n n , proving the claim for all s ∈ [ n ] s \in[n] s ∈ [ n ] at once. For n = 1 n = 1 n = 1 , necessarily s = 1 = n s = 1 = n s = 1 = n , which is covered by the first case below. Let n ≥ 2 n \ge2 n ≥ 2 , assume the claim for n − 1 n - 1 n − 1 hyperplanes and every s ∈ [ n − 1 ] s \in[n - 1] s ∈ [ n − 1 ] is true; let s ∈ [ n ] s \in[n] s ∈ [ n ] :
Case s = n s = n s = n : f f f is a constant, and it vanishes at the nonzero vector p S \mathbf{p}_{S} p S ; hence f = 0 f = 0 f = 0 .
Case s = 1 < n s = 1 < n s = 1 < n : f f f is a binary form of degree n − 1 n - 1 n − 1 with the n n n pairwise non-proportional zeros p { k } \mathbf{p}_{\{k\}} p { k } , k ∈ S k \in S k ∈ S (Lemma 1(a)); since a nonzero binary form of degree n − 1 n - 1 n − 1 has at most n − 1 n - 1 n − 1 zeros in the projective line, f = 0 f = 0 f = 0 .
Case 2 ≤ s ≤ n − 1 2 \le s \le n - 1 2 ≤ s ≤ n − 1 : fix j ∈ S j \in S j ∈ S and change coordinates so that h j ⋅ x \mathbf{h}_{j} \cdot\mathbf{x} h j ⋅ x is the first coordinate; write f = ( h j ⋅ x ) g + f ~ f = (\mathbf{h}_{j} \cdot\mathbf{x})g + \widetilde{f} f = ( h j ⋅ x ) g + f , where f ~ \widetilde{f} f does not depend on the first coordinate, so that f ~ \widetilde{f} f is the restriction of f f f to H j H_{j} H j , a homogeneous polynomial of degree ( n − 1 ) − ( s − 1 ) (n - 1) - (s - 1) ( n − 1 ) − ( s − 1 ) in s s s variables. By Lemma 1(b), the n − 1 n - 1 n − 1 hyperplanes H k ∩ H j H_{k} \cap H_{j} H k ∩ H j , k ∈ S ∖ { j } k \in S \setminus\{j\} k ∈ S ∖ { j } , of H j H_{j} H j are in general position, and their intersection points are the points p T ∪ { j } \mathbf{p}_{T \cup\{j\}} p T ∪ { j } , T ∈ Ω S ∖ { j } s − 1 T \in\Omega_{S \setminus\{j\}}^{s-1} T ∈ Ω S ∖ { j } s − 1 , at which f ~ \widetilde{f} f vanishes. By the induction hypothesis, applied to these n − 1 n - 1 n − 1 hyperplanes with s − 1 ∈ [ n − 1 ] s - 1 \in[n - 1] s − 1 ∈ [ n − 1 ] , f ~ = 0 \widetilde{f} = 0 f = 0 , so that f = ( h j ⋅ x ) g f = (\mathbf{h}_{j} \cdot\mathbf{x})g f = ( h j ⋅ x ) g with g ∈ P s + 1 , n − s − 1 g \in\mathcal{P}_{s+1,n-s-1} g ∈ P s + 1 , n − s − 1 . For T ∈ Ω S ∖ { j } s − 1 T \in\Omega_{S \setminus\{j\}}^{s-1} T ∈ Ω S ∖ { j } s − 1 , h j ⋅ p T ≠ 0 \mathbf{h}_{j} \cdot\mathbf{p}_{T} \ne0 h j ⋅ p T = 0 by Lemma 1(a), hence g ( p T ) = 0 g(\mathbf{p}_{T}) = 0 g ( p T ) = 0 . By the induction hypothesis, applied to the n − 1 n - 1 n − 1 hyperplanes { H k : k ∈ S ∖ { j } } \{H_{k}: k \in S \setminus\{j\}\} { H k : k ∈ S ∖ { j }} , which are in general position, with s ∈ [ n − 1 ] s \in[n - 1] s ∈ [ n − 1 ] , g = 0 g = 0 g = 0 . Hence f = 0 f = 0 f = 0 .
The embedding and proof of Theorem 4
Proof of Theorem 4. Field. Since the classical scheme is correct for every realization of the library, we may run μ \mu μ instances of it in parallel and view μ \mu μ symbols of F q 0 \mathbb{F}_{q_{0}} F q 0 as one symbol of F q \mathbb{F}_{q} F q , q = q 0 μ ≥ K − 1 q = q_{0}^{\mu} \ge K - 1 q = q 0 μ ≥ K − 1 . The matrix of L \mathcal{L} L in (7) has entries in F q 0 \mathbb{F}_{q_{0}} F q 0 ; applied to vectors over F q \mathbb{F}_{q} F q , it is F q \mathbb{F}_{q} F q -linear and acts on each of the μ \mu μ instances as in the classical scheme.
Trivial case. For t = A t = A t = A , the only subset is W = [ A ] W = [A] W = [ A ] , so every user caches L [ f [ A ] ] \mathcal{L}[f_{[A]}] L [ f [ A ] ] , which does not depend on the user, and the classical scheme applies unchanged. Let t ∈ [ A − 1 ] t \in[A - 1] t ∈ [ A − 1 ] , and let { H k : k ∈ [ K ] } \{H_{k}: k \in[K]\} { H k : k ∈ [ K ]} be hyperplanes of F q t + 1 \mathbb{F}_{q}^{t+1} F q t + 1 in general position, e.g., with the normal vectors (27) with s = t s = t s = t .
Files as polynomials. Index the ( A t ) \binom{A}{t} ( t A ) subfiles of each file by the monomials of degree A − t A - t A − t in t + 1 t + 1 t + 1 variables, and let f n ∈ P t + 1 , A − t f_{n} \in\mathcal{P}_{t+1,A-t} f n ∈ P t + 1 , A − t be the homogeneous polynomial whose coefficients are the subfiles of F n F_{n} F n , so that f n ( x ) ∈ F q 1 × B / ( A t ) f_{n}(\mathbf{x}) \in\mathbb{F}_{q}^{1 \times B/\binom{A}{t}} f n ( x ) ∈ F q 1 × B / ( t A ) for every x ∈ F q t + 1 \mathbf{x} \in\mathbb{F}_{q}^{t+1} x ∈ F q t + 1 . Let ℓ \ell ℓ be the homogeneous polynomial of degree A − t A - t A − t whose coefficient of each monomial is L \mathcal{L} L applied to the concatenation of the coefficients of that monomial in f 1 , … , f N f_{1}, \ldots, f_{N} f 1 , … , f N . Since evaluation combines coefficients linearly with scalar weights, and L \mathcal{L} L is linear,
ℓ ( x ) = L [ f 1 ( x ) , … , f N ( x ) ] ∈ F q 1 × M B / ( A − 1 t − 1 ) , x ∈ F q t + 1 . (33) \ell(\mathbf{x}) = \mathcal{L}\left[f_{1}(\mathbf{x}), \ldots, f_{N}(\mathbf{x})\right] \in\mathbb{F}_{q}^{1 \times MB/\binom{A-1}{t-1}}, \qquad\mathbf{x} \in\mathbb{F}_{q}^{t+1}. \tag*{(33)} ℓ ( x ) = L [ f 1 ( x ) , … , f N ( x ) ] ∈ F q 1 × M B / ( t − 1 A − 1 ) , x ∈ F q t + 1 . (33)
Placement. Let { u k , 1 , … , u k , t } \{\mathbf{u}_{k,1}, \ldots, \mathbf{u}_{k,t}\} { u k , 1 , … , u k , t } be a basis of H k H_{k} H k ; for the normal vectors (27), one may take u k , j \mathbf{u}_{k,j} u k , j as the coefficient vector of z j − 1 ( z − a k ) z^{j-1}(z-a_{k}) z j − 1 ( z − a k ) , j ∈ [ t ] j \in[t] j ∈ [ t ] , for k ∈ [ K − 1 ] k \in[K - 1] k ∈ [ K − 1 ] , and, for k = K k = K k = K , the vector with a one in coordinate j − 1 j - 1 j − 1 and zeros elsewhere (coordinates indexed by [ 0 : t ] [0:t] [ 0 : t ] ), since H K = { x : x t = 0 } H_{K} = \{\mathbf{x}: x_{t} = 0\} H K = { x : x t = 0 } . User k ∈ [ K ] k \in[K] k ∈ [ K ] caches the coefficients of
ℓ ~ k ( λ ) : = ℓ ( ∑ j ∈ [ t ] λ j u k , j ) , λ ∈ F q t , (34) \widetilde{\ell}_{k}(\boldsymbol{\lambda}) := \ell\left(\sum_{j \in[t]} \lambda_{j}\mathbf{u}_{k,j}\right), \qquad\boldsymbol{\lambda} \in\mathbb{F}_{q}^{t}, \tag*{(34)} ℓ k ( λ ) := ℓ j ∈ [ t ] ∑ λ j u k , j , λ ∈ F q t , (34)
a row vector of homogeneous polynomials of degree A − t A - t A − t in t t t variables; by (28), these are ( A − 1 t − 1 ) \binom{A-1}{t-1} ( t − 1 A − 1 ) coefficients of M B / ( A − 1 t − 1 ) MB/\binom{A-1}{t-1} M B / ( t − 1 A − 1 ) symbols each, i.e., M B MB M B symbols, as in Definition 1.2
New library. Given the set of active users I \mathcal{I} I , define
F n , W ′ : = f n ( p W ) , n ∈ [ N ] , W ∈ Ω I t , (35) F'_{n,\mathcal{W}} := f_n(\mathbf{p}_{\mathcal{W}}), \qquad n \in[N],\ \mathcal{W} \in\Omega_{\mathcal{I}}^t, \tag*{(35)} F n , W ′ := f n ( p W ) , n ∈ [ N ] , W ∈ Ω I t , (35)
and F n ′ : = ( F n , W ′ : W ∈ Ω I t ) F'_n := (F'_{n,\mathcal{W}} : \mathcal{W} \in\Omega_{\mathcal{I}}^t) F n ′ := ( F n , W ′ : W ∈ Ω I t ) and f W ′ : = [ F 1 , W ′ , … , F N , W ′ ] f'_{\mathcal{W}} := [F'_{1,\mathcal{W}}, \ldots, F'_{N,\mathcal{W}}] f W ′ := [ F 1 , W ′ , … , F N , W ′ ] . By Lemma 2, applied to the A A A hyperplanes { H k : k ∈ I } \{H_k : k \in\mathcal{I}\} { H k : k ∈ I } with s = t s=t s = t , the map F n ↦ F n ′ F_n \mapsto F'_n F n ↦ F n ′ is a bijection, the same for every file.
Caches of the active users. For k ∈ W k \in\mathcal{W} k ∈ W , p W ∈ H k \mathbf{p}_{\mathcal{W}} \in H_k p W ∈ H k ; hence user k ∈ I k \in\mathcal{I} k ∈ I obtains L [ f W ′ ] = ℓ ( p W ) \mathcal{L}[f'_{\mathcal{W}}] = \ell(\mathbf{p}_{\mathcal{W}}) L [ f W ′ ] = ℓ ( p W ) by evaluating its cached restriction, for every W ∈ Ω I t \mathcal{W} \in\Omega_{\mathcal{I}}^t W ∈ Ω I t with W ∋ k \mathcal{W} \ni k W ∋ k . Thus the active users hold the placement of Definition 1 for the library ( F n ′ : n ∈ [ N ] ) (F'_n : n \in[N]) ( F n ′ : n ∈ [ N ]) , with the users in I \mathcal{I} I in place of the classical users [ A ] [A] [ A ] , through any bijection between I \mathcal{I} I and [ A ] [A] [ A ] .
Delivery and decoding. The server sends the classical transmission for the library ( F n : n ∈ [ N ] ) (F_n : n \in[N]) ( F n : n ∈ [ N ]) and the demands d [ I ] \mathbf{d}[\mathcal{I}] d [ I ] , of load R R R . Since the classical scheme is correct for every realization of the library, every active user k k k decodes F d k ′ F'_{d_k} F d k ′ as the corresponding classical user, and recovers F d k F_{d_k} F d k by inverting the bijection F n ↦ F n ′ F_n \mapsto F'_n F n ↦ F n ′ .
Equivalent View: Symmetric Polynomials
This section gives an equivalent description of the code of § 6 that does not use hyperplanes, together with the explicit formula for the intersection points used earlier; it is not needed for the proofs. We use the normal vectors h k = ( 1 , a k , … , a k t ) \mathbf{h}_k=(1,a_k,\ldots,a_k^t) h k = ( 1 , a k , … , a k t ) in (30) with distinct a k a_k a k for all k ∈ [ K ] k \in[K] k ∈ [ K ] , i.e., without the point at infinity, which requires q ≥ K q \ge K q ≥ K .
A vector x = ( x 0 , … , x t ) \mathbf{x}=(x_0,\ldots,x_t) x = ( x 0 , … , x t ) lies in H k H_k H k if and only if the polynomial ∑ i = 0 t x i z i \sum_{i=0}^t x_i z^i ∑ i = 0 t x i z i vanishes at z = a k z=a_k z = a k . Hence, for W ∈ Ω [ K ] t \mathcal{W} \in\Omega_{[K]}^t W ∈ Ω [ K ] t , the intersection point p W \mathbf{p}_{\mathcal{W}} p W is the coefficient vector of ∏ k ∈ W ( z − a k ) \prod_{k\in\mathcal{W}}(z-a_k) ∏ k ∈ W ( z − a k ) , i.e.,
p W = ( ( ( − 1 ) t − i e t − i ( a W ) ) i = 0 t ) , (36) \mathbf{p}_{\mathcal{W}}=\left(\left((-1)^{t-i}e_{t-i}(\mathbf{a}_{\mathcal{W}})\right)_{i=0}^t\right), \tag*{(36)} p W = ( ( ( − 1 ) t − i e t − i ( a W ) ) i = 0 t ) , (36)
where e r e_r e r is the elementary symmetric polynomial (a symmetric polynomial is a polynomial in several variables that does not change when the variables are permuted) of degree r r r in t t t variables (e 0 = 1 e_0=1 e 0 = 1 ) and a W : = ( a k : k ∈ W ) \mathbf{a}_{\mathcal{W}} := (a_k : k \in\mathcal{W}) a W := ( a k : k ∈ W ) , in any order. Similarly, u k , j \mathbf{u}_{k,j} u k , j , the coefficient vector of z j − 1 ( z − a k ) z^{j-1}(z-a_k) z j − 1 ( z − a k ) , j ∈ [ t ] j \in[t] j ∈ [ t ] , is a basis of H k H_k H k , and for W ∋ k \mathcal{W} \ni k W ∋ k , p W = ∑ j ∈ [ t ] λ j u k , j \mathbf{p}_{\mathcal{W}}=\sum_{j\in[t]}\lambda_j\mathbf{u}_{k,j} p W = ∑ j ∈ [ t ] λ j u k , j , where λ \boldsymbol{\lambda} λ is the coefficient vector of ∏ l ∈ W ∖ { k } ( z − a l ) \prod_{l\in\mathcal{W}\setminus\{k\}}(z-a_l) ∏ l ∈ W ∖ { k } ( z − a l ) .
Let S t , δ S_{t,\delta} S t , δ be the space of symmetric polynomials in t t t variables with degree at most δ \delta δ in each variable. For f ∈ P t + 1 , A − t f \in P_{t+1,A-t} f ∈ P t + 1 , A − t , let
σ ( f ) ( y 1 , … , y t ) : = f ( ( ( − 1 ) t − i e t − i ( y 1 , … , y t ) ) i = 0 t ) , (37) \sigma(f)(y_1,\ldots,y_t):=f\left(\left((-1)^{t-i}e_{t-i}(y_1,\ldots,y_t)\right)_{i=0}^t\right), \tag*{(37)} σ ( f ) ( y 1 , … , y t ) := f ( ( ( − 1 ) t − i e t − i ( y 1 , … , y t ) ) i = 0 t ) , (37)
so that, by (36) , f ( p W ) = σ ( f ) ( a W ) f(\mathbf{p}_{\mathcal{W}})=\sigma(f)(\mathbf{a}_{\mathcal{W}}) f ( p W ) = σ ( f ) ( a W ) . The map σ \sigma σ is an isomorphism from P t + 1 , A − t P_{t+1,A-t} P t + 1 , A − t onto S t , A − t S_{t,A-t} S t , A − t : each e r e_r e r has degree at most one in each variable, so σ ( f ) \sigma(f) σ ( f ) has degree at most A − t A-t A − t in each variable; σ \sigma σ is injective, because e 1 , … , e t e_1,\ldots,e_t e 1 , … , e t are algebraically independent and f f f is homogeneous, hence determined by its values with x t = e 0 = 1 x_t=e_0=1 x t = e 0 = 1 ; and both spaces have dimension ( A t ) \binom{A}{t} ( t A ) , since a basis of S t , δ S_{t,\delta} S t , δ is given by the monomial symmetric polynomials indexed by δ ≥ c 1 ≥ ⋯ ≥ c t ≥ 0 \delta\ge c_1 \ge\cdots\ge c_t \ge0 δ ≥ c 1 ≥ ⋯ ≥ c t ≥ 0 , and there are ( δ + t t ) \binom{\delta+t}{t} ( t δ + t ) of them.
Therefore, applying σ \sigma σ to each component of ℓ \ell ℓ in (33) , the code can be described as follows: the files are vectors of symmetric polynomials in t t t variables, with degree at most A − t A-t A − t in each variable; the subfile indexed by W \mathcal{W} W is the evaluation at the set a W \mathbf{a}_{\mathcal{W}} a W of t t t distinct field elements; and the cache of user k k k is the polynomial obtained by fixing one variable to a k a_k a k , which lies in S t − 1 , A − t S_{t-1,A-t} S t − 1 , A − t . In this view, Lemma 2 states that a polynomial in S t , A − t S_{t,A-t} S t , A − t is determined by its values at the t t t -subsets of any A A A distinct field elements. For t = 1 t=1 t = 1 , S 1 , A − 1 S_{1,A-1} S 1 , A − 1 is the space of univariate polynomials of degree at most A − 1 A-1 A − 1 , and the construction is the Reed–Solomon code of Section 4.1.
For the example of Section 4.3, t = 2 t=2 t = 2 and f A ( x ) = A 0 x 0 + A 1 x 1 + A 2 x 2 f_A(\mathbf{x})=A_0x_0+A_1x_1+A_2x_2 f A ( x ) = A 0 x 0 + A 1 x 1 + A 2 x 2 ; then
σ ( f A ) ( y 1 , y 2 ) = A 0 y 1 y 2 − A 1 ( y 1 + y 2 ) + A 2 , σ ( f A ) ( a k , y ) = ( A 2 − a k A 1 ) + ( a k A 0 − A 1 ) y , (38) \sigma(f_A)(y_1,y_2)=A_0y_1y_2-A_1(y_1+y_2)+A_2,\qquad\sigma(f_A)(a_k,y)=(A_2-a_kA_1)+(a_kA_0-A_1)y, \tag*{(38)} σ ( f A ) ( y 1 , y 2 ) = A 0 y 1 y 2 − A 1 ( y 1 + y 2 ) + A 2 , σ ( f A ) ( a k , y ) = ( A 2 − a k A 1 ) + ( a k A 0 − A 1 ) y , (38)
so that the cache of user k k k , ( A 1 − a k A 0 , A 2 − a k A 1 ) (A_1-a_kA_0,A_2-a_kA_1) ( A 1 − a k A 0 , A 2 − a k A 1 ) , is, up to sign and order, the pair of coefficients of the linear polynomial σ ( f A ) ( a k , y ) \sigma(f_A)(a_k,y) σ ( f A ) ( a k , y ) . For the example of Section 5, t = 2 t=2 t = 2 , A = 4 A=4 A = 4 and f A f_A f A is a quadratic form; then
σ ( f A ) ( y 1 , y 2 ) = A 00 y 1 2 y 2 2 − A 01 y 1 y 2 ( y 1 + y 2 ) + A 02 y 1 y 2 + A 11 ( y 1 + y 2 ) 2 − A 12 ( y 1 + y 2 ) + A 22 , (39) \sigma(f_A)(y_1,y_2)=A_{00}y_1^2y_2^2-A_{01}y_1y_2(y_1+y_2)+A_{02}y_1y_2+A_{11}(y_1+y_2)^2-A_{12}(y_1+y_2)+A_{22}, \tag*{(39)} σ ( f A ) ( y 1 , y 2 ) = A 00 y 1 2 y 2 2 − A 01 y 1 y 2 ( y 1 + y 2 ) + A 02 y 1 y 2 + A 11 ( y 1 + y 2 ) 2 − A 12 ( y 1 + y 2 ) + A 22 , (39)
σ ( f A ) ( a k , y ) = ( a k 2 A 00 − a k A 01 + A 11 ) y 2 − ( a k 2 A 01 − a k [ A 02 + 2 A 11 ] + A 12 ) y + ( a k 2 A 11 − a k A 12 + A 22 ) , (40) \sigma(f_A)(a_k,y)=(a_k^2A_{00}-a_kA_{01}+A_{11})y^2-(a_k^2A_{01}-a_k[A_{02}+2A_{11}]+A_{12})y+(a_k^2A_{11}-a_kA_{12}+A_{22}), \tag*{(40)} σ ( f A ) ( a k , y ) = ( a k 2 A 00 − a k A 01 + A 11 ) y 2 − ( a k 2 A 01 − a k [ A 02 + 2 A 11 ] + A 12 ) y + ( a k 2 A 11 − a k A 12 + A 22 ) , (40)
i.e., σ ( f A ) ( a k , y ) = f ~ A ( − y , 1 ; a k ) \sigma(f_A)(a_k,y)=\tilde{f}_A(-y,1;a_k) σ ( f A ) ( a k , y ) = f ~ A ( − y , 1 ; a k ) : the cache of user k k k consists of the three coefficients of a univariate quadratic polynomial, and the subfile shared by users k k k and l l l is A { k , l } ′ = σ ( f A ) ( a k , a l ) = σ ( f A ) ( a l , a k ) A'_{\{k,l\}}=\sigma(f_A)(a_k,a_l)=\sigma(f_A)(a_l,a_k) A { k , l } ′ = σ ( f A ) ( a k , a l ) = σ ( f A ) ( a l , a k ) .
The symmetric polynomial view makes the Reed–Solomon case transparent; the projective view allows any hyperplanes in general position, includes the point at infinity (hence q ≥ K − 1 q\ge K-1 q ≥ K − 1 rather than q ≥ K q\ge K q ≥ K ), and identifies the code as a projective Reed–Muller code [16 , 17 ] restricted to the intersection points of the users’ hyperplanes.
Exact versus Generic Embedding, and Proof of Theorem 5
Why an exact embedding is limited to Definition 1
Let t ≥ 2 t\ge2 t ≥ 2 (for t = 1 t=1 t = 1 , see [12 Theorem 2] ). In the construction of Section 6, write the restriction of the files to H k H_k H k as the row vector r k ∈ F q 1 × N t B / A \mathbf{r}_k\in\mathbb{F}_q^{1\times N tB/A} r k ∈ F q 1 × N tB / A of its coefficients. For an active set I ∋ k \mathcal{I}\ni k I ∋ k , let s k ′ \mathbf{s}'_k s k ′ be the MAN cache of user k k k for the new library, i.e., the concatenation of the subfiles F n , W ′ F'_{n,\mathcal{W}} F n , W ′ , n ∈ [ N ] n\in[N] n ∈ [ N ] , W ∈ Ω t T \mathcal{W}\in\Omega_t^T W ∈ Ω t T , W ∋ k \mathcal{W}\ni k W ∋ k . Then
s k ′ = β I , k [ r k ] , (41) \mathbf{s}'_k=\beta_{\mathcal{I},k}[\mathbf{r}_k], \tag*{(41)} s k ′ = β I , k [ r k ] , (41)
where β I , k \beta_{\mathcal{I},k} β I , k evaluates the restriction at the points p W ∈ H k \mathbf{p}_{\mathcal{W}}\in H_k p W ∈ H k , W ∈ Ω t T \mathcal{W}\in\Omega_t^T W ∈ Ω t T , W ∋ k \mathcal{W}\ni k W ∋ k . By Lemma 1(b) and Lemma 2, applied on H k H_k H k to the A − 1 A-1 A − 1 hyperplanes H l ∩ H k H_l\cap H_k H l ∩ H k , l ∈ I ∖ { k } l\in\mathcal{I}\setminus\{k\} l ∈ I ∖ { k } , with s = t − 1 s=t-1 s = t − 1 , the map β I , k \beta_{\mathcal{I},k} β I , k is a linear bijection; it acts in the same way on every file and every symbol position, and it depends on the other active users. Note: for t = 1 t=1 t = 1 , H k H_k H k is spanned by p { k } \mathbf{p}_{\{k\}} p { k } , the restriction is the value at p { k } \mathbf{p}_{\{k\}} p { k } , and β I , k \beta_{\mathcal{I},k} β I , k is the identity.
Consider a classical scheme with a linear MAN-compression placement as in (9). Within this construction, i.e., when the cache of user k k k is a linear function of r k \mathbf{r}_k r k , an exact embedding with the same memory requires each user k k k to store, before I \mathcal{I} I is known, data from which it can compute the cache L a [ s k ′ ] = L a ∘ β I , k [ r k ] \mathcal{L}_a[\mathbf{s}'_k]=\mathcal{L}_a\circ\beta_{\mathcal{I},k}[\mathbf{r}_k] L a [ s k ′ ] = L a ∘ β I , k [ r k ] of the classical user a a a whose role it plays. Since both have size M B MB M B , if L a \mathcal{L}_a L a has full rank, the linear functions of r k \mathbf{r}_k r k given by L a ∘ β I , k \mathcal{L}_a\circ\beta_{\mathcal{I},k} L a ∘ β I , k must span the same space for every active set I ∋ k \mathcal{I}\ni k I ∋ k and every role a a a . Hence: (i) the span of the linear functions given by L a \mathcal{L}_a L a must be invariant under the re-interpolation maps β I , k ∘ β I ′ , k − 1 \beta_{\mathcal{I},k}\circ\beta_{\mathcal{I}',k}^{-1} β I , k ∘ β I ′ , k − 1 ; and (ii) it must not depend on a a a . The placements of Definition 1 satisfy both: L a \mathcal{L}_a L a applies the same operator L \mathcal{L} L to each subset, while the re-interpolation maps combine different subsets with scalar coefficients, in the same way for every file and every symbol position, so they commute with L \mathcal{L} L . User and file symmetry, which can be assumed without loss of generality, gives invariance only under permutations of the labels, not under re-interpolation. A compression that mixes subsets, as in [7 ] , need not satisfy (i), since the re-interpolation maps change how the subsets are combined. This is why Theorem 5 does not embed the classical scheme itself, but, for each active set, a classical scheme of the same family with different coefficients.
Proof of Theorem 5
Since s a s_a s a has N t B / A NtB/A N tB / A symbols, the placement in Definition 2 is a compression of the MAN placement only when M ≤ N t / A M \le Nt/A M ≤ N t / A ; for M ≥ N t / A M \ge Nt/A M ≥ N t / A the user may as well store s a s_a s a , which is the MAN placement. The proof uses the following lemma, as in [7 ] .
Lemma 3 (Schwartz–Zippel [13 , 14 ] ). Let P ∈ F [ x 1 , … , x n ] P \in\mathbb{F}[x_1,\ldots,x_n] P ∈ F [ x 1 , … , x n ] be a nonzero polynomial of total degree d d d over a field F \mathbb{F} F , and let S ⊆ F S \subseteq\mathbb{F} S ⊆ F be finite. If x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n are drawn independently and uniformly from S S S , then
Pr [ P ( x 1 , … , x n ) = 0 ] ≤ d ∣ S ∣ . (42) \Pr\left[P(x_1,\ldots,x_n)=0\right] \le\frac{d}{\lvert S\rvert}. \tag*{(42)} Pr [ P ( x 1 , … , x n ) = 0 ] ≤ ∣ S ∣ d . (42) In particular, if ∣ S ∣ > d \lvert S\rvert> d ∣ S ∣ > d , there exists ( x 1 , … , x n ) ∈ S n (x_1,\ldots,x_n) \in S^n ( x 1 , … , x n ) ∈ S n with $P(x_1,\ldots,x_n) \ne 0.
Proof of Theorem 5. Files as polynomials. As in the proof of Theorem 4, let { H k : k ∈ [ K ] } \{H_k:k\in[K]\} { H k : k ∈ [ K ]} be hyperplanes of F q t + 1 \mathbb{F}_q^{t+1} F q t + 1 in general position, which requires q ≥ K − 1 q \ge K-1 q ≥ K − 1 , write each file as a homogeneous polynomial of degree A − t A-t A − t in t + 1 t+1 t + 1 variables, and let r k ∈ F q 1 × N t B / A r_k \in\mathbb{F}_q^{1\times NtB/A} r k ∈ F q 1 × N tB / A be the coefficients of the restriction of the files to H k H_k H k .
Placement. Let user k k k cache Ψ k [ r k ] \Psi_k[r_k] Ψ k [ r k ] , where Ψ 1 , … , Ψ K : F q 1 × N t B / A → F q 1 × M B \Psi_1,\ldots,\Psi_K:\mathbb{F}_q^{1\times NtB/A}\to\mathbb{F}_q^{1\times MB} Ψ 1 , … , Ψ K : F q 1 × N tB / A → F q 1 × M B are linear operators chosen below.
Induced classical placement. Fix I \mathcal{I} I and a bijection π I : I → [ A ] \pi_{\mathcal{I}}:\mathcal{I}\to[A] π I : I → [ A ] , so that active user k k k plays the role of classical user π I ( k ) \pi_{\mathcal{I}}(k) π I ( k ) . With the new library F n , W ′ = f n ( p W ) F'_{n,\mathcal{W}}=f_n(\mathbf{p}_{\mathcal{W}}) F n , W ′ = f n ( p W ) , n ∈ [ N ] n\in[N] n ∈ [ N ] , W ∈ Ω I \mathcal{W}\in\Omega_{\mathcal{I}} W ∈ Ω I , of the proof of Theorem 4, and by (38), user k k k caches
Ψ k [ r k ] = L π I ( k ) ( I ) [ s k ′ ] , L π I ( k ) ( I ) : = Ψ k ∘ β I , k − 1 . (43) \Psi_k[r_k]=\mathcal{L}^{(\mathcal{I})}_{\pi_{\mathcal{I}}(k)}[s'_k],\qquad\mathcal{L}^{(\mathcal{I})}_{\pi_{\mathcal{I}}(k)}:=\Psi_k\circ\beta^{-1}_{\mathcal{I},k}. \tag*{(43)} Ψ k [ r k ] = L π I ( k ) ( I ) [ s k ′ ] , L π I ( k ) ( I ) := Ψ k ∘ β I , k − 1 . (43)
i.e., the active users hold the linear MAN-compression placement (9) with operators ( L a ( I ) : a ∈ [ A ] ) (\mathcal{L}^{(\mathcal{I})}_a:a\in[A]) ( L a ( I ) : a ∈ [ A ]) for the library ( F n ′ : n ∈ [ N ] ) (F'_n:n\in[N]) ( F n ′ : n ∈ [ N ]) .
Choice of the operators. For each I \mathcal{I} I , the map ( Ψ k ) k ∈ I ↦ ( L a ( I ) ) a ∈ [ A ] (\Psi_k)_{k\in\mathcal{I}}\mapsto(\mathcal{L}^{(\mathcal{I})}_a)_{a\in[A]} ( Ψ k ) k ∈ I ↦ ( L a ( I ) ) a ∈ [ A ] is an invertible linear change of variables, since distinct active users have distinct operators and each β I , k \beta_{\mathcal{I},k} β I , k is a bijection. Hence g I : = g ( L 1 ( I ) , … , L A ( I ) ) g_{\mathcal{I}}:=g(\mathcal{L}^{(\mathcal{I})}_1,\ldots,\mathcal{L}^{(\mathcal{I})}_A) g I := g ( L 1 ( I ) , … , L A ( I ) ) is a nonzero polynomial of degree deg ( g ) \deg(g) deg ( g ) in the entries of Ψ 1 , … , Ψ K \Psi_1,\ldots,\Psi_K Ψ 1 , … , Ψ K , and so is ∏ I g I \prod_{\mathcal{I}}g_{\mathcal{I}} ∏ I g I , of degree ( K A ) deg ( g ) \binom{K}{A}\deg(g) ( A K ) deg ( g ) . By Lemma 3 with S = F q S=\mathbb{F}_q S = F q , there exist Ψ 1 , … , Ψ K \Psi_1,\ldots,\Psi_K Ψ 1 , … , Ψ K at which ∏ I g I ≠ 0 \prod_{\mathcal{I}}g_{\mathcal{I}}\ne0 ∏ I g I = 0 whenever q > ( K A ) deg ( g ) q>\binom{K}{A}\deg(g) q > ( A K ) deg ( g ) .
Delivery and decoding. Given I \mathcal{I} I and d [ I ] d[\mathcal{I}] d [ I ] , the server sends the transmission D d ′ [ F 1 ′ , … , F N ′ ] \mathcal{D}_{d'}[F'_1,\ldots,F'_N] D d ′ [ F 1 ′ , … , F N ′ ] of R B RB R B symbols, where d ′ d' d ′ is the classical demand vector in which classical user π I ( k ) \pi_{\mathcal{I}}(k) π I ( k ) requests d k d_k d k . Since g ( L 1 ( I ) , … , L A ( I ) ) ≠ 0 g(\mathcal{L}^{(\mathcal{I})}_1,\ldots,\mathcal{L}^{(\mathcal{I})}_A)\ne0 g ( L 1 ( I ) , … , L A ( I ) ) = 0 , the operators are over the extension F q \mathbb{F}_q F q of F q 0 \mathbb{F}_{q_0} F q 0 , and the classical scheme is correct for every realization of the library, active user k k k decodes F d k ′ F'_{d_k} F d k ′ as classical user π I ( k ) \pi_{\mathcal{I}}(k) π I ( k ) , and recovers F d k F_{d_k} F d k by inverting the bijection F n ↦ F n ′ F_n\mapsto F'_n F n ↦ F n ′ of the proof of Theorem 4. □ \square □
Example: IE with A = 4 and N = 2
For ( A , N ) = ( 4 , 2 ) (A,N)=(4,2) ( A , N ) = ( 4 , 2 ) and t = 2 t=2 t = 2 , (3) gives ( M , R ) = ( 2 3 , 1 ) (M,R)=\left(\frac{2}{3},1\right) ( M , R ) = ( 3 2 , 1 ) , which by Corollary 3 is achievable in the hotplug model, and which was left open in [12 ] .
In the classical scheme, each file is split into B = ( 4 2 ) = 6 B=\binom{4}{2}=6 B = ( 2 4 ) = 6 symbols indexed by W ∈ Ω [ 4 ] 2 \mathcal{W}\in\Omega_{[4]}^{2} W ∈ Ω [ 4 ] 2 , s a ∈ F q 1 × 6 s_a\in\mathbb{F}_q^{1\times6} s a ∈ F q 1 × 6 collects the three symbols of each file indexed by the subsets containing a a a , and user a a a caches L a [ s a ] ∈ F q 1 × 4 \mathcal{L}_a[s_a]\in\mathbb{F}_q^{1\times4} L a [ s a ] ∈ F q 1 × 4 .
In the hotplug model, the files are quadratic forms in three variables, as in § 5 . User k k k computes the restriction r k ∈ F q 1 × 6 r_k\in\mathbb{F}_q^{1\times6} r k ∈ F q 1 × 6 of both files to H k H_k H k , i.e., three coefficients per file, and caches Ψ k [ r k ] ∈ F q 1 × 4 \Psi_k[r_k]\in\mathbb{F}_q^{1\times4} Ψ k [ r k ] ∈ F q 1 × 4 . Theorem 4 would store all of r k r_k r k , at memory M = N t / A = 1 M=Nt/A=1 M = N t / A = 1 ; here the user keeps a 4-dimensional compression of it, and Theorem 5 shows that a generic compression is correct for every active set.
It was noted in [12 ] that this case hinges on embedding the IE scheme [7 ] . Corollary 4 settles it: the hotplug tradeoff with 4 active users and 2 files equals the classical one wherever the latter is known, for every K ≥ 4 K\ge4 K ≥ 4 .
Thus, for every K ≥ A K\ge A K ≥ A , the hotplug model attains the lower convex envelope of the GV points [12 Theorem 2] , the YMA points (Corollary 2) and, for N ≤ A N\le A N ≤ A , the IE points (Corollary 3) of a classical system with A A A users.
Answer to an Open Question in DT2027ICCsubmission: the case A=N=3, M=3/5
Cao and Xu characterizes the optimal tradeoff for the classical ( A , N ) = ( 3 , 3 ) (A,N)=(3,3) ( A , N ) = ( 3 , 3 ) model under linear coding both in the placement ad delivery [9 ] , whose corner points are at M ∈ { 1 3 , 1 2 , 3 5 , 1 , 2 } M\in\left\{\frac{1}{3},\frac{1}{2},\frac{3}{5},1,2\right\} M ∈ { 3 1 , 2 1 , 5 3 , 1 , 2 } ; all of them except the point ( 3 5 , 3 2 ) \left(\frac{3}{5},\frac{3}{2}\right) ( 5 3 , 2 3 ) are attained in the hotplug model for every K ≥ 3 K\ge3 K ≥ 3 by Corollary 1 and Corollary 2, while the IE points add nothing here (the point with t = 2 t=2 t = 2 in (3) gives ( 4 3 , 1 ) \left(\frac{4}{3},1\right) ( 3 4 , 1 ) , which is dominated by the existing schemes).
The scheme of [9 ] that attains ( 3 5 , 3 2 ) \left(\frac{3}{5},\frac{3}{2}\right) ( 5 3 , 2 3 ) operates on q = 2 q=2 q = 2 and splits each file into 10 subfiles (one for all users, one for each pair, two for each user), and its placement relies on a cyclic orientation of the users; such a scheme does not appear to be generically correct according to Definition 2, so Theorem 5 does not appear to apply to it. A different placement found by Claude Opus 5.5 model, however, attains the same point ( 3 5 , 3 2 ) \left(\frac{3}{5},\frac{3}{2}\right) ( 5 3 , 2 3 ) and embeds explicitly in the spirit of RWP.
Proposition 1 (Point ( M , R ) = ( 3 5 , 3 2 ) (M,R)=\left(\frac{3}{5},\frac{3}{2}\right) ( M , R ) = ( 5 3 , 2 3 ) for A = N = 3 A=N=3 A = N = 3 ). For every K ≥ 3 K\ge3 K ≥ 3 , the point ( M , R ) = ( 3 5 , 3 2 ) (M,R)=\left(\frac{3}{5},\frac{3}{2}\right) ( M , R ) = ( 5 3 , 2 3 ) is achievable in the hotplug model with 3 active users out of K ≥ 3 K\ge3 K ≥ 3 and 3 files. Hence, under linear coding, the optimal tradeoff of this hotplug model equals that of the classical system with 3 users and 3 files, for every K ≥ 3 K\ge3 K ≥ 3 . For M ∈ [ 0 , 1 / 2 ] ∪ [ 1 , 3 ] M\in[0,1/2]\cup[1,3] M ∈ [ 0 , 1/2 ] ∪ [ 1 , 3 ] optimality holds without any restriction on the type of coding by the converse of [8 ] . *
Proof of Proposition 1. Here we work with q = 3 q=3 q = 3 .
Classical model: We split each file X ∈ { A , B , C } X\in\{A,B,C\} X ∈ { A , B , C } into nine private subfiles X k , [ Y ] X_{k,[Y]} X k , [ Y ] , k ∈ [ 3 ] k\in[3] k ∈ [ 3 ] , Y ∈ { A , B , C } Y\in\{A,B,C\} Y ∈ { A , B , C } , and one common subfile X c X_c X c , each of B/10 symbols. For each cyclic triple ( X , Y , W ) ∈ { ( A , B , C ) , ( B , C , A ) , ( C , A , B ) } (X,Y,W)\in\{(A,B,C),(B,C,A),(C,A,B)\} ( X , Y , W ) ∈ {( A , B , C ) , ( B , C , A ) , ( C , A , B )} , user k ∈ [ 3 ] k\in[3] k ∈ [ 3 ] caches
X k , [ W ] + Y k , [ Y ] + Y c , X k , [ X ] − X c + Y k , [ W ′ ] , (44) X_{k,[W]}+Y_{k,[Y]}+Y_c,\qquad X_{k,[X]}-X_c+Y_{k,[W']}, \tag*{(44)} X k , [ W ] + Y k , [ Y ] + Y c , X k , [ X ] − X c + Y k , [ W ′ ] , (44)
i.e., six symbols of B/10. The placement is row-wise up to one common subfile per file. The placement is invariant under every permutation of the users, and under every permutation σ \sigma σ of the files that also permutes the labels in brackets, provided that, for odd σ \sigma σ , each common subfile is also replaced by its negative, i.e., X c ↦ − σ ( X ) c X_c\mapsto-\sigma(X)_c X c ↦ − σ ( X ) c ; for example, the transposition A ↔ B A\leftrightarrow B A ↔ B maps ( Z k , 1 , … , Z k , 6 ) (Z_{k,1},\ldots,Z_{k,6}) ( Z k , 1 , … , Z k , 6 ) to ( Z k , 2 , Z k , 1 , Z k , 6 , Z k , 5 , Z k , 4 , Z k , 3 ) (Z_{k,2},Z_{k,1},Z_{k,6},Z_{k,5},Z_{k,4},Z_{k,3}) ( Z k , 2 , Z k , 1 , Z k , 6 , Z k , 5 , Z k , 4 , Z k , 3 ) . Since X c ↦ − X c X_c\mapsto-X_c X c ↦ − X c is an invertible re-encoding of the file, these are symmetries of the scheme. Every demand vector is equivalent to A A A AAA AAA , A B B ABB A B B or A B C ABC A B C . For demand A A A AAA AAA , the server sends A A A , for a total of 10 transmissions. For demands A B B ABB A B B and A B C ABC A B C , the deliveries has 15 transmissions, and the decoding steps are given in Appendix § 10 . Hence, R = 15 10 = 3 2 R = \frac{15}{10} = \frac{3}{2} R = 10 15 = 2 3 .
Hotplug model: For the hotplug model, write F n = ( W n , c n ) F_n = (W_n,c_n) F n = ( W n , c n ) , n ∈ [ 3 ] n \in[3] n ∈ [ 3 ] , where row k ∈ [ 3 ] k \in[3] k ∈ [ 3 ] matrix W n ∈ F q 3 × B / 10 W_n \in\mathbb{F}_q^{3 \times B/10} W n ∈ F q 3 × B /10 collects the private subfiles of user k ∈ [ 3 ] k \in[3] k ∈ [ 3 ] and c n ∈ F q 1 × B / 10 c_n \in\mathbb{F}_q^{1 \times B/10} c n ∈ F q 1 × B /10 is the common subfile. The cache of user k ∈ [ 3 ] k \in[3] k ∈ [ 3 ] is Φ ( e k W 1 , e k W 2 , e k W 3 , c 1 , c 2 , c 3 ) \Phi(e_kW_1,e_kW_2,e_kW_3,c_1,c_2,c_3) Φ ( e k W 1 , e k W 2 , e k W 3 , c 1 , c 2 , c 3 ) , with Φ \Phi Φ the map in (44) and e k e_k e k the standard vector with a 1 in position k k k . As in [12 Theorem 2] , user k ∈ [ K ] k \in[K] k ∈ [ K ] of the hotplug model caches Φ ( g k W 1 , g k W 2 , g k W 3 , c 1 , c 2 , c 3 ) \Phi(g_kW_1,g_kW_2,g_kW_3,c_1,c_2,c_3) Φ ( g k W 1 , g k W 2 , g k W 3 , c 1 , c 2 , c 3 ) , where g 1 , … , g K ∈ F q 1 × 3 g_1,\ldots,g_K \in\mathbb{F}_q^{1 \times3} g 1 , … , g K ∈ F q 1 × 3 , q = 3 μ ≥ K − 1 q=3^\mu\ge K-1 q = 3 μ ≥ K − 1 , are such that any three are linearly independent. Given I \mathcal{I} I , the map ( W n , c n ) ↦ ( G I W n , c n ) (W_n,c_n) \mapsto(G_{\mathcal{I}}W_n,c_n) ( W n , c n ) ↦ ( G I W n , c n ) , with G I G_{\mathcal{I}} G I the invertible matrix with rows g i 1 , g i 2 , g i 3 g_{i_1},g_{i_2},g_{i_3} g i 1 , g i 2 , g i 3 , is invertible and the same for every file; the cache of user i j i_j i j is the cache of classical user j j j for the new library, and the classical delivery, whose coefficients are in F 3 \mathbb{F}_3 F 3 , applies.
The lower bound under linear coding holds because a hotplug scheme restricted to any set of active users is a classical scheme. The converse of [9 ] holds for linear schemes over every field. □
Concluding Remarks
Open questions are:
An explicit embedding of the IE schemes of [7 ] , e.g., with a structured choice of the maps Ψ k \Psi_k Ψ k such as a rank-metric code applied to the restriction, and a bound on the field size better than the union bound.
The embedding of schemes that are neither of the form of Definition 1 nor generically correct as per Definition 2, and that generalize the placement (44) , aka row-wise up to a common subfile, to other values of N N N and A A A beyond A = N = 3 A=N=3 A = N = 3 .
Whether the optimal hotplug tradeoff depends only on A A A in general: every classical point known to us that is attained by a GV, YMA or IE scheme, and the corner points of the linear tradeoff for A = N = 3 A=N=3 A = N = 3 , are attained in the hotplug model for every K ≥ A K \ge A K ≥ A , which supports a positive answer.
Deliveries for the placement in (41)
All operations are over F 3 \mathbb{F}_3 F 3 , which may be the key difference compared to the original scheme in [9 ] .
Placement: Recall that the cache for user k ∈ [ 3 ] k \in[3] k ∈ [ 3 ] is
Z k , 1 = A k , [ C ] + B k , [ B ] + B c , (45) Z_{k,1} = A_{k,[C]} + B_{k,[B]} + B_c, \tag*{(45)} Z k , 1 = A k , [ C ] + B k , [ B ] + B c , (45)
Z k , 2 = A k , [ A ] − A c + B k , [ C ] , (46) Z_{k,2} = A_{k,[A]} - A_c + B_{k,[C]}, \tag*{(46)} Z k , 2 = A k , [ A ] − A c + B k , [ C ] , (46)
Z k , 3 = B k , [ A ] + C k , [ C ] + C c , (47) Z_{k,3} = B_{k,[A]} + C_{k,[C]} + C_c, \tag*{(47)} Z k , 3 = B k , [ A ] + C k , [ C ] + C c , (47)
Z k , 4 = B k , [ B ] − B c + C k , [ A ] , (48) Z_{k,4} = B_{k,[B]} - B_c + C_{k,[A]}, \tag*{(48)} Z k , 4 = B k , [ B ] − B c + C k , [ A ] , (48)
Z k , 5 = C k , [ B ] + A k , [ A ] + A c , (49) Z_{k,5} = C_{k,[B]} + A_{k,[A]} + A_c, \tag*{(49)} Z k , 5 = C k , [ B ] + A k , [ A ] + A c , (49)
Z k , 6 = C k , [ C ] − C c + A k , [ B ] . (50) Z_{k,6} = C_{k,[C]} - C_c + A_{k,[B]}. \tag*{(50)} Z k , 6 = C k , [ C ] − C c + A k , [ B ] . (50)
Delivery for demand A B C ABC A B C : Users 1, 2, 3 request A A A , B B B , C C C . The server sends
X 1 = A 3 , [ B ] , (51) X_1 = A_{3,[B]}, \tag*{(51)} X 1 = A 3 , [ B ] , (51)
X 2 = B 1 , [ C ] , (52) X_2 = B_{1,[C]}, \tag*{(52)} X 2 = B 1 , [ C ] , (52)
X 3 = C 2 , [ A ] , (53) X_3 = C_{2,[A]}, \tag*{(53)} X 3 = C 2 , [ A ] , (53)
X 4 = A 2 , [ C ] , (54) X_4 = A_{2,[C]}, \tag*{(54)} X 4 = A 2 , [ C ] , (54)
X 5 = B 3 , [ A ] , (55) X_5 = B_{3,[A]}, \tag*{(55)} X 5 = B 3 , [ A ] , (55)
X 6 = C 1 , [ B ] , (56) X_6 = C_{1,[B]}, \tag*{(56)} X 6 = C 1 , [ B ] , (56)
X 7 = A 2 , [ A ] + A 3 , [ A ] , (57) X_7 = A_{2,[A]} + A_{3,[A]}, \tag*{(57)} X 7 = A 2 , [ A ] + A 3 , [ A ] , (57)
X 8 = B 3 , [ B ] + B 1 , [ B ] , (58) X_8 = B_{3,[B]} + B_{1,[B]}, \tag*{(58)} X 8 = B 3 , [ B ] + B 1 , [ B ] , (58)
X 9 = C 1 , [ C ] + C 2 , [ C ] , (59) X_9 = C_{1,[C]} + C_{2,[C]}, \tag*{(59)} X 9 = C 1 , [ C ] + C 2 , [ C ] , (59)
X 10 = A 2 , [ A ] − A c , (60) X_{10} = A_{2,[A]} - A_c, \tag*{(60)} X 10 = A 2 , [ A ] − A c , (60)
X 11 = B 3 , [ B ] − B c , (61) X_{11} = B_{3,[B]} - B_c, \tag*{(61)} X 11 = B 3 , [ B ] − B c , (61)
X 12 = C 1 , [ C ] − C c , (62) X_{12} = C_{1,[C]} - C_c, \tag*{(62)} X 12 = C 1 , [ C ] − C c , (62)
X 13 = A 2 , [ A ] + B 3 , [ C ] − C 2 , [ B ] , (63) X_{13} = A_{2,[A]} + B_{3,[C]} - C_{2,[B]}, \tag*{(63)} X 13 = A 2 , [ A ] + B 3 , [ C ] − C 2 , [ B ] , (63)
X 14 = B 3 , [ B ] + C 1 , [ A ] − A 3 , [ C ] , (64) X_{14} = B_{3,[B]} + C_{1,[A]} - A_{3,[C]}, \tag*{(64)} X 14 = B 3 , [ B ] + C 1 , [ A ] − A 3 , [ C ] , (64)
X 15 = C 1 , [ C ] + A 2 , [ B ] − B 1 , [ A ] . (65) X_{15} = C_{1,[C]} + A_{2,[B]} - B_{1,[A]}. \tag*{(65)} X 15 = C 1 , [ C ] + A 2 , [ B ] − B 1 , [ A ] . (65)
Decoding for demand A B C ABC A B C : Each line of the decoding uses the transmissions X i X_i X i , the cache Z k , j Z_{k,j} Z k , j of the user, and the subfiles decoded in the previous lines. The joint cyclic shift of users, files and bracket labels (k → k + 1 k \to k + 1 k → k + 1 , A → B → C → A A \to B \to C \to A A → B → C → A ) maps the demand A B C ABC A B C to itself and permutes the transmissions within each row; hence it suffices to describe the decoding at user 1. Recall we work on q = 3 q = 3 q = 3 , i.e., q x = 0 qx = 0 q x = 0 , ∀ x ∈ F q \forall x \in\mathbb{F}_q ∀ x ∈ F q . User 1 does:
A 3 , [ B ] = X 1 , (66) A_{3,[B]} = X_1, \tag*{(66)} A 3 , [ B ] = X 1 , (66)
A 2 , [ C ] = X 4 , (67) A_{2,[C]} = X_4, \tag*{(67)} A 2 , [ C ] = X 4 , (67)
A 1 , [ B ] = − X 12 + Z 1 , 6 , (68) A_{1,[B]} = -X_{12} + Z_{1,6}, \tag*{(68)} A 1 , [ B ] = − X 12 + Z 1 , 6 , (68)
A 1 , [ C ] = − X 8 + X 11 + Z 1 , 1 , (69) A_{1,[C]} = -X_8 + X_{11} + Z_{1,1}, \tag*{(69)} A 1 , [ C ] = − X 8 + X 11 + Z 1 , 1 , (69)
A 2 , [ B ] = X 12 + X 15 + Z 1 , 3 = A 2 , [ B ] + 3 C 1 , [ C ] , (70) A_{2,[B]} = X_{12} + X_{15} + Z_{1,3} = A_{2,[B]} + 3C_{1,[C]}, \tag*{(70)} A 2 , [ B ] = X 12 + X 15 + Z 1 , 3 = A 2 , [ B ] + 3 C 1 , [ C ] , (70)
A 1 , [ A ] = X 2 + X 6 − Z 1 , 2 − Z 1 , 5 = − 2 A 1 , [ A ] = − 2 A 1 , [ A ] + 3 A 1 , [ A ] , (71) A_{1,[A]} = X_2 + X_6 - Z_{1,2} - Z_{1,5} = -2A_{1,[A]} = -2A_{1,[A]} + 3A_{1,[A]}, \tag*{(71)} A 1 , [ A ] = X 2 + X 6 − Z 1 , 2 − Z 1 , 5 = − 2 A 1 , [ A ] = − 2 A 1 , [ A ] + 3 A 1 , [ A ] , (71)
A c = X 2 − Z 1 , 2 + A 1 , [ A ] , (72) A_c = X_2 - Z_{1,2} + A_{1,[A]}, \tag*{(72)} A c = X 2 − Z 1 , 2 + A 1 , [ A ] , (72)
A 2 , [ A ] = X 10 + A c , (73) A_{2,[A]} = X_{10} + A_c, \tag*{(73)} A 2 , [ A ] = X 10 + A c , (73)
A 3 , [ A ] = X 7 − A 2 , [ A ] , (74) A_{3,[A]} = X_7 - A_{2,[A]}, \tag*{(74)} A 3 , [ A ] = X 7 − A 2 , [ A ] , (74)
A 3 , [ C ] = − X 8 − X 11 − X 14 + Z 1 , 4 = A 3 , [ C ] − 3 B 3 , [ B ] . (75) A_{3,[C]} = -X_8 - X_{11} - X_{14} + Z_{1,4} = A_{3,[C]} - 3B_{3,[B]}. \tag*{(75)} A 3 , [ C ] = − X 8 − X 11 − X 14 + Z 1 , 4 = A 3 , [ C ] − 3 B 3 , [ B ] . (75)
Delivery for demand A B B ABB A B B : Users 1, 2, 3 request A A A , B B B , B B B . The server sends
X 1 = B 1 , [ A ] , (76) X_1 = B_{1,[A]}, \tag*{(76)} X 1 = B 1 , [ A ] , (76)
X 2 = B 1 , [ C ] , (77) X_2 = B_{1,[C]}, \tag*{(77)} X 2 = B 1 , [ C ] , (77)
X 3 = A 1 , [ A ] + A c , (78) X_3 = A_{1,[A]} + A_c, \tag*{(78)} X 3 = A 1 , [ A ] + A c , (78)
X 4 = A 1 , [ B ] + C 1 , [ B ] , (79) X_4 = A_{1,[B]} + C_{1,[B]}, \tag*{(79)} X 4 = A 1 , [ B ] + C 1 , [ B ] , (79)
X 5 = A 2 , [ C ] + A 3 , [ C ] , (80) X_5 = A_{2,[C]} + A_{3,[C]}, \tag*{(80)} X 5 = A 2 , [ C ] + A 3 , [ C ] , (80)
X 6 = B 1 , [ B ] + B c , (81) X_6 = B_{1,[B]} + B_c, \tag*{(81)} X 6 = B 1 , [ B ] + B c , (81)
X 7 = A 1 , [ A ] − A 2 , [ A ] − A 3 , [ A ] , (82) X_7 = A_{1,[A]} - A_{2,[A]} - A_{3,[A]}, \tag*{(82)} X 7 = A 1 , [ A ] − A 2 , [ A ] − A 3 , [ A ] , (82)
X 8 = A 2 , [ B ] + A 3 , [ B ] − C c , (83) X_8 = A_{2,[B]} + A_{3,[B]} - C_c, \tag*{(83)} X 8 = A 2 , [ B ] + A 3 , [ B ] − C c , (83)
X 9 = B 2 , [ A ] + B 3 , [ A ] − B 2 , [ B ] − B 3 , [ B ] + B 2 , [ C ] + B 3 , [ C ] , (84) X_9 = B_{2,[A]} + B_{3,[A]} - B_{2,[B]} - B_{3,[B]} + B_{2,[C]} + B_{3,[C]}, \tag*{(84)} X 9 = B 2 , [ A ] + B 3 , [ A ] − B 2 , [ B ] − B 3 , [ B ] + B 2 , [ C ] + B 3 , [ C ] , (84)
X 10 = A 2 , [ A ] − A 3 , [ A ] , (85) X_{10} = A_{2,[A]} - A_{3,[A]}, \tag*{(85)} X 10 = A 2 , [ A ] − A 3 , [ A ] , (85)
X 11 = A 2 , [ B ] − A 3 , [ B ] , (86) X_{11} = A_{2,[B]} - A_{3,[B]}, \tag*{(86)} X 11 = A 2 , [ B ] − A 3 , [ B ] , (86)
X 12 = A 2 , [ C ] − A 3 , [ C ] , (87) X_{12} = A_{2,[C]} - A_{3,[C]}, \tag*{(87)} X 12 = A 2 , [ C ] − A 3 , [ C ] , (87)
X 13 = B 2 , [ A ] − B 3 , [ A ] , (88) X_{13} = B_{2,[A]} - B_{3,[A]}, \tag*{(88)} X 13 = B 2 , [ A ] − B 3 , [ A ] , (88)
X 14 = B 2 , [ B ] − B 3 , [ B ] , (89) X_{14} = B_{2,[B]} - B_{3,[B]}, \tag*{(89)} X 14 = B 2 , [ B ] − B 3 , [ B ] , (89)
X 15 = B 2 , [ C ] − B 3 , [ C ] . (90) X_{15} = B_{2,[C]} - B_{3,[C]}. \tag*{(90)} X 15 = B 2 , [ C ] − B 3 , [ C ] . (90)
Under the swap of users 2 and 3, X 1 , … , X 9 X_1, \ldots, X_9 X 1 , … , X 9 are invariant and X 10 , … , X 15 X_{10}, \ldots, X_{15} X 10 , … , X 15 change sign.
Decoding for demand A B B ABB A B B : User 1 (requests A A A ):
A 2 , [ C ] = − X 5 − X 12 = − 2 A 2 , [ C ] = A 2 , [ C ] − 3 A 2 , [ C ] , (91) A_{2,[C]}=-X_5-X_{12}=-2A_{2,[C]}=A_{2,[C]}-3A_{2,[C]}, \tag*{(91)} A 2 , [ C ] = − X 5 − X 12 = − 2 A 2 , [ C ] = A 2 , [ C ] − 3 A 2 , [ C ] , (91)
A 3 , [ C ] = − X 5 + X 12 = − 2 A 3 , [ C ] = A 3 , [ C ] − 3 A 3 , [ C ] , (92) A_{3,[C]}=-X_5+X_{12}=-2A_{3,[C]}=A_{3,[C]}-3A_{3,[C]}, \tag*{(92)} A 3 , [ C ] = − X 5 + X 12 = − 2 A 3 , [ C ] = A 3 , [ C ] − 3 A 3 , [ C ] , (92)
A 1 , [ C ] = − X 6 + Z 1 , 1 , (93) A_{1,[C]}=-X_6+Z_{1,1}, \tag*{(93)} A 1 , [ C ] = − X 6 + Z 1 , 1 , (93)
A 1 , [ A ] = X 2 − X 3 − Z 1 , 2 = − 2 A 1 , [ A ] = A 1 , [ A ] − 3 A 1 , [ A ] , (94) A_{1,[A]}=X_2-X_3-Z_{1,2}=-2A_{1,[A]}=A_{1,[A]}-3A_{1,[A]}, \tag*{(94)} A 1 , [ A ] = X 2 − X 3 − Z 1 , 2 = − 2 A 1 , [ A ] = A 1 , [ A ] − 3 A 1 , [ A ] , (94)
A c = X 3 − A 1 , [ A ] , (95) A_c=X_3-A_{1,[A]}, \tag*{(95)} A c = X 3 − A 1 , [ A ] , (95)
A 1 , [ B ] = X 3 + X 4 − Z 1 , 5 , (96) A_{1,[B]}=X_3+X_4-Z_{1,5}, \tag*{(96)} A 1 , [ B ] = X 3 + X 4 − Z 1 , 5 , (96)
A 2 , [ A ] = X 7 − X 10 − A 1 , [ A ] = − 2 A 2 , [ A ] = A 2 , [ A ] − 3 A 2 , [ A ] , (97) A_{2,[A]}=X_7-X_{10}-A_{1,[A]}=-2A_{2,[A]}=A_{2,[A]}-3A_{2,[A]}, \tag*{(97)} A 2 , [ A ] = X 7 − X 10 − A 1 , [ A ] = − 2 A 2 , [ A ] = A 2 , [ A ] − 3 A 2 , [ A ] , (97)
A 3 , [ A ] = − X 10 + A 2 , [ A ] , (98) A_{3,[A]}=-X_{10}+A_{2,[A]}, \tag*{(98)} A 3 , [ A ] = − X 10 + A 2 , [ A ] , (98)
A 2 , [ B ] = − X 1 − X 8 − X 11 + Z 1 , 3 − Z 1 , 6 + A 1 , [ B ] = A 2 , [ B ] − 3 A 2 , [ B ] + 3 C c , (99) A_{2,[B]}=-X_1-X_8-X_{11}+Z_{1,3}-Z_{1,6}+A_{1,[B]}=A_{2,[B]}-3A_{2,[B]}+3C_c, \tag*{(99)} A 2 , [ B ] = − X 1 − X 8 − X 11 + Z 1 , 3 − Z 1 , 6 + A 1 , [ B ] = A 2 , [ B ] − 3 A 2 , [ B ] + 3 C c , (99)
A 3 , [ B ] = − X 11 + A 2 , [ B ] . (100) A_{3,[B]}=-X_{11}+A_{2,[B]}. \tag*{(100)} A 3 , [ B ] = − X 11 + A 2 , [ B ] . (100)
Decoding for demand A B B ABB A B B : User 2 (requests B B B ):
B 1 , [ A ] = X 1 , (101) B_{1,[A]}=X_1, \tag*{(101)} B 1 , [ A ] = X 1 , (101)
B 1 , [ C ] = X 2 , (102) B_{1,[C]}=X_2, \tag*{(102)} B 1 , [ C ] = X 2 , (102)
B 2 , [ C ] = X 3 − X 7 + X 10 + Z 2 , 2 = B 2 , [ C ] + 3 A 2 , [ A ] , (103) B_{2,[C]}=X_3-X_7+X_{10}+Z_{2,2}=B_{2,[C]}+3A_{2,[A]}, \tag*{(103)} B 2 , [ C ] = X 3 − X 7 + X 10 + Z 2 , 2 = B 2 , [ C ] + 3 A 2 , [ A ] , (103)
B 3 , [ C ] = − X 15 + B 2 , [ C ] , (104) B_{3,[C]}=-X_{15}+B_{2,[C]}, \tag*{(104)} B 3 , [ C ] = − X 15 + B 2 , [ C ] , (104)
B 2 , [ A ] = − X 8 − X 11 + Z 2 , 3 − Z 2 , 6 = B 2 , [ A ] − 3 A 2 , [ B ] + 3 C c , (105) B_{2,[A]}=-X_8-X_{11}+Z_{2,3}-Z_{2,6}=B_{2,[A]}-3A_{2,[B]}+3C_c, \tag*{(105)} B 2 , [ A ] = − X 8 − X 11 + Z 2 , 3 − Z 2 , 6 = B 2 , [ A ] − 3 A 2 , [ B ] + 3 C c , (105)
B 3 , [ A ] = − X 13 + B 2 , [ A ] , (106) B_{3,[A]}=-X_{13}+B_{2,[A]}, \tag*{(106)} B 3 , [ A ] = − X 13 + B 2 , [ A ] , (106)
B 2 , [ B ] = X 9 + X 13 − X 14 + X 15 + B 2 , [ C ] + B 2 , [ A ] = B 2 , [ B ] − 3 B 2 , [ B ] + 3 B 2 , [ A ] + 3 B 2 , [ C ] , (107) B_{2,[B]}=X_9+X_{13}-X_{14}+X_{15}+B_{2,[C]}+B_{2,[A]}=B_{2,[B]}-3B_{2,[B]}+3B_{2,[A]}+3B_{2,[C]}, \tag*{(107)} B 2 , [ B ] = X 9 + X 13 − X 14 + X 15 + B 2 , [ C ] + B 2 , [ A ] = B 2 , [ B ] − 3 B 2 , [ B ] + 3 B 2 , [ A ] + 3 B 2 , [ C ] , (107)
B 3 , [ B ] = − X 14 + B 2 , [ B ] , (108) B_{3,[B]}=-X_{14}+B_{2,[B]}, \tag*{(108)} B 3 , [ B ] = − X 14 + B 2 , [ B ] , (108)
B c = X 5 + X 12 + Z 2 , 1 − B 2 , [ B ] = B c + 3 A 2 , [ C ] , (109) B_c=X_5+X_{12}+Z_{2,1}-B_{2,[B]}=B_c+3A_{2,[C]}, \tag*{(109)} B c = X 5 + X 12 + Z 2 , 1 − B 2 , [ B ] = B c + 3 A 2 , [ C ] , (109)
B 1 , [ B ] = X 6 − B c . (110) B_{1,[B]}=X_6-B_c. \tag*{(110)} B 1 , [ B ] = X 6 − B c . (110)
Decoding for demand A B B ABB A B B : User 3 (requests B B B ): As user 2, with the user indices 2 and 3 swapped and X 10 , … , X 15 X_{10},\ldots,X_{15} X 10 , … , X 15 replaced by − X 10 , … , − X 15 -X_{10},\ldots,-X_{15} − X 10 , … , − X 15 .
Cache structure at the point ( 3 5 , 3 2 ) \left(\frac{3}{5},\frac{3}{2}\right) ( 5 3 , 2 3 )
Lemma 4 next holds for every scheme, linear or not; by symmetry, the same bound holds with any user in place of user 1 and any two distinct files in place of F 1 , F 2 F_1,F_2 F 1 , F 2 .
Lemma 4. For ( A , N ) = ( 3 , 3 ) (A,N)=(3,3) ( A , N ) = ( 3 , 3 ) , every scheme with memory M M M and load R R R satisfies
4 M + 2 R ≥ 5 + max ( 1 3 , H ( Z 1 ∣ F 1 , F 2 ) B ) . (111) 4M+2R\ge5+\max\left(\frac{1}{3},\frac{H(Z_1|F_1,F_2)}{B}\right). \tag*{(111)} 4 M + 2 R ≥ 5 + max ( 3 1 , B H ( Z 1 ∣ F 1 , F 2 ) ) . (111)
Proof. In [8 ] it was proved that 6 M + 3 R ≥ 8 6M+3R\ge8 6 M + 3 R ≥ 8 ; thus the first term in (48). For the new term, the second term in (48), let X : = X A B C X:=X_{ABC} X := X A B C , in which users 1, 2, 3 request A , B , C A,B,C A , B , C , and Y : = X A C B Y:=X_{ACB} Y := X A C B , in which users 1, 2, 3 request ( F 1 , F 2 , F 3 ) = ( A , C , B ) (F_1,F_2,F_3)=(A,C,B) ( F 1 , F 2 , F 3 ) = ( A , C , B ) . From ( Z 1 , Z 2 , X ) (Z_1,Z_2,X) ( Z 1 , Z 2 , X ) , users 1 and 2 decode A A A and B B B ; from ( Z 1 , Z 3 , Y ) (Z_1,Z_3,Y) ( Z 1 , Z 3 , Y ) , users 1 and 3 decode A A A and B B B . Hence
H ( Z 1 ) + H ( Z 2 ) + H ( X ) ≥ H ( Z 1 , Z 2 , X ) = H ( A , B , Z 1 ) + H ( Z 2 , X ∣ A , B , Z 1 ) , (112) H(Z_1)+H(Z_2)+H(X)\ge H(Z_1,Z_2,X)=H(A,B,Z_1)+H(Z_2,X|A,B,Z_1), \tag*{(112)} H ( Z 1 ) + H ( Z 2 ) + H ( X ) ≥ H ( Z 1 , Z 2 , X ) = H ( A , B , Z 1 ) + H ( Z 2 , X ∣ A , B , Z 1 ) , (112)
H ( Z 1 ) + H ( Z 3 ) + H ( Y ) ≥ H ( Z 1 , Z 3 , Y ) = H ( A , B , Z 1 ) + H ( Z 3 , Y ∣ A , B , Z 1 ) . (113) H(Z_1)+H(Z_3)+H(Y)\ge H(Z_1,Z_3,Y)=H(A,B,Z_1)+H(Z_3,Y|A,B,Z_1). \tag*{(113)} H ( Z 1 ) + H ( Z 3 ) + H ( Y ) ≥ H ( Z 1 , Z 3 , Y ) = H ( A , B , Z 1 ) + H ( Z 3 , Y ∣ A , B , Z 1 ) . (113)
Summing these two inequalities and using
H ( Z 2 , X ∣ A , B , Z 1 ) + H ( Z 3 , Y ∣ A , B , Z 1 ) ≥ H ( Z 2 , Z 3 , X , Y ∣ A , B , Z 1 ) , (114) H(Z_{2},X\mid A,B,Z_{1})+H(Z_{3},Y\mid A,B,Z_{1})\ge H(Z_{2},Z_{3},X,Y\mid A,B,Z_{1}), \tag*{(114)} H ( Z 2 , X ∣ A , B , Z 1 ) + H ( Z 3 , Y ∣ A , B , Z 1 ) ≥ H ( Z 2 , Z 3 , X , Y ∣ A , B , Z 1 ) , (114)
we obtain
2 H ( Z 1 ) + H ( Z 2 ) + H ( Z 3 ) + H ( X ) + H ( Y ) (115) 2H(Z_{1})+H(Z_{2})+H(Z_{3})+H(X)+H(Y) \tag*{(115)} 2 H ( Z 1 ) + H ( Z 2 ) + H ( Z 3 ) + H ( X ) + H ( Y ) (115)
≥ H ( A , B , Z 1 ) + H ( A , B , Z 1 , Z 2 , Z 3 , X , Y ) (116) \ge H(A,B,Z_{1})+H(A,B,Z_{1},Z_{2},Z_{3},X,Y) \tag*{(116)} ≥ H ( A , B , Z 1 ) + H ( A , B , Z 1 , Z 2 , Z 3 , X , Y ) (116)
= H ( A , B , Z 1 ) + 3 B = H ( Z 1 ∣ A , B ) + 5 B , (117) =H(A,B,Z_{1})+3B=H(Z_{1}\mid A,B)+5B, \tag*{(117)} = H ( A , B , Z 1 ) + 3 B = H ( Z 1 ∣ A , B ) + 5 B , (117)
since user 3 decodes C C C from ( Z 3 , X ) (Z_{3},X) ( Z 3 , X ) , so that ( A , B , Z 1 , Z 2 , Z 3 , X , Y ) (A,B,Z_{1},Z_{2},Z_{3},X,Y) ( A , B , Z 1 , Z 2 , Z 3 , X , Y ) determines all three files. The claim follows from H ( Z k ) ≤ M B H(Z_{k})\le MB H ( Z k ) ≤ M B , H ( X ) ≤ R B H(X)\le RB H ( X ) ≤ R B and H ( Y ) ≤ R B H(Y)\le RB H ( Y ) ≤ R B .
Remark 4 (Cache structure at the point ( 3 5 , 3 2 ) \left(\frac{3}{5},\frac{3}{2}\right) ( 5 3 , 2 3 ) for ( A , N ) = ( 3 , 3 ) (A,N)=(3,3) ( A , N ) = ( 3 , 3 ) ). In both the placement of [9 ] and in (44) , the caches are mutually independent and jointly independent of each single file, that is,
H ( Z 1 ) = H ( Z 1 ∣ A ) = 6 10 B , (118) H(Z_{1})=H(Z_{1}\mid A)=\frac{6}{10}B, \tag*{(118)} H ( Z 1 ) = H ( Z 1 ∣ A ) = 10 6 B , (118)
H ( Z 1 , Z 2 ) = H ( Z 1 , Z 2 ∣ A ) = 12 10 B , (119) H(Z_{1},Z_{2})=H(Z_{1},Z_{2}\mid A)=\frac{12}{10}B, \tag*{(119)} H ( Z 1 , Z 2 ) = H ( Z 1 , Z 2 ∣ A ) = 10 12 B , (119)
H ( Z 1 , Z 2 , Z 3 ) = H ( Z 1 , Z 2 , Z 3 ∣ A ) = 18 10 B . (120) H(Z_{1},Z_{2},Z_{3})=H(Z_{1},Z_{2},Z_{3}\mid A)=\frac{18}{10}B. \tag*{(120)} H ( Z 1 , Z 2 , Z 3 ) = H ( Z 1 , Z 2 , Z 3 ∣ A ) = 10 18 B . (120)
Given two files, instead, the caches are dependent and jointly determine the third file, that is,
H ( Z 1 ∣ A , B ) = 4 10 B , (121) H(Z_{1}\mid A,B)=\frac{4}{10}B, \tag*{(121)} H ( Z 1 ∣ A , B ) = 10 4 B , (121)
H ( Z 1 , Z 2 ∣ A , B ) = 7 10 B , i.e., I ( Z 1 ; Z 2 ∣ A , B ) = 1 10 B , (122) H(Z_{1},Z_{2}\mid A,B)=\frac{7}{10}B,\quad\text{i.e., }I(Z_{1};Z_{2}\mid A,B)=\frac{1}{10}B, \tag*{(122)} H ( Z 1 , Z 2 ∣ A , B ) = 10 7 B , i.e., I ( Z 1 ; Z 2 ∣ A , B ) = 10 1 B , (122)
H ( Z 1 , Z 2 , Z 3 ∣ A , B ) = B = H ( C ) . (123) H(Z_{1},Z_{2},Z_{3}\mid A,B)=B=H(C). \tag*{(123)} H ( Z 1 , Z 2 , Z 3 ∣ A , B ) = B = H ( C ) . (123)
By Lemma 4, at M = 3 5 M=\frac{3}{5} M = 5 3 every scheme (linear or not) must satisfy R ≥ 13 10 + H ( Z 1 ∣ A , B ) 2 B R\ge\frac{13}{10}+\frac{H(Z_{1}\mid A,B)}{2B} R ≥ 10 13 + 2 B H ( Z 1 ∣ A , B ) . Hence every scheme with H ( Z 1 ∣ A , B ) ≥ 4 10 B H(Z_{1}\mid A,B)\ge\frac{4}{10}B H ( Z 1 ∣ A , B ) ≥ 10 4 B , such as Cao-Xu’s scheme, must have R ≥ 3 2 R\ge\frac{3}{2} R ≥ 2 3 ; and every scheme with R = 3 2 − ϵ R=\frac{3}{2}-\epsilon R = 2 3 − ϵ , ϵ > 0 \epsilon>0 ϵ > 0 , must have H ( Z k ∣ F i , F j ) ≤ ( 4 10 − 2 ϵ ) B H(Z_{k}\mid F_{i},F_{j})\le\left(\frac{4}{10}-2\epsilon\right)B H ( Z k ∣ F i , F j ) ≤ ( 10 4 − 2 ϵ ) B for every user k k k and every two files F i , F j F_{i},F_{j} F i , F j ; thus, each cache must store less about any file given the other two than in the known linear schemes.
The Linear Program (LP) that minimizes the load R R R over Shannon inequalities only, with the six demand vectors that are permutations of ( A , B , C ) (A,B,C) ( A , B , C ) and demand ( A , B , B ) (A,B,B) ( A , B , B ) , gives R ≥ 22 15 R\ge\frac{22}{15} R ≥ 15 22 at M = 3 5 M=\frac{3}{5} M = 5 3 , which is consistent with Lemma 4 for H ( Z 1 ∣ A , B ) = 1 3 B H(Z_{1}\mid A,B)=\frac{1}{3}B H ( Z 1 ∣ A , B ) = 3 1 B . An optimal solution of this “7-demand-Shannon-only-LP” gives the same entropies as in (55) but conditioning in two files gives
H ( Z 1 ∣ A , B ) = 1 3 B , (124) H(Z_{1}\mid A,B)=\frac{1}{3}B, \tag*{(124)} H ( Z 1 ∣ A , B ) = 3 1 B , (124)
H ( Z 1 , Z 2 ∣ A , B ) = 2 3 B , (125) H(Z_{1},Z_{2}\mid A,B)=\frac{2}{3}B, \tag*{(125)} H ( Z 1 , Z 2 ∣ A , B ) = 3 2 B , (125)
H ( Z 1 , Z 2 , Z 3 ∣ A , B ) = B = H ( C ) , (126) H(Z_{1},Z_{2},Z_{3}\mid A,B)=B=H(C), \tag*{(126)} H ( Z 1 , Z 2 , Z 3 ∣ A , B ) = B = H ( C ) , (126)
that is, given two files, the caches are mutually independent and split the third file into three disjoint parts. Row-wise placement produces independent caches. Every row-wise placement (linear or not) satisfies 3 R + 4 M ≥ 7 3R+4M\ge7 3 R + 4 M ≥ 7 [12 ] , i.e., R ≥ 23 15 > 22 15 R\ge\frac{23}{15}>\frac{22}{15} R ≥ 15 23 > 15 22 at M = 3 5 M=\frac{3}{5} M = 5 3 . Hence, a scheme that attains the “7-demand-Shannon-only-LP” bound R = 22 15 R=\frac{22}{15} R = 15 22 at M = 3 5 M=\frac{3}{5} M = 5 3 , if it exists, has a placement that is neither linear nor row-wise; thus, if it exists, the split of the third file among the caches must depend on the values of the two given files.
Table 2 reports the conditional entropies of sets of caches and transmissions given no file, one file and two files. The format is ( a ; b ; c ) (a;b;c) ( a ; b ; c ) , where a a a is for an optimal solution of the LP with Shannon inequalities only; b b b for an optimal solution of the LP with, in addition, the common information K 1 K_1 K 1 of [9 ] , which is a function of ( Z 1 , X B A C ) (Z_1,X_{BAC}) ( Z 1 , X B A C ) and of A A A , which gives R ≥ 3 2 R\ge\frac{3}{2} R ≥ 2 3 ; and c c c for the scheme in this Appendix which is equivalent to [9 ] . The two LP were solved with the HiGHS solver, with the six permutations of ( A , B , C ) (A,B,C) ( A , B , C ) and with ( A , B , B ) (A,B,B) ( A , B , B ) as demand vectors, and with the symmetries of the problem that map these demand vectors and the variable K 1 K_1 K 1 to themselves. The optimal solutions of the programs are not unique, and Table 2 reports the ones returned by the solver. At every optimal solution of the “7-demand-Shannon-only-LP”, we have: every cache has H ( Z k ) = H ( Z k ∣ F i ) = M B H(Z_k)=H(Z_k\mid F_i)=MB H ( Z k ) = H ( Z k ∣ F i ) = M B ; every two caches are independent, unconditionally and given one file; the joint entropy of the three caches, unconditionally or given one file, is in a range H ( Z 1 , Z 2 , Z 3 ) / B , H ( Z 1 , Z 2 , Z 3 ∣ A ) / B ∈ [ 46 / 30 , 18 / 10 ] H(Z_1,Z_2,Z_3)/B,H(Z_1,Z_2,Z_3\mid A)/B\in[46/30,18/10] H ( Z 1 , Z 2 , Z 3 ) / B , H ( Z 1 , Z 2 , Z 3 ∣ A ) / B ∈ [ 46/30 , 18/10 ] , which is noted in Table 2 as 18 ∗ 18^* 1 8 ∗ ; and, given two files, the three caches are mutually independent.
Table 2. Here B = 10 = H ( F n ) B=10=H(F_n) B = 10 = H ( F n ) ; we show H ( row ∣ column ) H(\text{row}\mid\text{column}) H ( row ∣ column ) for ( N , K ) = ( 3 , 3 ) (N,K)=(3,3) ( N , K ) = ( 3 , 3 ) and M = 3 2 B = 6 M=\frac{3}{2}B=6 M = 2 3 B = 6 ; entries are ( a ; b ; c ) (a;b;c) ( a ; b ; c ) , with a a a at an optimal point of the LP with Shannon inequalities only (R ≥ 22 15 = 44 3 B R\ge\frac{22}{15}=\frac{44}{3B} R ≥ 15 22 = 3 B 44 ), b b b at an optimal point of the LP with Shannon inequalities and the common information K 1 K_1 K 1 of [9 ] (R ≥ 3 2 = 15 B R\ge\frac{3}{2}=\frac{15}{B} R ≥ 2 3 = B 15 ), and c c c for the achievable scheme of [9 ] .
Remark 5. A stronger form of the second bound in Lemma 4 is: with ∑ j ∈ [ 3 ] H ( Z j ) ≤ 3 M B \sum_{j\in[3]}H(Z_j)\le3MB ∑ j ∈ [ 3 ] H ( Z j ) ≤ 3 M B we have
5 ≤ 2 R + 3 M + min k , { i , j } I ( Z k ; F i , F j ) B . (127) 5\le2R+3M+\min_{k,\{i,j\}}\frac{I(Z_k;F_i,F_j)}{B}. \tag*{(127)} 5 ≤ 2 R + 3 M + k , { i , j } min B I ( Z k ; F i , F j ) . (127)
Since the files are independent, I ( Z 1 ; F 1 , F 2 ) = I ( Z 1 ; F 1 ) + I ( Z 1 ; F 2 ) + I ( F 1 ; F 2 ∣ Z 1 ) I(Z_1;F_1,F_2)=I(Z_1;F_1)+I(Z_1;F_2)+I(F_1;F_2\mid Z_1) I ( Z 1 ; F 1 , F 2 ) = I ( Z 1 ; F 1 ) + I ( Z 1 ; F 2 ) + I ( F 1 ; F 2 ∣ Z 1 ) ; in the Cao–Xu’s schemes and at every optimal solution of “7-demand-Shannon-only-LP”, the caches are independent of each single file, so I ( Z 1 ; F 1 , F 2 ) = I ( F 1 ; F 2 ∣ Z 1 ) I(Z_1;F_1,F_2)=I(F_1;F_2\mid Z_1) I ( Z 1 ; F 1 , F 2 ) = I ( F 1 ; F 2 ∣ Z 1 ) ; hence, Lemma 4 states that, to lower the load, every cache must create more dependence between every two files.