Printer Friendly

On the Frobenius vector of some simplicial affine semigroups.

1 Introduction and basic notions

The set of nonnegative integers will be denoted by N. An affine semigroup is a finitely generated submonoid of Nr for some positive integer r. Let S = <[a.sub.1, ... ,[a.sub.r+m]> be an affine semigroup generated by A = {[a.sub.1], ... , [a.sub.r+m]} C [N.sup.r], that is to say, S = [Na.sub.1] + [Na.sub.2] + ... + [Na.sub.r+m]. In such a case, A will be said to be a system of generators of S. Moreover, if no proper subset of A generates S, the set A is a minimal system of generators of S. Every affine semigroup has a unique minimal system of generators (see [9, Chapter 3]). Let K be a field. The ring K[S] is defined as the subalgebra of K[[y.sub.1], ... ,[y.sub.r]] generated by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The semigroup S is said to be Cohen-Macaulay (Gorenstein) if K[S] is. Let IS, called the semigroup ideal of S, be the kernel of K-algebra homomorphism from K[[x.sub.1], ... ,[x.sub.r+m]] to K[S] defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we define the S-degree of the monomial [x.sup.u] by [[SIGMA].sup.r+m.sub.i=1] [u.sub.i] [a.sub.i] and denote by [deg.sub.S] ([x.sup.u]). The semigroup S is said to be complete intersection if [I.sub.S] is a complete intersection ideal. It is well-known that IS is a binomial prime ideal ([5, Proposition 1.4]). When r = 1 and [a.sub.1], ... ,[a.sub.m+1] are relatively prime positive integers, the semigroup is called numerical semigroup. In this case N S is a finite set. For a numerical semigroup S the largest integer f* (S) in N \ S is called the Frobenius number of S, and the problem of finding this number is called the Frobenius problem. The Frobenius number occurs in many branches of mathematics and is one of the most studied invariants in the theory of numerical semigroups. This problem has attracted substantial attention in the last 100+ years (see [4], [7], [8]). There is no general formula for the Frobenius number for m greater than one. Sylvester in [14] proved that for m = 1, f* (S) = [a.sub.1] [a.sub.2] - [a.sub.1] - [a.sub.2].

The Frobenius problem is generalized to the higher dimensional cases (see [1], [2], [15], [16]). The vector Frobenius problem of Cohen-Macaulay and Gorenstein simplicial affine semigroup is studied in the next section. It is shown that every simplicial affine semigroup has at least one minimal Frobenius vector and an algorithm is presented for computing minimal Frobenius vectors of some Cohen-Macaulay simplicial affine semigroup.

2 Frobenius vector

Let S be the affine semigroup generated by A = {[a.sub.1], ... ,[a.sub.r+m]} in [N.sup.r] and G(S) be the group generated by S in [Z.sup.r], that is, G(S) = {a--b|a, b [member of] S} . We use G([a.sub.1], ... ,[a.sub.n]) to denote the group generated by {[a.sub.1], ... ,[a.sub.n]}.

Definition 1. The affine semigroup S is called simplicial if there exist [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that

(1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are linearly independent over Q and

(2) for every a [member of] S, there exists 0 [not equal to] n [member of] N such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If r is lesser than three, every affine semigroup is simplicial. From now on, we will suppose that S is a simplicial affine semigroup. Assume without loss of generality that {[i.sub.1], ... ,[i.sub.r]} = {1, ... ,r}. The Apery set of a [not equal to] 0 in S is defined as Ap(S, a) = {x [member of] S|x - a [not member of] S}. Let [k.sub.i] be the smallest natural number such that [k.sub.i] [a.sub.r+i] [member of] [[SIGMA].sup.r.sub.i=1] [Na.sub.i], for i = 1, ... m. By definition,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so [[intersection].sup.r.sub.i=1] Ap(S,[a.sub.i]) is finite. The set [[intersection].sup.r.sub.i=1] Ap(S,[a.sub.i]) is also called the Apery set of S relative to E := {[a.sub.1], ... ,[a.sub.r]}. Observe that Ap (S, E) := {s [member of] S | s - e [not member of] S, [for all]e [member of] E} = [[intersection].sup.r.sub.i=1] Ap (S,[a.sub.i]). The set {[x.sup.[alpha]]|[deg.sub.S] ([x.sup.[alpha]]) [member of] Ap(S,E)} is a basis for K [[x.sub.1], ... ,[x.sub.r+m]]/<[I.sub.S], [x.sub.1], ... ,[x.sub.r]> as a K-vector space.

The following proposition gives a useful criterion for determining whether or not a simplicial affine semigroup is Cohen-Macaulay (see [11, Corollary 1.6]).

Proposition 1. If S is a simplicial affine semigroup, the following statements are equivalent:

* K[S] is Cohen-Macaulay;

* For all [[omega].sub.1],[[omega].sub.2] [member of] Ap(S, E), if [[omega].sub.1] [not member of] [[omega].sub.2], then [[omega].sub.1] - [[omega].sub.2] [not member of] G ([a.sub.1], ... , [a.sub.r]).

By definition, every element a [member of] S can be written as a = [[SIGMA].sup.r.sub.i=1] [[alpha].sub.1] [[alpha].sub.1] + [omega], with [omega] [member of] Ap(S,E) and [[alpha].sub.i] [member of] N, i = 1, ... ,r. Let a = [[SIGMA].sup.r+m.sub.i=1] [z.sub.i] [a.sub.i] [member of] G(S) and [z.sub.k] < 0 for some k [member of] {r + 1, ... ,r + m}. Since S is simplicial, there exists [n.sub.k] [member of] N such that ([n.sub.k] - [z.sub.k])[a.sub.k] [member of] [N.sub.a1] + ... + [N.sub.ar]. So a = [[SIGMA].sup.r+m.sub.i=1,i[not equal to] k] [z.sub.i] [a.sub.i] + ([z.sub.k] - [n.sub.k])[a.sub.k] + [n.sub.k] [a.sub.k] and ([z.sub.k] - [n.sub.k])[a.sub.k] [member of] G([a.sub.1], ... ,[a.sub.r]). Repeating this process, we see that a can be written as [[SIGMA].sup.r.sub.i=1] [z'.sub.i] [a.sub.i] + [[SIGMA].sup.r+m.sub.i=r+1] [n.sub.i] [a.sub.i],[n.sub.i] [member of] N. Without loss of generality one may assume [[SIGMA].sup.r+m.sub.i=r+1] [n.sub.i] [a.sub.i] [member of] Ap(S,E). Hence every element a G[member of] G(S) can be written as a = [[SIGMA].sup.r.sub.i=1] [z.sub.i] [a.sub.i] + [omega] where [omega] [member of] Ap(S,E). The next proposition, which is Corollary 1.7 from [11], assert that when S is Cohen-Macaulay, this expression is unique.

Proposition 2. If S is a Cohen-Macaulay simplicial affine semigroup, then

(1) Every element in G(S) is equal to an unique expression of the form [z.sub.1] [a.sub.1] + ... + [z.sub.r] [a.sub.r] + [omega] with [z.sub.i] [member of] Z and [omega] [member of] Ap(S,E).

(2) The element [[SIGMA].sup.r.sub.i=1] [z.sub.i] [a.sub.i] + [omega] with [z.sub.i] [member of] Z and [omega] [member of] Ap(S,E) is in S if and only if [z.sub.i] [greater than or equal to] 0 for all i.

The cone spanned by S and interior of cone S, are denoted by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

respectively. From the definition it is easy to see that

G(S) [intersection] intcone(S) = {[[SIGMA].sup.r.sub.i=1] [z.sub.i] [a.sub.i] + [[omega].sub.j] | [[gamma].sup.j.sub.1] > - [z.sub.1], ... ,[[gamma].sup.j.sub.r] > -[z.sub.r], j = 1, ... ,t}.

Definition 2. Let S be an affine semigroup. The vector f* [member of] G(S)\ S is called a Frobenius vector for S if for all x [member of] G(S) [intersection] intcone(S), f* + x [member of] S.

The set of Frobenius vectors of S will be denoted by F(S). We define a cone ordering on F(S) by writing [f.sup.*.sub.1] [less than or equal to] [f.sup.*.sub.2] if [f.sup.*.sub.2] + cone (S) [subset or equal to] [f.sup.*.sub.1] + cone(S). We will denote by MF(S) the set of minimal Frobenius vectors of S with respect to [less than or equal to].

Let Ap(S,E) = {[[omega].sub.1] = 0,[[omega].sub.2], ... ,[[omega].sub.t]}. Since S is simplicial, there exist nonnegative rational numbers [[gamma].sup.j.sub,i], i = 1, ... , r, j = 1, ... , t, such that [[omega].sub.j] = [[SIGMA].sup.r.sub.i=1] [[gamma].sup.j.sub.i] [a.sub.i]. Let M and [M.sup.j.sub.i] are r x r matrices, with column vectors [a.sub.1],[a.sub.2],...,[a.sub.r] and [a.sub.1], [a.sub.2], ... ,[[??].sub.i],..., [a.sub.r], [[omega].sub.j], respectively, where [[??].sub.i] means that [a.sub.i] is omitted. It is not hard to see that

[[gamma].sup.j.sub.i] = [absolute value of det [M.sup.j.sub.i]/det M] (2.1)

Now, by Euclidean division, there exists a unique integer [[mu].sup.j.sub.i] [greater than or equal to] - 1 and a unique rational number 0 < [[beta].sup.j.sub.i] [less than or equal to] 1 such that [[gamma].sup.j.sub.i] = [[mu].sup.j.sub.i] + [[beta].sup.j.sub.i], for each i = 1, ... , r. Define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Clearly [[xi].sub.j] [member of] G(S) [intersection] intcon (S). It is straightforward to see that

- [[mu].sup.j.sub.i] = [-[[gamma].sup.j.sub.i]] + 1. (2.2)

For example, let S [subset or equal to [N.sup.3] and [[omega].sub.2] = 3/2 [a.sub.1] + 5/7 [a.sub.2] + 13/4 [a.sub.3] [member of] Ap(S,E). Since [[gamma].sup.2.sub.1] = 3/2, [[gamma].sup.2.sub.2] = 5/7, [[gamma].sup.2.sub.3] = 13/4, we have [[mu].sup.2.sub.1] = [-2/3] + 1, [[mu].sup.2.sub.2] = [-5/7] + 1, [[mu].sup.2.sub.3] = [-13/4] + 1, and so [[xi].sub.2] = -[a.sub.1] - 3[a.sub.3] + [[omega].sub.2].

Lemma 1. Let S be 0 simplicial affine semigroup. Then f* [member of] F(S) if and only if f* + [[xi].sub.k] [member of] S, for every k = 1, ... ,t.

Proof. Let f* be a Frobenius vector for S. Since [[xi].sub.k] [member of] G(S) [intersection] intcone(S), f* + [[xi].sub.k] [member of] S. Conversely let x = [[SIGMA].sup.r.sub.i=1] [z.sub.i] [a.sub.i] + [[omega.sub.l] [member of] G(S) [intersection] intcone(S). Since x [member of] intcone (S),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 2.1. Let S be a simplicial affine semigroup. Then MF (S) [not equal to] [empty set].

Proof. Let f = [[SIGMA].sup.r.sub.i=1] [z.sub.i] [a.sub.i] + [[omega].sub.j] [member of] G(S)\ S. First of all, we observe that there exist [N.sub.1], ... ,[N.sub.t] [member of] N large enough such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now, if f [not member of] F(S), there exists [k.sub.1] [member of] {1, ... ,r} such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If [f.sub.1] [not member of] F(S), there exists [k.sub.2] [member of] {1, ... ,r} such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since this process can be repeated only finitely many times, by Lemma 1, we conclude that F(S) [not equal to] [empty set]. Now we prove that MF(S) [not equal to] [empty set]. Let f = [[SIGMA].sup.r.sub.i=1] [z.sub.i] [a.sub.i] + [[omega].sub.j] [member of] F(S), f' = [[SIGMA].sup.r.sub.i=1] [z'.sub.i] [a.sub.i] + [[omega].sub.j'] [member of] F(S) and f [member of] f' + cone(S). Then [z'.sub.i] + [[gamma].sup.j'.sub.i] [less than or equal to] [z.sub.i] + [[gamma].sup.j.sub.i] for all i = 1, ... , r, and so [z'.sub.i] [less than or equal to] z [less than or equal to] z [less than or equal to] i + [[gamma].sup.j.sub.i] - [[gamma].sup.j'.sub.i]. On the other hand, since [[SIGMA].sup.r.sub.i=1] [a.sub.i] [member of] G(S) [intersection] intcone(S), we have f' + [[SIGMA].sup.r.sub.i=1] [a.sub.i] = [[SIGMA].sup.r.sub.i=1] ([z'.sub.i] + [[gamma].sup.j'.sub.i] + 1) [member of] S, and thus -[[gamma].sup.j'.sub.i] - 1 [less than or equal to] [z'.sub.i. Hence - [[gamma].sup.j'.sub.i] - 1 < [z.sub.i] [less than or equal to] z [less than or equal to] i + [[gamma].sup.j.sub.i] - [[gamma].sup.j'.sub.i]. The finiteness of Ap(S,E) implies that {f * [member of] F(S) | f [member of] f* +cone(S)} is a finite set, which proves that MF (S) [not equal to] [empty].

Definition 3. The simplicial affine semigroup S is called pure simplicial if for each i = 1, ... ,m, [a.sub.r+i] [member of] intcone(S). We abbreviate pure simplicial as P-simplicial.

We can define the following relation on G(S): for any a, b [member of] G(S), a [[less than or equal to].sub.S] b [??] b - a [member of] S. Let max (Ap(S, E)) = {[[eta].sub.1],[[eta].sub.2], ... ,[[eta].sub.s]} be the set of maximal elements of Ap(S, E) with respect to [[less than or equal to].sub.s] and let [[gamma].sup.max.sub.i] = [[max.sub.j] ([[gamma].sup.j.sub.i])] + 1, where [max.sub.j] ([[gamma].sup.j.sub.i]) = max{[[gamma].sup.1.sub.i], [[gamma].sup.2.sub.i], ... ,[[gamma].sup.t.sub.i]}.

Theorem 2.2. Let Sbea simplicial affine semigroup.

(1) If S is Cohen-Macaulay, then

MF(S) [subset] {[[SIGMA].sup.r.sub.i=1] [z.sub.i] [a.sub.i] + [omega] |-1 [less than or equal to] [z.sub.i] [less than or equal to] [[gamma].sup.max.sub.i],[omega] [member of] Ap(S, E)}.

(2) If S is Cohen-Macaulay and P-simplicial, then

MF(S) [subset] {[[SIGMA].sup.r.sub.i=1] [z.sub.i] [a.sub.i] + [eta] |-1 [less than or equal to] [z.sub.i] [less than or equal to] [[gamma].sup.max.sub.i],[eta] [member of] max (Ap(S,E))}.

Proof. (1) Let f = [[SIGMA].sup.r.sub.i=1] [z.sub.i] [a.sub.i] + [omega] [member of] F(S). As [[SIGMA].sup.r.sub.i=1] [a.sub.i] [member of] G(S) [intersection] intcone(S), so f + [[SIGMA].sup.r.sub.i=1] [a.sub.i] = [[SIGMA].sup.r.sub.i=1] ([z.sub.i] + 1) + [omega] [member of] S. Hence by Proposition 2, [z.sub.i] [greater than or equal to] -1. Now let [z.sub.l] > [[gamma].sup.max.sub.l] for some l [member of] {1, ... ,r}. We show that f [not member of] MF(S). Set [f.sub.1] = [[SIGMA].sup.r.sub.i=1,i[not equal to]l] [z.sub.i] [a.sub.i] + [[gamma].sup.max.sub.i] [a.sub.l] + [omega]. Since f [member of] [f.sub.1] + cone(S), it suffices to prove that [f.sub.1] [member of] F(S). Let x = [[SIGMA].sup.r.sub.i=1] [z'.sub.i] [a.sub.i] + [omega]' [member of] G(S) [intersection] intcone(S).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since f [member of] F(S), we have f + x = [[SIGMA].sup.r.sub.i=1] ([z.sub.i] + [z'.sub.i]) [a.sub.i] + [omega] + [omega]' [member of] S. So by Proposition 2, [[SIGMA].sup.r.sub.i=1,i[not equal to]l] ([z.sub.i] + [z'.sub.i])[a.sub.i] + [omega] + [omega]' [member of] S. Clearly [[gamma].sup.max.sub.i] + [z.sub.'l] > 0, so [f.sub.1] + x is also in S and therefore [f.sub.1] [member of] F(S).

(2) Let f = [[SIGMA].sup.r.sub.i=1] [z.sub.i] [a.sub.i] + [omega] [member of] F(S). If [omega] [not member of] max (Ap(S, E)), then there exists [eta] [member of] max(Ap(S,E)) such that [eta] - [omega] [member of] S. Clearly [eta] - [omega] [member of] Ap(S,E), which implies that it belongs to intcone(S), because S is P-simplicial. Since f [not member of] S, by Proposition 2, f + [eta] - [omega] = [[SIGMA].sup.r.sub.i=1] [z.sub.i] [a.sub.i] + [eta] [not member of] S. This contradicts f [member of] F(S).

By the previous theorem and Proposition 2, if f* = [[SIGMA].sup.r.sub.i=1] [z.sub.i] [a.sub.i] + [eta] is a minimal Frobenius vector of the Cohen-Macaulay P-simplicial semigroup S, then there exists k [member of] {1, ... ,r} such that [z.sub.k] = -1 and therefore [f.sup.*.sub.1] = -[a.sub.k] + [[SIGMA].sup.r.sub.i=1,i[not equa; to]k] [[gamma].sup.max.sub.i] [a.sub.i] + [eta] is a Frobenius vector for S, because [f.sup.*.sub.1] [member of] f* + cone(S).

Remark 1 (Numerical case). Every numerical semigroup S = <[a.sub.1], ... ,[a.sub.m+1] > is a P-simplicial and Cohen-Macaulay semigroup. As a consequence of the above theorem f* (S) = -[a.sub.1] + max (Ap(S, [a.sub.1])) (see [10, Proposition 2.12]).

As a consequence of the Theorem 2.2 and Lemma 1, we can compute the elements of MF(S) for Cohen-Macaulay simplicial semigroup, because we only have to check if a finite number of elements of G(S) \ S belongs to MF(S).

Theorem 2.3. Let S be a simplicial affine semigroup and [absolute value of max (Ap(S, E))] = 1. Then f* = [eta] - [[SIGMA].sup.r.sub.i=1] [a.sub.i] is a Frobenius vector for S, where p = max (Ap(S, E)).

Proof. Let x [member of] G(S) n intcone(S) and f* + x = [[SIGMA].sup.r.sub.i=1] [z.sub.i] [a.sub.i] + [omega] [member of] G(S). So [eta] - [omega] + x = [[SIGMA].sup.r.sub.i=1] ([z.sub.i] + 1)[a.sub.i]. Since [eta] - [omega] [member of] cone(S) and x [member of] intcone(S), so [eta] - [omega] + x [member of] G(S) [intersection] intcone(S). Hence for all i = 1, ... ,r, [z.sub.i] + 1 > 0, and so [z.sub.i] [greater than or equal to] 0, consequently, f* + x [member of] S.

Proposition 3. Let S be a simplicial affine semigroup. The following statements are equivalent.

* S is a Gorenstein semigroup;

* Sis a Cohen-Macaulay semigroup and the set Ap(S, E) has a unique maximal element.

Proof. Combining Theorem 4.6 with Theorem 2.8 in [11].

Corollary 1. Let Sbea Gorenstein simplicial affine semigroup. Then f* = [eta] - [[SIGMA].sup.r.sub.i=1] [a.sub.i] is a Frobenius vector for S where p = max (Ap(S, E)). Moreover, if S is P-simplicial, then it is a minimal Frobenius vector for S and it is unique.

In [1] (resp. [2]) it is shown that when S is a complete intersection simplicial semigroup (resp. free semigroup) the vector f* = [eta] - [[SIGMA].sup.r.sub.i=1] [a.sub.i] is the only minimal Frobenius vector for S. We recall that a simplicial affine semigroup is said to be free if [absolute value of Ap(S, E)] = [n.sub.1] [n.sub.2] ... [n.sub.m], where [n.sub.i] = min{k [member of] N \ 0 | [ka.sub.r+i] [member of] ([a.sub.1], [a.sub.2], ... , [a.sub.r+i-1])}, i = 1,... m. Clearly every simplicial affine semigroup with m = 1 is free. Free semigoups are complete intersection and so they are Gorenstein. If S be a free semigoup, then [I.sub.S] is generated by the set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [n.sub.i] [a.sub.r+i] = [[SIGMA].sup.r+i-1.sub.k=1] [t.sub.ik] [a.sub.k] (for more details, please see [12]).

Let S be a Cohen-Macaulay P-simplicial semigroup. By Theorem 2.1, there exists at least one minimal Frobenius vector for S. Using the following algorithm we can compute minimal Frobenius vectors of S.

Algoritm : Computing minimal Frobenius vectors of a P-simplicial Cohen-Macaulay semigroup.

Inpute: A P-simplicial Cohen-Macaulay semigroup S = ([a.sub.1], ... ,[a.sub.r+m]) [subset] [N.sup.r].

Output: The set of minimal Frobenius vectors of S.

Steps of the Algorithm:

1. Compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ([6, Theorem 12.24]), ([13, Chapter 12]).

2. Compute a monomial K-basis {[M.sub.i]|i} K[[x.sub.1], ... ,[x.sub.r+m]]<[I.sub.S], [x.sub.1], ... ,[x.sub.r]> and set

Ap(S,E) = {[[omega].sub.1],[[omega].sub.2], ... ,[[omega].sub.t]} = {[deg.sub.S] ([M.sub.i]) |i}.

3. Using (2.1) and (2.2), compute [[xi].sub.j] = [[SIGMA].sup.r.sub.i=1] (-[[mu].sup.j.sub.i])[a.sub.i] + [w.sub.j],j = 1, ... ,t.

4. Choose [eta] [member of] max (Ap(S, E)) and set [A.sub.[eta]] = {-[a.sub.1] - [a.sub.2] - ... - [a.sub.r] + [eta]},M[F.sub.[eta]] (S) = [empty set].

5. Using Lemma 1, compute T = [t [member of] [A.sub.[eta]]|t [member of] F(S)}. Set M[F.sub.[eta]] (S) = M[F.sub.[eta]] (S) [union] T. Note that if f + [[xi].sub.k] [member of] S, k[member of] {1, ... ,t}, and f [less than or equal to] sf', then f' + [[xi].sub.k] [member of] S.

6. Set [A.sub.[eta]] = [[union].sup.r.sub.i=1] ([a.sub.i] + ([A.sub.[eta]] \ T)) \ S. We see that every element of [A.sub.[eta]] is of the form [c.sub.1] [a.sub.1] + ... + [c.sub.r] [a.sub.r] + [eta].

7. Set [A.sub.[eta]] = [A.sub.[eta]] \ {[c.sub.1] [a.sub.1] + ... + [c.sub.r] [a.sub.r] + [eta] [member of] [A.sub.[eta]]|[c.sub.i] > [[gamma].sup.max.sub.i], for some i} and repeat step 5.

8. The set of minimal Frobenius vectors of S is equal to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Example 1. Let S = <[a.sub.1] = (1,5),[a.sub.2] = (5,1),[a.sub.3] = (2,2),[a.sub.4] = (3,3)>. By Theorem 2.1, S has at least one minimal Frobenius vector. Performing the steps of the above algorithm we compute the set of minimal Frobenius vectors of S.

Step 1. Using CoCo A [3], K[S] [equivalent] K[x,y,z,w]/[I.sub.S], where [I.sub.S] = <[z.sup.3] - [w.sup.2], - xy + [w.sup.2]).

Step 2. The set {1, [bar.z], [[bar.z].sup.2],[bar.w],[bar.z][bar.z],[[bar.z].sup.2][bar.w]} is a monomial K-basis of K[x,y,z,w]/<[I.sub.S], x,y> Hence

Ap(S, E) = {[[omega].sub.1] = 0, [[omega].sub.2] = [a.sub.3],[[omega].sub.3] = 2[a.sub.3],[[omega].sub.4] = [a.sub.4], [[omega].sub.5] = [a.sub.3] + [a.sub.4], [[omega].sub.6] = 2[a.sub.3] + [a.sub.4]} .

By Proposition 1, the semigroup S is Cohen-Macaulay, because for every x,y [member of] Ap(S, E), x - y or y - x is in intcone(S) and since [a.sub.1] and [a.sub.2] are linearly independent, x - y [not member of] G([a.sub.1], [a.sub.2]).

Step 3. Using CoCoA, we see that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Step 4. Set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Step 5. Since f* + [[xi].sub.1] = 2[a.sub.3] + [a.sub.4] [member of] S, f* + [[xi].sub.2] = [a.sub.4] [member of] S, f* + [member of 3] = [a.sub.3] + [a.sub.4] [member of] S, f* + [[xi].sub.4] = 2[a.sub.3] [member of] S, f* + [[xi].sub.5] = 2[a.sub.4] [member of] S and f* + [[xi].sub.6] = [a.sub.3] [member of] S, so f* [member of] F(S). Set T = {f*}.

Step 6. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It follows that f* = (1,1) is the only minimal Frobenius vector for S. The semigroup S is free, because [absolute value of Ap(S, E)] = 6 (see Fig 1).

Example 2. Let S = <[a.sub.1] = (2,1),[a.sub.2] = (1,5),[a.sub.3] = (1,1),[a.sub.4] = (4,5)>.

Step 1. Using CoCoA, K[S] [equivalent] K[x,y,z,w]/[I.sub.S], where [I.sub.S] = (--[z.sup.6] + xw,[x.sup.3] y - [z.sup.3] w, [x.sup.2] y[z.sup.3] - [w.sup.2]).

Step 2. The set {1, [bar.z], [[bar.z].sup.2],[[bar.z].sup.3],[[bar.z].sup.3],[[bar.z].sup.3],[bar.w],[bar.w][bar.w], [[bar.z].sup.2] [bar.z]} is a monomial K-basis of K[x,y,z,w]/<[I.sub.S], x,y> Hence

Ap(S, E) = {[[omega].sub.1] = 0, [[omega].sub.2] = [a.sub.3],[[omega].sub.3] = 2[a.sub.3],[[omega].sub.4] = 3[a.sub.3], [[omega].sub.5] = 4[a.sub.3], [[omega].sub.6] 5[a.sub.3], [[omega].sub.7] = [a.sub.4], [[omega].sub.8] [a.sub.3] + [a.sub.4], [[omega].sub.9] = 2[a.sub.3] + [a.sub.4]} .

Since [a.sub.1] and [a.sub.2] are linearly independent, one obtains that if x, y [member of] Ap(S, E) and x [not equal to] y, then x - y [not member of] G([a.sub.1], [a.sub.2]). Hence by Proposition 1, S is a Cohen-Macaulay semigroup but not Gorenstein, because max(Ap(S, E)) = {[[eta].sub.1] = 2[a.sub.3] + [a.sub.4], [[eta].sub.2] = 5[a.sub.3]} (see Proposition 3).

Step 3. Using CoCoA, we see that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Step 4. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Step 5. We have [f.sub.1] + [[xi].sub.1] = 2[a.sub.3] + [a.sub.4] [member of] S, [f.sub.1] + [[xi].sub.2] = 2[a.sub.1] [member of] S, [f.sub.1] + [[xi].sub.3] = 2[a.sub.1] + [a.sub.3] [member of] S,

[f.sub.1] + [[xi].sub.4] = [a.sub.1] + 2[a.sub.3] [member of] S, [f.sub.1] + [[xi].sub.5] = [a.sub.1] + 3[a.sub.3] [member of] S,

[f.sub.1] + [[xi].sub.6] = 4[a.sub.3] [member of] S, [f.sub.1] + [[xi].sub.7] = 5[a.sub.3] [member of] S, [f.sub.1] + [[xi].sub.8] = [a.sub.4] [member of] S and [f.sub.1] + [[xi].sub.9] = 2[a.sub.1] + [a.sub.2] [member of] S. So [f.sub.1] [member of] F(S) and like in the example above [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now we use the algorithm for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since [f.sub.3] + [[xi].sub.4] = (4,6) [not member of] S and [f.sub.4] + [[xi].sub.4] = (5,2) [not member of] S, [f.sub.3] and [f.sub.4] are not in F(S). [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. As [[gamma].sup.max.sub.1] = 3 and [[gamma].sup.max.sub.2] = 1, we go back to Step 5. The vectors [f.sub.5] and f6 are not in F(S) because [f.sub.5] + [[xi].sub.4] = (5,11) [not member of] S and [f.sub.6] + [[xi].sub.4] = (7,3) [not member of] S. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. As [f.sub.7] + [[xi].sub.4] = (9,4) [not member of] S, so [f.sub.7] [not member of] F(S). [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since [f.sub.8] + [[xi].sub.4] = (11,5) [not member of] S, so [f.sub.8] [not member of] F(S). [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence [f.sub.1] is the only minimal Frobenius vector for S (see Fig 2).

Acknowledgement

The authors are very grateful to the anonymous referee for carefully reading the paper and for his or her comments and suggestions which have improved the paper.

References

[1] A. Assi, P. A. Garcia-Sanchez and I. Ojeda, Frobenius vectors, Hilbert series and gluing, Journal of Commutative Algebra, 7 (2015), no. 3, 317-335.

[2] A. Assi, The Frobenius vector of a free affine semigroup. J. Algebra Appl. 11 (2012), no. 4,1250065.

[3] CoCoATeam, CoCoA: A system for doing Computations in Commutative Algebra (2011). Available at http://cocoa.dima.unige.it

[4] R. Froberg, The Frobenius number of some semigroups, Comm. Algebra 22 (1994), 6021-6024.

[5] J. Herzog, Generators and relations of abelian semigroups and semigroup rings. Manuscripta Math., 3 (1970). 175-193.

[6] E. Miller and B. Sturmfels, Combinatorial commutative algebra, Vol. 227, Springer-Verlag, New York, 2005.

[7] J. L. Ramirez Alfonsin, The diophantine Frobenius problem, Equipe Combinatone Universite Pierre et Marie Curie, 2005.

[8] O. J. Rodseth, On a linear Diophantine problem of Frobenius, J. reine angew. Math. 301 (1978), 171-178.

[9] J. C. Rosales, P. A. Garcia-Sanchez, Finitely generated commutative monoids. Nova Science Publishers, Inc., Commack, NY, 1999.

[10] J. C. Rosales, P. A. Garcia-Sanchez, Numerical Semigroups, Developments in Mathematics, 20. Springer, New York, 2009.

[11] J. C. Rosales, P. A. Garcia-Sanchez, On Cohen-Macaulay and gorenstein simplicial affine semigroups, Proc. Edinburgh Math. Soc. (2) 41 (1998) 517-537.

[12] J. C. Rosales, P. A. Garcia-Sanchez, On free affine semigroups, Semigroup Forum 58 (1999) 367-385. Archiv der Mathematik 83 (2004), 488-496.

[13] B. Sturmfels, Grobner bases and convex polytopes, Univ. Lecture Ser., Vol. 8, Amer. Math. Soc., Providence, RI, 1995.

[14] J.J. Sylvester, Problem 7382, Educational Times 37 (1884), 26; reprinted in: Mathematical questions with their solution, Educational Times 41(1884), 21.

[15] B. Vizvari, Generation of uniformly distributed random vectors of good quality, Rutcor Research Report (1994), No. RRR1793.

[16] B. Vizvari, On a generalization of the Frobenius problem, Technical Report MN/30 Computer and Automation Inst., Hungarian Academy of Sciences (1987).

Ali Mahdavi Farhad Rahmati *

* Corresponding author.

Received by the editors in February 2016 - In revised form in June 2016.

Communicated by S. Caenepeel.

2010 Mathematics Subject Classification : 20M05,20M25,11D07.

Department of Pure Mathematics, Faculty of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

E-mail addresses: a-mahdavi@aut.ac., frahmati@aut.ac.ir
COPYRIGHT 2016 Belgian Mathematical Society
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

 
Article Details
Printer friendly Cite/link Email Feedback
Author:Mahdavi, Ali; Rahmati, Farhad
Publication:Bulletin of the Belgian Mathematical Society - Simon Stevin
Article Type:Report
Date:Oct 1, 2016
Words:5217
Previous Article:Flag-transitive point-primitive non-symmetric 2-(v, k, 2) designs with alternating socle.
Next Article:Optimization through dense sets.
Topics:

Terms of use | Privacy policy | Copyright © 2018 Farlex, Inc. | Feedback | For webmasters