\section{Introduction and statement of results}

The main contribution of this paper shows a surprising relation that holds between two well-established areas of research, proximity and sparsity of solutions to integer programs, in the case of  Gomory's corner polyhedra.

The proximity-type results provide estimates for the distance between optimal vertex solutions of linear programming relaxations and feasible integer points, with seminal works by Cook et al. \cite{MR839604} and, more recently, by Eisenbrand and Weismantel \cite{MR3775840}.
The sparsity-type results, in their turn, provide bounds for the size of support of feasible integer points and solutions to integer programs. Bounds of this type are dated back to the classical integer Carath\'eodory theorems of Cook, Fonlupt and Schriver \cite{MR830593} and Seb\H{o} \cite{Sebo}. More recent contributions include results of Eisenbrand and Shmonin \cite{EisenbrandShmonin2006} and Aliev et al. \cite{ADON2017,Support, AADO}.  Further, in a very recent work Lee, Paat, Stallknecht and Xu \cite{LPSX} apply new sparsity-type bounds to refine the bounds for proximity.

To state the main results of this paper, we will need the following notation. Let $A \in \mathbb Z^{m\times n}$, $m<n$,
 and let $\tau=\{i_1,\ldots,i_k\} \subseteq  \{1,\ldots,n\}$ with $i_1<i_2<\cdots<i_k$. We will use the notation  $A_\tau$ for the $m \times k$ submatrix  of $A$ with columns indexed by $\tau$.  In the same manner, given ${\boldsymbol x}\in \mathbb R^n$, we will denote by ${\boldsymbol x}_{\tau}$ the vector $(x_{i_1}, \ldots, x_{i_k})^{\top}$. The complement of $\tau$ in $ \{1,\ldots, n\}$ will be denoted as $\bar\tau$. We will say that $\tau$ is a {\em basis} of $A$ if $|\tau|=m$ and the submatrix $A_{\tau}$  is nonsingular. By $\Sigma(A)$ we will denote the maximum absolute $m\times m$ subdeterminant of $A$:
\begin{eqnarray*}
\Sigma(A)=\max\{|\det(A_{\tau})|: \tau\subset \{1,\ldots, n\} \mbox{ with } |\tau|= m \}\,.
\end{eqnarray*}
When $\Sigma(A)$ is positive, $\gcd(A)$ will denote the greatest common divisor of all $m \times m$ subdeterminants of $A$.

For ${\boldsymbol x}=(x_1, \ldots, x_n)^{\top}\in \mathbb R^n$, the $\ell_{\infty}$-norm of ${\boldsymbol x}$ will be denoted as $\|{\boldsymbol x}\|_{\infty}$.   We will denote by $\supp({\boldsymbol x})=\{i : x_i \not= 0\}$ the {\em support} of ${\boldsymbol x}$. Further, $\|{\boldsymbol x}\|_0:=|\supp({\boldsymbol x})|$ will denote the $0$-``norm'', widely used in the theory of {compressed sensing} \cite{candestao,CS_survey}, which counts the cardinality of the support of ${\boldsymbol x}$.

Let $A \in \mathbb Z^{m\times n}$ with $m<n$ and $\boldsymbol b \in \mathbb Z^m $. We will consider the polyhedron
\begin{eqnarray*}
{P}(A, {\boldsymbol b})=\{{\boldsymbol x}\in \mathbb R^n_{\ge 0}: A{\boldsymbol x}={\boldsymbol b}\}
\end{eqnarray*}
and take any vertex $\boldsymbol x^*$  of ${P}(A, {\boldsymbol b})$.  %
Without loss of generality, we may assume that
\begin{eqnarray}\label{matrix_partition}
A=(A_{\gamma}, A_{\bar \gamma})\in \mathbb Z^{m\times n} \mbox{ with nonsingular } A_{\gamma}\,,
\end{eqnarray}
\begin{eqnarray}\label{vertex_assumption}
 {\boldsymbol x}^*_\gamma = A_\gamma^{-1}{\boldsymbol b} \mbox{ and }{\boldsymbol x}^*_{\bar \gamma}={\boldsymbol 0}\,.
\end{eqnarray}
In general, there can be many choices for the basis $\gamma$. However, if ${\boldsymbol x}^*$ is \emph{nondegenerate}; that is, if the size of the support of ${\boldsymbol x}^*$ is $m$, then there is a unique choice for $\gamma$, namely $\gamma=\supp({\boldsymbol x})$.  For convenience, throughout this paper we will assume, given a choice for $\gamma$, that
\begin{eqnarray*} \gamma= \{1, \ldots, m\}\,.\end{eqnarray*}
For a set ${S}\subset \mathbb R^n$ we will denote by $\mathrm{conv}({S})$ the {\em convex hull} of ${S}$.  Gomory  \cite{Gomory_polyhedra} introduced  the {\em corner polyhedron} $\CP_{\gamma}(A, {\boldsymbol b})$ associated with $\gamma$ as
\begin{eqnarray*}\label{corner_polyhedron}
\CP_{\gamma}(A, {\boldsymbol b})=\mathrm{conv} (\{{\boldsymbol x}\in \mathbb Z^n: A{\boldsymbol x}={\boldsymbol b},  {\boldsymbol x}_{\bar \gamma}\ge 0\})\,.
\end{eqnarray*}

\begin{thm}\label{t:IPTP_general}
Suppose that  $A$ satisfies \eqref{matrix_partition}, ${\boldsymbol b}\in \mathbb Z^m$,  $\boldsymbol x^*$ is given by \eqref{vertex_assumption} and the corner polyhedron $\CP_{\gamma}(A, {\boldsymbol b})$ is nonempty.
Let ${\boldsymbol z}^{*}$  be a vertex of  $\CP_{\gamma}(A, {\boldsymbol b})$ and let $r=\|{\boldsymbol z}^{*}_{\bar\gamma}\|_0$. Then
\begin{equation}\label{eq:r_equals_0}
{\boldsymbol x}^{*}={\boldsymbol z}^{*} \mbox{ if } r= 0\,,
\end{equation}
\begin{equation}\label{eq:r_equals_1}
\|{\boldsymbol x}^{*}-{\boldsymbol z}^{*}\|_{\infty} \le \frac{\Sigma(A)}{\gcd(A)}-1 \mbox{ if } r= 1 \mbox{ and }
\end{equation}
\begin{equation}\label{eq:r_greater_1}
\|{\boldsymbol x}^{*}-{\boldsymbol z}^{*}\|_{\infty} \,\frac{2^{r}}{r} \leq \frac{\Sigma(A)}{\gcd(A)} \mbox{ if } r\ge 2\,.
\end{equation}
\end{thm}

The bounds \eqref{eq:r_equals_1} and \eqref{eq:r_greater_1} are optimal. Specifically, \eqref{eq:r_equals_1} is attained already in the knapsack scenario (with the choice of parameters
\eqref{optimal_example_r_equals_1}). The bound \eqref{eq:r_greater_1}, in its turn, is attained for
\begin{eqnarray*}
A= \left(\begin{array}{cccc}
2 & 0 & 5 & 5\\
0 & 4 & 2 &-1
\end{array}
\right)\,,\;
{\boldsymbol b}=\left(\begin{array}{c}
20\\
3
\end{array}
\right)\mbox{ and }
\end{eqnarray*}
the vertex ${\boldsymbol x}^*=(10, 3/4, 0, 0)^{\top}$ of ${P}(A, {\boldsymbol b})$. For this choice of parameters the corner polyhedron $\CP_{\gamma}(A, {\boldsymbol b})$
has the unique vertex  ${\boldsymbol z}^{*}= (0,1,1,3)^{\top}$.

Theorem \ref{t:IPTP_general} shows that for the corner polyhedron associated with a vertex ${\boldsymbol x}^*$ of ${P}(A, {\boldsymbol b})$ a strong {\em proximity-sparsity transference} holds: the distance from ${\boldsymbol x}^*$ to any vertex ${\boldsymbol z}^*$ of the corner polyhedron {\em exponentially} drops with the size of support of ${\boldsymbol z}^*$ and, vice versa, the size of support of ${\boldsymbol z}^*$ reduces with the growth of its distance to ${\boldsymbol x}^*$ .

Suppose next that the polyhedron ${P}(A, {\boldsymbol b})$ is integer feasible and consider its {\em integer hull} ${P}_I= \mathrm{conv}({P}(A, {\boldsymbol b})\cap \mathbb Z^n)$.
A natural direction for a further research would be to derive a distance-sparsity transference bound for the vertices of ${P}_I$. Notice that the set ${P}(A, {\boldsymbol b})\cap \mathbb Z^n$ is obtained from $\CP_{\gamma}(A, {\boldsymbol b})\cap\mathbb Z^n$ by enforcing back the nonnegativity constraints  $ {\boldsymbol x}_{\gamma}\ge 0$ and this may potentially result in cutting off all vertices of the corner polyhedron. In Section \ref{knapsackintro} we show that in the knapsack scenario at least one vertex of $\CP_{\gamma}(A, {\boldsymbol b})$ avoids the cut and Theorem \ref{t:IPTP_general} implies an optimal  distance-sparsity transference bound for lattice points in the knapsack polytope.

Although it remains an open problem to extend Theorem \ref{t:IPTP_general} to vertices of  ${P}_I$ in the general setting, the next result of this paper allows enforcing back the constraints $ {\boldsymbol x}_{\gamma}\ge 0$ that are tight at ${\boldsymbol x}^*$ when $\tau:=\supp({\boldsymbol x}^*)$ has size strictly less than $m$. In this situation, following \cite{thomas2005structure}, we may define the polyhedron
\begin{eqnarray*}
\CP_{\tau}(A,\ve b)=\mathrm{conv}(\{\ve x\in\mathbb Z^{n}:A\ve x=\ve b,\ve x_{\bar{\tau}}\geq\mathbf{0}\}).
\end{eqnarray*}
In this setting the choice of basis $\gamma$ in \eqref{matrix_partition} is typically not unique. However, we show is that there exists at least one basis $\gamma$ for which the conclusions of Theorem~\ref{t:IPTP_general} remain valid for this polyhedron, up to a factor which depends on the number of zero coordinates of $\ve x_{\tau}^*$.

