Capacity of 3-user Linear Computation Broadcast over Fq with 1D Demand and Side-Information

The linear computation broadcast (LCBC) problem studied in this work is comprised of a d dimensional data vector X that is stored at a server, and 3 users, such that the k
^th
user, k ∈ [1 : 3], has 1 dimensional demand W
k
= X
^T
v
k
and 1 dimensional side-information ${\text{W}}_k^\prime{\text{ = }}{{\text{X}}^T}{\text{v}}_k^\prime$, that are arbitrary linear combinations of the data vector over a finite field ${\mathbb{F}_q}$. The optimal broadcast cost Δ* is the minimum amount of information that the server must broadcast in order to satisfy all three users' demands. The main result of this work is the exact characterization of Δ
^*
, which is shown to only take one of the values: 0, 1, 1.5, 2, 3 in all cases. In contrast to the 2 user setting previously studied by Sun and Jafar, it turns out that in the 3 user LCBC, scalar linear coding is insufficient to construct optimal achievable schemes, and the entropic formulation (where the entropies of all subsets of $\left\{ {{{\mathbf{W}}_1},{{\mathbf{W}}_2},{{\mathbf{W}}_3},{\mathbf{W}}_1^\prime,{\mathbf{W}}_2^\prime,{\mathbf{W}}_3^\prime} \right\}$ are specified, but not their functional forms) is insufficient to obtain a tight converse. Instead, we need vector coding and functional submodularity, especially in those cases where Δ
^*
= 1.5. Remarkably, for a given dimensional specification d, while Δ
^*
can take different values depending on the realizations of ${{\mathbf{v}}_k},{\mathbf{v}}_k^\prime$, almost all realizations over a large field yield the same Δ
^*
as a function of d, which happens to be 0, 1, 1.5, 2, 2, 3 for d = 1, 2, 3, 4, 5, 6+, respectively.