On Base Field of Linear Network Coding

For a (single-source) multicast network, the size of a base field is the most known and studied algebraic identity that is involved in characterizing its linear solvability over the base field. In this paper, we design a new class $mathcal{N}$ of multicast networks and obtain an explicit formula for the linear solvability of these networks, which involves the associated coset numbers of a multiplicative subgroup in a base field. The concise formula turns out to be the first that matches the topological structure of a multicast network and algebraic identities of a field other than size. It further facilitates us to unveil emph{infinitely many} new multicast networks linearly solvable over GF($q$) but not over GF($q$) with $q < q$, based on a subgroup order criterion. In particular, i) for every $kgeq 2$, an instance in $mathcal{N}$ can be found linearly solvable over GF($2^{2k}$) but emph{not} over GF($2^{2k+1}$), and ii) for arbitrary distinct primes $p$ and $p$, there are infinitely many $k$ and $k$ such that an instance in $mathcal{N}$ can be found linearly solvable over GF($p^k$) but emph{not} over GF($p^{k}$) with $p^k < p^{k}$. On the other hand, the construction of $mathcal{N}$ also leads to a new class of multicast networks with $Theta(q^2)$ nodes and $Theta(q^2)$ edges, where $q geq 5$ is the minimum field size for linear solvability of the network.