# External Codes for Multiple Unicast Networks
via Interference Alignment111Data sharing not applicable to this article as no
datasets were generated or analysed during the current study.

F. R. Kschischang Supported by a Discovery Grant from the Natural Sciences and
Engineering Research Council of Canada. University of Toronto, Canada  F.
Manganiello Partially supported by the National Science Foundation under grant
DMS-1547399. Clemson University, U.S.A.  A. Ravagnani Supported by the Dutch
Research Council through grants VI.Vidi.203.045 and OCENW.KLEIN.539, by the
Royal Academy of Arts and Sciences of the Netherlands, and by the European
Commission via the ENCODE project. Eindhoven University of Technology, the
Netherlands  K. Savary 22footnotemark: 2 Clemson University, U.S.A.

###### Abstract

We introduce a formal framework to study the multiple unicast problem for a
coded network in which the network code is linear over a finite field and
fixed. We show that the problem corresponds to an interference alignment
problem over a finite field. In this context, we establish an outer bound for
the achievable rate region and provide examples of networks where the bound is
sharp. We finally give evidence of the crucial role played by the field
characteristic in the problem.

##  1 Introduction

The typical scenario considered in the context of network coding consists of
one or multiple sources of information attempting to communicate to multiple
terminals through a network of intermediate nodes. Various communication
paradigms have been studied in this setting, including noisy, adversarial,
error-free multicast, and multiple-unicast networks; see [1, 2, 3, 4, 5, 6, 7,
8] among many others.

To our best knowledge, in most network coding references users are allowed to
freely design both the network code (i.e., how the intermediate vertices
process information packets) and the external codes of the sources. In
particular, designing the network code is part of the communication problem.

This paper considers the multiple unicast problem when the network code is
linear and fixed, and only the external network codes can be freely designed
by the source-receiver pairs. In this context, source-receiver pairs compete
for network resources and interfere with each other. We argue that, in this
regime, the multiple unicast problem corresponds to an interference alignment
problem over finite fields. While interference alignment over the complex
field has been extensively studied in more classical information theory
settings, methods do not extend to finite fields in any obvious way. We refer
to [9] and [10] for the “classical” interference alignment problem.

The concept of interference alignment has also been considered over finite
fields, in connection with network coding. For example, [6] and [7] propose
interference alignment solutions, in combination with network coding, to
construct schemes for coded, multiple unicast networks. Related contributions
are [11, 12, 9, 13], all of which study a problem that is different from the
one we address in this paper.

This work makes three main contributions: (1) it introduces a framework for
investigating multi-shot interference alignment problems over finite fields;
(2) it establishes an outer bound for the achievable rate regions in the
context outlined above and provides examples where the bound is sharp; (3) it
shows how the field characteristic plays a crucial role in the solution to
this problem. Note that (3) already played an important role in the networks
introduced in [4], but is in sharp contrast with what is typically observed in
network coding results for unicast networks, where the field size, rather than
the characteristic, is the main player.

The rest of the paper is organized as follows. In Section 2 we formally
introduce the communication model and formulate the problem on which we focus.
In Section 3 we formalize the concepts of achievable rate regions, considering
the number of channel uses. Section 4 establishes an outer bound for said
achievable rate regions, and Section 5 describes the role played by the field
characteristic. The paper contains several examples that illustrate concepts
and results.

##  2 Communication Model and Problem Formulation

Throughout this paper, $q$ is a prime power and $\mathbb{F}_{q}$ denotes the
finite field with $q$ elements. We denote the set of positive integers by
$\mathbb{N}=\\{1,2,\ldots\\}$. All vectors in this paper are row vectors. For
$\alpha_{1},\dots,\alpha_{\ell}\in\mathbb{F}_{q}^{n}$, we denote by
$\langle\alpha_{1},\dots,\alpha_{\ell}\rangle$ the $\mathbb{F}_{q}$-span of
$\alpha_{1},\dots,\alpha_{\ell}$. When
$\mathbb{F}_{p}\subseteq\mathbb{F}_{q}$, we denote by
$\langle\alpha_{1},\dots,\alpha_{\ell}\rangle_{p}$ the $\mathbb{F}_{p}$-span
of $\alpha_{1},\dots,\alpha_{\ell}$.

We start by informally describing the problem studied in this paper, deferring
rigorous definitions for later.

######  Problem Formulation.

We consider $n$ uncoordinated sources and terminals, denoted by
$S_{1},...,S_{n}$ and $T_{1},...,T_{n}$, respectively. Terminal $T_{i}$ is
interested in decoding only the symbols emitted by source $S_{i}$ (multiple
unicast problem). The sources are connected to the terminals via a network of
intermediate nodes, $\mathcal{N}$ (a directed, acyclic multigraph). The
alphabet of the network is $\mathbb{F}_{q}$ and each edge has a capacity of
one symbol. Alphabet symbols combine linearly at the intermediate nodes of the
network, i.e., linear network coding is used; see [2, 3].

We are interested in describing the region of achievable rates for a network
of the type we just described, assuming that the operations performed by the
intermediate nodes are linear and fixed. In other words, sources and terminals
cannot change how the network’s nodes linearly combine symbols, but are free
to agree on a codebook. Under these assumptions, source-receiver pairs compete
for the network’s resources.

The following example illustrates the problem at hand.

######  Example 1.

Figure 1 depicts a network with two sources and terminals. Terminal $T_{i}$ is
interested only in decoding messages from source $S_{i}$. The operations
performed by the gray vertices are fixed. We will return to this network in
Example 4.

$S_{1}$$S_{2}$$T_{1}$$T_{2}$ Figure 1: Network for Example 1.

In this paper, we propose the following formal definition of a communication
network, which will facilitate the analysis of the problem we have described
above.

######  Definition 2.

A multiple unicast network is a 4-tuple

$\mathcal{N}=(\mathcal{V},\mathcal{E},(S_{1},\ldots,S_{n}),(T_{1},\ldots,T_{n})),$

where:

  1. (A)

$(\mathcal{V},\mathcal{E})$ is a finite, directed, acyclic multigraph, which
may include parallel edges;

  2. (B)

$n\geq 1$ is an integer;

  3. (C)

$S_{1},\ldots,S_{n}\in\mathcal{V}$ are distinct vertices called sources;

  4. (D)

$T_{1},\ldots,T_{n}\in\mathcal{V}$ are distinct vertices called terminals or
sinks.

We also assume that the following hold:

  1. (E)

$\\{S_{1},\ldots,S_{n}\\}\cap\\{T_{1},\ldots,T_{n}\\}=\emptyset$;

  2. (F)

for any $i\in\\{1,\ldots,n\\}$, there exists a directed path in
$(\mathcal{V},\mathcal{E})$ connecting $S_{i}$ to $T_{i}$;

  3. (G)

sources do not have incoming edges and terminals do not have outgoing edges;

  4. (H)

for every vertex $V\in\mathcal{V}$, there exists a directed path from $S_{i}$
to $V$ and from $V$ to $T_{j}$, for some $i,j\in\\{1,\ldots,n\\}$.

