A Class of Non-Linearly Solvable Networks
Joseph M. Connelly, K. Zeger · IEEE Transactions on Information Theory · 2016
For each positive composite integer m, a network is constructed, which is solvable over an alphabet of size m but is not solvable over any smaller alphabet. These networks have no linear solutions over any module alphabets and are not asymptotically linearly solvable over any finite-field alphabets. The networks' capacities are all shown to equal one, and their linear capacities are all shown to be bounded away from one for all finite-field alphabets. In addition, if m is a non-power-of-prime composite number, then such a network is not solvable over any prime-power-size alphabet.