Asymptotic ω-Primality of Finitely Generated Cancelative Commutative Monoids

Abstract

The computation of $\omega$-primality has been object of study, mainly, for numerical semigroups due to its multiple applications to the Factorization Theory. However, its asymptotic version is less well known. In this work, we study the asymptotic $\omega$-primality for finitely generated cancelative commutative monoids. By using discrete geometry tools and the Python programming language we present an algorithm to compute this parameter. Moreover, we improve the proof of a known result for numerical semigroups.

1. Introduction

Let S be a commutative, cancellative, reduced and finitely generated monoid. These conditions imply that S is isomorphic to a quotient of the form ${\mathbb{N}}^p/{\sim }_M$ for some positive integer p and some subgroup M of ${\mathbb{Z}}^p$ (see (Chapter 3 [1])). A monoid is called cancellative if for all $a,b,c\in S$ such that $a+c=b+c,$$a=b,$ and it is called reduced if $S\cap (-S)=\left\{0\right\}.$

Problems involving non-unique factorization in atomic monoids and integral domains have gathered much attention in the mathematical literature (see for instance [2] and the references therein). Let S be a monoid, the $\omega$-invariant, introduced in [3], 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 [3]) and it has been studied for several families of numerical semigroups (see, for instance, [5,6]). There are also several algorithms for its computation (see [7]).

Associated with the $\omega$-primality of an element a of a monoid S there is its asymptotic version, the asymptotic $\omega$-primality or $\overline{\omega }$-primality and denoted by $\omega \left(a\right)$. This parameter has been object of study in several works, for instance, in [8], the $\overline{\omega }$-primality is studied for numerical semigroups generated by two elements and it is given a formula for its computation, and, in [9], it is computed for numerical monoids, but no other studies provide methods to calculate this invariant for other types of monoids. Actually, the main goal of this work is being able to give such procedure to compute it. The asymptotic $\omega$-primality of a monoid S with set of atoms $\mathcal{A}\left(S\right)=\{a_1,\dots ,a_t\}$, denoted by $\overline{\omega }\left(S\right)$, is defined as the maximum of the set $\{\overline{\omega }\left(a_i\right)\mid a_i\in \mathcal{A}\left(S\right)\}$. The definition of $\overline{\omega }\left(a\right)$ is ${lim}_{n\to \infty }\omega \left(na\right)/n$. Thus, we give a method such that the $\omega$-primality of an element is computed using discrete sets of points, but to compute the $\overline{\omega }$-primality it is necessary to use continuous sets of points. Therefore, in this work, we see how to go from discrete to continuous sets and we give a method to compute this invariant in a huge class of finitely generated cancellative monoids. Futhermore, the method uses a partition of ${\mathbb{Q}}^p$ and performs its computations in each of these subsets independently. Thus, this method is suitable of being parallelized.

We would like to thanks to the team of [10] for its support on doing these computations.

2. Preliminaries and Notations

All monoids appearing in this work are commutative. For this reason, in the sequel we omit this adjective.

Let S be a commutative, cancellative, reduced (without units) and finitely generated monoid. By [1], there exists M a subgroup of ${\mathbb{Z}}^p$ such that S is isomorphic to ${\mathbb{N}}^p/{\sim }_M.$ For sake of simplicity, we will identify S with ${\mathbb{N}}^p/{\sim }_M$. This group is finitely generated and, since S has no units, it verifies that $M\cap {\mathbb{N}}^p=\left\{0\right\}$. Furthermore, every finitely abelian group M is isomorphic to a subgroup of ${\mathbb{Z}}_{d_1}\times \cdots {\mathbb{Z}}_{d_r}\times {\mathbb{Z}}^k$ where $d_i\in \mathbb{Z}$ and $d_i\mid d_{i+1}$. Therefore M is determined by a set of equations of the form:

$$\begin{array}{ccccccc}{a}_{11}{x}_1& +& \cdots & +& a_{1p}{x}_p& \equiv & 0,mod{d}_1,\hfill \\ & & ⋮& & \\ a_{r1}{x}_1& +& \cdots & +& a_{rp}{x}_p& \equiv & 0,mod{d}_r,\hfill \\ a_{(r+1)1}{x}_1& +& \cdots & +& a_{(r+1)p}{x}_p& =& 0,\hfill \\ & & ⋮& & \\ a_{(r+k)1}{x}_1& +& \cdots & +& a_{(r+k)p}{x}_p& =& 0,\hfill \end{array}$$

and, therefore, every monoid S is determined by the set of equations of M.

If $i\in \{1,\dots ,p\}$, then $e_i$ is the element of ${\mathbb{N}}^p$ having all its coordinates equal to zero except the ith which is equal to 1. For every $({\delta }_1,\dots ,{\delta }_p)\in {\mathbb{Q}}^p$ its length is denoted by $\left|\right|({\delta }_1,\dots ,{\delta }_p)\left|\right|={\sum }_{i=1}^p\left|{\delta }_i\right|$ and, as usual, we denote its maximum norm by $\left|\right|({\delta }_1,\dots ,{\delta }_p){\left|\right|}_{\infty }={max}_{i\in \{1,\dots ,p\}}\left\{\right|{\delta }_i\left|\right\}$. With this norm, we set the distance between two points in ${\mathbb{Q}}^p$ as $\mathrm{d}(x,y)=\left|\right|x-{y\left|\right|}_{\infty }$.