For $V\in\mathcal{V}$ we denote by $\partial^{-}(V)$, respectively
$\partial^{+}(V)$, the indegree, respectively outdegree, of $V$, meaning the
number of edges incident to, respectively from, $V$. Moreover, let
$\mathcal{V}^{*}=\mathcal{V}\setminus(\\{S_{1},\ldots,S_{n}\\}\cup\\{T_{1},\ldots,T_{n}\\})$
denote the set of nonsource and nonterminal vertices, meaning the set of
intermediate network nodes.

We assume that the intermediate nodes of a network process the alphabet
symbols linearly. This is made rigorous by the following concept.

######  Definition 3.

Let $\mathcal{N}$ be as in Definition 2. A linear network code, or simply
network code, for $\mathcal{N}$ is a tuple of matrices

$\mathcal{F}=\left(\mathcal{F}_{V}\in\mathbb{F}_{q}^{\partial^{-}(V)\times\partial^{+}(V)}\mid
V\in\mathcal{V}^{*}\right).$

Given a network code, the network operates as follows. Fix an intermediate
vertex $V\in\mathcal{V}^{*}$ and let $a=\partial^{-}(V)$, $b=\partial^{+}(V)$
be the indegree and outdegree of $V$, respectively. Then $V$ collects a vector
of alphabet symbols $(x_{1},\ldots,x_{a})$ over the incoming edges, and emits
the entries of

$\begin{pmatrix}y_{1}&\ldots&y_{b}\end{pmatrix}=\begin{pmatrix}x_{1}&\ldots&x_{a}\end{pmatrix}\cdot\mathcal{F}_{V}\in\mathbb{F}_{q}^{b}$

over the outgoing edges. This fully specifies how $V$ processes information,
provided a linear extension of the partial order of the network edges is
fixed. Thus, $x_{1}$ is the symbol that arrives on the minimum edge (with
respect to this linear order) at $V$, $x_{2}$ is the symbol that arrives on
the minimum of the remaining edges, etc., and similarly for
$y_{1},\dots,y_{b}$. In this paper, networks are delay-free, and communication
is instantaneous.

######  Example 4.

The same network admits multiple network codes. For this example, consider the
network $\mathcal{N}$ from Example 1 with the intermediate nodes labeled as in
Figure 2 and let us assume that the alphabet is $\mathbb{F}_{3}$.

$S_{1}$$S_{2}$$T_{1}$$T_{2}$$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$$V_{6}$$V_{7}$$V_{8}$
Figure 2: Network from Example 1 with labeled vertices.

The following are two network codes defined on the network of Figure 2 where
the order of the entries in the tuple follows the order of the intermediate
nodes, and the order of the entries in the matrices agrees with the order of
the outgoing and incoming channels in the nodes respectively.

$\mathcal{F}_{1}=\left(\begin{pmatrix}1\end{pmatrix},\begin{pmatrix}1\end{pmatrix},\begin{pmatrix}1&1&1\end{pmatrix},\begin{pmatrix}1&1&1\end{pmatrix},\begin{pmatrix}1\\\
1\\\ 1\end{pmatrix},\begin{pmatrix}1\\\ 1\\\
1\end{pmatrix},\begin{pmatrix}1\end{pmatrix},\begin{pmatrix}1\end{pmatrix}\right)$
$\mathcal{F}_{2}=\left(\begin{pmatrix}1\end{pmatrix},\begin{pmatrix}1\end{pmatrix},\begin{pmatrix}1&1&1\end{pmatrix},\begin{pmatrix}1&1&1\end{pmatrix},\begin{pmatrix}1\\\
1\\\ 1\end{pmatrix},\begin{pmatrix}1\\\ 1\\\
2\end{pmatrix},\begin{pmatrix}1\end{pmatrix},\begin{pmatrix}1\end{pmatrix}\right)$

The choice of a linear network code $\mathcal{F}$ for a communication network
$\mathcal{N}$ induces end-to-end transfer matrices, one for each source-
terminal pair. We denote by $F_{i,j}$ the transfer matrix from $S_{i}$ to
$T_{j}$.

######  Example 5.

Using the network $\mathcal{N}$ from Example 1, the network code
$\mathcal{F}_{1}$ induces the transfer matrices

$F_{1,1}=F_{2,2}=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix},\
F_{1,2}=\begin{pmatrix}0&0\\\ 0&0\end{pmatrix},\ \textnormal{and}\
F_{2,1}=\begin{pmatrix}1&1\\\ 1&1\end{pmatrix},$

whereas the network code $\mathcal{F}_{2}$ induces transfer matrices

$F_{1,1}=F_{2,2}=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix},\
F_{1,2}=\begin{pmatrix}0&0\\\ 0&0\end{pmatrix},\ \textnormal{and}\
F_{2,1}=\begin{pmatrix}1&1\\\ 1&2\end{pmatrix}.$

In one channel use, assuming that $S_{i}$ transmits
$x_{i}\in\mathbb{F}_{q}^{\partial^{+}(S_{i})}$, terminal $T_{j}$ observes the
vector

$y_{j}=\sum_{i=1}^{n}x_{i}F_{i,j}\in\mathbb{F}_{q}^{\partial^{-}(T_{j})}.$

Since in this paper both the communication network $\mathcal{N}$ and the
linear network code $\mathcal{F}$ are supposed to be fixed, the end-to-end
transfer matrices induced by them fully specify the communication channel. We,
therefore, propose the following definition.

######  Definition 6.

A $q$-ary linear multiple unicast channel (in short, $q$-LMUC) is a 4-tuple
$\mathcal{L}=(n,\boldsymbol{s},\boldsymbol{t},F)$, where $n\in\mathbb{N}$ is a
positive integer,
$\boldsymbol{s}=(s_{1},\dots,s_{n}),\boldsymbol{t}=(t_{1},\dots,t_{n})\in\mathbb{N}^{n}$,
and $F\in\mathbb{F}_{q}^{s\times t}$, where $s=\sum_{i=1}^{n}s_{i}$ and
$t=\sum_{i=1}^{n}t_{i}$. We call $F$ the transfer matrix and regard it as a
block matrix

$F=\begin{pmatrix}F_{1,1}&\cdots&F_{1,n}\\\ \vdots&\ddots&\vdots\\\
F_{n,1}&\cdots&F_{n,n}\end{pmatrix},$

where block $F_{i,j}$ has size $s_{i}\times t_{j}$.

Here $n$ represents the number of source-terminal pairs,
$s_{i}=\partial^{+}(S_{i})$, and $t_{i}=\partial^{-}(T_{i})$ for
$i=1,\dots,n$. Moreover, $F$ collects the transfer matrices for each source-
terminal pair. Note that we do not need to remember the communication network
or the entire network code. The matrix $F$ fully describes the end-to-end
channel laws for a single channel use.

We can extend this definition for multiple uses of the channel as follows.
Suppose that the network is used $m\geq 1$ times. The channel input is an
element
$x=(x_{1},\dots,x_{n})\in\mathbb{F}_{q^{m}}^{s_{1}}\times\cdots\times\mathbb{F}_{q^{m}}^{s_{n}}=\mathbb{F}_{q^{m}}^{s}$.
More precisely, for all $i\in\\{1,\dots,n\\}$,
$x_{i}\in\mathbb{F}_{q^{m}}^{s_{i}}$ is the input that source $S_{i}$ emits.
Then the channel output is
$\smash{y=(y_{1},\dots,y_{n})\in\mathbb{F}_{q^{m}}^{t_{1}}\times\cdots\times\mathbb{F}_{q^{m}}^{t_{n}}=\mathbb{F}_{q^{m}}^{t}}$,
where

