# A note on the low-dimensional Minkowski-reduction

Ákos G.Horváth  Á. G.Horváth, Dept. of Geometry, Budapest University of
Technology, Egry József u. 1., Budapest, Hungary, 1111<EMAIL_ADDRESS>
###### Abstract.

In this research-expository paper we recall the basic results of reduction
theory of positive definite quadratic forms. Using the result of Ryskov on
admissible centerings and the result of Tammela about the determination of a
Minkowski-reduced form, we prove that the absolute values of coordinates of a
minimum vector in a six-dimensional Minkowski-reduced basis are less or equal
to three. To get this little sharpening of the result which can be deduced
automatically from Tammela’s works we combine some elementary geometric
reasonings with the mentioned theoretical results.

###### Key words and phrases:

Dirichlet-Voronoi cell, Hermite-reduction, minimum vector of a lattice,
Minkowski-reduction, admissible centering, positive quadratic forms

###### 2020 Mathematics Subject Classification:

11H50, 11H55

##  1\. Introduction

A lattice is a discrete subgroup of $\mathbb{R}^{n}$. Any lattice $L$ has a
lattice basis, i.e., a set of linearly independent vectors such that the
lattice is the set of all integer linear combinations of them. All bases have
the same number of elements, called the dimension of the lattice. A reduced
basis is a basis made of reasonably short vectors that are almost orthogonal.
There exist many different notions of reduction. The most important classic
reductions are of Hermite [13], of Minkowski [16], of Korkine-Zolotarev [14]
and of Venkov [28]. For computational point of view well-usable the Lenstra-
Lenstra-Lovász (LLL) reduction [15] and there are some nice recent variation
as the one of Nguyen and Stehlé in works [18] and [19]. Comparison of these
methods in theoretical point of view is not so simple as we think for a first
glance. The long story that the reductions of Minkowski and of Hermite are
agree up to six dimension and gives distinct results in higher dimension can
be found in [21]. We shortly review the history of this result. Ryskov proved
in [20] that these are agree for dimensions $n\leq 5$ and distinct for $n\geq
11$. In a private letter Barnes wrote to Ryskov that there is a counting error
in his paper from which follows that the two reductions are distinct in
dimensions $9$ and $10$. Meanwhile P.P. Tammela proved in [24] that the
reduction by Minkowski and by Hermite are equivalent in dimension $6$.
Finally, Ryskov in [21] closed the problem, he gave an example of dimension
seven for a quadratic form which is Minkowski-reduced but not Hermite-reduced
one. More detailed history of the reduction theory see the book [12] and the
literature therein.

Very important task in geometric number theory to find a shortest vector in a
lattice which we call minimum vector of the lattice. All classical theory of
reduction a priori assumes the solvability of this problem. The problem of
searching of minimum vectors connects reduction theory of positive definite
quadratic forms, the theory of admissible centerings of a minimum
parallelepiped and the determination problem of the Dirichlet-Voronoi cell of
a lattice. The geometric structure of minimum vectors of a lattice also
important in another theory of mathematics it can be used in the packing and
covering problems of discrete geometry, in coding theory, and the theory of
root lattices which is used in modern differential geometry.

In this expository-research paper we concentrate to the coordinates of minimum
vectors in a Minkowski-reduced basis. A definition or result can be found in
that section where it first appear. In the first section we recall the
definition of Minkowski and Hermite reductions and give a $9$-dimensional
example for a Minkowski-reduced basis which is not Hermite-reduced one. Its
advantage is the simple geometric proof on the basis of the natural geometric
definitions.(This example can be found in [8] in Hungarian.) In the second
section we summarize the theory of admissible centerings and that results
which needed to the proof of our Theorem 1. It can be found in the last
section of this paper.

##  2\. Minkowski-reduced form which is not Hermite-reduced one.

In our paper $n$-dimensional _lattice_ $L[e_{1},\ldots,e_{n}]$ is the set of
the integer linear combinations of a basis $\\{e_{1},\ldots,e_{n}\\}$ of the
$n$-dimensional real vector space
$\mathbb{R}^{n}=\mathrm{Lin}[e_{1},\ldots,e_{n}]$. A $k$-element _primitive
system_ $\\{f_{1},\ldots,f_{k}\\}$ of the lattice contains such lattice
vectors for which $\mathrm{Lin}[f_{1},\ldots,f_{k}]\cap
L[e_{1},\ldots,e_{n}]=L[f_{1},\ldots,f_{k}]$. A basis of the lattice is a
primitive system of $n$ elements. A basis of the lattice is _reduced by
Hermite_ (or Hermite-reduced one) if it is a lexicographical minimum of bases
arranged by the increasing lengths of their elements. A _Minkowski-reduced
basis_ (or basis reduced by Minkowski) can be get on the following algorithm:
Denote by $a_{1}$ a shortest vector of the lattice, let $a_{2}$ be a shortest,
from $a_{1}$ linearly independent vector, which gives with $a_{1}$ a primitive
system, and similarly for $a_{i}$ $i=3,\ldots,n$. Then
$\\{a_{1},\ldots,a_{n}\\}$ is a basis reduced by Minkowski. Clearly, all
subsets of a primitive system are also primitive one; a shortest vector of a
lattice is a primitive one; in all $n$-lattice there exist bases reduced by
Minkowski and also bases reduced by Hermite. If a basis is reduced by Hermite
then it is reduced by Minkowski, and a basis which contains only minimum
vectors is reduced by Hermite.

In every lattice we can use the following algorithm to get a linearly
independent vector system of short vectors: Denote by $a_{1}$ a shortest
vector of the lattice, let $a_{2}$ be a shortest, from $a_{1}$ linearly
independent vector and similarly for $a_{i}$ $i=3,\ldots,n$. The system
$\\{a_{1},\ldots,a_{n}\\}$ is a so-called _system of successive minimum
vectors_. The lengths of these vectors are the _successive minima_ of the
lattice. In general it is not a basis in the original lattice.

To get a basis in a lattice which is reduced by Minkowski but is not reduced
by Hermite consider the following construction. Let the lattice
$L[e_{1},\ldots,e_{9}]$ of dimension $9$ in the twelve-dimensional Euclidean
space $\mathbb{R}^{12}$ is spanned by the column $e_{i}$ of the matrix:

(1)
$E=\left(\begin{array}[]{ccccccccc}\frac{1}{2}&0&0&0&0&0&0&\frac{1}{2}&0\\\
\frac{1}{2}&0&0&0&0&0&0&0&\frac{1}{3}\\\
\frac{1}{2}&0&0&0&0&0&0&0&\frac{1}{3}\\\
\frac{1}{2}&0&0&0&0&0&0&0&\frac{1}{3}\\\ 0&1&0&0&0&0&0&\frac{1}{2}&0\\\
0&0&1&0&0&0&0&\frac{1}{2}&0\\\ 0&0&0&1&0&0&0&0&\frac{1}{3}\\\
0&0&0&0&1&0&0&0&\frac{1}{3}\\\ 0&0&0&0&0&1&0&0&\frac{1}{3}\\\
0&0&0&0&0&0&1&0&\frac{1}{3}\\\ 0&0&0&0&0&0&0&0&\frac{1}{3}\\\
0&0&0&0&0&0&0&-\frac{1}{2}&\frac{1}{3}\end{array}\right)$

(The coordinates are written with respect to an orthonormal vector system of
$\mathbb{R}^{12}$.) We prove that the length of a lattice vector is greater or
equal to $1$ so the columns of the matrix $E$ (of lengths $1$) forms a
Hermite-reduced basis of $L$. Thus it is also a Minkowski-reduced basis (and
the corresponding quadratic form is a Minkowski-reduced form).

In fact, the square of the lengths of the lattice vector
$v=\sum\limits_{i=1}^{9}x_{i}e_{i}$ can be get in two ways. It is the squared
sum of its coordinates and also an integer substitution of the symmetric
quadratic form $f(x)$ generated by the Gram matrix of the basis
$\\{e_{1},\ldots,e_{12}\\}$. Hence we have

(2)
$\sum\limits_{i=1}^{12}v_{i}^{2}=v^{T}v=x^{T}(E^{T}E)x=x^{T}Gx=:f(x)=\sum\limits_{i=1}^{9}x_{i}^{2}+\frac{1}{2}x_{1}x_{8}+x_{1}x_{9}-\frac{1}{3}x_{8}x_{9}.$

From this we can see if $x_{8}=x_{9}=0$ then $f(x)\geq 1$. If $x_{8}=0$ and
$x_{9}\neq 0$ then $x_{1}^{2}+x_{1}x_{9}+x_{9}^{2}\geq 1$ for all integer
values of $x_{1}$ and $x_{9}$ because
$|x_{1}x_{9}|\leq\max\\{x_{1}^{2},x_{9}^{2}\\}$. Similarly, if $x_{8}\neq 0$
and $x_{9}=0$ then $x_{1}^{2}+\frac{1}{2}x_{1}x_{8}+x_{8}^{2}\geq 1$. Finally,
if $x_{8}\neq 0$ and $x_{9}\neq 0$ then we have three cases.

Assume first that $|x_{9}|\geq 3$. Then $|v_{11}|\geq 1$ so $|v|\geq 1$, too.

Secondly, if $|x_{9}|=2$ and $x_{8}$ is an odd integer then
$|v_{5}|,|v_{6}|\geq\frac{1}{2}$,
$|v_{7}|,|v_{8}|,|v_{9}|,|v_{10}|\geq\frac{1}{3}$ and
$|v_{11}|\geq\frac{2}{3}$ showing that $|v|^{2}\geq\frac{1}{2}+\frac{8}{9}>1$.
Similarly, if $|x_{9}|=2$ and $x_{8}$ is even then
$|v_{7}|,|v_{8}|,|v_{9}|,|v_{10}|,|v_{12}\geq\frac{1}{3}$ and
$|v_{11}|\geq\frac{2}{3}$ implying that $|v|^{2}\geq 1$.

In the third case, $|x_{9}|=1$ and again either $x_{8}$ is odd or $x_{8}$ is
even. In both cases $|v_{7}|,|v_{8}|,|v_{9}|$,
$|v_{10}|,|v_{11}|\geq\frac{1}{3}$ and either $|v_{5}|,|v_{6}|\geq\frac{1}{2}$
or $|v_{12}\geq\frac{2}{3}$ showing the statement.

Let denote $e_{8}^{\star}$ a unit lattice vector defined by the equality

$e_{8}^{\star}:=-2e_{1}-\sum\limits_{i=2}^{7}e_{i}+2e_{8}+3e_{9}=(0,0,0,0,0,0,0,0,0,0,1,0)^{T}.$

Note that the vector system $\\{e_{1},\ldots,e_{7},e_{8}^{\star}\\}$ is a
primitive system. Really, if a lattice vector $v\in L[e_{1},\ldots,e_{9}]$ is
in that linear subspace which is spanned by this linearly independent vectors,
then its last coordinate is zero. This gives the equality $3x_{8}=2x_{9}$,
hence $x_{8}$ is even and $x_{9}$ can be divided by $3$. Hence the coordinates
of $x_{8}e_{8}+x_{9}e_{9}$ are integers moreover the first four coordinates
are always agree to each other. Hence $v$ is in the integer linear hull of
$\\{e_{1},\ldots,e_{7},e_{8}^{\star}\\}$ as we stated.

Since this primitive system contains only minimal vectors, it can be
supplemented to a Minkowski-reduced basis with a vector $e_{9}^{\star}\in
L[e_{1},\ldots,e_{9}]$. Since this will be a basis its coordinates has to
satisfy the following congruences

$v_{2}\equiv v_{3}\equiv v_{4}\equiv v_{12}\equiv\pm\frac{1}{6}\mod(1)$
$v_{5}\equiv v_{6}\equiv\frac{1}{2}\mod(1)$

