arXiv:1307.5807v5 [math.AC] 9 Mar 2014

Computation of the ω-primality and asymptotic
ω-primality with applications to numerical
semigroups
J. I. Garcı́a-Garcı́a∗
M.A. Moreno-Frı́as†
A. Vigneron-Tenorio‡

Abstract
We give an algorithm to compute the ω-primality of finitely generated
atomic monoids. Asymptotic ω-primality is also studied and a formula to
obtain it in finitely generated quasi-Archimedean monoids is proven. The
formulation is applied to numerical semigroups, obtaining an expression
of this invariant in terms of its system of generators.
Keywords: Asymptotic ω-primality, commutative monoid, finitely
generated monoid, numerical semigroup, quasi-Archimedean monoid, ωprimality.
MSC-class: 20M14, 13A05 (Primaries), 13F15, 20M05 (Secondaries).

Introduction
All semigroups appearing in this paper are commutative. For this reason, in the
sequel we will omit this adjective. Here, an atomic monoid means a commutative
cancellative semigroup with identity element such that every non-unit may be
expressed as a sum of finitely many atoms (irreducible elements).
Problems involving non-unique factorizations in atomic monoids and integral
domains have gathered much recent attention in the mathematical literature (see
for instance [10] and the references therein). Let S be a monoid, the ω-invariant,
introduced in [8], is a well-established invariant in the theory of non-unique
factorizations, and appears also in the context of direct-sum decompositions
of modules [4]. This invariant essentially measures how far an element of an
integral domain or a monoid is from being prime (see [1]). In [7] it is proven that
the tame degree and ω-primality coincide for half-factorial affine semigroups and
∗ Departamento de Matemáticas, Universidad de Cádiz, E-11510 Puerto Real (Cádiz,
Spain). E-mail: ignacio.garcia@uca.es. Partially supported by the grant MTM2010-15595
and Junta de Andalucı́a group FQM-366.
† Departamento de Matemáticas, Universidad de Cádiz, E-11510 Puerto Real (Cádiz,
Spain). E-mail: mariangeles.moreno@uca.es. Partially supported by MTM2008-06201-C02-02
and Junta de Andalucı́a group FQM-298.
‡ Departamento de Matemáticas, Universidad de Cádiz, E-11405 Jerez de la Frontera (Cádiz, Spain). E-mail: alberto.vigneron@uca.es. Partially supported by the grant
MTM2007-64704 (with the help of FEDER Program), MTM2012-36917-C03-01 and Junta
de Andalucı́a group FQM-366.

1

in [2] and [7] the ω-primality is computed for some kinds of affine semigroups
(when the semigroup is the intersection of a group and Zp ). Associated with
the ω-primality there is its asymptotic version, the asymptotic ω-primality or
ω-primality, which is object of study in several works. In [3], the ω-primality is
studied for numerical semigroups generated by two elements and it is given a
formula for its computation, but no other studies provide methods to calculate
this invariant in other types of monoids.
Our study uses that every finitely generated commutative monoid is finitely
presented (see [13]). Thus, every monoid can be completely described in terms
of a finite set of relations and in case it is cancellative, the monoid is described
from a subgroup of Zp . The first goal of this work is to give an algorithm
to compute from a presentation of a finitely generated atomic monoid the ωprimality of any of its elements. Our second goal is for finitely generated quasiArchimedean cancellative monoids (note that every numerical semigroup belongs to this class of monoids). For them we give an explicit formulation of
the asymptotic ω-primality of its elements, and a method to compute their
asymptotic ω-primalities.
All the theoretical results of this work are complemented with the software
OmegaPrimality developed in Mathematica (see [6]). This software provides
functions to compute the ω-primality of a monoid and its elements from one of
its presentations or from a system of generators.
The contents of this paper are organized as follows. In Section 1, we provide
some basic tools and definitions that are used in the rest of the work. In Section
2, we recall the definitions of atomic monoid and ω-primality and we give an
algorithm to compute the ω-primality of an element. In Section 3, we start
by studying the ω-primality and the ω-primality in atomic monoids minimally
generated by two elements. Finally, Section 4 is devoted to give a formulation
of the ω-primality in quasi-Archimedean atomic monoids. We finish obtaining
the formulation of this invariant for numerical semigroups.

1

Preliminaries