$y_{i}=x_{i}F_{i,i}+\sum_{j\neq i}x_{j}F_{j,i}$ (1)

is the vector that terminal $T_{i}$ receives on its incoming edges. Note that
the field extension $\mathbb{F}_{q^{m}}$ models $m$ uses of the channel
because the network code is assumed to be $\mathbb{F}_{q}$-linear.

######  Remark 7.

Given any $q$-LMUC as in Definition 6, it is always possible to construct a
multiple unicast network $\mathcal{N}$ and a network code $\mathcal{F}$ for
$\mathcal{N}$ that induces the given transfer matrix. We illustrate the
procedure with an example.

######  Example 8.

The $11$-LMUC

$\mathcal{L}=\left(2,(1,2),(2,2),\begin{pmatrix}1&0&2&3\\\ 0&4&5&0\\\
6&7&0&0\end{pmatrix}\right)$

induces the matrices

$F_{1,1}=\begin{pmatrix}1&0\end{pmatrix},\quad
F_{1,2}=\begin{pmatrix}2&3\end{pmatrix},\quad F_{2,1}=\begin{pmatrix}0&4\\\
6&7\end{pmatrix},\quad F_{2,2}=\begin{pmatrix}5&0\\\ 0&0\end{pmatrix}.$

A network code that induces these matrices is

$\mathcal{F}=\left(\begin{pmatrix}1&1&1\end{pmatrix},\begin{pmatrix}1&1\end{pmatrix},\begin{pmatrix}1&1\end{pmatrix},\begin{pmatrix}1\\\
6\end{pmatrix},\begin{pmatrix}4\\\ 7\end{pmatrix},\begin{pmatrix}2\\\
5\end{pmatrix},\begin{pmatrix}3\end{pmatrix}\right),$

realized by the network depicted in Figure 3. Note that

$\mathcal{F}=\left(\begin{pmatrix}1&2&3\end{pmatrix},\begin{pmatrix}4&5\end{pmatrix},\begin{pmatrix}6&7\end{pmatrix},\begin{pmatrix}1\\\
1\end{pmatrix},\begin{pmatrix}1\\\ 1\end{pmatrix},\begin{pmatrix}1\\\
1\end{pmatrix},\begin{pmatrix}1\end{pmatrix}\right),$

also induces the given transfer matrix.

$S_{1}$$S_{2}$$T_{1}$$T_{2}$ Figure 3: Network for Example 8.

Given a $q$-LMUC $\mathcal{L}=(n,\boldsymbol{s},\boldsymbol{t},F)$
representing a $q$-ary linear multiple unicast channel, we are interested in
determining which rates can be achieved by carefully selecting the codebooks
of the sources. Recall that each terminal $T_{i}$ is interested in decoding
only its corresponding source $S_{i}$. Therefore the information emitted by
the sources $S_{j}$ with $j\neq i$ acts as interference for terminal $T_{i}$.

##  3 Achievable Rate Regions and Their Properties

In this section, we propose a formal framework to describe the capacity of a
$q$-LMUC, based on the concept of fan-out set and unambiguous code. We start
with the concept of code(book).

######  Definition 9.

Let $\mathcal{L}=(n,\boldsymbol{s},\boldsymbol{t},F)$ be a $q$-LMUC and let
$m\geq 1$ be an integer. An $m$-external code, or simply an $m$-code, for
$\mathcal{L}$ is a Cartesian product $C=C_{1}\times\cdots\times C_{n}$, where
$C_{i}\subseteq\mathbb{F}_{q^{m}}^{s_{i}}$ for all $i\in\\{1,\ldots,n\\}$. The
elements of each $C_{i}$ are called codewords.

Note that we do not require that $C$ is a linear space. Recall that the
parameter $m$ in Definition 9 represents the number of channel uses, as
already mentioned when introducing Equation (1). In the sequel, for a $q$-LMUC
$\mathcal{L}=(n,\boldsymbol{s},\boldsymbol{t},F)$ and for
$i\in\\{1,\dots,n\\}$, we denote by
$\pi_{i}:\mathbb{F}_{q^{m}}^{t}\rightarrow\mathbb{F}_{q^{m}}^{t_{i}}$ the
projection on the $i$th block of coordinates (recall that
$\boldsymbol{t}=(t_{1},\ldots,t_{n})$ and $t=t_{1}+\cdots+t_{n}$).

######  Definition 10.

Let $\mathcal{L}=(n,\boldsymbol{s},\boldsymbol{t},F)$ be a $q$-LMUC,
$i\in\\{1,\ldots,n\\}$, $C$ an $m$-code for $\mathcal{L}$, and $x\in C_{i}$.
We denote by

$\textnormal{Fan}_{i}(x,C):=\\{\pi_{i}((x_{1},\dots,x_{i-1},x,x_{i+1},\dots,x_{n})F)\mid
x_{j}\in C_{j}\mbox{ for all }j\neq i\\}$

the $i$-th fan-out set of $x$ with respect to terminal $i$ and the code $C$.
The $i$-th fan-out set of $C$ is $\textnormal{Fan}_{i}(C)=\cup_{x\in
C_{i}}{\textnormal{Fan}_{i}(x,C)}\subseteq\mathbb{F}_{q^{m}}^{t_{i}}$, for all
$i\in\\{1,\ldots,n\\}$.

Following the notation of Definition 10, $\textnormal{Fan}_{i}(x,C)$ is the
set of possible words that the $i$th terminal can possibly receive when the
$i$th source emits $x$ and the other sources emit their own codewords. Fan-out
sets relate to the concept of interference as follows.

######  Definition 11.

Let $\mathcal{L}$, $m$, and $C$ be as in Definition 9. We define the
interference set of $C$ at terminal $T_{i}$ as

$\textnormal{IS}_{i}(C)=\textnormal{Fan}_{i}(0,C)=\left\\{\sum_{j\neq
i}c_{j}F_{j,i}\mid c_{j}\in C_{j}\right\\}.$

######  Remark 12.

Note that using Definition 11 we can rewrite equation (1) as

$\textnormal{Fan}_{i}(x,C)=xF_{i,i}+\textnormal{IS}_{i}(C)=\\{xF_{i,i}+y\mid
y\in\textnormal{IS}_{i}(C)\\}.$ (2)

for any $m$-code $C$, any $i\in\\{1,\ldots,n\\}$, and any $x\in C_{i}$.
Therefore the $i$-th fan-out set of $x\in C_{i}$ is a translate (or a coset,
if each $C_{i}$ is linear) of the interference set $\textnormal{IS}_{i}(C)$.

Communication is considered to be successful when each codeword can be
uniquely decoded. The following definition models this concept.

######  Definition 13.

Let $\mathcal{L}$, $m$, and $C$ be as in Definition 9. We say that $C$ is
unambiguous for $\mathcal{L}$ if for all $i\in\\{1,...,n\\}$ and for all
codewords $x_{1},x_{2}\in C_{i}$ with $x_{1}\neq x_{2}$, we have
$\textnormal{Fan}_{i}(x_{1},C)\cap\textnormal{Fan}_{i}(x_{2},C)=\emptyset$.