\begin{thm}
\label{thm:upper_bound_extension}
Suppose that $A$ satisfies \eqref{matrix_partition} and ${\boldsymbol b}\in \mathbb Z^m$. Let  $\boldsymbol x^*$ be given by \eqref{vertex_assumption} and let $\tau=\supp(\ve x^{*})$. Let $\ve z^{*}$ be a vertex of the polyhedron $\CP_{\tau}(A,\ve b)$. Then the basis $\gamma$ in \eqref{matrix_partition} may be chosen so that, letting $r=\|{\boldsymbol z}^{*}_{\bar\gamma}\|_0$ and $d=m-\left|\tau\right|$, we have
\begin{equation}\label{eq:r_equals_0_extension}
{\boldsymbol x}^{*}={\boldsymbol z}^{*} \mbox{ if } r= 0\,,
\end{equation}
\begin{equation}\label{eq:r_equals_1_extension}
\|{\boldsymbol x}^{*}-{\boldsymbol z}^{*}\|_{\infty} \le \frac{\Sigma(A)}{\gcd(A)}-1 \mbox{ if } r= 1 \mbox{ and }
\end{equation}
\begin{equation}\label{eq:r_greater_1_extension}
\|{\boldsymbol x}^{*}-{\boldsymbol z}^{*}\|_{\infty} \,\frac{2^{r}}{r^{d+1}} \leq \frac{\Sigma(A)}{\gcd(A)} \mbox{ if } r\ge 2\,.
\end{equation}
\end{thm}
We remark that integer programs of the form $A\ve x=\ve b,\ve x_{\bar{\tau}}\geq\mathbf{0}, \ve x\in\mathbb Z^n$, where $\tau$ is the support of a vertex of ${P}(A, {\boldsymbol b})$, have been investigated in \cite{thomas2005structure}. Such an integer program is called a \emph{Gomory relaxation with respect to $\tau$}. See in particular \cite[\S 2]{thomas2005structure} for more details.

\subsection{Distance-sparsity transference for knapsacks}\label{knapsackintro}

We will now separately consider the case $A\in \mathbb Z_{>0}^{1\times n}$, known as {\em knapsack scenario}. We will follow a traditional vector notation and replace $A$ and ${\boldsymbol b}$ with a positive integer vector ${\boldsymbol a}=(a_1, \ldots, a_n)^{\top} \in \mathbb Z^{n}_{>0}$ and integer $b\in\mathbb Z$.
In this setting ${P}(A, {\boldsymbol b})$ is referred to as the  {\em knapsack polytope}
\begin{eqnarray*}
{P}({\boldsymbol a},b)=\{{\boldsymbol x}\in \mathbb R^n_{\ge 0}: {\boldsymbol a}^{\top}{\boldsymbol x}=b\}\,.
\end{eqnarray*}
In what follows, we will exclude the trivial case $n=1$ and assume that $n\ge 2$. We also assume that the polytope ${P}({\boldsymbol a}, b)$ contains integer points. Equivalently, ${b}$ belongs to the \emph{semigroup}
\begin{equation*}
\icone({\boldsymbol a}) = \{{\boldsymbol a}^{\top}{\boldsymbol z}: {\boldsymbol z} \in \ZZ^n_{\ge 0} \}
\end{equation*}
generated by the entries of the vector ${\boldsymbol a}$. Note that any element of the semigroup $\icone({\boldsymbol a}) $ must be divisible by the greatest common divisor $\gcd(a_1, \ldots, a_n)$ of $a_1, \ldots, a_n$. Hence, we may assume without loss of generality that ${\boldsymbol a}$  satisfies the following conditions:
\begin{eqnarray} \label{positive_primitive}
\begin{array}{l}
{\boldsymbol a}=(a_1, \ldots, a_n)^{\top} \in \mathbb Z^{ n}_{>0}\,,n\ge 2\,, \text{ and }
\gcd(a_1, \ldots, a_n)=1\,.
\end{array}
\end{eqnarray}

Aliev et al \cite[Theorem 1] {AHO} proved that for any vertex ${\boldsymbol x}^{*}$ of the polytope ${P}({\boldsymbol a},b)$ there exists an integer point ${\boldsymbol z}\in  {P}({\boldsymbol a},b)$ such that
\begin{eqnarray}\label{AHO_bound}
\|{\boldsymbol x}^{*}-{\boldsymbol z}\|_{\infty}\le \|{\boldsymbol a}\|_\infty -1
\end{eqnarray}
and that the bound (\ref{AHO_bound}) is sharp in the following sense.
For any positive integer $k$ and any dimension $n$ there exist ${\boldsymbol a}$ satisfying (\ref{positive_primitive}) with $\|{\boldsymbol a}\|_{\infty}=k$  and $b\in \mathbb Z$ such that
the knapsack polytope ${P}({\boldsymbol a},b)$ contains exactly one integer point ${\boldsymbol z}$ and $\|{\boldsymbol x}^{*}-{\boldsymbol z}\|_{\infty}=\|{\boldsymbol a}\|_\infty-1$.

The best known sparsity-type estimate in the knapsack scenario \eqref{positive_primitive}, obtained in  \cite[Theorem 6]{AADO}, guarantees existence of an integer point  ${\boldsymbol z}\in {P}({\boldsymbol a},b)$ that satisfies the bound
 %
 \begin{eqnarray}\label{sparse_knapsack}
 \|{\boldsymbol z}\|_0\le 1 + \log(\min\{a_1, \ldots, a_n\})\,.
 \end{eqnarray}
The next result will combine and refine the bounds (\ref{AHO_bound}) and (\ref{sparse_knapsack}) as follows.
The knapsack polytope ${P}({\boldsymbol a}, b)$ is an $(n-1)$-dimensional simplex in $\mathbb R^n$ with vertices $({b}/{a_1})\boldsymbol{e}_1, \ldots, ({b}/{a_n})\boldsymbol{e}_n$,
where $\boldsymbol{e}_i$ denotes the $i$-th standard basis vector.
Hence, without loss of generality, we may assume that the vertex ${\boldsymbol x}^{*}$ has the form
\begin{eqnarray}\label{knapsack_vertex} {\boldsymbol x}^{*}=\frac{b}{a_1}{\boldsymbol e}_1\,.
\end{eqnarray}
The corner polyhedron associated with the vertex ${\boldsymbol x}^{*} $ (with $\gamma=\{1\}$) can be written as
$\CP_{\gamma}({\boldsymbol a}, {b})=\mathrm{conv} (\{{\boldsymbol x}\in \mathbb Z^n: {\boldsymbol a}^{\top}{\boldsymbol x}={ b},  x_2\ge 0, \ldots, x_n\ge 0\})$.
\begin{thm}\label{t:IPTP_positive_knapsack}
Let ${\boldsymbol a}$ satisfy (\ref{positive_primitive}), $b\in\icone({\boldsymbol a})$ and ${\boldsymbol x}^{*}$ is given by \eqref{knapsack_vertex}. Then $ {P}({\boldsymbol a}, {b})$ contains a vertex ${\boldsymbol z}^{*}$ of $\CP_{\gamma}({\boldsymbol a}, {b}) $ with $r=\|(z^*_2,\ldots, z^*_n)^{\top}\|_0$  such that
\begin{equation}\label{eq:r_equals_0_knapsack}
{\boldsymbol x}^{*}={\boldsymbol z}^{*} \mbox{ if } r= 0\,,
\end{equation}
\begin{equation}\label{eq:r_equals_1_knapsack}
\|{\boldsymbol x}^{*}-{\boldsymbol z}^{*}\|_{\infty} \le \|{\boldsymbol a}\|_{\infty}-1 \mbox{ if } r= 1 \mbox{ and }
\end{equation}
\begin{equation}\label{eq:r_greater_1_knapsack}
\|{\boldsymbol x}^{*}-{\boldsymbol z}^{*}\|_{\infty} \,\frac{2^{r}}{r} < \|{\boldsymbol a}\|_{\infty}  \mbox{ if } r\ge 2\,.
\end{equation}
\end{thm}
Theorem \ref{t:IPTP_positive_knapsack} can be viewed as a transference result that allows strengthening the distance bound (\ref{AHO_bound})  if integer points in the knapsack polytope  are not sparse and, vice versa, strengthening the sparsity bound  (\ref{sparse_knapsack}) if feasible integer points are sufficiently far from a vertex of the knapsack polytope.

 Given a cost vector ${\boldsymbol c}\in \mathbb Z^n$, we will now consider the integer knapsack problem
 \begin{eqnarray}
\min\{ {\boldsymbol c}^{\top}{\boldsymbol x}: {\boldsymbol x}\in {P}({\boldsymbol a},b)\cap \mathbb Z^n\}\,.
\label{initial_IP}
\end{eqnarray}
Note that  \eqref{initial_IP} is feasible since $b\in{Sg}({\boldsymbol a})$.

Let $IP({\boldsymbol c}, {\boldsymbol a}, {b})$ and $LP({\boldsymbol c}, {\boldsymbol a}, { b})$ denote the optimal values of (\ref{initial_IP}) and its linear programming relaxation
\begin{eqnarray}\label{initial_LP}
\min\{ {\boldsymbol c}^{\top} {\boldsymbol x}: {\boldsymbol x}\in {P}({\boldsymbol a},b)\}\,,
\end{eqnarray}
 respectively.
The {\em integrality gap } $IG({\boldsymbol c}, {\boldsymbol a}, {b})$ of  (\ref{initial_IP}) is defined as
\begin{eqnarray*} IG({\boldsymbol c}, {\boldsymbol a}, {b})= IP({\boldsymbol c}, {\boldsymbol a}, { b})-LP({\boldsymbol c}, {\boldsymbol a}, { b})\,.\end{eqnarray*}
As a corollary of Theorem \ref{t:IPTP_positive_knapsack}, we obtain the following bound for the integrality gap.
\begin{cor}\label{coro_upper_bound} Let ${\boldsymbol a}$ satisfy (\ref{positive_primitive}), $b\in\icone({\boldsymbol a})$ and ${\boldsymbol c}\in\mathbb Z^n$.
Suppose that ${\boldsymbol x}^{*}$ given by \eqref{knapsack_vertex} is an optimal vertex solution to  \eqref{initial_LP}.
Let further ${\boldsymbol z}^{*}$ be any vertex of $\CP_{\gamma}({\boldsymbol a}, {b}) $ such that ${\boldsymbol z}^{*}\in {P}({\boldsymbol a}, b)$. Then for $r=\|(z^*_2,\ldots, z^*_n)^{\top}\|_0$  we have
\begin{equation}\label{eq:r_equals_0_gap}
IG({\boldsymbol c}, {\boldsymbol a}, {b})=0 \mbox{ if } r= 0\,,
\end{equation}
\begin{equation}\label{eq:r_equals_1_gap}
IG({\boldsymbol c}, {\boldsymbol a}, {b}) \le 2(\|{\boldsymbol a}\|_{\infty}-1) \|{\boldsymbol c}\|_{\infty}  \mbox{ if } r=1 \mbox{ and }
\end{equation}
\begin{equation}\label{eq:r_greater_1_gap}
IG({\boldsymbol c}, {\boldsymbol a}, {b})  < \frac{r(r+1)}{2^{r}}\|{\boldsymbol a}\|_{\infty} \|{\boldsymbol c}\|_{\infty} \mbox{ if } r\ge 2\,.
\end{equation}
\end{cor}