The usual cartesian product order ≤ on ${\mathbb{Q}}^p$ is defined as follows: $\lambda ,\mu \in {\mathbb{Q}}^p$ verify $\lambda \le \mu$ if and only if $\mu -\lambda \in {\mathbb{Q}}_{\ge }^p$. Another map we use is $\mathsf{\Pi }:{\mathbb{Q}}^p\to {\mathbb{Q}}_{\ge }^p$ defined as $\mathsf{\Pi }\left({\sum }_{i=1}^p{\lambda }_i{e}_i\right)={\sum }_{{\lambda }_i>0}{\lambda }_i{e}_i$, where $e_i$ is the element of ${\mathbb{Q}}^p$ having all its coordinates equal to zero except the ith which is equal to one.

Denote by $\phi :{\mathbb{N}}^p\to {\mathbb{N}}^p/{\sim }_M$ the projection map. For every $A\subset {\mathbb{N}}^p/{\sim }_M$ denote by $\mathsf{Z}\left(A\right)$ the set ${\phi }^{-1}\left(A\right)$. Since S is a reduced semigroup, for every $a\in S$, $\mathsf{Z}\left(\right\{a\left\}\right)$ is finite. For all $a\in S$ the set $\mathsf{Z}(a+S)$ is an ideal of ${\mathbb{N}}^p$, that is, if $x\in {\mathbb{N}}^p$ and $y\in \mathsf{Z}(a+S)$, then $x+y$ belongs to $\mathsf{Z}(a+S)$. Example 1 shows a graphical representation of the set $\mathsf{Z}(a+S)$.

Example 1. 

Let $S=\langle 5,7\rangle$ be a monoid and $100\in S$. Figure 1 represents the ideal $\mathsf{Z}(100+S)$.

Lemma 1. 

Let $a\in S={\mathbb{N}}^p/{\sim }_M$ and $\gamma \in \mathsf{Z}\left(a\right)$. The sets $\mathsf{Z}(a+S)$, $((\gamma +M)+{\mathbb{N}}^p)\cap {\mathbb{N}}^p$, $\mathsf{\Pi }((\gamma +M)+{\mathbb{N}}^p)$, and $\mathsf{\Pi }(\gamma +M)+{\mathbb{N}}^p$ are equal.

Proof. 

It is straightforward that $((\gamma +M)+{\mathbb{N}}^p)\cap {\mathbb{N}}^p=\mathsf{\Pi }((\gamma +M)+{\mathbb{N}}^p)=\mathsf{\Pi }(\gamma +M)+{\mathbb{N}}^p$.

Let $x\in \mathsf{Z}(a+S)$. There exists $\delta \in {\mathbb{N}}^p$ such that $x{\sim }_M\gamma +\delta$; therefore, $x-(\gamma +\delta )\in M$, and $\gamma +x-(\gamma +\delta )=x-\delta \in \gamma +M$. Since $x=(x-\delta )+\delta$ and $x\in {\mathbb{N}}^p$, x belongs to $((\gamma +M)+{\mathbb{N}}^p)\cap {\mathbb{N}}^p$.

Assume that $x\in ((\gamma +M)+{\mathbb{N}}^p)\cap {\mathbb{N}}^p$. This implies that there exists ${\gamma }^{\prime }\in \gamma +M$ and $\delta \in {\mathbb{N}}^p$ such that $x={\gamma }^{\prime }+\delta$. Thus $x{\sim }_M\gamma +\delta$, and since $\gamma +\delta \in \mathsf{Z}(a+S)$, x is also in $\mathsf{Z}(a+S)$.    □

Given a monoid S, we define the following binary relation:

$$a{⪯}_{S}b\mathrm{if}b=a+c\mathrm{for}\mathrm{some}c\in S.$$

Clearly ${⪯}_S$ is reflexive and transitive. Moreover, if $a{⪯}_{S}b$, then $a+c{⪯}_{S}b+c$ for all $c\in S$. With this notation, $a+S=\{b\in S\mid a{⪯}_{S}b\}$.

Factorization-theoretic notions are usually defined for multiplicative monoids, but we use additive notation for our aim. In this way, the notion of “divisibility” is the same as being “less than” with the order ${⪯}_S$. So, if $a,b\in S$, then a divides b (denoted by $a|b$) if and only if $a{⪯}_{S}b$.

An element $a\in S$ is called irreducible if there is no $b\in S$ fulfilling $b|a.$ The set of irreducible elements in S is denoted by $\mathcal{A}\left(S\right)$. When $\mathcal{A}\left(S\right)$ is the minimal generating set of S, the monoid S is atomic. In [11], it is proved that every finitely generated cancelative monoid is atomic. In this way, every concept concerning factorization properties such as the $\omega$-primality is well-defined for the monoids appearing in this work.

Definition 1 

(See Definition 1.1 [8]). Let S be an atomic monoid with set of units $S^{\times }$ and set of irreducibles $\mathcal{A}\left(S\right)$. For $s\in S\backslash S^{\times }$, we define $\omega \left(x\right)=n$ if n is the smallest positive integer with the property that whenever $x\left|\right(a_1+\dots +a_t)$, where each $a_i\in \mathcal{A}\left(S\right)$, there is a $T\subseteq \{1,2,\dots ,t\}$ with $\left|T\right|\le n$ such that $x|{\sum }_{k\in T}{a}_k$. If no such n exists, then $\omega \left(s\right)=\infty$. For $x\in S^{\times }$, we define $\omega \left(x\right)=0$.

The following result appearing (Proposition 3.3 [12]), and (Algorithm 16 [13]), give us the key for computing the $\omega$-primality in finitely generated monoids.

Lemma 2. 