An unambiguous code, as in the previous definition, uniquely defines decoder
maps. More precisely, the $i$-th decoder is the map
$D_{i}:\textnormal{Fan}_{i}(C)\rightarrow\mathbb{F}_{q^{m}}^{s_{i}}$ defined
by $D_{i}(v_{i})=x_{i}$ for all $v_{i}\in\textnormal{Fan}_{i}(C)$, where
$x_{i}\in C_{i}$ is the only element with
$v_{i}\in\textnormal{Fan}_{i}(x_{i},C)$.

######  Remark 14.

Following the notation of Definition 13, if $C$ is an unambiguous $m$-code for
$\mathcal{L}$ and $C^{\prime}$ is an $m$-code for $\mathcal{L}$ with
$C^{\prime}\subseteq C$, then $C^{\prime}$ is unambiguous as well.

We are now ready to give a rigorous definition of the achievable rate region
of a $q$-LMUC $\mathcal{L}$. For convenience, for $m\geq 1$ we define the set

$\log_{q^{m}}(\mathbb{N}^{n})=\\{(\log_{q^{m}}(u_{1}),...,\log_{q^{m}}(u_{n}))\mid(u_{1},...,u_{n})\in\mathbb{N}^{n}\\}.$

######  Definition 15.

The $m$-shot achievable rate region of a $q$-LMUC $\mathcal{L}$ as in
Definition 6 is the set

$\mathcal{R}_{m}(\mathcal{L})=\\{\alpha\in\log_{q^{m}}(\mathbb{N}^{n})\mid\exists\,C=C_{1}\times\cdots\times
C_{n}\mbox{ unambiguous $m$-code for $\mathcal{L}$}\\\ \mbox{with
}\log_{q^{m}}(|C_{i}|)=\alpha_{i}\ \forall\ 1\leq i\leq
n\\}\subseteq\mathbb{R}_{\geq 0}^{n}.$

The achievable rate region of $\mathcal{L}$ is the set

$\mathcal{R}(\mathcal{L})=\overline{\bigcup_{m\geq
1}\mathcal{R}_{m}(\mathcal{L})},$

where the overline indicates the closure operator with respect to the
Euclidean topology on $\mathbb{R}^{n}$. The elements of
$\mathcal{R}(\mathcal{L})$ elements are called achievable rates.

The following example illustrates that different LMUCs supported on the same
network might have very different achievable rate regions.

######  Example 16.

The two 3-LMUCs induced by Example 4 are

$\mathcal{L}_{1}=\left(2,(2,2),(2,2),\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\
1&1&1&0\\\ 1&1&0&1\end{pmatrix}\right),\ \
\mathcal{L}_{2}=\left(2,(2,2),(2,2),\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\
1&1&1&0\\\ 1&2&0&1\end{pmatrix}\right).$

Although the two 3-LMUC have the same underlying network, they have different
1-shot achievable rate regions. Indeed, for $\mathcal{L}_{1}$, the code
$\langle(1,2)\rangle_{\mathbb{F}_{3}}\times\mathbb{F}_{3}^{2}$ is unambiguous,
meaning that $(1,2)\in\mathcal{R}_{1}(\mathcal{L})$. On the other hand,
$(1,2)\notin\mathcal{R}_{1}(\mathcal{L}_{2})$, as we now briefly explain. In
$\mathcal{L}_{2}$, the matrix $F_{2,1}$ is invertible. Moreover, a rate of the
form $(\alpha_{1},2)$ can be achieved only by a code of the form
$C=C_{1}\times\mathbb{F}_{3}^{2}$. Together with the invertibility of
$F_{2,1}$, this implies that $\textnormal{IS}_{1}(C)=\mathbb{F}_{3}^{2}$,
making $C=\\{0\\}\times\mathbb{F}_{3}^{2}$ the only unambiguous code with
$C_{2}=\mathbb{F}_{3}^{2}$.

The following result states a quite intuitive property of achievable rate
regions.

######  Proposition 17.

Let $\mathcal{L}$ be a $q$-LMUC as in Definition 6 and let $m\geq 1$. If
$(\alpha_{1},\ldots,\alpha_{n})\in\mathcal{R}_{m}(\mathcal{L})$ and
$\smash{(\beta_{1},\ldots,\beta_{n})\in\log_{q^{m}}(\mathbb{N}^{n})}$
satisfies $\beta_{i}\leq\alpha_{i}$ for all $i\in\\{1,\ldots,n\\}$, then we
have $(\beta_{1},\ldots,\beta_{n})\in\mathcal{R}_{m}(\mathcal{L})$.

###### Proof.

Since $(\alpha_{1},\ldots,\alpha_{n})\in\mathcal{R}_{m}(\mathcal{L})$, there
exists an $m$-code $C=C_{1}\times\cdots\times C_{n}$ unambiguous for
$\mathcal{L}$ with $|C_{i}|=q^{m\alpha_{i}}$ for all $i$. Since
$(\beta_{1},\ldots,\beta_{n})\in\log_{q^{m}}(\mathbb{N}^{n})$, for all $i$
there exists $D_{i}\subseteq C_{i}$ with $|D_{i}|=q^{m\beta_{i}}$. By Remark
14, the $m$-code $D=D_{1}\times\cdots\times D_{n}$ is unambiguous for
$\mathcal{L}$. This establishes the desired result. ∎

We now investigate how the various achievable rate regions relate to each
other. The following two results are inspired by (but do not immediately
follow from) the concept of time sharing.

######  Proposition 18.

Let $\mathcal{L}$ be a $q$-LMUC as in Definition 6 and let $m,m^{\prime}\geq
1$. We have

$\mathcal{R}_{m+m^{\prime}}(\mathcal{L})\supseteq\frac{m\,\mathcal{R}_{m}(\mathcal{L})+m^{\prime}\,\mathcal{R}_{m^{\prime}}(\mathcal{L})}{m+m^{\prime}}.$

###### Proof.

Let $C$ and $C^{\prime}$ be an $m$-code and an $m^{\prime}$-code,
respectively, for $\mathcal{L}$. Let $\\{\gamma_{1},...,\gamma_{m}\\}$ and
$\smash{\\{\gamma^{\prime}_{1},...,\gamma^{\prime}_{m^{\prime}}\\}}$ be
ordered bases of $\smash{\mathbb{F}_{q^{m}}}$ and
$\smash{\mathbb{F}_{q^{m^{\prime}}}}$ over $\mathbb{F}_{q}$, respectively. We
denote by $\smash{\varphi_{m}:\mathbb{F}_{q}^{m}\to\mathbb{F}_{q^{m}}}$ the
$\mathbb{F}_{q}$-isomorphism
$(a_{1},\ldots,a_{m})\mapsto\sum_{i=1}^{m}a_{i}\gamma_{i}$. Define
$\smash{\varphi_{m^{\prime}}:\mathbb{F}_{q}^{m^{\prime}}\to\mathbb{F}_{q^{m^{\prime}}}}$
analogously. Fix an ordered basis
$\smash{\\{\beta_{1},\ldots,\beta_{m+m^{\prime}}\\}}$ of
$\mathbb{F}_{q^{m+m^{\prime}}}$ over $\mathbb{F}_{q}$. We extend these three
$\mathbb{F}_{q}$-linear maps coordinate-wise. Take