It follows from the proof of Theorem 1(ii) in \cite{AHO} that the bound \eqref{eq:r_equals_1_knapsack} (and hence \eqref{eq:r_equals_1} and \eqref{eq:r_equals_1_extension} for $m=1$) corresponding to the case $r=1$ is optimal.  For completeness, we recall that it is sufficient to choose a positive integer $k$ and set
\begin{eqnarray}\label{optimal_example_r_equals_1}
{\boldsymbol a}=(k,\ldots,k,1)^{\top}\,, b=k-1 \mbox{ and } {\boldsymbol x}^*=\frac{k-1}{k}\cdot\boldsymbol{e}_1\,.
\end{eqnarray}
Then the knapsack polytope ${P}({\boldsymbol a},b)$ contains precisely one integer point,  ${\boldsymbol z}^*=(k-1)\cdot\boldsymbol{e}_n$ and we obtain
$\|{\boldsymbol x}^*-{\boldsymbol z}^*\|_{\infty}=k-1 =\|{\boldsymbol a}\|_{\infty}-1$.
The next result of this paper shows that the bounds in Theorems \ref{t:IPTP_general} - \ref{t:IPTP_positive_knapsack} are optimal in the knapsack scenario for $r\ge 2$.
\begin{thm}\label{t:IPTP_positive_knapsack_sharpness}
Fix integer $s\ge 3$. For any $\epsilon>0$ there exists an integer vector ${\boldsymbol a}\in \mathbb Z^s$ satisfying (\ref{positive_primitive}) and $b\in\icone({\boldsymbol a})$ such that for ${\boldsymbol x}^{*}=({b}/{a_1}){\boldsymbol e}_1$ the knapsack polytope $ {P}({\boldsymbol a}, {b})$ contains a vertex ${\boldsymbol z}^*$ of $\CP_{\gamma}({\boldsymbol a}, {b}) $ with $\|{\boldsymbol z}^*_{\bar\gamma}\|_0=s-1$ and
\begin{equation}\label{eq:general_Knapsack_Bound_via_determinant_sharpness}
\|{\boldsymbol x}^*-{\boldsymbol z}^*\|_{\infty} \,\frac{2^{s-1}}{s-1} >(1-\epsilon)\|{\boldsymbol a}\|_{\infty}\,.
\end{equation}
\end{thm}

\subsection{A refined sparsity-type bound for solutions to integer programs}

The next result of this paper aims to refine the general sparsity-type bound obtained in \cite[Theorem 1]{Support}.
Let
\begin{eqnarray*}
\rho({\boldsymbol x})=\min\{|x_i| : i\in\supp({\boldsymbol x}) \}\,
\end{eqnarray*}
denote the minimum absolute nonzero entry of ${\boldsymbol x}$. The notation $\log(\cdot)$ will be used for logarithm with base two.
Let $A \in \mathbb Z^{m\times n}$, $\boldsymbol b \in \mathbb Z^m $ and $\boldsymbol c \in \mathbb Z^n$. We will consider  the general integer linear problem in standard form
\begin{equation}
  \label{eq:mainProblem}
  \max\left\{ \boldsymbol c^{\top}\boldsymbol x : {\boldsymbol x}\in {P}(A, {\boldsymbol b})\cap  \mathbb Z^n\right\}\,.
\end{equation}
We assume that $ {P}(A, {\boldsymbol b})$ contains integer points, so that \eqref{eq:mainProblem} is feasible.
We will also assume without loss of generality that the matrix $A$ has full row rank, i.e., $\mathrm{rank}(A)=m$.

It was shown in \cite[Theorem 1]{Support} that there exists an optimal solution $\boldsymbol z^*$ for \eqref{eq:mainProblem} satisfying the bound
\begin{equation}\label{t:Bound_via_determinant_bound1}
\|\boldsymbol z^*\|_0 \le m + \log\left(\frac{\sqrt{\det(AA^{\top})}}{\gcd(A)}\right)\,.
\end{equation}

Note that any vertex  solution for \eqref{eq:mainProblem} has the size of support $\le m$. Any non-vertex  solution $\boldsymbol z^*$, in its turn, belongs to the interior
of the face ${\mathcal F}={P}(A, {\boldsymbol b})\cap\{{\boldsymbol x}\in \mathbb R^n: x_i=0 \mbox{ for } i\notin \supp(\boldsymbol z^*)\}$ of the polyhedron ${P}(A, {\boldsymbol b})$.
Then the minimum absolute nonzero entry $\rho(\boldsymbol z^*)$ is the $\ell_{\infty}$-distance from $\boldsymbol z^*$ to the boundary of  ${\mathcal F}$.
To obtain a refinement of the bound (\ref{t:Bound_via_determinant_bound1}) we will link the minimum absolute nonzero entry and the size of support of solutions to \eqref{eq:mainProblem}.

\begin{thm}
\label{thm:UpperBound}
Let $A \in \mathbb Z^{m\times n}$, $\boldsymbol b \in \mathbb Z^m $, $\boldsymbol c \in \mathbb Z^n$ and suppose that  \eqref{eq:mainProblem} is feasible. Then there is an optimal solution $\boldsymbol z^*$ to \eqref{eq:mainProblem} such that, letting $s=\|{\boldsymbol z}^*\|_0$,
\begin{equation}\label{t:Bound_via_transference}
(\rho({\boldsymbol z}^*)+1)^{s-m} \le \frac{\sqrt{\det(AA^{\top})}}{\gcd(A)}\,.
\end{equation}
\end{thm}

\section{Lattices and corner polyhedra}

For linearly independent ${\boldsymbol b}_1, \ldots, {\boldsymbol b}_l$ in $\mathbb R^d$, the set $\Lambda=\{\sum_{i=1}^{l} x_i {\boldsymbol b}_i,\, x_i\in \mathbb Z\}$ is a $l$-dimensional {\em lattice} with {\em basis} ${\boldsymbol b}_1, \ldots, {\boldsymbol b}_l$ and {\em determinant}
$\det(\Lambda)=(\det({\boldsymbol b}_i\cdot {\boldsymbol b}_j)_{1\le i,j\le l})^{1/2}$, where ${\boldsymbol b}_i\cdot {\boldsymbol b}_j$ is the standard inner product of the basis vectors ${\boldsymbol b}_i$ and  ${\boldsymbol b}_j$. Recall that the {\em Minkowski sum} $X+Y$ of the sets $X, Y\subset \mathbb R^d$ consists of all points ${\boldsymbol x}+{\boldsymbol y}$ with ${\boldsymbol x}\in X$ and ${\boldsymbol y}\in Y$. The {\em difference set} $X-X$ is the Minkowski sum of $X$ and $-X$.
For a lattice $\Lambda\subset\mathbb R^d$ and ${\boldsymbol y}\in \mathbb R^d$, the set ${\boldsymbol y}+\Lambda$ is an {\em affine lattice} with determinant $\det(\Lambda)$.

Let $\Lambda\subset \mathbb Z^d$ be a $d$-dimensional integer lattice.
The point ${\boldsymbol x}\in \mathbb Z^d_{\ge 0}$ is  called {\em irreducible (with respect to $\Lambda$)}  if for any two points ${\boldsymbol y}, {\boldsymbol y}'\in \mathbb Z^d_{\ge 0}$
with $0\le y_i\le x_i$, $0\le y_i'\le x_i$, $i\in \{1,\ldots, d\}$ the inclusion ${\boldsymbol y}-{\boldsymbol y}'\in \Lambda$ implies ${\boldsymbol y}={\boldsymbol y}'$.

\begin{lemma}[Theorem 1 in \cite{Gomory_polyhedra}]\label{t:bound_for_irreducible_points}
If ${\boldsymbol x}\in \mathbb Z^d_{\ge 0}$ is irreducible with respect to the lattice $\Lambda$ then
\begin{eqnarray}\label{product_det}
\prod_{i=1}^d (x_i+1) \le \det(\Lambda)\,.
\end{eqnarray}

\end{lemma}

\begin{proof}
The lattice $\Lambda$ can be viewed as a subgroup of the additive group $\mathbb Z^d$.
The number of points ${\boldsymbol y}\in \mathbb Z^d_{\ge 0}$ with $0\le y_i\le x_i$, $i\in\{1,\ldots, d\}$ is equal to $\prod_{i=1}^d (x_i+1)$.
 Since ${\boldsymbol x}$ is irreducible, each such ${\boldsymbol y}$ corresponds to a unique coset (affine lattice) ${\boldsymbol y}+\Lambda$ of $\Lambda$.
Finally notice that there are only $\det(\Lambda)$ different cosets.
\end{proof}

 Let ${\boldsymbol r}\in \mathbb Z^d$ and consider the affine lattice  $\Gamma= {\boldsymbol r}+\Lambda$. We will call the set $\sail(\Gamma)= \mathrm{conv}(\Gamma\cap \mathbb R^d_{\ge 0})$ the {\em sail} associated with $\Gamma$.

\begin{lemma}\label{t:bound_for_irreducible_points}
Every vertex of the sail $\sail(\Gamma)$ is irreducible.
\end{lemma}

\begin{proof}

Let ${\boldsymbol x}$ be a vertex of $\sail(\Gamma)$. Suppose, to derive a contradiction, that ${\boldsymbol x}$ is reducible. Then
there are distinct points ${\boldsymbol y}, {\boldsymbol y}'\in \mathbb Z^d_{\ge 0}$
with $0\le y_i\le x_i$, $0\le y_i'\le x_i$, $i\in  \{1,\ldots, d\}$ such that ${\boldsymbol y}-{\boldsymbol y}'\in \Lambda$.

Since ${\boldsymbol x}-{\boldsymbol y}\in \mathbb Z^d_{\ge 0}$ and ${\boldsymbol x}-{\boldsymbol y}'\in \mathbb Z^d_{\ge 0}$, the vectors ${\boldsymbol v}_1= {\boldsymbol x}-{\boldsymbol y}+{\boldsymbol y}'$ and ${\boldsymbol v}_2= {\boldsymbol x}-{\boldsymbol y}'+{\boldsymbol y}$
have nonnegative integer entries. Further, ${\boldsymbol v}_1, {\boldsymbol v}_2\in \Gamma$ and  ${\boldsymbol x}= ({\boldsymbol v}_1+{\boldsymbol v}_2 )/2$. Therefore ${\boldsymbol x}$ is not a vertex of  $\sail(\Gamma)$.
\end{proof}