Let $S={\mathbb{N}}^p/{\sim }_M$ be a finitely generated atomic monoid and $x\in S$. Then $\omega \left(x\right)$ is equal to $max\left\{\right|\left|\delta \right||\mid \delta \in {\mathrm{minimals}}_{\le }\left(\mathsf{Z}(x+S)\right)\}.$

We illustrate in an easy example how this lemma works.

Example 2. 

We continue with Example 1. In this case, we have that ${\mathrm{minimals}}_{\le }\left(\mathsf{Z}(100+S)\right)\}=\{(15,0),(6,10),(13,5),(20,0)\}$. The lengths of these points are 15, 16, 18 and 20, respectively. Therefore, $\omega \left(100\right)=20$.

The asymptotic version of the $\omega$-primarity is defined as follows.

Definition 2. 

Let S be an atomic monoid and$x\in S\backslash \left\{0\right\}$, then the asymptotic ω-primality of x is the limit $\overline{\omega }\left(x\right)={lim}_{n\to +\infty }\frac{\omega \left(nx\right)}{n}$.

By (Lemma 3.3 [14]), the function $\omega$ is subadditive, that is, $\omega (a+b)\le \omega \left(a\right)+\omega \left(b\right)$ for all $a,b\in S$. Thus, for every $n,m\in \mathbb{N}$, $\omega \left(\right(n+m\left)a\right)\le n\omega \left(a\right)+m\omega \left(b\right)$. Fekete’s Subadditive Lemma (see [15]) states that for every subadditive sequence $\left\{z_n\right|n=1,\dots ,\infty \}$, the limit ${lim}_{n\to \infty }\frac{z_n}{n}$ exists and it is equal to $inf\frac{z_n}{n}$ or $-\infty$. Since $\omega \left(x\right)\ge 0$ for every $x\in S\backslash \left\{0\right\}$, the limit $\overline{\omega }\left(x\right)={lim}_{n\to \infty }\frac{\omega \left(nx\right)}{n}$ always exists for all $x\in S.$ Besides, in (Lemma 3.3 [14]), it is proven that $\omega \left(\gamma \right)\le \omega (\gamma +{\gamma }^{\prime })\le \omega \left(\gamma \right)+\omega \left({\gamma }^{\prime }\right)$. Taking $\gamma ={\gamma }^{\prime }$ we have that $\omega \left(\gamma \right)\le \omega \left(2\gamma \right)\le 2\omega \left(\gamma \right)$.

The concept of asymptotic $\omega$-primality of an element can be expanded to the semigroup (see [3]).

Definition 3. 

Asymptotic ω-primality of S is defined as

$$\overline{\omega }\left(S\right)=sup\left\{\overline{\omega }\left(x\right)\right|x\in \mathcal{A}\left(S\right)\}.$$

Given$\mathcal{A}\left(S\right)=\{a_1,\dots ,a_p\}$the minimal generating set of$S,$$\overline{\omega }\left(S\right)$is equal to$max\left\{\overline{\omega }\left(a_i\right)\right|i\in \{1,\dots ,p\}\}$.

Next result proves that the congruence equations from the defining equations of M can be ignored.

Corollary 1. 

Let M and$M^{\prime }$ be two subgroups of ${\mathbb{Z}}^p$ with sets of defining equations

