Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 41 (2000), No. 1, 49-55.

On Minimal Solutions of Diophantine Equations

Martin Henk Robert Weismantel^{∗}

Fachbereich Mathematik, IMO, Otto-von Guericke-Universität Magdeburg Universitätsplatz 2, D-39106 Magdeburg, Germany e-mail: henk@imo.mathematik.uni-magdeburg.de e-mail: weismantel@imo.mathematik.uni-magdeburg.de

Abstract. This paper investigates the region in which all the minimal solutions of a linear diophantine equation lie. We present best possible inequalities which must be satisfied by these solutions and thereby improve earlier results. Keywords: linear Diophantine equations, Hilbert basis, pointed rational cones.

1. Introduction

For two nonnegative integral vectors a ∈ ℕ^{n}, b ∈ ℕ^{m}, n, m ≥ 1, let

L(a, b) = {(x, y) ∈ ℕ^{n} × ℕ^{m} : a^{⊺}x = b^{⊺}y}  (1.1)

be the set of all nonnegative solutions of the linear Diophantine equation a^{⊺}x = b^{⊺}y. Here we are interested in the minimal solutions of this linear Diophantine equation, where (x, y) ∈ L(a, b) is called minimal if it can not be written as the sum of two other elements of L(a, b)\{0}. The set of all minimal solutions is denoted by H(a, b). By definition we have

L(a, b) = {∑_{i=1}^{p} q_{i}h^{i} : q_{i}, p ∈ ℕ, h^{i} ∈ H(a, b)}

and H(a, b) is a minimal subset of L(a, b) having this generating property.

∗Supported by a Gerhard-Hess-Forschungsförderpreis of the German Science Foundation (DFG)

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2000 Heldermann Verlag

In other words, H(a, b) is the Hilbert basis of the pointed rational cone

C(a, b) = {(x, y) ∈ ℝ_{≥0}^{n} × ℝ_{≥0}^{m} : a^{⊺}x = b^{⊺}y}.  (1.2)

A Hilbert basis of an arbitrary pointed rational polyhedral cone C ⊂ ℝ^{n} is defined as the unique minimal generating system (w.r.t. nonnegative integral combinations) of the semigroup C ∩ ℤ^{n}. Observe, that C(a, b) ∩ ℕ^{n×m} = L(a, b). The existence of such a system of finite cardinality was already shown by Gordan [5] for any rational cone. Van der Corput [1] proved the uniqueness for pointed rational cones.

The set H(a, b) of all minimal solutions of a linear Diophantine equation has been studied for a long time in various contexts, see e.g., [3], [4], [6] and the references within. The purpose of this note is to generalize a result of Lambert [7] and Diaconis/Graham/Sturmfels [2] by proving that the elements of H(a, b) satisfy a certain system of inequalities.

We assume throughout that a = (a_{1}, …, a_{n})^{⊺} ∈ ℕ^{n}, b = (b_{1}, …, b_{m})^{⊺} ∈ ℕ^{m}, n ≥ m ≥ 1, and a_{1} ≤ a_{2} ≤ ⋯ ≤ a_{n}, b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{m}. It is not hard to see that

C(a, b) = pos {b_{j}e^{i} + a_{i}e^{n+j} : 1 ≤ i ≤ n, 1 ≤ j ≤ m} ,

where pos denotes the positive hull and e^{i} ∈ ℝ^{n+m} denotes the i-th unit vector. A trivial system of valid inequalities for the elements of H(a, b) is given by the facet defining hyperplanes of the zonotope

{(x, y) ∈ ℝ^{n+m} : (x, y)^{⊺} = ∑_{i,j} λ_{ij}(b_{j}e^{i} − a_{i}e^{n+j}), 0 ≤ λ_{ij} ≤ 1},

because it is well-known (and easy to see) that the Hilbert basis of a pointed rational cone is contained in the zonotope spanned by the generators of the cone. Stronger inequalities were given by Lambert ([7]) and independently by Diaconis/Graham/Sturmfels [2]. They proved that every (x, y)^{⊺} ∈ H(a, b) satisfies

∑_{i=1}^{n} x_{i} ≤ b_{m} and ∑_{j=1}^{m} y_{j} ≤ a_{n}.  (1.3)

Here we show

Theorem 1. Every (x, y)^{⊺} ∈ H(a, b) satisfies the n + m inequalities

