arXiv:1611.02627v2 [math.GR] 17 Mar 2017

On a transport problem and monoids of
non-negative integers
Aureliano M. Robles-Pérez∗† and José Carlos Rosales∗‡

Abstract
A problem about how to transport profitably a group of cars leads
us to study the set T formed by the integers n such that the system of
inequalities, with non-negative integer coefficients,
a 1 x 1 + · · · + a p x p + α ≤ n ≤ b1 x 1 + · · · + bp x p − β
has at least one solution in Np . We will see that T ∪ {0} is a submonoid
of (N, +). Moreover, we show algorithmic processes to compute T .

Keywords: Transport problem, Diophantine inequalities, monoids.
2010 AMS Classification: 20M14, 11D75

1

Introduction

A transport company is dedicated to carry cars from the factory to the authorised dealer. For that, the company uses small and large trucks with a capacity
of three and six cars, respectively. Moreover, we have the following determinants.
• The use of those trucks represents, for the company, a cost of 1200 and
1500 euros, respectively.
• The company charges to the dealer 300 euros for each transported car.
• Without charge for the customer, an additional car is loaded facing possible eventualities.
∗ Both authors are supported by the project MTM2014-55367-P, which is funded by Ministerio de Economı́a y Competitividad and Fondo Europeo de Desarrollo Regional FEDER,
and by the Junta de Andalucı́a Grant Number FQM-343. The second author is also partially
supported by Junta de Andalucı́a/Feder Grant Number FQM-5849.
† Departamento de Matemática Aplicada, Universidad de Granada, 18071-Granada, Spain.
E-mail: arobles@ugr.es
‡ Departamento de Álgebra, Universidad de Granada, 18071-Granada, Spain.
E-mail: jrosales@ugr.es

1

If the company consider that a transport order is cost-effective when it has
profits of at least 900 euros, how many cars must be transported in order to
achieve that purpose?
It is clear that a transport order is profitable if and only if there exist x, y ∈ N
(where N is the set of non-negative integers) such that
)
300n ≥ 1200x + 150y + 900
.
(1.1)
n + 1 ≤ 3x + 6y
Simplifying the first inequality of (1.1), we have the equivalent system
)
n ≥ 4x + 5y + 3
.
n ≤ 3x + 6y − 1

(1.2)


Consequently, the set n ∈ N | (1.2) has a solution in N2 is formed by the nonnegative integers which give us an affirmative answer to the proposed problem.
We can generalize the above problem in the following way: if we consider
a = (a1 , . . . , ap ), b = (b1 , . . . , bp ) ∈ Np and α, β ∈ N, then we want to compute
the set
(
)
a1 x1 + · · · + ap xp + α ≤ n ≤ b1 x1 + · · · + bp xp − β
S(a, b, α, β) = n ∈ N
.
for some (x1 , . . . xp ) ∈ Np
(1.3)
In this work we will prove that S(a, b, α, β) ∪ {0} is a submonoid of (N, +)
(that is, a subset of N that is closed under addition and contains the zero
element) and our main purpose will be to give an algorithm in order to compute
the minimal system of generators for such a monoid.
To finish this introduction, let us observe that, with the above notation, the
problem studied in [4] is associated to the particular sets S(a, b, 1, 1).

2

First results and the case (α, β) = (0, 0)

In this section will be suppose that a = (a1 , . . . , ap ), b = (b1 , . . . , bp ) belong to
Np and that α, β ∈ N.
Lemma 2.1. If m, n ∈ S(a, b, α, β), then m + n ∈ S(a, b, α, β).
Proof. If m, n ∈ S(a, b, α, β), then there exist (x1 , . . . , xp ), (y1 , . . . , yp ) ∈ Np
such that
a1 x1 + · · · + ap xp + α ≤ m ≤ b1 x1 + · · · + bp xp − β
and
a1 y1 + · · · + ap yp + α ≤ n ≤ b1 y1 + · · · + bp yp − β.
Therefore,
a1 (x1 + y1 )+ · · ·+ ap (xp + yp )+ 2α ≤ m+ n ≤ b1 (x1 + y1 )+ · · · + bp (xp + yp )− 2β.
2