$$\left\{\begin{array}{ccccccc}{a}_{11}{x}_1& +& \cdots & +& a_{1p}{x}_p& \equiv & 0mod{d}_1,\hfill \\ & & ⋮& & \\ a_{r1}{x}_1& +& \cdots & +& a_{rp}{x}_p& \equiv & 0mod{d}_r,\hfill \\ a_{(r+1)1}{x}_1& +& \cdots & +& a_{(r+1)p}{x}_p& =& 0,\hfill \\ & & ⋮& & \\ a_{(r+k)1}{x}_1& +& \cdots & +& a_{(r+k)p}{x}_p& =& 0,\hfill \end{array}\right.$$

and

$$\left\{\begin{array}{ccccccc}{a}_{(r+1)1}{x}_1& +& \cdots & +& a_{(r+1)p}{x}_p& =& 0,\hfill \\ & & ⋮& & \\ a_{(r+k)1}{x}_1& +& \cdots & +& a_{(r+k)p}{x}_p& =& 0,\hfill \end{array}\right.$$

respectively. If $S={\mathbb{N}}^p/{\sim }_M$, $S^{\prime }={\mathbb{N}}^p/{\sim }_M^{\prime }$ and $\varphi :S^{\prime }⟶S$ such that $\varphi ({\left[x\right]}_{{\sim }_M^{\prime }})={\left[x\right]}_{{\sim }_M}$ then $\overline{\omega }({\left[x\right]}_{{\sim }_M^{\prime }})=\overline{\omega }({\left[x\right]}_{{\sim }_M})$.

Proof. 

Let k be the least common multiple of $d_1,\dots ,d_r$. Then $\overline{\omega }\left({\left[x\right]}_{{\sim }_M}\right)={lim}_{n\to +\infty }\frac{\omega \left(nx\right)}{n}={lim}_{n\to +\infty }\frac{\omega \left(nkx\right)}{nk}=\overline{\omega }({\left[x\right]}_{{\sim }_M^{\prime }}).$ □

3. Computing the Asymptotic $\mathbf{\omega }$-Primality

We introduce now some results that will allow us to show that the computation of the asymptotic $\omega$-primality can be done from some subsets of ${\mathbb{Q}}^p$ instead of some subsets of ${\mathbb{Z}}^p$ using tools of linear programming. For every $n\in \mathbb{N}$, if A is a set, we define $\frac{1}{n}A=\{\frac{a}{n}\mid a\in A\}$.

Assume that $a={\left[\gamma \right]}_{{\sim }_M}$, that is, $\gamma$ is an element in $\mathsf{Z}\left(a\right).$ By Lemma 1, $((\gamma +M)+{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p=\mathsf{Z}(a+S)$. Besides, for every $n\in \mathbb{N}$ the set $((n\gamma +M)+{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p$ is equal to $n(((\gamma +\frac{1}{n}M)+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p)$, and this implies that $\omega \left(na\right)/n$ coincides with

$$\begin{array}{c}(max\{\parallel x\parallel \mid x\in {\mathrm{minimals}}_{\le }n\left(\right((\gamma +\frac{1}{n}M)+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p)\left\}\right)/n=\\ max\{\parallel x\parallel \mid x\in {\mathrm{minimals}}_{\le }(\left(\right(\gamma +\frac{1}{n}M)+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p\left)\right\},\end{array}$$

(1)

and denoting $\left(\gamma +\frac{1}{n}M\right)$ by ${\mathrm{\Gamma }}^n$, then

$$\overline{\omega }\left(a\right)=\underset{n\to \infty }{lim}max\{\parallel x\parallel \mid x\in {\mathrm{minimals}}_{\le }(({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p)\}.$$

Define $\pi :{\mathbb{Q}}^p\to {\mathbb{Q}}_{\ge }^p$ as $\pi \left({\sum }_{i=1}^n{\lambda }_i{e}_i\right)={\sum }_{{\lambda }_i>0}{\lambda }_i{e}_i$. The set $({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p$ can be expressed as $\pi ({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)$. Furthermore, if $x\in {\mathrm{minimals}}_{\le }\left(\pi ({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\right)$, there exists $y\in {\mathrm{\Gamma }}^n$ such that $x=\pi \left(y\right)$. Thus,

$$\overline{\omega }\left(a\right)=\underset{n\to \infty }{lim}max\{\parallel x\parallel \mid x\in {\mathrm{minimals}}_{\le }\left(\pi \left({\mathrm{\Gamma }}^n\right)\right)\}.$$

Among the properties of ${\mathrm{\Gamma }}^n$, the following has to be marked:

• If $n_1$ divides $n_2$, then ${\mathrm{\Gamma }}^{n_1}\subset {\mathrm{\Gamma }}^{n_2}$ and $\mathsf{\Pi }\left({\mathrm{\Gamma }}^{n_1}\right)\subset \mathsf{\Pi }\left({\mathrm{\Gamma }}^{n_2}\right)$. Furthermore, by (Lemma 3.3 [14]), $\omega \left(na\right)/n\le \omega \left(a\right)$, which implies that $\overline{\omega }\left(a\right)\le \omega \left(a\right)$.
• If $n_1$ divides $n_2$, i.e., $n_2=k{n}_1$, applying again (Lemma 3.3 [14]), $\omega \left(n_{2}a\right)=\omega \left(k{n}_{1}a\right)\le k\omega \left(n_{1}a\right)$. Thus, $n_1\omega \left(n_{2}a\right)\le n_2\omega \left(n_{1}a\right)$ and therefore $\frac{\omega \left(n_{2}a\right)}{n_2}\le \frac{\omega \left(n_{1}a\right)}{n_1}$.
• For every n, ${\mathrm{\Gamma }}^n\subset \mathrm{\Gamma }$ and ${\cup }_{n\ge 1}{\mathrm{\Gamma }}^n=\mathrm{\Gamma }$. Besides, $\mathsf{\Pi }\left({\mathrm{\Gamma }}^n\right)\subset \mathsf{\Pi }\left(\mathrm{\Gamma }\right)$ and ${\cup }_{n\ge 1}\mathsf{\Pi }\left({\mathrm{\Gamma }}^n\right)=\mathsf{\Pi }\left(\mathrm{\Gamma }\right)$. Since $\mathsf{\Pi }\left({\mathrm{\Gamma }}^k\right)\subset \mathsf{\Pi }\left({\mathrm{\Gamma }}^{n!}\right)$ for every $k\le n$, we also have ${\cup }_{n\ge 1}\mathsf{\Pi }\left({\mathrm{\Gamma }}^{n!}\right)=\mathsf{\Pi }\left(\mathrm{\Gamma }\right)$.
• The sequence ${\left\{\frac{\omega (n!a)}{n!}\right\}}_{n\in \mathbb{N}}$ is decreasing.

For every subset $\mathrm{\Delta }$ of $\{1,\dots ,p\}$ define the set

$${\mathfrak{Q}}_{\mathrm{\Delta }}=\{(x_1,\cdots ,x_p)\in {\mathbb{Q}}^p\mid x_i\ge 0,\forall i\in \mathrm{\Delta },\mathrm{and}{x}_i\le 0\forall i\in \{1,\dots ,p\}\backslash \mathrm{\Delta }\}.$$

We use the following notation: for every $\mathrm{\Delta }\subset \{1,\dots ,p\}$, intersect ${\mathrm{\Gamma }}^n$ and ${\mathfrak{Q}}_{\mathrm{\Delta }}$ and denote ${\mathrm{\Gamma }}^n\cap {\mathfrak{Q}}_{\mathrm{\Delta }}$ by ${\mathrm{\Gamma }}_{\mathrm{\Delta }}^n.$ Also define $\pi :{\mathfrak{Q}}_{\mathrm{\Delta }}\to {\mathbb{Q}}_{\le }^p$ and consider $\pi \left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)$. Next proposition gives us more information about the minimals elements of the set $({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p$.

Proposition 1. 

The set${\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}\pi \left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)$ is a subset of $({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p$,

$${\mathrm{minimals}}_{\le }(({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p)\subset {\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}{\mathrm{minimals}}_{\le }\pi \left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right),$$

(2)

and

$$\begin{array}{c}\hfill {\mathrm{minimals}}_{\le }(({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p)={\mathrm{minimals}}_{\le }\left({\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}{\mathrm{minimals}}_{\le }\pi \left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)\right).\end{array}$$

(3)

Proof. 

We have that

$${\mathrm{minimals}}_{\le }\left({\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}{\mathrm{minimals}}_{\le }\pi \left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)\right)={\mathrm{minimals}}_{\le }\left({\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}\pi \left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)\right).$$

If $x\in {\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}\pi \left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)$, there exits $x^{\prime }\in {\mathrm{\Gamma }}_{\mathrm{\Delta }}^n$ such that ${\pi }_{\mathrm{\Delta }}\left(x^{\prime }\right)=x$. The difference $x-x^{\prime }$ verifies that all its coordinates are fractions of the form of $\frac{k}{n}$ with $k\in \mathbb{N}$; therefore, $x\in (x^{\prime }+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p\subset ({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p$.

Let x be an element of ${\mathrm{minimals}}_{\le }(({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p)$. There exists $y\in {\mathrm{\Gamma }}^n$ such that $y\le x$. Besides, there exists $\mathrm{\Delta }$ such that $y\in {\mathfrak{Q}}_{\mathrm{\Delta }}$. Since $x\in {\mathbb{Q}}_{\ge }^p$, we have ${\pi }_{\mathrm{\Delta }}\left(y\right)\le x$. Take $y^{\prime }\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)$ verifying $y^{\prime }\le {\pi }_{\mathrm{\Delta }}\left(y\right)$. Then, $y^{\prime }\le {\pi }_{\mathrm{\Delta }}\left(y\right)\le x$. Since ${\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)\subset ({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p$, $x=y^{\prime }$, and, thus, ${\mathrm{minimals}}_{\le }(({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p)\subset {\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}{\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)$.

Now, since ${\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}{\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)\subset ({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p$ and

$${\mathrm{minimals}}_{\le }(({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p)\subset {\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}{\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right),$$

we have

$${\mathrm{minimals}}_{\le }(({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p)={\mathrm{minimals}}_{\le }\left({\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}{\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)\right).$$

   □

The computation of ${\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)$ gives us the $\omega$-primality of a when $n=1$. Since for different values of n we obtain different ${\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)$, we have to study how these sets change when n changes. Moreover, as we are interested in getting the minimal elements of these sets we need to ensure that there exist a bounded region where these elements are found. In the following section, we see how this is solved for many cases using tools of Linear Programming.

4. Computing the Asymptotic $\mathbf{\omega }$-Primality

Let $\langle M\rangle$ be the vectorial subspace of ${\mathbb{Q}}^p$ generated by M. Note that the set $\gamma +\langle M\rangle$ is an affine variety (affine subspace) of ${\mathbb{Q}}^p$, and $\langle M\rangle$ is defined by the set of homogeneous equations of $M.$ Take into account the following considerations:

• For every $\mathrm{\Delta }$ the set ${\mathfrak{Q}}_{\mathrm{\Delta }}$ is a cone.
• The sets $\gamma +\langle M\rangle$ and ${\mathrm{\Gamma }}_{\mathrm{\Delta }}=(\gamma +\langle M\rangle )\cap {\mathfrak{Q}}_{\mathrm{\Delta }}\subset {\mathbb{Q}}^p$ are polyhedrons, and the projection ${\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$ is also a polyhedron.
• For every $n\in \mathbb{N}$, ${\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\subset {\mathrm{\Gamma }}_{\mathrm{\Delta }}$ and ${\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)\subset {\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$.
• In general, ${\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)$ is not a subset of ${\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$.

We illustrate these considerations in a couple of easy examples.

Example 3. 

Consider the monoid$S={\mathbb{N}}^2/{\sim }_M$with M the subgroup of${\mathbb{Z}}^2$generated by$\left\{\right(-10,11\left)\right\}$, and$\gamma =(15,0)$. The values of Δ are $\{{\mathrm{\Delta }}_1=\{1,2\},{\mathrm{\Delta }}_2=\left\{1\right\},{\mathrm{\Delta }}_3=\left\{2\right\},{\mathrm{\Delta }}_4=Ø\}$ and:

• ${\pi }_{{\mathrm{\Delta }}_1}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_1}^1\right)=\{(15,0),(5,11)\}$, and ${\pi }_{{\mathrm{\Delta }}_1}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_1}\right)$ is the segment $\overline{(15,0)(0,\frac{33}{2})}$.
• ${\pi }_{{\mathrm{\Delta }}_2}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_2}^1\right)=\{(15,0),(25,0),(35,0),\cdots \}$, and ${\pi }_{{\mathrm{\Delta }}_2}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_2}\right)$ is the ray with origin $(15,0)$.
• ${\pi }_{{\mathrm{\Delta }}_3}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_3}^1\right)=\{(0,22),(0,33),(0,44),\cdots \}$, and ${\pi }_{{\mathrm{\Delta }}_3}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_3}\right)$ is the ray with origin $(0,\frac{33}{2})$.
• ${\pi }_{{\mathrm{\Delta }}_4}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_4}^1\right)=Ø$, and ${\pi }_{{\mathrm{\Delta }}_4}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_4}\right)=Ø$.

Thus,

• ${\mathrm{minimals}}_{\le }{\pi }_{{\mathrm{\Delta }}_1}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_1}^1\right)=\{(15,0),(5,11)\}$, and${\mathrm{minimals}}_{\le }{\pi }_{{\mathrm{\Delta }}_1}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_1}\right)=\overline{(15,0)(0,\frac{33}{2})}$.
• ${\mathrm{minimals}}_{\le }{\pi }_{{\mathrm{\Delta }}_2}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_2}^1\right)=\left\{(15,0)\right\}$, and${\mathrm{minimals}}_{\le }{\pi }_{{\mathrm{\Delta }}_2}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_2}\right)=\left\{(15,0)\right\}$(the same set of minimals).
• ${\mathrm{minimals}}_{\le }{\pi }_{{\mathrm{\Delta }}_3}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_3}^1\right)=\left\{(0,22)\right\}$, and${\mathrm{minimals}}_{\le }{\pi }_{{\mathrm{\Delta }}_3}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_3}\right)=\left\{(0,\frac{33}{2})\right\}$(they are not equal).
• ${\mathrm{minimals}}_{\le }{\pi }_{{\mathrm{\Delta }}_4}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_4}^1\right)=Ø$, and${\mathrm{minimals}}_{\le }{\pi }_{{\mathrm{\Delta }}_4}\left({\mathrm{\Gamma }}_{{\mathrm{\Delta }}_4}\right)=Ø$.

Previous sets can be computed easily from Figure 2.

Example 4. 

Let S be the monoid${\mathbb{N}}^4/{\sim }_M$where M is given by the equations$x+y+z+t=0,-6x+7y+4z-3t=0$, and let γ be the factorization$(1,1,1,1)$. In this case, we have that${\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}{\mathrm{minimals}}_{\le }\pi \left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)=\{(0,0,20/3,0),(0,0,0,5),(4/5,0,16/5,0),(20/13,32/13,0,0),$$(0,0,0,8),(4/9,0,0,32/9)\}$but${\mathrm{minimals}}_{\le }(({\mathrm{\Gamma }}^n+\frac{1}{n}{\mathbb{N}}^p)\cap {\mathbb{Q}}_{\ge }^p)=\{(0,0,20/3,0),(0,0,0,5),$$(4/5,0,16/5,0),(20/13,32/13,0,0),(4/9,0,0,32/9)\}$.

Note that, in general, Equality (2) does not hold as Example 4 shows. Moreover, from Example 3, we have that ${\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)$ is not, in general, a subset of ${\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$. Since ${\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\subset {\mathrm{\Gamma }}_{\mathrm{\Delta }}$, it can only be assured that ${\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)\subset {\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$ and that for every $x\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)$ there exists $y\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$ such that $y\le x$. Now, we prove that increasing the value of n these sets of minimal elements get closer.

Theorem 1. 

For all$\mathrm{\Delta }\subset \{1,\dots ,p\}$and for all$ϵ>0$, there exists$n_0\in \mathbb{N}$such that if$n\ge n_0$and$x\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)$, then$\mathrm{d}(x,{minimals}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right))<ϵ$.

Proof. 

Let $\mathrm{\Delta }$ be a subset of $\{1,\dots ,p\},$ and x be a minimal element of ${\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)\subset {\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$. There exists $y\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$ such that $y\le x$. The set ${\pi }_{\mathrm{\Delta }}\left(M\right)$ is a finitely generated subgroup of $\{{\mu }_i{e}_i\mid {\mu }_i\in \mathbb{Z}\mathrm{and}{\mu }_i=0\forall i\notin \mathrm{\Delta }\}\cong {\mathbb{Z}}^{\left|\mathrm{\Delta }\right|}$ and ${\pi }_{\mathrm{\Delta }}{\left(M\right)}_{\ge }={\pi }_{\mathrm{\Delta }}\left(M\right)\cap \{{\mu }_i{e}_i\mid {\mu }_i\in \mathbb{N}\mathrm{and}{\mu }_i=0\forall i\notin \mathrm{\Delta }\}$ is a submonoid of ${\pi }_{\mathrm{\Delta }}\left(M\right)$. Since the monoid ${\pi }_{\mathrm{\Delta }}{\left(M\right)}_{\ge }$ is isomorphic to the intersection of a finitely generated group with ${\mathbb{N}}^{\left|\mathrm{\Delta }\right|}$, it is a finitely generated monoid. Assume that $\{s_1,\dots ,s_t\}$ is a system of generators of the monoid ${\pi }_{\mathrm{\Delta }}{\left(M\right)}_{\ge },$ so any $s_i$ is the projection of an element $s_i^{\prime }$ belonging to $M.$ The element x can be expressed as $x=y+{\sum }_{i=1}^t{\lambda }_i\frac{s_i}{n}$ with ${\lambda }_i\in {\mathbb{Q}}_{\ge }$. If for example ${\lambda }_1\ge 1$, we consider the element $z=x-\frac{s_1}{n}$. The element z verifies $y\le z\le x$. Since $s_1={\pi }_{\mathrm{\Delta }}\left(s_1^{\prime }\right)$ and $x={\pi }_{\mathrm{\Delta }}\left(x^{\prime }\right)$ for any $x^{\prime }\in {\mathrm{\Gamma }}_{\mathrm{\Delta }}^n$, the element z is equal to ${\pi }_{\mathrm{\Delta }}(x^{\prime }-\frac{s_1^{\prime }}{n})$, and belongs to ${\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)$. Thus, x is not minimal, which is a contradiction and therefore every minimal element of ${\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)$ can be expressed as $y+{\sum }_{i=1}^t{\lambda }_i\frac{s_i}{n}$ with $0\le {\lambda }_i<1$. This implies that, for every $ϵ>0$ if $n_0\left(\mathrm{\Delta }\right)=\frac{{\sum }_{i=1}^t\left|\right|s_i\left|\right|}{ϵ}$, then for every $n\ge n_0\left(\mathrm{\Delta }\right)$ and for every $x\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^n\right)$ we have $\mathrm{d}(x,{minimals}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right))<ϵ$.

Since the set $\mathrm{\Sigma }=\left\{\mathrm{\Delta }\right|\mathrm{\Delta }\subset \{1,\dots ,p\}\}$ is finite, the theorem is satisfied for $n_0=max\left\{n_0\left(\mathrm{\Delta }\right)\right|\mathrm{\Delta }\in \Sigma \}.$    □

Theorem 2. 

For every$y\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$, there exist$\sigma :\mathbb{N}\to \mathbb{N}$strictly increasing such that$y\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}({\mathrm{\Gamma }}_{\mathrm{\Delta }}^{\sigma \left(n\right)})$.

Proof. 

Assume that $y={\pi }_{\mathrm{\Delta }}\left(y^{\prime }\right)$. The element $y^{\prime }-\gamma$ belongs to $\langle M\rangle$. Fixed $\{m_1,\dots ,m_r\}$ a generating set of $M,$ there exist ${\lambda }_1,\dots ,{\lambda }_r\in \mathbb{Q}$ such that ${\sum }_1^r{\lambda }_i{m}_i=y^{\prime }-\gamma$. Let d be the least common multiple of the denominators of ${\lambda }_1,\dots ,{\lambda }_r$. The element $y^{\prime }$ belongs to $\gamma +\frac{1}{2^{n}d}M={\mathrm{\Gamma }}_{\mathrm{\Delta }}^{2^{n}d}$ for every n. Thus, $y\in {\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^{2^{n}d}\right)$. Since $y\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$ and ${\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^{2^{n}d}\right)\subset {\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$, the element y is in ${\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}({\mathrm{\Gamma }}_{\mathrm{\Delta }}^{\sigma \left(n\right)})$ with $\sigma \left(n\right)=2^{n}d$.    □

Following corollary gives us the main computational characterization of this work.

Theorem 3. 

Let$S={\mathbb{N}}^p/{\sim }_M$and$\gamma \in {\mathbb{N}}^p$. If the set

$${\mathfrak{M}}_{\gamma }={\mathrm{minimals}}_{\le }\left({\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}{\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)\right)$$

is equal to${\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}{\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right),$then

$$\overline{\omega }\left({\left[\gamma \right]}_{{\sim }_M}\right)=max\{\left|\right|x\left|\right|\mid x\in {\mathrm{minimals}}_{\le }({\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}{\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)\left)\right\}.$$

Proof. 

Recall that for every $x=(x_1,\dots ,x_p)\in {\mathbb{Q}}^p$, $\parallel x\parallel ={\sum }_1^p\left|x_i\right|$ and ${\left|\right|x\left|\right|}_{\infty }=max\left\{\right|x_i|\mid i\in \{1,\dots ,p\}\}$, and that for every $x,y\in {\mathbb{Q}}^p$, $\mathrm{d}(x,y)=\left|\right|x-{y\left|\right|}_{\infty }$. Using the triangle inequality, it is not hard to prove that if $x,y\in {\mathbb{Q}}^p$, then $|\parallel x\parallel -\parallel y\parallel |\le p·\mathrm{d}(x,y)$.

The sets ${\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$ are closed and bounded. The set

$${\mathfrak{M}}_{\gamma }={\mathrm{minimals}}_{\le }\left({\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}{\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)\right)$$

is closed subset of ${\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}{\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$, so it is also closed and bounded. For this reason, there exists $x_0\in {\mathfrak{M}}_{\gamma }$ such that $x_0$ has maximum length, that is $\parallel x_0\parallel =max\{\parallel x\parallel \mid x\in {\mathfrak{M}}_{\gamma }\}$. We also have that there exists $\mathrm{\Delta }\subset \{1,\dots ,p\}$ such that $x_0\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$, and by Theorem 2, there exist $\sigma :\mathbb{N}\to \mathbb{N}$ and $n_0\in \mathbb{N}$ such that $x_0\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^{\sigma \left(n\right)}\right)$ for every $n\ge n_0$. By Theorem 1, there exists $n_0^{\prime }$ such that for every $n\ge n_0^{\prime }$ and every $x\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^{\sigma \left(n\right)}\right)$, there exists $y\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$ such that $\mathrm{d}(x,y)<\frac{1}{n}.$ Thus, there exists $\tau :\mathbb{N}\to \mathbb{N}$ such that $x_0\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^{\tau \left(n\right)}\right)$ for every n, and for every $x\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^{\tau \left(n\right)}\right)$ there exists $y\in {\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$ verifying that $\mathrm{d}(x,y)<\frac{1}{n}$.

The sets ${\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}^{\tau \left(n\right)}\right)$ are finite; denote by $x_n$ the element having maximum length and by $y_n$ an element ${\mathrm{minimals}}_{\le }{\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$ verifying that $\mathrm{d}(x_n,y_n)<\frac{1}{n}$. Note that $\parallel x_0\parallel \le \parallel x_n\parallel$ and $\parallel y_n\parallel \le \parallel x_0\parallel$ for every $n\in \mathbb{N}$. Using the Equality (1), the sequence $\{\parallel x_n{\parallel \}}_{n\in \mathbb{N}}$ has limit and it is equal to $\overline{\omega }\left({\left[\gamma \right]}_{{\sim }_M}\right)$. Since $|\parallel x_n\parallel -\parallel y_n\parallel |\le p·\mathrm{d}(x_n,y_n)<p\frac{1}{n}$, the sequence $\{\parallel y_n{\parallel \}}_{n\in \mathbb{N}}$ also has limit equal to $\overline{\omega }\left({\left[\gamma \right]}_{{\sim }_M}\right)$. Using now that $\parallel y_n\parallel \le \parallel x_0\parallel \le \parallel x_n\parallel$, the limit $\overline{\omega }\left({\left[\gamma \right]}_{{\sim }_M}\right)$ is equal to $\parallel x_0\parallel$.    □

From the above results and under certain conditions, we are ready to give a method for computing the asymptotic $\omega$-primality of a given element of a cancellative monoid.

Algorithm 1 admits a parallel version because each of the needed computations for step 1 can be done as separate procedures. In [16], a Python implementation of this algorithm can be found.

Algorithm 1: Computing the asymptotic $\omega$-primality of an element.

Input: A system of generators of M and $\gamma \in {\mathbb{N}}^p$. Output: The asymptotic $\omega$-primality of ${\left[\gamma \right]}_{{\sim }_M},$$\overline{\omega }\left({\left[\gamma \right]}_{{\sim }_M}\right)$. For every $\mathrm{\Delta }\subset \{1,\dots ,p\}$ compute $V_{\mathrm{\Delta }}$ the set minimal vertices ${\pi }_{\mathrm{\Delta }}\left({\mathrm{\Gamma }}_{\mathrm{\Delta }}\right)$. Compute $V={\mathrm{minimals}}_{\le }{\cup }_{\mathrm{\Delta }\subset \{1,\dots ,p\}}{V}_{\mathrm{\Delta }}$. Return $\overline{\omega }\left({\left[\gamma \right]}_{{\sim }_M}\right)=max\left\{\right|\left|v\right||\mid v\in V\}$.

5. Two Particular Cases

In this section we focus on two particular cases that can be easily studied: $rank\left(M\right)=1$ and $rank\left(M\right)=p-1$.

5.1. Case $rank\left(M\right)=1$

Let v be the generator of M and $\left[\gamma \right]\in S$. Since $v=(v_1,\dots ,v_p)$ has, at least, a negative and a positive component, we can define the following Algorithm 2.

Algorithm 2: Computing the asymptotic $\omega$-primality of an element for the case $rank\left(M\right)=1$.

Input: v generator of M and $\gamma \in {\mathbb{N}}^p$. Output: The asymptotic $\omega$-primality of ${\left[\gamma \right]}_{{\sim }_M},$$\overline{\omega }\left({\left[\gamma \right]}_{{\sim }_M}\right)$ $\mathcal{I}=\{1,\dots ,p\}$, $W=Ø$, $v^{\prime }=v$. While all coordinates of $v\notin {\mathbb{N}}^p$:   (a) Compute the minimum $\lambda \in {\mathbb{Q}}_{\ge }$ such that there exist $i\in \mathcal{I}$ with ${\gamma }_i+\lambda v_i^{\prime }=0$. (b) Set $v_i^{\prime }=0$, $\mathcal{I}=\mathcal{I}\backslash \left\{i\right\}$ and $W=W\cup \{\gamma +\lambda v^{\prime }\}$. (c) $\mathcal{I}=\{1,\dots ,p\}$, $v^{\prime }=v$. (d) Repeat Step 2 and return $max\left\{\right|\left|w\right||\mid w\in W\}$.

5.2. Case $rank\left(M\right)=p-1$

If $rank\left(M\right)=p-1$, then S is a numerical semigroup. This kind of structures has been broadly studied (see for example [17]). In (Corollary 20 [9]), the authors state that if $S=\langle s_1<\cdots <s_q\rangle$ then $\overline{\omega }\left(s\right)=\frac{s}{s_1}$. Note that with our construction we get the same result, since in this kind of semigroups ${\mathrm{minimals}}_{\le }\left(\pi \left({\mathrm{\Gamma }}^n\right)\right)$ are the intersection of the hyperplane spanned by M and the axes. As M is defined as $m_1{x}_1+\cdots +m_n{p}_n=0$, then an element $s\in S$ is given by $m_1{x}_1+\cdots +m_n{p}_n=0$. Therefore, ${\mathrm{minimals}}_{\le }\left(\pi \left({\mathrm{\Gamma }}^n\right)\right)=\{\frac{s}{s_1}>\cdots >\frac{s}{s_q}\}$ and $\overline{\omega }\left(s\right)=\frac{s}{s_1}$.

6. Conclusions

We have generalize the known results about the asymptotic $\omega$-primality for any finitely generated commutative cancelative monoids. We have described a discrete geometric method using partitions ${\mathbb{Q}}^n\cap {\mathbb{N}}^n$ which can be used for computing other invariants. This method has allowed us to develop an algorithm for computing the $\omega$-primality for this kind of semigroups under some assumptions. Moreover, this method allowed us to proof a prevous known result in a more straightforward way.

7. Future Work

We are interested in being able to compute the asymptotic $\omega$-primality in all the possible cases not only under the hypotesis of Theorem 3. In order to achieve this goal, a possible strategy may be to study different families of cancelative monoids as it has been done for the $\omega$-primality.