$D:=\varphi_{m}^{-1}(C)\times\varphi_{m^{\prime}}^{-1}(C^{\prime}).$

Then the $(m+m^{\prime})$-code $\varphi_{m+m^{\prime}}(D)$ is unambiguous and
it satisfies

$\log_{q^{m+m^{\prime}}}\left(\varphi_{m+m^{\prime}}(D)\right)=\frac{m}{m+m^{\prime}}\log_{q^{m}}(|C|)+\frac{m^{\prime}}{m+m^{\prime}}\log_{q^{m^{\prime}}}(|C^{\prime}|).$

This establishes the desired result. ∎

The following result shows that $\mathcal{R}(\mathcal{L})$ contains the convex
hull of $\mathcal{R}_{1}(\mathcal{L})$.

######  Theorem 19.

Let $\mathcal{L}$ be a $q$-LMUC as in Definition 6. Denote by
$\mbox{conv}(\mathcal{R}_{1}(\mathcal{L}))$ the convex hull of
$\mathcal{R}_{1}(\mathcal{L})$, i.e., the set of convex combinations of the
points of $\mathcal{R}_{1}(\mathcal{L})$. Then

$\mathcal{R}(\mathcal{L})\supseteq\mbox{conv}(\mathcal{R}_{1}(\mathcal{L})).$

###### Proof.

Define $Z=|\mathcal{R}_{1}(\mathcal{L})|$ and let
$\mathcal{R}_{1}(\mathcal{L})=\\{\alpha^{(\ell)}\mid 1\leq\ell\leq Z\\}$. Let
$A:=\\{(a_{1},...,a_{Z})\in[0,1]^{Z}\mid a_{1}+\cdots+a_{Z}=1\\}$, and let
$a\in A$. We will show that for any real number $\varepsilon>0$, there exists
$m\geq 1$ and $\beta\in\mathcal{R}_{m}(\mathcal{L})$ with

$\left\|\sum_{\ell=1}^{N}a_{\ell}\alpha^{(\ell)}-\beta\right\|\leq\varepsilon.$

This will imply the desired theorem by the definition of closure in the
Euclidean topology.

Since the result is clear if $\mathcal{R}_{1}(\mathcal{L})=\\{(0,\dots,0)\\}$,
we shall assume $\nu:=\max_{\ell}\left\|\alpha^{(\ell)}\right\|>0$. For all
$\ell\in\\{1,\dots,Z\\}$, fix an unambiguous 1-code
$\smash{C^{(\ell)}=C^{(\ell)}_{1}\times\cdots\times C^{(\ell)}_{n}}$ that
achieves rate $\alpha_{\ell}$, i.e., such that

$\log_{q}\left(C^{(\ell)}_{i}\right)=\alpha_{i}\mbox{ for all $i$.}$

Since $A\cap\mathbb{Q}^{n}$ is dense in $A$, there exists a sequence
$(s^{k})_{k\in\mathbb{N}}\subseteq A\cap\mathbb{Q}^{Z}$ with the property that
$\lim_{k\rightarrow\infty}s^{k}=a$. There exists
$k_{\varepsilon}\in\mathbb{N}$ such that
$\left\|s^{k}-a\right\|\leq\varepsilon/(\nu\sqrt{Z})$ for all $k\geq
k_{\varepsilon}$. Let $s=s^{k_{\varepsilon}}$ and
$\smash{\beta=\sum_{\ell=1}^{Z}s_{\ell}\alpha_{\ell}}$ and observe that

$\left\|\sum_{\ell=1}^{Z}a_{\ell}\alpha_{\ell}-\beta\right\|\leq\nu\sum_{\ell=1}^{Z}(s_{\ell}-a_{\ell})\leq\nu\sum_{\ell=1}^{Z}|s_{\ell}-a_{\ell}|\leq\nu\sqrt{Z}\left\|s-a\right\|\leq\varepsilon.$

Therefore, it suffices to show that $\beta\in\mathcal{R}_{m}(\mathcal{L})$ for
some $m\geq 1$. Write $s=(s_{1},...,s_{Z})=(b_{1}/c_{1},...,b_{Z}/c_{Z})$,
where the $b_{\ell}$’s and the $c_{\ell}$’s are integers, and let
$m=c_{1}\cdots c_{Z}$. Then $\beta$ can be achieved in $m$ rounds by using
code $C^{(\ell)}$ for $mb_{\ell}/c_{\ell}$ rounds, $\ell\in\\{1,...,Z\\}$, in
any order. A more precise formulation can be obtained using field extension
maps as in the proof of Proposition 18 (we do not go into the details). ∎

##  4 An Outer Bound for the Achievable Rate Region

In this section, we establish an outer bound for the achievable rate region of
a $q$-LMUC. Our proof technique derives a lower bound for the size of the fan-
out sets introduced in Definition 10, which we obtain by estimating the
“amount” of interference that the users cause to each other. The outer bound
is stated in Theorem 24, which relies on two preliminary results.

######  Remark 20.

Let $M\in\mathbb{F}_{q}^{a\times b}$ be any matrix. Embed $\mathbb{F}_{q}$
into $\mathbb{F}_{q^{m}}$, where $m\geq 1$. It is well-known that the
$\mathbb{F}_{q}$-rank of $M$ is the same as its $\mathbb{F}_{q^{m}}$-rank.

We start with the following simple observation.

######  Proposition 21.

Let $\mathcal{L}=(n,\boldsymbol{s},\boldsymbol{t},F)$ be a $q$-LMUC and let
$m\geq 1$ be an integer. If $n=1$, then
$\mathcal{R}_{m}(\mathcal{L})=\\{\alpha\in\log_{q}(\mathbb{N})\mid
0\leq\alpha\leq\operatorname{rank}F\\}$.

###### Proof.

Let $C\subseteq\mathbb{F}_{q^{m}}^{s_{1}}$ be an $m$-code. Then $C$ is
unambiguous if and only if $F(x)\neq F(y)$ for all $x,y\in C$ with $x\neq y$,
i.e., if and only if the elements of $C$ belong to distinct equivalent classes
of $\mathbb{F}_{q^{m}}^{r_{1}}/\ker(F)$. This shows that if $C$ is
unambiguous, then $|C|\leq q^{m\cdot\operatorname{rank}(F)}$. Vice versa,
taking one representative for each class of
$\smash{\mathbb{F}_{q^{m}}^{r_{1}}/\ker(F)}$ produces an unambiguous $m$-code.
∎

In the remainder of the section, we show how the argument in the previous
proposition extends to an arbitrary number of users. We will need the
following preliminary result.

######  Lemma 22.

Let $V,W$ be linear spaces over $\mathbb{F}_{q^{m}}$, $m\geq 1$, and let
$L:V\to W$ be an $\mathbb{F}_{q^{m}}$-linear map. For all non-empty sets
$A\subseteq V$, we have $|L(A)|\cdot|\ker(L)|\geq|A|$.

###### Proof.

