Sub-groups of Z^{n}, standard basis, and linear diophantine systems

Loïc Pottier ^{∗}

July 22, 1991

1 Introduction

Some connections between commutative algebra and linear diophantine problems exist for a long time (recently, see [4], [2], [3], [1] for works and bibliographies).

The results proposed here show that this connection can be systematicaly extended to relie standard (Gröbner) basis, Knuth-Bendix completion on commutative words, affine sub-groups of Z^{n}, and linear systems of inequalities on integers.

The main tool is the notion of ideal associated to an affine sub-group of Z^{n}, and its algorithmic aspect: its standard basis.

We then show that these tools can solve directly the following algorithmic problems on (affine) sub-groups and their non-negative parts :

• the membership problem,

• the triviality problem,

• find the smallest non zero vector.

• find the minimal non-negative elements.

• solve linear diophantine systems (Ax = 0, x ≥ 0), (Ax = b, x ≥ 0), Ax ≤ b on integers, and find smallest solutions.

2 Ideal of a sub-group H of Z^{n}

Theorem 1 Let v_{1},…, v_{p} generating H a sub-group os Z^{n}, and J_{H} the poluynomial ideal

generated by the polynomials Xv+ i − Xv− i and the polynomial T X^{1} − 1, where X^{u} denotes the monomial X_{1}^{u_{1}} … X_{n}^{u_{n}}, and T is a new indeterminate.

Then

v ∈ H ⇔ X^{v^{+}} − X^{v^{−}} ∈ J_{H}

Let I_{H} = J_{H} ∩ Z[X_{1},…, X_{n}].

I_{H} is called the ideal of H, and we have v ∈ H ⇔ X^{v^{+}} − X^{v^{−}} ∈ I_{H}.

3 Ideal of a + H

We extend theorem 2 to affine sub-groups.

Theorem 2 Let v_{1},…, v_{p} generating H, and J_{a+H} the ideal generated by the polynomials

Xv+ i − Xv− i, T UX^{1} − 1, and UX^{a−} − X^{a^{+}}, where T and U are new indeterminates. Then

v ∈ a + H ⇔ X^{v^{+}} − UX^{v^{−}} ∈ J_{a+H}

Let I_{a+H} = J_{a+H} ∩ Z[U, X_{1},…, X_{n}].

I_{a+H} is called the ideal of a + H, and we have v ∈ a + H ⇔ X^{v^{+}} − UX^{v^{−}} ∈ I_{a+H}.

4 Standard basis of H and a + H

Let B a standard basis of J_{H} for an ordering eliminating T, and Bs_{H} be the set of polynomials of B not containing T. Then Bs_{H} is a standard basis of I_{H} , and is called a standard basis of H.

Let B a standard basis of J_{a+H} for an ordering eliminating T and U, with T > U, and Bs_{H} be the set of polynomials of B not containing T. Then Bs_{a+H} is a standard basis of I_{a+H} , and is called a standard basis of (a + H).

By an easy remark, every polynomial of Bs_{H} is of the form X^{v^{+}} − X^{v^{−}}, with v ∈ H.

5 Non-negative parts of (affine) sub-groups of Z^{n}

5.1 Triviality problem

Theorem 3

(a + H)^{+} ≠ ∅ ⇔ ∃(X^{α} − U) ∈ Bs_{a+H}

H^{+} ≠ {0} ⇔ ∃(X^{α} − 1) ∈ Bs_{H}

5.2 Minimal elements of (a + H)^{+}

A standard basis of a + H gives an element of (a + H)^{+} when such an element exists. We will use this fact to give an algorithm computing the set Min((a + H)^{+}) of minimal elements of a + H for the partial ordering ≤ (is it well known that this set is finite).

The algorithm MINAFFINE computes Min((a + H)^{+}) :

MINAFFINE(a,H): (H is given by its generators) Bs_{a+H} := a standard basis of (a + H). IF it exists (X^{α} − U) in Bs_{a+H}

THEN v:= α

ELSE RETURNS ∅ FOR i:= 1...n AND k:=0...v_{i} − 1 DO

Compute a_{i,k} and generators of H_{i,k} such that a_{i,k} + H_{i,k} = (a + H) ∩ {x | x_{i} = k} ≠ ∅

RETURNS Minimals elements of {v} ∪ (⋃_{i,k} MINAFFINE(a_{i,k}, H_{i,k}))

5.3 Minimal non zero elements of H^{+}

The previous algorithm can be modified to compute minimal non zero elements of H^{+} :

we just begin with a = 0, take v such that X^{v} − 1 ∈ Bs_{a+H}, and then continue the previous algorithm.

6 Linear diophantine systems

We show now how the previous results apply to the study of linear diophantine systems. We will study the following types of systems : Ax = 0, x ≥ 0, Ax = b, x ≥ 0, Ax ≤ b

where A is a matrix of integers with n columns and m rows, x is in Z^{n}, and b in Z^{m}.

In the following, S will be the set of solutions of the considered system.

6.1 Systems Ax = 0, x ≥ 0

Here S = H^{+}, where H = Ker(A), which is an sub-group of Z^{n}. The computation of generators of H from A can be made by computing an Hermite normal form of A.

Theorem 5 and algorithm 1 give then the awnsers to our questions on S :

Theorem 4

x ∈ S ⇔ X^{x} − 1 ∈ I_{H}

S ≠ {0} ⇔ ∃(X^{α} − 1) ∈ Bs_{H} ⇒ α ∈ S

and MINHOM(H) is the set of minimal non zero elements of S.

6.2 Other systems

Same techniques apply to the two other kinds of systems, by reducing the problem to an affine sub-group.

References

[1] P.Conti and C.Traverso “Buchberger algorithm and integer programming”, internal report,Univ. Pisa, Italy, 91, submitted to publication.

[2] F.Ollivier “Le problème de l’identifiabilité structurelle globale : approche théorique, méthodes effectives et bornes de complexité”, Phd Thesis, Ecole Polytechnique, France, june 1990.

[3] L.Pottier “Minimals solutions of linear diophantine systems : bounds and algorithms”, Proc. RTA-91, LNCS 488, april 91.

[4] R.P.Stanley “Combinatorics and commutative algebra”, Progress in Mathematics, Birkäuser ed., 1983.