[J_{l}] :  ∑_{i=1}^{n} x_{i} + ∑_{j=1}^{l−1} ⌊\frac{b_{l} − b_{j}}{a_{n}} ⌋ y_{j} ≤ b_{l} + ∑_{j=l+1}^{m} ⌈\frac{b_{j} − b_{l}}{a_{1}} ⌉ y_{j}, l = 1, …, m,

[I_{k}] :  ∑_{j=1}^{m} y_{j} + ∑_{i=1}^{k−1} ⌊\frac{a_{k} − a_{i}}{b_{m}} ⌋ x_{i} ≤ a_{k} + ∑_{i=k+1}^{n} ⌈\frac{a_{i} − a_{k}}{b_{1}} ⌉ x_{i}, k = 1, …, n,

where ⌈x⌉ (⌊x⌋) denotes the smallest integer not less than x (the largest integer not greater than x).

Observe, that [J_{m}] and [I_{n}] are generalizations of the inequalities stated in (1.3).

2. Proof of Theorem 1

In the following we denote by ≤ (respectively by <) the usual partial order, i.e., for two vectors x, y we write x ≤ y if for each coordinate holds x_{i} ≤ y_{i} and we write x < y if, in addition, there exists a coordinate with x_{j} < y_{j}. The proof of Theorem 1 relies on the following observation.

Lemma 1. Let (x̂, ŷ)^{⊺} ∈ L(a, b) and let (x^{1}, y^{1})^{⊺}, (x^{2}, y^{2})^{⊺} ∈ ℕ^{n+m} such that 0 < (x^{2} − x^{1}, y^{2} − y^{1})^{⊺} < (x̂, ŷ)^{⊺} and a^{⊺}x^{1} − b^{⊺}y^{1} = a^{⊺}x^{2} − b^{⊺}y^{2}. Then (x̂, ŷ)^{⊺} is not an element of H(a, b).

Proof. Let (z_{x}, z_{y}) = (x^{2} − x^{1}, y^{2} − y^{1}). By assumption we have (z_{x}, z_{y})^{⊺}, (x̂ − z_{x}, ŷ − z_{y})^{⊺} ∈ L(a, b)\{0}. Thus (x̂, ŷ) = (x̂−z_{x}, ŷ−z_{y})+(z_{x}, z_{y}) can be written as a non-trivial combination of two elements of L(a, b)\{0}.

Proof of Theorem 1. Let (x̃, ỹ)^{⊺} ∈ H(a, b). By symmetry it suffices to consider only the inequalities [J_{l}], l = 1, …, m. Let us fix an index l ∈ {1, …, m} and let ξ = ∑_{i=1}^{n} x̃_{i}, υ = ∑_{j=1}^{m} ỹ_{j}. We choose a sequence of points x^{i} ∈ ℕ^{n}, 0 ≤ i ≤ ξ, such that

0 = x^{0} < x^{1} < x^{2} < ⋯ < x^{ξ} = x̃.  (2.1)

Next we define recursively a sequence of points y^{j} ∈ ℕ^{m}, 0 ≤ j ≤ υ, by y^{0} = 0 and y^{j} = y^{j−1} + e^{d(j)}, j ≥ 1, where the index d(j) is given by d(j) = min{1 ≤ d ≤ m : y_{d}^{j−1} + e^{d} ≤ ỹ_{d}}. Observe that here e^{d} denotes the d-th unit vector in ℝ^{m}. Obviously, we have

0 = y^{0} < y^{1} < y^{2} < ⋯ < y^{υ} = ỹ.  (2.2)

For two points x ∈ ℕ^{n}, y ∈ ℕ^{m} let r(x, y) = a^{⊺}x − b^{⊺}y and for a given point x^{i} let y^{μ(i)} be the unique point such that

r(x^{i}, y^{μ(i)}) = min {r(x^{i}, y^{j}) : r(x^{i}, y^{j}) ≥ 0, 0 ≤ j ≤ υ} .

For abbreviation we set r(i) = r(x^{i}, y^{μ(i)}). It is easy to see that r(i) ∈ {0, …, b_{m} − 1} and

0 = y^{μ(0)} ≤ y^{μ(1)} ≤ ⋯ ≤ y^{μ(ξ)} = ỹ.  (2.3)

Moreover, by definition of y^{j} we have the relation

r(i) ≥ b_{t} ⟹ y_{j}^{μ(i)} = ỹ_{j}, 1 ≤ j ≤ t.  (2.4)

So we have assigned to each i ∈ {0, …, ξ − 1} its residue r(i) and now we count the number of different residues which may occur. To this end let

R_{l} = {i ∈ {0, …, ξ − 1} : r(i) < b_{l}} ,