Define an equivalence relation on $A$ by setting $a\sim b$ if and only if
$L(a)=L(b)$, i.e., if and only if $a-b\in\ker(L)$. Then we know from
elementary set theory that $|A/_{\sim}|=|f(A)|$. The equivalence class of
$a\in A$ is $(a+\ker(L))\cap B$ and, therefore, it has size at most
$|\ker(L)|$. Since the equivalence classes partition $A$, we have
$|A|\leq|A/_{\sim}|\cdot|\ker(L)|$. This concludes the proof. ∎

We are now ready to state the main result of this section, providing an outer
bound for the achievable rate region of a $q$-LMUC.

######  Notation 23.

In the sequel, for a non-empty subset $I\subseteq\\{1,...,n\\}$ and $j\in I$,
we denote by $F_{I,j}$ the submatrix of $F$ formed by the blocks indexed by
$(i,j)$, as $i$ ranges over $I$.

The main result of this section is the following outer bound.

######  Theorem 24.

Let $\mathcal{L}=(n,\boldsymbol{s},\boldsymbol{t},F)$ be a $q$-LMUC, and let
$m\geq 1$ be an integer. Let
$(\alpha_{1},...,\alpha_{n})\in\mathcal{R}_{m}(\mathcal{L})$. Then for all
non-empty $I\subseteq\\{1,\ldots,n\\}$ and for all $j\in I$, we have

$\sum_{i\in
I}\alpha_{i}\leq\operatorname{rank}(F_{I,j})-\operatorname{rank}(F_{I\setminus\\{j\\},j})+\sum_{\begin{subarray}{c}k\in
I\\\ k\neq j\end{subarray}}s_{k}.$

Therefore, for all non-empty $I\subseteq\\{1,\dots,n\\}$, we have

$\sum_{i\in I}\alpha_{i}\leq\min_{j\in
I}\left\\{\operatorname{rank}(F_{I,j})-\operatorname{rank}(F_{I\setminus\\{j\\},j})+\sum_{\begin{subarray}{c}k\in
I\\\ k\neq j\end{subarray}}s_{k}\right\\}.$

###### Proof.

The result easily follows the definitions if $|I|=1$. Now fix an index set
with $|I|\geq 2$, a tuple
$(\alpha_{1},...,\alpha_{n})\in\mathcal{R}_{m}(\mathcal{L})$, and an
unambiguous $m$-code $C=(C_{1},\dots,C_{n})$ with
$\alpha_{i}=\log_{q^{m}}(|C_{i}|)$ for all $i$. For $i\notin I$, we replace
$C_{i}$ with an arbitrary subset of cardinality one. The resulting code is
unambiguous by Remark 14, and it has

$\log_{q^{m}}(|C_{i}|)=\begin{cases}\alpha_{i}&\mbox{ if $i\in I$,}\\\
0&\mbox{ if $i\notin I$.}\end{cases}$

The remainder of the proof uses the following lower bound, which we will
establish later.

######  Claim A.

For all $j\in I$ and $x\in C_{j}$, we have

$|\textnormal{Fan}_{j}(x,C)|\geq\frac{\prod_{\begin{subarray}{c}k\in I\\\
k\neq j\end{subarray}}|C_{k}|}{|\ker F_{I\setminus\\{j\\},j}|}.$ (3)

Note that by fixing $j\in I$ and summing the inequality in Claim A over all
$x\in C_{j}$ one obtains

$\sum_{x\in C_{j}}|\textnormal{Fan}_{j}(x,C)|\geq\frac{\prod_{k\in
I}|C_{k}|}{|\ker F_{I\setminus\\{j\\},j}|}\quad\mbox{for all $j\in I$.}$ (4)

Since $C$ is unambiguous, we have

$\sum_{x\in C_{j}}|\textnormal{Fan}_{j}(x,C)|=\left|\bigcup_{x\in
C_{j}}\textnormal{Fan}_{j}(x,C)\right|\leq
q^{m\cdot\operatorname{rank}(F_{I,j})},$

where the latter inequality follows from the fact that $\bigcup_{x\in
C_{j}}\textnormal{Fan}_{j}(x,C)$ is contained in the image of $F_{I,j}$.
Therefore, the inequality in (4) implies

$q^{m\cdot\operatorname{rank}(F_{I,j})}\geq\frac{\prod_{k\in
I}|C_{k}|}{|\ker(F_{I\setminus\\{j\\},j})|}\quad\mbox{for all $j\in I$.}$ (5)

We also have

$\dim_{\mathbb{F}_{q^{m}}}\ker
F_{I\setminus\\{j\\},j}=\sum_{\begin{subarray}{c}k\in I\\\ k\neq
j\end{subarray}}s_{k}-\operatorname{rank}(F_{I\setminus\\{j\\},j}).$

Therefore, taking the logarithm with base $q^{m}$ in (5) yields

$\operatorname{rank}(F_{I,j})\geq\alpha_{1}+\ldots+\alpha_{n}-\sum_{\begin{subarray}{c}k\in
I\\\ k\neq
j\end{subarray}}s_{k}+\operatorname{rank}(F_{I\setminus\\{j\\},j})\quad\mbox{for
all $j\in I$,}$ (6)

which is the desired bound.

It remains to show that Claim A holds. We only prove it for $I=\\{1,...,n\\}$
and $j=1$, as the proof for all other cases is the same (but more cumbersome
notation-wise). Fix an arbitrary $x\in C_{1}$ and view $F_{1,\\{1,...,n\\}}$
as an $\mathbb{F}_{q^{m}}$-linear map
$\mathbb{F}_{q^{m}}^{s_{1}+\cdots+s_{n}}\to\mathbb{F}_{q^{m}}^{t_{1}}$. Then
$\textnormal{Fan}_{1}(x,C)$ is the image of $C_{2}\times\cdots\times C_{n}$
under the map

$f:\mathbb{F}_{q^{m}}^{s_{2}+\cdots+s_{n}}\to\mathbb{F}_{q^{m}}^{t_{1}},\qquad(x_{2},...,x_{n})\mapsto(x,x_{2},...,x_{n})F_{\\{1,...,n\\},1}.$

We have $f=F_{11}x+g$ as functions, where

$g:\mathbb{F}_{q^{m}}^{s_{2}+\cdots+s_{n}}\to\mathbb{F}_{q^{m}}^{t_{1}},\qquad(x_{2},...,x_{n})\mapsto(x_{2},...,x_{n})F_{\\{2,...,n\\},1}.$

Therefore, the images of $f$ and $g$ have the same cardinality,
$|\textnormal{Fan}_{1}(x,C)|$. Finally, by applying Lemma 22 to the
$\mathbb{F}_{q^{m}}$-linear function $g$, we obtain

$|\textnormal{Fan}_{1}(x,C)|\cdot|\ker(g)|\geq|C_{2}\times\cdots\times
C_{n}|,$

which is the inequality in Claim A. ∎

We illustrate Theorem 24 with two examples.

######  Example 25.

Let $q$ be arbitrary and consider the $q$-LMUC
$\mathcal{L}=(2,(2,2),(2,2),F)$, where

$F=\begin{pmatrix}1&0&0&0\\\ 0&1&1&0\\\ 0&1&1&0\\\ 0&0&0&1\end{pmatrix}.$

Note that $\mathcal{L}$ is induced, for example, by the network in Figure 4.

$S_{1}$$S_{2}$$T_{1}$$T_{2}$ Figure 4: Network for Example 25.