Every finitely generated monoid S is isomorphic to a quotient of the form
Np /σ with σ a congruence on Np . Thus, if a ∈ S, it can be written as
a = [γ]σ with γ ∈ Np , where [γ]σ denotes the class of equivalence of γ.
We denote as {e1 , . . . , ep } the
Np and
Ppminimal generating set of the monoid
p
denote by k(δ1 , . . . , δp )k =
i=1 δi the length of (δ1 , . . . , δp ) ∈ N . Given
λ = (λ1 , . . . , λp ), µ = (µ1 , . . . , µp ) ∈ Zp , we define the usual cartesian product
order ≤ on Zp as λ ≤ µ if and only if µ−λ ∈ Np . If A ⊆ Np , define Minimals≤ A
as the set of the minimal elements with respect to the order ≤. Given two elements λ, µ ∈ Np , define λ ∨ µ = (max{λ1 , µ1 }, . . . , max{λp , µp }). For any L
subset of Rp , denote by L> the set {(x1 , . . . , xp ) ∈ L|xi > 0, i = 1, . . . , p} and
by L≥ the set {(x1 , . . . , xp ) ∈ L|xi ≥ 0, i = 1, . . . , p}.
Let a, b ∈ S. We say that a divides b when there exists c ∈ S such that
a + c = b, we denote it by a|b. The elements a, b ∈ S are associated if a|b and
b|a. When an element a ∈ S verifies that there exists b ∈ S such that a + b = 0,
then it is called a unit; the set of units of S is denoted by S × . An element x ∈ S
is an atom if it fulfills that x 6∈ S × and if a|x, then either a ∈ S × or a and x are
associated. If the semigroup S \ S × is generated by its set of atoms A(S), the

2

monoid S is called an atomic monoid. It is known that every non-group finitely
generated cancellative monoid is atomic (see [14, Corollary 16]).
A subset I of a monoid S is an ideal if I + S ⊆ I. It is straightforward to
prove that for every a ∈ S the set a + S = {a + c | c ∈ S} = {s ∈ S | a divides s}
is an ideal of S.

2

Computing the ω-primality in atomic monoids

In this section we show an algorithm to compute the ω-primality of an element in
a finitely generated atomic monoid from one of its presentations. The knowledge
of the computation of ω(a) for every atom a can be directly used to obtain ω(S)
(see [1, Definition 1.1]). There exist algorithms to compute ω in some kinds of
monoids, for instance in numerical monoids (see [3] and [2, Remark 5.9.1]), in
half-factorial affine semigroups (see [7]), in saturated affine semigroups (see [2,
Corollary 3.5]), but there is not a general method for its computation in more
general situations.
Definition 1. (See Definition 1.1 in [3].) Let S be an atomic monoid with set of
units S × and set of irreducibles A(S). For s ∈ S \S × , we define ω(x) = n if n is
the smallest positive integer with the property that whenever x|a1 +· · ·+a
Pt , where
each ai ∈ A(S), there is a T ⊆ {1, 2, . . . , t} with |T | ≤ n such that x| k∈T ak .
If no such n exists, then ω(s) = ∞. For x ∈ S × , we define ω(x) = 0.
Recall that every finitely generated monoid S is isomorphic to Np /σ, for
some congruence σ on Np and some positive integer p. For sake of simplicity,
we will identify S with Np /σ. Denote by ϕ : Np → Np /σ the projection map.
For every A ⊂ Np /σ denote by E(A) the set ϕ−1 (A). Note that for every a ∈ S
the set E(a + S) is an ideal of Np .
The following result is proven in [2, Proposition 3.3] for atomic monoids.
Proposition 2. Let S = Np /σ be a finitely generated atomic monoid and a ∈ S.
Then ω(a) is equal to max{kδk : δ ∈ Minimals≤ (E(a + S))}.
The set a + S collects all the multiples of a, and therefore in many cases
it is not a finite set. The problem now is to compute its minimal elements
with respect ≤ the usual cartesian product order on Np . A solution is given
by Algorithm 16 of [16] which computes the set Minimals≤ E(I) for every ideal
I of S. The following algorithm computes the ω-primality of an element of an
atomic monoid.
Algorithm 3. Input: A finite presentation of S = Np /σ and γ an element of Np
verifying that a = [γ]σ .
Output: ω(a).
(Step 1) Compute the set ∆ = Minimals≤ (E([γ]σ + S)) using [16, Algorithm
16].
(Step 2) Set Ψ = {kµk : µ ∈ ∆}.
(Step 3) Return max Ψ.

3

