Multicast Network Coding and Field Sizes

Abstract—In an acyclic multicast network, it is well known that a linear network coding solution over GF(q) exists when q is sufficiently large. In particular, for each prime power q no smaller than the number of receivers, a linear solution over GF(q) can be efficiently constructed. In this work, we reveal that a linear solution over a given finite field does not necessarily imply the existence of a linear solution over all larger finite fields. Specifically, we prove by construction that: (i) For every source dimension no smaller than 3, there is a multicast network linearly solvable over GF(7) but not over GF(8), and there is another multicast network linearly solvable over GF(16) but not over GF(17); (ii) There is a multicast network linearly solvable over GF(5) but not over such GF(q) that q> 5 is a Mersenne prime plus 1, which can be extremely large. Index Terms—Linear network coding, multicast network, field size, Mersenne prime. I