By applying Theorem 24, we obtain that for all $m\geq 1$ and all
$(\alpha_{1},\alpha_{2})\in\mathcal{R}_{m}(\mathcal{L})$ we have
$\alpha_{1}+\alpha_{2}\leq 3$, since

$\displaystyle\operatorname{rank}\begin{pmatrix}F_{11}\\\
F_{21}\end{pmatrix}-\operatorname{rank}F_{21}+s_{2}$ $\displaystyle=2-1+2=3,$
$\displaystyle\operatorname{rank}\begin{pmatrix}F_{12}\\\
F_{22}\end{pmatrix}-\operatorname{rank}F_{12}+s_{1}$ $\displaystyle=2-1+2=3.$

For $m=1$, the $1$-codes
$C=\left(\mathbb{F}_{q}^{2},\langle(0,1)\rangle\right)$ and
$C=\left(\langle(1,0)\rangle,\mathbb{F}_{q}^{2}\right)$ are both unambiguous,
meaning that the rates $(2,1)$ and $(1,2)$ are achievable in one shot. This
implies that the upper bound of Theorem 24 is tight in this case.

######  Example 26.

Let $q$ be arbitrary and consider the $q$-LMUC
$\mathcal{L}=(2,(1,2),(1,2),F)$, where

$F=\begin{pmatrix}1&1&1\\\ 1&1&0\\\ 1&0&1\end{pmatrix}.$

Note that $\mathcal{L}$ is induced, for example, by the network in Figure 5.

$S_{1}$$S_{2}$$T_{1}$$T_{2}$ Figure 5: Network for Example 26.

By applying Theorem 24 we obtain that for all $m\geq 1$ and for all
$(\alpha_{1},\alpha_{2})\in\mathcal{R}_{m}(\mathcal{L})$ we have
$\alpha_{1}+\alpha_{2}\leq 2$. Indeed,

$\displaystyle\operatorname{rank}\begin{pmatrix}F_{11}\\\
F_{21}\end{pmatrix}-\operatorname{rank}F_{21}+s_{2}$ $\displaystyle=1-1+2=2,$
$\displaystyle\operatorname{rank}\begin{pmatrix}F_{12}\\\
F_{22}\end{pmatrix}-\operatorname{rank}F_{12}+s_{1}$ $\displaystyle=2-1+1=2.$

In the next section, we will show that whether or not this bound is sharp
depends on the characteristic of the finite field $\mathbb{F}_{q}$ and not,
for example, on $m$.

##  5 The Role of the Field Characteristic

The goal of this section is to illustrate the role that the field
characteristic plays in the problem we are considering. Note that the problem
we are studying in this section is an extension of the problem studied until
now. When defining a $q$-LMUC, since $q$ is a given parameter of the network,
the characteristic of the field is, in general, fixed. The problem we consider
in this section is based on the remark that any field contains the neutral
elements for addition and multiplication and that in general those are denoted
by 0 and 1. This implies that any matrix with entries only in $\\{0,1\\}$ can
be the transfer matrix of a $q$-LMUC for any prime power $q$. It is natural to
look into the achievable rates regions across different fields for these types
of $q$-LMUCs.

It is well known that the size of the field plays an important role in
achieving the network capacity for multicast networks when the network code
design is part of the problem, see [2, 3]. We show that in sharp contrast with
this scenario, the characteristic of the underlying field plays an important
role in our model. Note that it is not the first time the characteristic of
the field has played an important role in network coding. In [4], the authors
show networks for which capacities are achievable in either even or odd
characteristic fields. It is worth repeating that our problem differs from the
one studied in [4] since the authors focus on constructing a network code,
whereas in our case, the network code is frozen.

We show that given the $q$-LMUC from Example 26, the achievable rates region
of the network over an odd characteristic field strictly contains the
achievable rates region over an even characteristic field.

######  Theorem 27.

Let $\mathcal{L}=(2,(1,2),(1,2),F)$ be the $q$-LMUC from Example 26. Recall
that

$F=\begin{pmatrix}1&1&1\\\ 1&1&0\\\ 1&0&1\end{pmatrix}.$

If $q$ is odd, then
$(1,1)\in\mathcal{R}_{1}(\mathcal{L})\subseteq\mathcal{R}(\mathcal{L})$. If
$q$ is even, then for any $m\geq 1$ and any
$(\alpha_{1},\alpha_{2})\in\mathcal{R}_{m}(\mathcal{L})$ we have

$2\alpha_{1}+\alpha_{2}\leq 2.$ (7)

In particular, $(1,1)\notin\mathcal{R}(\mathcal{L})$.

######  Remark 28.

Note that this result not only proves that the achievability regions of the
network when using even or odd characteristics are different, but it also
shows that the achievability region when communicating using an even
characteristic field is strictly contained in the one obtained using an odd
characteristic field. More specifically, an interested reader will be able to
see that, when using even characteristic fields, the rate $(1,1)$ not only is
not achievable but is bounded away, meaning that it cannot be achieved even
with infinitely many uses of the network.

###### Proof.

Observe that if $q$ is odd, then the 1-code
$C=\mathbb{F}_{q}\times\langle(1,-1)\rangle$ is unambiguous and therefore
$(1,1)\in\mathcal{R}_{1}(\mathcal{L})$, as claimed.

To prove the second part of the theorem, denote by $f_{i,j}$ the
multiplication by $F_{i,j}$ on the right, for $i,j\in\\{1,2\\}$. Let
$(\alpha_{1},\alpha_{2})\in\mathcal{R}_{m}(\mathcal{L})$ and let
$C=C_{1}\times C_{2}$ be an unambiguous $m$-code with
$\log_{q^{m}}(C_{1})=\alpha_{1}$ and $\log_{q^{m}}(C_{2})=\alpha_{2}$. Recall
that by Equation (2), we have that
$|\textnormal{Fan}_{1}(x,C)|=|\textnormal{IS}_{1}(C)|$ for all $x\in C_{1}$.
Since $C$ is unambiguous, we have
$|C_{1}|\cdot|\textnormal{IS}_{1}(C)|\leq|\mathbb{F}_{q^{m}}|=q^{m}$, or
equivalently

$|\textnormal{IS}_{1}(C)|\leq\frac{q^{m}}{|C_{1}|}.$ (8)

Recall that, by definition, $\textnormal{IS}_{1}(C)=f_{2,1}(C_{2})$. Observe
that for all $x\in\mathbb{F}_{q^{m}}$ we have $f_{2,1}^{-1}(x)=\\{(y,x-y)\mid
y\in\mathbb{F}_{q^{m}}\\}$ and therefore it holds that

$C_{2}\subseteq
f_{2,1}^{-1}(f_{2,1}(C_{2}))=f_{2,1}^{-1}(\textnormal{IS}_{1}(C))=\bigcup_{x\in\textnormal{IS}_{1}(C)}f_{2,1}^{-1}(x)=\bigcup_{x\in\textnormal{IS}_{1}(C)}\\{(y,x-y)\mid
y\in\mathbb{F}_{q^{m}}\\}.$