\begin{lemma}\label{t:sum_product}
For $d\ge 2$ and $x_1, \ldots, x_d\ge 1$ the inequality
\begin{eqnarray}\label{sum_product}
x_1+\cdots+x_d \le \frac{d(x_1+1)\cdots(x_d+1)}{2^{d}}
\end{eqnarray}
holds. \end{lemma}

\begin{proof}

Suppose that (\ref{sum_product}) is satisfied for $x_1=y_1, \ldots, x_d=y_d$. We will first show that for any $\epsilon>0$ and any $i\in\{1,\ldots, d\}$ the inequality
(\ref{sum_product}) is satisfied for  $x_1=y_1, \ldots, x_{i-1}=y_{i-1}, x_i=y_i+\epsilon,  x_{i+1}=y_{i+1}, \ldots, x_d=y_d$. After possible renumbering, it is sufficient to consider the case $i=1$. We have
\begin{eqnarray*}
(y_1+\epsilon)+y_2+\cdots+y_d \le \frac{d(y_1+1)\cdots(y_d+1)}{2^{d}} + \epsilon \\
\le \frac{d(y_1+1)\cdots(y_d+1)}{2^{d}} + \epsilon \frac{d(y_2+1)\cdots(y_d+1)}{2^{d}} = \frac{d(y_1+1+\epsilon)\cdots(y_d+1)}{2^{d}}\,.
\end{eqnarray*}
To complete the proof it is sufficient to observe that (\ref{sum_product}) holds for $y_1=\cdots =y_d=1$.
\end{proof}

Given $A\in\mathbb Z^{m\times n}$ and ${\boldsymbol b}\in\mathbb Z^m$, we will denote by $\Gamma(A,{\boldsymbol b})$  the set of integer points in the affine subspace
\begin{eqnarray*}
{H}({A,{\boldsymbol b}})= \{{\boldsymbol x}\in \mathbb R^n: A{\boldsymbol x}={\boldsymbol b}\}\,,
\end{eqnarray*}
 that is
\begin{eqnarray*} \Gamma(A,{\boldsymbol b})={H}({A,{\boldsymbol b}})\cap \mathbb Z^n\,.\end{eqnarray*}
The set $\Gamma(A,{\boldsymbol b})$  is an affine lattice of the form $\Gamma(A,{\boldsymbol b})= {\boldsymbol r}+ \Gamma(A)$,
where ${\boldsymbol r}$ is any integer vector with $A{\boldsymbol r}={\boldsymbol b}$  and $\Gamma(A) = \Gamma(A,{\boldsymbol 0})$ is the  lattice formed by all integer points in the kernel of the matrix $A$.

Let $\pi_{\gamma}$ denote the projection map from $\mathbb R^n$ to $\mathbb R^{n-m}$ that forgets the first $m$ coordinates, $\pi_{\gamma}: {\boldsymbol u}\mapsto {\boldsymbol u}_{\bar\gamma}$ . Recall that  $A_{\gamma}$ is nonsingular. It follows that  the restricted map $\pi_{\gamma} |_{{H}({A,{\boldsymbol b}})}:{H}({A,{\boldsymbol b}})\rightarrow \mathbb R^{n-m} $ is bijective. Specifically, for any ${\boldsymbol u}_{\bar\gamma}\in \mathbb R^{n-m}$ we have
\begin{eqnarray}\label{structure_of_projection}
\pi_{\gamma} |_{{H}({A,{\boldsymbol b}})}^{-1}({\boldsymbol u}_{\bar\gamma})= \left(
\begin{array}{c}{\boldsymbol u}_{\gamma}\\ {\boldsymbol u}_{\bar\gamma}\end{array}
\right)\,\mbox{ with } {\boldsymbol u}_{\gamma}= A_{\gamma}^{-1}({\boldsymbol b}-A_{\bar \gamma}{\boldsymbol u}_{\bar\gamma})\,.
\end{eqnarray}

For technical reasons, it is convenient to consider the projected affine lattice $\Lambda(A,{\boldsymbol b})=\pi_{\gamma}(\Gamma(A,{\boldsymbol b}))$ and the projected lattice $\Lambda(A)=\pi_{\gamma}(\Gamma(A))$.
Let ${\boldsymbol g}_1, \ldots, {\boldsymbol g}_{n-m}$ be a basis of $\Gamma(A)$.
Since the map $\pi_{\gamma} |_{{H}({A,{\boldsymbol 0}})}$ is bijective, the vectors ${\boldsymbol b}_1=\pi_{\gamma}({\boldsymbol g}_1), \ldots, {\boldsymbol b}_{n-m}=\pi_{\gamma}({\boldsymbol g}_{n-m})$ form a basis of the lattice $\Lambda(A)$.
Let $G\in \mathbb Z^{n \times (n-m)}$ be the matrix with columns  ${\boldsymbol g}_1, \ldots, {\boldsymbol g}_{n-m}$.
We will denote by $F$ the $(n-m)\times (n-m)$-submatrix of $G$ consisting of the last $n-m$
rows; hence, the columns of $F$ are ${\boldsymbol b}_1, \ldots, {\boldsymbol b}_{n-m}$. Then $\det(\Lambda(A))=|\det(F)|$.
The rows of the matrix $A$ span the $m$-dimensional rational subspace of $\mathbb R^n$ orthogonal to the $(n-m)$-dimensional rational subspace spanned by the columns of $G$. Therefore, by Lemma 5G and Corollary 5I in \cite{Schmidt_Approximations}, we have $|\det(F)|=|\det(A_{\gamma})|/\gcd(A)$ and, consequently,

\begin{eqnarray}\label{determinant_via_submatrix}\det(\Lambda(A))=\frac{|\det(A_{\gamma})|}{\gcd(A)}\,.\end{eqnarray}

\begin{thm}\label{nondegenerate}
Suppose that  $A$ satisfies \eqref{matrix_partition}, ${\boldsymbol b}\in \mathbb Z^m$ and  $\boldsymbol x^*$ is given by \eqref{vertex_assumption}.
For any vertex ${\boldsymbol z}^{*}$ of the corner polyhedron $\CP_{\gamma}(A, {\boldsymbol b})$
the bound
\begin{eqnarray}\label{product_det_z}
\prod_{j\in\bar\gamma}(z_j^*+1)\leq \frac{|\det(A_{\gamma})|}{\gcd(A)}
\end{eqnarray}
holds.
\end{thm}

\begin{proof}

Since $\pi_{\gamma} |_{{H}({A,{\boldsymbol b}})}$ is a bijection, the point ${\boldsymbol y}^*=\pi_{\gamma}({\boldsymbol z}^{*})$ is a vertex of the sail $\sail(\Lambda(A, {\boldsymbol b}))$. The result now follows by  Lemma \ref{t:bound_for_irreducible_points} and \eqref{determinant_via_submatrix}.
\end{proof}

\section{Proof of Theorem \ref{t:IPTP_general}}

Theorem \ref{t:IPTP_general} is an immediate consequence of Theorem \ref{nondegenerate} and the following lemma:

\begin{lemma}
\label{proximity_bound_by_product}
Suppose that  $A$ satisfies \eqref{matrix_partition}, and let ${\boldsymbol b}\in \mathbb Z^m$. Let $\boldsymbol x^*$ be a vertex of ${P}(A, {\boldsymbol b})$, and let $\gamma$ be any basis of $A$ containing $\supp({\boldsymbol x}^{*})$.
Let ${\boldsymbol z}^{*}$ be an integral vector satisfying $A{\boldsymbol z}^{*}={\boldsymbol b}$, with ${\boldsymbol z}_{\bar{\gamma}}^{*}\geq \mathbf{0}$, and let $r=\|{\boldsymbol z}^{*}_{\bar\gamma}\|_0$. Then
\begin{equation}\label{eq:r_equals_0_lemma}
{\boldsymbol x}^{*}={\boldsymbol z}^{*} \mbox{ if } r= 0\,,
\end{equation}
\begin{equation}\label{eq:r_equals_1_lemma}
\|{\boldsymbol x}^{*}-{\boldsymbol z}^{*}\|_{\infty} \le \frac{\Sigma(A)}{|\det(A_{\gamma})|}\prod_{j\in\bar\gamma}(z_j^*+1) - 1 \mbox{ if } r= 1 \mbox{ and }
\end{equation}
\begin{equation}\label{eq:r_greater_1_lemma}
\|{\boldsymbol x}^{*}-{\boldsymbol z}^{*}\|_{\infty} \,\frac{2^{r}}{r} \leq \frac{\Sigma(A)}{|\det(A_{\gamma})|}\prod_{j\in\bar\gamma}(z_j^*+1) \mbox{ if } r\ge 2\,.
\end{equation}
\end{lemma}

\begin{proof}
If $r=\|{\boldsymbol z}_{\bar\gamma}^{*}\|_0=0$ the vector ${\boldsymbol z}^{*}_{\gamma}$ is the unique solution to the system $A_{\gamma}{\boldsymbol x}_{\gamma}= {\boldsymbol b}$. Therefore
\eqref{eq:r_equals_0_lemma} holds.

In the rest of the proof we assume that $r\ge 1$.
We will set $\delta= \|{\boldsymbol x}^*-{\boldsymbol z}^{*}\|_{\infty}$ and consider the following two cases. First suppose that there exists an index $j\in\bar\gamma$ such that
$\delta= |x^*_j-z_j^{*}|=z_j^{*}$.  Observe that $r$ of the numbers $z^{*}_{m+1}, \ldots, z^{*}_{n}$ are nonzero. Hence,
\begin{eqnarray}\label{distance_nonbasic}
(\delta+1) 2^{r-1}\le \prod_{j\in\bar\gamma} (z^{*}_j+1)
\end{eqnarray}
and so
\begin{eqnarray}\label{distance_nonbasic_rearranged}
\delta \frac{2^{r}}{r}\le   \frac{2}{r}\prod_{j\in\bar\gamma} (z^{*}_j+1) -\frac{2^{r}}{r}\,.
\end{eqnarray}
Since $\Sigma(A)\geq|\det(A_{\gamma})|$, inequality \eqref{distance_nonbasic_rearranged} justifies both \eqref{eq:r_equals_1_lemma} and \eqref{eq:r_greater_1_lemma}.