We illustrate now Algorithm 3 with some examples (all the computations
were done in an Intel Core i7 with 16 GB of main memory). Note that the
inputs in each example are the minimal generator set of the semigroup and an
element of the semigroup. The presentations and the expressions of the elements
in terms of the atoms are computed internally by the program.
Example
4. Let
S
be
the
affine
semigroup
generated
by
{(5, 3), (5, 11), (2, 7), (11, 4)}. To compute the ω-primality we use the package
OmegaPrimality developed for this work, which is available in [6]. For the
element (154, 118) we obtained the output
In[1]:= OmegaPrimalityOfElemAffSG[{154,118},
{{5,3}, {5,11}, {2,7}, {11,4}}]
The expression of the element is {3,5,2,10}
Length of output of Alg16=40
Out[1]= 68
In this case, an expression of (154, 118) is 3(5, 3) + 5(5, 11) + 2(2, 7) + 10(11, 4),
the size of Minimals≤ (E([γ]σ + S)) (the output of [16, Algorithm 16]) is equal
to 40 and the ω-primality of the element is 68.
In order to compare the timings obtained using Algorithm 3 and the
numericalsgps GAP package [12], which uses the method described in [2], we
consider the following examples. Note that the implementation of ω-primality
in the numericalsgps relies on the construction of Apéry set while our implementation is based on Gröbner basis calculations. In any case, the procedures
in the numericalsgps package only apply to numerical semigroups, while the
algorithm presented here applies also for any affine semigroup.
Example 5. Let S be the numerical semigroup generated by {115, 212, 333, 571}.
We use again the package OmegaPrimality obtaining for the element 10000 the
output
In[1]:= OmegaPrimalityOfElemAffSG[{10000},
{{115}, {212}, {333}, {571}}]
The expression of the element is {3,2,2,15}
Length of output of Alg16=203
Out[1]= 109
The timing was approximately 22 seconds and the value obtained for ω(10000) was equal to 109.
Using the function
OmegaPrimalityOfElementOfNumericalSemigroup of numericalsgps GAP
package we obtained
gap> OmegaPrimalityOfElementInNumericalSemigroup(10000,S);
109
with a timing of approximately 1389 seconds (and the same value for ω(10000)).
Example 6. The ω-primality of an atomic monoid S is defined as ω(S) =
sup{ω(x) | x is irreducible}. Hence, Algorithm 3 can be used to compute ω(S)
when S is atomic and finitely generated just computing the ω-primality of
its generators and taking the maximum. This is implemented in function
OmegaPrimalityOfAffSG:

4

In[2]:= OmegaPrimalityOfAffSG[{{115}, {212}, {333}, {571}}]
...
w-primalities of the generators: {15,36,36,36}
Out[2]= 36
In this case, the ω-primalities of the generators are 15, 36, 36 and 36, respectively, and this computation took 496 milliseconds. Via the numericalsgps
functions
gap> OmegaPrimalityOfNumericalSemigroup(S);
36
it took 1888 milliseconds.
Example 7. Consider the numerical semigroup S minimally generated by
{10, . . . , 19}. The package OmegaPrimality needed approximately 3779 milliseconds for computing ω(S),
In[1]:= OmegaPrimalityOfAffSG[{{10},{11},{12},{13},
{14},{15},{16},{17},{18},{19}}]
...
w-primalities of the generators: {2,3,3,3,3,3,3,3,3,3}
Out[1]= 3
while the numericalsgps functions took 125 milliseconds.
Example 8. Consider now S = h101, 111, 121, 131, 141, 151, 161, 171, 181, 191i,
its ω−primality was computed in approximately 135081 milliseconds,
In[1]:= OmegaPrimalityOfAffSG[{{101}, {111}, {121}, {131},
{141}, {151}, {161}, {171}, {181}, {191}}]
...
w-primalities of the generators: {12,23,22,22,22,22,22,22,22,22}
Out[1]= 23
and the numericalsgps functions took just 383949 milliseconds.
After some comparisons between the times required to obtain the ω-primality
using our implementation and numericalsgps, we can conclude that the larger
are the elements or generators, the better performance one gets with our procedure. But, if there are many generators and small, then one should use the
Apéry method.

3

Asymptotic ω-primality in monoids generated
by two elements

Let S be an atomic monoid and x ∈ S, define ω(x) = limn→+∞ ω(nx)
n
the asymptotic ω-primality of x. Asymptotic ω-primality of S is defined as
ω(S) = sup{ω(x)|x is irreducible} (see [1]). As in the preceding section if
S = hs1 , . . . , sp i, then ω(S) is equal to max{ω(si )|i = 1, . . . , p}.
In this section we focus our attention on cancellative reduced monoids minimally generated by two elements. These monoids are all isomorphic to monoids
of the form N2 /σ, and they are atomic (see [14]). The following result shows how
their congruences are. Note that in particular all numerical monoids generated
by two elements are monoids of this type.
5