In particular, all the elements of $C_{2}$ are of the form $(y,x-y)$ for some
$x\in\textnormal{IS}_{1}(C)$ and $y\in\mathbb{F}_{q^{m}}$. Now fix any
$y\in\mathbb{F}_{q^{m}}$ and $x\in\textnormal{IS}_{1}(C)$ with $(y,x-y)\in
C_{2}$, and observe that

$\textnormal{Fan}_{2}((y,x-y),C)=f_{2,2}(y,x-y)+\textnormal{IS}_{2}(C)=(y,x-y)+\langle(1,1)\rangle.$
(9)

Here is where the characteristic of the field starts to play a crucial role.
If $q$ is even, then Equation (9) can be rewritten as

$\displaystyle\textnormal{Fan}_{2}((y,x+y),C)=(y,x+y)+\langle(1,1)\rangle=\\{(z,x+z)\mid
x\in\mathbb{F}_{q^{m}}\\}=f_{2,1}^{-1}(x).$

It follows that

$\bigcup_{(y,x+y)\in
C_{2}}\textnormal{Fan}_{2}((y,x+y),C)\subseteq\bigcup_{x\in\textnormal{IS}_{1}(C)}f_{2,1}^{-1}(x)=f_{2,1}^{-1}(\textnormal{IS}_{1}(C)).$
(10)

Again by Equation (2) and that $f_{1,2}$ is injective, we have
$|\textnormal{Fan}_{2}((y,x+y),C)|=|\textnormal{IS}_{2}(C)|=|C_{1}|$.
Combining this fact with Equation (10) and with the unambiguity of $C$ we
obtain

$|C_{2}|\leq\frac{|f_{2,1}^{-1}(\textnormal{IS}_{1}(C))|}{|\textnormal{Fan}_{2}((y,x+y),C)|}=\frac{|\textnormal{IS}_{1}(C)|\cdot|\mathbb{F}_{q^{m}}|}{|C_{1}|}\leq\left(\frac{q^{m}}{|C_{1}|}\right)^{2},$

where the last equality is a consequence of Equation (8). Taking the logarithm
with base $q^{m}$ of the inequality above, one gets $\alpha_{2}\leq
2(1-\alpha_{1})$, as desired. ∎

The following proposition shows that some of the rates satisfying Equation (7)
are achievable.

######  Proposition 29.

Let $\mathcal{L}=(2,(1,2),(1,2),\mathbb{F}_{2^{m}})$ be the $2^{m}$-LMUC from
Example 26. Then for any $n\leq m$ we have
$\left(\frac{n}{m},2\left(1-\frac{n}{m}\right)\right)\in\mathcal{R}(\mathcal{L})$.

###### Proof.

Let $\\{x_{1},\dots,x_{m}\\}$ be an ordered basis of $\mathbb{F}_{2^{m}}$ over
$\mathbb{F}_{2}$. Define $C_{1}=\langle
x_{1},\dots,x_{n}\rangle_{\mathbb{F}_{2}}$ and
$C_{2}=\langle(x_{i},0),(0,x_{i})\mid i=n+1,\dots,m\rangle_{\mathbb{F}_{2}}$.
We can compute the interference sets
$\textnormal{IS}_{1}(C)=f_{2,1}(C_{2})=\langle
x_{n+1},\dots,x_{m}\rangle_{\mathbb{F}_{2}}$ and
$\textnormal{IS}_{2}(C)=f_{1,2}(C_{1})=\langle(x_{1},x_{1}),\dots,(x_{n},x_{n})\rangle_{\mathbb{F}_{2}}$.
Thus $C_{1}\times C_{2}$ is unambiguous because
$C_{1}\cap\textnormal{IS}_{1}(C)=C_{2}\cap\textnormal{IS}_{2}(C)=\\{0\\}$. ∎

##  6 Conclusions

We considered the multiple unicast problem over a coded network where the
network code is linear over a finite field and fixed. We introduced a
framework to define and investigate the achievable rate region in this
context. We established an outer bound on the achievable rate region and
provided examples where the outer bound is sharp. Finally, we illustrated the
role played by the field characteristic in this problem, which is different
than what is generally observed in the context of linear network coding.

## References

  * [1] R. Ahlswede, N. Cai, S.-Y. R. Li, , and R. W. Yeung, “Network information flow,” _IEEE Trans. Info. Theory_ , vol. 46, no. 4, pp. 1204–1216, Jul. 2000.
  * [2] S.-Y. R. Li, , R. W. Yeung, and N. Cai, “Linear network coding,” _IEEE Trans. Info. Theory_ , vol. 49, no. 2, pp. 371–381, Feb. 2003.
  * [3] R. Koetter and M. Médard, “An algebraic approach to network coding,” _IEEE Trans. Info. Theory_ , vol. 11, no. 5, pp. 782–795, Oct. 2003.
  * [4] R. Dougherty, C. Freiling, and K. Zeger, “Insufficiency of linear coding in network information flow,” _IEEE Trans. Info. Theory_ , vol. 51, no. 8, pp. 2745–2759, Aug. 2005.
  * [5] C. Wang, T. Gou, and S. A. Jafar, “Multiple unicast capacity of 2-source 2-sink networks,” in _Proc. IEEE Global Commun. Conf. (GLOBECOM)_ , Houston, TX, USA, Dec. 2011, pp. 1–5.
  * [6] A. Das, S. Vishwanath, S. Jafar, and A. Markopoulou, “Network coding for multiple unicasts: An interference alignment approach,” in _Proc. IEEE Int. Symp. Info. Theory (ISIT)_ , Austin, TX, USA, Jun. 2010, pp. 1878–1882.
  * [7] A. Ramakrishnan, A. Das, H. Malek, A. Markopoulou, S. Jafar, and S. Vishwanath, “Network coding for three unicast sessions: Interference alignment approaches,” in _Proc. 48th Ann. Allerton Conf. Commun., Control, Comp._ , Monticello, IL, USA, Sep. 2010, pp. 1054–1061.
  * [8] A. Ravagnani and F. R. Kschischang, “Adversarial network coding,” _IEEE Trans. Info. Theory_ , vol. 63, no. 1, pp. 198–219, Jan. 2019.
  * [9] V. R. Cadambe and S. A. Jafar, “Interference alignment and the degrees of freedom of the ${K}$-user interference channel,” _IEEE Trans. Info. Theory_ , vol. 54, no. 8, pp. 3425–3441, Aug. 2008.
  * [10] N. Zhao, F. R. Yu, M. Jin, Q. Yan, and V. C. M. Leung, “Interference alignment and its applications: A survey, research issues, and challenges,” _IEEE Comm. Surv. Tut._ , vol. 18, no. 3, pp. 1779–1803, Third Quarter 2016.
  * [11] S. R. Krishnamurthy and S. A. Jafar, “Precoding based network alignment and the capacity of a finite field X channel,” in _Proc. IEEE Int. Symp. Info. Theory (ISIT)_ , Istanbul, Turkey, Jul. 2013, pp. 2701–2705.
  * [12] ——, “On the capacity of the finite field counterparts of wireless interference networks,” _IEEE Trans. Info. Theory_ , vol. 60, no. 7, pp. 4101–4124, Jul. 2014.
  * [13] S.-N. Hong and G. Caire, “On interference networks over finite fields,” _IEEE Trans. Info. Theory_ , vol. 60, no. 8, pp. 4902–4921, Aug. 2014.