Now suppose that $\delta= x^*_j-z^{*}_j$ for $j\in \gamma$. We can write
\begin{eqnarray*}
A_{\gamma}{\boldsymbol z}^{*}_{\gamma}+A_{\bar\gamma}{\boldsymbol z}^{*}_{\bar\gamma}={\boldsymbol b}\mbox{ and }
A_{\gamma}{\boldsymbol x}^*_{\gamma}={\boldsymbol b}\,.
\end{eqnarray*}
Therefore
\begin{eqnarray}\label{equation_difference_vector}
A_{\gamma}({\boldsymbol x}^*_{\gamma}-{\boldsymbol z}^{*}_{\gamma})= A_{\bar\gamma}{\boldsymbol z}^{*}_{\bar\gamma}\,.
\end{eqnarray}
Given a vector ${\boldsymbol v}\in \mathbb R^m$, we will denote by $A_{\gamma}^j({\boldsymbol v})$ the matrix obtained from $A_{\gamma}$ by replacing its $j$-{th} column with ${\boldsymbol v}$. Let $A_{1}, \ldots, A_{n}$  be the columns of the matrix $A$. Solving \eqref{equation_difference_vector} by Cramer's rule, we have
\begin{eqnarray}\label{Cramer}
\begin{split}
 \delta=x^*_j-z^{*}_j = \frac{ \det (A_{\gamma}^j(A_{\bar\gamma}{\boldsymbol z}^{*}_{\bar\gamma}) )}{\det(A_{\gamma})}\\
 =\frac{1}{\det(A_{\gamma})}(z^{*}_{m+1}\det(A_{\gamma}^j(A_{m+1}) )+ \cdots + z^{*}_{n}\det(A_{\gamma}^j(A_{n})))\,.
\end{split}
\end{eqnarray}
If $r=1$, then for some $i\in \bar\gamma$ we can write
\begin{eqnarray}\label{Product_r_equals_1}
 \delta=\frac{z^{*}_{i}\det(A_{\gamma}^j(A_{i}) )}{\det(A_{\gamma})}= \left(z^{*}_i + 1\right)\frac{\det(A_{\gamma}^j(A_{i}) )}{\det(A_{\gamma})} - \frac{\det(A_{\gamma}^j(A_{i}) )}{\det(A_{\gamma})}\,.
\end{eqnarray}
Equation \eqref{Product_r_equals_1} plus the integrality of $\delta$ imply \eqref{eq:r_equals_1_lemma}.

To settle the case $r\ge 2$, observe that \eqref{Cramer} implies
\begin{eqnarray}\label{Delta_upper_bound_r_ge_2}
\delta \leq (z^{*}_{m+1}+\cdots+z^{*}_n)\frac{\Sigma(A)}{|\det(A_{\gamma})|}\,.
\end{eqnarray}

Without loss of generality, assume that $z^{*}_i\neq 0$ for $i\in \{m+1, \ldots, m+r\}$ and $z^{*}_i=0$ for $m+r<i\le n$.
Then, by \eqref{Delta_upper_bound_r_ge_2} and Lemma \ref{t:sum_product}, we have
\begin{equation}
\delta \leq \frac{r(z^{*}_{m+1}+1)\cdots(z^{*}_{m+r}+1)\Sigma(A)}{2^{r}|\det(A_{\gamma})|}\,.
\end{equation}
This establishes inequality \eqref{eq:r_greater_1_lemma}.
\end{proof}

\section{Proof of Theorem \ref{thm:upper_bound_extension}}

As in the proof of Theorem \ref{t:IPTP_general}, we have that Theorem
\ref{thm:upper_bound_extension} is an immediate consequence of Lemma
\ref{proximity_bound_by_product} and the generalization of Theorem
\ref{nondegenerate} given below. Recall that $\tau$ denotes the
support of $\ve x^{*}$, and $\CP_{\tau}(A,\ve b)$ denotes the polyhedron
\[
\CP_{\tau}(A,\ve b)=\mathrm{conv}\left(\left\{ \ve x\in\mathbb Z^{n}:A\ve x=\ve b,\;\ve x_{\bar{\tau}}\geq\mathbf{0}\right\} \right).
\]

\begin{thm}
\label{thm:upper_bound_product_coords_extension}Let $\ve z^{*}$ be
a vertex of $\CP_{\tau}(A,\ve b)$. Then there exists a basis $\gamma$
of $A$ containing $\tau$ such that
\[
\prod_{j\in\ol{\gamma}}(\ve z_{j}^{*}+1)\leq r^{d}\,\frac{\left|\det(A_{\gamma})\right|}{\gcd(A)},
\]
where $r=\left\Vert \ve z_{\bar{\gamma}}^{*}\right\Vert _{0}$ and $d=m-\left|\tau\right|$.
\end{thm}
Theorem \ref{thm:upper_bound_product_coords_extension} is proved
over the remainder of this section.