and for l + 1 ≤ j ≤ m let

R_{j} = {i ∈ {0, …, ξ − 1} : b_{l} ≤ r(i) < b_{j}, y_{j−1}^{μ(i)} = ỹ_{j−1}, y_{j}^{μ(i)} < ỹ_{j}} .

Since {0, …, ξ − 1} = ⋃_{j=l}^{m} R_{j} we have

∑_{i=1}^{n} x̃_{i} ≤ #R_{l} + ∑_{j=l+1}^{m} #R_{j}.  (2.5)

By Lemma 1, (2.1), (2.2) we have

#R_{l} = #{r(i) : i ∈ R_{l}} ≤ b_{l}.  (2.6)

We claim that for j = l + 1, …, m

#R_{j} ≤ ⌈\frac{b_{j} − b_{l}}{a_{1}} ⌉ ỹ_{j}.  (2.7)

To show this let ζ ∈ {0, …, ỹ_{j} − 1} and let x^{i_{1}} < ⋯ < x^{i_{τ}} be all vectors of the x-sequence (cf. (2.1)) satisfying y_{j}^{μ(i)} = ζ and i ∈ R_{j}. By construction we have y^{μ(i_{1})} = y^{μ(i_{2})} = ⋯ = y^{μ(i_{τ})} and so

(τ − 1)a_{1} ≤ a^{⊺}x^{i_{τ}} − a^{⊺}x^{i_{1}} = r(i_{τ}) − r(i_{1}) ≤ (b_{j} − 1) − b_{l}.

Hence τ ≤ ⌈(b_{j} − b_{l})/a_{1}⌉ and we get (2.7).

So far we have proved (cf. (2.5), (2.7))

∑_{i=1}^{n} x̃_{i} ≤ #R_{l} + ∑_{j=l+1}^{m} ⌈\frac{b_{j} − b_{l}}{a_{1}} ⌉ ỹ_{j}.  (2.8)

In the following we estimate the number of residues in {0, …, b_{l} −1} which are not contained in {r(i) : i ∈ R_{l}}.

To do this we have to extend our x-sequence. For v ∈ ℕ let p_{v}, q_{v} ∈ ℕ be the uniquely determined numbers with v = p_{v}ξ + q_{v}, 0 ≤ q_{v} < ξ, and let

\overline{x}^{v} = p_{v}x^{ξ} + x^{q_{v}}.

Observe that r(\overline{x}^{v}, y) = p_{v}b^{⊺}ỹ− b^{⊺}y + a^{⊺}x^{q_{v}}. For s ∈ \{1, …, l − 1\} and t ∈ \{0, …, ỹ_{s} − 1\} let y^{s,t} be the point of the y-sequence (cf. (2.2)) with coordinates

y_{s}^{s,t} = t, y_{j}^{s,t} = ỹ_{j}, 1 ≤ j ≤ s − 1, and y_{j}^{s,t} = 0, s + 1 ≤ j ≤ m.

For such a vector y^{s,t} let \overline{x}^{δ(s,t)} be the point of the \overline{x}-sequence such that

r(\overline{x}^{δ(s,t)}, y^{s,t}) = min \{r(\overline{x}^{i}, y^{s,t}) : r(\overline{x}^{i}, y^{s,t}) ≥ b_{s}, i ∈ \{0, …, ξ\}\} .

Observe that such a point \overline{x}^{δ(s,t)} exists, because t ∈ \{0, …, ỹ_{s} − 1\}. Moreover, \overline{x}^{δ(s,t)} belongs to the “original” x-sequence. In particular, we have

b_{s} ≤ r(x^{δ(s,t)}, y^{s,t}) < b_{s} + a_{n}.  (2.9)

Let r_{s,t} = \{\overline{x}^{i} : b_{s} ≤ r(\overline{x}^{i}, y^{s,t}) < b_{l}\}. Obviously, by (2.9) we have

#r_{s,t} ≥ ⌊(b_{l} − b_{s})/a_{n}⌋.  (2.10)

Now we study the cardinality of

\overline{R} = ⋃_{s=1}^{l−1} \{ ⋃_{t=0}^{ỹ_{s}−1} \{r(\overline{x}^{i}, y^{s,t}) : b_{s} ≤ r(\overline{x}^{i}, y^{s,t}) < b_{l}\}\}

and we show

#\overline{R} ≥ ∑_{s=1}^{l−1} ⌊\frac{b_{l} − b_{s}}{a_{n}} ⌋ ỹ_{s}.  (2.11)

