Linear diophantine equations and applications

Zusammenfassung

Motivation, theoretic and software development The resolution of systems of linear Diophantine equations is a well known complex problem with many applications. In this work we are concerned with the computation of the integer non-negative solutions of this kind of systems. Let $A$ be a matrix with integer entries. The set of nonnegative integer solutions of $Ax=0$ is a submonoid, $M$, of $\N^k$, where $k$ is the number of unknowns of the system. Minimal nonzero elements of $M$ with respect to the usual partial ordering can be used to compute every other element of this set; these are usually named the generators of $M$. These minimal elements are a Hilbert basis of $M$. Computing the non-negative integer solutions of a system of linear Diophantine equations is thus equivalent to the computation of the Hilbert basis (see for instance \cite{Pottier_MinimalSolutions}) for $M$. Knowing if a system of linear Diophantine equations has or not any solution is a $\mathrm{NP}$-complete problem. However a series of significant methods have progressively appeared in the literature offering responses at reasonable times, or in other words, useful when the input is not too unpleasant. In the last decade of the past century appeared the first of them, see for example in \cite{ContejeanDevie_EfficientAlgorithm, ContiTraverso_Buchberger, Pottier_MinimalSolutions, Pottier96theeuclide}. Recently, some theoretical results as those presented in \cite{BrunsIchim_Normaliz} and \cite{Hemmecke_Hilbertbases} have been used to develop software packages providing computation results at reasonable execution times (see \cite{Normaliz} and \cite{4ti2}, respectively). What we mean with reasonable times is that for systems of equations with $k \le 10$, a personal computer can be used, by expecting a waiting time of a few minutes (as we have experienced in different examples, but not as a rule of thumb in any case). For larger systems, a supercomputer is indeed necessary to get an output in an acceptable period of time. With all these considerations in mind, and the opportunity of the state of the art of the computing hardware and software technology available, we decided to face the problem of solving this type of equations systems developing some refinements to the algorithm by Pis\'{o}n and Vigneron-Tenorio (\cite{PisonVigneron_Nsolutions}). In the first chapter of the present work, the program \texttt{DPSolve} is presented with the component algorithms to be used in order to compute the solutions of a system of linear Diophantine equations. One of the refinements in \texttt{DPSolve} relies in the following idea. The relations between the columns of $A$ can be represented by considering the semigroup ideal defined as the kernel of the ring morphism that assigns to each variable in $\kring[x_1,\ldots,x_k]$ the value $Y^c$ with $c$ ranging in the columns of $A$. These relations can be obtained by Gr\"{o}bner basis computations. By \cite{Herzog_Generators}, this semigroup ideal is generated by binomials, $\langle X^\alpha-X^\beta \mid A\alpha= A\beta\rangle$. Besides, from \cite{Vigneron_Semigroupidealslineardiophantine} we know how to check for a solution of $Ax=0$ (even for non-homogeneous systems) by looking for the existence of certain binomial in a Gr\"{o}bner basis of the semigroup ideal. We use a suited order for this Gr\"{o}bner basis computation, in order to feed \texttt{DPSolve} with particular solutions. This computation is done by means of the effective software tool \texttt{4ti2} (see \cite{4ti2}), doing direct library calls in our code. An additional refinement is in the slicing of the values of possible solutions to check, driven by the progress of the algorithm and the relations between the solutions obtained in each step. At the end of this chapter, we discuss a brief comparison with the programs \texttt{hilbert} (a component program included in \texttt{4ti2}) and \texttt{Normaliz} (see \cite{Normaliz}). The second chapter presents a generalization in two dimensions of proportionally modular numerical semigroups. Proportionally modular numerical semigroups consist in the set of numerators of rational numbers belonging to a given interval $I=[\alpha, \beta]\subseteq \R_\ge$, with $\alpha < \beta$, that is, proportionally modular numerical semigroups are monoids of the form $\bigcup_{n\in \mathbb N} n I\cap \mathbb N$. Equivalently, they are the set of nonnegative integer solutions of the inequality $ax \, \mod b \le c x$, with $a, b, c \in \Z^+$ (see \cite{RosalesEtal_ProportionallyModular}). We introduce affine convex body semigroups defined as $\mathcal{F}=\bigcup_{n\in \mathbb N} n F\cap \N^k$, with $F\subseteq \R^{k}_{\ge}$ a compact convex body. We particularize our study to $k=2$. In general, convex body semigroups are not finitely generated, but under conditions related with the slopes of the extremal rays of the minimal cone containing $\mathcal{F}$, it is possible to compute its minimal generating set. Those convex body semigroups that are finitely generated are called affine convex body semigroups, and are characterized when $F$ is a convex polygon or a circle. The characterization is based on the fact that the intersection of $F$ and the rays of the pointed cone associated to $F$ contains rational points. The non-negative integer solutions of a system of linear Diophantine equations can be used to obtain a system of generators of the pointed cone associated to a convex body semigroup (see \cite{RosalesGarcia_NonnegativeElements}). This is the approach that we adopted in \cite{GarciaMorenoSanchezVigneron_Affine_convex_body_semigroups}, whose content corresponds to the first sections of the second chapter. However for the present work, we choose an approach based in \cite{RosalesEtal_Bezout} that uses B\'ezout sequences (unimodular decomposition of cones in this setting) with much better results in computation time. Most of the results in Chapter 2 are tailored for affine convex body semigroups. First we focus on procedures to compute the minimal generating set of affine convex body semigroups. For the case of the circles, the resulting method has been implemented as a Mathematica\footnote{Every reference to the term Mathematica in this document, is referred to the set of programs of Wolfram Research, except where it is otherwise stated. Mathematica is a registered trademark of Wolfram Research Inc.} package, called \texttt{CircleSG} (see \cite{CircleSG}). The last sections of this chapter show how to determine whether or not affine circles or convex polygonal semigroups are Buchsbaum. We make use of a characterization of Buchsbaum simplicial affine semigroups, based on the property of being Cohen-Macaulay (\cite{GarciaVigneron_ComputingFamiliesRings} and \cite{GarciaRosales_BuchsbaumSimplicial}). We also benefit from the fact that membership to these affine convex body semigroups is easy to accomplish. The test is also implemented for affine polygonal convex semigroups in the Mathematica package \texttt{PolySGTools} (see \cite{polysgtools}). The non-negative integer solutions of a system of linear Diophantine equations appear in the context of the study of factorizations on affine semigroups: computing the set of factorizations of $m$ in the affine semigroup $M$ is equivalent to finding the set of nonnegative integer solutions of the system of linear Diophantine equations $A x = m$, where $A$ is a matrix whose columns are the generators of $M$. Under this perspective, the last chapter reviews invariants related with factorizations of elements in affine semigroups, with special focus on half-factorial monoids. Since in a half-factorial monoid all the lengths of factorizations of an element are the same, invariants such as elasticity, sets of lengths and Delta sets yield no information about how wild are the factorizations in these monoids. To this end a distance between factorizations was introduced in the literature, together with several invariants related to distances (see for example \cite{GeroldingerHalter_NonuniqueFactorizacions}). We review these invariants and see how they can be computed in the scope of affine semigroups. For the particular case of half-factorial affine semigroups we show that every possible catenary degree is attained in a Betti element of the monoid (which is far from being true in general). Also we prove that the tame degree and $\omega$-primality coincide for half-factorial monoids. We introduce a new invariant: the homogeneous catenary degree, which is an upper bound for the catenary degree and a lower bound for the monotone catenary degree. From any affine semigroup $M$ we define two new affine semigroups: $M^{\sfeq}$ and $M^\sfhom$. Both monoids are half-factorial, and the catenary degree of the first coincides with the equal catenary degree of $M$, while that of the second with the homogeneous catenary degree of $M$. We introduce the \texttt{GAP} package \texttt{4ti2gap} (\cite{4ti2gap}), which is a wrapper designed to give us an affordable way to perform affine computations using the software \texttt{4ti2} (\cite{4ti2}). In fact the main motivation to develop this package were the algorithms presented in Chapter 3 that rely on solving systems of linear Diophantine equations or (binomial) Gr\"obner basis computations. We provide an implementation in \texttt{GAP} of the procedures presented in Chapter 3. Results and conclusions Our software \texttt{DPSolve} has in general worst performance than \texttt{Normaliz} and \texttt{4ti2}. We have not been able to characterize families of systems of equations in which \texttt{DPSolve} runs faster, nor any heuristics suitable to discriminate which software to use for a given system of equations. The lack of satisfactory results encouraged us to develop the package \texttt{4ti2gap}, to deal with factorizations and presentations of affine semigroups in \texttt{GAP}. The results on affine convex body semigroups, apart from generalizing the concept of proportionally modular numerical semigroups, had an unexpected and gratifying consequence: the possibility of building in an easy way, families of Buchsbaum affine semigroups. Our study of nonunique factorization invariants started due to the interconnection with linear integer programming. We wanted to determine the range of possible catenary degrees, and we were able to achieve this for half-factorial monoids. Also we introduced a new promising invariant, and were able to relate equal catenary degree and this new catenary degre with catenary degree in auxiliary half-factorial monoids, that are inspired in classical constructions.