\subsection{Convex geometry lemmas}
For an affine subspace $F\subseteq\mathbb R^d$, let $\mathrm{vol}_F(\cdot)$ denote the standard Lebesgue measure with respect to $F$. We denote $\mathrm{vol}_{\mathbb R^d}(\cdot)$ simply by $\mathrm{vol}_d(\cdot)$.
\begin{lemma}[{Blichfeldt's lemma \cite[Chapter III, Theorem I]{cassels1996introduction}}]
\label{lem:Blichfeldt lemma}Let $K\subseteq\mathbb R^{d}$ be bounded,
nonempty, Lebesgue measurable and let $\Lambda$ be a full-dimensional
lattice in $\mathbb R^{d}$. Suppose that the difference set $K-K$ contains no nonzero
lattice points from $\Lambda$. Then $\mathrm{vol}_{d}(K)\leq\det(\Lambda)$.\qed
\end{lemma}

\begin{thm}[{Brunn's concavity principle \cite[Theorem 1.2.1]{artstein2015asymptotic}}]
\label{lem:Brunn concavity}Let $K$ be a convex body, and let $F$ be a $k$-dimensional subspace of $\mathbb R^d$. Then the function $g:F^{\perp}\rightarrow\mathbb R$ defined by
\[
g(x)=\mathrm{vol}_{F+x}(K\cap(F+x))^{1/k}
\]
is concave on its support.
\end{thm}

By a \emph{slab} we mean the nonempty intersection of two halfspaces
with antiparallel normals. Let $\qq\in\mathbb R^d$ be nonzero.
The \emph{width} of a set $K\subseteq\mathbb R^{d}$ along $\qq$ is defined
to be
\[
w_{\qq}(K):=\left(\sup_{\ve x\in K}\qq^{\top}\ve x\right)-\left(\inf_{\ve x\in K}\qq^{\top}\ve x\right).
\]

\begin{prop}
\label{prop:lower_bound_volume_slab}Let $K$ be a centrally symmetric
convex body with centre $\ve c$. Let $S$ be a slab centred at $\ve c$
with a facet normal $\qq$. If $S$ does not contain $K$, then
\[
\mathrm{vol}_{d}(K\cap S)\geq\frac{w_{\qq}(S)}{w_{\qq}(K)}\cdot\mathrm{vol}_{d}(K).
\]
\end{prop}
\begin{proof}
Without loss of generality, we may assume $\ve c$ is the origin. For
$\lambda\in[-1,1]$, define the affine hyperplane
\[
L_{\lambda}:=\left\{ \ve x\in\mathbb R^{d}:\qq^{\top}\ve x=\lambda \cdot w_{\qq}(K)/2\right\} \,.
\]
Let $K_{\lambda}:=K\cap L_{\lambda}$, and define the cross-sectional
volume
\[
f(\lambda):=\mathrm{vol}_{L_{\lambda}}\left(K_{\lambda}\right).
\]
By symmetry, we have $K_{\lambda}=-K_{-\lambda}$. Hence, $f$ is an even function on $[-1,1]$, which means that $g(\lambda):=(f(\lambda))^{1/(d-1)}$ is an even function as well. Since $g$ is concave on $[-1,1]$ by Brunn's concavity principle, we have that $g$, and therefore $f$, is a decreasing function on $[0,1]$.

Now let $\delta:=w_{\qq}(S)/w_{\qq}(K)$. By Fubini's theorem, symmetry, and monotonicity on $[0,1]$, we
conclude
\[
\mathrm{vol}_{d}(K\cap S)=\int_{-\delta}^{\delta}f(\lambda)d\lambda =2\int_{0}^{\delta}f(\lambda)d\lambda \geq 2\delta\int_{0}^{1}f(\lambda)d\lambda=\frac{w_{\qq}(S)}{w_{\qq}(K)}\cdot\mathrm{vol}_{d}(K).\qedhere
\]
\end{proof}
The notion of irreducibility from Lemma \ref{t:bound_for_irreducible_points}
can be mildly generalized as follows. Let $C$ be a pointed cone.
Let $\Lambda\subset\mathbb Z^{d}$ be a $d$-dimensional integer lattice.
The point ${\boldsymbol x}\in C\cap\mathbb Z^{d}$ is called {\em irreducible (with
respect to $\Lambda$ and $C$)} if
\[
(-\ve x+C)\cap(\ve x-C)\cap\Lambda=\{\mathbf{0}\}.
\]

Let $\boldsymbol r\in\mathbb Z^{d}$ and consider the affine lattice $\Gamma=\boldsymbol r+\Lambda$.
We will call the set $\sail(\Gamma,C)=\mathrm{conv}(\Gamma\cap C)$ the {\em
sail} associated with $\Gamma$ and $C$.
\begin{lemma}
\label{t:bound_for_irreducible_points_cone} Every vertex of the sail
$\sail(\Gamma,C)$ is irreducible.
\end{lemma}
\begin{proof}
Let ${\boldsymbol x}$ be a vertex of $\sail(\Gamma,C)$. Suppose, to derive
a contradiction, that ${\boldsymbol x}$ is reducible. Then there exists nonzero
$\boldsymbol{\lambda}\in\Lambda$ and vectors ${\boldsymbol y},{\boldsymbol y}'\in C$ such
that $\boldsymbol{\lambda}=-\ve x+\ve y=\ve x-\ve y'$. The fact that $\ve x$ is a
vertex of $\sail(\Gamma,C)$ implies $\ve x\in\Gamma$, and therefore
both $\ve y=\boldsymbol{\lambda}+\ve x$ and $\ve y'=-\boldsymbol{\lambda}+\ve x$ are contained
in $\Gamma\cap C$, and hence in $\sail(\Gamma,C)$. Since $\boldsymbol{\lambda}$
is nonzero, we conclude that $\ve x=(\ve y+\ve y')/2$ is not a vertex of
$\sail(\Gamma,C)$.
\end{proof}

\subsection{Lemmas for Theorem \ref{thm:upper_bound_product_coords_extension}}
In this subsection we further assume the condition that $\bar{\tau}\subseteq\supp(\ve z^{*})$. We fix a basis $\gamma$ of $A$ containing $\tau$ such that for all $i\in\gamma\backslash\tau$,
\begin{eqnarray}
\label{eq:careful_choice_of_gamma}
z_{i}^{*}+1\geq\frac{1}{r}\sum_{j\in\bar{\gamma}}\left|(A_{\gamma}^{-1}A_{\bar{\gamma}})_{i,j}(z_{j}^{*}+1)\right|.
\end{eqnarray}
The existence of such a basis $\gamma$ is justified in Proposition \ref{prop:There_exists_a_basis}. Without loss of generality, we continue with our notational assumption that $\gamma=\left\{ 1,2,\ldots,m\right\} $
and we further assume $\gamma\backslash\tau=\left\{ 1,2,\ldots,d\right\} .$ We denote the rows of
the matrix $-A_{\gamma}^{-1}A_{\bar{\gamma}}$ by $\qq_{1}^{\top},\qq_{2}^{\top},\ldots,\qq_{m}^{\top}$. Note that the equality $A\ve z^{*}=\ve b$
implies $\qq_{i}^{\top}\ve z_{\bar{\gamma}}^{*}=z_{i}^{*}-x_{i}^{*}$ for
all $i\in\gamma$.

\begin{prop}
\label{prop:There_exists_a_basis}Assume $\bar{\tau}\subseteq\supp(\ve z^{*})$.
Then there exists a basis $\gamma$ of $A$ containing $\tau$ satisfying inequality \eqref{eq:careful_choice_of_gamma}.
\end{prop}
\begin{proof}
Among all bases of $A$ containing $\tau$, choose a basis $\gamma$
so that the quantity $\left|\det A_{\gamma}\right|\cdot\prod_{i\in\gamma}(z_{i}^{*}+1)$
is as large as possible. If $i\in\gamma$ and $j\in\bar{\gamma}$, then by Cramer's rule we
have
\[
q_{i,j}=-\frac{\det(A_{\gamma}^{i}(A_{j}))}{\det(A_{\gamma})},
\]
where $A_{\gamma}^{i}(A_{j})$ denotes the matrix obtained by replacing
column $i$ of $A_{\gamma}$ with column $j$ of $A$. The choice
of $\gamma$ implies that if $i\in\gamma\backslash\tau$ and $j\in\bar{\gamma},$
then
\[
z_{i}^{*}+1\geq\left|\frac{\det(A_{\gamma}^{i}(A_{j}))}{\det(A_{\gamma})}(z_{j}^{*}+1)\right|=\left|q_{i,j}(z_{j}^{*}+1)\right|.
\]
The condition $\bar{\tau}\subseteq\supp(\ve z^{*})$ implies $r=\left|\bar{\gamma}\right|$.
Hence, for all $i\in\gamma\backslash\tau$, we have
\[
z_{i}^{*}+1\geq\frac{1}{r}\sum_{j\in\bar{\gamma}}\left|q_{i,j}(z_{j}^{*}+1)\right|.\qedhere
\]
\end{proof}

Let $\ve 1_{n-m}\in\mathbb R^{n-m}$ be the vector of all ones, and define, for
each $i\in\gamma\backslash\tau$,
\begin{align*}
S_{i} & :=\left\{ \ve x\in\mathbb R^{n-m}:-\tfrac{1}{2}<\qq_{i}^{\top}\ve x<\qq_{i}^{\top}\ve z_{\bar{\gamma}}^{*}+\tfrac{1}{2}\right\} .
\end{align*}
Also define
\begin{align*}
B & :=\left\{ \ve x\in\mathbb R^{n-m}:-\tfrac{1}{2}\ve 1_{n-m}<\ve x<\ve z_{\bar{\gamma}}^{*}+\tfrac{1}{2}\ve 1_{n-m}\right\},
\end{align*}
and for each $i\in\gamma\backslash\tau$, let $P_{i}:=P_{i-1}\cap S_{i}$ with $P_{0}=B$. Let $P:=P_d$.
\begin{lemma}
\label{lem:lower_bound_volume}Assume $\bar{\tau}\subseteq\supp(\ve z^{*})$.
Then
\[
\mathrm{vol}_{n-m}(P)\geq\frac{1}{r^{d}}\prod_{j\in\bar{\gamma}}(z_{j}^{*}+1).
\]
\end{lemma}
\begin{proof}
Suppose $i\in\gamma \backslash \tau$. If $S_{i}$ contains $P_{i-1}$ then $P_{i-1}=P_{i}$,
and hence
\[
\mathrm{vol}_{n-m}(P_{i})=\mathrm{vol}_{n-m}(P_{i-1}).
\]
Otherwise, define
\[
\lambda_{i}:=\frac{w_{\qq_{i}}(S_{i})}{w_{\qq_{i}}(P_{i-1})}.
\]
The fact that $\bar{\tau}\subseteq\supp(\ve z^{*})$ implies $z_{i}^{*}\geq1$
for all $i\in\gamma\backslash\tau$. Applying Proposition \ref{prop:There_exists_a_basis},
we get
\[
\lambda_{i}\geq\frac{w_{\qq_{i}}(S_{i})}{w_{\qq_{i}}(B)}=\frac{\qq_{i}^{\top}\ve z_{\bar{\gamma}}^{*}+1}{\sum_{j\in\bar{\gamma}}\left|q_{i,j}(z_{j}^{*}+1)\right|}=\frac{z_{i}^{*}+1}{\sum_{j\in\bar{\gamma}}\left|q_{i,j}(z_{j}^{*}+1)\right|}\geq\frac{z_{i}^{*}+1}{r(z_{i}^{*}+1)}=\frac{1}{r}.
\]
Since $S_{i}$ does not contain $P_{i-1}$, Proposition \ref{prop:lower_bound_volume_slab}
applies, and so
\[
\mathrm{vol}_{n-m}(P_{i})\geq\frac{w_{\qq_{i}}(S_{i})}{w_{\qq_{i}}(P_{i-1})}\mathrm{vol}_{n-m}(P_{i-1})=\lambda_{i}\mathrm{vol}_{n-m}(P_{i-1})\geq\frac{1}{r}\mathrm{vol}_{n-m}(P_{i-1}).
\]
Applying induction to the sequence of polytopes $P=P_d,\ldots,P_1,P_0=B$, we get
\[
\mathrm{vol}_{n-m}(P)\geq\frac{1}{r^{d}}\mathrm{vol}_{n-m}(B)=\frac{1}{r^{d}}\prod_{j\in\bar{\gamma}}(z_{j}^{*}+1).\qedhere
\]
\end{proof}
\begin{lemma}
\label{lem:upper_bound_polyhedron_volume}Assume $\bar{\tau}\subseteq\supp(\ve z^{*})$.
Then
\[
\mathrm{vol}_{n-m}(P)\leq\frac{\left|\det(A_{\gamma})\right|}{\gcd(A)}.
\]
\end{lemma}
\begin{proof}
Recall we defined the lattice $\Lambda(A)=\pi_{\gamma}(\mathrm{ker}(A)\cap\mathbb Z^{n})$,
whose determinant is given by $\left|\det(A_{\gamma})\right|/\gcd(A)$
by \eqref{determinant_via_submatrix}. We show that $(P-P)\cap\Lambda(A)=\{\mathbf{0}\}$.
The conclusion then follows from Lemma \ref{lem:Blichfeldt lemma}.

Suppose that $\ve u,\ve v\in P$ and $\ve u-\ve v\in\Lambda(A)$. Since $P$
is symmetric, $P-P$ is the origin-symmetric translate of $2P$, and
therefore
\begin{equation}
\begin{gathered}-\ve z_{\bar{\gamma}}^{*}-\mathbf{1}_{n-m}<\ve u-\ve v<\ve z_{\bar{\gamma}}^{*}+\mathbf{1}_{n-m}\\
-\qq_{i}^{\top}\ve z_{\bar{\gamma}}^{*}-1<\qq_{i}^{\top}(\ve u-\ve v)<\qq_{i}^{\top}\ve z_{\bar{\gamma}}^{*}+1\text{ for all \ensuremath{i\in\gamma\backslash\tau}}.
\end{gathered}
\label{eq:x_minus_y_open_bounds}
\end{equation}
The lattice $\Lambda(A)$ can be characterized as the set of points
$\ve x\in\mathbb Z^{n-m}$ such that $\qq_{i}^{\top}\ve x\in\mathbb Z$ for
each $i\in\gamma$. Hence, the inequalities from (\ref{eq:x_minus_y_open_bounds})
imply
\[
\begin{gathered}-\ve z_{\bar{\gamma}}^{*}\leq\ve u-\ve v\leq\ve z_{\bar{\gamma}}^{*}\\
-\qq_{i}^{\top}\ve z_{\bar{\gamma}}^{*}\leq\qq_{i}^{\top}(\ve u-\ve v)\leq\qq_{i}^{\top}\ve z_{\bar{\gamma}}^{*}\text{ for all \ensuremath{i\in\gamma\backslash\tau}}.
\end{gathered}
\]
In particular, $\ve u-\ve v$ lies in the polyhedron $(-\ve z_{\bar{\gamma}}^{*}+C)\cap(\ve z_{\bar{\gamma}}^{*}-C)$,
where
\[
C:=\left\{ \ve x\in\mathbb R^{n-m}:\ve x\geq0,\;\qq_{i}^{\top}\ve x\geq0\text{ for all \ensuremath{i\in\gamma\backslash\tau}}\right\} .
\]
By assumption, $\ve z_{\bar{\gamma}}^{*}$ is a vertex of the sail $\sail(\Lambda(A,\ve b),C)$.
Hence, $\ve z_{\bar{\gamma}}^{*}$ is irreducible by Lemma \ref{t:bound_for_irreducible_points_cone},
and therefore $\ve u=\ve v$.
\end{proof}

\subsection{Proof of Theorem \ref{thm:upper_bound_product_coords_extension}}

Let $\mu=\tau\cup\supp(\ve z^{*})$, which we may assume without loss of generality is given by $\mu=\{1,2,\ldots,\left|\mu\right|\}$, and let $A'_{\mu}$ be any full
row rank integer matrix with the same rowspace as $A_{\mu}$. We have
that $\ve x_{\mu}^{*}$ is a basic feasible solution of the system
\begin{eqnarray}
A_{\mu}'\ve x_{\mu}=\ve b',\;\ve x_{\mu}\geq\mathbf{0},
\label{eq:reduced_system}
\end{eqnarray}
where $\ve b':=A_{\mu}'\ve x_{\mu}^{*}$. Moreover, letting
\[
\CP_{\tau}(A_{\mu}',\ve b') := \mathrm{conv}(\{\ve x_{\mu}\in\mathbb Z^{\left|\mu\right|}:A_{\mu}'\ve x_{\mu}=\ve b',\;\ve x_{\mu\backslash\tau}\geq\mathbf{0}\}),
\]
we have that $\CP_{\tau}(A_{\mu}',\ve b')\times\{\mathbf{0}\}^{\bar{\mu}}$
is the face of $\CP_{\tau}(A,\ve b)$ for which the constraints $\ve x_{\bar{\mu}}\geq\mathbf{0}$ are tight, and this face contains $\ve z^{*}=(\ve z_{\mu}^{*},\mathbf{0})$. Hence, $\ve z_{\mu}^{*}$ is a vertex of $\CP_{\tau}(A_{\mu}',\ve b')$.
We may therefore apply the above results to $\ve x_{\mu}^{*},\ve z_{\mu}^{*},$
and the system \eqref{eq:reduced_system}. Let $\sigma\subseteq\mu$
be a basis of $A_{\mu}'$ containing $\tau$ satisfying \eqref{eq:careful_choice_of_gamma}, whose existence is guaranteed by \eqref{eq:careful_choice_of_gamma}. Then Lemmas \ref{lem:lower_bound_volume}
and \ref{lem:upper_bound_polyhedron_volume} imply
\[
\prod_{j\in\bar{\sigma}}(\ve z_{j}^{*}+1)\leq r^{\left|\sigma\right|-\left|\tau\right|}\,\frac{\left|\det(A_{\sigma}')\right|}{\gcd(A_{\mu}')}.
\]
Now let $\gamma$ be a basis of $A$ containing $\sigma$. Then $\mu$
and $\gamma\backslash\sigma$ partition $\mu\cup\gamma$. Up to invertible
row operations, we can write
\[
A_{\mu\cup\gamma}=\begin{pmatrix}A_{\mu}' & A_{\gamma\backslash\sigma}'\\
\mathbf{0} & A_{\gamma\backslash\sigma}''
\end{pmatrix}=\begin{pmatrix}A_{\mu\backslash\sigma}' & A_{\sigma}' & A_{\gamma\backslash\sigma}'\\
\mathbf{0} & \mathbf{0} & A_{\gamma\backslash\sigma}''
\end{pmatrix},
\]
where both $A_{\sigma}'$ and $A_{\gamma\backslash\sigma}''$ are
both invertible. Now, every nonzero maximal subdeterminant of $A_{\mu\cup\gamma}$
is the product of $\det(A_{\gamma\backslash\sigma}'')$ with a maximal
subdeterminant of $A_{\mu}'$. It follows that
\[
\gcd(A_{\mu\cup\gamma})=\bigl|\det(A_{\gamma\backslash\sigma}'')\bigr|\cdot\gcd(A_{\mu}'),
\]
and hence
\[
\frac{\bigl|\det(A_{\sigma}')\bigr|}{\gcd(A_{\mu}')}=\frac{\bigl|\det(A_{\sigma}')\bigr|\cdot\bigl|\det(A_{\gamma\backslash\sigma}'')\bigr|}{\gcd(A_{\mu\cup\gamma})}=\frac{\bigl|\det(A_{\gamma})\bigr|}{\gcd(A_{\mu\cup\gamma})}.
\]
We conclude
\[
\prod_{j\in\bar{\gamma}}(\ve z_{j}^{*}+1)\leq\prod_{j\in\bar{\sigma}}(\ve z_{j}^{*}+1)\leq r^{\left|\sigma\right|-\left|\tau\right|}\,\frac{\bigl|\det(A_{\gamma})\bigr|}{\gcd(A_{\mu\cup\gamma})}\leq r^{d}\,\frac{\bigl|\det(A_{\gamma})\bigr|}{\gcd(A)}.\qedhere
\]

\section{Proof of Theorem \ref{t:IPTP_positive_knapsack}}

First we will show that the knapsack polytope ${P}({\boldsymbol a}, b)$ contains a vertex of the corner polyhedron
$\CP_{\gamma}({\boldsymbol a}, {b}) $.  Let ${\boldsymbol z}^*$ be a vertex of $\CP_{\gamma}({\boldsymbol a}, {b}) $ that gives an optimal solution to the linear program
\begin{eqnarray*} \max\{x_1: {\boldsymbol x}=(x_1, \ldots, x_n)^{\top} \in \CP_{\gamma}({\boldsymbol a}, {b}) \}\,.\end{eqnarray*}
By definition of $\CP_{\gamma}({\boldsymbol a}, {b})$ the vertex ${\boldsymbol z}^*$ is in ${P}({\boldsymbol a}, b)$ if and only if $z_1^*\ge 0$.
Since ${P}({\boldsymbol a}, b)\subset \CP_{\gamma}({\boldsymbol a}, {b}) $, it is now sufficient to choose any integer point  ${\boldsymbol z}=(z_1, \ldots, z_n)^{\top}\in {P}({\boldsymbol a}, b)$ and observe that
$z_1^*\ge z_1\ge 0$.

Applying Theorem  \ref{t:IPTP_general} with the vertex ${\boldsymbol z}^*\in {P}({\boldsymbol a}, b)$ we immediately  obtain \eqref{eq:r_equals_0_knapsack}
and \eqref{eq:r_equals_1_knapsack}. Further,  the bound \eqref{eq:r_greater_1} implies for $r\ge 2$ the non-strict inequality
\begin{equation}\label{eq:r_greater_1_knapsack_nonstrict}
\|{\boldsymbol x}^{*}-{\boldsymbol z}^{*}\|_{\infty} \,\frac{2^{r}}{r} \le  \|{\boldsymbol a}\|_{\infty}\,.
\end{equation}
To show that \eqref{eq:r_greater_1_knapsack_nonstrict} is strict (and hence that \eqref {eq:r_greater_1_knapsack} holds), it is sufficient to prove that the bound
\eqref{Delta_upper_bound_r_ge_2} in the proof of Theorem \ref{t:IPTP_general}  is strict in the knapsack scenario.
Specifically, we need to prove that for the vertex ${\boldsymbol z}^*$
\begin{eqnarray}\label{lincomb_via_sum_knapsack}
\delta= |x^*_1-z^*_1|< \frac{(z_2^*+\cdots+z^*_{n})\|{\boldsymbol a}\|_{\infty}}{a_1}\,.
\end{eqnarray}

Set $A=(a_1, \ldots, a_n)\in\mathbb Z^{1\times n}$  and consider the affine lattice $\Lambda({\boldsymbol a},{b}):=\Lambda(A,{b})$.
We can write
\begin{equation}\label{affine_congruence}
\Lambda({\boldsymbol a}, b)= \{(\lambda_2, \ldots, \lambda_n)^{\top}\in \mathbb Z^{n-1}: \lambda_2 a_2+\cdots+ \lambda_{n-1}a_{n-1}\equiv b\, (\,\mathrm{mod}\; a_1)\}\,.
\end{equation}
Following \eqref{structure_of_projection},  the map $\pi_{\gamma} |_{{H}({A,{b}})}$, with $\gamma=\{1\}$ in the knapsack scenario, is a bijection. It follows that the point ${\boldsymbol y}^*=\pi_{\gamma}({\boldsymbol z}^{*})$ is a vertex of the sail $\sail(\Lambda({\boldsymbol a}, {b}))$.

Suppose, to derive a contradiction, that the equality
\begin{eqnarray}\label{contr_equal} \delta=\frac{(z_2^*+\cdots+z_{n}^*)\|{\boldsymbol a}\|_{\infty}}{a_1}\end{eqnarray}
holds. By \eqref{Cramer} we have
\begin{eqnarray*}
 \delta=\frac{z^{*}_{2}a_2+ \cdots + z^{*}_{n}a_n}{a_1}
\end{eqnarray*}
 and, consequently, \eqref{contr_equal}  implies $a_2=\cdots=a_n=\|{\boldsymbol a}\|_{\infty}$. Therefore, using \eqref{affine_congruence}, the affine lattice $\Lambda({\boldsymbol a}, b)$ contains the points
\begin{eqnarray} \label{simplex}
(z_2^*+\cdots+z_{n}^*){\boldsymbol e}_j\,,\; j\in \{1,\ldots, n-1\}\,.
\end{eqnarray}
The point ${\boldsymbol y}=(z_2^*, \ldots, z^*_{n})^{\top}$, in its turn, belongs to the simplex with vertices \eqref{simplex} and has $\|{\boldsymbol y}\|_0=r\ge 2$.
Therefore ${\boldsymbol y}$ cannot be a vertex of the sail $\sail(\Lambda({\boldsymbol a},{b}))$. The derived contradiction completes the proof of Theorem \ref{t:IPTP_positive_knapsack}.

\section{Proof of Corollary \ref{coro_upper_bound}}

By Theorem \ref{t:IPTP_positive_knapsack} the knapsack polytope ${P}({\boldsymbol a}, b)$ contains a vertex ${\boldsymbol z}^{*}$ of $\CP_{\gamma}({\boldsymbol a}, {b}) $.
Therefore
\begin{eqnarray}\label{gap-distance}
IG({\boldsymbol c}, {\boldsymbol a}, {b})\le \|{\boldsymbol x}^{*}-{\boldsymbol z}^{*}\|_{\infty}\sum_{i\in\supp({\boldsymbol x}^{*}-{\boldsymbol z}^{*})}|c_i|\,.
\end{eqnarray}
If $r=0$ we have ${\boldsymbol x}^*={\boldsymbol z}^{*}$ that justifies \eqref{eq:r_equals_0_gap}.
Further,  \eqref{gap-distance} implies  the bound
\begin{eqnarray*}
IG({\boldsymbol c}, {\boldsymbol a}, {b})\le (r+1)\|{\boldsymbol x}^{*}-{\boldsymbol z}^{*}\|_{\infty}\|{\boldsymbol c}\|_{\infty}
\end{eqnarray*}
that immediately gives \eqref{eq:r_equals_1_gap} and \eqref{eq:r_greater_1_gap}.

\section{Proof of Theorem \ref{t:IPTP_positive_knapsack_sharpness}}

For  $s\ge 2$ set
$
{\boldsymbol a}^{(s)}=(2^{s-1}, 2^{s-2}, \ldots,  1)^{\top}
$
and
$b^{(s)}= {\boldsymbol 1}^{\top}_s{\boldsymbol a}^{(s)}=2^{s}-1$. Let ${P}_I({\boldsymbol a}^{(s)}, {b}^{(s)})= \mathrm{conv} ({P}({\boldsymbol a}^{(s)}, {b}^{(s)})\cap \mathbb Z^s)$ be the {integer hull} of the knapsack polytope ${P}({\boldsymbol a}^{(s)}, b^{(s)})$.

We will need the following observations.
\begin{lemma}\label{vertex_integer_hull}
The point ${\boldsymbol 1}_{s}$ is a vertex of the polytope ${P}_I({\boldsymbol a}^{(s)}, {b}^{(s)})$.
\end{lemma}
\begin{proof}
We will use induction on $s$. The basis step $s=2$ holds as there are only two integer points ${\boldsymbol 1}_2$ and $(0,3)^{\top}$
in the polytope ${P}({\boldsymbol a}^{(2)}, {b}^{(2)})$.
To verify the inductive step, suppose that the result does not hold for some $s\ge 3$. Observe that any integer point ${\boldsymbol z}=(z_1, \ldots, z_s)^{\top}\in {P}({\boldsymbol a}^{(s)}, {b}^{(s)})$ has $z_1\le 1$. Consequently, ${\boldsymbol 1}_s$ belongs to the face ${P}_I({\boldsymbol a}^{(s)}, {b}^{(s)})\cap\{{\boldsymbol x}\in \mathbb R^s: x_1=1\}$ of the polyhedron ${P}_I({\boldsymbol a}^{(s)}, {b}^{(s)})$. Hence ${\boldsymbol 1}_s$ is a convex combination of some integer points in ${P}({\boldsymbol a}^{(s)}, { b}^{(s)})$ that have the first entry $1$.  Therefore, removing the first entry we obtain a convex combination of integer points from ${P}({\boldsymbol a}^{(s-1)}, {\boldsymbol b}^{(s-1)})$ equal to  ${\boldsymbol 1}_{s-1}$. The obtained contradiction completes the proof.
\end{proof}

For the rest of the proof we assume $s\ge 3$.
\begin{lemma}\label{vertex_sail}
The point ${\boldsymbol 1}_{s-1}$ is a vertex of the sail $\sail(\Lambda({\boldsymbol a}^{(s)}, {\boldsymbol b}^{(s)}))$.
\end{lemma}
\begin{proof}

Using  \eqref{affine_congruence}, the affine lattice $\Lambda({\boldsymbol a}^{(s)}, b^{(s)})$ can be written as
\begin{equation*}\label{affine_congruence_sharpness}
\Lambda({\boldsymbol a}^{(s)}, b^{(s)})= \{{\boldsymbol x}\in \mathbb Z^{s-1}:  2^{s-2}x_2+ \cdots+ x_{s}\equiv -1\, (\,\mathrm{mod}\; 2^{s-1})\}\,.
\end{equation*}
Therefore
\begin{eqnarray*} \label{simplex_boundary}
{\mathcal H}= \{{\boldsymbol x}\in \mathbb R^{s-1}: 2^{s-2}x_2+ \cdots+ x_{s}= 2^{s-1}-1\}\,
\end{eqnarray*}
is a supporting hyperplane of $\sail(\Lambda({\boldsymbol a}^{(s)}, { b}^{(s)}))$. Consequently,
\begin{eqnarray*}{P}_I({\boldsymbol a}^{(s-1)}, {b}^{(s-1)})={\mathcal H}\cap \sail(\Lambda({\boldsymbol a}^{(s)}, { b}^{(s)}))
\end{eqnarray*}
is a face of $\sail(\Lambda({\boldsymbol a}^{(s)}, { b}^{(s)}))$.
The result now follows by Lemma \ref{vertex_integer_hull}.

\end{proof}

For a positive integer $t$ set
\begin{eqnarray*}
{\boldsymbol a}^{(s)}(t)= (a^{(s)}_1(t), \ldots, a^{(s)}_s(t))^{\top}=(2^{s-1}, 2^{s-2}+t2^{s-1},\ldots, 1+t 2^{s-1})^{\top}
\end{eqnarray*}
and
$b^{(s)}(t)= {\boldsymbol 1}^{\top}_s{\boldsymbol a}^{(s)}(t)=2^{s} + (s-1)t2^{s-1}-1$. Consider the vertex ${\boldsymbol v}^{(s)}(t)=(b^{(s)}(t)/a_1^{(s)}(t)){\boldsymbol e}_1$ of the knapsack polytope ${P}({\boldsymbol a}^{(s)}(t), b^{(s)}(t))$.

In view of  \eqref{affine_congruence}, we have $\Lambda({\boldsymbol a}^{(s)}, b^{(s)})= \Lambda({\boldsymbol a}^{(s)}(t), b^{(s)}(t))$. Therefore, by Lemma \ref{vertex_sail}
the point ${\boldsymbol 1}_{s-1}$ is a vertex of the sail $\sail(\Lambda({\boldsymbol a}^{(s)}(t), { b}^{(s)}(t)))$. Observe that the sail $\sail(\Lambda({\boldsymbol a}^{(s)}(t), { b}^{(s)}(t)))$ is the image of the corner polyhedron $\CP_{{\boldsymbol v}^{(s)}(t)}({\boldsymbol a}^{(s)}, b^{(s)})$ under the bijective linear map $\pi_{\gamma}|_{{H}({\boldsymbol a}^{(s)}(t), b^{(s)}(t))}(\cdot)$. Using \eqref{structure_of_projection}, the point
\begin{eqnarray*}
{\boldsymbol 1}_s=\pi^{-1}_{\gamma}|_{{H}({\boldsymbol a}^{(s)}(t), b^{(s)}(t))}({\boldsymbol 1}_{s-1})
\end{eqnarray*}
is a feasible vertex of $\CP_{{\boldsymbol v}^{(s)}(t)}({\boldsymbol a}^{(s)}, b^{(s)})$.
Note also that  ${\boldsymbol 1}_s\in {P}({\boldsymbol a}^{(s)}(t), {b}^{(s)}(t))$.

It is now sufficient to show that  for any $\epsilon>0$
\begin{eqnarray}\label{sharp_a_}
\|{\boldsymbol v}^{(s)}(t)-{\boldsymbol 1}_s\|_{\infty}\frac{2^{s-1}}{s-1}>(1-\epsilon) \|{\boldsymbol a}^{(s)}(t)\|_{\infty}
\end{eqnarray}
for sufficiently large $t$. We have
\begin{eqnarray*}\label{sharp_a_1}
\|{\boldsymbol v}^{(s)}(t)-{\boldsymbol 1}_s\|_{\infty}=\left|\frac{b^{(s)}(t)}{a_1^{(s)}(t)}-1\right | = (s-1)t+1-\frac{1}{2^{s-1}}\,.
\end{eqnarray*}
Finally,
\begin{eqnarray*}
\frac{\|{\boldsymbol v}^{(s)}(t)-{\boldsymbol 1}_s\|_{\infty}}{\|{\boldsymbol a}^{(s)}(t)\|_{\infty}}= \frac{(s-1)t+1-2^{-(s-1)}}{2^{s-2}+t2^{s-1}}\longrightarrow\frac{s-1}{2^{s-1}}
\end{eqnarray*}
as $t\rightarrow\infty$, that implies (\ref{sharp_a_}).

\section{Proof of Theorem \ref{thm:UpperBound}}

We will apply the following result by Bombieri and Vaaler \cite{BombVaal}.

\begin{thm}[{\cite[Theorem~2]{BombVaal}}]\label{eq:sl_sl_f}
Let $A\in \mathbb Z^{m\times n}$, $m<n$, be a matrix of rank $m$. There exist $n - m$ linearly independent integral vectors ${\boldsymbol y}_1, \ldots,{\boldsymbol y}_{n-m} \in \Gamma(A)$ satisfying
\begin{equation*}
 \prod_{i=1}^{n-m} \| {\boldsymbol y}_i\|_{\infty} \le \frac{\sqrt{{\rm det}(AA^{T})}}{\gcd(A)}\,.
 \end{equation*}
\end{thm}

Let ${\boldsymbol z}^*$ be a vertex of the integer hull ${P}_I(A, {\boldsymbol b})$ that gives an optimal solution to \eqref{eq:mainProblem}.
We will show that ${\boldsymbol z}^*$  satisfies \eqref{t:Bound_via_transference}.
First, we argue that it suffices to consider the case $\|\boldsymbol z^*\|_0=n$.
Suppose that $\|\boldsymbol z^*\|_0<n$. For $\tau=\supp(\boldsymbol z^*)$ set
$\bar A=A_\tau$, $\bar{\boldsymbol b}=\boldsymbol b$, $\bar{\boldsymbol c}=\boldsymbol c_\tau$, and $\bar{\boldsymbol z}^*=\boldsymbol z^*_\tau$.
By removing linearly dependent rows, we may assume that $\bar A$ has full row rank. Let $\bar m = \mathrm{rank}(\bar A) \le m$.
Observe that  $\bar{\boldsymbol z}^*$ is an optimal solution for the corresponding problem \eqref{eq:mainProblem} with minimal support.
Furthermore, note that $\bar{\boldsymbol z}^*$ has full support.
Now, if \eqref{t:Bound_via_transference} holds true for $\bar{\boldsymbol z}^*$, then
\begin{eqnarray}\label{split_rho_1}
(\rho({\boldsymbol z}^*)+1)^{s-m}\le (\rho(\bar{\boldsymbol z}^*)+1)^{s-\bar m}\le \frac{\sqrt{\det(\bar A\bar A^{\top})}}{\gcd(\bar A)}\,.
\end{eqnarray}
Further, using \cite[Lemma~2.3]{ADON2017} we have
\begin{eqnarray}\label{split_rho_2}
\frac{\sqrt{\det(\bar A\bar A^{\top})}}{\gcd(\bar A)}\le \frac{\sqrt{\det(AA^{\top})}}{\gcd(A)}\,.
\end{eqnarray}
Combining \eqref{split_rho_1} and \eqref{split_rho_2}, we obtain \eqref{t:Bound_via_transference}.

From now on, we may assume that $\|\boldsymbol z^*\|_0=n$. Suppose, to derive a contradiction, that \eqref{t:Bound_via_transference} does not holds, that is $(\rho({\boldsymbol z}^*)+1)^{n-m}> (\gcd(A))^{-1}\sqrt{\det(AA^{\top})}$. By Theorem \ref{eq:sl_sl_f}, there exists a vector $\boldsymbol y\in\mathbb Z^n\setminus\{\boldsymbol 0\}$ such that
$$A\boldsymbol y=\boldsymbol 0 \;\; \text{ and } \;\; \|\boldsymbol y\|_\infty\le\left(\frac{\sqrt{\det(AA^{\top})}}{\gcd(A)}\right)^{\frac{1}{n-m}}<\rho({\boldsymbol z}^*)+1.$$
It follows that both $\boldsymbol z^* + \boldsymbol y$ and $\boldsymbol z^* - \boldsymbol y$ are in the knapsack polytope ${P}(A, {\boldsymbol b})$. Therefore $\boldsymbol z^*$ is not a vertex of ${P}_I(A, {\boldsymbol b})$.
The obtained contradiction completes the proof.

\bibliographystyle{plain}