text:
\begin{document}

\IEEEoverridecommandlockouts
\title{On the Gap between Scalar and Vector Solutions of Generalized Combination Networks}

\author{
    Hedongliang Liu,~\IEEEmembership{Student Member,~IEEE},
    Hengjia Wei,
    Sven Puchinger,~\IEEEmembership{Member,~IEEE}\\
    Antonia Wachter-Zeh,~\IEEEmembership{Senior Member,~IEEE},
    Moshe Schwartz,~\IEEEmembership{Senior Member,~IEEE}
    \thanks{This research was supported in part by a German Israeli Project Cooperation (DIP) grant under grant no.~PE2398/1-1 and KR3517/9-1, and by the European Union's Horizon 2020 research and innovation programme under the Marie Sk\l{}odowska-Curie grant agreement no.~713683. The material in this paper was partly presented at the 2020 International Symposium on Information Theory (ISIT).}
    \thanks{Hedongliang Liu, Sven Puchinger, and Antonia Wachter-Zeh are with the Department of Electrical and Computer Engineering, Technical University of Munich, Munich 80333, Germany (e-mail: lia.liu@tum.de; sven.puchinger@tum.de; antonia.wachter-zeh@tum.de). This work was partly done while Sven Puchinger was with the Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark.}
    \thanks{Hengjia Wei and Moshe Schwartz is with the School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer Sheva 8410501, Israel (e-mail: hjwei05@gmail.com; schwartz@ee.bgu.ac.il)}

}

\maketitle
\begin{abstract}
We study scalar-linear and vector-linear solutions of the generalized combination network. We derive new upper and lower bounds on the maximum number of nodes in the middle layer, depending on the network parameters and the alphabet size. These bounds improve and extend the parameter range of known bounds. Using these new bounds we present a lower bound and an upper bound on the gap in the alphabet size between optimal scalar-linear and optimal vector-linear network coding solutions. For a fixed network structure, while varying the number of middle-layer nodes $r$, the asymptotic behavior of the upper and lower bounds shows that the gap is in $\Theta(\log(r))$.
\end{abstract}

\begin{IEEEkeywords}
Gap Size, Generalized Combination Network, Network Coding, Vector Network Coding
\end{IEEEkeywords}

\section{Introduction}
\label{sec:intro}
\IEEEPARstart{I}{n} multicast networks that apply routing, a source node multicasts information to other nodes in the network in a multihop fashion, where every node can pass on their received data. \emph{Network coding} has been attracting increasing attention since the seminal papers~\cite{ACLY00,LYCfeb2003} {which showed that the throughput can be increased significantly by not just forwarding packets but also performing linear combinations of them}. Several follow-up works~\cite{NYoct2004,HJsep2009,MLLfeb2012,EGLapr2014} also showed that network coding outperforms routing in terms of delay, throughput and reliability for specific networks.

In network coding, each node is allowed to encode its received data before passing it on. We formulate the \emph{network coding problem} as follows: for each node in the network, find a function of its incoming messages to transmit on its outgoing links, such that each receiver can recover all (or a predefined subset of all) the messages. We say a network is \emph{solvable} if such a function exists.
The encoding at relay nodes incurs delay and memory cost in the network. One approach in minimizing these costs, is reducing the alphabet size of the coding operations, thus resulting in less complexity in practical implementations of network coding~\cite{LSB2006,LS2009,GSRMsep2019}.

\subsection{Previous Work}
A considerable number of studies have been conducted on different types of network coding:
such as linear network coding~\cite{LYCfeb2003,KM03} and non-linear network coding~\cite{LLjan2004}, deterministic network coding~\cite{XiaMedAul07} and random linear network coding~\cite{KK08,SKK08}. In this paper, we only focus on linear network coding and discuss the performance of scalar linear network coding and vector linear network coding.

  In linear network coding, each linear function for a receiver consists of coding coefficients for incoming messages. If the messages are scalars in $\Fq$ and the coding coefficients are vectors over $\Fq$, the solution is called a scalar linear solution. If the messages are vectors in $\Fq^t$, and the coding coefficients are matrices over $\Fq$, it is called a vector linear solution. Vector network coding was mentioned in~\cite{CDFZ06} as fractional network coding and extended to vector network coding in~\cite{EFfeb2011}.

  Although a scalar solution over $\F_{q^t}$ can be translated to a vector solution composed of $t\times t$ matrices over $\Fq$, directly designing codes for vector network coding still has advantages: there exist $q^{t^2}$ many $t\times t$ matrices over $\Fq$, while a scalar solution only employs $q^t$ of them. Therefore, vector network coding offers a larger space of choices for optimizing the performance of a network. However, not every solvable network has a vector solution~\cite{DFZaug2005}. The hardness of finding a capacity-achieving vector solution for a general instance of the network coding problem was proved in~\cite{LSfeb2011}. In~\cite{DRsep2016} it was proved that {for a class of non-multicast networks, a vector linear solution of dimension $t$ exists but no vector solution over any finite field exists if the message dimension is less than $t$.}
  {The existence of explicit networks where scalar solutions still outperform binary vector solutions was shown in~\cite{SYL+dec2016}.}
{Nevertheless, a {multicast} network was constructed in~\cite{SYL+dec2016} whose minimal alphabet for a scalar linear solution is strictly larger than the minimal alphabet for a vector linear solution.}
The gap in the minimum alphabet size between a scalar solution and a vector solution was shown to be positive in generalized combination networks~\cite{EW18} and minimal multicast networks~\cite{CCESW20}. Several algorithms for deterministic networks via vector coding were presented in~\cite{EFjan2010,EFjun2010,EFfeb2011,EW18}.

  Solving network coding problems also motivates research in other topics such as new metrics for network codes~\cite{EZjul2019}, subspace codes design~\cite{GYmay2010,ESfeb2013,EKOOfeb2020}, networks over the erasure channel~\cite{GBFTjul2011} and distributed storage~\cite{DGW+sep2010,DRWS2011}.
More long-standing open problems can be found in~\cite{FS2016}.

\subsection{Our Goals and Contributions}
In this paper, we only consider linear solutions of {multicast} networks.
Denote by $\Fq$ a finite field of size $q$. Bold lowercase letters denote vectors and bold capital letters denote matrices.

The scalar and vector solutions stand for scalar linear and vector linear solutions throughout the rest of the paper.
We call a scalar solution over $\Fq$ for a network, a $(q,1)$-{linear solution}, and we call a {vector solution} of length $t$ over $\Fq$, a $(q,t)$-linear solution.

The main object we study in this paper is the class of \emph{generalized combination networks}. An $(\eps,\ell)-\cN_{h,r,\alpha\ell+\eps}$ generalized combination network is illustrated in Figure~\ref{fig:Network} (see also~\cite{EW18}).
\begin{figure}[t!]
  \centering
  \input{GeneralizedNetwork.tex}
  \caption{Illustration of $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ networks}
  \label{fig:Network}
\end{figure}
The network has three layers. The first layer consists of a source with $h$ source messages. The source transmits $h$ messages to $r$ middle nodes via $\ell$ parallel links (solid lines) between itself and each middle node. Any $\alpha$ middle nodes in the second layer are connected to a unique receiver (again, by $\ell$ parallel links each). Each receiver is also connected to the source via $\eps$ direct links (dashed lines).
It was shown in~\cite[Thm.~8]{EW18} that the $(\eps,\ell)-\cN_{h,r,\alpha\ell+\eps}$ network has a trivial solution if $h\leq\ell+\eps$ and it has no solution if $h>\alpha\ell+\eps$. In this paper we focus on non-trivially solvable networks, so it is assumed $\ell+\eps< h \leq \alpha\ell+\eps$ throughout the paper.

The goal of this paper is to investigate {the maximum number of middle-layer nodes, denoted by $r_{\max}$, such that the network with fixed $h,\alpha,\ell,\eps$ has a $(q,t)$-linear solution. This implies bounds on} the gap between the minimum required alphabet size for scalar and vector solutions of generalized combination networks.
In order to derive the gap size, a metric to measure the improvement has to be specified.
We follow the notations from~\cite{CCESW20} to distinguish between optimal scalar and vector solutions. Given a generalized combination network $\cN$, let $$q_s(\cN):=\min\set*{q ; \cN\textrm{ has a } (q,1)\textrm{-linear solution}}.$$
The $(q_s(\cN),1)$-linear solution is said to be \emph{scalar-optimal}.
Similarly, let $$q_v(\cN):=\min\set*{q^t ; \cN\textrm{ has a } (q,t)\textrm{-linear solution}}.$$
Note that $q_v(\cN)$ is defined by the size of the vector space, rather than the field size.
For $q^t = q_v(\cN)$, a $(q,t)$-linear solution is called \emph{vector-optimal}.
By definition,
\[
q_s(\cN)\geq q_v(\cN).
\]
We define the \emph{gap} as
\[ \gap (\cN):= \log_2 (q_s(\cN)) -\log_2(q_v(\cN)),\]
which intuitively measures the advantage of vector network coding by the amount of extra bits per transmitted symbol we have to pay for an optimal scalar-linear solution compared to an optimal vector-linear solution. {We note that although the definition of the gap differs from the definition of gap in~\cite{CCESW20}, it has been implicitly used in~\cite{EW18}, and mentioned as \emph{information gap} in~\cite{CCESW20}.}

Our main contributions are the following:
\begin{itemize}

    \item two upper bounds on $r_{\max}$, the maximal number of nodes in the middle layer of a generalized combination network {such that the network has a $(q,t)$-linear solution} (Corollary~\ref{cor:imupperbound-N}, valid only for $h\geq 2\ell+\eps$, and Corollary~\ref{cor:imupperbound-2-Network} for $\alpha=2$),
    \item two lower bounds on $r_{\max}$ (Theorem~\ref{thm:LLL_bound} and Corollary~\ref{cor:EK19_lb} for $h\leq 2\ell+\eps$),
    \item an upper bound on the gap in the minimum alphabet size for any fixed generalized combination network structure (Theorem~\ref{thm:gap_ub}),
    \item a lower bound on the gap (Theorem~\ref{thm:gap_lb}) .

\end{itemize}

Our new upper bound on $r_{\max}$ is better than a previous bound from~\cite{EZjul2019} (recalled in Corollary~\ref{cor:EZ19_vector}) for $h\geq 2\ell+\eps$, and the lower bounds outperform previous ones for the whole parameter range of non-trivially solvable generalized combination networks, and they agree with our upper bound up to a small constant factor, for $h\leq 2\ell$ or $h\geq 2\ell,\alpha=2$.

To the best of our knowledge, our upper and lower bounds on the gap are the first such bounds considering fixed network parameters. These bounds are valid for all generalized combination networks with $\eps\neq 0$. The asymptotic behavior of the upper and lower bound shows that $\gap(\cN) = \Theta\parenv*{\log(r)}$.

\subsection{Paper Organization}
The rest of this paper is organized as follows.
In Section~\ref{sec:ub_rs}, we present two new upper bounds on the maximum number of middle-layer nodes, and in Section~\ref{sec:lb_rv} we give two new lower bounds on it. In Section~\ref{sec:bound_gap} we show the gap between the field sizes of scalar-linear and vector-linear solutions. In Section~\ref{sec:discussion}, we compare our upper and lower bounds on the maximum number of nodes in the middle layer with the other known bounds.

\section{Upper Bounds on The Maximum Number of Middle Layer Nodes}
\label{sec:ub_rs}

In this section we fix the network parameters $\alpha,\ell,\eps, h$ and we bound from above the {maximum} number of nodes in the middle layer {such that the network has a $(q,t)$-linear solution}. The main result is given in Corollary~\ref{cor:imupperbound-N} and Corollary~\ref{cor:imupperbound-2-Network}.

We denote by $\mathcal{G}(n,k)$ the Grassmannian of dimension $k$, which is a set of all $k$-dimensional subspaces of $\mathbb{F}_q^n$. The cardinality of $\mathcal{G}(n,k)$ is the well-known $q$-binomial coefficient (a.k.a.~the Gaussian coefficient):
\begin{equation*}
  |\mathcal{G}(n,k)|=\quadbinom{n}{k}_q := \prod\limits_{i=0}^{k-1} \frac{q^n-q^i}{q^k-q^i}=\prod\limits_{i=0}^{k-1} \frac{q^{n-i}-1}{q^{k-i}-1}.
\end{equation*}
A good approximation of the $q$-binomial coefficient can be found in~\cite[Lemma 4]{KK08}:
\begin{equation}
    \label{eq:gauss}
q^{k(n-k)}\leq \quadbinom{n}{k}_q < \gamma \cdot q^{k(n-k)},
\end{equation}
where $\gamma\approx 3.48$.

\begin{lemma}\label{lm-full-t2}
Let $\alpha\geq 2$, $h,\ell,t\geq 1$, $\eps\geq 0$, $h-\eps \geq 2 \ell$, and let $\cT$ be a collection of subspaces  of $\F_q^{(h-\eps) t}$ such that
\begin{enumerate}
\item[(i)] each subspace has dimension at most $\ell t$; and
\item[(ii)] any subset of $\alpha$ subspaces spans $\F_q^{(h-\eps)t}$.
\end{enumerate}
Then  we have $\alpha \ell  \geq h-\eps$ and
$$|\cT| \leq \parenv*{\floor*{ \frac{h-\eps}{\ell} }-2} +\parenv*{\alpha- \floor*{ \frac{h-\eps}{\ell} }+1} \sbinom{\ell t+1}{1}_q.$$
\end{lemma}

\begin{IEEEproof}
Take arbitrarily $\lfloor \frac{h-\eps}{\ell} \rfloor-2$ subspaces  from $\cT$ and take arbitrarily a subspace  $W$ of dimension $(h-\eps)t-\ell t-1$ which contains all these $\lfloor \frac{h-\eps}{\ell} \rfloor-2$  subspaces. Then
for any subspace $T\in \cT$, there is a hyperplane of $\F_q^{(h-\eps)t}$ containing both $W$ and $T$.
Note that there are $\sbinom{\ell t+1}{\ell t}=\sbinom{\ell t +1}{1}$ hyperplanes containing $W$ and each of them contains at most $\alpha-1$ subspaces from $\cT$. Thus
\begin{align*}
  |\cT| \leq  &\parenv*{\floor*{ \frac{h-\eps}{\ell} }-2} \\
  &+ \sbinom{\ell t+1}{\ell t}_q\parenv*{\alpha-1 - \parenv*{\floor*{ \frac{h-\eps}{\ell} }-2}} \\
  = & \parenv*{\floor*{ \frac{h-\eps}{\ell} }-2} +\parenv*{\alpha- \floor*{ \frac{h-\eps}{\ell} }+1}  \sbinom{\ell t+1}{1}_q.
\end{align*}
\end{IEEEproof}

\begin{theorem}\label{thm-upbound-v2}
Let $\alpha\geq 2$, $h,\ell,t\geq 1$, $\eps\geq 0$, $h-\eps\geq 2\ell$, and let $\cS$ be a collection of  subspaces of $\F_q^{ht}$ such that
\begin{enumerate}
\item[(i)] each subspace has dimension at most $\ell t$; and
\item[(ii)] any subset of $\alpha$ subspaces spans a subspace of dimension at least $(h-\eps)t$.
\end{enumerate}
Then  we have $\alpha \ell  \geq h-\eps$ and
\begin{align*}|\cS| \leq &\sbinom{(\eps+\ell)t}{\eps t}_q \parenv*{ \parenv*{\alpha- \floor*{ \frac{h-\eps}{\ell} }+1}  \frac{q^{\ell t+1}-1}{q-1}-1}\\
                         &+ \floor*{\frac{h-\eps}{\ell}}-1\\
\overset{(*)}{<}& \gamma\parenv*{\alpha- \floor*{ \frac{h-\eps}{\ell} }+1} q^{\ell t (\eps t+1)} {+ \floor*{ \frac{h-\eps}{\ell}}-1}.
\end{align*}
\end{theorem}

\begin{IEEEproof}
Take arbitrarily $\floor*{\frac{h-\eps}{\ell}}-1$ subspaces from $\cS$ and a subspace $W \subset \F_q^{ht}$ of dimension $(h-\eps)t-\ell t$ such that $W$ contains all these  $\floor*{\frac{h-\eps}{\ell}}-1$ subspaces.  Then for any subspace $S \in \cS$ there is a subspace of dimension $(h-\eps)t$ containing both $W$ and $S$.

Let $m:= \sbinom{(\eps+\ell )t}{\eps t}_q$. Then there are $m$ subspaces of dimension $(h-\eps)t$ containing $W$, say $W_1, W_2, \ldots, W_m$. Note that every $\alpha$ subspaces in $W_i \cap \cS$ span the subspace $W_i$. According to Lemma~\ref{lm-full-t2}, we have
\begin{align*}
    |W_i \cap \cS| &\leq \parenv*{\floor*{ \frac{h-\eps}{\ell} }-2}
    +\parenv*{\alpha- \floor*{ \frac{h-\eps}{\ell} }+1}  \sbinom{\ell t +1}{1}_q.
\end{align*}
Hence,
\begin{align*}
|\cS|  \leq& \sum_{i=1}^{m}\parenv*{|W_i\cap \cS|- \parenv*{\floor*{ \frac{h-\eps}{\ell}}-1  }} + \floor*{ \frac{h-\eps}{\ell}}-1 \\
  \leq & \sbinom{(\eps+\ell)t}{\eps t}_q \parenv*{ \parenv*{\alpha- \floor*{ \frac{h-\eps}{\ell} }+1}  \frac{q^{\ell t+1}-1}{q-1}  -1}\\
         &+ \floor*{ \frac{h-\eps}{\ell}}-1.
 \end{align*}
The inequality $(*)$ is derived by \eqref{eq:gauss}.
\end{IEEEproof}
The following corollary rephrases Theorem~\ref{thm-upbound-v2} with network parameters.

\begin{corollary}\label{cor:imupperbound-N}
Let $\alpha\geq 2$, $h,\ell,t\geq 1$, $\eps\geq 0$, and $h-\eps \geq 2\ell$. If $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ has a $(q,t)$-linear solution then
\[
r \leq r_{\max}
< \gamma\theta q^{\ell t (\eps t+1)} +\alpha-\theta,
\]
where $\theta:= \alpha- \floor*{ \frac{h-\eps}{\ell} }+1$ and $\gamma\approx 3.48$.
\end{corollary}
\begin{IEEEproof}
If a $(q,t)$-linear solution exists, then each of the $r$ nodes in the middle layer gets a subspace of dimension $\ell t$ of the source messages space. Since all receivers are able to recover the entire source message space, every $\alpha$-subset of the middle nodes span a subspace of dimension at least $(h-\eps)t$. We then use Theorem~\ref{thm-upbound-v2}.
\end{IEEEproof}

Theorem~\ref{thm-upbound-v2} and Corollary~\ref{cor:imupperbound-N} are valid for all $\alpha\geq 2$. However, we derive a better upper bound for $\alpha = 2$, as shown in the following theorem.

\begin{theorem}\label{thm:imupbound-2}
Let $\alpha=2,h,\ell,t\geq 1$, $\eps\geq 0$, and let $\cS$ be a collection of  subspaces of $\F_q^{ht}$ such that
\begin{enumerate}
\item[(i)] each subspace has dimension at most $\ell t$; and
\item[(ii)] the sum of any two subspaces has dimension at least $(h-\eps)t$.
\end{enumerate}
Then we have
\[|\cS|  \leq \frac{\sbinom{ht}{2\ell t - (h-\eps)t+1}_q}{ \sbinom{\ell t}{2\ell t - (h-\eps)t+1}_q}
 < \gamma \cdot q^{(h-\ell)(2\ell+\eps-h)t^2+(h-\ell)t}.
\]
\end{theorem}

\begin{IEEEproof}
We may assume that each subspace has dimension  $\ell t$. Since the sum of every two subspaces has dimension at least $(h-\eps)t$, then their intersection has dimension at most $2\ell t - (h-\eps)t$. It follows that any subspace of dimension $2\ell t - (h-\eps)t+1$ is contained in at most one subspace of $\cS$. Note that there are $\sbinom{ht}{2\ell t - (h-\eps)t+1}_q$ subspaces of dimension  $2\ell t - (h-\eps)t+1$  and each   subspace of dimension $\ell t$ contains $\sbinom{\ell t}{2\ell t - (h-\eps)t+1}_q$ such spaces.  We have that
$$|\cS| \leq \sbinom{ht}{2\ell t - (h-\eps)t+1}_q \Big/ \sbinom{\ell t}{2\ell t - (h-\eps)t+1}_q.$$
\end{IEEEproof}
The following corollary rephrases Theorem~\ref{thm:imupbound-2} with network parameters.

\begin{corollary}\label{cor:imupperbound-2-Network}
Let $\alpha= 2$, $h,\ell,t\geq 1$, $\eps\geq 0$. If $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ has a $(q,t)$-linear solution then
\[
r \leq r_{\max}
< \gamma \cdot q^{(h-\ell)(2\ell+\eps-h)t^2+(h-\ell)t},
\]
where $\gamma\approx 3.48$.
\end{corollary}
\begin{IEEEproof}
If a $(q,t)$-linear solution exists, then each of the $r$ nodes in the middle layer gets a subspace of dimension $\ell t$ of the source messages space. Since all receivers are able to recover the entire source message space, any two subset of the middle nodes span a subspace of dimension at least $(h-\eps)t$. We then use Theorem~\ref{thm:imupbound-2}.
\end{IEEEproof}

\section{Lower Bounds on the Maximum Number of Middle Layer Nodes}

\label{sec:lb_rv}

We now turn to study a lower bound on $r_{\max}$ {with the parameters $\alpha,\ell,\eps,h$ being fixed}. The main results are summarized in Theorem~\ref{thm:LLL_bound} and Corollary~\ref{cor:EK19_lb}.
In the following, we first give the condition on the coding coefficients under which a linear solution exists.

Let $\x_1,\dots,\x_h\in\mathbb{F}^t_{q}$ denote the $h$ source messages and $\y_1,\dots,\y_N\in\mathbb{F}^{(\eps+\alpha\ell)t}_q$ the messages received by each receiver\footnote{The vector $\y_i$ is the concatenation of all the messages received by the $i$th receiver node.}. Since each middle-layer node receives $\ell$ incoming edges, and has $\ell$ outgoing edges directed at a given receiver, we may assume without loss of generality that this node just forwards its incoming messages. Let us denote the \emph{coding coefficients} used by the source node for the messages transmitted to the $r$ middle nodes by $\A_1,\dots,\A_r \in \Fq^{\ell t \times ht}$. Additionally, we denote the coding coefficients used by the source node for the messages transmitted directly to the receivers by $\B_1,\dots,\B_N\in\F_q^{\eps t\times ht}$.

Each receiver has to solve the following linear system of equations (LSE):
\begin{equation*}
\y_i
=\begin{pmatrix}
  \A_{i_1}\\ \vdots\\ \A_{i_\alpha}\\ \B_i
\end{pmatrix}_{(\eps+\alpha\ell)t\times ht}
\cdot
\begin{pmatrix}
\x_1\\
\vdots\\
\x_{h}
\end{pmatrix}_{ht\times 1},\ \forall i =1,\dots,N=\binom{r}{\alpha},
\end{equation*}
where $\{\A_{i_1},\dots, \A_{i_\alpha}\}\subset \{\A_1,\dots,\A_r \}$.

Any receiver can recover the $h$ source messages $\x_1,\dots,\x_h$ if and only if
\begin{equation}\label{eq:NC_sol}
\rank
\begin{pmatrix}
  \A_{i_1}\\ \vdots\\ \A_{i_\alpha}
\end{pmatrix}_{\alpha \ell t\times ht}
\geq (h-\eps)t,\ \forall i =1,\dots,N.
\end{equation}
Here the {solution} of the $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ network is a set of the coding coefficients $\{\A_1,\dots,\A_r \}$ s.t.~\eqref{eq:NC_sol} holds (where $\B_1,\dots,\B_N$ may be easily determined from the solution).

\subsection{A Lower Bound by the Lov\'asz-Local Lemma}
\begin{lemma}[The Lov\'asz-Local-Lemma~{\cite[Ch.~5]{TheProbMethod}}, \cite{LLLbeck1991}]\label{lem:LLL}
Let $\mathcal{E}_1, \mathcal{E}_2, \hdots,\mathcal{E}_k$ be a sequence of events. Each event occurs with probability at most $p$ and each event is independent of all the other events except for at most $d$ of them.
If $epd\leq 1$ {(where $e\approx 2.71828$ is Euler's number)}, then there is a non-zero probability that none of the events occurs.
\end{lemma}

We choose the matrices $\A_1,\dots,\A_r \in \Fq^{\ell t \times ht}$ independently and uniformly at random.
For $1 \leq i_1 <  \dots<i_\alpha \leq r$, we define the event
\begin{align*}
\mathcal{E}_{i_1,\dots,i_\alpha} := \set*{ (\A_{i_1},\dots, \A_{i_\alpha}) ; \rank \begin{pmatrix}
\A_{i_1} \\ \vdots \\ \A_{i_\alpha}
\end{pmatrix} < (h-\eps)t }.
\end{align*}

Let $p=\Pr(\mathcal{E}_{i_1,\dots,i_\alpha})$ and denote by $d$ the number of other events $\mathcal{E}_{i'_1,\dots,i'_\alpha}$ that are dependent on $\mathcal{E}_{i_1,\dots,i_\alpha}$.

\begin{lemma}\label{lem:upper_bound_on_p}
Let $\alpha\geq 2$, $h,\ell,t\geq 1$, $\eps\geq 0$. Fixing $1 \leq i_1 < \dots < i_\alpha \leq r$, we have
\begin{align*}
\Pr(\mathcal{E}_{i_1,\dots,i_{\alpha}}) \leq 2\gamma \cdot q^{(h-\alpha\ell-\eps)\eps t^2+(h-\alpha\ell-2\eps)t-1},
\end{align*}
where $\gamma\approx3.48$.
\end{lemma}
\begin{IEEEproof}
The number of matrices $\A\in\mathbb{F}_q^{m\times n}$ of rank $s$ is
\begin{equation}
  M(m,n,s):=\prod\limits^{s-1}_{j=0}\frac{(q^m-q^j)(q^n-q^j)}{q^s-q^j}
  \leq \gamma\cdot q^{(m+n)s-s^2} \label{eq:number_matrices_upper_bound}.
\end{equation}
Then,
\begin{align}
  \Pr(\mathcal{E}_{i_1,\dots,i_{\alpha}}) &=\frac{\sum\limits^{(h-\eps)t-1}_{i=0}M(\alpha \ell t,ht,i)}{q^{\alpha \ell h t^2}}\nonumber\\
    & \leq \frac{\sum\limits^{(h-\eps)t-1}_{i=0}\gamma \cdot q^{(h+\alpha\ell)ti-i^2}}{q^{\alpha\ell h t^2}}\label{eq:NM_upper_bound} \\
    & \leq \gamma \cdot \frac{q}{q-1}\cdot q^{\max_i\{(h+\alpha\ell)ti-i^2\} - \alpha\ell h t^2} \label{eq:summation_upper_bound}\\
    & = \gamma \cdot \frac{q}{q-1}\cdot q^{(h+\alpha\ell)ti-i^2|_{i=(h-\eps)t-1} - \alpha\ell h t^2} \label{eq:quadratic_maximum}\\
    & \leq \gamma\cdot 2\cdot q^{(h-\alpha\ell-\eps)\eps t^2+(h-\alpha\ell-2\eps)t-1} \nonumber
\end{align}
where (\ref{eq:NM_upper_bound}) holds due to~\eqref{eq:number_matrices_upper_bound}, (\ref{eq:summation_upper_bound}) follows from a geometric sum, and \eqref{eq:quadratic_maximum} follows by maximizing $(h+\alpha\ell)ti-i^2$.
\end{IEEEproof}

\begin{lemma}\label{lem:upper_bound_on_d}
Let $\alpha\geq 2$, $h,\ell,t\geq 1$, $\eps\geq 0$. Fixing $1 \leq i_1 <\dots < i_\alpha \leq r$, the event $\mathcal{E}_{i_1,\dots,i_\alpha}$ is statistically independent of all the other events $\mathcal{E}_{i_1',\dots,i_\alpha'}$ ($1 \leq i_1' < \dots < i_\alpha' \leq r$), except for at most $\alpha\binom{r-1}{\alpha-1}$
of them.
\end{lemma}

\begin{IEEEproof}
For $1 \leq i_1 < \dots < i_\alpha \leq r$ and $1 \leq i_1' <\dots < i_\alpha' \leq r$, the events $\mathcal{E}_{i_1,\dots,i_\alpha}$ and $\mathcal{E}_{i_1',\dots,i_\alpha'}$ are statistically independent if and only if $\{i_1,\dots,i_\alpha\} \cap \{i_1',\dots,i_\alpha'\} = \emptyset$. Thus, having chosen $1 \leq i_1 < \dots < i_\alpha \leq r$, there are at most
$\alpha\binom{r-1}{\alpha-1}$
ways of choosing an independent event.
\end{IEEEproof}
\begin{remark}
Lemma~\ref{lem:upper_bound_on_d} is a union-bound argument on the number of dependent events. The exact number is $\binom{r}{\alpha}-\binom{r-\alpha}{\alpha}$.
 However the exact expression makes it harder to resolve everything for $r$ later so we use the bound here.
\end{remark}
\begin{theorem}\label{thm:LLL_bound}
  Let $\alpha\geq 2$, $\eps \geq 0$, $\ell,t \geq 1$, and $1\leq h \leq \alpha\ell+\eps$ be fixed integers.
  If
  \begin{equation}\label{eq:r_LLL_lb}
      r \leq \beta \cdot
      q^{\frac{f(t)}{\alpha-1}}
  \end{equation}
where $\beta := \parenv*{\frac{(\alpha-1)!}{2e\gamma\alpha}}^{\frac{1}{\alpha-1}}, \gamma\approx3.48$, {$e\approx 2.71828$ is Euler's number,} and $f(t):=(\alpha\ell+\eps-h)\eps t^2+(\alpha\ell+2\eps-h)t +{1}$, then $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ has a $(q,t)$-linear solution.

Namely, for an $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ that has a $(q,t)$-linear solution, the maximum number of middle nodes satisfies
\[
      r_{\max}\geq \beta \cdot q^{\frac{f(t)}{\alpha-1}}.
\]
\end{theorem}

\begin{IEEEproof}
By the Lov\'asz Local Lemma, it suffices to show that $epd\leq 1$. Noting that $d\leq \alpha\binom{r-1}{\alpha-1}\leq \alpha\cdot \frac{(r-1)^{\alpha-1}}{(\alpha-1)!}$, we shall require
\begin{align*}
    e\cdot2\gamma q^{(h-\alpha\ell-\eps)\eps t^2+(h-\alpha\ell-2\eps)t-1}
    \cdot \alpha\frac{(r-1)^{\alpha-1}}{(\alpha-1)!}\leq 1.
\end{align*}

Namely, if
$ r \leq {\beta}\cdot
q^{\frac{(\alpha\ell+\eps-h)\eps}{\alpha-1}t^2+\frac{\alpha\ell+2\eps-h}{\alpha-1}t+\frac{1}{\alpha-1}}+1$, then $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ has a $(q,t)$-linear solution.
We omit the plus one for simplicity.
\end{IEEEproof}
\begin{remark}
 For any $\alpha\geq 7$,
 \eqref{eq:r_LLL_lb} can be simplified to
 \begin{equation*}
    r \leq
    q^{\frac{f(t)}{\alpha-1}},
 \end{equation*}
 since the prefactor $\beta>1$ for all $\alpha\geq 7$.
\end{remark}

\begin{remark}
 For $t\geq 3$, $\alpha \geq 5$ or $q\geq 4$, it can be seen from numerical analysis that
 $\beta \cdot q^{\frac{\alpha\ell+2\eps-h}{\alpha-1}t +\frac{1}{\alpha-1}} \geq 1$. Thus, \eqref{eq:r_LLL_lb} can be simplified to a looser upper bound
 \[
    r \leq q^{\frac{(\alpha\ell+\eps-h)\eps}{\alpha-1}t^2}.
 \]
 However, omitting the term $\beta \cdot q^{\frac{\alpha\ell+2\eps-h}{\alpha-1}t+\frac{1}{\alpha-1}} $ will cause a loss in estimating the maximum achievable number of middle nodes. Nevertheless, the loss is negligible when $t\to \infty$.
\end{remark}

\subsection{A Lower Bound by $\alpha$-Covering Grassmannian Codes}
\begin{definition}[Covering Grassmannian Codes~\cite{EZjul2019}]
  An $\alpha$-$(n,k,\delta)_q^c$ \emph{covering Grassmannian code} $\mathbb{C}$ is a subset of $\mathcal{G}(n,k)$ such that each subset with $\alpha$ codewords of $\mathbb{C}$ spans a subspace whose dimension is at least $\delta+k$ in $\mathbb{F}_q^n$. Additionally, let ${\cal B}_q(n,k,\delta;\alpha)$ denote the maximum possible size of an $\alpha$-$(n,k,\delta)_q^c$ covering Grassmannian code.
\end{definition}
The following theorem from~\cite{EZjul2019} shows the connection between covering Grassmannian codes and linear network coding solutions.
\begin{theorem}[{\cite[Thm.~4]{EZjul2019}}]\label{thm:cover_scalar_sol}
  The $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ network is solvable with a $(q,t)$-linear solution if and only if there exists an $\alpha$-$(ht,\ell t,ht-\ell t-\eps t)_{q}^c$ code with $r$ codewords.
\end{theorem}

{
For two matrices $A,B\in\F_q^{k\times\ell}$, the rank distance between them is defined to be $d(A,B):=\rank(A-B)$. A linear subspace $\mathbb{C}\subseteq \F_q^{k\times\ell}$ is a linear rank-metric code with parameters $[k\times\ell,K,d]$ if it has dimension $K$, and for any two distinct matrices $C_1,C_2\in\mathbb{C}$, $d(C_1,C_2)\geq d$. It was proved in~\cite{Del78} that
\[ K\leq \min\{ k(\ell-d+1),\ell(k-d+1)\}.\]
Codes attaining this bound with equality are always possible, and are called \emph{maximum rank distance (MRD) codes~\cite{Del78}}.
}

Let $\A$ be a $k\times (n-k)$ matrix, and let $\ve{I}_k$ be a $k\times k$ identity matrix. The matrix $[\ve{I}_k\ \A]$ can be viewed as a generator matrix of a $k$-dimensional subspace of $\Fq^{n}$, and it is called the \emph{lifting} of $\A$.
When all the codewords of an MRD code are lifted to $k$-dimensional subspaces, the result is
called a \emph{lifted MRD code}, denoted by $\mathbb{C}^{\mathrm{MRD}}$.
\begin{theorem}\label{thm:EK_1_ext}
Let $n,k,\delta$ and $\alpha$ be positive integers such that $1\leq \delta \leq k$, $\delta+k\leq n$ and $\alpha\geq 2$. Then
$${\cal B}_q(n,k,\delta;\alpha) \geq (\alpha -1) q^{\max\{k,n-k\}(\min\{k,n-k\}-\delta+1)}.$$
\end{theorem}

\begin{IEEEproof} Let $m=n-k$ and $K=\max\{m,n-m\}(\min\{m,n-m\}-\delta+1)$.
Since $\delta \leq \min\{m,n-m\}$,  an $[m\times (n-m), K, \delta]_q$ MRD code $\mathbb{C}$ exists.
Let $\mathbb{C}^{\mathrm{MRD}}$ be the lifted code of $\mathbb{C}$. Then $\mathbb{C}^{\mathrm{MRD}}$ is a subspace code of $\Fq^n$, which contains $q^K$ $m$-dimensional subspaces as codewords and its minimum subspace distance is $2\delta$~\cite{SKK08}.
Hence, for any two different codewords $C_1,C_2 \in \mathbb{C}^{\mathrm{MRD}}$ we have
$$\dim (C_1 \cap C_2)\leq m-\delta.$$

Now, let $\mathbb{D}=\set*{C^{\perp} ; C \in \mathbb{C}^{\mathrm{MRD}}}$. Take $\alpha -1$ copies of $\mathbb D$ and denote their multiset union as  $\mathbb{D}^{(\alpha)}$. We claim that $\mathbb{D}^{(\alpha)}$ is an $\alpha$-$(n,k,\delta)_q^c$ covering Grassmannian code. For each codeword of $\mathbb{D}^{(\alpha)}$, since it is the dual of a codeword in $\mathbb{C}^{\mathrm{MRD}}$, it has dimension $n-m$, which is $k$. For arbitrarily $\alpha$ codewords $D_1,D_2,\ldots, D_\alpha$ of $\mathbb{D}^{(\alpha)}$, there exist $1\leq i < j\leq \alpha$ such that $D_i \not= D_j$. Let $C_i=D_i^{\perp}$ and $C_j=D_j^\perp$. Then $C_i$ and $C_j$ are two distinct codewords of $\mathbb{C}^{\mathrm{MRD}}$. It follows that
\begin{align*}
    \dim\parenv*{\sum_{\ell=1}^\alpha D_\ell} & \geq \dim \parenv*{D_i +D_j }
    = n - \dim \parenv*{D_i^{\perp} \cap D_j^{\perp}}\\
    & = n - \dim \parenv*{C_i \cap C_j}
    \geq n-m+\delta = k+\delta.
\end{align*}
So far we have shown that $\mathbb{D}^{(\alpha)}$ is an $\alpha$-$(n,k,\delta)_q^c$ covering Grassmannian code. Then the conclusion follows by noting that
\begin{align*}
|\mathbb{D}^{(\alpha)}|= & (\alpha-1)|\mathbb{D}|=(\alpha-1)|\mathbb{C}^{\mathrm{MRD}}| \\
= & (\alpha-1) q^{\max\{k,n-k\}(\min\{k,n-k\}-\delta+1)}.
\end{align*}
\end{IEEEproof}

Corollary~\ref{cor:EK19_lb} below results from the relation between covering Grassmannian codes and network solutions in Theorem~\ref{thm:cover_scalar_sol} and the lower bound on the cardinality of covering Grassmannian codes in Theorem~\ref{thm:EK_1_ext}.

\begin{corollary}\label{cor:EK19_lb}
Let $\alpha\geq 2$, $h,\ell,t\geq 1$, $\eps\geq 0$, $h\leq 2\ell+\eps$.
For an $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ which has a $(q,t)$-linear solution, the maximum number of middle nodes
\[
r_{\max}\geq (\alpha-1)q^{g(t)}
\]
where
 \begin{align*}
     g(t):=&\max\{\ell t,(h-\ell)t\}\\
     &\cdot(\min\{\ell t, (h-\ell)t\}-(h-\ell-\eps)t+1) \\
     =&\begin{cases}\ell\eps t^2 +\ell t & h\leq 2\ell, \\ (h-\ell)(2\ell+\eps-h)t^2+(h-\ell)t & \text{otherwise.} \end{cases}
 \end{align*}
\end{corollary}

\section{Bounds on the Field Size Gap}\label{sec:bound_gap}
In previous sections, we discussed bounds on $r_{\max}$. The main results in this section are the lower and upper bounds on $\gap(\cN)$ in Theorem~\ref{thm:gap_lb} and~\ref{thm:gap_ub} respectively.
To discuss $\gap (\cN)$, we first need the following conditions on the smallest field size $q_s(\cN)$ or $q_v(\cN)$, for which a network $\cN$ is solvable.

\begin{lemma}\label{lem:lb_q}
Let $\alpha\geq 2$, $r,h,\ell,t\geq 1$, $\eps\geq 0$. If $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ has a $(q,t)$-linear solution then
    \begin{align*}
        q^t \geq
        \begin{cases}
        \parenv*{ \frac{r+\theta-\alpha}{\gamma\cdot\theta}}^{\frac{1}{\ell (\eps t+1)}} & h\geq 2\ell+\eps,\\
        \parenv*{ \frac{r}{\gamma(\alpha-1)}}^{\frac{1}{\ell(\eps t+1)}} & \text{otherwise,}
        \end{cases}
    \end{align*}
    where $\theta := \alpha-\floor*{\frac{h-\eps}{\ell}}+1$ and $\gamma\approx 3.48$.
\end{lemma}
\begin{IEEEproof}
    The first case follows from Corollary~\ref{cor:imupperbound-N} that for $h\geq 2\ell+\eps$,
    $q^t\geq \parenv*{ \frac{r+\theta-\alpha}{\gamma\cdot\theta}}^{\frac{1}{\ell (\eps t+1)}}$. The second case is derived from an upper bound on $r$ in~\cite{EZjul2019} (recalled in Corollary~\ref{cor:EZ19_vector}) in a similar manner.
\end{IEEEproof}

\begin{lemma}\label{lem:ub_q}
Let $\alpha\geq 2$, $r,h,\ell,t\geq 1$, $\eps\geq 0$. There exists a $(q,t)$-linear solution to $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ when
\[
    q^t \geq
    \begin{cases}
    \parenv*{\frac{r}{\beta}}^{\frac{(\alpha-1)t}{f(t)}} & h\geq2\ell+\eps \\
    \parenv*{\frac{r}{\alpha-1}}^{\frac{t}{g(t)}}   &\text{otherwise,}
    \end{cases}
    \]
    where $\beta$ and $f(t)$ are defined as in Theorem~\ref{thm:LLL_bound}, and $g(t)$ is defined as in Corollary~\ref{cor:EK19_lb}.
\end{lemma}
\begin{IEEEproof}
    The proof is similar to that in Lemma~\ref{lem:lb_q} and the cases follow from Theorem~\ref{thm:LLL_bound} and Corollary~\ref{cor:EK19_lb} respectively.
\end{IEEEproof}
Lemma~\ref{lem:lb_q} and Lemma~\ref{lem:ub_q} can be seen as the necessary and the sufficient conditions respectively on the pair $(q,t)$ s.t.~a $(q,t)$-linear solution exists.

In the following, we use the lemmas above to derive  bounds on the $\gap(\cN)$ for a given network $\cN$. The bounds are determined only by the network parameters.

\begin{theorem}\label{thm:gap_ub}
 Let $\alpha\geq 2$, $r,h,\ell\geq 1$, $\eps\geq 0$. Then for the $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ network,
  \begin{align*}
      \gap(\cN)\leq
      \begin{cases}
      \frac{\alpha-1}{f(1)}\log_2\parenv*{\frac{r}{\beta}}-A & h\geq 2\ell+\eps\\
      \frac{1}{g(1)}\log_2\parenv*{\frac{r}{\alpha-1}}- B & \text{otherwise},
      \end{cases}
  \end{align*}
where $\theta := \alpha-\floor*{\frac{h-\eps}{\ell}}+1$, $\beta$ and $f(t)$ are defined as in Theorem~\ref{thm:LLL_bound}, $g(t)$ is defined as in Corollary~\ref{cor:EK19_lb}, and we define
\begin{align*}
  A := \min \set*{ \log_2\parenv*{q^t} ; q^t \geq \parenv*{\tfrac{r+\theta-\alpha}{\gamma \theta}}^{\frac{1}{\ell(\varepsilon t + 1)}} }
\end{align*}
and
\begin{align*}
B := \min \set*{ \log_2\parenv*{q^t} ; q^t \geq \parenv*{\tfrac{r}{\gamma (\alpha-1)}}^{\frac{1}{\ell(\varepsilon t + 1)}} }.
\end{align*}
Furthermore, for $t_A := \min \set*{ t ; 2^t \geq \parenv*{\tfrac{r+\theta-\alpha}{\gamma \theta}}^{\frac{1}{\ell(\varepsilon t + 1)}} } > 2$, we have
\begin{align*}
A \geq \min\set*{t_A,\frac{1}{\ell(\varepsilon (t_A-2) + 1)} \log_2\parenv*{\tfrac{r+\theta-\alpha}{\gamma \theta}}} \geq t_A-1,
\end{align*}
and for $t_B := \min \set*{ t ; 2^t \geq \parenv*{\tfrac{r}{\gamma (\alpha-1)}}^{\frac{1}{\ell(\varepsilon t + 1)}} } > 2$, we have
\begin{align*}
B \geq \min\set*{t_B,\frac{1}{\ell(\varepsilon (t_B-2) + 1)} \log_2\parenv*{\tfrac{r+\theta-\alpha}{\gamma \theta}}} \geq t_B-1.
\end{align*}

\end{theorem}

\begin{IEEEproof}
We only prove the bound for the case $h\geq 2\ell+\varepsilon$.
The other case follows analogously.
Lemma~\ref{lem:ub_q} implies that
\[q_s(\cN)\leq \parenv*{\frac{r}{\beta}}^{\frac{\alpha-1}{f(1)}}.\]
By the definition of $q_v(\cN)$ and Lemma~\ref{lem:lb_q}, $q^t = q_v(\cN)$ must fulfill
\[q^t \geq \parenv*{\tfrac{r+\theta-\alpha}{\gamma \theta}}^{\frac{1}{\ell(\varepsilon t + 1)}}.\]
Hence, we get a lower bound on $q_v(\cN)$ by determining the smallest $q^t$ that fulfills this inequality, i.e., $A$.
Note that the left-hand side of the inequality is a strictly monotonically increasing function in $t$ (for a fixed $q$), and the right side is monotonically decreasing in $t$ (among others, this implies that $A$ and $t_A$ are well-defined).

For the lower bound on $A$ for $t_A>2$, consider the case that there is a prime power $q>2$ and a positive integer $t$ with $2^{t_A} \geq q^t \geq
\parenv*{\tfrac{r+\theta-\alpha}{\gamma \theta}}^{\frac{1}{\ell(\varepsilon t + 1)}}$.
Then we have $t \leq t_A-2$ since $q \geq 3$ and $t_A \geq 3$.
Hence,
\begin{align*}
q^t \geq \parenv*{\tfrac{r+\theta-\alpha}{\gamma \theta}}^{\frac{1}{\ell(\varepsilon (t_A-2) + 1)}} \geq \parenv*{\tfrac{r+\theta-\alpha}{\gamma \theta}}^{\frac{1}{\ell(\varepsilon (t_A-1) + 1)}} \geq 2^{t_A-1},
\end{align*}
which proves the claim.
\end{IEEEproof}

\begin{corollary}\label{cor:gap_ub}
  Let $\alpha\geq 2$, $r,h,\ell\geq 1$, $\eps\geq 0$. Then for the $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ network,
  \begin{align*}
    \gap(\cN)\leq
      \begin{cases}
      \frac{\alpha-1}{f(1)}\log_2\parenv*{\frac{r}{\beta}}- \max\set*{t'-1,1} &\!\!\! h\geq 2\ell+\eps\\
      \frac{1}{g(1)}\log_2\parenv*{\frac{r}{\alpha-1}}- \max\set*{t''-1,1} & \text{otherwise},
      \end{cases}
  \end{align*}

  where $\gamma\approx 3.48$, $\theta= \alpha-\floor*{\frac{h-\eps}{\ell}}+1$, $\beta= \parenv*{\frac{(\alpha-1)!}{2e\gamma\alpha}}^{\frac{1}{\alpha-1}}$, $f(t)$ and $g(t)$ are defined as in Theoremm~\ref{thm:LLL_bound} and Corollary~\ref{cor:EK19_lb} respectively, and
  \begin{align*}
    t' &= \sqrt{\frac{1}{\ell\varepsilon}\log_2\parenv*{\frac{r+\theta-\alpha}{\gamma\theta}}+\frac{1}{4 \varepsilon^2}}-\frac{1}{2 \varepsilon},\\
  t''&=\sqrt{\frac{1}{\ell\varepsilon}\log_2\parenv*{\tfrac{r}{\gamma (\alpha-1)}}+\frac{1}{4 \varepsilon^2}}-\frac{1}{2 \varepsilon}.
  \end{align*}
  In particular, if all parameters are constants except for $r\to\infty$, then $\gap(\cN)\in O(\log r)$.
\end{corollary}
\begin{IEEEproof}
We only prove the bound for the case $h\geq 2\ell+\varepsilon$.
The other case follows analogously.
We determine $t_A$ as defined in Theorem~\ref{thm:gap_ub}.
Note that $2^t$ is strictly monotonically increasing in $t$ and $\parenv*{\tfrac{r+\theta-\alpha}{\gamma \theta}}^{\frac{1}{\ell(\varepsilon t + 1)}}$ is strictly monotonically decreasing.
Hence, we have $t_A = \lceil t' \rceil$, where $t'$ is the unique (positive) solution of
\[2^{t'} = \parenv*{\tfrac{r+\theta-\alpha}{\gamma \theta}}^{\frac{1}{\ell(\varepsilon t' + 1)}}.\]
By rewriting this equation into a quadratic equation in $t'$, we obtain the following positive solution:
\begin{equation*}
t' = \sqrt{\frac{1}{\ell\varepsilon}\log_2\parenv*{\frac{r+\theta-\alpha}{\gamma\theta}}+\frac{1}{4 \varepsilon^2}}-\frac{1}{2 \varepsilon}.
\end{equation*}
Using the bound $A \geq t_A-1$ for $t_A >2$ (Theorem~\ref{thm:gap_ub}) and the trivial bound $A \geq 1$ otherwise, the claim follows.
The asymptotic statement is an immediate consequence.
\end{IEEEproof}

\begin{theorem}
\label{thm:gap_lb}
  Let $\alpha\geq 2$, $r,h,\ell\geq 1$, $\eps\geq 0$. Then for the $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ network,
  \begin{align*}
      \gap(\cN)\geq
      \begin{cases}
      \frac{1}{\ell(\eps+1)}\log_2\parenv*{\frac{r+\theta-\alpha}{\gamma\theta}}-t_{\Delta} & h\geq 2\ell+\eps\\
      \frac{1}{\ell(\eps+1)}\log_2\parenv*{\frac{r}{\gamma(\alpha-1)}}-t_{\star} & \text{otherwise},
      \end{cases}
  \end{align*}
  where {$\gamma\approx 3.48$, $\theta = \alpha-\floor*{\frac{h-\eps}{\ell}}+1$,} $t_{\Delta}$ is the smallest positive integer s.t.~$2^{\frac{f(t_{\Delta})}{\alpha-1}}\geq \frac{r}{\beta}$ and $t_{\star}$ is the smallest positive integer s.t.~$2^{g(t_{\star})}\geq \frac{r}{\alpha-1}$.
  Here, $\beta$ and $f(t)$ are defined as in Theorem~\ref{thm:LLL_bound}, and $g(t)$ is defined as in Corollary~\ref{cor:EK19_lb}.
\end{theorem}
\begin{IEEEproof}
 Let us only consider the first case $h\geq 2\ell+\eps$. The other case can be proved in the same manner. According to Lemma~\ref{lem:lb_q}, we have the lower bound on the smallest field size of a scalar solution,
 \[q_s(\cN)\geq \parenv*{ \frac{r+\theta-\alpha}{\gamma\cdot\theta}}^{\frac{1}{\ell (\eps +1)}}.\]
For vector solutions, according to Lemma~\ref{lem:ub_q}, we want to find $(q,t)$ s.t.~$q^{\frac{f(t)}{\alpha-1}}\geq \frac{r}{\beta}.$
Since $t_{\Delta}$ is the smallest positive integer $t$ s.t.~$2^{\frac{f(t)}{\alpha-1}}\geq \frac{r}{\beta}$, it is guaranteed that a $(2,t_{\Delta})$-linear solution exists.
Therefore, $q_v(\cN)$ (the smallest value of $q^t$) should be at most
$q_v(\cN)\leq 2^{t_{\Delta}}$.
The lower bound then follows directly from the definition of $\gap(\cN)$.
\end{IEEEproof}

By carefully bounding $t_{\star}$ and $t_{\Delta}$, the following is obtained:

\begin{corollary}
\label{cor:gap}
Let $\alpha\geq 2$, $r,h,\ell,\eps\geq 1$. {Assume that $h\not= \alpha \ell+\varepsilon$.} Then for the $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ network,
\[
\gap(\cN) \geq
\begin{cases}
\frac{\log_2\parenv*{\frac{r+\theta-\alpha}{\gamma \theta}}}{\ell(\eps+1)} - \sqrt{\frac{(\alpha-1)\log_2(\frac{r}{\beta})}{(\alpha\ell+\eps-h)\eps}}  & h\geq 2\ell+\eps\\
\frac{\log_2\parenv*{\frac{r}{\alpha-1}}-2}{\ell(\eps+1)}-\sqrt{\frac{\log_2(\frac{r}{\alpha-1})}{\ell\eps}}& \text{otherwise,}
\end{cases}
\]
{where $\gamma\approx 3.48$, $\theta= \alpha-\floor*{\frac{h-\eps}{\ell}}+1$, $\beta= \parenv*{\frac{(\alpha-1)!}{2e\gamma\alpha}}^{\frac{1}{\alpha-1}}$, $f(t)$ and $g(t)$ are defined as in Theoremm~\ref{thm:LLL_bound} and Corollary~\ref{cor:EK19_lb} respectively.}
In particular, if all parameters are constants except for $r\to\infty$, then $\gap(\cN) \in \Omega(\log r)$.
\end{corollary}
\begin{IEEEproof}
When $h \geq 2\ell+\eps$, noting that $\alpha \ell+2\eps-h>0$ {and $h\not= \alpha \ell+\varepsilon$}, we may choose
$$t=\parenv*{\frac{(\alpha-1)\log_2(\frac{r}{\beta})}{(\alpha\ell+\eps-h)\eps} }^{1/2}$$
such that $2^{f(t)}\geq 2^{(\alpha\ell+\eps-h)\eps t^2}=(\frac{r}{\beta})^{\alpha-1}.$
Then we have that
\begin{align*}
\gap(\cN)\geq &
\frac{\log_2\parenv*{\frac{r+\theta-\alpha}{\gamma \theta}}}{\ell(\eps+1)} - \parenv*{\frac{(\alpha-1)\log_2(\frac{r}{\beta})}{(\alpha\ell+\eps-h)\eps} }^{1/2}
  \\ \geq & \frac{\log_2 (r+\theta-\alpha)-\log_2\theta-2}{\ell(\eps+1)} \\
  &-\parenv*{\frac{\log_2 r-\log_2 \beta}{ (\ell-\frac{h-\ell-\eps}{\alpha-1})\eps}}^{1/2}
\end{align*}
Recall that $\beta$ and $\theta$ are determined by $\alpha, h, \eps,$ and $\ell$. Thus if $\alpha, h, \eps,$ and $\ell$ are fixed,  $\gap(\cN)=\Omega(\log r)$.

When $h< 2\ell+\eps$, we may choose $$t=\parenv*{\frac{\log_2(\frac{r}{\alpha-1})}{\ell\eps}}^{1/2}$$
such that $2^{g(t)}\geq 2^{\ell \eps t^2}=\frac{r}{\alpha-1}.$ It follows that
\begin{align*}
\gap(\cN)&\geq \frac{\log_2\parenv*{\frac{r}{\gamma(\alpha-1)}}}{\ell(\eps+1)}-\parenv*{\frac{\log_2(\frac{r}{\alpha-1})}{\ell\eps}}^{1/2}\\
& \geq \frac{\log_2\parenv*{\frac{r}{\alpha-1}}-2}{\ell(\eps+1)}-\parenv*{\frac{\log_2(\frac{r}{\alpha-1})}{\ell\eps}}^{1/2}
\end{align*}
This shows that $\gap(\cN) \in \Omega(\log r)$.
\end{IEEEproof}

Corollaries~\ref{cor:gap_ub} and \ref{cor:gap} show that for fixed network parameters except for $r$, the gap size grows as
\begin{equation*}
\gap(\cN) = \Theta(\log r) \quad (r \to \infty).
\end{equation*}

\begin{example}
  We illustrate the proof of Theorem~\ref{thm:gap_ub} and Theorem~\ref{thm:gap_lb} by two network examples with $r=8\times 10^5$ in Figure~\ref{fig:q_bound} and $r=8\times 10^6$ in Figure~\ref{fig:q_bound2}. Note that the curves in the figures are not bounds on the gap size. They are the necessary (blue curve) and the sufficient (green curve) condition on $q^t$ such that a $(q,t)$-linear solution exists. Namely, there is no $(q,t)$-linear solution in the region below the blue curve and there must be a $(q,t)$-linear solution in the region above the green curve. Thus the minimum gap of the network $(2,1)-\cN_{12,r,20}$ is determined by the difference between the necessary condition with $t=1$ and the minimum $2^t$ that is in the region above the sufficient condition. Similarly, the maximum gap of the network is determined by the difference between the sufficient condition with $t=1$ and the minimum $2^t$ that is in the region above the necessary condition.

  By comparing the two plots it can be seen that the gap increases as the number of middle node in the network increases.
\begin{figure*}[t!]
    \centering
    \minipage{0.49\textwidth}
    \input{h12l1e2r8e5a20}
    \caption{An illustration of proofs of Theorem~\ref{thm:gap_ub} and Theorem~\ref{thm:gap_lb} for the network $(2,1)-\cN_{12,8e5,20}$.
    }
    \label{fig:q_bound}
\endminipage\hfill
\minipage{0.49\textwidth}
    \input{h12l1e2r8e6a20}
    \caption{An illustration of proofs of Theorem~\ref{thm:gap_ub} and Theorem~\ref{thm:gap_lb} for the network $(2,1)-\cN_{12,8e6,20}$.
    }
    \label{fig:q_bound2}
    \endminipage
\end{figure*}
\end{example}

\section{Discussion}\label{sec:discussion}
In this section we will compare our upper and lower bound on $r_{\max}$ with previous known bounds.
\subsection{Other Upper Bound on $r_{\max}$}

In the following we recall the result from~\cite[Corollary 3]{EZjul2019} and compare it with our upper bound in Corollary~\ref{cor:imupperbound-2-Network}.

\begin{theorem}[{\cite[Corollary~3]{EZjul2019}}]\label{thm:codesize}
  If $n$, $k$, $\delta$, and $\alpha$, are positive integers such that $1<k<n,\ 1\leq\delta\leq n-k$ and $2\leq\alpha\leq\quadbinom{k+\delta-1}{k}_{q}+1$, then for an $\alpha-(n,k,\delta)_q^c$ {covering Grassmannian code} $\mathbb{C}$, we have that
$$|\mathbb{C}|\leq\floor*{(\alpha-1)\frac{\quadbinom{n}{\delta+k-1}_{q}}{{\quadbinom{n-k}{\delta-1}_{q}}}}.$$
\end{theorem}

By combining Theorem~\ref{thm:codesize} and Theorem~\ref{thm:cover_scalar_sol}, the following corollary can be directly derived.
\begin{corollary}\label{cor:EZ19_vector}
  If the $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ network has a $(q,t)$-linear solution then
  \begin{align*}
    r\leq r_{\max}&\leq\floor*{(\alpha-1)\frac{\quadbinom{ht}{ht-\eps t-1}_{q}}{{\quadbinom{ht-\ell t}{ht -\ell t-\eps t -1}_{q}}}}\\
    & < (\alpha-1)\frac{\gamma q^{(\eps t+1)(ht -\eps t-1)}}{q^{(\eps t+1)(ht -\ell t -\eps t-1)}}\\
    & =  \gamma (\alpha-1)q^{\ell t(\eps t+1)},
  \end{align*}
  with $1<\ell t<h t$, $0\leq \eps\leq h-\ell-\frac{1}{t}$, $2\leq \alpha\leq\quadbinom{ht-\eps t-1}{\ell t}_{q}+1$.\\
\end{corollary}
\subsection{Comparison Between Upper Bounds}
In the following, we first show that for some parameters, the upper bound in Corollary~\ref{cor:imupperbound-N} could be better than that in Corollary~\ref{cor:EZ19_vector}.
Denote
$$\theta := \parenv*{\alpha- \floor*{ \frac{h-\eps}{\ell} }+1}.$$
The upper bound in Corollary~\ref{cor:imupperbound-N} and Corollary~\ref{cor:EZ19_vector} can be respectively written as
$$U_A := \sbinom{(\eps+\ell) t}{\eps t}_q \parenv*{\theta \cdot \frac{q^{\ell t+1}-1}{q-1}  -1   }+ \alpha -\theta$$
 and
$$U_B:= (\alpha-1)\frac{\quadbinom{ht}{ht-\eps t-1}_{q}}{{\quadbinom{ht-\ell t}{ht -\ell t-\eps t -1}_{q}}}=(\alpha-1)q^{\ell t(\eps t +1)}\prod\limits^{\eps t}_{i=0}\frac{q^{ht-i}-1}{q^{ht-i}-q^{\ell t}}.$$

\begin{lemma}\label{lem:compare-2}
 Let $h \geq 2\ell+\eps$ and $2\leq \alpha \leq \sbinom{ht-\eps t-1}{\ell t}_q+1$. Assume $\sbinom{\eps+\ell)t}{\eps t}_q\leq \alpha$,
then
\[
  \log_q U_A - \log_q U_B < \log_q\frac{2\theta\alpha}{\alpha-1}- \ell \eps t^2.
\]
Particularly, if $$\frac{2\theta \alpha}{\alpha-1}\leq q^{\ell\eps t^2},$$
then
$$U_A<U_B.$$
That is, the upper bound in Corollary~\ref{cor:imupperbound-N} is better than that in  Corollary~\ref{cor:EZ19_vector}.
 \end{lemma}

\begin{IEEEproof}
Under the assumption $\sbinom{(\eps+\ell)t }{\eps t}_q\leq {\alpha}$, we have
\begingroup
\allowdisplaybreaks
\begin{align*}
\log_q U_A & \leq \log_q \parenv*{\alpha \parenv*{ \theta\cdot \frac{q^{\ell t+1}-1}{q-1}  -1   }+ \alpha-\theta } \\
&=\log_q( \alpha \theta \cdot\frac{q^{\ell t+1}-1}{q-1} -\alpha+\alpha-\theta)\\
&=\log_q \theta+\log_q(\alpha \cdot \frac{q^{\ell t+1}-1}{q-1} -1)\\
&<\log_q \theta+\log_q(\alpha \cdot \frac{q^{\ell t+1}-1}{q-1})\\
&\overset{(*)}{<}\log_q \theta +\log_q \alpha + \log_q(2\cdot q^{\ell t})\\
& = \log_q \theta +\log_q \alpha +  \ell t + \log_q 2.
\end{align*}
\endgroup
The inequality $(*)$ is because $\frac{q^{\ell t+1}-1}{q-1}=\sum\limits^{\ell t}_{i=0}q^i<2\cdot q^{\ell t}$.
By the bounds on the $q$-binomial coefficient,
\begin{align*}
  \log_q U_B >  \log(\alpha-1) + \ell t (\eps t+1),
\end{align*}
we have that
\begin{align*}
  \log_q U_A - \log_q U_B < \log_q\frac{2\theta\alpha}{\alpha-1}- \ell \eps t^2.
\end{align*}
Together with the assumption $\frac{2\theta \alpha}{\alpha-1}\leq q^{\ell\eps t^2}$, the conclusion follows.
 \end{IEEEproof}

 \begin{lemma}\label{lem:compare}Let $h \geq 2\ell+\eps$ and $2\leq\alpha \leq \sbinom{ht-\eps t-1}{\ell t}_q+1$.
Assume $\sbinom{(\eps+\ell)t}{\eps t}_q\geq \alpha$. If
$h\geq  2\eps$, then
$$\frac{U_A}{U_B}\leq \frac{8\theta}{\alpha-1}.$$
So, when
$${8\theta} < {\alpha-1},$$
we have that
$${U_A}<{U_B}.$$
 That is, the upper bound in Corollary~\ref{cor:imupperbound-N} is better than that in  Corollary~\ref{cor:EZ19_vector}.
\end{lemma}
\begin{IEEEproof}
  Since $\quadbinom{\eps+\ell)t}{\eps t}_q\geq \alpha$,  we have that
  $$ U_A \leq  \theta\cdot \sbinom{(\eps+\ell) t}{\eps t}_q \frac{q^{\ell t+1}-1}{q-1}.$$
  Then
\begin{align*}
  \frac{U_A}{U_B}  \leq&  \frac{\theta}{\alpha-1}\cdot \frac{q^{\ell t+1}-1}{q-1}\sbinom{(\eps+\ell)t}{\eps t}_q\\
  &\cdot\sbinom{(h-\ell)t}{(h-\ell-\eps)t-1}_q\sbinom{ht}{(h-\eps)t-1}_q^{-1}  \\
  = &\frac{\theta}{\alpha-1}\cdot\frac{q^{\ell t+1}-1}{q-1}\sbinom{(\eps+\ell)t}{\eps t}_q\sbinom{(h-\ell)t}{\eps t+1}_q\sbinom{ht}{\eps t+1}_q^{-1}  \\
  = &\frac{\theta}{\alpha-1}\cdot \frac{q^{\ell t+1}-1}{q-1}\cdot \frac{(q^{(\eps+\ell)t}-1)\cdots (q^{\ell t+1}-1)}{(q^{\eps t}-1)\cdots(q-1)}\\
  &\cdot \frac{(q^{(h-\ell)t}-1)\cdots(q^{(h-\ell-\eps)t}-1)}{(q^{ht}-1)\cdots (q^{(h-\eps)t}-1)}\\
  <& \frac{\theta}{\alpha-1}\cdot \frac{q^{\ell t+1}}{q-1}\cdot \frac{q^{(\eps+\ell)t}\cdots q^{\ell t+1}}{(q^{\eps t}-1)\cdots(q-1)}\\
  &\cdot \frac{q^{(h-\ell)t}\cdots q^{(h-\ell-\eps)t}}{(q^{ht}-1)\cdots (q^{(h-\eps)t}-1)}\\
  =&\frac{\theta}{\alpha-1}\cdot \frac{q}{q-1}\cdot
  \prod_{i=1}^{\eps t}  \parenv*{1-\frac{1}{q^i}}^{-1}  \cdot\prod_{i=h t -\eps t}^{h t}  \parenv*{1-\frac{1}{q^i}}^{-1}\\
  \leq& \frac{\theta}{\alpha-1}\cdot\parenv*{1+\frac{1}{q-1}}
  \prod_{i=1}^{h t}  \parenv*{1-\frac{1}{q^i}}^{-1}\!\textrm{(assume $2\eps\leq h$)}\\
  <&  \frac{8\cdot \theta }{\alpha-1},
\end{align*}
and the conclusion follows.
\end{IEEEproof}

Now,  we compare the upper bound  in Corollary~\ref{cor:imupperbound-2-Network} with that in Corollary~\ref{cor:EZ19_vector} for $\alpha=2$.
\begin{lemma}\label{lem:compare-alpha2}
Denote $U_C:= \gamma q^{(h-\ell)(2\ell+\eps-h)t^2+(h-\ell)t}$
and $U_D:= \gamma q^{\ell t(\eps t+1)}$. Then
\[
    \log_q U_C -\log_q U_D  =   [(h-\ell)(2\ell+\eps-h)-\eps \ell]t^2 +(h-2\ell)t.
\]
Particularly, if one of the following three conditions is satisfied,
\begin{itemize}
    \item $\eps t +1<\ell t$, and either $h>2\ell$ or $h<\ell+\eps+\frac{1}{t}$;
    \item $\eps t +1> \ell t$, and either $h>\ell+\eps+\frac{1}{t}$ or $h<2\ell$;
    \item $\eps t +1=\ell t$ and $h\not=2\ell$,
\end{itemize}
then
\begin{align*}
   \log_q U_C -\log_q U_D   <  0,
\end{align*}
and the upper bound  in Corollary~\ref{cor:imupperbound-2-Network} is better than the upper bound in Corollary~\ref{cor:EZ19_vector} for $\alpha=2$.
\end{lemma}

\begin{IEEEproof}
Denote $C=(h-\ell)(2\ell+\eps-h)t+(h-\eps)$ and $D=\ell(\eps t+1)$. Then $\log_q U_C -\log_q U_D=Ct-Dt$. So it suffices to show that $C < D$.
Note that $C=-th^2 +{3\ell +\eps }t h + h + \cdots$ is a quadratic function in $h$ which is symmetric about $h=\frac{(3\ell+\eps)t+1}{2t}$. We proceed in three cases, according to the position of the axis of symmetry.

\begin{enumerate}
    \item If $\eps t+1 < \ell t$, then $\frac{(3\ell+\eps)t+1}{2t}< 2\ell$, i.e., the axis of symmetry is on the left of $h=2\ell$. In this case, $C$ is decreasing when $h \geq 2\ell$. It follows that $C < D$ for $h> 2\ell$ as $C=D$ when $h=2\ell$.
    Furthermore, according to the symmetry, $C < D$ also holds for $h<\ell +\eps +\frac{1}{t}$.
    \item If $\eps t+1 > \ell t$,  then $\frac{(3\ell+\eps)t+1}{2t}> 2\ell$. Using the same argument, we can see that $C < D$ holds for $h< 2\ell$ and $h>\ell+\eps +\frac{1}{t}$.
    \item If $\eps t+1=\ell t$,  then $\frac{(3\ell+\eps)t+1}{2t}= 2\ell$. The maximal value of $C-D$ is taken at $h=2\ell$, which is $0$. So $C<D$ for all $h\not=2\ell$.
\end{enumerate}
\end{IEEEproof}

The following example shows that, in some cases, the upper bound in Corollary~\ref{cor:imupperbound-2-Network} matches a lower bound from~\cite{EKOOfeb2020} within a factor of $\gamma\approx 3.48$.
\begin{example}
Let $\alpha=2$, $\eps=\ell$, and $h=2\ell+1$.
A lower bound from \cite{EKOOfeb2020} is
$$q^{(\ell^2-1)t^2+(\ell+1) t} \leq r.$$
For the upper bound,
Corollary~\ref{cor:imupperbound-2-Network} shows that
$$r \leq \gamma q^{(\ell^2-1)t^2+(\ell+1)t},$$
agreeing with the lower bound up to a factor of $\gamma$. In contrast, Corollary~\ref{cor:EZ19_vector} shows that
$$r \leq \gamma q^{\ell^2 t^2+\ell t},$$
which differs from the lower bound by a factor of $\gamma q^{t^2-t}$.
\end{example}
\begin{corollary}
  If $n$, $k$, $\delta$, and $\alpha$, are positive integers such that $1<k<n$, $1\leq\delta\leq \min\{ n-k, k\}$, and $2\leq\alpha\leq\quadbinom{k+\delta-1}{k}_{q}+1$, then an upper bound on the size of an $\alpha-(n,k,\delta)_q^c$ code $\mathbb{C}$ is that
  \begin{align*} |{\mathbb{C}}| \leq & \quadbinom{n-\delta}{k}_q \parenv*{ \parenv*{\alpha- \floor*{ \frac{\delta-k}{k} }+1}  \frac{q^{k+1}-1}{q-1}  -1   }\\
    &+ \floor*{ \frac{\delta-k}{k}}-1.
\end{align*}
\end{corollary}
\begin{IEEEproof}
Note that an $\alpha-(n,k,\delta)_q^c$ code $\mathbb{C}$ exists if and only if the $(\eps,\ell)-\mathcal{N}_{h,r,\alpha\ell+\eps}$ network is solvable with linear scalar solutions, where $h=n$, $r=|\mathbb{C}|$, $\ell = k$ and $\eps=h-\ell-\delta=n-k-\delta$. Then the conclusion follows from Corollary~\ref{cor:imupperbound-N} by setting $t=1$.
\end{IEEEproof}

\subsection{Other Lower Bounds on $r_{\max}$}
Let ${\cal B}_q(n,k,\delta;\alpha)$ denote the maximum possible size of an $\alpha$-$(n,k,\delta)_q^c$ covering Grassmannian code. Etzion \emph{et al.} proposed the following lower bounds on  ${\cal B}_q(n,k,\delta;\alpha)$ for $\delta \leq k$ in~\cite{EKOOfeb2020}.

\begin{theorem}[{\cite[Theorem 21]{EKOOfeb2020}}]\label{thm:EK_lb}
Let $1\leq \delta \leq k$, $k+\delta \leq n$ and $2\leq \alpha \leq q^k+1$ be integers.
\begin{enumerate}
    \item If $n<k+2\delta$, then
    $${\cal B}_q(n,k,\delta;\alpha) \geq (\alpha -1) q^{\max\{k,n-k\}(\min\{k,n-k\}-\delta+1)}.$$

    \item If $n\geq k+2\delta$, then for each $t$ such that $\delta\leq t\leq n-k-\delta$, we have \label{case:EK_2}
    \begin{enumerate}
        \item If $t<k$, then
        $${\cal B}_q(n,k,\delta;\alpha) \geq (\alpha-1)q^{k(t-\delta+1)}{\cal B}_q(n-t,k,\delta;\alpha).$$
        \item If $t\geq k$, then
        \begin{align*}{\cal B}_q(n,k,\delta;\alpha) \geq &(\alpha-1)q^{t(k-\delta+1)}{\cal B}_q(n-t,k,\delta;\alpha) \\
        &\ +{\cal B}_q(t+k-\delta,k,\delta;\alpha).
        \end{align*}
    \end{enumerate}
\end{enumerate}
\end{theorem}
Theorem~\ref{thm:EK_1_ext} improves the theorem above by removing the conditions $\alpha \leq q^k+1$ and $n<k+2\delta$.
For $n\geq k+2\delta$, the numerical results show that either could be better, depending on the parameters. The theoretical comparison between the two lower bounds is hard due to the recursive function and is left for {future research}.
\subsection{Discussion of Lower Bounds}
In the following, we compare the lower bound on $r_{\max}$ in Corollary~\ref{cor:EK19_lb} with the upper bounds in the previous sections.
\begin{itemize}
\item When $h \leq 2\ell$, Corollary~\ref{cor:EK19_lb} gives
$$r_{\max}\geq (\alpha-1)q^{\ell t(\eps t+1)},$$
which is close (up to a constant factor of $\gamma\approx 3.48$) to the upper bound in Corollary~\ref{cor:EZ19_vector}, i.e., $$r_{\max}< \gamma(\alpha-1)q^{\ell t (\eps t+1)}.$$
\item When $h \geq 2\ell$ and $\alpha =2$,
Corollary~\ref{cor:EK19_lb} gives
$$r_{\max}\geq q^{(h-\ell)(2h+\eps-h)t^2 +(h-\ell)t},$$
which is close (up to a constant factor of $\gamma$) to the upper bound in Theorem~\ref{thm:imupbound-2},  $$r_{\max}< \gamma q^{(h-\ell)(2h+\eps-h)t^2 +(h-\ell)t}.$$
\item The upper bound in Corollary~\ref{cor:imupperbound-N} cannot be applied here as $(h-\eps)/\ell \leq 2$.
\end{itemize}
{\subsection{Minimal Generalized Combination Networks}
Minimal networks are networks in which the removal of any single edge makes it unsolvable linearly (see~\cite{CCESW20} and the references therein). Thus, in such minimal networks, the number of messages equals the min-cut. These networks are of interest since they require the least amount of network resources to enable the multicast operation.

For generalized combination networks, minimality occurs exactly when $h=\alpha\ell+\varepsilon$. For the case $\alpha=2$, it has been shown in~\cite{EW18} that vector linear solutions do not outperform scalar linear solutions in minimal generalized combination networks. In Figures~\ref{fig:min-cut1} and~\ref{fig:min-cut2} we show two examples of our results for $\alpha>2$ in minimal generalized combination networks. The lower bound on the gap in Theorem~\ref{thm:gap_lb} may give a negative value, as illustrated in these two examples. This is because the gap between the necessary (blue curve) and the sufficient (green curve) conditions on $q^t$ such that a $(q,t)$-linear solution exists, is relatively large compared to non-minimal networks (cf.~Figures~\ref{fig:q_bound} and~\ref{fig:q_bound2}). Taking a closer look into the sufficient condition in Lemma~\ref{lem:ub_q}, the function $f(t)$ results in the different behaviors of the green curve for $h=\alpha\ell+\varepsilon$ and $h<\alpha\ell+\varepsilon$. We observe that $f(t)=\eps t+1$ if $h=\alpha\ell+\varepsilon$, and is quadratic in $t$ otherwise. Since the sufficient condition for $h\geq 2\ell+\eps$ is directly derived from the lower bound on $r_{\max}$ in Theorem~\ref{thm:LLL_bound}, one possible way to close the gap between the necessary and sufficient conditions is to improve the lower bound on the $r_{\max}$ in Theorem~\ref{thm:LLL_bound}, which we leave as an open question.
}
\begin{figure*}[t!]
  \centering
  \minipage{0.49\textwidth}
  \input{h8a3minimal.tex}
  \caption{{An illustration of the gap for a minimal generalized combination network $(5,1)-\mathcal{N}_{8,8e5,8}$, where the number of messages is the min-cut of the network.}}
  \label{fig:min-cut1}
  \endminipage\hfill
  \minipage{0.49\textwidth}
  \input{h13a8minimal.tex}
  \caption{{An illustration of the gap for a minimal generalized combination network $(5,1)-\mathcal{N}_{13,8e5,13}$, where the number of messages is the min-cut of the network.}}
  \label{fig:min-cut2}
  \endminipage
\end{figure*}

\section{Conclusion}
In this work, we studied necessary and sufficient conditions for the existence of $(q,t)$-linear solutions to the generalized combination network $(\eps,\ell)$-$\mathcal{N}_{h,r,\alpha\ell+\eps}$. We derived new upper and lower bounds on $r_{\max}$, the maximum number of nodes in the middle layer, for a fixed network structure, thus getting bounds on the field size of the scalar/vector solution. Our lower bound is close (within a constant factor of $\gamma\approx 3.48$) to our upper bound for $h\leq 2\ell$ or $h\geq 2\ell,\alpha=2$. We summarize the best known bounds on $r_{\max}$ for different parameter ranges, in Table~\ref{tab:r_bound_summary}.

\begin{table*}[t!]
  \caption{Bounds on $r_{\max}$ of the $(\eps,\ell)-\cN_{\alpha,r,\alpha\ell+\eps}$ network with $(q,t)$-linear solutions}
  \label{tab:r_bound_summary}
  \begin{center}
  \begin{tabular}[l]{|l|l|l|l|l|}
    \hline
    Upper Bounds & $h< 2\ell+\eps$& Reference &$h\geq 2\ell+\eps$ & Reference\\
    \hline
    $\alpha> 2$ & $r_{\max}<\gamma (\alpha-1)q^{\ell t(\eps t+1)}$ &\cite{EZjul2019} (see also Corollary~\ref{cor:EZ19_vector}) &$r_{\max}<\gamma\theta q^{\ell t(\eps t+1)}+\alpha-\theta$  & Corollary~\ref{cor:imupperbound-N} \\
    \hline
    \multirow{2}{*}{$\alpha=2$}&\multicolumn{3}{c}{\multirow{2}{*}{$r_{\max}<\gamma q^{\min \{\ell t(\eps t+1),(h-\ell)(2\ell+\eps-h)t^2+(h-\ell)t\}}$}}& \cite{EZjul2019} \& Corollary~\ref{cor:imupperbound-2-Network}\\ &\multicolumn{3}{c}{\ }& (Comparison in Lemma~\ref{lem:compare-alpha2}) \\
    \hline
    \hline
    Lower Bounds& $h< 2\ell+\eps$& Reference & $h\geq 2\ell+\eps$ & Reference\\
    \hline
    $\alpha\geq 2$ & $r_{\max}\geq (\alpha-1)q^{g(t)}$& Corollary~\ref{cor:EK19_lb}& $r_{\max}\geq \beta \cdot q^{\frac{f(t)}{\alpha-1}}$ &  Theorem~\ref{thm:LLL_bound} \\
    \hline
  \end{tabular}
  \end{center}
  Remarks: The bounds are valid for $\alpha\geq 2,h,\ell\geq 1,\eps\geq 0$. For non-trivially solvable generalized combination networks, $\ell+\eps\leq h\leq \alpha\ell+\eps$. The other parameters are $\gamma\approx3.48$, $\beta = \parenv*{(\alpha-1)!/(2e\gamma\alpha)}^{1/(\alpha-1)}$,  $f(t)=(\alpha\ell+\eps-h)\eps t^2+(\alpha\ell+2\eps-h)t +{1}$, $\theta = \alpha-\floor*{(h-\eps)/\ell}+1$, and  $g(t)=\max\{\ell t,(h-\ell)t\}\cdot(\min\{\ell t, (h-\ell)t\}-(h-\ell-\eps)t+1)$.
\end{table*}

Moreover, we studied the gap between the minimal field size of a scalar solution and a vector solution.
{For general multicast networks, the gap is not well defined, since some multicast networks with no scalar $(q_s,1)$-linear solution, but only vector $(q,t)$-linear solutions (even for $q_s>q^t$), were demonstrated in~\cite{SYL+dec2016}. In our work, we focused on a class of multicast networks, the generalized combination networks, where both scalar and vector solutions exist. We studied the gap for this specific class of multicast networks. Unlike the previous works~\cite{EW18,CCESW20},} which focused on engineering the networks to obtain a high gap, we started by fixing network parameters (i.e., $h,r,\alpha,\ell,\eps $), and then provided bounds for its gap, which do not depend on $t$. Of particular interest is the conclusion from~Corollary~\ref{cor:gap_ub} and Corollary~\ref{cor:gap}: fixing the number of messages $h$, and parameters relating to the connectivity level of the network (i.e., $\alpha,\ell,\eps$), we only vary the number of middle layer nodes, $r$, or equivalently, the number of receivers $N:=\binom{r}{\alpha}$, proving that the gap is $\gap(\cN)=\Theta(\log r)=\Theta(\log N)$. Namely, the scalar linear solutions over-pays an order of $\log(r)$ extra bits per symbol to solve the network, in comparison to the vector linear solutions.

The novel upper and lower bounds on the gap cover all generalized network parameters, except $\eps=0$. This may imply that the direct links between the source and the terminals are crucial for vector network coding to have an advantage in generalized combination networks. The direct link in usual communication networks might not be practical, however, in some recent applications, such as coded caching, this direct link can be seen as the cached content at the receivers. The exact nature of the connection between direct links and field-size gap, is left for future work.

\bibliographystyle{IEEEtranS}
\bibliography{VNC}

\begin{IEEEbiographynophoto}{Hedongliang Liu}
  (S'19) is a doctoral student at the Technical University of Munich (TUM), Germany in the Department of Electrical and Computer Engineering.
  She received the B.Eng.~degree in Information Engineering at Southeast University, Nanjing, P.~R.~China in 2016 and M.Sc.~degree in Communication Engineering in 2019.
  Her research interests are coding theory and its application in networks, storage, and cryptography.
\end{IEEEbiographynophoto}

\begin{IEEEbiographynophoto}{Hengjia Wei}
  is a postdoctoral fellow in the School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Israel.
  He received the Ph.D.~degree in Applied Mathematics from Zhejiang University, Hangzhou, Zhejiang, P.~R.~China in 2014. He was a postdoctoral fellow in the Capital Normal University, Beijing, P.~R.~China, from 2014 to 2016, and a research fellow in the School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, from 2016 to 2019.
  His research interests include combinatorial design theory, coding theory and their intersections.

  Dr. Wei received the 2017 Kirkman Medal from the Institute of Combinatorics and its Applications.
\end{IEEEbiographynophoto}
\begin{IEEEbiographynophoto}{Sven Puchinger}
  (S'14, M'19) is a postdoctoral researcher at the Technical University of Munich (TUM), Germany.
  He received the B.Sc.~degree in electrical engineering and the B.Sc.~degree in mathematics from Ulm University, Germany, in 2012 and 2016, respectively. During his studies, he spent two semesters at the University of Toronto, Canada. He received his Ph.D.~degree from the Institute of Communications Engineering, Ulm University, Germany, in 2018. He has been a postdoc at the Technical University of Munich (2018--2019 and since 2021) and the Technical University of Denmark (2019--2021), Denmark.
  His research interests are coding theory, its applications, and related computer-algebra methods.
\end{IEEEbiographynophoto}

\begin{IEEEbiographynophoto}{Antonia Wachter-Zeh}
  (S’10–M’14-SM'20) is an Associate Professor at the Technical University of Munich (TUM), Munich, Germany in the Department of Electrical
  and Computer Engineering.
  She received the M.Sc.~degree in communications technology in 2009 from Ulm University, Germany. She obtained her Ph.D.~degree in 2013 from Ulm University and from Universite de Rennes 1, Rennes, France. From 2013 to 2016, she was a postdoctoral researcher at the Technion—Israel Institute of Technology, Haifa, Israel, and from 2016 to 2020 a Tenure Track Assistant Professor at TUM.
  Her research interests are coding theory, cryptography and information theory and their application to storage, communications, privacy, and security.

  Prof.~Wachter-Zeh is a recipient of the DFG Heinz Maier-Leibnitz-Preis and of an ERC Starting Grant.
\end{IEEEbiographynophoto}

\begin{IEEEbiographynophoto}{Moshe Schwartz}
(M'03--SM'10)
is a professor at the School of Electrical and Computer
Engineering, Ben-Gurion University of the Negev, Israel. His research
interests include algebraic coding, combinatorial structures, and
digital sequences.

He received the B.A.~(\emph{summa cum laude}), M.Sc., and
Ph.D.~degrees from the Technion -- Israel Institute of Technology,
Haifa, Israel, in 1997, 1998, and 2004 respectively, all from the
Computer Science Department. He was a Fulbright post-doctoral
researcher in the Department of Electrical and Computer Engineering,
University of California San Diego, and a post-doctoral researcher in
the Department of Electrical Engineering, California Institute of
Technology. While on sabbatical 2012--2014, he was a visiting scientist
at the Massachusetts Institute of Technology (MIT).

Prof.~Schwartz received the 2009 IEEE Communications Society Best
Paper Award in Signal Processing and Coding for Data Storage, and the
2020 NVMW Persistent Impact Prize. He has also been serving as an
Associate Editor for Coding Techniques for the IEEE Transactions on
Information Theory since 2014, and an Editorial Board Member for the
Journal of Combinatorial Theory Series A since 2021.
\end{IEEEbiographynophoto}
\end{document}

config: arxiv


text:
\section{{Distorting the Inputs and the Implication on States}}
\label{sec:inputs}

In many situations, it is easier to obtain a handle on the distribution of the input sequence than on the distribution of the state transition sequence.
{{Moreover, in some situations, a simple transformation of the original trajectory would lead to a fake trajectory that does not obey the system dynamics and thus can be detected by the adversary -- alternatively, the state trajectory distribution does not have useful symmetry properties. }

Motivated by these, here we consider a different setup where Alice encodes and transmits the input sequence to Bob instead of the state transition sequence, {{{\it i.e.}, $Z_t \coloneqq \mathcal{E}_t (U_t, K)$}. Under this setup, using the mirroring based scheme on inputs, one can provide guarantees on the level of {{average/worst-case} distortion for Eve's estimate of the inputs. {{We} then ask the following question: if Alice encodes and transmits the input vectors, how does the guarantees on average and worst-case distortions on the \textbf{inputs} translates to the guarantees on average and worst-case distortions on the \textbf{states}?

{Formally, we} consider the system model in~\eqref{eq:sys_model} with zero noise, {{\it i.e.}, $w_t = 0$. Following the definition of average and worst-case distortions in~\eqref{eq:average_case} and~\eqref{eq:worst_case} respectively, the {distortions} on inputs and states vectors {are} as follows:\\

\noindent Expected distortions:
{\begin{align*}
D_E^{(X)} &= \frac{1}{T} \mathbb{E}_Z \sum_{t=1}^{T} \text{tr} \left( R_{X_t|Z} \right), & D_E^{(U)} = \frac{1}{T} \mathbb{E}_Z \sum_{t=0}^{T-1} \text{tr} \left( R_{U_t|Z} \right).
\end{align*}
}
Worst-case distortions:
{\begin{align*}
D_W^{(X)} &= \min_Z \min_{t} \text{tr} \left( R_{X_t|Z} \right), &D_W^{(U)} = \min_Z \min_{t} \text{tr} \left( R_{U_t|Z} \right).
\end{align*}
}
{The following Theorem provides a relation between the distortion on the input vector and the distortion on the state vector for both expected and worst-case scenarios. In particular, it provides relations between {$D_E^X$, $D_E^U$, and $D_W^X$, $D_W^U$} .}
{
\begin{theorem}
\label{thm::MirroringPerformanceCausal_input}
If the input vectors $U_t, \: t \in [T-1] \cup \{0\}$

satisfy the following condition,
{
\begin{equation}
\label{eq::MirroringPerformanceCausal_input_cond}
 \mathbb{E}_Z \left[ \text{tr}\left( \underbrace{\sum\limits_{i=1}^t \sum\limits_{j=i+1}^t  B^\prime (A^{t-j})^\prime A^{t-i} B R_{U_{i-1}U_{j-1}|Z} }_{\Phi_t} \right) \right]\geq 0,
\end{equation}
}
then, for given distortions $D_E^{(U)}$ and $D_W^{(U)}$, the following bounds holds:
{
\begin{align*}
D_E^{(X)} &\geq \lambda_{\min} \left(B^\prime B \right) D_E^{(U)},
&D_W^{(X)} \geq \lambda_{\min} \left(B^\prime B \right) D_W^{(U)},
\end{align*}
}

where $\lambda_{\min} \left(B^\prime B \right)$ is the minimum eigenvalue of $B^\prime B$.
\end{theorem}

Theorem~\ref{thm::MirroringPerformanceCausal_input} gives a lower bound on the distortion level of the state vectors when distorting the inputs. The bound holds when the condition~\eqref{eq::MirroringPerformanceCausal_input_cond} holds. {{Examples} where condition~\eqref{eq::MirroringPerformanceCausal_input_cond} holds {are} open loop control systems where the distribution on {{the inputs has} a point of symmetry. We expand more on {{condition}~\eqref{eq::MirroringPerformanceCausal_input_cond} after {{the proof of Theorem~\ref{thm::MirroringPerformanceCausal_input}}.

\begin{IEEEproof}
We start by introducing the following notation $Z = Z_0^{T-1}$, $U = U_0^{T-1}$, $X = X_1^T$. Moreover, without loss of generality, we assume that $X_0  = 0$. The states of the noiseless dynamical system can be expressed as {$X_t = \sum\limits_{i=1}^t A^{t-i}BU_{i-1}$.}

Then we can write
{
\begin{align}
R_{X_t|Z} & = \sum_{i=1}^{t} A^{t-i} B R_{U_{i-1}|Z} B^\prime (A^{t-i})^\prime + 2\Phi_t \label{eq:R_x_t_U_to_X}

\end{align}}

{Therefore, combining \eqref{eq::MirroringPerformanceCausal_input_cond} and~\eqref{eq:R_x_t_U_to_X}}, we express $D_E^{(X)}$ as
\begin{align*}
&D_E^{(X)} \geq \dfrac{1}{T}  \mathbb{E}_Z \sum\limits_{t=1}^{T}  \sum\limits_{i=1}^t \text{tr}\left( A^{t-i} B  R_{U_{i-1}|Z}  B^\prime (A^{t-i})^\prime \right) \\
&\stackrel{(a)}{\geq} \dfrac{1}{T}  \mathbb{E}_Z \sum\limits_{t=1}^{T} \text{tr}\left( B  R_{U_{t-1}|Z}  B^\prime \right) = \dfrac{1}{T}  \mathbb{E}_Z \sum\limits_{t=1}^{T}  \text{tr}\left(B^\prime B  R_{U_{t-1}|Z} \right), \\
&\geq \lambda_{\min}(B^\prime B) \dfrac{1}{T}  \mathbb{E}_Z \sum\limits_{t=1}^{T} \text{tr}\left( R_{U_{t-1}|Z} \right) =\lambda_{\min}(B^\prime B) D_E^{(U)},
\end{align*}
\noindent where $(a)$ follows by noting that the matrices $B^\prime \left(A^{t-i} \right)^\prime R_{U_{i-1}|Z} A^{t-i} B$ are positive semidefinite, and therefore their trace is greater than or equal to zero. To see that they are indeed positive semidefinite, note that $R_{U_{i-1}|Z}$ is positive semidefinite, therefore it has the eigen-decomposition $R_{U_{i-1}|Z} = \Sigma \Lambda \Sigma^\prime$. Therefore, the claim follows by noting that, for any vector $z$, we have
\begin{align*}
&z ^\prime B^\prime \left(A^{t-i} \right)^\prime R_{U_{i-1}|Z} A^{t-i} B z = \\
& z^\prime B^\prime \left(A^{t-i} \right)^\prime \Sigma \Lambda^{1/2} \Lambda^{1/2} \Sigma^\prime A^{t-i} B z = \| \Lambda^{1/2} \Sigma^\prime A^{t-i} B z \|^2 \geq 0.
\end{align*}
{Identical arguments can be made to show the bound on $D_W^{(X)}$.}

\end{IEEEproof}

{Next, we show some sufficient conditions which ensure that condition~\eqref{eq::MirroringPerformanceCausal_input_cond} holds:}\\

\noindent {\it 1) $U_{i}$ and $U_{j}$ are uncorrelated for $i \neq j$ and $U := U_0^{T-1}$ has Point Symmetry:}
In this case, the optimal mirroring scheme is to mirror the point $U$ across the point of symmetry. Therefore, given $Z$, $U_i$ takes two values: $Z_i$ with probability $p_Z$ and $\tilde{Z_i}$ with probability $1-p_Z$, where $p_Z$ is equal to $p_Z  = {f_U(Z)}/(f_U(Z) + f_U(\tilde{Z})) = 0.5$,
which follows from {the Point Symmetry assumption on $U$. {So we have $\mathbb{E} [U_i | Z] = \frac{Z_i +\tilde{Z}_{i}}{2}$.} Therefore,} $R_{U_{i}U_{j}|Z}$ can be computed as follows
{
\begin{align*}
R&_{U_{i} U_{j} | Z } = \mathbb{E}_{U|Z} \left[ \left(U_i - \mathbb{E} [U_i |Z] \right)  \left(U_j - \mathbb{E} [U_j |Z] \right) ^\prime \right]\\

& =  \frac{1}{4} \left(Z_i - \tilde{Z}_i \right) \left(Z_j - \tilde{Z}_j \right)^\prime = \left(Z_i - \mu_{Z_i} \right) \left(Z_j - \mu_{Z_j} \right)^\prime.
\end{align*}
}

{Then we have $E_Z R_{U_i U_j | Z }= R_{U_i U_j} = 0$ by noting that $Z_i, Z_j$ have {the} same {distribution as $U_i, U_j$:}
\begin{align*}
&f_{Z_i, Z_j}(z_i, z_j)  = \frac{1}{2} \left( f_{U_i, U_j} (z_i, z_j) +  f_{U_i, U_j} (\tilde{z}_i, \tilde{z}_j) \right), \\
&= \frac{1}{2} \left( f_{U_i} (z_i) f_{U_j} (z_j) +  f_{U_i} (\tilde{z}_i) f_{U_j} (\tilde{z}_j) \right) =  f_{U_i, U_j} (z_i, z_j).

\end{align*} }

\noindent {\it 2) $A$ and $R_{U_i, U_j | Z}$ are positive semidefinite matrices for all $i$, $j$ and $Z$:} this follows because, if $A$ is positive semidefinite, then so is $A^i$ for any value of $i$. Therefore we can write

{
\begin{align*}
& \text{tr}\left( B^\prime (A^{t-j})^\prime A^{t-i} B R_{U_{i-1}U_{j-1}|Z} \right) \\
&= \text{tr}\left( B^\prime A^{t-j} A^{t-i} B R_{U_{i-1}U_{j-1}|Z} \right) \\
&= \text{tr}\left( B^\prime A^{2t-i-j} B R_{U_{i-1}U_{j-1}|Z} \right)\\
&= \text{tr}\left( B^\prime \Sigma \Lambda^{1/2} \Lambda^{1/2} \Sigma^\prime B R_{U_{i-1}U_{j-1}} \right) \\
&= \text{tr}\left( \Lambda^{1/2} \Sigma^\prime B R_{U_{i-1}U_{j-1}|Z} B^\prime \Sigma \Lambda^{1/2} \right) \\
&= \text{tr}\left( \Lambda^{1/2} \Sigma^\prime B \Phi \Gamma^{1/2} \underbrace{\Gamma^{1/2} \Phi^\prime B^\prime \Sigma \Lambda^{1/2}}_{D} \right) = \text{tr}\left( D^\prime D \right) \geq 0.
\end{align*}}


text:
\section{\revision{red}{Regularized homogeneous interior-point algorithm}}
\label{sec:ipm}

In this section, we describe the homogeneous self-dual formulation and algorithm.
Our implementation largely follows the algorithmic framework of \cite{Xu1996} and \cite{Andersen2000}, \revision{red}{combined with the primal-dual regularization scheme of \cite{Friedlander2012}}.
Consequently, we focus on the algorithm's main components, and refer to \revision{red}{\cite{Xu1996, Andersen2000,Friedlander2012}} for convergence proofs and theoretical results.
Specific implementation details will be further discussed in Section \ref{sec:implementation}.

\subsection{Homogeneous self-dual embedding}
\label{sec:ipm:hsd_model}

	The simplified homogeneous self-dual form was introduced in \cite{Xu1996}.
	It consists in reformulating the primal-dual pair \eqref{eq:standard_LP} as a single, self-dual linear program, which writes
	\begin{align}
        \label{eq:HSD:obj}
        (HSD) \ \ \
        \min_{x, y, \tau} \ \ \
        & 0 \\
        s.t. \ \ \
        \label{eq:HSD:dual}
        & -A^{T}y + c \tau \geq 0,\\
        \label{eq:HSD:primal}
        & Ax  - b \tau = 0,\\
        \label{eq:HSD:gap}
        & - c^{T}x + b^{T}y  \geq 0,\\
        \label{eq:HSD:domain}
        & x, \tau \geq 0,
    \end{align}
	where $\tau$ \revision{red}{is a scalar variable.
	Let $s$, $\kappa$ be the non-negative slacks associated to \eqref{eq:HSD:dual} and \eqref{eq:HSD:gap}, respectively.}
	A solution $(x, y, s, \tau, \kappa)$ is strictly complementary if
	\begin{align*}
		x_{i}s_{i} = 0, x_{i} + s_{i} > 0, \text{ and } \tau \kappa = 0, \tau + \kappa > 0.
	\end{align*}
	Problem $(HSD)$ is always feasible, has empty interior and, under mild assumptions, possesses a strictly complementary feasible solution \cite{Xu1996}.

	Let $(x^{*}, y^{*}, s^{*}, \tau^{*}, \kappa^{*})$ be a strictly complementary feasible solution for $(HSD)$.
	If $\tau^{*} >0$, then $(\frac{x^{*}}{\tau^{*}}, \frac{y^{*}}{\tau^{*}}, \frac{s^{*}}{\tau^{*}})$ is an optimal solution for the original problem \eqref{eq:standard_LP}.
	Otherwise, we have $\kappa^{*} >0$ and thus $c^{T}x^{*} - b^{T}y^{*} < 0$.
	In that case, the original problem (P) is infeasible or unbounded.
	If $c^{T}x^{*} < 0$, then (P) is unbounded and $x^{*}$ is an unbounded ray.
	If $-b^{T}y^{*} < 0$, then (P) is infeasible and $y^{*}$ is an unbounded dual ray.
	The latter is also referred to as a Farkas proof of infeasibility.
	Finally, if both $c^{T}x^{*} < 0$ and $-b^{T}y^{*} < 0$, then both (P) and (D) are infeasible.

\revision{red}{
\subsection{Regularized formulation}

Friedlander and Orban \cite{Friedlander2012} introduce an exact primal-dual regularization scheme for convex quadratic programs, which we extend to the HSD form.
The benefits of regularizations will be further detailed in Section \ref{sec:KKT}.
Importantly, rather than viewing $\HSD$ as a generic LP to which the regularization procedure of \cite{Friedlander2012} is applied, we exploit the fact that $\HSD$ is a self-dual embedding of $(P){-}(D)$, and formulate the regularization in the original primal-dual space.

Thus, we consider a \emph{single}, regularized, self-dual problem
\begin{align}
    \label{eq:rHSD:obj}
    (rHSD) \ \ \
    \min_{x, y, \tau} \ \ \
    & \prho (x - \bar{x})^{T}x + \drho (y - \bar{y})^{T}y + \grho (\tau - \bar{\tau}) \tau \\
    s.t. \ \ \
    \label{eq:rHSD:dual}
    & -A^{T}y + c \tau +  \prho (x - \bar{x}) \geq 0,\\
    \label{eq:rHSD:primal}
    & Ax  - b \tau + \drho (y - \bar{y}) = 0,\\
    \label{eq:rHSD:gap}
    & - c^{T}x + b^{T}y + \grho (\tau - \bar{\tau}) \geq 0,\\
    \label{eq:rHSD:domain}
    & x, \tau, \geq 0,
\end{align}
where $\rho_{p}, \rho_{d}, \rho_{g}$ are positive scalars, and $\bar{x} \in \R^{n}, \bar{y} \in \R^{m}, \bar{\tau} \in \R$ are given estimates of an optimal solution of $\HSD$.
We denote by $s, \kappa$ the non-negative slack variables of constraints \eqref{eq:rHSD:dual} and \eqref{eq:rHSD:gap}, respectively.
The first-order Karush-Kuhn-Tucker (KKT) conditions for $\rHSD$ can then be expressed in the following form:
\begin{align}
    \label{eq:KKT:rHSD:dual}
    \prho x - A^{T}y - s + c \tau &= \prho \bar{x},\\
    \label{eq:KKT:rHSD:primal}
    A x + \drho y - b \tau &= \drho \bar{y},\\
    \label{eq:KKT:rHSD:gap}
    -c^{T}x + b^{T}y + \grho \tau - \kappa &= \grho \bar{\tau},\\
    \label{eq:KKT:rHSD:xs}
    x_{j} s_{j} &= 0, & j=1, ..., n\\
    \label{eq:KKT:rHSD:tk}
    \tau \kappa &= 0,\\
    \label{eq:KKT:rHSD:domain}
    x, s, \tau, \kappa &\geq 0.
\end{align}

The correspondence between $\rHSD$ and \cite{Friedlander2012} follows from the fact that, up to a constant term, the objective function \eqref{eq:rHSD:obj} equals
\begin{align*}
    \frac{1}{2}
    \left(
        \prho \sqnorm{x - \bar{x}} + \drho \sqnorm{y - \bar{y}} + \grho \sqnorm{\tau - \bar{\tau}}
        + \prho \sqnorm{x} + \drho \sqnorm{y} + \grho \sqnorm{\tau}
    \right).
\end{align*}
Note that, for $\prho = \drho = \grho = 0$, the regularized problem $\rHSD$ reduces to $\HSD$.
Furthermore, Theorem \ref{thm:exact_reg} shows that, for positive $\prho, \drho, \grho$, the regularization is exact.

\begin{theorem}
\label{thm:exact_reg}
    Assume $\prho, \drho, \grho > 0$.
    Let $(x^{*}, y^{*}, \tau^{*})$ be a complementary optimal solution of $\HSD$, and let $(\bar{x}, \bar{y}, \bar{\tau}) = (x^{*}, y^{*}, \tau^{*})$ in the definition of $\rHSD$.
    Then, $(x^{*}, y^{*}, \tau^{*})$ is the unique optimal solution of $\rHSD$.
\end{theorem}
\begin{proof}The uniqueness of the optimum is a direct consequence of $\rHSD$ being a convex problem with strictly convex objective.

Next, we show that any feasible solution of $\rHSD$ has non-negative objective.
Let $(x, y, s, \tau, \kappa)$ be a feasible solution of $\rHSD$.
Substituting Eq. \eqref{eq:rHSD:dual}-\eqref{eq:rHSD:gap} into the objective \eqref{eq:rHSD:obj}, one obtains
\begin{align*}
    Z &= \prho (x - \bar{x})^{T}x + \drho (y - \bar{y})^{T}y + \grho (\tau - \bar{\tau}) \tau\\
    & = (A^{T}y + s - c\tau)^{T}x  + (b \tau - Ax)^{T}y + (c^{T}x - b^{T}y + \kappa) \tau\\
    & = x^{T}s + \tau \kappa \geq 0.
\end{align*}
Then, $(x^{*}, y^{*}, \tau^{*})$ is trivially feasible for $\rHSD$, and its objective value is $(x^{*})^{T}s^{*} + \tau^{*} \kappa^{*} = 0$.
Thus, it is optimal for $\rHSD$, which concludes the proof.
\qed
\end{proof}
}

\subsection{\revision{red}{Regularized homogeneous algorithm}}
\label{sec:ipm:hsd_algo}

	We now describe the \revision{red}{regularized} homogeneous interior-point algorithm.
	\revision{red}{
	    Similar to \cite{Friedlander2012}, we apply a single Newton iteration to a sequence of problems of the form $\rHSD$ where, at each iteration, $\bar{x}, \bar{y}, \bar{\tau}$ are chosen to be the current primal-dual iterate.
	}

	Let $(x, y, s, \tau, \kappa)$ denote the current primal-dual iterate, with $(x, s, \tau, \kappa) >0$, and define the residuals
	\begin{align}
		r_{p}  &= b \tau - Ax,\\
		r_{d}  &= c \tau - A^{T}y - s,\\
		r_{g}  &= c^{T}x - b^{T}y + \kappa,
	\end{align}
	and the barrier parameter
	\[
		\mu = \dfrac{x^{T}s + \tau \kappa}{n+1}.
	\]

	\revision{red}{For given $\bar{x}, \bar{y}, \bar{\tau}$,}
	a search direction $(\delta_{x}, \delta_{y}, \delta_{s}, \delta_{\tau}, \delta_{\kappa})$ is computed by solving a Newton system of the form
	\revision{red}{
	\begin{align}
        \label{eq:Newton:dual}
		-\prho \delta_{x} + A^{T} \delta_{y} + \delta_{s} - c \delta_{\tau}
		    &= \eta \left( c \tau - A^{T}y - s + \prho (\bar{x} - x) \right),\\
		\label{eq:Newton:primal}
		A \delta_{x} + \drho \delta_{y} - b \delta_{\tau}
		    &= \eta \left( b \tau - Ax - \drho(y - \bar{y}) \right),\\
		\label{eq:Newton:gap}
	    -c^{T} \delta_{x} + b^{T} \delta_{y} + \grho \delta_{\tau} - \delta_{\kappa}
	        &= \eta \left( c^{T}x - b^{T}y + \kappa - \grho (\tau - \bar{\tau}) \right),\\
	    \label{eq:Newton:xs}
	    S \delta_{x} + X \delta_{s}
	        &= -XSe + \gamma \mu e,\\
	    \label{eq:Newton:tk}
		\kappa \delta_{\tau} + \tau \delta_{\kappa}
		    &= -\tau \kappa + \gamma \mu,
	\end{align}}
	where $\gamma$ and $\eta$ are non-negative scalars \revision{red}{whose values will be specified in Section \ref{sec:ipm:algo:direction}}.
	\revision{red}{
	We evaluate the Newton system at $(\bar{x}, \bar{y}, \bar{\tau}) = (x, y, \tau)$, which yields
	\begin{align}
	    \label{eq:Newton:reg}
	    \begin{bmatrix}
	        -\prho I && A^{T} && I && -c && 0\\
	        A && \drho I && 0 && -b && 0\\
	        -c^{T} && b^{T} && 0 && \grho && -1\\
	        S && 0 && X && 0 && 0\\
	        0 && 0 && 0 && \kappa && \tau
	    \end{bmatrix}
	    \begin{bmatrix}
	        \delta_{x}\\
	        \delta_{y}\\
	        \delta_{s}\\
	        \delta_{\tau}\\
	        \delta_{\kappa}
	    \end{bmatrix}
	    =
	    \begin{bmatrix}
	        \eta r_{d}\\
	        \eta r_{p}\\
	        \eta r_{g}\\
	        -XSe + \gamma \mu e\\
	        -\tau \kappa + \gamma \mu
	    \end{bmatrix}
	    .
	\end{align}
	System \eqref{eq:Newton:reg} is identical to the Newton system obtained when solving $\HSD$ (see, e.g., \cite{Andersen2000}), except for the regularization terms that appear in the left-hand side.
	In particular, the right-hand side remains unchanged.
	}

\iffalse

	It then follows \cite{Andersen2000} that
	\begin{align}
		\label{eq:residuals_update}
		(r_{p}^{+}, r_{d}^{+}, r_{g}^{+}) &= (1 - \alpha \eta) (r_{p}, r_{d}, r_{g}),
	\end{align}
	and
	\begin{align}
		\label{eq:complementary_update}
		(x^{+})^{T}s^{+} + \tau^{+}\kappa^{+} &= \left( 1 - \alpha (1-\gamma) + \alpha^{2} \eta (1 - \gamma - \eta) \right) (x^{T} s + \tau \kappa).
	\end{align}
	Consequently, if $\eta = 1 - \gamma$, then infeasibility and optimality gap are decreased by the same factor $(1-\alpha \eta)$.
	This remarkable property contrasts with classical infeasible primal-dual algorithms such as \cite{Mehrotra1992}, in which feasibility is often reached earlier than optimality.
\fi

\subsubsection{Starting point}

	We choose the following default starting point
	\[
		(x^{0}, y^{0}, s^{0}, \tau^{0}, \kappa^{0}) = (e, 0, e, 1, 1).
	\]
	This initial point was proposed in \cite{Xu1996}.
	Besides its simplicity, it has well-balanced \revision{blue}{complementarity} products, which are all equal to one.

\subsubsection{Search direction}
\label{sec:ipm:algo:direction}

	At each iteration, a search direction is computed using Mehrotra's predictor-corrector technique \cite{Mehrotra1992}, combined with Gondzio's multiple centrality corrections \cite{Gondzio1996_correction}.
	Following \cite{Andersen2000}, we adapt the original formulas of \cite{Mehrotra1992, Gondzio1996_correction} to account for the homogeneous embedding.

	First, the affine-scaling direction $(\delta^{\text{aff}}_{x}, \delta^{\text{aff}}_{y}, \delta^{\text{aff}}_{s}, \delta^{\text{aff}}_{\tau}, \delta^{\text{aff}}_{\kappa})$ is obtained 	by solving the Newton system
	\begin{align}
		\label{eq:NS_aff_dual}
		\revision{red}{-\prho \delta^{\text{aff}}_{x}} + A^{T} \delta^{\text{aff}}_{y} + \delta^{\text{aff}}_{s} - c \delta^{\text{aff}}_{\tau} &= r_{d},\\
		\label{eq:NS_aff_primal}
		 A \delta^{\text{aff}}_{x} \revision{red}{+ \drho \delta^{\text{aff}}_{y}} -b \delta^{\text{aff}}_{\tau} &= r_{p},\\
		\label{eq:NS_aff_opt}
	    -c^{T} \delta^{\text{aff}}_{x} + b^{T} \delta^{\text{aff}}_{y} \revision{red}{+ \grho \delta^{\text{aff}}_{\tau}} -\delta^{\text{aff}}_{\kappa} &= r_{g},\\
	    \label{eq:NS_aff_comp_xs}
	    S \delta^{\text{aff}}_{x} + X \delta^{\text{aff}}_{s} &= -XSe,\\
	    \label{eq:NS_aff_comp_tk}
		\kappa \delta^{\text{aff}}_{\tau} + \tau \delta^{\text{aff}}_{\kappa} &= -\tau \kappa,
	\end{align}
	which corresponds to \revision{red}{\eqref{eq:Newton:reg} with} $\eta=1$ and $\gamma=0$.
	Taking a full step ($\alpha=1$) would thus reduce both infeasibility and \revision{blue}{complementarity} gap to zero.
	However, doing so is generally not possible, due to the non-negativity requirement on $(x, s, \tau, \kappa)$.

	Consequently, a corrected search direction is computed, as proposed in \cite{Mehrotra1992}.
	The corrected direction hopefully enables one to make longer steps, thus reducing the total number of IPM iterations.
	Let $\eta = 1 - \gamma$, where
	\begin{align}
		\gamma = (1 - \alpha^{\text{aff}})^{2} \min\left( \revision{blue}{\gamma_{min}}, (1 - \alpha^{\text{aff}}) \right)
	\end{align}
	for some $\revision{blue}{\gamma_{min}} > 0$, and
	\begin{align}
		\alpha^{\text{aff}} = \max \left\{ 0 \leq \alpha \leq 1 \mid (x, s, \tau, \kappa) + \alpha (\delta^{\text{aff}}_{x}, \delta^{\text{aff}}_{s}, \delta^{\text{aff}}_{\tau}, \delta^{\text{aff}}_{\kappa}) \geq 0 \right\} .
	\end{align}
	The corrected search direction is then given by
	\begin{align}
		\label{eq:NS_cor_dual}
		\revision{red}{-\prho \delta_{x}} + A^{T} \delta_{y} + \delta_{s} - c \delta_{\tau}			&= \eta r_{d},\\
		\label{eq:NS_cor_primal}
		 A \delta_{x} \revision{red}{+ \drho \delta_{y}} -b \delta_{\tau} 							&= \eta r_{p},\\
		\label{eq:NS_cor_opt}
	    -c^{T} \delta_{x} + b^{T} \delta_{y} \revision{red}{+ \grho \delta_{\tau}} -\delta_{\kappa}   	&= \eta r_{g},\\
	    \label{eq:NS_cor_comp_xs}
	    S \delta_{x} + X \delta_{s}                   			&= -XSe + \gamma \mu e - \Delta_{x}^{\text{aff}} \Delta_{s}^{\text{aff}} e,\\
	    \label{eq:NS_cor_comp_tk}
		\kappa \delta_{\tau} + \tau \delta_{\kappa}   			&= -\tau \kappa + \gamma \mu - \delta_{\tau}^{\text{aff}} \delta_{\kappa}^{\text{aff}},
	\end{align}
	where $\Delta^{\text{aff}}_{x} = Diag(\delta^{\text{aff}}_{x})$ and $\Delta^{\text{aff}}_{s}=Diag(\delta^{\text{aff}}_{s})$.

\subsubsection{\revision{red}{Additional centrality corrections}}
	\revision{red}{Additional centrality corrections}
	aim at improving the centrality of the new iterate, i.e., to keep the complementary products well balanced.
	Doing so generally allows to make longer steps, thus reducing the total number of IPM iterations.
	We implement Gondzio's original technique \cite{Gondzio1996_correction}, with some modifications introduced in \cite{Andersen2000}.

	Let $\delta = (\delta_{x}, \delta_{y}, \delta_{s}, \delta_{\tau}, \delta_{\kappa})$ be the current search direction, $\alpha^{max}$ the corresponding maximum step size, and define
	\begin{align}
		(\bar{x}, \bar{y}, \bar{s}, \bar{\tau}, \bar{\kappa}) := (x, y, s, \tau, \kappa) + \bar{\alpha} (\delta_{x}, \delta_{y}, \delta_{s}, \delta_{\tau}, \delta_{\kappa}),
	\end{align}
	where $\bar{\alpha} := \min(1, 2 \alpha^{max})$ is a tentative step size.

	First, a soft target in the space of \revision{blue}{complementarity} products is computed as
	\begin{align}
		t_{j} &=
		\left\{
		\begin{array}{cl}
			\mu_{l} - \bar{x}_{j} \bar{s}_{j} & \text{ if } \bar{x}_{j} \bar{s}_{j} < \mu_{l}\\
			0 & \text{ if } \bar{x}_{j} \bar{s}_{j} \in [\mu_{l}, \mu_{u}]\\
			\mu_{u} - \bar{x}_{j} \bar{s}_{j} & \text{ if } \bar{x}_{j} \bar{s}_{j} > \mu_{u}
		\end{array}
		\right.
		, \ \
		j = 1, \dots, n,\\
		t_{0} &=
		\left\{
		\begin{array}{cl}
			\mu_{l} - \bar{\tau} \bar{\kappa} & \text{ if } \bar{\tau} \bar{\kappa} < \mu_{l}\\
			0 & \text{ if } \bar{\tau} \bar{\kappa} \in [\mu_{l}, \mu_{u}]\\
			\mu_{u} - \bar{\tau} \bar{\kappa} & \text{ if } \bar{\tau} \bar{\kappa} > \mu_{u}
		\end{array}
		\right.
		,
	\end{align}
	where $\mu_{l} = \gamma \mu \beta$ and $\mu_{u} = \gamma \mu \beta^{-1}$, for a fixed $0 < \beta \leq 1$.
	Then, define
	\begin{align}
		v &= t - \dfrac{e^{T}t + t_{0}}{n+1} e,\\
		v_{0} &= t_{0} - \dfrac{e^{T}t + t_{0}}{n+1}.
	\end{align}
	A correction is obtained by solving the linear system
	\begin{align}
		\label{eq:NS_cor2_dual}
		\revision{red}{-\prho \delta^{c}_{x}} + A^{T} \delta^{c}_{y} + \delta^{c}_{s} - c \delta^{c}_{\tau}			&= 0,\\
		\label{eq:NS_cor2_primal}
		 A \delta^{c}_{x} \revision{red}{+ \drho \delta^{c}_{y}} -b \delta^{c}_{\tau} 							&= 0,\\
		\label{eq:NS_cor2_opt}
	    -c^{T} \delta^{c}_{x} + b^{T} \delta^{c}_{y} \revision{red}{+ \grho \delta^{c}_{\tau}} -\delta^{c}_{\kappa}   	&= 0,\\
	    \label{eq:NS_cor2_comp_xs}
	    S \delta^{c}_{x} + X \delta^{c}_{s}                   			&= v,\\
	    \label{eq:NS_cor2_comp_tk}
		\kappa \delta^{c}_{\tau} + \tau \delta^{c}_{\kappa}   			&= v_{0},
	\end{align}
	which yields a corrected search direction
	\begin{align*}
		(
			\delta_{x},
			\delta_{y},
			\delta_{s},
			\delta_{\tau},
			\delta_{\kappa}
		) +
		(
			\delta^{c}_{x},
			\delta^{c}_{y},
			\delta^{c}_{s},
			\delta^{c}_{\tau},
			\delta^{c}_{\kappa}
		).
	\end{align*}
	The corrected direction is accepted if it results in an increased step size.

	Finally, additional centrality corrections are computed only if a sufficient increase in the step size is observed.
	Specifically, as suggested in \cite{Andersen2000}, an additional correction is computed only if the new step size $\alpha$ satisfies
	\begin{align}
		\label{eq:test_keep_correcting}

		\alpha \geq 1.10 \times \alpha^{\text{max}}.
	\end{align}

\revision{red}{
\subsubsection{Regularizations}

    Following \cite{Friedlander2012}, the regularizations are updated as follows.
    Let $\prho^{k}, \drho^{k}, \grho^{k}$ denote the regularization terms at iteration $k$.
    We set $\prho^{0} = \drho^{0} = \grho^{0} = 1$, and use the update rule
    \begin{align}
        \prho^{k+1} = \max \left( \sqrt{\epsilon}, \frac{\prho^{k}}{10} \right),\\
        \drho^{k+1} = \max \left( \sqrt{\epsilon}, \frac{\drho^{k}}{10} \right),\\
        \grho^{k+1} = \max \left( \sqrt{\epsilon}, \frac{\grho^{k}}{10} \right),
    \end{align}
    where $\epsilon$ denotes the machine precision, e.g., $\epsilon \simeq 10^{-16}$ for double-precision floating point arithmetic.

    Further details on the role of regularizations in the resolution of the Newton system are given in Section \ref{sec:KKT}.
    Let us only mention here that $\prho, \drho, \grho$ may become too small to ensure that the Newton system is properly regularized, e.g., for badly scaled problems.
    When this is the case, we increase the regularizations by a factor of $100$, and terminate the algorithm if three consecutive increases fail to resolve the numerical issues.
}

\subsubsection{Step size}

	Once the final search direction has been computed, the step size $\alpha$ is given by
	\begin{align}
		\alpha = 0.9995 \times \alpha^{max},
	\end{align}
	where
	\begin{align*}
		 \alpha^{max} = \max \left\{ 0 \leq \alpha \leq 1 \mid (x, s, \tau, \kappa) + \alpha (\delta_{x}, \delta_{s}, \delta_{\tau}, \delta_{\kappa}) \geq 0 \right\}.
	\end{align*}

\subsubsection{Stopping criteria}
\label{sec:ipm:stoppingCriteria}

	The algorithm stops when, up to numerical tolerances, one of the following three cases holds: the current iterate is optimal, the primal problem is proven infeasible, the dual problem is proven infeasible (unbounded primal).

	The problem is declared solved to optimality if
	\begin{align}
		\label{eq:stop_primalfeas}
		\dfrac{\normInf{r_{p}}}{\tau (1 + \normInf{b})} &< \varepsilon_{p},\\
		\label{eq:stop_dualfeas}
		\dfrac{\normInf{r_{d}}}{\tau (1 + \normInf{c})} &< \varepsilon_{d},\\
		\label{eq:stop_opt}
		\dfrac{|c^{T}x - b^{T}y|}{\tau + |b^{T}y|} &< \varepsilon_{g},
	\end{align}
	where $\varepsilon_{p}, \varepsilon_{d}, \varepsilon_{g}$ are positive parameters.
	The above criteria are independent of the magnitude of $\tau$, and correspond to primal feasibility, dual feasibility and optimality, respectively.

	Primal or dual infeasibility is detected if
	\begin{align}
		\label{eq:stop_inf_mu}
		\mu &< \varepsilon_{i},\\
		\label{eq:stop_inf_tau}
		\frac{\tau}{\kappa} &< \varepsilon_{i},
	\end{align}
	where $\varepsilon_{i}$ is a positive parameter.
	When this is the case, a \revision{blue}{complementary} solution with small $\tau$ has been found.
	If $c^{T}x < - \varepsilon_{i}$, the problem is declared dual infeasible (primal unbounded), and $x$ is an unbounded ray.
	If $-b^{T}y < - \varepsilon_{i}$, the problem is declared primal infeasible (dual unbounded), and $y$ is a Farkas dual ray.

	Finally, premature termination criteria such as numerical instability, time limit or iteration limit are discussed in Section \ref{sec:implementation}.


TITLE: Is the function $F(x)=\int_{0}^{x} f(t) dt$ differentiable at 0?
QUESTION [4 upvotes]: Let
$$
f(x)=\left\{\begin{matrix}
\cos\frac{1}{x} & x\neq0\\
0, & x=0
\end{matrix}\right.$$
I think the answer is not differentiable at 0 because of the chain rule, but I don't know how to prove it.

REPLY [5 votes]: It is indeed differentiable with derivative zero: Of course, $\int_0^h \cos(1/x)\;\mathrm dx\to 0$, and it happens to go very quickly. This can be seen by a change of variables as follows.
$$
\int_0^h \cos(1/x)\;\mathrm dx=\int_{1/h}^\infty \frac{\cos(x)}{x^2}\mathrm dx
$$
which is easier to analyze. Namely, through an integration by parts
$$
\int_{1/h}^\infty \frac{\cos(x)}{x^2}\mathrm dx=
-h^2\sin(1/h)+\int_{1/h}^\infty \frac{2}{x^3}\sin(x)\;\mathrm dx
$$
so,
$$
\left|\int_{1/h}^\infty \frac{\cos(x)}{x^2}\mathrm dx\right|=
\left|-h^2\sin(1/h)+\int_{1/h}^\infty \frac{2}{x^3}\sin(x)\;\mathrm dx \right|\\
\leq
h^2|\sin(1/h)|+\int_{1/h}^\infty \frac{2|\sin(x)|}{x^3}\;\mathrm dx
$$
by the triangle inequality. Evaluating the integral and using the obvious bound on $\sin$ we have
$$
\left|\int_{1/h}^\infty \frac{\cos(x)}{x^2}\mathrm dx\right|\leq
2h^2
$$
Using the above in the difference quotient:
$$
\left|\frac{1}{h}\int_0^h \cos(1/x)\;\mathrm dx\right|=
\left|\frac{1}{h}\int_{1/h}^\infty \frac{\cos(x)}{x^2}\mathrm dx\right|\leq
2|h|\to 0
$$
Remark: If you keep playing the integration by parts game, you'll see it actually vanishes to the order of $O(h^n)$ for any $n\in \mathbb{N}$, i.e. faster than any polynomial.


TITLE: Showing that the limit exists for a function in a Banach space
QUESTION [1 upvotes]: Let E be a normed space and F a Banach space. Suppose we have A ⊂ E, $x_o$ ∈ Acc(A) and
f : A → F , a function uniformly continuous. Show that lim x→x0 of f(x) exists.

REPLY [0 votes]: As $x_0 \in \operatorname{Acc}(A)$, it exists a sequence $(x_n)$ in $A$ such that $\lim\limits_{n \to \infty} x_n =x_0$. As $f$ is uniformly continuous, you’ll be able to prove that the sequence $(f(x_n))$ is Cauchy. As $F$ is a Banach space, $(f(x_n))$ converges let’s say to $y_0$.
Now if you take any sequence $(x_n^\prime)$ of $A$ converging to $x_0$, $(f(x_n^\prime))$ converges to $y_0$ according to $f$ uniform continuity. Which provides the result that $\lim\limits_{x \to x_0} f(x) =y_0$.