Suppose the contrary. Then, by (2.10), we can find s, s′ ∈ {1, …, l − 1}, t ∈ {0, …, ỹ_{s} − 1}, t′ ∈ \{0, …, ỹ_{s′} − 1\} and vectors \overline{x}^{v}, \overline{x}^{w} of the \overline{x}-sequence such that r(\overline{x}^{v}, y^{s,t}) = r(\overline{x}^{w}, y^{s′,t′}). We may assume y^{s,t} < y^{s′,t′} and therefore \overline{x}^{v} < \overline{x}^{w}, i.e., v ≤ w. Since

r(\overline{x}^{v}, y^{s,t}) = p_{v}b^{⊺}ỹ − b^{⊺}y^{s,t} + a^{⊺}x^{q_{v}} = p_{w}b^{⊺}ỹ − b^{⊺}y^{s′,t′} + a^{⊺}x^{q_{w}} = r(\overline{x}^{w}, y^{s′,t′})

we get p_{w} ∈ {p_{v}, p_{v} + 1}.

a) If p_{w} = p_{v} then 0 < \overline{x}^{w} − \overline{x}^{v} = x^{q_{w}} − x^{q_{v}} < x^{ξ} and we can apply Lemma 1 to (\overline{x}^{v}, y^{s,t})^{⊺}, (\overline{x}^{w}, y^{s′,t′})^{⊺} which yields the contradiction (x̃, ỹ) ∉ H(a, b).

b) If p_{w} = p_{v} + 1 then 0 < \overline{x}^{w} − \overline{x}^{v} = x^{ξ} + x^{q_{w}} − x^{q_{v}}. Since

a^{⊺}(x^{q_{v}} − x^{q_{w}}) = b^{⊺}ỹ + b^{⊺}y^{s,t} − b^{⊺}y^{s′,t′} > 0

we have x^{q_{w}} < x^{q_{v}} and thus 0 < \overline{x}^{w} − \overline{x}^{v} < x^{ξ}. Hence, also in this case we can apply Lemma 1 and obtain a contradiction.

Next we claim that

\overline{R} ∩ \{r(i) : i ∈ R_{l}\} = ∅.  (2.12)

Otherwise there exist \overline{x}^{v}, y^{s,t} with b_{s} ≤ r(\overline{x}^{v}, y^{s,t}) < b_{l} and \overline{x}^{i}, y^{μ(i)}, 0 ≤ i ≤ ξ − 1, such that r(\overline{x}^{v}, y^{s,t}) = r(\overline{x}^{i}, y^{μ(i)}). Since r(\overline{x}^{v}, y^{s,t}) ≥ b_{s} but y_{s}^{s,t} < ỹ_{s} we have y^{s,t} ≠ y^{μ(i)} (cf. (2.4)). Hence, we may assume y^{s,t} < y^{μ(i)} or y^{μ(i)} < y^{s,t}.

a) If y^{s,t} < y^{μ(i)} then \overline{x}^{v} < \overline{x}^{i} and thus v < i < ξ. Again, by Lemma 1 we find (x̃, ỹ) ∉ H(a, b).

b) If y^{μ(i)} < y^{s,t} then \overline{x}^{i} < \overline{x}^{v}. As above, it is easy to see that p_{v} ∈ \{0, 1\} and that in both cases Lemma 1 can be applied in order to get a contradiction.

Finally, we note that (2.6), (2.12) and (2.11) imply

#R_{l} ≤ b_{l} − ∑_{s=1}^{l−1} ⌊\frac{b_{l} − b_{s}}{a_{n}} ⌋ ỹ_{s},

which proves inequality [J_{l}] (cf. (2.8)).

3. Remarks

Theorem 1 shows that the minimal solutions of a linear Diophantine equation lie in the region that one obtains from intersecting the zonotope associated with the generators of C(a, b) with all the halfspaces induced by the inequalities [I_{k}], k = 1, …, n and [J_{l}], l = 1, …, m. We believe that a stronger statement is true: every element of H(a, b) is a convex combination of 0 and the generators b_{j}e^{i} + a_{i}e^{n+j} of C(a, b). More formally, let

P (a, b) = conv {0, b_{j}e^{i} + a_{i}e^{n+j} : 1 ≤ i ≤ n, 1 ≤ j ≤ m} .

We conjecture that

Conjecture 1. H(a, b) ⊂ P (a, b).^{1}