Thus,
a1 (x1 + y1 ) + · · · + ap (xp + yp ) + α ≤ m + n ≤ b1 (x1 + y1 ) + · · · + bp (xp + yp ) − β,
and, consequently, m + n ∈ S(a, b, α, β).
As an immediate consequence of the above result we have the following
proposition.
Proposition 2.2. S(a, b, α, β) ∪ {0} is a submonoid of (N, +).
Let X be a non-empty subset of Nk . We will denote by hXi the submonoid
of (Nk , +) generated by X, that is,
hXi = {λ1 x1 + · · · + λn xn | n ∈ N \ {0}, x1 , . . . , xn ∈ X, λ1 , . . . , λn ∈ N} .
If M is a submonoid of (Nk , +) and M = hXi, then we will say that X is a
system of generators of (for) M or, equivalently, that M is generated by X. In
addition, if no proper subset of X generates M , then we will say that X is a
minimal system of generators of (for) M .
The next result is [6, Corollary 2.8].
Proposition 2.3. Every submonoid of (N, +) admit a unique minimal system
of generators. Moreover, such a system is finite.
Our objective in this work is to show an algorithm to compute the minimal
system of generators of S(a, b, α, β) ∪ {0}. In this section we will solve the
problem when (α, β) = (0, 0).
A submonoid M of (Np , +) is finitely generated if there exists a finite set X
such that M = hXi. From Proposition 2.3 we know that every submonoid of
(N, +) is finitely generated. However, if k ≥ 2, then there exist submonoids of
(Nk , +) which are not finitely generated.
Let z = (z1 , . . . , zp ) ∈ Zp (where Z is the set of integers) and let A(z) =
{(x1 , . . . , xp ) ∈ Np | z1 x1 + · · · + zp xp ≥ 0}. It is well known that A(z) is a finitely generated submonoid of (Np , +) and, moreover, in [1] it is shown an algorithm to compute a finite system of generators of A(z).
If s, t ∈ Z (with s ≤ t), then we will denote by [s, t] = {x ∈ Z | s ≤ x ≤ t}.
Theorem 2.4. Let {m1 , . . . , , mq } be a system of generators of A(b − a), where
mi = (mi1 , . . . , mip ) for all i ∈ {1,S. . . , q}. Then S(a, b, 0, 0) ∪ {0} is the submonoid of (N, +) generated by L = qi=1 [a1 mi1 +· · ·+ap mip , b1 mi1 +· · ·+bp mip ].
Proof. It is clear that
S(a, b, 0, 0) =

