Multicast Network Coding and Field Sizes

A fundamental result in network coding theory is that a multicast network is linearly solvable over every sufficiently large field. In particular, a linear solution over GF(q) can be efficiently constructed when q is no smaller than the number of receivers,.

 In the first part of the talk, we reveal a surprising property that a multicast network linearly solvable over a given finite field is not necessarily linearly solvable over all larger finite fields, i.e., it is possible to have q_min < q^*_max­, where q_min and q^*_max­ stand for the minimum field size for the existence of a linear solution and the maximum field size for the non-existence of a linear solution, respectively. Specifically, we demonstrate three multicast networks each of which respectively has: (i) q_min = 7, q^*_max­ = 8; (ii) q_min = 16, q^*_max­ = 17; (iii) q_min = 5, q^*_max­ equal to a Mersenne prime plus 1, which can be extremely large.The insight brought from these networks with the intriguing property q_min < q^*_max is that not only the field size q, but also the order of multiplicative subgroups in GF(q) plays an important role in the linear solvability over GF(q).

 In the second part of the talk, for every finite field pair (GF(q), GF(q¢)) subject to a so-called subgroup order criterion, we propose a general framework to construct a multicast network linearly solvable over GF(q) but not over GF(q’). This general framework subsumes all exemplifying networks in the first part as special construction instances. Moreover, it can construct a series of new multicast networks with q_min < q^*_max. In particular, for any k ³ 2, an even more surprising network that is linearly solvable over GF(2^2k) but not over GF(2^2k+1) can be constructed. This reveals that the gap q^*_max – q_min can not only be positive, but tend to infinity as well.