Lemma 9. A non-free monoid S is cancellative, reduced and minimally generated by two elements if and only if S ∼
= N2 /σ with σ = h((α, 0), (0, β))i and
α, β > 1.
Proof. Assume that S is minimally generated by two elements. There exists
a congruence σ such that S ∼
= N2 /σ. From Propositions 3.6 and 3.10 in [17],
there exist positive integers a and b verifying that if (x, y)σ(x0 , y0 ) then a(x −
x0 ) + b(y − y0 ) = 0. Let M be the subgroup of Z2 defined by the equation
ax + by = 0. Then M = h(α, −β)i with α = b/d and β = a/d, with d =
gcd(a, b). Hence (x − x0 , y − y0 ) = k(α, −β) for some integer k, and thus
(x, y) = (x0 , y0 ) + k(α, −β). From this easily follows that σ = h((α, 0), (0, β))i.
Since S is not free, σ is not trivial and therefore with α, β 6= 0. Using now that
S is reduced and minimally generated by two elements we obtain that α, β > 1.
Assume now that S ∼
= N2 /σ with σ = h((α, 0), (0, β))i and α, β > 1. Using
that α, β > 1 it is straightforward to prove that S is minimally generated by
two elements and that S is reduced. We see that S is cancellative. For every
γ ∈ N2 , E([γ]σ ) = {γ + λ(α, −β)|λ ∈ Z} ∩ N2 . This implies that for all γ 0 ∈ N2 ,
we have γ σ γ 0 if and only if γ −γ 0 belongs to the subgroup G of Z2 generated by
(α, −β). Hence, the congruence σ is defined by a subgroup of Z2 and therefore
S is cancellative (see [17, Proposition 1.4]).
In order to compute the asymptotic ω-primality of an element [γ]σ ∈ S we
give explicitly Minimals≤ (E([γ]σ + S)) and ω([γ]σ ). Denote by b ab c the integer
part of ab with a, b ∈ N and b 6= 0.
Lemma 10. Let S = N2 /σ with σ = h((α, 0), (0, β))i and α, β > 1. Then for
all γ = (γ1 , γ2 ) ∈ N2 , E([γ]σ ) = {γ + λ(α, −β)|λ ∈ Z, −b γα1 c ≤ λ ≤ b γβ2 c},
Minimals≤ (E([γ]σ + S))
= Minimals≤ (E([γ]σ ) ∪ {(0, γ2 + (b

γ2
γ1
(1)
c + 1)β), (γ1 + (b c + 1)α, 0)})
α
β

and ω([γ]σ ) = max{γ2 + (b γα1 c + 1)β, γ1 + (b γβ2 c + 1)α}.
Proof. For every element γ the set E([γ]σ ) is equal to {γ +λ(α, −β)|λ ∈ Z}∩N2 .
Note that γ + λ(α, −β) ∈ N2 if and only if −b γα1 c ≤ λ ≤ b γβ2 c.
Using now that for every element z in [γ]σ + S there exists δ ∈ N2 such
that z = [γ + δ]σ , we obtain E([γ]σ + S) = ({γ + λ(α, −β)|λ ∈ Z} + N2 ) ∩ N2 .
To describe this set we need to obtain the intersection of E([γ]σ + S) with the
axes. These are the points (0, γ2 + (b γα1 c + 1)β) and (γ1 + (b γβ2 c + 1)α, 0). Thus
E([γ]σ + S) = (E([γ]σ ) + N2 ) ∪ ((0, γ2 + (b γα1 c + 1)β) + N2 ) ∪ ((γ1 + (b γβ2 c +
1)α, 0) + N2 ) and therefore (1) is satisfied.
The set {kxk ∈ N2 |x ∈ E([γ]σ )} is equal to {γ1 +γ2 +λ(α−β)|λ ∈ Z, −b γα1 c ≤
λ ≤ b γβ2 c}. If α ≥ β the maximum is achieved by the element γ + b γβ2 c(α, −β).
Using now that γ2 − b γβ2 cβ ≤ β, we obtain kγ + b γβ2 c(α, −β)k ≤ k(γ1 + (b γβ2 c +
1)α, 0)k. Analogously, if α ≤ β it can be proved that kγ − b γα1 c(α, −β)k ≤
k(0, γ2 +(b γα1 c+1)β)k. Hence, ω([γ]σ ) = max{γ2 +(b γα1 c+1)β, γ1 +(b γβ2 c+1)α}.
The proof of the above result can be used to compute the ω-primality of
any element of a numerical monoid generated by two elements. Let S be the
6

numerical monoid generated by x < y ∈ N and let z = ax + by ∈ S with (a, b) ∈
N2 . Take σ = h((α, 0), (0, β))i with lcm(x,y)
= α > β = lcm(x,y)
. It verifies that
x
y
2
S∼
= N /σ and, by Lemma 10, ω(z) = ω([(a, b)]σ ) = ||(a, b)+q(α, −β)+(α, −r)||
where b = βq + r with 0 ≤ r < β.
Example 11. Let us consider the congruence σ = h((7, 0), (0, 5))i and take γ =
(6, 7). In this case, the ideal E([γ]σ +S) is showed in Figure 1 and it is generated
by the elements {(0, 12), (6, 7), (13, 2), (20, 0)}. The ω-primality of [(6, 7)]σ is
15

10

5

5

10

15

20

25

Figure 1: E([(6, 7)]σ + N2 /σ).
equal to max{0 + 12, 6 + 7, 13 + 2, 20 + 0} = 20.
1
a
Lemma 12. For all a, b ∈ N with b 6= 0, it holds that limn→∞ b na
b cn = b .