[

[a1 x1 + · · · + ap xp , b1 x1 + · · · + bp xp ].

(x1 ,...,xp )∈A(b−a)

Therefore, S(a, b, 0, 0) ∪ {0} is a submonoid of (N, +) which contains L. In order
to finish the proof, we will see that, if T is a submonoid of (N, +) which contains
3

L, then S(a, b, 0, 0) ⊆ T . For that we will prove that, if (x1 , . . . , xp ) ∈ A(b − a),
then [a1 x1 + · · · + ap xp , b1 x1 + · · · + bp xp ] ⊆ T .
If (x1 , . . . , xp ) ∈ A(b − a), then we have (x1 , . . . , xp ) = λ1 m1 + · · · + λq mq
for some λ1 , . . . , λq ∈ N. By induction over λ1 + · · · + λq , we will show that
[a1 x1 + · · · + ap xp , b1 x1 + · · · + bp xp ] ⊆ T . Thus, if λ1 + · · · + λq = 0 the result
is obvious. Let us suppose that λ1 + · · · + λq ≥ 1 and let i ∈ {1, . . . , q} such
that λi 6= 0. If we take (y1 , . . . , yp ) = λ1 m1 + · · · + (λi − 1)mi + · · · + λq mq ,
then (x1 , . . . , xp ) = (y1 , . . . , yp ) + mi and, by the induction hypothesis, we get
that [a1 y1 + · · · + ap yp , b1 y1 + · · · + bp yp ] ⊆ T . Since T is a monoid, then
[a1 y1 +· · ·+ap yp , b1 y1 +· · ·+bp yp ]+[a1 mi1 +· · ·+ap mip , b1 mi1 +· · ·+bp mip ] ⊆ T
and, consequently, [a1 x1 + · · · + ap xp , b1 x1 + · · · + bp xp ] ⊆ T .
Now, we are going to describe an algorithmic process, given in [4], in order
to compute a system of generators for A(z). Thereby, we get a self-contained
paper and, in addition, we will be able to describe examples without necessity
of referencing to [1].
Let B(z) = {(x1 , . . . , xp , xp+1 ) ∈ Np+1 | z1 x1 + · · · + zp xp − xp+1 = 0}. It is
well known (see [5]) that B(z) is a finitely generated submonoid of (Np+1 , +) and,
in addition, its set of minimal generators coincide with the minimal elements
(with the usual order in Np+1 ) of the set B(z) \ {(0, . . . , 0)}. Moreover, we
know that, if (x1 , . . . , xp , xp+1 ) is a minimal element of B(z) \ {(0, . . . , 0)}, then
x1 +· · ·+xp+1 ≤ |z1 |+· · ·+|zp |+2 (Pottier’s bound, [3]). Finally, it is easy to see
that, if {b1 , . . . , bq } is a system of generators of B(z), then {π(b1 ), . . . , π(bq )}
is a system of generators for A(z) (where π(x1 , . . . , xp , xp+1 ) = (x1 , . . . , xp )).
Therefore, we have an algorithm to compute a system of generators for A(z).
Example 2.5. We aregoing to compute the minimal system of generators for
S = S (4, 5), (3, 6), 0, 0 ∪ {0}. We begin computing a system of generators for
A(−1, 1) = {(x, y) ∈ N2 | −x + y ≥ 0}. For that, we compute the minimal elements of B(−1, 1)\{(0, 0, 0)}, where B(−1, 1) = {(x, y, z) ∈ N3 | −x+y−z = 0}.
By applying the Pottier’s bound, we have that (1, 1, 0), (0, 1, 1) are such minimal elements and, in consequence, {(1, 1), (0, 1)} is a system of generators for
A(−1, 1). Therefore, by applying Theorem 2.4, we conclude that [9, 9] ∪ [5, 6] =
{5, 6, 9} is a system of generators for S. Thus, S = {0, 5, 6, 9, 10, 11, 12, 14, →}
(where the symbol → means that every number greater than 14 belongs to S).

3

The case (α, β) 6= (0, 0)

Let A = {(x1 , . . . , xp ) ∈ Np | (b1 − a1 )x1 + · · · + (bp − ap )xp ≥ α + β}. Then it
is clear that
[
[a1 x1 + · · · + ap xp + α, b1 x1 + · · · + bp xp − β].
S(a, b, α, β) =
(x1 ,...,xp )∈A

Let us define over A the binary relation ≤A(b−a) as follow:
x ≤A(b−a) y if y − x ∈ A(b − a).
4

In [7] it is shown that ≤A(b−a) is an order relation. Moreover, from the results
in such a work, we also know that, if D is a system of generators of A(b − a) and
C = minimals≤A(b−a) A, then A = C + hDi. Furthermore, in [7] it is also given
an algorithm to compute C and D.
Let B ⊆ N. We will say that M is a B-monoid if M is a submonoid of
(N, +) fulfilling that (M \ {0}) + B ⊆ M .
It is clear that N is a B-monoid and that the intersection of B-monoids is
another B-monoid. Therefore, we can give the notion of smallest B-monoid
which contains a given set A of non-negative integers.
Theorem 3.1. With the above notation, let
[
[a1 c1 + · · · + ap cp + α, b1 c1 + · · · + bp cp − β]
C=
(c1 ,...,cp )∈C

and let
D=

[

[a1 d1 + · · · + ap dp , b1 d1 + · · · + bp dp ].

(d1 ,...,dp )∈D

Then S(a, b, α, β) ∪ {0} is the smallest D-monoid which contains C.
Proof. It is clear that S(a, b, α, β) ∪ {0} is a D-monoid which contains C. Now,
let us see that, if T is a D-monoid containing C, then S(a, b, α, β) ∪ {0} ⊆ T .
For that, we will prove that, if (x1 , . . . , xp ) ∈ A, then
[a1 x1 + · · · + ap xp + α, b1 x1 + · · · + bp xp − β] ⊆ T.

(3.1)

Let us suppose that D = {d1 , . . . , dq }, where di = (di1 , . . . , dip ) for all i ∈
{1, . . . , q}. Since (x1 , . . . , xp ) ∈ A, then there exist c ∈ C and λ1 , . . . , λq ∈ N
such that (x1 , . . . , xp ) = c+λ1 d1 +· · ·+λq dq . Now, in order to show (3.1), we use
induction over λ1 + · · ·+ λq following the reasoning exposed in Theorem 2.4.
At this moment, we propose to give an algorithm that allows us to compute
the smallest B-monoid containing a given set A.
Proposition 3.2. Let M be a submonoid of (N, +) and let A = {a1 , . . . , an } ⊆
N \ {0} be a system of generators of M . Then M is a B-monoid if and only if
A + B ⊆ M.
Proof. The necessary condition is trivial. So, let us see the sufficient one.
If m ∈ M \ {0}, then there exists (λ1 , . . . , λn ) ∈ Nn \ {(0, . . . , 0)} such that
m = λ1 a1 + · · · + λn an . Now, by induction over λ1 + · · · + λn , we will prove that
m + b ∈ M for all b ∈ B. Firstly, the result is trivially true for λ1 + · · · + λn = 1.
Let us suppose that λ1 + · · ·+ λn ≥ 2 and let i ∈ {1, . . . , n} such that λi 6= 0. By
the induction hypothesis, we easily deduce that (m − ai ) + b ∈ M . Therefore,
(m − ai ) + b + ai ∈ M and, consequently, m + b ∈ M .
If M is a submonoid of (N, +), we will denote by msg(M ) the minimal system
of generators of M .
5

Algorithm 3.3. INPUT: A finite set A of positive integers.
OUTPUT: The minimal system of generators for the smallest B-monoid
containing A.
(1) X = msg(hAi).
(2) Y = X ∪ (X + B).
(3) If msg(hY i) = X, then return X.
(4) Set X = msg(hY i) and go to (2).
By using Propositon 3.2, it is easy to see that the above algorithm operates suitably. On the other hand, observe that the most complex process in
Algorithm 3.3 is to compute msg(hY i), that is, compute the minimal system of
generators for a monoid starting from any system of generators of it. For this
purpose, we can use the GAP package numericalsgps (see [2]).
Example 3.4. By using Algorithm 3.3, we are going to compute the smallest
{2, 3}-monoid containing {5, 7}.
• X = {5, 7}.
• Y = {5, 7, 8, 9, 10}.
• msg(hY i) = {5, 7, 8, 9}.
• X = {5, 7, 8, 9}.
• Y = {5, 7, 8, 9, 10, 11, 12}.
• msg(hY i) = {5, 7, 8, 9, 11}.
• X = {5, 7, 8, 9, 11}.
• Y = {5, 7, 8, 9, 10, 11, 12, 13, 14}.
• msg(hY i) = {5, 7, 8, 9, 11} = X.
Therefore, h5, 7, 8, 9, 11i = {0, 5, 7, →} is the smallest {2, 3}-monoid containing
{5, 7}.
As a consequence of the previous results, we have an algorithm which allows
us to compute the minimal system of generators of the monoid S(a, b, α, β)∪{0}.
Algorithm 3.5. INPUT: a, b ∈ Np and α, β ∈ N such that (α, β) 6= (0, 0).
OUTPUT: The minimal system of generators of S(a, b, α, β) ∪ {0}.
(1) Compute a finite system of generators D for A(b − a).
(2) Compute C = minimals≤A(b−a) A, where
A = {(x1 , . . . , xp ) ∈ Np | (b1 − a1 )x1 + · · · + (bp − ap )xp ≥ α + β} .
S
(3) C = (c1 ,...,cp )∈C [a1 c1 + · · · + ap cp + α, b1 c1 + · · · + bp cp − β] and
S
D = (d1 ,...,dp )∈D [a1 d1 + · · · + ap dp , b1 d1 + · · · + bp dp ].
(4) Return the minimal system of generators of the smallest D-monoid containing C.
6

In Section 2, we have described an algorithmic process to compute D. At
the beginning of this section, we also have commented that, from the results of
[7], we have an algorithm to compute C. In order to give a self-contained paper
and to show examples without necessity of referencing to [7], we are going to
mention briefly how to build C. For that, we need to consider the following
equations and inequalities:
(b1 − a1 )x1 + · · · + (bp − ap )xp ≥ α + β,

(3.2)

(b1 − a1 )x1 + · · · + (bp − ap )xp − xp+1 − (α + β)xp+2 = 0,

(3.3)

(b1 − a1 )x1 + · · · + (bp − ap )xp ≥ 0.

(3.4)

The next result is a direct consequence of the results from [7, Section 2].
Proposition 3.6. Let A = {α1 , . . . , αt }, with αi = (αi1 , . . . , αip+2 ), be a system
of generators of the monoid formed by the set of non-negative solutions of (3.3).
Assume that α1 , . . . , αd are the elements in A with the last coordinate equal to
zero and αd+1 , . . . , αg are those elements in A with the last coordinate equal
to one. Let π : Np+2 → Np be the projection onto the first p coordinates.
Then the set of non-negative integer solutions of (3.2) is {π(αd+1 ), . . . , π(αg )}+
hπ(α1 ), . . . , π(αd )i. Moreover, A(b − a) = hπ(α1 ), . . . , π(αd )i.
An immediate consequence of the above proposition is the next result.
Corollary 3.7.

1. D = {π(α1 ), . . . , π(αd )}.

2. C = minimals≤A(b−a) {π(αd+1 ), . . . , π(αg )}.
Remark 3.8. Let us observe that it is really easy to determine C using (3.4). In
effect, let F = {(x1 , . . . , xp+2 ) ∈ Np+2 | (b1 − a1 )x1 + · · · + (bp − ap )xp − xp+1 −
(α+β)xp+2 = 0}. It is well known (see [5]) that F is a finitely generated monoid
of (Np+2 , +) and, in addition, its set of minimal generators coincide with the set
of minimal elements (with respect the usual order in Np+2 ) of F \ {(0, . . . , 0)}.
Moreover, from [3], we have that, if {(x1 , . . . , xp+2 ) is a minimal element of
F \ {(0, . . . , 0)}, then x1 + · · · + xp+2 ≤ |b1 − a1 | + · · · + |bp − ap | + α + β + 2.
Example 3.9. We are going to compute the minimal system of generators of
S = S (4, 5), (3, 6), 3, 1 ∪ {0} using Algorithm 3.5.
Let F = {(x1 , x2 , x3 , x4 ) ∈ N4 | −x1 + x2 − x3 − 4x4 = 0}. Having in mind
Remark 3.8, it is easy to see that

minimals F \ {(0, 0, 0, 0)} = {(1, 1, 0, 0), (0, 1, 1, 0), (0, 4, 0, 1)}.

Now, by Corollary 3.7, we have that D = {(1, 1), (0, 1)} and C = {(0, 4)}.
Consequently, D = [9, 9] ∪ [5, 6] = {5, 6, 9} and C = [23, 23] = {23}. Finally, by
applying Algorithm 3.3, the smallest {5, 6, 9}-monoid containing {23} is
S = {0, 23, 28, 29, 32, 33, 34, 35, 37, →}.
By the way, let us observe that S is the set of solutions for the example in the
introduction.
7

4

A brief remark on numerical semigroups

By Proposition 2.2, we know that S(a, b, α, β) ∪ {0} is a submonoid of (N, +).
On the other hand, we have that the sets of solutions in Examples 2.5, 3.4, and
3.9 are numerical semigroups (that is, a submonoid S of (N, +) such that N \ S
is finite). In the next example the answer is related with a monoid that is not
a numerical semigroup.

Example 4.1. Let us calculate S = S (4, 5), (3, 5), 0, 0 (observe that 0 ∈ S).
First, we need a system of generators for A(−1, 0) = {(x, y) ∈ N2 | −x+0y ≥ 0}.
For that, we compute the minimal elements of B(−1, 0) \ {(0, 0, 0)}, where
B(−1, 0) = {(x, y, z) ∈ N3 | −x + 0y − z = 0}. It is obvious that (0, 1, 0) is the
unique minimal element of B(−1, 0) \ {(0, 0, 0)} and, in consequence, {(0, 1)} is
a system of generators for A(−1, 0). Therefore, by applying Theorem 2.4, we
conclude that [5, 5] = {5} is a system of generators for S. Thus, S = h5i = 5N.
At this point, a question arise in a natural way: when is S(a, b, α, β) ∪ {0}
a numerical semigroup? In order to give an answer, we will study three cases.
Case 1. ai > bi for all i ∈ {1, . . . , r} and (α, β) ∈ N2 or ai ≥ bi for all
i ∈ {1, . . . , r} and (α, β) ∈ N2 \ (0, 0).
It is obvious that
a1 x1 + · · · + ap xp + α > b1 x1 + · · · + bp xp − β
for all (x1 , . . . xp ) ∈ Np . Thus, S(a, b, α, β) = ∅ and S(a, b, α, β) ∪ {0} = {0}
(that is, the trivial submonoid).
Case 2. ai ≥ bi for all i ∈ {1, . . . , r}, there exists i∗ ∈ {1, . . . , r} such that
ai∗ = bi∗ , and

 (α, β) = (0, 0).
If E = i ∈ {1, . . . , r} | ai = bi and I = i ∈ {1, . . . , r} | ai > bi , then it
is clear that E ∪ I = {1, . . . , r} and E ∩ I = ∅. On the other hand,
X
a1 x1 + · · · + ap xp ≤ b1 x1 + · · · + bp xp ⇔ 0 ≤
(bi − ai )xi .
i∈I

Since bi − ai < 0 for all i ∈ I and (x1 , . . . , xp ) ∈ Np , we have that the last
inequality is true if and only if xi = 0 for all i ∈ I. Therefore,
)
(
X
X
r
S(a, b, 0, 0) = n ∈ N
ai xi ≤ n ≤
bi xi for some (xi )i∈E ∈ N ,
i∈E

i∈E

P
P
where r is the cardinality of E. Now, since
i∈E bi xi for all
i∈E ai xi =
(xi )i∈E ∈ Nr , we conclude that S(a, b, 0, 0) is the submonoid generated by the
set A = {ai | i ∈ E}. In addition, S(a, b, 0, 0) will be a numerical semigruoup if
and only if gcd(A) = 1 (see [6, Lemma 2.1]).
Case 3. There exists j ∈ {1, . . . , r} such that aj < bj .
It is clear that (bj − aj )xj − β − α > 0 for a suitable choice of xj . Therefore,
the numerical semigroup generated by {aj xj + α, aj xj + α + 1} is a subset of
S(a, b, α, β) ∪ {0} which, in consequence, is also a numerical semigroup.
8

5

Conclusion

Starting from a real world situation, the aim of this work has been to compute
the set
)
(
a1 x1 + · · · + ap xp + α ≤ n ≤ b1 x1 + · · · + bp xp − β
,
S(a, b, α, β) = n ∈ N
for some (x1 , . . . xp ) ∈ Np
where a = (a1 , . . . , ap ), b = (b1 , . . . , bp ) ∈ Np and α, β ∈ N.
We have achieved our purpose in two steps. Firstly, we have studied the
case (α, β) = (0, 0). Secondly, by means of an algorithm, we have solved the
case (α, β) 6= (0, 0).
It is interesting to observe that, in general, S(a, b, α, β) ∪ {0} is a submonoid
of (N, +) and, in some cases, a numerical semigroup.

References
[1] F. Ajili, E. Contejean, Avoiding slack variables in the solving of linear diophantine equations and inequations, Theoretical Computer Science 173(1)
(1997), 183–208.

[2] M. Delgado, P. A. Garcı́a-Sánchez, and J. Morais. “numericalsgps”: a
GAP package on numerical semigroups.
(\protect\vrule width0pt\protect\href{http://www.gap-system.org/Packages/numericalsgps.h
[3] L. Pottier, Bornes et algorithme de calcul des générateurs des solutions de
systèmes diophantiens linéaires, C. R. Acad. Sci. Paris 311 (1990), 813–
816.
[4] A. M. Robles-Pérez, J. C. Rosales, Numerical semigroups in a problem
about cost-effective transport, Forum Math. 29(2) (2017), 329–345.
[5] J. C. Rosales and P. A. Garcı́a-Sánchez, Finitely generated commutative
monoids (Nova Science Publishers, New York, 1999).
[6] J. C. Rosales and P. A. Garcı́a-Sánchez, Numerical semigroups (Developments in Mathematics, vol. 20, Springer, New York, 2009).
[7] J. C. Rosales, P. A. Garcı́a-Sánchez, J. I. Garcı́a-Garcı́a and M. B. Branco,
Systems of inequalities and numerical semigroups, J. Lond. Math. Soc.
65(3) (2002), 611–623.

9