and

$v_{7}\equiv v_{8}\equiv v_{9}\equiv v_{10}\equiv v_{11}\equiv\pm\frac{1}{3}.$

From this we get that

$|e_{9}^{\star}|^{2}\geq\frac{4}{36}+\frac{20}{36}+\frac{18}{36}=\frac{7}{6}>1.$

Hence this basis is Minkowski-reduced basis but not Hermite-reduced one. (It
can be seen easily that with the vector $e_{9}^{\star}:=-e_{1}+e_{8}+e_{9}$,
the above primitive system is a Minkowski-reduced basis.)

##  3\. The admissible centering of a lattice

In general, the lattice $L[e_{1},\ldots,e_{n}]$ of dimension $n$ is a
_centering_ of the lattice $L^{\prime}[a_{1},\ldots,a_{n}]$ of the same
dimension if $L^{\prime}[a_{1},\ldots,a_{n}]\subset L[e_{1},\ldots,e_{n}]$. We
have a quite simple possibility to define the concept of _admissible
centering_ of $L^{\prime}[a_{1},\ldots,a_{n}]$ if in it there is a basis which
elements have minimal length (briefly we say that in
$L^{\prime}[a_{1},\ldots,a_{n}]$ there is a _minimum basis_). In this case, we
say that the centering is _admissible_ if $\min
L^{\prime}[a_{1},\ldots,a_{n}]=\min L[e_{1},\ldots,e_{n}]$, where $\min
L[e_{1},\ldots,e_{n}]$ means the minimal value of the lengths of the vectors
of $L[e_{1},\ldots,e_{n}]$. Note, that in general there is no minimum basis of
a lattice, hence the above strict idea of permissibility cannot be
interpretable. On the other hand, in all lattices we can find system of
successive minimum vectors. In this case take $n$ independent lattice vectors
$\\{a_{1},\ldots,a_{n}\\}$ which lengths are the successive minima of the
lattice $L^{\prime}[e_{1},\ldots,e_{n}]$. Then
$L^{\prime}[e_{1},\ldots,e_{n}]$ is a centering of $L[a_{1},\ldots,a_{n}]$. We
say that this centering is admissible if for arbitrary sequence $1\leq
i_{1}<\ldots i_{k}\leq n$ of indices in the lattice
$\mathrm{Lin}[a_{i_{1}},\ldots,a_{i_{k}}]\cap L^{\prime}[e_{1},\ldots,e_{n}]$
the successive minima are $|a_{i_{1}}|\leq\ldots\leq|a_{i_{k}}|$.

If the lattice $L[a_{1},\ldots,a_{n}]$ with the minimum basis
$[a_{1},\ldots,a_{n}]$ has a admissible centering
$L^{\prime}[e_{1},\ldots,e_{n}]$ then in the half-closed basic parallelepiped
$\Pi[a_{1},\ldots,a_{n}]$ are finitely many points $\\{s_{1},\ldots s_{j}\\}$
of $L^{\prime}[e_{1},\ldots,e_{n}]$ with the following properties:

  * •

The vector system $\\{a_{1},\ldots,a_{n},s_{1},\ldots s_{j}\\}$ generates
precisely the lattice $L^{\prime}[e_{1},\ldots,e_{n}]$.

  * •

$\min L[a_{1},\ldots,a_{n}]=\min L^{\prime}[e_{1},\ldots,e_{n}]$.

The modified version of this denotation for admissible centerings of a lattice
with basis containing the successive minimum vectors of
$L^{\prime}[e_{1},\ldots,e_{n}]$ is also used. Ryskov in [23] proved that for
every admissible centerings of a parallelepiped based on the successive
minimum vectors of a lattice there is an affinity which sends to this
parallelepiped to a admissible centerings of a parallelepiped based on a
system of minimum vectors of the corresponding lattice. This result says that
the admissible centerings of the lattices having basis from successive minimum
vectors combinatorially the same as the admissible centerings of those
lattices which have minimum basis. A lattice $L^{\star}[e_{1},\ldots,e_{n}]$
(given by a basis) is always a admissible centerings of a lattice
$L[a_{1},\ldots,a_{n}]$ which is spanned by a system of successive minimum
vectors of $L^{\prime}[e_{1},\ldots,e_{n}]$. By Ryskov’s result the relative
connection between the two lattices always can be described as a admissible
centering of a lattice with minimum basis. If a given dimension the admissible
centerings are classified then we know the possible connections between the
given lattice $L^{\prime}[e_{1},\ldots,e_{n}]$ and its sublattices
$L[a_{1},\ldots,a_{n}]$. The following table of Ryskov contains the most
important geometric data of the admissible centerings of a minimum
parallelepiped. To review it note that the above points $\\{s_{1},\ldots
s_{j}\\}$ of the parallelepiped $\Pi[a_{1},\ldots,a_{n}]$ have rational
coordinates with respect to the basis $\\{a_{1},\ldots,a_{n}\\}$. In fact, if
a basis of $L^{\prime}[e_{1},\ldots,e_{n}]$ is $\\{f_{1},\ldots,f_{n}\\}$,
then the matrix $A$ of the linear transformation sending $f_{i}$ to $e_{i}$
has integer elements. The coordinates of the points $\\{s_{1},\ldots s_{j}\\}$
are also integers with respect to the basis $\\{f_{1},\ldots,f_{n}\\}$. Hence
the basis change $f_{i}$ to $e_{i}$ changes the coordinates of
$\\{s_{1},\ldots,s_{j}\\}$ such rational coordinates whose denominators divide
the determinant of $A$. Hence the least common multiple $U$ of the
denominators of the coordinates of the points $\\{s_{1},\ldots s_{j}\\}$
divides the determinant $V$ of $A$. $V$ is the volume (or index) of the
centering. The relevant rows of a admissible centering are the coordinates of
$\\{s_{1},\ldots s_{j}\\}$ with respect to the basis
$\\{a_{1},\ldots,a_{n}\\}$. Table 3 contains the data of the admissible
centerings up to dimension $6$.

(3)
$\begin{array}[]{|c|c|c|cccccc|}\hline\cr\mbox{dimension}&U&V&\lx@intercol\hfil\mbox{relevant
rows}\hfil\lx@intercol\vrule\lx@intercol\\\ \hline\cr\hline\cr
2&1&1&0,&0&&&&\\\ \hline\cr 3&1&1&0,&0,&0&&&\\\ \hline\cr
4&1&1&0,&0,&0,&0&&\\\ \hline\cr 4&2&2&{1}/{2},&{1}/{2},&{1}/{2},&{1}/{2}&&\\\
\hline\cr 5&1&1&0,&0,&0,&0,&0&\\\ \hline\cr
5&2&2&{1}/{2},&{1}/{2},&{1}/{2},&{1}/{2},&0&\\\ \hline\cr
5&2&2&{1}/{2},&{1}/{2},&{1}/{2},&{1}/{2},&{1}/{2}&\\\ \hline\cr
6&1&1&0,&0,&0,&0,&0,&0\\\ \hline\cr
6&2&2&{1}/{2},&{1}/{2},&{1}/{2},&{1}/{2},&0,&0\\\ \hline\cr
6&2&2&{1}/{2},&{1}/{2},&{1}/{2},&{1}/{2},&{1}/{2},&0\\\ \hline\cr
6&2&2&{1}/{2},&{1}/{2},&{1}/{2},&{1}/{2},&{1}/{2},&{1}/{2}\\\ \hline\cr
6&2&4&{1}/{2},&{1}/{2},&{1}/{2},&{1}/{2},&0,&0\\\
&&&{1}/{2},&{1}/{2},&0,&0,&{1}/{2},&{1}/{2}\\\
&&&0,&0,&{1}/{2},&{1}/{2},&{1}/{2},&{1}/{2}\\\ \hline\cr
6&3&3&{1}/{3},&{1}/{3},&{1}/{3},&{1}/{3},&{1}/{3},&{1}/{3}\\\
\hline\cr\end{array}$

Note that similar table of dimension seven was also given by Ryskov in [23],
and of dimension eight by Zakharova and Novikova in [27], but there is no such
in higher dimension.

##  4\. Characterization of the Minkowski-reduced forms by a finite system of
inequalities.

We turn now to the third from the following three question of reduction
theory:

  * •

How we can find a something-like reduced basis in a given lattice?

  * •

How we can find a minimum vector or a short vector in a given lattice?

  * •

How we can find all minimum vectors in a given lattice if we know one of its
reduced basis?

In low-dimensional cases the first two questions can be solved. The reason is
that Tammela in [24] up to dimension six gave a chance to search Minkowski and
(also Hermite) reduced basis. We recall his argument. Every basis
$\\{e_{1},\ldots,e_{n}\\}$ of a lattice determines a point in the
$N=:\binom{n+1}{2}$-dimensional Euclidean space by the coefficients of its
symmetric Gram matrix. The set of all such points is an open convex cone in
$\mathbb{R}^{N}$ with vertex the origin. In this cone the Minkowski-reduced
forms set a sub-domain is denoted by $\mathcal{M}$. A positive quadratic form
$Q$ (also corresponding to the Gram matrix of the given basis) is Minkowski-
reduced if for every point $u=\sum\limits_{i=1}^{n}u_{i}e_{i}$
($u_{i}\in\mathbb{Z}$) with $\mathrm{g.c.d}(u_{i},\ldots u_{n})=1$ holds the
inequality $Q(u)\geq Q(e_{i})$. (It can be seen easily that in this case the
basis $\\{e_{1},\ldots,e_{n}\\}$ is a Minkowski-reduced basis of the
corresponding lattice.) Now the domain $\mathcal{M}\cup\\{0\\}$ is a closed
convex cone with apex $0$. It can be given the explicit description of
$\mathcal{M}$ for $n\leq 6$. One can specify a concrete finite system of
inequalities $Q(u)\geq Q(e_{i})$ that determine $\mathcal{M}$. It consists of
the $n-1$ inequalities $Q(e_{i+1})\geq Q(e_{i})$ and inequalities $Q(u)\geq
Q(e_{i})$ for which $u$ can be transformed into a column of the matrix

(4) $\left(\begin{array}[]{ccccccccc}1&1&1&1&1&1&1&1&1\\\ 1&1&1&1&1&1&1&1&1\\\
0&1&1&1&1&1&1&1&1\\\ 0&0&1&1&1&1&1&1&1\\\ 0&0&0&1&2&1&1&2&2\\\
0&0&0&0&0&1&2&2&3\\\ \end{array}\right)$

by permuiting the coordinates of $u$ and omitting the signes of these
coordinates, while $\mathrm{g.c.d}(u_{i},\ldots,u_{n})=1$. This result was
announced by Minkowski for $n\leq 6$ (only the columns with nonzero
coordinates $\leq n$ are taken in dimension $n$) and proved by Minkowski for
$n\leq 4$ ([17]), Ryskov (in [22]) and later Afflerbach (in [1]) for $n=5$ and
by Tammela for $n=6$. The result was slightly refined and extended to the case
$n=7$ by Tammela in [26].