We remark that there is an example by Hosten and Sturmfels showing that if one replaces P (a, b) by the “smaller” polytope P̃(a, b) = conv {0, (b_{j}e^{i} + a_{i}e^{n+j})/ gcd(b_{j}, a_{i}) : 1 ≤ i ≤ n, 1 ≤ j ≤ m}, then H(a, b) ⊄ P̃(a, b).

For m = 1 Theorem 1 implies the inclusion H(a, b) ⊂ P (a, b). This can easily be read off from the representation

P (a, b) = {(x, y)^{⊺} ∈ ℝ^{n} × ℝ : a^{⊺}x = b_{1}y, x, y ≥ 0, ∑_{i=1}^{n} x_{i} ≤ b_{1}} .

It is not difficult to check that the inequalities [I_{k}] and [J_{l}] of Theorem 1 “without rounding” define facets of P (a, b).

Proposition 1. For l = 1, …, m let

J_{l} = \{(x, y) ∈ ℝ^{n} × ℝ^{m} : ∑_{i=1}^{n} x_{i} + ∑_{j=1}^{l−1} \frac{b_{l} − b_{j}}{a_{n}} y_{j} ≤ b_{l} + ∑_{j=l+1}^{m} \frac{b_{j} − b_{l}}{a_{1}} y_{j}\}

and for k = 1, …, n let

I_{k} = \{(x, y) ∈ ℝ^{n} × ℝ^{m} : ∑_{j=1}^{m} y_{j} + ∑_{i=1}^{k−1} \frac{a_{k} − a_{i}}{b_{m}} x_{i} ≤ a_{k} + ∑_{i=k+1}^{n} \frac{a_{i} − a_{k}}{b_{1}} x_{i}\} .

Then we have P (a, b) ⊂ J_{l}, P (a, b) ⊂ I_{k}. Moreover, P (a, b) ∩ J_{l} and P (a, b) ∩ I_{k} are facets of P (a, b), 1 ≤ l ≤ m, 1 ≤ k ≤ n.

Proof. It is quite easy to check that all vectors b_{j}e^{i} + a_{i}e^{n+j}, 1 ≤ i ≤ n, 1 ≤ j ≤ m, are contained in J_{l}, l = 1, …, m. Moreover, the inequality corresponding to J_{l} is satisfied with equality by the n + m − 1 linearly independent points b^{l}e^{i} + a_{i}e^{n+l}, 1 ≤ i ≤ n, b_{j}e^{n} + a_{n}e^{n+j}, 1 ≤ j ≤ l − 1, b_{j}e^{1} + a_{1}e^{n+j}, l + 1 ≤ j ≤ m. The halfspaces I_{k} can be treated in the same way.

1This conjecture was independently made by Hosten and Sturmfels, private communication.

Elementary considerations show that for m = 2 the polytope P (a, b) can be written as P (a, b) = {(x, y)^{⊺} ∈ ℝ^{n} × ℝ^{2} : a^{⊺}x = b^{⊺}y; x, y ≥ 0, (x, y)^{⊺} ∈ I_{k}, 1 ≤ k ≤ n}, and thus Theorem 1 and Proposition 1 imply that the conjecture is “almost true” when m = 2 (or respectively, for n = 2).

Acknowledgements. We would like to thank Robert T. Firla and Bianca Spille for helpful comments.

References

[1] van der Corput, J. G.: Über Systeme von linear-homogenen Gleichungen und Ungleichungen. Proceedings Koninklijke Akademie van Wetenschappen te Amsterdam 34 (1931), 368–371.

[2] Diaconis, P.; Graham, R.; Sturmfels, B.: Primitive partition identities. Paul Erdös is 80, Vol. II, Janos Bolyai Society, Budapest (1995), 1–20.

[3] Ehrhart, E.: Sur les équations diophantiennes linéaires. C. R. Acad. Sci. Paris, 288 (1979), Série A, 785–787.

[4] Filgueiras, M.; Tomás, A. P.: A fast method for finding the basis of non-negative solutions to a linear Diophantine equation. J. Symbolic Comput. 19 (1995), 507–526.

[5] Gordan, P.: Über die Auflösung linearer Gleichungen mit reellen Coefficienten. Math. Ann. 6 (1873), 23–28.

[6] Greenberg, H.: Solution to a linear Diophantine equation for nonnegative integers. J. Algorithms 9 (1988), 343–353.

[7] Lambert, J. L.: Une borne pour les générateurs des solutions entiéres positives d’une équation diophantienne linéaire. C.R. Acad. Sci. Paris 305 (1987), Série I, 39–40.

Received January 4, 1999