Proof. For every n ∈ N, na can be expressed as na = bm + t with m ∈ N and
m→∞ a
1
bm+t
a
t
a
a
0 ≤ t < b. Hence, b na
b c n = b b c bm+t = bm + b c bm+t = m bm+t −→ b .
The following result gives us an explicit formulation of the ω-primality of
the elements of the monoids studied in this section.
Proposition 13. Let S = N2 /σ with σ = h((α, 0), (0, β))i and α, β > 1. If α ≥
β
β, then ω([(γ1 , γ2 )]σ ) = γ1 + α
β γ2 and if α < β, then ω([(γ1 , γ2 )]σ ) = α γ1 + γ2 .
Proof. Assume that α ≥ β (if α < β proceed similarly). By Lemma 10,
σ)
ω([γ]σ ) = γ1 + (b γβ2 c + 1)α. Thus, ω([γ]σ ) = limn→∞ ω(n[γ]
= limn→∞ (nγ1 +
n
2
2
(b nγ
c
+
1)α)/n.
Using
now
Lemma
12,
we
have
ω([γ]
)
=
γ
+ αγ
σ
1
β
β .
If α ≥ β, since ((α, 0), (0, β)) ∈ σ means that α[e1 ]σ = β[e2 ]σ , abusing of
σ +γ2 [e2 ]σ
2 ]σ
= γ1 + γ2 [e
the notation we could say that ω([γ]σ ) = [e[γ]1 ]σσ = γ1 [e1 ][e
[e1 ]σ =
1 ]σ
γ1 + γ2 α
β.
Corollary 14. Let S = N2 /σ be an reduced atomic monoid finitely generated
by two different elements and let σ = h((α, 0), (0, β))i a non-trivial congruence.
Then:
• If α ≥ β, then ω([e1 ]σ ) = 1 and ω(S) = ω([e2 ]σ ) =

α
β.

• If α < β, then ω([e2 ]σ ) = 1 and ω(S) = ω([e1 ]σ ) =

β
α.

7

Note that if ω([ei ]σ ) 6= 1, the elasticity of S is equal to ω([ei ]σ ) (see [14]).
The monoid S is a numerical monoid if and only if α and β are coprime. In
such case S ∼
= hα, βi.
In [3] the asymptotic ω-primality and ω-primality of numerical monoids generated by two elements is computed. In that paper it is also given the formulation of the ω-primality for two other families of numerical monoids (monoids
generated by {n, n + 1, . . . , 2n − 1} with n ≥ 3 and by {n, n + 1, . . . , 2n − 2} with
n ≥ 4). The approach proposed in this work allows us to obtain the same formulation for the ω-primality of an element, but it can be used in a more general
scope. For example, consider S to be the non-torsion free monoid given by the
presentation {((4, 0), (0, 2))}. Since 4 and 2 are not coprime, S is not a numerical
monoid. In this case, we have ω([e1 ]σ ) = 1 and ω(S) = ω([e2 ]σ ) = 42 = 2.

4

Asymptotic ω-primality in Archimedean semigroups

We start by introducing some basic concepts used in this section. An element
x 6= 0 of a monoid S is Archimedean if for all y ∈ S \ {0} there exists a positive
integer k such that y|kx. We say that S is quasi-Archimedean if the zero element
is not Archimedean and the rest of elements in S are Archimedean. If a monoid
is finitely generated, cancellative and quasi-Archimedean, then it verifies that
for all x, y ∈ S \ {0}, there exist positive integers p and q such that px = qy (see
[15, Theorem 2.1] or [11]). All monoids in Section 3, the submonoids of N and
in particular numerical semigroups are quasi-Archimedean.
Remark 15. If S is a quasi-Archimedean cancellative monoid, for all i = 2, . . . , p
there exist ai , bi ∈ N\{0} such that ai [e1 ]σ = bi [ei ]σ . Consider now a2 . . . ap [e1 ]σ ,
applying the above equalities we obtain that a2 . . . ap [e1 ]σ = b2 a3 . . . ap [e2 ]σ =
· · · = a2 . . . ap−1 bp [ep ]σ . For instance if S is the numerical semigroup generated
by 5, 7 and 11 we can take a1 = 7, b1 = 5, a2 = 11 and b2 = 5, obtaining that
77 · 5 = 55 · 7 = 35 · 11.
Let S be a quasi-Archimedean cancellative monoid. After rearranging its
minimal generators we obtain that there exist k1 ≥ · · · ≥ kp ∈ N \ {0} verifying
that k1 [e1 ]σ = · · · = kp [ep ]σ . In this way some elements of S can be expressed
using only the generator [e1 ]σ . Abusing again of the notation, we say that
Pp
Pp
[ei ]σ
[γ]σ
[ei ]σ
k1
k1
i=1 γi [e1 ]σ =
i=1 γi ki .
[e1 ]σ = ki and in the same manner that [e1 ]σ =
Theorem 18 proves that ω([γ]σ ) =
lemmas.

[γ]σ
[e1 ]σ .

In order to prove it, we need two

Pp
Lemma 16. Let k1 ≥ · · · ≥ kp ∈ N, γ
b ∈ Np , Γ be equal to {b
γ + i,j=1 µij (ki ei −
kj ej )|µij ∈ Z} and let Θ = {γ ∨ (γ + (k2 e2 − k1 e1 )) ∨ · · · ∨ (γ + (kp ep − k1 e1 ))|γ ∈
Γ}. The set I = {x ∈ Zp | there exists γ ∈ Γ such that x ≥ γ} is equal to
Zp \ {x ∈ Zp | there exists φ ∈ Θ such that xi < φi for all i = 1, . . . , p}.
Proof. Let G be the subgroup of Zp spanned by {k2 e2 − k1 e1 , . . . , kp ep − k1 e1 }.
Then Γ = γ
b +G and I = Γ+Np . An element x is in I if and only if x−b
γ ∈ G+Np .
p
Also a + (b ∨ c) = (a + b) ∨ (a + c) for all a, b, c ∈ Z . For this reason, we may
assume without loss of generality that γ
b = 0.

8

Take x = (x1 , . . . , xp ) ∈ Zp . For every i ∈ {2, . . . , p} let qi , ri ∈ Z
such P
that xi = ki qi + ri , with 0 ≤ ri < ki (division algorithm). Set y =
p
(−k1 i=2 qi , q2 k2 , . . . , qp kp ) andPy 0 = y∨(y+k2 e2 −k1 e1 )∨· · ·∨(y+kp ep −k1 e1 ).
p
ThenPy ∈ G and y 0 = (−k1 i=2 qi , (q2 + 1)k2 , . . . , (qp + 1)kp ) ∈ Θ. If
p
−k1 i=2 qi ≤ x1 , then y ≤ x and thus x ∈ G + Np . Otherwise, x < y 0 ∈ Θ.
Lemma 17. Let S = Np /σ = hs1 , . . . , sp i be a cancellative monoid with σ a
congruence, let k1 ≥ · · · ≥ kp ∈ N be such that k1 s1 = · · · = kp sp and let γ ∈ Np .
Then every element x = (x1 , . . . , xp ) ∈ Np \ {0} fulfilling that
p
X
k1 · · · kp
i=1

ki

xi ≥ (p − 1)k1 · · · kp +

p
X
k1 · · · kp
i=1

ki

γi

(2)

belongs to E([γ]σ + S).
Proof. Assume that x ∈ Np verifies (2). Take γ
b = γ and Γ, Θ and I as in Lemma
16. It is easy to prove that for every element in Θ equality in (2) holds, and
thus, by Lemma 16, x ∈ I. This implies that there exist γ 0 ∈ Γ and y ∈ Np such
that x = P
γ 0 + y. Since γ 0 ∈ Γ, there exist µij ∈ Z with
Ppi, j ∈ {1, . . . , p} such that
p
0
γ = γ + i,j=1 µij (ki ei − kj ej ). Thus, γ + y = x + i,j=1 µij (ki ei − kj ej ) ∈ Np .
Since S is cancellative there exists G a subgroup of Zp such that for every
a, b ∈ Np , a σ b if and only if a − b ∈ G
Pp(see [17, Proposition 1.4]). Using this
fact and that ki ei σ kj ej , we have that i,j=1 µij (ki ei − kj ej ) ∈ G and therefore
Pp
x σ x + i,j=1 µij (ki ei − kj ej ) = γ + y. Hence, x ∈ E([γ]σ + S).
Theorem 18. Let S = Np /σ be a quasi-Archimedean cancellative reduced
monoid. There exists a rearrange {t1 , . . . , tp } of the set {1, . . . , p} such that
Pp k γ
ω(a) = γt1 + i=2 tk1t ti for every a = [(γ1 , . . . , γp )]σ ∈ S.
i

Proof. By [9, Lemma 3.3], ω(a+b) ≤ ω(a)+ω(b) for all a, b ∈ S. Thus, for every
n, m ∈ N and every a ∈ S, ω((n + m)a) ≤ nω(a) + mω(a). Fekete’s Subadditive
Lemma (see [5]) states that for every subadditive sequence {zn |n = 1, . . . , ∞},
the limit limn→∞ znn exists and it is equal to inf znn or −∞. Since ω(a) ≥ 0 for
every a ∈ S \ {0}, the limit ω(a) = limn→∞ ω(na)
always exists for all a ∈ S.
n
Without loss of generality we can assume that there exist k1 ≥ · · · ≥ kp ∈
N \ {0} verifying k1 [e1 ]σ = · · · = kp [ep ]σ . Then for all γ = (γ1 , . . . , γp ) ∈ Np , it
holds that k2 · · · kp [γ]σ = k2 · · · kp γ1 [e1 ]σ + · · · + k2 · · · kp γp [ep ]σ = (γ1 k2 · · · kp +
Pp k ···k
k1 γ2 k3 · · · kp + · · · + k1 . . . kp−1 γp )[e1 ]σ = [( i=1 1 ki p γi , 0, . . . , 0)]σ .
Let a = [γ]σ ∈ S with γ ∈ Np . Denote by H the hyperplane of
p
Q spanned by {k1 e1 − ki ei |i = 2, . . . , p}; H is defined by the equation
Pp k1 ···kp
i=1
ki xi = 0. It is straightforward to prove that E([γ]σ ) ⊆ Hγ where
Pp k1 ···kp
Hγ is the affine subvariety of Qp defined by the equation
i=1
ki xi =
Pp k1 ···kp
k1 ···kp
k1 ···kp
Using now that 0 ≤
≤ ··· ≤
and that
i=1
ki γi .
k
kp
Pp k1 ···k
Pp 1
p
p
i=1
i=1 xi |(x1 , . . . , xp ) ∈ Hγ ∩ Q≥ } is
ki γi ≥ 0 we deduce that max{
P
k ···k
p
1
achieved by the element k2 ···k
( i=1 1 ki p γi , 0, . . . , 0). For the elements of
p
the form nk2 · · · kp [γ]σ with n ∈ N \ {0} its maximum is achieved by the elPp k ···k
Pp k ···k
1
ement nk2 · · · kp k2 ···k
( i=1 1 ki p γi , 0, . . . , 0) = n( i=1 1 ki p γi , 0, . . . , 0) ∈
p

9

Np , which clearly verifies that
p
X
k1 · · · kp
nk2 · · · kp [γ]σ = [n(
γi , 0, . . . , 0)]σ .
ki
i=1

Using
S is cancellative and reduced, it is easy to prove that
Pp that
k ···k
Thus,
n( i=1 1 ki p γi , 0, . . . , 0) ∈ Minimals≤ (E(nk2 · · · kp [γ]σ + S)).
Pp k ···k
Pp k ···k
ω(nk2 · · · kp [γ]σ ) ≥ kn( i=1 1 ki p γi , 0, . . . , 0)k = n i=1 1 ki p γi . Since the
σ)
limit ω(a) = limn→∞ ω(n[γ]
exists and every subsequence converges to the
n
same limit. Therefore,

Pp k ···k
n i=1 1 ki p γi
ω(n[γ]σ )
ω(nk2 · · · kp [γ]σ )
ω(a) = lim
= lim
≥ lim
n→∞
n→∞
n→∞
n
nk2 · · · kp
nk2 · · · kp
nk1 k2 · · · kp (γ1 /k1 + · · · + γp /kp )
= lim
= k1 (γ1 /k1 + · · · + γp /kp ).
n→∞
nk2 · · · kp
Obtaining in this way a lower bound for ω(a).
We now prove that the equality holds.
By Lemma 17, every elePp k1 ···k
p
ment (x1 , . . . , xp ) ∈ Np verifying that
i=1
ki xi ≥ (p − 1)k1 · · · kp +
Pp
k ···k
n 1 ki p γi belongs to E(n[γ]σ + S). Thus, every element fulfilling
Ppi=1 k1 ···k
Pp
k1 ···kp
p
i=1
i=1 n ki γi also belongs to E(n[γ]σ +
ki (xi −1) ≥ (p−1)k1 · · · kp +
S), but does not belong to Minimals≤ (E(n[γ]σ + S)). Therefore, the elements
of Minimals≤ (E(n[γ]σ + S)) satisfy the inequality
p
X
k1 · · · kp
i=1

ki

xi ≤

p
X
k1 · · · kp
i=1

ki

+ (p − 1)k1 · · · kp +

p
X
k1 · · · kp
n
γi .
ki
i=1

(3)

Hence,
the
set
Minimals≤ (E(n[γ]σo + S))
is
included
n
p
(x1 , . . . , xp ) ∈ Q≥ : (x1 , . . . , xp ) satisfies (3) and for this reason
ω(n[γ]σ ) ≤ sup{k(x1 , . . . , xp )k : (x1 , . . . , xp ) ∈ Qp≥ and satisfies (3)}.
Using that the coefficients of the left-hand side of (3) verify that 0 ≤
··· ≤

k1 ···kp
kp ,

in

(4)

k1 ···kp
k1

≤

it is straightforward to prove that for every d ∈ Q the set
Pp k ···k
{(x1 , . . . , xp ) ∈ Qp≥ : i=1 1 ki p xi = d} is nonempty if and only if d ≥ 0. BePp k1 ···kp
sides, the maximum of {k(x1 , . . . , xp )k : (x1 , . . . , xp ) ∈ Qp≥ and
i=1
ki xi =
d} is achieved by the element (d/(k2 · · · kp ), 0, . . . , 0), it is equal to d/(k2 · · · kp ),
and if we increase d, then it increases. Since the right-hand side of (3) is greater
than zero, we deduce that the supreme of (4) is achieved by an element of Qp≥
fulfilling that equality in (3) holds and having all its coordinates equal to zero
but the first one. That point is equal to nξ with
!
Pp k1 ···kp
Pp k1 ···kp
(p − 1)k1
i=1
i=1
ki
ki γi
+
+
, 0, . . . , 0 ∈ Qp≥
ξ=
nk2 · · · kp
n
k2 · · · kp

10

and it verifies that ω(n[γ]σ ) ≤ knξk. Therefore,
ω(a) = lim

n→∞
Pp

ω(n[γ]σ )
knξk
≤ lim
n→∞ n
n

i=1

= lim

n→∞

k1 ···kp
ki

k2 ···kp

+

(p−1)k1
1

Pp

+n

n

i=1

k1 ···kp
ki

k2 ···kp

γi

Pp
=

i=1

k1 ···kp
ki γi

k2 · · · kp

= k1 (γ1 /k1 + · · · + γp /kp ).

Corollary 19. Let S = Np /σ be a quasi-Archimedean cancellative reduced
max{k1 ,...,kp }
monoid. There exist k1 , . . . , kp ∈ N such that ω([ei ]σ ) =
for all
ki
i = 1, . . . , p.
As we pointed out in the abstract, we give a formula to compute the ωprimality in numerical semigroups.
Corollary 20. Let S be a numerical monoid minimally generated by hs1 < s2 <
· · · < sp i. For every s ∈ S, we have that ω(s) = ss1 .
Pp
Proof. Use that there exist γ1 , . . . , γp ∈ N such that s = i=1 γi si and take
lcm(s1 ,...,sp )
.
ki =
si

References
[1] D.F. Anderson and S. T. Chapman, How far is an element from being
prime. J. Algebra Appl. 9 (2010), no. 5, 779–789.
[2] V. Blanco, P. A. Garcı́a-Sánchez and A. Geroldinger, Semigrouptheoretical characterizations of arithmetical invariants with applications to
numerical monoids and Krull monoids. Illinois J. Math. 55 (2011), no. 4,
1385–1414.
[3] D.F. Anderson, S.T. Chapman, N. Kaplan, and D. Torkornoo,
An algorithm to compute ω-primality in a numerical monoid. Semigroup
Forum 82 (2011), no. 1, 96–108.
[4] L. Diracca, On a generalization of the exchange property to modules with
semilocal endomorphism rings. J. Algebra 313 (2007), 972–987.
[5] M. Fekete, Uber die Verteilung der Wurzeln bei gewissen algebraischen
Gleichungen mit. ganzzahligen Koeffizienten. Mathematische Zeitschrift 17
(1923), 228–249.
[6] J.I. Garcı́a-Garcı́a, A. Vigneron-Tenorio. OmegaPrimality, a package for computing the omega primality of finitely generated atomic monoids.
Handle: http://hdl.handle.net/10498/15961 (2014).
[7] P.A. Garcı́a Sánchez, I. Ojeda and A. Sánchez-R-Navarro, Factorization invariants in half-factorial affine semigroups. J. Algebra Comput. 23 (2013), 111–122.

11

[8] A. Geroldinger, Chains of factorizations in weakly Krull domains. Colloquium Mathematicum 72 (1997), 53–81.
[9] A. Geroldinger and W. Hassler, Local tameness or v-Noetherian
monoids. J. Pure Applied Algebra 212 (2009), 1509–1524.
[10] A. Geroldinger and F. Halter-Koch, Non-unique factorizations. Algebraic, combinatorial and analytic theory. Pure and Applied Mathematics
(Boca Raton) 278, Chapman & Hall/CRC, 2006.
[11] R. G. Levin, On commutative, nonpotent, archimedean semigroups. Pacific J. Math. 27 (1968), 365–371.
[12] M. Delgado, P. A. Garcı́a-Sánchez, J. Morais, ”NumericalSgps”:
a GAP package for numerical semigroups, http://www.gap-system.org/
Packages/numericalsgps.html
[13] L. Redéi, The theory of finitely generated commutative monoids. Pergamon, Oxford, Edinburgh, New York, 1965.
[14] J. C. Rosales, P. A. Garcı́a-Sánchez, and J. I. Garcı́a-Garcı́a,
Atomic commutative monoids and their elasticity. Semigroup Forum 68
(2004), 64–86.
[15] J. C. Rosales and J. I. Garcı́a-Garcı́a, Hereditary archimedean commutative semigroups. Intern. Math. Journal 5 (2002), 467–472.
[16] J. C. Rosales, P. A. Garcı́a-Sánchez, and J. I. Garcı́a-Garcı́a,
Irreducible ideals of finitely generated commutative monoids. J. Algebra
238 (2001), 328–344.
[17] J.C. Rosales, P.A. Garcı́a-Sánchez, Finitely generated commutative
monoids. Nova Science Publishers, Inc., New York (1999).

12