This result says that $\\{e_{1},\ldots,e_{n}\\}$ forms a Minkowski-reduced
basis in its lattice $L[e_{1},\ldots,e_{n}]$ if for the above finite number of
inequalities $Q(u)\geq Q(e_{i})$ hold with the vectors permitted by the table.
Contrary, if we find a vector $u$ permitted by the table for which the reverse
inequality hold the basis is not reduced by Minkowski. In general to find
algorithmically a shortest vector (minimum vector) in a lattice is a hard task
so to find a Minkowski-reduced basis in a lattice is not easy, too. First
Beyer, Roof and Williamson in [4], and Beyer in [5]) did an algorithm for
determination of a Minkowski-reduced basis. In practice, this algorithm is
used only $n\leq 6$. The Minkowski reduction theory can be extended to
integral $n\times m$ matrices with respect to the module $\mathcal{M}$ which
is the module over the integers generated by the columns of the given $n\times
m$ matrix $A$. Zassenhaus and Ford indicated that the number of operations
needed to reduce the matrix decreases sharply if $m$ fixed and $n$ tends to
infinity. This fact was established by Donaldson in [7] using probability
method. In his paper by the assumption that we need to check only finite
number of inequalities to identify a reduced matrix, was given a sketch of an
algorithm as follows: Let $Q$ be the quadratic form corresponding to the given
basis $\\{l_{1}\ldots,l_{n}\\}$. We test all the finitely many inequalities.
If all are satisfied, we are done. If contrary for a row $s_{1},\ldots,s_{n}$
in the table we have $Q(l_{k})>Q(s_{1}l_{1}+\ldots+s_{n})$, we may apply an
unimodular transformation to replace $l_{k}$ by $s_{1}l_{1}+\ldots+s_{n}l_{n}$
and leave $l_{1},...,l_{k-1}$ fixed (that this is possible follows from the
fact that $\mathrm{g.c.d}(s_{k},\ldots,s_{n})=1$. Eventually, all the
inequalities must be satisfied, and the matrix will be Minkowski reduced.

A little bit later Afflerbach and Groethe presented a new algorithm which is
more practicable for greater dimensions and requires less computation time
(see in [2]). The algorithm presented in their paper was used to determine
Minkowski-reduced lattice bases of pseudo-random number generators up to
dimension 20. We suggest for the interested reader the paper of Agrell,
Eriksson, Vardy and Zeger (see [3]) to a good review on the algorithmically
point of view of the closest lattice point and reduced bases problems.

To recall again Tammela’s work we note that his method can be used to
determine the Dirichlet-Voronoi cell of a lattice point, too. Note that the
Dirichlet-Voronoi cell of a lattice point contains those points of the space
which are closer to it as to any other lattice-point. The cell is a convex
polytope, which facets are determined by certain lattice vectors; these
vectors are their normal vectors and go through they middle points,
respectively. We call them relevant vectors of the cell. It can be seen
easily, that all minimum vectors of a lattice are relevant vectors of the
Dirichlet-Voronoi cell of the origin. We can read more to the Dirichlet-
Voronoi cells in papers [9, 10, 11]. In his work [25] proved that with respect
to a Minkowski-reduced basis, the integer representation of the relevant
vectors of the Dirichlet-Voronoi cell of the lattice can be found among those
lattice vectors which can be transformed into a column of the matrix of Table
5

(5)
$\left(\begin{array}[]{ccccccccc||ccccccccc||ccccc}1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\\
1&1&1&1&1&1&1&1&1&0&1&1&1&1&1&1&1&1&1&1&1&1&2\\\
0&1&1&1&1&1&1&1&1&0&1&1&1&1&1&1&2&1&1&1&1&2&2\\\
0&0&1&1&1&1&1&1&1&0&2&2&1&2&2&2&2&1&2&2&2&2&2\\\
0&0&0&1&2&1&1&2&2&0&0&2&1&2&2&2&2&2&3&3&3&3&3\\\
0&0&0&0&0&1&2&2&3&0&0&0&3&2&3&4&3&m&0&3&4&4&3\\\ \end{array}\right)$

by permuiting the coordinates and omitting the signes of these coordinates, if
we exclude the last column $(1,1,1,1,2,m)^{T}$ of the second part. The reason
of the partitioning of the matrix is that the first part is Table 4 can be
used to the reduction process. The second part (with the mentioned column)
holds the property, that contains those vectors which could be shorter than
the longest reduced-basis vector needed to its representation. In dimension
$n$ we have to take into consideration only those vectors which have less or
equal to $n$ non-zero coordinates.

Since a vector of minimal length is always relevant vector of the Dirichlet-
Voronoi cell of the origin, its coordinates with respect to a Minkowski-
reduced basis can be permuted one of the column of this table if we also omit
the signs of the coefficient.

##  5\. The coordinates of a minimum vector in a Minkowski-reduced basis

Let $n\leq 6$ and assume that the lattice $L[e_{1},\ldots,e_{6}]$ is spanned
by a Minkowski-reduced basis. Combining the results on admissible centerings
with the results of reduction theory we can prove a little sharpening of
Tammela’s result on the coordinates of the minimum vectors. From the Tables 5
we see that the maximum of the absolute value of the coordinates in dimension
$5$ and $6$ are $3$ and $4$, respectively. We prove the following:

######  Theorem 1.

Let $n\leq 6$ be the dimension of a lattice $L$. The absolute value of a
coordinate of a minimum vector with respect to Minkowski-reduced basis of $L$
are less or equal to the maximum of the denominators of the relevant rows in
the $n$-dimensional Table of $n$-dimensional admissible centerings. Precisely,

$|x_{i}|\leq\left\\{\begin{array}[]{ccl}1&\mbox{if}&n=2,3\\\
2&\mbox{if}&n=4,5\\\ 3&\mbox{if}&n=6.\end{array}\right.$

First we highlights some easy geometric observations which we continuously use
in our proof.

  * (A)

Since we prove step by step the statement from lower to higher dimensions,
without loss of generality we can assume that there is no zero coordinate of
the investigated minimum vector $m=\sum x_{i}e_{i}$.

  * (B)

If a parallelepiped $\Pi[a_{1},\ldots,a_{n}]$ has a $k$-dimensional centered
face of denominator $2$ then its volume is even. In fact, if the centered face
is $\Pi[a_{1},\ldots,a_{k}]$ then the coordinates of the vector
$b=(1/2)(a_{1}+\ldots+a_{k})\in L[e_{1},\ldots,e_{n}]$ are integers,
respectively. Hence the volume of $\Pi[b,a_{2},\ldots,a_{n}]$ is also an
integer. But
$\mathrm{vol}(\Pi[b,a_{2},\ldots,a_{n}])=\det[b,a_{2},\ldots,a_{n}]=(1/2)\det[a_{1}+\ldots+a_{k},a_{2},\ldots,a_{n}]=(1/2)\mathrm{vol}(\Pi[a_{1},a_{2},\ldots,a_{n}])$
proves the statement.

  * (C)

Since the minimum vectors of the lattice $L[e_{1},\ldots,e_{n}]$ are relevant
vectors of the Dirichlet-Voronoi cell of the origin (see [9]), so by Theorem 2
in [25] the absolute value of its coordinates with respect to a Minkowski-
reduced basis can be found in that modification of Table 5 in which we omitted
the last column of the middle part. From this immediately follows that for all
$i$ $|x_{i}|\leq 4$.

  * (D)

We recall a result of G. Csóka from his paper [6]. It says that in a
$n$-dimensional lattice with $n\leq 6$ the Minkowski-reduced basis is the
lexicographical minima of the set of such bases which are ordered by its
increasing lengths of their vectors.(Observe that this theorem is a
consequence of the fact (is proved by Ryskov) that the domains of the
Minkowski-reduced forms, Hermite-reduced forms and $L^{\star}$-reduced forms
are agree for $n\leq 6$.) From this immediately follows that _the first four
elements of a Minkowski-reduced basis gives a primitive system of successive
minimum vectors, and so Ryskov’s affinity sends these vectors to a primitive
system of minimum vectors of the image lattice without changing the
coordinates of a minimum vector. Hence we can assume that
$|e_{1}|=|e_{2}|=|e_{3}|=|e_{4}|=|m|=1$_

  * (E)

Assume that $n\leq 6$ and let $\\{e_{1},\ldots,e_{n-2},x\\}$ be a primitive
system of $n-1$ elements with $|e_{1}|\leq\ldots\leq|e_{n-2}|\leq|x|$.
Additionally we assume that the lattice is spanned by such Minkowski-reduced
basis $\\{e_{1},\ldots,e_{n}\\}$ for which
$e_{n-1}\not\in\mathrm{Lin}[e_{1},\ldots,e_{n-2},x]$. Then there is an
orthogonal affinity $\varphi$ with ratio $(1+\varepsilon)$ with positive
$\varepsilon$, such that hold the following two properties:

    * –

It fixes the vectors of the subspace $\mathrm{Lin}[e_{1},\ldots,e_{n-2},x]$,

    * –

the image vector $e_{n-1}^{\prime}:=\varphi(e_{n-1})$ is a shorter vector
among those vectors which are not lying in the subspace
$\mathrm{Lin}[e_{1},\ldots,e_{n-2},x]$ and completes
$\\{e_{1},\ldots,e_{n-2}\\}$ to a primitive system.

Clearly, $e_{n-1}$ ”shows to the first layer” with respect to the sublattice
$L[e_{1},\ldots,e_{n-2},x]$ and it is a shorter vector in this layer.
Consequently, if we decompose $z$ to the orthogonal components $z_{1}$ and
$z_{2}$, the minimum value of the formula
$|\varphi(z)|=|z_{1}+(1+\varepsilon)z_{2}|$ for every positive $\varepsilon$
attends at $e_{n-1}$ if we take into consideration the vectors $z\in
L[e_{1},\ldots,e_{n-2},e_{n-1},e_{n}]\setminus L[e_{1},\ldots,e_{n-2},x]$. Let
$\varepsilon$ such that the previous minimal value let be greater than the
length of $x$. Now in this lattice
$\\{e_{1},\ldots,e_{n-2},e_{n-1}^{\prime}\\}$ is not a part of a Minkowski-
reduced basis, hence there is a column
$\alpha:=\alpha_{1}e_{1}+\ldots+\alpha_{n-1}e_{n-1}^{\prime}+\alpha_{n}e_{n}^{\prime}$
in the $n$-dimensional part of Table 4, which exclude $e_{n-1}^{\prime}$ from
the possible Minkowski reduced-basis elements. But the vector corresponding to
the row $\alpha$ has to be shorter then $e_{n-1}^{\prime}$. Hence it is in the
original layer implying that
$\alpha=y_{1}e_{1}+\ldots+y_{n-2}e_{n-2}+y_{n-1}x$ where $y_{i}$’s are all
integers. Consequently, at the same time hold the equalities
$\alpha_{n-1}=y_{n-1}x_{n-1}$ and $\alpha_{n}=y_{n-1}x_{n}$. (Here
$\alpha_{n-1}$, $\alpha_{n}$ are such non-zero integers which absolute values
are in Table 4.)

######  Remark 1.

_If $\\{e_{1},\ldots,e_{n}\\}$ is a basis with $|e_{i}|=1$ for all $i$_ then
the statement of Theorem 1 easily proved with the equality
$\mathrm{vol}(\Pi[e_{1},\ldots,m,\ldots
e_{n}])=|x_{i}|\mathrm{vol}(\Pi[e_{1},\ldots,e_{n}])$. In fact, the admissible
volumes in Table 3 are greater than 3 only in one case when $n=6$ and the
centering of the parallelepiped $\Pi[e_{1},\ldots,e_{i-1},m,e_{i+1}\ldots
e_{n}]$ has volume 4. However in this case the corresponding low-dimensional
sublattice $L^{\prime}[e_{1},\ldots,e_{i-1},e_{i+1}\ldots e_{n}]$ contains a
four-dimensional centered cubic lattice $L^{\prime\prime}$ with index $2$ with
respect to $L^{\prime}[e_{1},\ldots,e_{i-1},e_{i+1}\ldots e_{n}]$ and thus
$4=\mathrm{vol}(\Pi[e_{1},\ldots,e_{i-1},m,e_{i+1}\ldots
e_{n}]\geq|x_{i}|\mathrm{ind}(L^{\prime\prime}/L^{\prime}[e_{1},\ldots,e_{i-1},e_{i+1}\ldots
e_{n}])=2|x_{i}|$ implying that in this case also hold the inequality
$|x_{i}|\leq 2$.

###### Proof of Theorem 1.

Let $\\{e_{1},\ldots,e_{n}\\}$ be a Minkowski-reduced basis and $m=\sum
x_{i}e_{i}$ is a minimum vector in the lattice $L=[e_{1},\ldots,e_{n}]$.
Assume that the volume of the basic parallelepiped $\Pi[e_{1},\ldots,e_{n}]$
is equal to 1. By (A) and (D) we can assume that the coordinates $x_{i}$ are
non-zero and the first four elements of the basis are minimum vectors. By
Remark 1 the statement is trivial in dimensions $n\leq 4$ hence we have to
investigate only the cases $n=5$ and $n=6$, respectively.

n=5

Consider the four-dimensional minimum parallelepiped
$\Pi[m,e_{1},e_{2},e_{3}]$. Its edges have length 1 and so the corresponding
system of vectors is a system of successive minima. Then $e_{4}$ be a fifth
successive minima, so the lattice $L[e_{1},\ldots,e_{5}]$ is an admissible
centering of the lattice $L[m,e_{1},e_{2},e_{3},e_{4}]$. Hence
$\mathrm{vol}L[m,e_{1},e_{2},e_{3},e_{4}]=|x_{5}|\leq 2$ by Table 3.

If $\\{e_{1},e_{2},e_{3},m\\}$ is a primitive system then there is a
Minkowski-reduced basis with first four element $\\{e_{1},e_{2},e_{3},m\\}$.
We use here (E) with choice $x=m$, so the coefficients $x_{i}$ are non-zero
integers. Since by the $5$-dimensional part of Table 4 for all $i$
$|\alpha_{i}|\leq 2$, and since $|y_{4}|\geq 1$ we get $|x_{4}|\leq 2$, too.

Assume now that $\\{e_{1},e_{2},e_{3},m\\}$ is not a primitive system in
$L[e_{1},\ldots,e_{5}]$. Then
$L[e_{1},\ldots,e_{5}]\cap\mathrm{Lin(e_{1},e_{2},e_{3},m)}$ is an admissible
centering of $L[e_{1},e_{2},e_{3},m]$. Hence the lattice
$L[e_{1},\ldots,e_{5}]\cap\mathrm{Lin(e_{1},e_{2},e_{3},m)}$ is a centered
cubic lattice of dimension four and volume $2$. Since $e_{4}$ is a fifth
vector with minimal length for which
$\\{e_{1},e_{2},e_{3},e_{4}^{\star},e_{4}\\}$ should form a basis (there is no
admissible centering with volume 4) we can conclude by (D) that $e_{5}$ is
also a minimum vector. We can finish the proof of this case using the result
of the Remark 1, so in this case also hold $|x_{4}|\leq 2$.

Clearly, to prove that $|x_{i}|\leq 2$ for $i=1,2,3$ the argument of $i=4$ can
be applied again.

n=6

We use that the statement is true for $n\leq 5$. Let
$\\{e_{1},\ldots,e_{6}\\}$ be the Minkowski-reduced basis, and
$m=\sum_{i=1}^{6}x_{i}e_{i}$ is the minimal vector with non-zero integer
coefficients.

We have now two cases.

If $\\{e_{1},\ldots,e_{4},m\\}$ is a primitive system then $|e_{5}|=1$ and
$\Pi[e_{1},\ldots,e_{5},m]$ is a minimum parallelepiped with volume $|x_{6}|$.
By (C) $|x_{6}|\leq 4$ and we have to prove that $|x_{6}|\neq 4$. By Table 3
the only lattice which can be centered by volume 4 is the 6-dimensional cubic
lattice. The mentioned centering can be realized metrically only in one way
(see [23] Theorem 6). Here that shortest vector which linearly independent
from $\\{e_{1},\ldots,e_{5}\\}$ and completes it to a basis is also a minimal
vector. Hence we have $|e_{6}|=1$. Now we can use again the last argument of
Remark 1 showing that all coordinates of $m$ is less or equal to 3, as we
stated.

If $\\{e_{1},\ldots,e_{4},m\\}$ is not a primitive system then the face
$\Pi[e_{1},\ldots,e_{4},m]$ is a centered facet of the parallelepiped
$\Pi[e_{1},\ldots,e_{4},m,e_{5}]$. By (B)
$|x_{6}|=\mathrm{vol}(\Pi[e_{1},\ldots,e_{4},m,e_{5}])$ is even. (We note that
in this case immediately cannot apply the Table 3 because $|e_{5}|>1$ also a
real possibility.) By (C) it is either 2 or 4.

  * •

Assume that $|x_{6}|=2$. Then there is a vector $e_{5}^{\star}\in
L[e_{1},\ldots,e_{4},m]$ for which $\\{e_{1},\ldots,e_{4},e_{5}^{\star}\\}$ is
a primitive system. By Table 3 this vector $e_{5}^{\star}$ is of the form
either $1/2(e_{1}+\ldots+e_{4}+m)+L[e_{1},\ldots,e_{4}]$ or
$1/2(e_{1}+\ldots+e_{i-1}+e_{i+1}+\ldots+e_{4}+m)+L[e_{1},\ldots,e_{i-1},e_{i+1},\ldots
e_{4}]$.

    * –

In the first case,
$e_{5}^{\star}=\sum_{i=1}^{4}((x_{i}+k_{i})/2)e_{i}+(x_{5}/2)e_{5}+e_{6}$,
where the coordinates are integers. Now we can apply (E) with
$x:=e_{5}^{\star}$ and so we have an integer vector $\alpha$ for which by the
integer coefficient $y_{n-1}$ hold simultaneously the equalities
$\alpha_{5}=y_{5}(x_{5}/2)$ and $\alpha_{6}=y_{5}$. Since
$|\alpha_{6}|=|y_{5}|\leq 3$ and $|\alpha_{5}|=|y_{5}||x_{5}/2|\geq 3$ we have
the possibilities: $|y_{5}|=3$ and $|x_{5}|\leq 2$; $|y_{5}|=2$ and
$|x_{5}|\leq 3$; or $|y_{5}|=1$ and $|x_{5}|\leq 6$, respectively. By (C) we
have to exclude only that $|x_{5}|=4$ could hold. Indirectly assume that
$|x_{5}|=4$ and consider the system $\\{e_{1},e_{2},e_{3},m,e_{6}\\}$. By the
integer coordinates of $e_{5}^{\star}$ $x_{4}$ is odd, hence $e_{4}$ is not in
the lattice $\mathrm{Lin}[e_{1},e_{2},e_{3},m,e_{6}]\cap
L[e_{1},\ldots,e_{6}]$ and we can use again (E). From this follows that there
is an integer vector
$\beta=\beta_{1}e_{1}+\beta_{2}e_{2}+\beta_{3}e_{3}+\beta_{6}e_{6}+\beta_{4}e_{4}^{\prime}+\beta_{5}e_{5}^{\prime}\in\mathrm{Lin}[e_{1},e_{2},e_{3},m,e_{6}]\cap
L[e_{1},e_{2},e_{3},e_{6},e_{4}^{\prime},e_{5}^{\prime}]$ with coordinates
$|\beta_{i}|\leq 3$. Here
$m=x_{1}e_{1}+x_{2}e_{2}+x_{3}e_{3}+x_{4}e_{4}^{\prime}+x_{5}e_{5}^{\prime}+x_{6}e_{6}$.
$\beta$ has the form $y_{1}e_{1}+y_{2}e_{2}+y_{3}e_{3}+y_{4}m+y_{6}e_{6}$
where $|\beta_{5}|=|y_{4}x_{5}|\leq 3$ and so $|y_{4}|=k/4$ with $k=1,2$ or
$3$ ($k=0$ implies that $\beta\in L[e_{1},e_{2},e_{3},e_{6}]$ therefore
$e_{6}$ cannot be chosen to the sixth element of a Minkowski-reduced basis).
But $y_{4}x_{4}$ is also an integer hence $x_{4}$ is even which is a
contradiction with the fact that $x_{4}$ is odd and by assumption it is non-
zero. We finally got that in this case $|x_{5}|\leq 3$ holds. But $|x_{5}|=2$
because it is also non-zero and even. Investigate now the first four
coordinates. By the above argument $|y_{4}|=k/2$ where $k=1,2$ or $3$. Since
$x_{4}$ is odd then $k=2$, $|y_{4}|=1$ and $3\geq|\beta_{4}|=|x_{4}|$ proves
the required inequality for the fourth coordinate $x_{4}$, too. Clearly, the
first four coordinates have equivalent role in our arguments, so for all $i$
in this case hold the equality $|x_{i}|\leq 3$.

    * –

Secondly, we assume that
$e_{5}^{\star}=\sum_{i=2}^{4}((x_{i}+k_{i})/2)e_{i}+(x_{5}/2)e_{5}+e_{6}$,
hence $e_{5}^{\star}$ gives a admissible centering of the minimal
4-dimensional parallelepiped $\Pi[e_{2},e_{3},e_{4},m]$. This means that
$e_{5}^{\star}$ is a minimal vector, and
$\\{e_{1},e_{2},e_{3},e_{4},e_{5}^{\star}\\}$ is a primitive system of minimal
vectors, implying that $e_{5}$ is also minimal vector. Since
$\\{e_{1},e_{2},e_{3},e_{4},e_{5},e_{5}^{\star}\\}$ is also a basis then
$e_{6}$ is a minimal vector and we can apply Remark 1. Hence the absolute
values of the coordinates of $m$ are less or equal to $3$.

  * •

To end the discussion, assume that $\\{e_{1},\ldots,e_{4},m\\}$ is not a
primitive system and $|x_{6}|=4$. Then the parallelepiped
$\Pi[e_{1},\ldots,e_{4},m,e_{5}]$ has volume $4$. On the other hand let
$a_{5}$ be a sixth vector which lengths is the sixth successive minimum of the
lattice with respect to the system $\\{e_{1},\ldots,e_{4},m\\}$ of minimum
vectors. The volume of the parallelepiped $\Pi[e_{1},\ldots,e_{4},m,a_{5}]$ is
less or equal to 4, because its admissible centering is the lattice
$L[e_{1},\ldots,e_{6}]$.

    * –

If $\mathrm{vol}(\Pi[e_{1},\ldots,e_{4},m,a_{5}])=2$ and $e_{5}^{\star}$ is
centering the facet $\Pi[e_{1},\ldots,e_{4},m]$ then
$\\{e_{1},\ldots,e_{4},a_{5},e_{5}^{\star}\\}$ is a basis. If
$|e_{5}^{\star}|\leq|a_{5}|$ then $|a_{5}|\geq|e_{5}^{\star}|\geq|e_{5}|$
implying that $|a_{5}|=|e_{5}|$. Now $\\{e_{1},\ldots,e_{4},m,e_{5}\\}$ a
system of successive minimum vectors and so the centering of
$\Pi[e_{1},\ldots,e_{4},m,e_{5}]$ is the same as the admissible centering of
the cubic lattice with index $4$. But in this lattice there is no minimum
vector with coordinate $4$. This is a contradiction. So we have
$|e_{5}^{\star}|>|a_{5}|$ and so
$\\{e_{1},\ldots,e_{4},a_{5},e_{5}^{\star}\\}$ is an ordered basis. Hence
again $|a_{5}|=|e_{5}|$ leads to the same contradiction as above.

    * –

If $\mathrm{vol}(\Pi[e_{1},\ldots,e_{4},m,a_{5}])=4$ then the centering is
combinatorially agree with the centering of the $6$-dimensional cube with
index $4$. Hence there is a $4$-dimensional centered face by index $2$ which
contains $a_{5}$ as an edge vector. Denotes by $x$ the shortest half diagonal
of this face. Its length is smaller than the half-diagonal of a brick with the
same edge lengths and greater than the length of $a_{5}$. Thus
$|a_{5}|^{2}\leq|x|^{2}\leq 1/4(3+|a_{5}|^{2})$ so $|a_{5}|^{2}=1$ and the
successive minimum vector is in fact a minimum vector. The lattice
$L[e_{1},\ldots,e_{4},m,a_{5}]$ is the $6$-dimensional cubic lattice and
$L[e_{1},\ldots,e_{4},e_{5},e_{6}]$ is its admissible centering. In this
lattice the Minkowski reduced basis contains six minimal vectors and so we can
apply Remark 1, again.

$\Box$

## References

  * [1] Afflerbach, L.: Minkowskische Reduktionsbedingungen für positiv definite quadratische Formen in 5 Variablen Monatsh. Math. 94 (1982) 1–8.
  * [2] Afflerbach, L., Grothe, H.: Calculation of Minkowski-Reduced Lattice Bases Computing 35, (1985) 269–276.
  * [3] Agrell, E., Eriksson, T., Vardy, A., Zeger, K.: Closest point search in lattices. IEEE Transactions on Information Theory 48/8 (2002) 2201–2214.
  * [4] Beyer, W. A., Roof, R. B., Williamson, D. : The lattice structure of multiplicative congruential pseudo-random vectors. Math. Comput. 25 (1971) 345–360.
  * [5] Beyer, W. A. : Lattice structure and reduced bases of random vectors generated by linear recurrences. _In: Applications of Number Theory to Numerical Analysis (Zaremba, S. K., ed.)_ , (1972) 361–370.
  * [6] Csóka, G.: On an extrem property of bases reduced by Minkowski. (in Russian) Studia Sci. Math. 13 (1978) 469–475.
  * [7] Donaldson, J. L.: Minkowski Reduction of Integral Matrices MATHEMATICS OF COMPUTATION, 33/145 (1979) 201–216.
  * [8] G.Horváth, Á.: On $n$-dimensional lattice bases reduced by Minkowski and by Hermite (in Hungarian) Mat. Lapok  33 (1982-1986), 93–98.
  * [9] G.Horváth, Á.: On Dirichlet-Voronoi cell. {Part I. Classical problems} Per. Poly. ser Mech. Eng.  39. (1995), 25–42.
  * [10] G.Horváth, Á.: On the Dirichlet-Voronoi cells of unimodular lattices. Geometriae Dedicata 63 (1996), 183–191.
  * [11] G.Horváth, Á.: On Dirichlet-Voronoi cell. {Part II. Diagrams} Per. Poly. ser Mech. Eng. 41/2(1997), 95–117.
  * [12] Gruber P.M. and Lekkerkerker C.G.: Geometry of numbers Second Edition, North-Holland, (1987).
  * [13] Hermite, C.: Extraits de lettres de M. Hermite à M. Jacobi sur différents objets de la théorie des nombres, deuxième lettre. _J. für die reine und angewandte Mathematik_ 40, (1850) 279–290.
  * [14] Korkine, A., and Zolotarev, G.: Sur les formes quadratiques. Mathematische Annalen 6, (1873) 336–389.
  * [15] Lenstra, A. K., Lenstra, Jr., H. W., and Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261, (1982) 515–534.
  * [16] Minkowski, H.: Geometrie der Zahlen. Teubner-Verlag, (1896).
  * [17] Minkowski, H.: Sur la reduction des formes quadratiques positives quaternaries Ges. Abh. I 145–148.
  * [18] Nguyen, P.Q., Stehlé, D.: _Low-dimensional lattice basis reduction revisited_ In: Buell D. (eds) Algorithmic Number Theory. ANTS (2004). Lecture Notes in Computer Science, vol 3076. Springer, Berlin, Heidelberg. (2004). DOI: 10.1007/978-3-540-24847-7 26
  * [19] Nguyen, P.Q., Stehlé, D.: Low-dimensional lattice basis reduction revisited ACM Transactions on Algorithms 5/4 (2009) DOI: 10.1145/1597036.1597050
  * [20] Ryskov, S. S.: On the reduction theory of positive quadratic forms. (in Russian) Doklady Akademii Nauk 198/5, (1971) 1028–1031.
  * [21] Ryskov, S. S.: On Hermite, Minkowski and Venkov reduction of positive quadratic forms in n variables. (in Russian) Soviet Mathematics Doklady 13, (1972) 1676–1679.
  * [22] Ryskov, S. S.: The theory of Hermite-Minkowski reduction of positive definite quadratic forms. (in Russian) Zap. Naucn. Sem. Leningrad, Otdel. Mat. Inst. Steklov. (LOM) 33, (1973) 37–64.
  * [23] Ryskov, S. S.: On the problem of finding perfect quadratic forms in higher space. (in Russian) Trudy MIAN, SSSR 142, (1976) 215–239.
  * [24] Tammela, P. P.: The domain of the Hermite-Minkowski reduction of positive quadratic forms in dimension six. (in Russian) Zap. Naucs. Sem. LOMI 33 (1973) 72–89.
  * [25] Tammela, P.P.: On reduction theory of positive quadratic forms, (in Russian) Zap. Nauchn. Sem. LOMI, 50 (1975), 6–96.
  * [26] Tammela, P. P.: The minkowski reduction domain for positive quadratic forms of seven variables (in Russian) Zap. Naucn. Sem. Leningrad, Otdel. Mat. Inst. Steklov. (LOM) 67, (1977) 108–143.
  * [27] Zakharova, N.V.: Centerings of eight-dimensional lattices that preserves a frame of successive minima, Geometry of positive quadratic forms. Trudy MIAN, SSSR 152, (1980) 97–123, 237 (in Russian) Correction: Novikova N.V.: Three admissible centerings of eight-dimensional lattices, Deposited in VINITI No. 4842-81 Dep. (1981), I.8. (In Russian).
  * [28] Venkov, B. A.: On the reduction of positive quadratic forms. Izv. Akad. Nauk SSSR Ser. Mat. 4/1 (1940) 37–52.


# Rules in Play: On the Complexity of Routing Tables and Firewalls

M. Wahdwa, A. Pal, A. Shah, P. Mittal and H. B. Acharya
IIIT Delhi, India
<EMAIL_ADDRESS>
###### Abstract

A fundamental component of networking infrastructure is the _policy_ , used in
routing tables and firewalls. Accordingly, there has been extensive study of
policies. However, the theory of such policies indicates that the size of the
decision tree for a policy is very large ( $O((2n)^{d})$, where the policy has
$n$ rules and examines $d$ features of packets). If this was indeed the case,
the existing algorithms to detect anomalies, conflicts, and redundancies would
not be tractable for practical policies (say, $n=1000$ and $d=10$). In this
paper, we clear up this apparent paradox. Using the concept of “rules in
play,” we calculate the actual upper bound on the size of the decision tree,
and demonstrate how three other factors - narrow fields, singletons, and all-
matches \- make the problem tractable in practice. We also show how this
concept may be used to solve an open problem: pruning a policy to the minimum
possible number of rules, without changing its meaning.

##  I Introduction

Policies, such as routing and filtering policies (implemented in routing
tables and firewalls) are essential to the operation of networks. In current,
packet-switched networks, routers, switches and middleboxes examine incoming
packets, and decide (based on the relevant policy) what course of action to
pursue for each packet. Accordingly, fast packet _resolution_ , the operation
of checking which rule in the policy is applicable for the packet, is an
important area of research. A second important use of policies is in access
control lists, for firewalls and intrusion detection; as the security of the
system depends on the correctness of such a policy, policy _verification_ is
also an important problem. Algorithms for fast operation, design,
optimization, and verification of policies work on a decision diagram
representation of these policies; a good way to measure the complexity of a
policy is the size of its decision diagram.

However, the theory of policy decison diagrams comes with a major caveat. The
best known bound for the size of such a diagram is very large - specifically,
$(2n-1)^{d}$, where the policy has $n$ rules and the number of features of
interest (which we call ’fields’) is $d$. As $n$ is of the order of thousands
of rules, and $d$ can easily be $5-10$, it would seem that the complexity of
these algorithms is too large for practical cases. But this is not the case at
all - in fact, these algorithms are in common use to analyze policies and
entire networks [1]!

This paper solves this apparent paradox. We deepen the theory of policy
decision diagrams with the idea of keeping track of “rules in play,” which
allows us to determine a tight upper bound on the size of a decision diagram
and show why the size does not explode for practical policies. We also suggest
how this allows us to optimize policies, and obtain truly minimum (rather than
just minimal, i.e. with no redundant rules) policies.

We begin by providing our definitions and concepts, in the next section. Next,
we discuss decision diagrams and the algorithm to create them, as well as how
we modify it to keep track of rules in play. After this, we demonstrate how
there are mitigating factors - narrow fields, singletons, and all-matches -
that reduce the size of decision diagrams in practice. Finally, we provide our
experimental results, discuss how our paper fits into the context of related
work, and finish with some concluding remarks.

##  II Terms and Concepts

In this section, we define the terms and concepts used in the paper, such as
policies and properties, and formally introduce our concepts of _oneprob_ ,
_allprob_ , and _fieldwidth_. We will introduce decision diagrams and “rules-
in-play” in the next section.

###  II-A Packets, Rules, and Matching

In our work, we model a _packet_ as a $d$-tuple of non-negative integers. Why
this model? In order to decide what to do with a packet (whether to forward
it, which interface to forward it on, etc.), routers and firewalls examine its
various attributes - usually values in the packet header, such as source
address, destination address, source port, destination port, protocol, and so
on. (In ‘deep packet inspection’, attributes from the packet payload are also
checked.) The $d$ fields of our packet model represent the $d$ features
examined.

A _rule_ represents a single rule in a flow table. It consists of two parts: a
_predicate_ and a _decision_.

The rule predicate is of the form

$x_{1}\in[x_{1,1},x_{1,2}]\land x_{2}\in[x_{2,1},x_{2,2}]\ldots
x_{d}\in[x_{d,1},x_{d,2}]$

where each interval $[x_{k,1},x_{k,2}]$ is an interval of non negative
integers, drawn from the domain of field $k$. (For example, suppose the third
field in packets and rules represents source IP address. In IPv4, the domain
of this field is $[0,2^{32}-1]$. Then, in any rule, $0\leq x_{3,1}\leq
x_{3,2}\leq 2^{32}-1$.)

The decision is an action, such as (in a firewall) _accept_ or _discard_. [We
call a rule with decision _accept_ an “$accept$ rule”, and a rule with
decision _discard_ a “$discard$ rule”.]

A packet that satisfies the predicate of a rule is said to _match_ the rule.
For example, the packet $(1,26,7)$ clearly matches the rule

$x_{1}\in[0,108]\land x_{2}\in[21,65535]\land x_{3}\in[7,616]\to accept$

###  II-B Policies and Packet Resolution

A _policy_ consists of multiple rules (as defined in the previous subsection),
and a specification of which action to execute, in the event that multiple
rules match a given packet. There are two principal methods in use to decide
the precedence of matching rules.

  1. 1.

_First Match._ The rules are arranged in sequence in the policy, and the
action of the first rule in the sequence that is matched by a packet is the
action executed.

This is the method usually used in firewalls.

  2. 2.

_Best Match._ One specific field is chosen and, out of the rules matched by
the packet, the one with the smallest interval for this particular field has
precedence.

This is the method used in routing tables. The field chosen is the destination
IP, and this technique is called ’longest prefix matching’. (In routing
tables, IP address intervals are usually denoted by prefixes, e.g.,
$100.150.200.0-100.150.200.255$, which is really the interval
$[1687603200,1687603455]$, is written $100.150.200.0/24$. Thus the best match
is by the rule which had the longest prefix out of the rules matched by the
packet.)

The practical order of deciding precedence in a router is quite complicated.
In short,

  1. 1.

First, find the best match.

  2. 2.

In case of conflict, choose rules in the order:

    1. (a)

Static routes

    2. (b)

Dynamic routes, in order
(usually EIGRP, OSPF, ISIS, RIP)

    3. (c)

Default route

  3. 3.

If no rule matches, discard the packet.

However, this entire procedure can be effectively reduced to first match,
simply by ordering the rules! (The primary sort key in this ordering is the
specified prefix length, and the secondary sort key, the type of rule.) Hence,
in our work, we assume first match semantics for policies.

The ‘winning’ rule, the decision of which is implemented for a packet, is said
to _resolve_ the packet.

###  II-C OneProb, AllProb, and FieldWidth

In policy research, the complexity of a policy is considered to be affected by
two principal factors. The first is $n$, the number of rules in the policy,
which can be up to several thousand; the other is $d$, the number of fields in
a rule, which is usually around $5-10$. For example, the complexity of the
simple standard algorithm for resolution - check, for each of $d$ fields of
the packet, that the value falls in the interval specified by the rule; repeat
until a rule is matched - is clearly $O(nd)$.

However, we contend that this is not sufficient information to predict the
complexity of a policy. There are two other metrics of interest.

The first observation is that, in practice, rules are almost always targeted
to very specific uses; as a result, many of their fields are set to either a
single specific value, or to “All” - i.e. the entire domain of the field. (For
example, firewalls built using Structured Firewall Design[2] have many fields
set to All.) As demonstrated in earlier work[3], policies where high
proportions of fields are set to single values, or to All, show significantly
different behavior than other policies with the same values of $n$ and $d$. To
capture this, we use the metrics $allprob$ and $oneprob$.

$allprob$ is the probability that, on randomly choosing a field and a rule in
the policy, the interval specified by the rule for the field is “All”.

$oneprob$ is the probability that the interval specified by a randomly chosen
rule for a randomly chosen field, is a single value, such as $[6,6]$.

The second observation is that the domains of different fields are of very
different sizes. For example, IPv4 addresses take $32$ bits, protocol takes
$8$ bits, and version takes $4$ bits in a standard header. We use the metric
of $fieldwidth$ to measure narrow fields (whose domain is expressed in a small
number of bits); it is the total number of bits needed to express all narrow
fields in the policy. The reason for introducing a new metric is that narrow
and wide fields have different effects on the complexity of a policy. We
provide details in Section V.

##  III Decision Diagrams

In this section, we describe how policies can be represented using Decision
Diagrams, as proposed by Gouda [2].

A decision diagram (over fields $f_{1}..f_{d}$) is an acyclic, rooted digraph.
Every _terminal_ node, i.e. one with no outgoing edges, is marked with a
decision (for example, in case of firewalls, decisions are _accept_ or
_discard_). Every non-terminal node is marked with the name of a field, and
has outgoing edges marked with an interval of values for its field; values
marked on the edges from a node do not overlap.

There is at least one directed path from the root to every other node, and no
directed path has more than one node labeled with the same field. Thus, a
decision diagram represents a simple deterministic finite automaton. Given any
packet $p=(p.f_{1},..p.f_{d})$, there is exactly one path from the root
corresponding to the field values of $p$, and it terminates in a terminal
node; the decision at this node is the decision of the policy for $p$.

We consider the decision diagram in its fully expanded form, as a tree. In our
example, the root is labeled $f_{1}$, its children are $f_{2}$, down to
$f_{d}$, whose children are the leaf i.e. terminal nodes.

To resolve a packet, we follow a path from the root down to a leaf node, at
each node choosing the edge matched by the packet - i.e., labeled with the
interval containing the value of the corresponding field for the packet. Given
a policy with $n$ rules of $d$ fields, a decision diagram performs packet
resolution in $O(d)$ time. Policy verification has the same time complexity as
the size of the diagram. (It is essential to check the decision corresponding
to packets that match the property; in the worst case , the property specifies
all possible packets, and it is necessary to check paths from the root to
every terminal node.)

We now extend the algorithm to construct decision diagrams, by introducing the
concept of _rules in play_. A rule $R$ of a policy is “in play” at a node if
at least one packet matching $R$ follows a path through the node when it is
resolved. $R$ is in play at an edge if it is in play at the node into which
the edge leads. Annotating the nodes with the rules in play requires only
slight modification to the algorithm for building a decision diagram; we
present the algorithm in Figure 1. In Figure 2, we show an example, building
an annotated decision diagram from the policy

$\displaystyle x\in[10,110]\land y\in[90,190]\to 0$ $\displaystyle
x\in[20,120]\land y\in[80,180]\to 1$

For our first demonstration of how rules in play can be useful, we demonstrate
how, given a policy, we can use the rules in play at the leaf nodes, and find
a $minimum$ equivalent policy (equivalent policies have the same decision for
every packet). We delete rules, without changing the decision of the policy
for the packets reaching any leaf node. (As we are not adding rules, there
will be no new paths or new leaves to consider.)

Consider a leaf node with the $accept$ rules $3,13$ and the $discard$ rule $7$
in play. So long as rule $3$ remains, deleting other rules does not affect the
decision at this leaf. What if we delete rule $3$? We must delete rule $7$ (so
it does not become the first rule to match these packets), and keep rule $13$.
Using $x_{i}$ to mean that rule $i$ is present, we must satisfy

$x_{3}\lor(\lnot x_{7}\land(x_{13}))$

We can apply this logic recursively: if we had $accept$ rules $3$, $13$ and
$23$, and $discard$ rules $7$, $10$ and $17$, then

$x_{3}\lor(\lnot x_{7}\land(\lnot x_{10}\land(x_{13}\lor(\lnot
x_{17}\land(x_{23})))))$

must be satisfied, to preserve the policy decision at this leaf.

  1. 1.

At a leaf node, we start with the first rule in play. All other rules with the
same decision are _complying_ rules, and the others are _conflicting_ rules.

  2. 2.

We traverse the list of rules in play, in order, building an expression
(string).

  3. 3.

If the rule $R_{i}$ is complying, we add “$x_{i}\lor($”. If it is conflicting,
we add “$\lnot x_{i}\land($”.

  4. 4.

At the end, we close all parentheses.

Taking the AND of the expressions for all the leaf nodes, we get an expression
which must be satisfied to keep the decision of the policy unchanged for all
packets.

To find the minimum policy, we create our expression for the original policy
(as described above), and search for the solution with the smallest number of
$x_{i}$ set to $1$ \- a Min-One SAT problem. This gives us the smallest
combination of the rules in the policy that preserve its semantics for all
packets, a minimum policy (rather than the minimal policies obtained by
trimming as many redundant rules as possible). So far, this algorithm is too
slow to be practical for policies of more than $50$ rules; however, we expect
optimizing the solver will make it fast enough for real use. We will develop
this further in future work.

In the next two sections, we show how, by keeping track of rules in play, we
can prove that decision diagrams do not grow exponentially large in practice.

Figure 1: Building annotated decision diagram from policy

procedure AddnewRule(Rule $R$, name $R.name$, node $x$)

Add $R.name$ to list of rules in play at $x$

if $x$ is a terminal node then

Label $x$ with the decision of $R$.

else

$i$ is the field of node $x$.

$R.i$ is the interval for field $i$ in $R$.

$x.i_{1},x.i_{2}..$ are the values on the edges from node $x$.

Build new paths from $x$, starting with new outgoing edges labeled with the
intervals in $R.i-\\{x.i_{1},x.i_{2}..\\}$. $\triangleright$ To each edge, add
new nodes and edge labels as per remaining fields in $R$. The terminal node
has decision of $R$. These nodes start with only one rule in play, i.e.
$R.name$.

for all labels $x.i_{k}$ do

if $x.i_{k}\cap R.i$ is empty then

continue

else

$y$ is the target of edge labeled $x.i_{k}$.

for every interval $x.i_{new}\in x.i_{k}-R.i$ do

Copy (subgraph rooted at $y$ ).

$y^{\prime}$ is the new copy of $y$ itself.

Add edge $x\to y^{\prime}$, labeled $x.i_{new}$.

end for

Relabel edge $x\to y$ with $x.i_{k}\cap R.i$.

$AddNewRule(R,R.name,y)$

end if

end for

end if

end procedure

procedure BuildDDiagram(Policy $\\{R_{1},R_{2}..R_{n}\\}$)

Create empty node $x$ with no outgoing edges.

Label $x$ with desired field for root.

for $index\leftarrow n...1,$ step $-1$ do

$AddNewRule(R_{index},index,x)$

end for

return Decision Diagram rooted at $x$.

end procedure

Figure 2: Example: building a decision diagram, step by step.

|
---|---
|
|
|

(a)

(b)

Step $1$. First rule from bottom, i.e. rule $2$

(c)

Step $2$. Adding $f_{1}$ from next rule, rule $1$.

(d)

(e)

(f)

Step $3$. Adding $f_{2}$ from rule $1$.

(g)

Step $4$. Adding decision from rule $1$.

(h)

##  IV The Size of Decision Diagrams

In this section, we determine the worst case size of a policy decision
diagram, measured as the number of leaf nodes of the diagram. We begin with
the existing upper bound.

The intuition behind the bound is that, as the decision diagram is a tree of
fixed depth, its size can be maximized by making the branching factor of each
node as large as possible.

As there are $n$ rules in the policy, there can be a maximum of $2n-1$
outgoing edges for a node. (Each edge must be labeled with at least one
interval. The $n$ rules have $2n$ end points - each interval has a start and
an end. These $2n$ end points thus divide the domain into a maximum of $2n-1$
intervals. Hence we can have at most $2n-1$ edges from a node.)

Thus, an upper bound on the size of the decision diagram for a policy of $n$
rules and $d$ fields is $(2n-1)^{d}$.

Our construction, which is mindful of rules in play, allows us to tighten this
bound considerably. The intuition behind this is that, while a node with $n$
rules in play can indeed have a branching factor of $(2n-1)$, as seen above,
not all these branches still have $n$ rules in play! In fact, of the outgoing
edges, exactly _one_ edge still has all $n$ rules in play (the one
corresponding to the intersection of all the rules). There are also edges with
$n-1$ rules in play, $n-2$ rules in play, and so on, down to edges with $1$
rule in play. In our example from Figure 2, consider the edges emerging from
the root: edge $(10,19)$ has only one rule in play (the first), edge
$(20,110)$ has both rules in play, and edge $(111,120)$ has only one rule in
play (the second).

So, in order to construct the largest decision diagram, there are two factors
to maximize:

  1. 1.

The number of branches, i.e. the branching factor at each node

  2. 2.

The number of rules in play along each branch.

In fact, in the largest possible decision diagram for a given $n$ and $d$, the
pattern is that one outgoing edge has $n$ rules in play, two have $n-1$, two
have $n-2$, and so on, down to the last two edges which have a single rule in
play. This is a dynamic programming problem: given the largest decision
diagrams that can be built with $1,2...n$ rules in play, at a depth $d-1$, we
can compute the size of the largest decision diagram with depth $d$, and $n$
rules in play. We also have the following observations.

  1. 1.

For any $d$, when $n=1$, the number of leaves is $1$. (Only a single rule is
in play, so there is no branching.)

  2. 2.

$d=0$ indicates we are at a leaf node, so the size is $1$.

  3. 3.

When $d=1$, and the number of rules in play is $n$, then the size of the
decision diagram (measured by number of leaves) is $2n-1$.

Stating this result formally,

######  Theorem 1.

If we represent the maximum size (measured by number of leaf nodes) of a
decision diagram with $n$ rules and $d$ fields as $f(n,d)$,

$\displaystyle f(n,d)$
$\displaystyle=2\sum\limits_{i=1}^{n-1}f(i,d-1)+f(n,d-1)$ for $n>1,d>1$
$\displaystyle f(n,1)$ $\displaystyle=2n-1$ $\displaystyle f(1,d)$
$\displaystyle=1$

Next, we need to prove that this intuitively appealing construction ( all $n$
rules overlapping for one central edge, and rules “falling off” one by one to
either side) is in fact the largest possible decision diagram for a given $n$
and $d$. Our proof is as follows.

Consider any decision diagram. It forms a tree, in which every non-leaf node
represents a field. Every edge is labeled with an interval (of values for the
field represented by the node it starts from), and associated with a list of
rules in play at that edge.

We consider how, in constructing the old bound, we maximize the branching
factor at a node. Every rule $R_{i}$ has a range $[start_{i},end_{i}]$; these
end points ($start_{i}$ and $end_{i}$) segment the domain space into
intervals. $n$ rules introduce $2n$ end points, and each point added has the
potential to create a new edge. (The set of rules in play is different before
and after an end point.) To maximize the number of edges, we assume that no
two end points coincide; this gives us $2n-1$ as the number of outgoing edges
from a node.

Now, we extend this argument. We will abuse the variable names $n$ and $d$. In
general, we now use $n$ to mean the number of rules in play at a node (or an
edge) ; the original meaning of $n$, the number of rules in the policy, is the
$n$ seen at the root. Similarly, we use $d$ to mean the depth of the subtree
rooted at a node; the original meaning of $d$, the number of fields, is the
$d$ seen at the root. Clearly, $f(n,d)$ increases monotonically with $n$ and
with $d$.

Let us arrange the outgoing edges from a node in ascending order of the values
of their labels (intervals). [As these intervals are non overlapping, we can
sort them by their start, i.e. smallest values, or by end, i.e. largest values
- the order will be the same.] Two edges are said to be _adjacent_ if there
exists no edge whose label (interval) lies in between their labels.

######  Lemma.

In the largest decision diagram for a given $n$ and $d$, the sets of rules in
play on adjacent edges differ by one rule exactly.

_Proof._ Let the rulesets on two adjacent edges be $A$ and $B$.

Let $A=X+Y$ and $B=Y+Z$.

If $X$ and $Z$ are both non-null, then by increasing the $end_{i}$ of rules in
$X$, by $1$ (or reducing the $start_{i}$ of rules in $Y$, by $1$) we can add a
new edge with the ruleset $X+Y+Z$ in between these edges.

This edge could not already exist. (Let the field be named $f_{1}$. Without
loss of generality, assume $f_{1}$ increases going from $A$ to $B$. The labels
of rules are intervals - they start once and stop once exactly. $X$ appears on
no edge with greater $f_{1}$ than edge labeled $A$, and $Z$ on no edge with
less $f_{1}$ than edge labeled $B$. So the edge with $X+Y+Z$ could not have
been at some other position.)

Also, adding this edge does not affect the rest of the diagram (for $f_{1}$,
the other edges have different values, and are not affected; the other fields
are not touched at all). Adding this new edge clearly increases the decision
diagram size. But this is the _largest_ decision diagram for this $n$ and $d$,
so we have a contradiction.

Now, we have proved that either $X$ or $Z$ is the null set. Without loss of
generality, let us assume that $X$ was null.

Can $Z$ also be a null set? This is not possible, because then $A==B$! The
edges labelled $A$ and $B$ would be merged to form a single edge.

On the other hand, can $Z$ contain more than $1$ rule?

In this case, $Z=Z_{1}+Z_{2}$, where $Z_{1}$ has one rule and $Z_{2}$ is non-
empty. The $start_{i}$ of rules in $Z_{1}$ and $Z_{2}$ coincide.

If we had a decision diagram where all else is the same, but these rules did
not share the same $start_{i}$, we would have an extra edge labeled with
$Y+Z_{1}$ between these two edges. But this is the largest possible decision
diagram for given $n$ and $d$, so again we have a contradiction.

Hence, one of $A-B$ or $B-A$ is the null set, and the other has exactly one
rule. This suffices to prove our lemma. ∎

Next, we consider the first edge (i.e. the one with the smallest $start_{i}$.
This edge has only one rule in play; if it had more, by a similar construction
as above, we could add a preceding edge. Now the next edge can have at most
two rules in play, and if we continue to count up, we eventually reach $n$
rules in play. After we reach $n$ rules, on the next edge we can only have
$n-1$ rules in play, and so on.

To complete our proof that the largest decision diagram indeed follows this
structure, we introduce the idea of “closed” rules. At every edge, besides the
number of rules in play, we can keep count of $n^{\prime}$, the number of
rules for which we have already exceeded the $end_{i}$. These rules can
therefore not come into play at a later edge \- they are used up. In our
running example, consider the last edge $[111,120]$ coming out of the root;
this edge has the second rule in play, and the first rule closed.

Suppose we characterize decision diagrams, for a given $n$ and $d$, by drawing
a plot, showing the number of rules in play on an edge vs. the position of the
edge (first edge is the one with smallest $start_{i}$, etc.) We know that, for
the largest decision diagram, adjacent $y$-values differ by exactly $1$. Given
the monotonic nature of $f$, clearly, if the figure for decision diagram $D1$
is enclosed within the figure for another decision diagram $D2$, then $D2$ is
larger than $D1$.

Our construction produces a symmetric triangle sloping from $1$ up to $n$ and
from $n$ back down to $1$. It is easy to see that, for the rising half, the
plot for the largest decision diagram is contained within this triangle; it
increases the number of rules in play as quickly as possible. However, it is
not so obvious that this condition also holds for the second (falling) half
(because our construction also grows the number of closed rules as slowly as
possible). Could there be a larger decision diagram whose plot “breaks out”
from the triangle? The two plots must intersect, so suppose it intersects the
falling half after $k_{o}$ rules have been brought into play and $k_{c}$ rules
have been closed,

$\displaystyle k_{o}+k_{c}=k$ $\displaystyle k_{o}-k_{c}=2n-k$ $\displaystyle
k_{c}\leq k_{o}\leq n$

which reduces to $k_{o}=n,k_{c}=0$, i.e. the only plot that satisfies the
given constraints is our original construction.

This concludes our proof that the largest decision diagram for a given $n$ and
$d$ indeed follows the pattern where edges have $1,2...n-1,n,n-1,...2,1$ rules
in play. Our bound is tight: the following policy has exactly this decision
diagram, and hence, matches the size of this upper bound.

$\displaystyle x_{1}\in[1,2n-1]\land...\land x_{d}\in[1,2n-1]\to accept$
$\displaystyle x_{1}\in[2,2n-2]\land...\land x_{d}\in[2,2n-2]\to discard$
$\displaystyle...$ $\displaystyle x_{1}\in[n,n]\land...x_{d}\in[n,n]\to
discard$

##  V Size in real Decision Diagrams

In the previous section, we present our new bound for the size of decision
diagrams. This bound is much smaller than the old bound of $(2n-1)^{d}$; for
example, for $n=1000$ and $d=10$,

$f(n,d)=2.808\times 10^{26}<<(2n-1)^{d}=1.019\times 10^{33}$

. However, this bound, though tight, is still quite large. In this section, we
answer the question of why, in practice, decision diagrams do not grow
intractably large. The answer makes use of our concepts of oneprob, allprob,
and narrow fields.

###  V-A OneProb and Singletons

In constructing a decision diagram, we have two main operations that increase
its size. One is adding a new path; this happens when the new rule specifies
new values for a field, i.e. values for which no outgoing edges exist. The
other operation is when the interval specified by the rule only partly
overlaps with the label of an edge; in this case, we ‘split’ the edge and make
copies of the subgraph below. (In our example, the rule has $x\in[10,110]$ and
the old edge has $x\in[20,120]$. As they partially overlap, we get new edges
labeled $x\in[10,19]$, $x\in[20,110]$, and $x\in[111,120]$.)

Now we consider the impact of _singletons_. A rule is called a singleton for
field $x$ if matches only packets with one single value of $x$, i.e. its
interval for $x$ is a single value like $[29,29]$.

Clearly, singletons cannot have partial overlap with any other rule. As a
consequence, an edge (from a node labeled $x$) with a singleton (for $x$)
cannot be split! This leads immediately to the observation that if all the
rules are singletons, the maximum branching factor at a node is not $2n-1$,
but $n$ (when all the singletons have different values for $x$, and thus
produce different branches). However, this attractive idea is limited in its
power: as soon as we introduce a single non-singleton rule $R^{\prime}$, we
are back to $2n-1$. [The worst case is when all $n-1$ singletons split
$R^{\prime}$, cutting up its interval into $n-1+1=n$ parts in between them.
Now we have $n-1$ edges with two rules in play ($R^{\prime}$ and one of the
singletons), and $n$ edges with only $R^{\prime}$ in play, so $2n-1$ edges in
all. For example, consider rules with intervals $[1,10]$, $[3,3]$ and $[7,7]$;
we have $2\times 3-1=5$ edges, labeled with $[1,2]$, $[3,3]$, $[4,6]$,
$[7,7]$, and $[8,10]$. ]

To make a stronger argument, we consider the number of rules in play along an
edge.

When we have mutliple singletons for a field, there are two choices. They
either overlap completely, or they do not overlap at all. If they do not
overlap, this increases the branching factor at the node (more outgoing
edges). But this means the number of rules in play along those edges (and
therefore, at the nodes the next layer down) is reduced! For the largest
decision diagram, we need to trade off the “immediate” branching factor at the
node and the “potential” for more branching at lower levels. The solution is
only obvious at nodes where $d=1$, as the only lower level is the leaf nodes
(i.e. no more branching is possible at lower levels); in the largest decision
diagram, all singletons of the field where $d=1$ have distinct values.

Singletons increase the size of the decision diagram most effectively if they
intersect the interval with the largest possible number of rules in play.
Consider the diagram made with the non-singleton rules; the edges follow the
standard pattern, with $1,2...n,n-1,...1$ rules in play. Now we introduce a
singleton. If it splits an edge with $r$ rules in play, we replace one edge
with $x$ rules with two edges with $r$ rules (before and after the singleton),
plus one edge with $r+1$ rules (where the $r$ rules and the singleton
overlap). If on the other hand, the singleton did not split any edge, it would
introduce only one new edge with a single rule in play (the singleton).
Clearly, the maximum is when $r=n$.

How are we to proceed when introducing more singletons? This is not
straightforward. Let us assume that the number of singletons is $s$, the
number of non singletons is $t$, and the depth of the tree (below the node we
are considering) is, as usual, $d$. Then to find the size of the largest
decision diagram, we try all the partitions of $s$ singletons; for example, if
$s=4$, we need to try $1+1+1+1,1+2+1,1+3,2+2$, and $4$. Then, using $g(s+t,d)$
as the formula for maximum size, and $a$ as the number of pieces in the
partition $\\{s_{1},s_{2},...s_{a}\\}$,

$\displaystyle g(n,d)=$ $\displaystyle 2\sum\limits_{i=1}^{t-1}f(i,d-1)$
$\displaystyle+max\Big{[}(a+1)g(t,d-1)$
$\displaystyle+\sum\limits_{j=1}^{a}g(t+s_{j},d-1)\Big{]}$ $\displaystyle n=$
$\displaystyle s+t$

where the max is taken over all partitions.

There is a small gap in this argument, which we now explain. How do we know
the largest decision diagram is produced by adding singletons to the largest
diagram without singletons? The reason is the monotonicity of the size
function. With or without singletons, a diagram with more edges and more rules
in play along an edge is larger. [It is also of interest to note that a rule
being a singleton for one field does not mean it is a singleton for the fields
at lower levels! Counted as a rule in play, it is just as powerful as any
other rule.] The largest diagram to begin with, also produces the largest
increases: other structures also grow fastest by adding singletons that split
the edge with the most rules in play, and they cannot have edges with more
than $t$ rules in play. For example, consider two diagrams with the number of
rules-in-play, $(1,2,1,2,1)$ and $(1,2,3,2,1)$. If we now add two singletons,
the first will yield a diagram with the maximum size

$3g(1,d)+g(2,d)+max\big{(}g(4,d)+2g(2,d),2g(3,d)+3g(2,d)\big{)}$

and the second,

$2g(1,d)+2g(2,d)+max\big{(}g(5,d)+2g(3,d),2g(4,d)+3g(3,d)\big{)}$

which is clearly larger.

The probability that a rule is a singleton is given by $oneprob$, so our
intuition is that a high value of $oneprob$ leads to a smaller decision
diagram. One point that we have not highlighted, is that singletons are also
much less likely to overlap than other rules are; as our focus is on the worst
case, we could not make use of this factor, but it most likely also plays a
role in the tractable size of practical decision diagrams.

###  V-B AllProb and All-Matches

The behavior of _all-matches_ , that is, rules that match all values for a
given field, is much less complicated. At a given node, there is no choice
about where to place the all-matches; they cover the entire domain for the
field. So the all-matches all behave like one single large rule, which adds
$u$ (the number of all-match rules) to the number of rules in play on each
edge. We can update the formula for largest decision diagram as follows.

$\displaystyle g(n,d)=$ $\displaystyle 2\sum\limits_{i=0}^{t-1}f(i+u,d-1)$
$\displaystyle+max\Big{[}(a+1)g(t+u,d-1)$
$\displaystyle+\sum\limits_{j=1}^{a}g(t+s_{j}+u,d-1)\Big{]}$ $\displaystyle
n=$ $\displaystyle s+t+u$

where, again, $a$ is the number of pieces the singletons are partitioned into,
and the max is taken over all such partitions.

The probability that a rule is an all-match is given by $allprob$. An
intuitive way to explain of the effect of all-matches is that, when $allprob$
grows sufficiently large, as most of the rules have total (rather than
partial) overlap, the size of the decision diagram is reduced. In fact, in the
extreme case of $allprob=100$, the decision diagram is a linked list (from the
root to the decision of the first rule, which resolves all packets).

###  V-C Narrow Fields

Our construction of decision diagrams follows an implicit assumption. When we
state that the outgoing edges from a node can carve the domain into $2n-1$
pieces, etc., we assume that the domain is large enough to divide into so many
distinct pieces.

However, this assumption is not true for some domains. These are the ones we
call _narrow_ fields.

Clearly, if a field is represented with $w$ bits, the greatest possible number
of outgoing edges is upper bounded by $2^{w}$. [Every possible value of the
field labels a distinct edge.] We can extend this argument by placing all the
narrow fields together, as the fields closest to the leaves (i.e. with
$d=1,2...d_{narrow}$. Suppose $fieldwidth=W$ bits, i.e. the narrow fields can
all be represented using $W$ bits. Our computation for the size of the
decision diagram does not change for the non-narrow fields; however, the
“leaf” nodes for this tree are now the roots of decision trees for the narrow
fields, which expand to $2^{W}$ bits each. So we can simply compute the size
for the non-narrow bits, and multiply the result by $2^{W}$ to get an upper
bound on the size. This idea is similar to the automata size bound of Erradi
[4].

$\displaystyle g(n,d)=$ $\displaystyle 2\sum\limits_{i=0}^{t-1}f(i+u,d-1)$
$\displaystyle+max\Big{[}(a+1)g(t+u,d-1)$
$\displaystyle+\sum\limits_{j=1}^{a}g(t+s_{j}+u,d-1)\Big{]}$ $\displaystyle
n=$ $\displaystyle s+t+u$

for $d>d_{narrow}$, the number of narrow fields, and

$\displaystyle g(n,d)=$ $\displaystyle g(n,d-1)*2^{w_{d}}$

otherwise. ($w_{d}$ = bit width of field at height $d$.)

However, this is no longer a _strict_ upper bound. The reason is that, if we
do organize the decision diagram with wide fields closer to the root and
narrow fields closer to the leaves, some of the edges from the upper nodes to
the lower nodes have a very small number of rules in play - $1$, $2$ etc.
Clearly, for these edges, the lower nodes are no longer “narrow” fields, as
the bound of $2n-1$ is again smaller than $2^{w}$.

Though this bound is no longer tight, in the presence of narrow fields, it
also serves to reduce the size of the decision diagram considerably. We
present our experimental results in the next section.

##  VI Results

This section describes our experimental verification of the size bounds for
decision diagrams. In Figure 3, we demonstrate the effect of the mitigating
factors, on practical policies with $n=100,200...1000$ rules and $d=5$ fields.
We show that the effect of the factors compounds together, by showing the
original bound $f(n,d)$, then $g(n,d)$, the bound in presence of these
factors, introducing first $allprob$, then narrow fields, and finally
$oneprob$.

As the maximum size in the presence of singletons requires us to compute and
check all partitions - an exponential number - we do not compute the bound for
such large $n$; we provide the impact of $oneprob$ for $n=10,20...100$. [The
other plots were similar in shape for $n=10,20...100$ and $n=100,200...1000$.]
We also checked that these bounds are in fact correct by generating decision
diagrams for a large number of policies (a total of approx. two million); the
bounds were never exceeded.

Figure 3: Performance of size bounds for Decision Diagrams

(a) First bound: smaller than $(2n-1)^{d}$

(b) Effect of $allprob$. (Top to bottom, $0,20,40,60,80$.)

(c) Effect of narrow fields. $allprob=40$. (Lines, top to bottom, $5$ wide
fields; $4$ wide + $1$ narrow; and $3$ wide + $2$ narrow. Narrow fields $2$
bits wide.)

(d) Effect of $oneprob$. (Top to bottom, $0,20,40,60$.) $allprob=40$, $4$ wide
+ $1$ narrow field.

##  VII Related Work

Owing to the practical importance of policies, there exists a considerable
body of work devoted to their study. A natural question is how this paper fits
into the context of this research.

The first and most obvious area related to our work is the theory of policies.
This area includes the design of algorithms and data structures for fast
packet processing (i.e. resolution) as well as for verification of policies.
Policies have been represented as tries [5] and lookup-tables by Waldvogel [6]
and Gupta [7]. As preprocessing can be expensive, solutions have been
developed by Suri[8] using B-trees, and by Sahni and Kim[9] using red-black
trees and skip lists; these solutions allow fast update, and also perform
(longest prefix) matching in $O(\log n)$ time.

Our work not only advances the theory of policies by providing an exact bound
on the size of the policy decision diagram [2], but also proposes new metrics
for the complexity of a policy, and shows why the algorithms for fast
resolution and verification are tractable in practice. Our new metrics
(fieldwidth, allprob and oneprob) make it possible to answer if a policy will
have a decision diagram of tractable size.

More generally, the analysis of policies includes the study of anomalies [10],
inter-rule conflicts [11], redundancies, and so on. For example, Frantzen [12]
provides a framework for understanding the vulnerabilities in a firewall, and
Blowtorch [13] is a framework to generate packets for testing. These
algorithms depend on the complexity of a policy, as measured by the size of
its decision diagram; our work sheds light on why they are practical to use.

Finally, our work impacts the study of high-performance architecture for fast
packet resolution. High-throughput systems, such as backbone routers, make use
of special hardware - ternary content addressable memory[14], ordinary RAM,
pipelining systems [15], and so on. But these systems are very expensive, as
well as limited in the size of policies they can accommodate. Therefore, there
is active research on algorithms to optimize policies, such as Liu’s TCAM
Razor[14]. This paper shows how, using our concept of rules in play, we can
improve upon these algorithms to create truly minimum policies (rather than
just locally minimal ones).

##  VIII Concluding Remarks

In this paper, we make two contributions to the theory of policies and their
complexity. Our first contribution is to introduce the concept of “rules in
play”, which enables us to calculate the actual upper bound on the size of the
policy decision diagram. We also show why this size does not grow explosively
for practical policies, and introduce new metrics for the complexity of a
policy. These metrics (oneprob, allprob and fieldwidth) are not only simple to
compute (one pass through the policy, $O(nd)$ time), but also have a dramatic
effect on the behavior of policy algorithms. Thus, our work provides an
explanation for the “unreasonable effectiveness” of practical decision diagram
based algorithms: their running time is not really $O(n^{d})$, but depends on
our new metrics also, and practical policies have tractable values for these
new metrics.

Our second contribution is that, using rules in play, we propose the first
optimization algorithm that can produce a truly minimum-length policy (rather
than simply a minimal one, as can be found by removing redundant rules from
the policy until no redundancy remains).

Our work on decision diagrams suggests several problems for further study. How
do our metrics influence other measures of complexity, such as how many rules
the average rule in a policy overlaps with? Can they be further refined (for
example, by taking the oneprob and allprob field by field, rather than one
measure for the whole policy)? And how do they influence other algorithms and
data structures in policy research, such as decision-diagram compression by
Bit Weaving [16]? For our own future work, we are focusing on the last of
these questions. We also aim to improve our new algorithm for policy
optimization, so as to make it fast enough for practical use.

## References

  * [1] E. Al-shaer, W. Marrero, A. El-atawy, and K. Elbadawi, “Network configuration in a box: Towards end-to-end verification of network reachability and security,” 2009.
  * [2] A. X. Liu and M. G. Gouda, “Firewall policy queries,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 20, no. 6, pp. 766–777, 2009.
  * [3] H. B. Acharya, “On rule width and the unreasonable effectiveness of policy verification,” in _IEEE 39th Conference on Local Computer Networks, LCN 2014, Edmonton, AB, Canada, 8-11 September, 2014_ , 2014, pp. 314–321.
  * [4] A. Khoumsi, W. Krombi, and M. Erradi, “A formal approach to verify completeness and detect anomalies in firewall security policies,” in _Foundations and Practice of Security_ , 2014, pp. 221–236.
  * [5] K. Sklower, “A tree-based routing table for berkeley unix,” in _Technical report, University of California_ , 1993.
  * [6] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable high speed ip routing lookups,” in _Proceedings of ACM SIGCOMM_ , 1997, p. 25–36.
  * [7] P. Gupta, S. Lin, and N. McKeown, “Routing lookups in hardware at memory access speeds,” in _Proceedings of IEEE INFOCOM_ , 1998.
  * [8] S. Suri, G. Varghese, and P. Warkhede, “Multiway range trees: Scalable ip lookup with fast updates,” in _GLOBECOM_ , 2001.
  * [9] S. Sahni and K. Kim, “O(log n) dynamic packet routing,” in _IEEE Symposium on Computers and Communications_ , 2002.
  * [10] H. H. Hamed, E. S. Al-Shaer, and W. Marrero, “Modeling and verification of ipsec and vpn security policies,” in _ICNP_ , 2005, pp. 259–278.
  * [11] D. Eppstein and S. Muthukrishnan, “Internet packet filter management and rectangle geometry,” in _SODA_ , 2001, pp. 827–835.
  * [12] M. Frantzen, F. Kerschbaum, E. E. Schultz, and S. Fahmy, “A framework for understanding vulnerabilities in firewalls using a dataflow model of firewall internals,” _Computers & Security_, vol. 20, no. 3, pp. 263–270, 2001\.
  * [13] D. Hoffman and K. Yoo, “Blowtorch: a framework for firewall test automation,” in _Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering_ , 2005, pp. 96–103.
  * [14] D. Shah and P. Gupta, “Fast updating algorithms for tcams,” _IEEE MICRO_ , vol. 21, no. 1, p. 36–47, 2001.
  * [15] A. Basu and G. Narlika, “Fast incremental updates for pipelined forwarding engines,” in _Proceedings of IEEE INFOCOM_ , 2003.
  * [16] C. R. Meiners, A. X. Liu, and E. Torng, “Bit weaving: A non-prefix approach to compressing packet classifiers in tcams,” _IEEE/ACM Trans. Netw._ , vol. 20, no. 2, pp. 488–500, 2012.