%THIS CONTAINS CORRECTION AFTER THE PAPER WAS SENT TO COMBINATORICA.
%IN PARTICULAR, THEOREM 7.1 IS NOW CHANGED TO SAY THAT THE RIGHT HAND
%SIDES SPACE IS PARTITIONED INTO SETS OF THE FORM (POLYHEDRA/INTEGER LATTICE)
%NOT JUST POLYHEDRA AS BEFORE. THIS VERSION WAS SENT TO COMBINATORICA IN
%APRIL 1991.
\documentstyle[12pt]{article}
\newcommand{\proofend}{\begin{flushright}
\vrule height4pt width3pt depth2pt \end{flushright} }
\begin{document}
\baselineskip 16pt \lineskip 2.5pt
\def \lin {\hbox{ lin}}
\def\width {\hbox{ Width}}
\begin{center}
{\Large \bf SOLUTION OF THE FROBENIUS PROBLEM AND ITS GENERALIZATION}
Ravi Kannan\footnote {Supported by NSF-Grant CCR 8805199}
November 27,1989
\end{center}
{\bf Abstract } This paper considers the ``Frobenius
problem'' : Given $n$ natural numbers $a_1,a_2,\ldots a_n$ such that their
greatest common divisor is 1, find the largest
natural number that is not expressible as a nonnegative integer combination
of them. This problem can be seen to be
NP-hard. For the cases $n=2,3$ polynomial time
algorithms are known to solve it. Here a polynomial time algorithm is given
for every fixed $n$. This is done by first proving an exact
relation between the Frobenius problem and a geometric concept called
the ``covering radius''. Then a
polynomial time algorithm is developed for finding the covering radius of
any polytope in a fixed number of dimensions. The last algorithm relies on a
structural theorem proved here that describes for any polytope $K$, the set
$K+{\bf Z}^n=\{ x : x\in {\bf R}^n\ ;\ x=y+z\ ; \ y\in K\ ;\ z\in {\bf
Z}^n\}$ which is the portion of space covered by all lattice translates of
$K$.
The proof of the structural theorem relies on some recent
developments in the Geometry of Numbers. In particular, it uses
a theorem of Kannan and Lov\`asz [\ref{kl}],
bounding the width of lattice-point-free
convex bodies and the techniques of Kannan, Lov\'asz and Scarf [\ref{kls}]
to study the shapes of a polyhedron obtained by translating each facet
parallel to itself. The concepts involved are defined from first principles.
In the last section, I develop
an algorithm which is polynomial time
bounded for fixed $p,n$ to decide the
truth / falsity of any sentence of the following form (where $Q$ is a given
copolyhedron in ${\bf R}^p$ and $A,B,b$ are given matrices of suitable
dimensions. See Notation below.)
$$\forall y\in Q/{\bf Z}^l\quad \exists x\in {\bf Z}^n \quad Ax+By\leq b.$$
The sentence says in words : for every $y$ for which an integer vector
$z\in {\bf Z}^l$ exists such that $(y,z)$ is in $Q$, there exists also an
integer vector $x$ so that $Ax+By\leq b$.
The Frobenius problem can be easily reduced to such a sentence.
{\bf Notation }
${\bf R}^n$ is Euclidean $n$ space. The lattice of all integer vectors in $
{\bf R}^n$ is denoted ${\bf Z}^n$. For any two sets $S,T\subseteq {\bf
R}^n$, we denote by $S+T$ the set $\{ s+t : s\in S;t\in T\}$. For any
positive real, $\lambda $, we denote by $\lambda S$, the set $\{\lambda
s : s\in S\}$. For any set $W$ in ${\bf R}^{n+l}$ and any set $V$ in
${\bf R}^l$, we denote by $W/V$ the set
$$\{ x : x\in {\bf R}^n\ \hbox{
such that there exists a }\ y\in V\hbox{ with } (x,y)\in W\}.$$
$W/V$ is the set obtained by ``projecting out'' $V$ from $W$.
A {\bf copolyhedron} is the intersection of a finite number of half
spaces - some of them closed and the others open. (``co'' for closed /
open.) If a copolyhedron is bounded, I will call it a copolytope.
Some statements in the paper will assert ``the algorithm {\it finds}
copolytope $P_i$.......''. The precise meaning of this statement is as
follows : suppose $P_i$ is in ${\bf R}^n$. The algorithm will find a
rational $m\times (n+l)$ matrix $C$ and a rational $m\times 1$ vector
$b$ where $l$ is at most some polynomial function of $n$ and for each
row of $C$, either the $\leq $ or the $<$ sign such that $P_i$ equals
$$\{ x : x\in {\bf R}^n\ \hbox{
such that there exists a }\ y\in {\bf R}^l
\hbox{ with } C{x\choose y}{\leq\choose <}b\}.$$
By a ``rational polyhedron'', we mean a polyhedron that can be described by
a system of inequalities that have rational coefficients; the inequalities
may have irrational right hand sides.
In much of the paper $A$ will be a fixed $m\times n$ matrix. If the
meaning of $A$ is clear from the context, for any $b$ in ${\bf R}^m$,
the polyhedron $\{x\in {\bf R}^n : Ax\leq b\}$ will be denoted by $K_b$. In
much of the paper, $b$ will vary over some copolyhedron in ${\bf R}^m$.
Some bounds in the paper will be in terms of the affine dimension $j_o$
of this copolyhedron. Except for Theorem (7.2), this generality is not
strictly needed. The reader may restrict attention to the case when
$j_o=m$ for the first reading. The
``size'' of a rational matrix is the number of bits needed to express it. It
is assumed that integers are written in binary notation, so it takes a $O(\log
M)$ length string to express an integer of magnitude $M$.
A basis $B$ of the lattice ${\bf Z}^n$ is a set of $n$ linearly independent
vectors $\{ b_1,b_2,\ldots b_n\}$ in ${\bf Z}^n$,
such that each member of ${\bf Z}^n$
can be expressed as an integer linear combination of $\{ b_1,b_2,\ldots
b_n\}$. The ``fundamental parallelopied'' corresponding to $B$ is the set
$\{ x : x = \sum _{i=1}^n \lambda _i b_i\hbox{ where }\lambda_i \in {\bf
R}\hbox{ satisfy } 0\leq \lambda_i < 1\}$. It is denoted $F(B)$. For each
point $y$ in ${\bf R}^n$, there is a unique lattice point $z$ such
that $z+F(B)$ contains $y$. The parallelopied $z+F(B)$ is denoted
$F(B;y)$. It is an elementary fact that the set of integer solutions to
a linear system of congruences i.e., a set of the form $\{ (x_1,x_2,
\ldots x_n) : \sum_{i=1}n a_ix_i\equiv 0 (mod p)\} $ where $a_i,p$
are natural numbers, is a lattice. This fact will be used once only in the
paper, in section 2.
In most of the paper, the only lattices that occur are ${\bf Z}^r$ for
some natural number $r$. In section 2, we use more general lattices. A
lattice in general is the set of all integer linear combinations of a set of
linearly independent vectors in Euclidean space.
\section{Introduction}
The Frobenius problem can be rephrased as follows : ``Given $n$ coins
of denominations $a_1,a_2,\ldots a_n$, with GCD$(a_1,a_2,\ldots a_n)$ equal
to 1, what is the largest integer amount of money for which change cannot be
made with these coins ? '' Note that the GCD condition implies that we can
in fact make change for any large enough integer amount of money.
The simple statement of the Frobenius problem makes it
attractive. Not surprisingly, the Frobenius problem is NP-hard in general.
This is not proved in this paper. For
the special case of $n=2$, the answer is explicitly known - it is
$a_1a_2-a_1-a_2$. The proof of this is elementary. (For example, this
follows from Theorem 2.1.)
Algorithms to solve the Frobenius problem
in the case $n=3$ were recently developed by R\"odseth [\ref{rodseth}],
Selmer and Beyer[\ref{sb}] Greenberg[\ref{green}] and Scarf and Shallcross
[\ref{ss}]. There is a substantial
literature on
the general problem - see for example [\ref{hv}] and the bibliography in
[\ref{selmer}], [\ref{erdos}].
No polynomial time is known for fixed $n$ greater than 3.
This paper develops one for any fixed $n$. It might seem that this result
would follow from the result of Lenstra [\ref{lenstra}] that Integer
Programming in a fixed number of variables can be solved in polynomial time
; but note that a n\"aive solution to the Frobenius problem involves solving
(in the worst case) an exponential number of Integer Programs - one each to
determine for each natural number $b$ whether $b$ can be expressed as a
nonnegative integer combination of $a_1,a_2,\ldots a_n$. Some pruning is
possible, but no such direct method is known to work. For an approximation
algorithm, see [\ref{paz}].
The Frobenius problem is related to the study of
maximal lattice point free convex bodies, a topic of long-standing interest
in the Geometry of Numbers. This relation is described by Lov\'asz in
[\ref{lovasz}]. He also formulates a conjecture which he proves would imply
a polynomial time algorithm for the Frobenius problem for a fixed number of
integers. The structural result of this paper does not prove this
conjecture, but does imply a closely related one as shown in section 7
. Scarf and Shallcross
[\ref{ss}] have recently observed a somewhat direct relation between maximal
lattice free convex bodies and the Frobenius problem.
There have been some applications of the Frobenius problem
to a sorting method called Shell-Sort - see for example Incerpi and Sedgwick
[\ref{sedgwick}] and Sedgwick [\ref{sedgwick2}].
In section 2, the Frobenius problem for $n$ coins is exactly related to the
``covering radius'' of a certain simplex in ${\bf R}^{n-1}$. The notion of
covering radius for centrally symmetric convex sets
is a classical notion in the Geometry of Numbers ; in
[\ref{kl}], it was introduced and studied for general convex sets. It is
defined as follows :
For a closed bounded convex set $P$ of nonzero volume in ${\bf
R}^n$, and a lattice $L$ of dimension $n$ also in ${\bf R}^n$,
the least positive real $t$ so that $tP +
L$ equals ${\bf R}^n$ is called the ``covering radius'' of $P$ with respect
to $L$. It will be denoted by $\mu (P,L)$.
In words, the covering radius is the least amount $t$ by which we
must ``blow up'' $P$ and one copy of $P$ placed at each lattice point so
that all of space is covered.
Suppose $K$ is a closed bounded convex set in ${\bf R}^n$
and $v$ is an element of ${\bf R}^n$. The {\bf width of $K$ along $v$} is
$$\max\{ v\cdot x :x\in K\} - \min\{v\cdot x : x\in K\}.$$
The {\bf width of $K$ } (with respect to the lattice ${\bf Z}^n$ )
is defined to be the
minimum width of $K$ along any nonzero integer vector. Note that this
differs from the usual
definition of the geometric width of $K$, where the minimum is over
all vectors $v$ of length 1, rather than all nonzero integer vectors.
The width as defined here is greater than or equal to the
geometric width since nonzero integer vectors have length at least one.
The following theorem will be used.
{\bf Flatness Theorem } [\ref{kl}] There is a universal constant $c_o$ such
that any closed bounded
convex set $K$ in ${\bf R}^n$ of width
at least $c_o n^2$ contains a point of ${\bf Z}^n$.
{\bf Remark } : The constant $c_o$ will be used throughout the paper. By
looking at the case $n=1$, we see that $c_o$ must be at least 1, a fact
that we will use.
Kannan, Lov\'asz and Scarf
[\ref{kls}] show that for any fixed $m\times n$ matrix $A$ satisfying
some nondegeneracy condition, there is a small finite set $V$ of nonzero
integer vectors such that for any ``right hand side'' $b$, there is some
$v(b)$ belonging to $V$ such that the polytope
$K_b=\{ x : Ax\leq b\} $ has approximately the smallest width along
$v(b)$; more precisely, the width of $K_b$ along $v(b)$ is at most
twice the width of $K_b$ along any nonzero integer vector. Section 3 of
this paper proves from first principles
a result in the same spirit. There are two differences -
here, I do not assume any nondegeneracy condition. Secondly, in the result
here, $b$ is allowed to vary over some subset of ${\bf R}^m$
and the upper bound on the cardinality of $V$ is in terms of the dimension
of the affine hull of this subset. Letting the subset be the whole of ${\bf
R}^m$, we can recover a result similar to [\ref{kls}].
The result of
section 3 will be used in the main structural theorem proved in section 4
which describes the set $K+{\bf Z}^n$ where $K$ is a polyhedron. The
proof of this theorem is by induction ; the inductive proof will need a
``uniform'' description of $K+{\bf Z}^n$ as each facet of $K$ is moved
parallel to itself in some restricted fashion. In this context, the theorem
of section 3 comes in useful.
Section 5 gives a polynomial time algorithm for finding the covering radius
of a polytope in a fixed number of dimensions using the theorem of section 4.
Thus also, the Frobenius problem is solved for fixed $n$ in the sense of a
polynomial time algorithm.
In both sections 3 and 4, the ``right hand side'' $b$ is allowed to vary
only over a bounded set. Section 6 proves the theorem of section 4
without such a restriction.
The result of section 6 is used to produce a ``test set'' for Integer
Programming - see Theorem (7.1). This theorem is then used to design a
decision procedure for sentences of the form mentioned in the Abstract - see
Theorem (7.2). In particular, the decision procedure decides in polynomial
time (for fixed $n,p$), the truth / falsity of a sentence of the form
$$\forall y\in {\bf Z}^p\quad\exists x\in {\bf Z}^n\quad : Ax+By\leq b.$$
This is a generalization of Lenstra's result which gives a polynomial time
algorithm for deciding sentences of the form
$$\exists x\in {\bf Z}^n \quad : Ax\leq b.$$
It is an interesting open problem to devise such algorithms for sentences
with a higher number of alternations, in particular for sentences of the form
$$\exists z\in {\bf Z}^p\quad \forall y\in {\bf Z}^q \quad\exists x\in
{\bf Z}^n \quad : Ax+By+Cz\leq b.$$
See Remark 4 of section 8.
\section{Frobenius problem to Covering Radius}
For $a_1, a_2 \ldots, a_n$ positive integers
with $GCD(a_1 \ldots, a_n) = 1$, let $Frob(a_1 \ldots, a_n) =$ largest
natural number $t$ such that $t$ is not a nonnegative integer combination
of $a_1 \ldots, a_n$. The aim of this section is to relate
$Frob(a_1,a_2,\ldots a_n)$ to the covering radius of a certain $n-1$
dimensional simplex. This is done in Theorem (2.5).
{\bf (2.1) Theorem} [\ref{bs}]
$$Frob(a_1 \ldots, a_n) = \max_{l \in \{1,2 \ldots,
a_n-1\} } t_l -a_n\eqno (2.2)$$
where $t_l =$ the smallest positive integer congruent to $l$ modulo $a_n$,
that is expressible as nonnegative integer combination of $a_1 \ldots,
a_{n-1}$.\\
{\bf Proof}: The proof is rather simple.
Let $N$ be any positive integer. If $N \equiv
0 (mod \; a_n)$, then $N$ is a nonnegative
integer combination of $a_n$ alone. Otherwise, if
$N \equiv l (mod \; a_n)$, then $N$ is a nonnegative integer combination of
$a_1 \ldots, a_n$ iff $N \geq t_l$.
\proofend
$$\hbox{Let }\quad
L= \{ (x_1 \ldots, x_{n-1}): x_i \hbox{ integers and }\sum_{i=1}^{n-1}
a_i x_i \equiv 0(mod \;a_n) \}\eqno (2.3) $$
$$\hbox{ and let }
\quad S = \{ (x_1, x_2 \ldots, x_{n-1}): x_i \geq 0 \hbox{ reals and }
\sum_{i=1}^{n-1} a_i x_i \leq 1 \}\eqno (2.4)$$
{\bf (2.5) Theorem }
$\mu (S,L) = Frob(a_1, a_2 \ldots, a_n) + a_1 +a_2 + \ldots + a_n\quad $
where $\mu (S, L)$ is the covering radius of $S$ with respect to $L$.
{\bf Proof}: Abbreviate $Frob(a_1,a_2,\ldots, a_n)$ by $F$ and $\mu(S,L)$ by
$\mu$.
First, I show $\mu \leq F+ a_1 +a_2 \ldots + a_n$. Suppose $y \in
{\bf Z}^{n-1}$, and $\sum_1^{n-1} a_i y_i \equiv l (mod \; a_n).$ By
definition of $t_l, \exists x_1, \ldots, x_{n-1}, x_n \geq 0$ integers such
that $\sum_{i=1}^{n-1} a_i x_i = t_l = l + a_n x_n$; thus with $x^\prime
=(x_1 \ldots, x_{n-1})$, we have $(y-x^\prime) \in L$ and
$(y-x^\prime) + t_lS$ contains $y-x^\prime+ x^\prime =y$. Since this is
true of any $y\in {\bf Z}^{n-1}$, and $t_l \leq F + a_n$, we have:
$$ {\bf Z}^{n-1} \subseteq (F+a_n) S+L\eqno (2.6)$$
Further it is clear that
${\bf R}^{n-1} \subseteq {\bf Z}^{n-1} + (a_1 + \ldots + a_{n-1})S$. To see
this, note that for $z \in {\bf R}^{n-1}$, we have $\lfloor z \rfloor =
( \lfloor z_1 \rfloor, \ldots \lfloor z_{n-1} \rfloor ) \in
{\bf Z}^{n-1}$ and $(z- \lfloor z \rfloor ) \in (a_1 + a_2 \ldots +
a_{n-1})S$. Hence I have shown
$${\bf R}^{n-1}\subseteq {\bf Z}^{n-1} + (a_1 + \ldots + a_{n-1}) S
\subseteq (F + a_1 + \ldots + a_n) S +L\eqno (2.7) $$
Now for the converse: Consider $(F+a_n) S+L$. I claim that $F+a_n$ is the
smallest positive real $t$ such that $tS + L$ contains ${\bf Z}^{n-1}.$
Suppose, for some $t^\prime < F +a_n,\quad t^\prime S + L$ contains ${\bf
Z}^{n-1}$. Then for any $l \in \{1, \ldots, a_n -1 \}$, pick a $y
\in {\bf Z}^{n-1}$, such that $\sum_1^{n-1} a_i y_i \equiv l(mod \;
a_n)$. $y$ is in $t^\prime S + x$ for some $x$ in $L$, so $(y-x)$ is in
$t^\prime S$. But $\sum_1^{n-1} a_i (y_i-x_i) \equiv l(mod \;a_n)$ and $y_i
-x_i \geq 0 \forall_i$, implies that $t_l \leq t^\prime$. Since this is
true of any $l$, we have $F \leq t^\prime -a_n < F$ a contradiction
(using Theorem (2.1)).
Thus I have shown:
$$\ \ F+a_n = \min \{ t: t > 0, \hbox{ real and } tS +L \supseteq {\bf
Z}^{n-1}\}\eqno (2.8)$$
By (2.8), we see that $\exists y \in {\bf Z}^{n-1}$, such that for any $x
\in L$, with $y_i - x_i \geq 0 \forall i$, we have $\sum_{i=1}^{n-1}
a_i (y_i - x_i) \geq F + a_n$. Now let $\epsilon$ be any real number
with $0 < \epsilon < 1$ and consider the point $p = (p_1, p_2,\ldots p_{n-1})$
defined by $p_i = y_i + (1-\epsilon) \forall i$. Suppose $q$ is any
point of $L$ such that $p_i \geq q_i \forall i$. Then $q_i$ are all
integers, so we must have
$q_i \leq y_i \forall_i .$
$$ \hbox{So, }
\sum_1^{n-1} a_i (p_i -q_i) = ( \sum _1^{n-1} a_i) (1-\epsilon )
+ \sum_1^{n-1} a_i (y_i-q_i)
\geq (1-\epsilon) \sum_1^{n-1} a_i + (F+a_n)$$
by the above.
Since this argument holds for any $\epsilon \in (0\ \ 1)$, we have $\mu\geq F
+ \sum_1^n a_i$.
Together with (2.7) now, Theorem (2.5) is proved.
\proofend
{\bf Remark } : By applying a suitable linear transformation, we can
``send'' $L$ to ${\bf Z}^{n-1}$. This sends the simplex $S$ to some
simplex whose constraint matrix is still rational. It is easy to see that
applying the same linear transformation to $S$ and $L$ leaves the covering
radius unchanged.
I assume this has been
done ; in the coming sections, I will deal only with covering radii of sets
with respect to the standard lattice of integer points.
It is assumed that the reader is familiar with computational aspects of
linear algebra; I omit the details of how the linear trnasformation above
is applied etc.. For a thorough introduction to such matters, the reader is
referred to [\ref{schrijver}].
\section{Vectors along which $K_b$ have small width}
Our main aim is to develop an algorithm to find the covering radius of a
polytope $K=\{ x : Ax\leq b\}$. As will be explained in the beginning of
section 4, it will be useful to deal with $K_b$ where $b$ is allowed to vary
over some copolytope. This section will develop the tools needed for section
4. For each fixed $b$, there is an nonzero integer direction that acheives the
minimum width of $K_b$. The main result of this section is lemma 3.1 which
says that we can compute
a small number of nonzero integer directions such that
as $b$ varies over a large set, for each $K_b$, one of our directions
acheives close to minimum width. This is the third point in the conclusion of
lemma 3.1, the first two are technical ones that are needed for theorem 4.1.
{\bf (3.1) Lemma } : Suppose $A$ is an $m\times n$ matrix of integers of
size $\phi $.
For each $b\in {\bf R}^m$, we denote by $K_b$ the polyhedron $\{ x
: Ax\leq b\} $.
Let $P$ be a copolytope in ${\bf R}^m$ of affine dimension
$j_o$ such that for all $b\in P,\ \ \ K_b$ is nonempty and bounded.
Let $M$ be $\max \{ |b| : b\in P\}$.
There is an algorithm that finds a partition of $P$ into
copolytopes $P_1,P_2,\ldots P_r$ where $r$ is at most $m^{3n+j_o}
\left( 2 \log_2 M+ 12n^2\phi )\right) ^{n+j_o}$,
and for each copolytope $P_i$, it finds a
nonzero integer vector $v_i$ and $n\times m$ matrices
$T_i,T_i^\prime $ such that
for all $i$, $1\leq i\leq r$ and all $b\in P_i$, we have
\begin{enumerate}
\item The point $T_i b$ maximizes the linear function $v_i\cdot x$ over
$x$ in $K_b$.
\item The point $T_i^\prime b$ minimizes the linear function $v_i\cdot
x$ over $x$ in $K_b$ and
\item $$\hbox{ either }\quad \width _{v_i}(K_b)\leq 1$$
$$\hbox{ or } \forall u\not= 0 , u\in {\bf Z}^n, \hbox{ Width} _{v_i}(K_b)
\leq 2\hbox{Width} _u(K_b).$$
\end{enumerate}
Further, the algorithm works in time polynomial in data and $\log M$
if $n,j_o$ are fixed.
{\bf Proof }
I first describe how to find the nonzero integer vectors $v_1,v_2,\ldots $
with which to prove the theorem and then describe how to find the partition
of $P$. The first $m$ of the vectors will be the rows of $A$. We note that
every $K_b$ of zero volume has width 0 along one of these $m$ vectors. Also,
if a $K_b$ has width at most 1 along one of these $m$ directions, it is
``taken care of'' by that direction. So we only need the rest of the vectors
to take care of full-dimensional $K_b$ with width at least 1 along each of
the $m$ facet directions.
Since $K_b$ is bounded, we have that
$K_b$ is contained in a ball of radius $M2^{4n^2\phi}$ [\ref{schrijver},
Theorem 10.2] around the origin. Also, $K_b$ has a centroid - say -
$x_o$. (The centroid $x_o$ is the unique point such that
$\int _{K_b} (x-x_o) dx =0$. )
Consider $K_b - x_o $. Let this be $\{ x : Ax\leq b^\prime \}$.
Note that $b^\prime $ belongs to $P^\prime =P+ $( column space of $A$ ) which
is a set of affine dimension at most $n+j_o$ .
By the above, $0 < b_i^\prime \leq M2^{5n^2\phi } \forall i $. By a
property of the centroid (namely, if $y_o$ is the centroid of a
bounded convex set $K$ in ${\bf R}^n$, then for any $z\in K$, we have
$(1+{1\over n})y_o-{1\over n}z\in K$.)
, and the lower bound of 1 on the width of
$K_b$ in any of the facet directions, we have that
$${1\over (n+1)}\leq b_i^\prime \leq M2^{5n^2\phi }\forall i.$$
Let $R\subseteq {\bf R}^m$ be the rectangular solid $\{ y :
{1\over (n+1)}\leq y_i \leq M2^{5n^2\phi }\forall i\} $. Applying
lemma (3.3) with $Q=$ the affine hull of $P^\prime $
, we get a finite set $V^\prime $ in ${\bf R}^m$ such
that for each $y\in R\cap P^\prime $, there is a $y^\prime \in V^\prime
$ with $ y^\prime \leq y\leq 2 y^\prime $. (Note that by that lemma, the set
$V^\prime $ can be found in polynomial time when $n,j_o$ are fixed.)
For each $y^\prime $ in $V^\prime $ such that $K_{y^\prime }$ is full
dimensional, we find the nonzero integer vector that attains the width of
$K_{y^\prime }$. This set of nonzero integer vectors
suffices as our set of
$v_i$ 's. This is so because $y^\prime \leq y\leq 2y^\prime $ implies that
$K_{y^\prime }\subseteq K_y\subseteq K_{2 y^\prime }$ which implies that for
any nonzero vector $v$, $\width _v(K_{y^\prime })\leq \width _v (K_y)
\leq \width _v(K_{2y^\prime })$.
(The nonzero integer vector along which the width of
a polyhedron is minimised, can be found in polynomial time
for a fixed number of dimensions - see [\ref{kl} (1986) version].)
We now have a set of vectors $v_1,v_2,\ldots $ such that each of the
relevant $K_b$ has ``small'' width (``Small'' will
mean either at most 1 or at most twice the minimum width along any nonzero
integer direction.)
along one of these vectors. For each
$v_i$, we perturb it slightly to get a $v_i^\prime $ with the property
that (i) for any $b\in P$, a vertex of $K_b$ achieves the maximum
(minimum) of the
linear function $v_i^\prime \cdot x$ over $K_b$ iff it achieves the
maximum (respectively minimum) of $v_i\cdot x$ over $K_b$ ; and (ii)
for each $b$ in $P$, there is a unique vertex of $K_b$ that achieves
the maximum and a unique vertex that achieves the minimum of $v_i^\prime
\cdot x$ over $K_b$. This is possible with an increase in size by at most a
polynomial additive term. (For example, see [\ref{schrijver}].)
Consider each of the (at most $m^n$) nonsingular
$n\times n$ submatrices $B$ of $A$. For each of these we can define an
$n\times m$ matrix $T$ by augmenting $B^{-1}$ with 0 columns so that
the possible corners of any $K_b$
are of the form $Tb$ for such $T$. I will denote by $f(T)$ the ordered
subset of $\{ 1,2,\ldots m\}$ of cardinality $n$ that contains the
indices of the rows of $A$ that go into $B$. Let $f(T) = \{
f_1(T),f_2(T),\ldots f_n(T)\}$. We let $f_0(T)$ be zero for all $T$.
If there is degeneracy, it may happen that
a vertex $v$ of some $K_b$ equals $Tb$ for more than one $T$. In
that case, we will say that $T$ is the lexicographically least one
defining the vertex
$v$ if the set $f(T)$ is lexicographically least among all
``basis'' sets that define $v$. This can be expressed more precisely as
follows : let $g(T)$ be the set of $l$ such that for $s$ with $f_s(T) < l
< f_{s+1}(T)$, we have that row $l$ of $A$ is independent of rows
$f_1(T),f_2(T),\ldots f_s(T)$ of $A$.
Then, we say that $v=Tb$ satisfies $Av\leq b$ and for each $l$ in
$g(T)$, we have the $l$ th component of $Av$ is strictly less than
$b_l$.
We order the $T$ 's and call them
$T_1,T_2,\ldots $. There will be one copolytope $P(T_i,T_j,v_k)$ for
each triple $i,j,k$ in the partition of $P$. The copolytope $P(T_i,T_j,v_k)$
will be the set of all $b$ 's in $P$ for which
\begin{itemize}
\item $p=T_i b$ and $q=T_j b$ belong to $K_b$. Further, $T_i$ is the
lexicographically least one that defines $p$ and the same for $T_j$ and
$q$.
\item The maximum value of $v_k^\prime \cdot x$ over $K_b$ is attained
at $T_ib$.
\item The minimum value of $v_k^\prime \cdot x$ over $K_b$ is attained
at $T_j b$.
\item For each $l < k$, there exist $x^{(l)},y^{(l)}$ in $K_b$, such
that $v_l\cdot (x^{(l)}-y^{(l)} ) > v_k\cdot (T_i b -T_j b)$.
\item For each $l>k$, there exist $x^{(l)},y^{(l)}$ in $K_b$, such
that $v_l\cdot (x^{(l)}-y^{(l)} ) \geq v_k\cdot (T_i b -T_j b)$. (This and
the previous condition say that the width of $K_b$ along $v_k$ is the
least among all the directions $\{ v_l\}$.
The strict inequality in the previous
condition is there to ensure that each $b$ belongs to only one
$P(T_i,T_j,v_k)$.
\end{itemize}
{\bf (3.2) Claim } Each $P(T_i,T_j,v_k)$ defined above is a copolytope. The
copolytopes form a partition of $P$. For each $b\in P(T_i,T_j,v_k)$, we
have that $K_b$ has small width (at most 1 or at most twice the minimum
in any integer direction) along $v_k$ and further $T_ib$ maximizes $v_k\cdot
x$ over $K_b$ and $T_jb$ minimizes $v_k\cdot x$ over $K_b$.
{\bf Proof } To prove the first statement, I will show that each of the
above conditions in the definition of $P(T_i,T_j,v_k)$ can be expressed by
linear constraints possibly with the introduction of new variables. Only the
second and third condition need any explanation at all. The second
condition is expressed by complementary slackness of linear programming -
namely, we say that the complementary solution is feasible to the dual,
i.e., that $v_k B_i^{-1}\geq 0$ where $B_i$ is the $n\times n$ basis
matrix corresponding to $T_i$. Note that in fact, this statement does not
involve $b$, so it need not be included as a constraint, if it is not
satisfied, then the $P(T_i,*,v_k)$ is empty for all $*=T_j$, so these
pieces need not be included in the partition of $P$. Condition 3 is
treated similarly.
The statement in the claim that the copolytopes form a partition of $P$
is easy to see : if $b$ belongs to $P(T_i,T_j,v_k)$, then the width of
$K_b$ along $v_k$ is less than its width along $v_1,v_2,\ldots
v_{k-1}$ and at most its width along $v_{k+1},\ldots $, so $v_k$ is
uniquely determined by $b$. Then clearly, by the perturbation, $T_i$ and
$T_j$ are uniquely determined.
The rest of the claim is easy to see.
\proofend
Now for the lemma : we may return the partition $\{ P(T_i,T_j,v_k) \}$ of
$P$, and associated with $P(T_i,T_j,v_k)$, the vector $v_k$ and the
matrices $T_i,T_j$ to satisfy the lemma. The upper bound on $r$, the number
of elements in the partition is easily obtained.
\proofend
{\bf (3.3) Lemma }
Let $R\subseteq {\bf R}^m$ be the rectangle $\{ y : \alpha \leq
y_i\leq \beta \forall i\}$ where $0 < \alpha \leq \beta $
are arbitrary rationals.
Let $Q$ be any affine subspace of ${\bf R}^m$ with dimension say $t$.
Then there exist a finite set $V^\prime $ in ${\bf R}^m$ with $|V^\prime |\leq
\left( 2m(\log_2{\beta \over \alpha }+1)\right) ^t $ such
that for each $y\in R\cap Q $, there is a $y^\prime \in V^\prime
$ with $y^\prime\leq y \leq 2 y^\prime $.
Further, given $R,Q$, the set $V^\prime $ can be found in polynomial time
provided $n,t$ are fixed.
{\bf Proof } : Divide $R$ into sub-rectangles each of the form
$$\{z: \alpha 2^{p_i} \leq z_i \leq \alpha 2^{p_i +1} \; {\rm for} \; i=1, 2
\ldots, m\}$$
where $p_1, p_2 \ldots, p_m$ are natural numbers between 0 and
$l=\log _2(\beta /\alpha )$. I will show by induction on the pair $t,m$
that $Q\cap R$ is contained in the union of some
$$2^t m^t (l+1)^t$$ subrectangles of $R$ which clearly proves the lemma.
The case $t=0$ is clear for all $m$. The case $m=0$ is trivial. For
higher $t$, note that if $Q$ intersects a subrectangle, it intersects the
boundary of the subrectangle. For any $i, 1 \leq i \leq m$ and any $p_i, 0
\leq p_i \leq l$, consider the $(m-1)$-dimensional rectangle $R^\prime = R
\cap \{ z: z_i = 2^{p_i}\alpha \} $ and the division of it into subrectangles
``induced'' by the division of $R$. Also, let $Q\cap\{ z:z_i=2^{p_i}\alpha\}$
be $Q^\prime $. If for any $i$ and any $p_i$, such a $Q^\prime $
equals $Q$, we have the lemma by induction on $m$. So assume this is not
the case. Then, $Q ^\prime$ is a $(t-1)$-dimensional affine space.
Applying
the inductive assumption, we know that there are $(2(m-1)(l+1))^{t-1}$
subrectangles whose union contains $Q^\prime \cap R^\prime $.
Each such subrectangle is a
facet of 2 subrectangles of $R$. Thus there are $2. (2(m-1)(l+1) )^{t-1}\;
m\; (l+1)$ subrectangles of $R$ whose union contains $Q\cap R$.
To get the required algorithm, note that in the case where some $Q^\prime
$ equals $Q$, we get one ``problem of size '' $t,m-1$ and in the other
case, we get $m(l+1)$ problems each of ``size'' $t-1,m-1$.
\proofend
{\bf (3.4) Lemma } : Suppose $K$ is a rational polyhedron
in ${\bf R}^n$ and $v\in {\bf
Z}^n\setminus \{ 0\} $ satisfies
$$\hbox{ either }\hbox { Width}_{v} (K)\leq 1$$
$$\hbox{ or } \forall u\not= 0 , u\in {\bf Z}^n, \hbox{ Width} _{v}(K)
\leq 2\hbox{Width} _u(K).$$
Suppose also that $y$ is in $K$ and $v\cdot y = \alpha $. For $\beta
\in {\bf R}$, denote by $H(\beta )$ the set $\{ x\in {\bf R}^n : v\cdot
x = \beta \}$. Let $s=2c_o n^{2}+1$ (where $c_o$ is the constant from the
Flatness theorem of section 1).
Then for all $\gamma \in (\alpha \ \ \alpha +1] $, we have
$$(K+{\bf Z}^n)\cap H(\gamma ) = \left[ K+\left( \bigcup_{k=-s}^s ({\bf Z}^n
\cap H(k)) \right) \right]\quad \cap \quad H(\gamma ).$$
{\bf Proof } : It is easy to see that we may assume that $y=0$ and
$\alpha =0$ since both sides in the above equation are unchanged by
translations of $K$ (provided of course, $H(\gamma )$ is also suitably
translated). Now suppose $x$ belongs to $H(\gamma )$ for some $\gamma
\in (0\ \ 1] $ and $x$ belongs to $K+{\bf Z}^n$. So $x-K$ intersects
${\bf Z}^n$, hence there exists a real number $t\in [0\ \ 1] $ such that
$x-tK$ intersects ${\bf Z}^n$, but the interior of $x-tK$ does not.
(This uses the fact that $K$ is closed and $0\in K$.) Then the width of
$tK$ along some nonzero integer vector must be at most $c_on^2$
by the Flatness Theorem from which it follows that the width of
$tK$ along $v$ must be at most $2c_on^2$. Then if $z$ is in
$(x-tK)\cap {\bf Z}^n$, we have $|v\cdot (z-x)|\leq 2c_on^2$, thus we
have $|v\cdot z|\leq s$ which implies that $x$ belongs to
$$\left[ K+\left( \bigcup_{k=-s}^s ({\bf Z}^n \cap H(k)) \right) \right] $$
proving the lemma.
\proofend
\section{The structure of $K_b+{\bf Z}^n$ as $b$ varies over a bounded set}
In this section, the main structural
theorem is stated and proved. The idea of the
theorem is to describe the set $K+{\bf Z}^n$ where $K$ is a polyhedron
. We assume $K$ is described by $m$ linear
inequalities $Ax\leq b$ where $A$ is an $m\times n$ matrix and $b$
an $m\times 1$ vector. If it happens that $K$ is contained in the
fundamental parallelopiped $F(B)$ corresponding to some basis $B$ of
$L={\bf Z}^n$, then clearly, $K+L = (K\cap F(B))+L$. This of course is
not true in general.
In spirit, the theorem below states that in general, it is enough to
look at the portion of $K+L$ (where $L={\bf Z}^n$), contained in some
parallelopipeds which are lattice translates of the fundamental
parallelopiped corresponding to some bases (note the plural) of $L$.
Further, we need to consider only a ``small'' number of lattice translates.
The number of bases of $L$ as well as the number of lattice translates is
bounded above by a function of $n$ alone. The proof of the theorem will be
by induction; in the body of the inductive proof, we will look at sets of
the form $K^\prime +L^\prime $ where $K^\prime $ is the intersection of
$K$ with some lattice hyperplane and $L^\prime $ the intersection of
$L$ with the subspace parallel to the hyperplane. We will need to derive a
``uniform'' description of these sets as the hyperplane is translated
parallel to itself. The sections then can be all described as $\{ y :
A^\prime y\leq b^\prime \}$ where the $b^\prime $ varies as an affine
function of $b$ and the position of the hyperplane. To facilitate such an
inductive proof, we will consider a more general setting than $K+L$, namely
$K_b+L$ where $K_b=\{x:Ax\leq b\}$ and now, we let $b$ vary over a
copolytope $P$ in ${\bf R}^m$. The theorem will say that for fixed $n$
and the affine dimension of $P$, we can partition
$P$ into a polynomial number of copolytopes such that in each part, there
is an uniform description of $K_b +L$.
{\bf (4.1) Theorem } Let $A$ be an $m\times n$ matrix of integers of size
$\phi$. Let $P$ be
a copolytope in ${\bf R}^m$ of affine dimension $j_o$ such that for all
$b\in P$, the set $K_b = \{ x : Ax\leq b\}$ is nonempty and bounded.
Let $M=(\max_{b\in P} (|b|+1) )$. There is an
algorithm which for any fixed $n,j_o$ runs in time polynomial in
$\phi , \log M$ and finds a partition of
$P\times {\bf R}^n$ into subsets $S_1,S_2,\ldots S_r$ such that
\begin{enumerate}
\item $r\leq (n\phi m \log M)^{j_o n^{dn}}$, where $d$ is a constant
independent of $n,m,M,\phi $.
\item Each $S_i$ is of the form $S^\prime _i /{\bf Z}^l$ where
$S^\prime _i$ is a copolyhedron in ${\bf R}^{m+n+l}$ and $l\leq (3c_on)^{3n}$.
\item Letting $S_i(b) = \{ x\in {\bf R}^n : (b,x)\in S_i\}$, we have
for all $i$ and all $b\in P$, $S_i(b)+{\bf Z}^n = S_i(b)$.
\end{enumerate}
The algorithm also finds corresponding to each $S_i$, a collection ${\cal
B}_i $ of at most $(3c_on)^{3n}$ bases of ${\bf Z}^n$. Corresponding to
each basis $B$ in each ${\cal B}_i$, it finds an affine transformation
$T(B) : {\bf R}^m\rightarrow {\bf R}^n$ and a set $Z(B)$ of at most
$n^{n}$ points of ${\bf Z}^n$ such that for all $i$ and all $b\in
P$, we have
$$(K_b +{\bf Z}^n)\cap S_i(b)=$$
$$\left[ \left\{ \bigcup_{B\in {\cal B}_i} \left( (K_b+Z(B) )\cap F(B;
T(B)b)\right) \right\} +{\bf Z}^n \right] \cap S_i(b).$$
/*END OF STATEMENT OF THE THEOREM*/
{\bf Remark } Reminder on some notation : $F(B;y)$ is the lattice
translate of the fundamental parallelopiped $F(B)$ corresponding to the
basis $B$, that contains the point $y$.
{\bf Proof }: The proof is by induction on $n$. First, I do the case
$n=1$. Here each row of $A$ can be assumed to be $\pm 1$ ; say the
first $k$ rows are +1 and the rest -1. We will have $S_1,S_2,\ldots
S_k\subseteq P\times {\bf R}^1$ defined by
$$S_i = \{ (b,x) : b\in P; b_i $ be any $(2s+1)$ - tuple of integers each in the range $ [0\ \
t+1] $. There will be one subset $S_J$ in the partition of $P\times {\bf R}^n$
for each such $J$. It is defined as the set of $(b,\beta ,x) : b\in P,\beta
\in {\bf R},x\in {\bf R}^{n-1}$ such that
$$\exists z\in {\bf Z} : \beta +z\in (\alpha \ \ \alpha
+1],\ \ (b,\beta +z-k,x)\in R_{i_k}\hbox{ for }k=-s,-s+1,\ldots
s\eqno (4.5)$$
Note here that $b$ ``comes from'' $P$ and $(\beta ,x)$ ``come from''
${\bf R}^n$.
It is obvious that the sets $S_J$ are of the form $S_J^\prime /{\bf
Z}^l$ where the $S_J^\prime $ is a copolyhedron and $l$ is not too high. (In
fact, $l\leq 1+(2s+1)(3c_o(n-1))^{3(n-1)}\leq (3c_on)^{3n}$.)
To show for any $b$, the intersection of $S_J(b)$ and $S_{J^\prime }(b)$
is empty for $J\not= J^\prime $, we proceed as follows : $J$ and
$J^\prime $ must differ in one of their ``coordinates'', say, in the $k$
th coordinate $J$ has $j$ and $J^\prime $ has $j^\prime $ with
$j\not= j^\prime $. For any $b\in P$, and $\beta \in (\alpha -s\ \ \alpha +s+1]
$, we have that $R_j(b,\beta )$ and
$R_{j^\prime }(b,\beta )$ do not intersect, from this it follows that
$S_J(b)$ and $S_{J^\prime }(b)$ do not intersect.
The other two properties required of the collection $\{ S_J\}$ - that
their union is $P\times {\bf R}^n$ for any fixed $b$ and they are invariant
under ${\bf Z}^n$ also follow easily.
The bound on the number of $S_J$ given by item 1 is argued by induction on
$n$ as follows : It is obvious for $n=1$. For other $n$, by lemma
(3.1), the partition of $P$ incurs us a factor of at most $(mn\log M \phi
)^{c(n+j_o)}$ for some constant $c$. Then we may apply the inductive
assumption for $t$, the number of pieces into which $P^\prime \times {\bf
R}^{n-1}$ is partitioned. The $\phi $ and $\log M$ passed on to this
problem are easily checked to be at most $n^{c^\prime }$ times the original
$\phi $ and $\log M$ and of course the $n+j_o$ passed on is the same
as before, since $n$ is decreased by 1 and $j_o$ increased by 1.
Further, the number of $J$ is at most
$(t+2)^{2s+1}$. So we get, by induction,
the number of $J$ is at most $(mn\log M \phi )^{j_o n^{dn} }$ for a
suitable choice of $d$.
We must now associate a certain set of bases of ${\bf Z}^n$ with each
$S_J$. I do this after giving an idea of what the set must be. For each
$J$, say $J=\bigl< i_{-s},i_{-s+1},\ldots i_0,\ldots i_s\bigr> $, and
for $\gamma \in (\alpha \ \ \alpha +1] $, we get using (4.2),
$$\left( (K_b + L )\cap H(\gamma )\right) \cap S_J (b) =$$
$$\gamma \times \left[ \bigcup_{k=-s}^s \left( \hat Q(b,\gamma -k )+{\bf
Z}^{n-1}\right) \right] \quad \cap \quad S_J(b)\eqno (4.6) $$
$$\subseteq \bigcup_{k=-s}^s \gamma \times
\left\{ \left( \hat Q(b,\gamma -k)+{\bf Z}^{n -1}
\right) \cap R_{i_k}(b,\gamma -k) \right\} $$
where the last containment comes from the fact that for $\gamma $ in the
range $ (\alpha \ \ \alpha +1] $, if $ (b,\gamma ,\hat x)$ belongs to
$S_J$, then $ (b,\gamma -k ,\hat x) $ belongs to $R_{i_k}$.
Now, by (4.4), we get,
$$\left( \hat Q(b,\gamma -k )+{\bf Z}^{n-1}\right) \quad\cap\quad R_{i_k}
(b,\gamma -k) = \eqno (4.7) $$
$$\left\{ {\bf Z}^{n-1} + \left\{ \bigcup _{B\in {\cal B}_{i_k}}\left[ \left(
\hat Q(b,\gamma -k ) +Z(B)\right) \cap F(B;T(B){b\choose \gamma -k})\right]
\right\} \right\} \quad \cap\quad R_{i_k}(b,\gamma -k ).$$
We can write $T(B){b\choose \beta }$ as $T_0^\prime b + w^\prime \beta $
where $T_0^\prime $ is an affine transformation and $w^\prime $ is an
$(n-1)\times 1$ vector. Let $T_0$ be the $n\times m$ matrix with 0 's
in the first row and $T_0^\prime $ in the other rows ; let $w$ be the
$n$ vector ${0\choose w^\prime }$. Let $z\in {\bf Z}^{n-1}$ be such
that
$$w^\prime \in F(B)+z.$$
We ``complete '' $B$ to a basis $B^\prime $ of $L$ as follows : if
$B=\{ b_1,b_2,\ldots b_{n-1}\}$, then we let $B^\prime =\{
(0,b_1),(0,b_2),\ldots (0,b_{n-1}),(1,z)\}$.
To define $T(B^\prime )$, we proceed as follows : let $B\in {\cal B}_{i_k}$.
Let $y=T(B){b\choose \gamma -k} = T_0^\prime b +w^\prime (\gamma -k)$. Let
$y^\prime = (0,y)$ and let $y_o = (\gamma -k) e_1 +y^\prime $. Then as
$\gamma $ varies over $ ( \alpha\ \ \alpha +1] $, $\quad y_o$ varies
on the straight line segment $p$ from $T_0 b + (\alpha
-k)(e_1+w) = z_o$, say, to $z_o +e_1 +w$. We can express $z_o$ as
$Ub$ where $U$ is an affine transformation. Then it is easy to see that
$ p\subseteq F(B^\prime ;Ub) + C$, for a set $C$ of at most $n$ corners
of $F(B^\prime )$. So we get, for $\gamma $ in $ (\alpha \ \ \alpha +1]
$,
$$\left[ 0\times F(B;T(B){b\choose \gamma -k })\right] + (\gamma -k)e_1
\subseteq C+F(B^\prime ;Ub)\eqno (4.8)$$
We will let $U=T(B^\prime )$ be the affine transformation corresponding to
$B^\prime $. We let $Z(B^\prime ) = (0\times Z(B))-C$.
So, we have $|Z(B^\prime )|\leq n
|Z(B)|\leq n^{n}$ using the inductive assumption. The collection ${\cal
B}_J$ of bases of $L$ corresponding to $S_J$ is defined as the set of
$B^\prime $ defined as above - one for each $B$ in each $R_{i_k}$ for
$k=-s,-s+1,\ldots 0,\ldots s$.
Now, for $\gamma $ belonging to $ (\alpha \ \ \alpha +1] $, we have
$$(\gamma -k )\times \left[ \left( \hat Q(b,\gamma -k) +Z(B)\right) \cap
F\left( B;T(B){b\choose \gamma -k}\right) \right] $$
$$\subseteq \left[ \left( K_b+Z(B^\prime )\right) \cap F(B^\prime
;Ub)\right] +C\eqno (4.9)$$
By substituting this into (4.7), we get
$$(\gamma - k)\times
\left( \hat Q(b,\gamma -k )+{\bf Z}^{n-1}\right) \quad\cap\quad (\gamma -k)
\times R_{i_k} (b,\gamma -k) $$
$$\subseteq \bigcup_{B\in {\cal B}_{i_k}}
\left[ \left( K_b+Z(B^\prime )\right) \cap F(B^\prime
;Ub)\right] +{\bf Z}^n .$$
Substituting this into (4.6), we get
$$\left( (K_b + L )\cap H(\gamma )\right) \cap S_J (b) \subseteq $$
$$\bigcup_{k=-s}^s ke_1 + \bigcup_{B\in {\cal B}_{i_k}}
\left[ \left( K_b+Z(B^\prime )\right) \cap F(B^\prime
;Ub)\right] +{\bf Z}^n \eqno (4.10).$$
Since $ke_1+{\bf Z}^n = {\bf Z}^n$ and the right hand side of (4.10) is
invariant under adding ${\bf Z}^n$, we have
$$(K_b + {\bf Z}^n)\quad \cap \quad S_J(b) = $$
$$\bigcup_{B^\prime \in {\cal B}_J}
\left[ \left( K_b+Z(B^\prime )\right) \cap F(B^\prime
;Ub)\right] +{\bf Z}^n\quad \cap \quad S_J(b).$$
This completes the proof of the theorem.
\proofend
\section{Algorithm to find the covering radius}
{\bf (5.1) Proposition } : There is a polynomial $p(\cdot )$ such that for any
rational polytope $Q$ of nonzero volume
and rational lattice $L$, with total size $N$,
$\mu =\mu (Q,L)$ is a rational number of size at most $p(N)$.
{\bf Proof} : We have $\mu \leq c_o n^2 /\lambda_1^*$ [\ref{kl}]
. But $\lambda_1^*$ is
equal to the dot product of an integer vector with the difference of two
vertices of $Q$, so we have $\lambda_1^*\geq 1/M$ where $M$ is an integer
with number of bits bounded above by some polynomial in $N$. Thus $\mu\leq
c_o n^2 M$. The diameter of $Q$ (the maximum Euclidean distance between two
points in $Q$) is bounded above by an integer
with number of bits bounded above by some polynomial in $N$. From these two
facts, we can derive an integer $D$ with polynomial number of bits such that
the Euclidean distance between any two points in $\mu Q$ is at most $D$.
Since $\mu $ is invariant under translations, we can translate $Q$ so that
$0$ belongs to the interior of $Q$. Let $Q =\{ x : a^{(i)}x\leq b_i;
i=1,2,\ldots m\}$ where $b_i$ are all now strictly positive.
In what follows, we say that a point $x$ in space is
``covered'' by a lattice point $z$ if $x\in z + \mu Q$.
Let $R$ be the fundamental parallelopiped of $L$ corresponding to some basis
of $L$. Let $T$ be the set of all points of $L$ at distance at most $D$ from
$R$. Then, each point of $R$ is covered by a point of $T$.
There is a ``last'' point $x_0$ in $R$ that is covered and thus for
each $l\in T$, we have that $x_0$ does not lie in the interior of $l+\mu Q$,
i.e., there exists an integer $i(l), 1\leq i(l)\leq m$, such that
$a^{(i(l))}(x_0-l)
\geq \mu b_{i(l)}$. Thus, there is a function $i:T\rightarrow
{1,2,\ldots m}$ such that we have that $\mu $ is the maximum value of the
following linear program : (using the fact that $b_j>0\forall j$)
$$\max t : x\in R\quad ; \quad {a^{i(l)}\over b_{i(l)}} (x-l)\geq t
\forall l\in T $$
The maximum value must be attained at a basic feasible solution of this
linear program whose coefficients are rationals whose sizes are polynomially
bounded in $N$ and thus the proposition follows.
\proofend
Given a rational polyhedron $K_b=\{ x : Ax\leq b\}$ in ${\bf R}^n$, we
wish to compute its covering radius. Since this is a fraction with numerator
and denominator polynomially bounded in size, we can do this by binary
search provided for any rational $t$, we can check whether $tK_b +{\bf
Z}^n$ equals ${\bf R}^n$. Without loss of generality, we may assume that
$t=1$. We appeal to the theorem of the last section
to find the $S_i,{\cal B}_i$ etc. where
$P$ is assumed to be the singleton $\{b\}$. Then we check in turn for
each $S_i$ whether there exists an $x\in S_i(b)$ so that $x\notin K+{\bf
Z}^n$. We will formulate the last as several mixed integer programs each with
polynomially many constraints and a fixed number of integer variables (for
fixed $n$). For each $B$ in ${\cal B}_i$, and for each $z\in Z(B)$, we
wish to assert that the unique lattice translate $x(B)$ of $x$ that
falls in the parallelopiped $F(B;T(B)b)$ is not in $K_b+z$. To express
this by linear constraints, we consider all mappings $f$ of the following
sort : $f$ takes two arguments - a $B$ in ${\cal B}_i$ and a $z$ in
$Z(B)$. The range of $f$ is $\{ 1,2,\ldots m\}$. We will consider each
possible such mapping $f$ and for each solve a mixed integer program that
asserts that there exists an $x$ in $S_i(b)$ such that for each $B\in
{\cal B}_i$ and for each $z\in Z(B)$, there is a $y(B)$ in ${\bf
Z}^n$ such that $x+y(B)$ belongs to $F(B;T(B)b)$ and $x+y(B)-z$
violates the $f(B,z)$ th constraint among the $m$ constraints $Ax\leq
b$. If any of the MIP's is feasible , then we know that $K_b+{\bf Z}^n
\not= {\bf
R}^n$, otherwise $K_b+{\bf Z}^n={\bf R}^n$. We use the algorithm from
[\ref{kannan}] to solve each MIP in polynomial time.
Here, $j_o=1$ and $M=|b|$. So the number of $S_i$ 's is at most $
(n\phi m \log |b|)^{n^{dn}}$ by 1. of Theorem (4.1). The number of $f$
's is at most $m^{(cn)^{4n}}$ again from Theorem (4.1). The number of integer
variables in each MIP is at most $(O(n))^{4n}$. So the total running time of
the algorithm for checking if $K+{\bf Z}^n={\bf R}^n$ is
$$ (n\phi m |b| )^{n^{en}}$$
for some constant $e$. A similar bound with a different constant obviously
applies to the algorithm for finding the covering radius and solving the
Frobenius problem.
This concludes the description of the algorithm to find the covering radius
of a polytope in a fixed number of dimensions.
\section{The case of unbounded right hand sides}
This section proves Theorem (6.1) which
extends Theorem (4.1) to the case when $P$ is a copolyhedron. In this
case, the parameter $\phi $, the size of the matrix $A$ will essentially
substitute $\log (\max_{b\in P})|b|$. Here is a precise statement of the
theorem.
{\bf (6.1) Theorem } Let $A$ be an $m\times n$ matrix of integers of size
$\phi $. Let $P$ be
a copolyhedron in ${\bf R}^m$ of affine dimension $j_o$ such that for all
$b\in P$, the set $K_b = \{ x : Ax\leq b\}$ is nonempty and bounded.
There is an
algorithm which for any fixed $n,j_o$ runs in time polynomial in the size
of the input and finds subsets a partition of
$P\times {\bf R}^n$ into subsets $R_1,R_2,\ldots R_r$ such that
\begin{enumerate}
\item $r\leq (n\phi m)^{j_o n^{en} }$ where $e$ is a constant.
\item Each $R_i$ is of the form $R^\prime _i /{\bf Z}^l$ where
$R^\prime _i$ is a copolyhedron in ${\bf R}^{m+n+l}$ and $l\leq n^{O(n)}$.
\item Letting $R_i(b) = \{ x\in {\bf R}^n : (b,x)\in R_i\}$, we have
for all $i$ and all $b\in P$, $R_i(b)+{\bf Z}^n = R_i(b)$.
\end{enumerate}
The algorithm also finds corresponding to each $R_i$, a collection ${\cal
B}_i $ of at most $n^{O(n)}$ bases of ${\bf Z}^n$. Corresponding to
each basis $B$ in each ${\cal B}_i$, it finds an affine transformation
$T(B) : {\bf R}^m\rightarrow {\bf R}^n$ and a set $Z(B)$ of at most
$n^n$ points of ${\bf Z}^n$ such that for all $i$ and all $b\in
P$, we have
$$(K_b +{\bf Z}^n)\cap R_i(b)=$$
$$\left[ \left\{ \bigcup_{B\in {\cal B}_i} \left( (K_b+Z(B) )\cap F(B;
T(B)b)\right) \right\} +{\bf Z}^n \right] \cap R_i(b).$$
/*END OF STATEMENT OF THE THEOREM*/
I will prove the theorem by using Theorem (4.1). To do so, I will show using
lemma (6.2) below
that for any $b\in P$, the description of $K_b+{\bf Z}^n$ can be easily
obtained from the description of $K_{c}+{\bf Z}^n$ where $c$
has all its components in the range $[0\ \ n2^{3\phi }]$. Further, I will
show that $c$ is a ``piecewise affine'' function of $b$ ; i.e., that
$P$ can be partitioned into polynomially many copolyhedra such that for each
copolyhedron in the partition, there is an affine function that maps $b$ to
$c$. This proof will use lemma (6.3). Throughout this section, I let $M$
denote $n2^{3\phi }$.
{\bf Lemma (6.2)} : Let $A$ be an $m\times n$ matrix of integers of size
$\phi$. Suppose $b$ is any point in ${\bf R}^m$ with $b\geq 0$. (So, 0 is in
$K_b$.) Define $b^\prime = (b_1^\prime , b_2^\prime , \ldots b_m^\prime )$
by : $b_i ^\prime = \min \{ b_i,n2^{3\phi }\}.$
Then,
$$K_b +{\bf Z}^n = K_{b^\prime }+{\bf Z}^n.$$
{\bf Proof } : The proof is based on the following fact due to Cook,
Gerards, Schrijver and Tardos [\ref{cgst}] : Let $\Delta $ be the
maximum absolute
value of any subdeterminant of $A$. If a point $p$ belongs to $K_b$, and
if $K_b$ contains some point in ${\bf Z}^n$, then there is a point $q\in
{\bf Z}^n\cap K_b$ with $|p_i-q_i|\leq n\Delta $ for $i=1,2,\ldots n$. (This
fact is true for any ``right hand side'' $b$.)
It is clear that
$$K_b +{\bf Z}^n \supseteq K_{b^\prime }+{\bf Z}^n.$$
Now, I will prove the converse.
Suppose $x$ is any point in $K_b +{\bf Z}^n$.
Then
$K_b-x$ contains an integer point; it also contains $-x$. So, by the above
fact, there is an integer point $z$ in $K_b-x$ with $|z_i+x_i|\leq
n\Delta $ for all $i$. By Theorem
3.2 of [\ref{schrijver}], $\Delta$ is at most $2^{2\phi }$.
It is now easy to see that $z+x$ belongs to $K_{b^\prime
}$ finishing the proof of the lemma.
\proofend
Suppose $v\cdot x = v_o$ is a hyperplane in Euclidean space. It partitions
space into two ``regions'' - $\{ x : v\cdot x \leq v_o\}$ and
$\{ x : v\cdot x > v_o\}$. Similarly,
a set of $l$ hyperplanes in ${\bf R}^m$ partition
${\bf R}^m$ into (at most) $2^l$ ``regions'' each region being
determined by which side of each hyperplane it is on. There is another
well-known upper bound on the number of regions - it is
$$\sum_{k=0}^m{l\choose k}.$$
For $l\leq m$, the sum is $2^l$ and the
result is obvious. For $l>m$, we proceed by induction. The number of
regions formed by the first $l-1$ of the hyperplanes is at most
$\sum_{k=0}^m{l-1\choose k}$ by induction. Now imagine adding the $l$ th
hyperplane. I claim that the number of
existing regions that the $l$ th hyperplane intersects is at most
$\sum_{k=0}^{m-1}{l-1\choose k}$ - to see this, note that the intersections
of the existing regions
with the $l$ th hyperplane form a partition of the $l$ th hyperplane (an $m-1$
dimensional affine space). Each region intersected by
the $l$ th hyperplane is divided into two by it. So we get the total number
of regions formed by all the $l$ hyperplanes is at most
$$\sum_{k=0}^m{l-1\choose k}+\sum_{k=0}^{m-1}{l-1\choose k}
=\sum_{k=1}^m\left( {l-1\choose k-1}+{l-1\choose k}\right) +1$$
which proves the claim. The lemma below follows immediately.
{\bf Lemma (6.3)} Suppose $V$ is a $j$ dimensional affine subspace of ${\bf
R}^m$. For any set of $l$ hyperplanes in ${\bf R}^m$, the number of
regions in the partition of ${\bf R}^m$ by the $l$ hyperplanes
that $V$ intersects is at most
$$\sum_{k=0}^j {l\choose k}\leq l^j.$$
Further, if $j$ is fixed, then given the hyperplanes and $V$, we can
find the regions intersected by $V$ in polynomial time.
{\bf Proof } : The first part is already proved. For the algorithm, we go
again to the first part of the proof and see that a problem with parameters
$l,j$ is reduced to two problems one with parameters $l-1,j$ and the
other $l-1,j-1$. If the running time of the algorithm is $T(l,j)$, we
get the recurrence $T(l,j)\leq T(l-1,j)+T(l-1,j-1)+O(1)$ which solves to
$T(l,j)$ is in $O(l^j)$.
\proofend
Suppose as in the Theorem (6.1), $P$ is a copolyhedron of affine dimension
$j_o$ in ${\bf R}^m$. Consider each of the (at most $m^n$) nonsingular
$n\times n$ submatrices $B$ of $A$. For each of these we can define an
$n\times m$ matrix $T$ by augmenting $B^{-1}$ with 0 columns so that
the possible corners of any $K_b$ are of the form $Tb$ for such $T$.
For each such $T$, and each $i$, $1\leq i\leq m$, consider the
hyperplane $\{ b : a^{(i)}Tb = b_i\} $ in ${\bf R}^m$. (Reminder :
$a^{(i)}$ is the $i$ th row of $A$.) There are at most
$m^{n+1}$ such hyperplanes and so by lemma (6.3) , we have that $P$
intersects at most $m^{(n+1)j_o}$ of the regions that these hyperplanes
partition ${\bf R}^m$ into. It is not difficult to see that for fixed
$n,j_o$, we can find these regions in polynomial time. For
each such region $U$,
there is a $T_U$ such that $T_Ub$ is in $K_b$ for all
$b\in U$ ; in other words $b-AT_Ub$ is a nonnegative vector for all
$b\in U$. Consider the $m$ hyperplanes $(b-AT_Ub)_i=M$ for
$i=1,2,\ldots m$. By applying lemma (6.3) again, we see that $U$ intersects
at most $m^{j_o}$ of the regions that these $m$ hyperplanes partition
space into. We partition $U$ into these $m^{j_o}$ or less parts. Thus we
have found so far in polynomial time, a partition of $P$ into copolyhedra
$P_1,P_2,\ldots P_t$ with
$$t\leq m^{(n+2)j_o}$$
and associated with copolyhedron $P_k$ in the
above partition, we have an affine transformation
$T(P_k)$ and an $I(P_k)\subseteq \{ 1,2,\ldots
m\}$ such that for all $b\in P_k$,
$$0\leq (b-AT(P_k)b)_i\leq M\forall
i\in I(P_k)\qquad \hbox{ and } $$
$$(b-AT(P_k)b)_i>M\forall i\notin I(P_k).$$
For each $b\in P_k$, let $b^\prime = b-AT(P_k)b$, let $b^{\prime\prime
} $ be defined by $b^{\prime\prime }_i = b^\prime _i$ for $i\in I(P_k)$
and $b^{\prime\prime }_i = M$ for other $i$. Let $b^{\prime \prime
\prime } = b^{\prime \prime } + AT(P_k)b$. Note that there is a linear
transformation that maps each $b$ to $b^{\prime \prime \prime }$.
Now by lemma
(6.2), we see that for all $b\in P_k$, we have
$$K_{b^\prime } +{\bf Z}^n = K_{b^{\prime \prime }} +{\bf Z}^n.$$
Note that $b^{\prime \prime }$ belongs to the copolytope
$$P^\prime =\{ b : b\in P; |b|\leq M\}$$
We apply the main theorem (4.1) with this copolytope. I will show that an
easy argument then gives us Theorem (6.1). To this end, let $S_i$ be one
of the sets in the partition of $P^\prime \times {\bf R}^n$ that Theorem
(4.1) yields. Corresponding to each such $S_i$ we define one subset
$R_{ik}$ of $P_k\times {\bf R}^n$ for each $k$. Namely,
$$R_{ik} =\{ (b,x) : b\in P_k\ ; \ (b^{\prime\prime },x-T(P_k)b )\in
S_i\}$$
It is easy to see that the $R_{ik}$ have all properties 1,2, and 3 in the
statement of Theorem (6.1) with a suitable choice of constant $e$.
By Theorem (4.1), we have for all $b$ in $P_k$,
$$(K_{b^\prime }+{\bf Z}^n )\cap S_i(b^{\prime\prime })\ \ = \ \
(K_{b^{\prime\prime }} +{\bf Z}^n)\cap S_i(b^{\prime\prime })=$$
$$\left[ \left\{ \bigcup_{B\in {\cal B}_i} \left( (K_{b^{\prime\prime }}
+Z(B) )\cap F(B;
T(B)b^{\prime\prime })\right) \right\} +{\bf Z}^n \right] \cap S_i(b^{\prime
\prime }).$$
Translating the sets on both sides of the above equation by $T(P_k)b$, we
obtain
$$(K_{b} +{\bf Z}^n)\cap R_{ik}(b)=$$
$$\left[ \left\{ \bigcup_{B\in {\cal B}_i} \left( (K_{b^{\prime\prime\prime }}
+Z(B) )\cap F(B;
T(B)b^{\prime\prime }+T(P_k)b)\right) \right\}
+{\bf Z}^n \right] \cap R_{ik}(b)
.$$
Since $K_{b^{\prime \prime \prime }}\subseteq K_b$, we may replace
$K_{b^{\prime \prime \prime }}$ on the right hand side (rhs) of the above
equation by $K_b$. (Note that then we would have lhs contained in the rhs.
The converse is obvious.) Further, there is an affine transformation, say,
$Q$ that takes $b$ to $b^{\prime\prime }$. So, we may now define the
affine transformation corresponding to the basis $B$ to be
$$T(B)Q + T(P_k)$$ to complete the proof of Theorem (6.1).
\proofend
\section{Test sets for Integer Programs, $\forall\exists $ sentences and
maximal lattice-free $K_b$}
For linear programming problems, we know that if there is a feasible
solution, there is a basic feasible one. This can be expressed as follows :
Suppose as before $A$ is an $m\times n$ matrix of rank $n$. Consider
as before, each of the (at most $m^n$) nonsingular
$n\times n$ submatrices $B$ of $A$. For each of these we can define an
$n\times m$ matrix $T$ by augmenting $B^{-1}$ with 0 columns so that
the possible corners of any $K_b$ are of the form $Tb$ for such $T$. Then we
can say that for all possible right hand sides $b$, if $K_b$ is
nonempty, then one of the $Tb$ belongs to $K_b$. This section proves a
similar theorem for Integer Programs.
{\bf (7.1) Theorem} : Let $A$ be an $m\times n$ matrix of integers of size
$\phi $ with the property that $\{ x : Ax\leq 0\} = \{ 0\}$ (or
equivalently, $K_b$ is bounded for all $b$). Let $P$ be
a copolyhedron in ${\bf R}^m$ of affine dimension $j_o$. For $n,j_o$
fixed, there is a polynomial time algorithm that finds a partition of $P$
into $P_1,P_2,\ldots P_r$ with $r\leq (mn\phi )^{j_o n^{dn} }$
%the next two lines were added after bonnfrob.tex was sent to combinatorica
and each $P_i$ of the form $P_i^\prime /{\bf Z}^l$ where $P_i^\prime $ is
a coplyhedron and $l$ is a constant
and for each $P_i$, finds a set ${\cal T}_i$ of
pairs $(T,T^\prime )$ affine transformations where $T:{\bf
R}^m\rightarrow {\bf R}^n$ and $T^\prime : {\bf Z}^n\rightarrow {\bf
Z}^n$ such that for all $i$ and for all $b\in P_i$,
$$K_b\cap {\bf Z}^n\not= \emptyset \quad \Longleftrightarrow\quad
\exists (T,T^\prime )\in {\cal T}_i\ : \ T^\prime \lfloor
Tb\rfloor \in K_b.$$
Further, for each $i$, the set ${\cal T}_i$ contains at most
$(O(n))^{4n}$ pairs $(T,T^\prime )$.
{\bf Proof} : First, we may replace $P$ by $\{ b : b\in P, \exists x :
Ax\leq b \} $. So assume without loss of generality that for all $b$ in
$P$, we have $K_b\not= \emptyset $ and bounded.
Let $L={\bf Z}^n$. Note that $K_b\cap L$ is empty iff $K_b +L$ does
not contain 0. We apply Theorem (6.1) to get the partition of $P\times {\bf
R}^n $ into $R_1,R_2,\ldots R_r$.
Let $P_i =\{ b : 0\in R_i(b)\}$. It is easy to see that
$P_i$ is of the form $P^\prime _i/{\bf Z}^l$ where $P^\prime _i$ is a
copolyhedron and $l$ is a constant (for fixed $n$).
%the rest of the paragraph was deleted after bonnfrob.tex was sent
%In fact a stronger
%statement is true. The $P_i$ are actually copolyhedra. To see this, we
%have to go into the proof of theorem (4.1). The partition of $P\times {\bf
%R}^n$ into $S_1,S_2,\ldots $ in that theorem (where $S_i = S_i^\prime
%/{\bf Z}^l$ ) has the following property : for each $(b,x)\in S_i$ (with
%$b\in P, x\in {\bf Z}^n$), there is a unique $y\in {\bf Z}^l$ so that
%$(b,x,y)$ belongs to $S_i^\prime $. In fact, each component of $y$ is
%of the form $F^\prime \lfloor Fx\rfloor $ where $F^\prime , F$ are
%affine transformations. This is easily proved by induction on $n$ noting
%that in (4.5), the $z$ is in fact forced to be $ \lfloor \alpha +1-\beta
%\rfloor $.
Also, from
Theorem (6.1), we have for $b$ in $P_i$,
$$(K_b +{\bf Z}^n)\cap {\bf Z}^n=$$
$$\left[ \left\{ \bigcup_{B\in {\cal B}_i}\left(
K_b+Z(B)\right) \cap
F(B;T(B)b)\right\} +{\bf Z}^n\right] \cap {\bf Z}^n.$$
The left hand side in the above equation is empty if and only if for each
$B$, the unique lattice point $z_B(b)$ in $F(B;T(B)b)$ has the
property that $z_B(b)-Z(B)$ does not intersect $K_b$. It is quite
straightforward to see that for each $p\in Z(B)$, we can find a pair of
affine transformations $(T,T^\prime )$ as required in the statement of
Theorem (7.1), such that $ z_B(b)-p=T^\prime (\lfloor Tb\rfloor )$. This
completes the proof of the theorem.
\proofend
I now give a decision procedure for deciding the truth or falsity of certain
sentences in Presberger arithmetic.
{\bf (7.2) Theorem} : There is an algorithm which takes as input an
$m\times n$ matrix $A$ and an $m\times p$ matrix $B$ and an
$m\times 1$ matrix $b$ all made up of integers and a copolyhedron $Q$ in
${\bf R}^{p+l}$ by a set of defining inequalities, decides whether the
following sentence is true.
$$\forall y\in Q/{\bf Z}^l\quad \exists x\in {\bf Z}^n:\qquad Ax+By\leq
b.$$
Further for fixed $n,p,l$, the algorithm runs in time bounded by a
polynomial in the length of the input.
{\bf Remark } : Note ${\bf R}^p$ and ${\bf Z}^p$ are both special cases
of sets of the form $Q/{\bf Z}^l$. The first is obvious. For the second,
we can make $l=p$ and $Q=\{ (y,y) : y\in {\bf R}^p\}$. Also, it is easy to
see that the Frobenius problem : given $a_1,a_2,\ldots a_n, a_{n+1}$, is
$Frob ( a_1,a_2,\ldots a_n)\leq a_{n+1} $ ? is a special case of such a
sentence.
{\bf Proof } : Let $Q/{\bf R}^l=Q^\prime $. The set $Q^\prime $ includes
the set $Q/{\bf Z}^l $ - the set of all the $y$ of interest.
For $y$ in $Q^\prime $, the quantity $b-By$
is in an affine subspace $P$ of ${\bf R}^m$ of dimension $p$ or less. So
by Theorem (7.1), we can find in polynomial time (since $n,p$ are fixed) a
partition of $P$ into $P_1,P_2,\ldots P_r$ with
$$ r\leq (n\phi m)^{pn ^{dn}}$$
and for each $P_i$, a collection ${\cal T}_i$ of pairs of affine
transformations $(T,T^\prime )$ satisfying the conditions of that theorem.
The sentence
$$\forall y\in Q/{\bf Z}^l\quad \exists x\in {\bf Z}^n:\qquad Ax+By\leq
b$$
is false iff there is some $P_i$ with the property that
$$\exists y\in P_i\cap Q/{\bf Z}^l : \forall (T,T^\prime )\in {\cal T}_i
: T^\prime \lfloor T(b-By)\rfloor \notin
\{ x : Ax\leq b-By\} .$$
This will be true iff one of the Mixed Integer programs set up
below is feasible : Consider each of the $m^{(cn)^{4n}}$
maps $f$ from pairs $(T,T^\prime )$ in
${\cal T}_i$ to $\{ 1,2,\ldots m\}$. For each such map, we will have one MIP
that asserts that there exists a $y\in P_i\cap Q/{\bf Z}^l$ with
$(T^\prime \lfloor T(b-By)\rfloor )$ violating the $f(T,T^\prime )$ th
constraint for each $(T,T^\prime )$. Note that the floor of a real variable
$w$ can be expressed using a new integer variable which is constrained to
be in the interval $ (w-1 \ \ w] $. Also the condition that $y\in
Q/{\bf Z}^l$ can be expressed by introducing $l$ new integer variables.
%next two lines added after bonnfrob.tex
Each $P_i$ is of the form $P_i^\prime /{\bf Z}^k$ and we deal with this
analogously.
For convenience, order the pairs $(T,
T^\prime )$ and refer to them as $(T,T^\prime )_i$.
The MIP will read as follows :
$$\exists y \in {\bf R}^p , z\in {\bf Z}^l , z_1,z_2,\ldots \in {\bf Z}^n
: (y,z)\in Q ; y\in P_i $$
$$T_i(b-By)-1 b_{f(T,T^\prime )_i}.$$
Clearly, we may solve each MIP for
each $P_i$ in turn and if one of them is feasible, return false for the
sentence otherwise, true.
It is not difficult to see that the required bound on the running time.
\proofend
The rest of the section discusses properties of the set of right hand sides
$b$ for which $K_b\cap {\bf Z}^n$ is empty.
Let
$$LF(A,P)=\{ b : b\in P, K_b\cap {\bf Z}^n=\emptyset \}.$$
Let $P_1,P_2,\ldots $ be the partition of $P$ that Theorem (7.1) yields.
Let $$LF(A,P) = \cup _i LF(A,P_i).$$
$LF(A,P_i)$ can be described by linear constraints with the introduction
of some extra integer variables as the following shows
: we consider all mappings $f$ of the
following sort : $f$ takes as argument a pair $(T,T^\prime )$ in ${\cal
T}_i$ and its range is $\{1,2,\ldots m\}$. Let $V(i,f)$ be the set of
$b$ satisfying
\begin{itemize}
\item $b$ belongs to $P_i$.
\item $T^\prime (\lfloor Tb\rfloor )$ violates constraint number
$f(T,T^\prime )$ of the $m$ constraints $Ax\leq b$.
\end{itemize}
To express the floor, we can introduce a new integer variable and linear
constraint. Thus, we see that $LF(A,P_i)$ is the union of a polynomial
number of sets each of the form copolyhedron$/{\bf Z}^l$ where $l$ is a
constant for fixed $n,j_o$.
We use this discussion in a slightly different context below.
Suppose as above $A$ is a fixed $m\times n$ matrix of integers with $\{ x:
Ax\leq 0\}=\{ 0\}$.
For any $b\in {\bf R}^m$, as before, we let $K_b=\{ x : x\in {\bf
R}^n;Ax\leq b\}$. We say that a $K_b$ is maximal-lattice-point free if it
has no points of ${\bf Z}^n$ in its interior and any convex set that
strictly contains $K_b$ does. We can replace the last
condition by the requirement that every facet of $K_b$ have a lattice
point interior to it [\ref{lovasz}]. By a theorem of Bell [\ref{bell}] and
Scarf [\ref{scarf}], a maximal lattice free $K_b$ has at most $2^n$
facets. We choose all subsets of the $m$ inequalities $Ax\leq b$ of
cardinality at most $2^n$,
and for each subset, we will study the positions of the facets that result
in maximal lattice free sets; we only incur an extra factor of $m^{2^n}$ by
this which is polynomially bounded for fixed $n$. Then arguing as for the
case of lattice-point-free sets and adding the condition that each facet
have a lattice point, we get the following theorem.
{\bf (7.3) Theorem } : Suppose $n$ is fixed. Then for any $m\times n$
integral matrix $A$, there exists a collection of sets $\{ U_1,U_2,\ldots
U_t\}$, where $t$ is bounded by a polynomial in the size of $A$, and each
$U_i$ is of the form $U^\prime _i/{\bf Z}^l$, where $l$ is a constant, and
$U_i^\prime $ is a copolyhedron
such that the collection of maximal lattice point free sets $K_b$ is
precisely the collection$\{ K_b : b\in U_1\cup U_2\cup \ldots U_t\} $.
{\bf Remark } : Note that a similar
theorem is not true for just lattice-point-free $b$ - there we would have
also needed to assume that $m$ was fixed or else at least the affine
dimension of $P$ over which $b$ varied was fixed. The theorem of Bell and
Scarf helps us dispense with this assumption for {\it maximal} lattice point
free sets.
\section{Remarks}
{\bf Remark 1} : The time bounds for the decision procedure for the
sentences of Theorem (7.2) have a double exponential dependence on $n$,
the number of variables in the inner quantifier. While this may seem
prohibitive, it will be shown in a forthcoming paper that the following
problem is NP-complete - given a sentence of the form in Theorem (7.2) in
which $n+p$ is $O(\log (\hbox { length of the sentence } ))$, decide
whether it is true or false. (In other words, even if the number of
variables is restricted to be very small, the problem still remains NP-hard.)
A substantial improvement in the double exponential dependence would thus
result in faster simulations of general nondeterministic Turing machines by
deterministic ones.
{\bf Remark 2} : The question arises : what can be said about the Frobenius
problem when $n$ is not fixed. In a forthcoming paper, I will show
that for variable $n$, in deterministic polynomial time, we can find an
approximation to the Frobenius number to within a factor of $2^n$. With a
nondeterministic algorithm, we can come within a factor of $O(n^3)$ in
polynomial time.
{\bf Remark 3} : Related to the Frobenius problem is the following : Given
$a_1,a_2,\ldots a_n$, with GCD$(a_1,a_2,\ldots a_n)$ equal to 1,
find the total number of natural numbers that cannot be expressed as a
nonnegative integer combination of $a_1,a_2,\ldots a_n$. It is easy to see
that this number is within a factor of 2 of $F=Frob(a_1,a_2,\ldots a_n)$ :
just note that for any integer $x$, $1\leq x\leq F$, either $x$ or
$F-x$ cannot be expressed as a nonnegative integer combination of
$a_1,a_2,\ldots a_n$. No polynomial time algorithm is known to find this
number exactly in fixed dimension.
{\bf Remark 4} : Lenstra's result quoted earlier gives a polynomial time
algorithm to decide the truth or falsity of a $\Sigma _1$ sentence
over Presberger arithmetic, (using terminology from Logic)
i.e., a sentence of the form :
$$\exists x_1,x_2,\ldots x_n \in {\bf Z} : x\in P_1\cup P_2\cup P_3\ldots
P_l$$
where $P_i$ are polyhedra. Actually, $\Sigma _1$ sentences may have a
conjunctions, disjunctions and negations of linear constraints. Negations
may be replaced by the opposite inequality. We may then use Lemma (6.3) to
convert the linear constraints into ``disjunctive normal form'', i.e., into
a disjunction of groups where each group is a conjunction of constraints, or
equivalently, a polyhedron. By Lemma (6.3), this does not increase the size
by more than a polynomial in fixed dimension. The details of the conversion
to ``disjunctive normal form'' are left to the reader. Also, note that
Lenstra's result as stated works only for the case of one polyhedron ; but
obviously, we may repeat the procedure for each $P_i$.
The algorithm is polynomial time bounded
provided $n$ is fixed.
Theorem (7.2) gives an algorithm for deciding certain so-called $\Pi _2$
sentences (using terminology from Logic) , i.e., sentences of the form
$$\forall y\in {\bf Z}^p\quad \exists x\in {\bf Z}^n:\qquad (x,y)\in P.$$
This algorithm is polynomial time bounded provided $n+p$ is fixed. A
general $\Pi_2$ sentence over Presberger arithmetic could require $(x,y)$
to belong to a union of polytopes rather than just one (cf. last paragraph)
. If it is the union
of $l$ polytopes, then using $O(\log l)$ extra integer variables, we can
write it as a conjunction of constraints. So if $l$ also fixed, we have a
polynomial time algorithm for deciding such sentences. It is an interesting
open problem to remove this restriction that $l$ be fixed.
More interestingly, we do not know decision procedure for $\Sigma _3$
sentences which runs in polynomial time for fixed number of variables. This
and similar algorithms for higher levels of the hierarchy in Presberger
arithmetic remain interesting open problems.
\vskip0.9in
{\bf Acknowledgments } I thank Imre B\'ar\'any,
Bill Cook, Mark Hartmann, Laci Lov\'asz, Herb Scarf and David Shallcross for
many helpful discussions.
\vskip0.9in
{\bf References}
\begin{enumerate}
\item D.E.Bell, \label{bell}{\it A theorem concerning the integer lattice},
Studies in Applied Mathematics, 56, (1976/77) pp187-188 (see Math. Rev. 57\#
2590)
\item A.Brauer and J.E.Shockley, \label{bs} {\it On a problem of Frobenius},
Journal f\"ur reine und angewnadte Mathematik, 211 (1962) pp 399-408
(see Math. Rev. 47\#127)
\item W.Cook, A.M.H.Gerards, A.Schrijver and E.Tardos, \label{cgst} {\it
Sensitivity theorems in integer linear programming }, Mathematical
Programming 34 (1986) pp 251-264
\item P.Erd\"os and R.Graham\label{erdos},
{\it On a linear diophantine problem of Frobenius},
Acta Arithmetica, 21 (1972).
\item H.Greenberg\label{green}, {\it Solution to a linear diophantine
equation for nonnegative integers}, Journal of Algorithms 9, pp 343-353,
(1988).
\item M.Hujter and B.Vizv\'ari, \label{hv}
{\it The exact solution to the Frobenius
problem with three variables}, Journal of the Ramanujan Math. Soc.,
2 (1987) pp 117-143; (see Math. Rev. 89f:11039).
\item M.Gr\"otschel, L.Lov\'asz and A.Schrijver, \label{gls}{\it Geometric
algorithms and combinatorial optimization}, Springer-Verlag (1988)
\item J. Incerpi and R.Sedgwick, \label{sedgwick}
{\it Improved upper bounds on ShellSort}, Journal of Computer and Systems
Sciences, Vol. 31, No. 2, October 1985 pp 210-224. (see Math. Rev. 87j\# 68025)
\item R.Kannan, \label{kannan}
{\it Minkowski's Convex body theorem and integer programming},
Mathematics of Operations Research, Volume 12, Number 3, (1987) pp415-440.
\item R.Kannan and L.Lov\'asz,\label{kl}
{\it Covering minima and lattice point free convex
bodies}, in Lecture Notes in Computer Science 241, ed. K.V.Nori,
Springer-Verlag (1986) pp 193-213. Final version in
Annals of Mathematics, Volume 128, No.3, pp 577-602 (1988).
(see Math. Rev. 89b:11055, 89i:52020)
\item R.Kannan, L.Lov\'asz and H.E.Scarf,\label{kls} {\it The shapes of
polyhedra}, Cowles Foundation Discussion paper No. 883, September (1988). To
appear in Mathematics of Operations Research.
\item H.Krawczyk and A.Paz, \label{paz} , {\it The diophantine problem of
Frobenius : A close bound}, Discrete Applied Mathematics 23 (1989) pp
289-291.
\item H.W.Lenstra, \label{lenstra}{\it Integer programming with a fixed number
of variables}, Mathematics of Operations Research, Volume 8, Number
4 Nov (1983) pp 538-548
\item L.Lov\'asz, \label{lovasz}{\it Geometry of Numbers and Integer
Programming}, Proceedings of the 13 th International Symposium on
Mathematical Programming, M.Iri and K.Tanabe eds., Mathematical
Programming (1989) pp 177-201.
\item O.J.R\"odseth, \label{rodseth}
{\it On a linear diophantine problem of Frobenius}, Journal
f\"ur reine und angewante Mathematik, 301, (1978), pp 171-178.
(see Math. Rev. 58\#27741)
\item H.E.Scarf, \label{scarf} {\it An observation on the structure of
production sets with indivisibilities}, Proceedings of the National Academy
of Sciences, USA, 74, pp 3637-3641 (1977).
\item H.E.Scarf and D.Shallcross, \label{ss} {\it The Frobenius problem
and maximal lattice free bodies}, Manuscript (1989).
\item R.Sedgwick, \label{sedgwick2}
{\it A new upper bound for ShellSort}, Journal of Algorithms, 7
(1986), pp 159-173. (see Math. Rev. 87e:68015)
\item E.S.Selmer, \label{selmer}
{\it On the linear diophantine problem of Frobenius}, Journal
f\"ur reine und angewandte Mathematik, 293/294 (1977) pp 1-17.
(see Math. Rev.56\#246)
\item E.S.Selmer and O.Beyer, \label{sb}
{\it On the linear diophantine problem of Frobenius
in three variables} Journal f\"ur reine und angewandte
Mathematik, Band 301, (1978), pp 161-170. (see Math. Rev.58\#27740)
\item A.Schrijver, \label{schrijver}, {\it Theory of Linear and Integer
Programming}, Wiley (1986).
\item B.Vizv\'ari, \label{viz} {\it An application of Gomery cuts in number
theory}, Periodica Mathematica Hungaria 18 (1987) pp 213-228. (see Math.
Rev. 89d:11017)
\end{enumerate}
\end{document}
try it. i will be off tomorrow, so i may not log n anymore. will see
you next week, thanks