From ApCoCoAWiki
Revision as of 16:29, 2 October 2020 by AndraschkoBot (talk | contribs) (Bot: Category moved)


Enumerate a Macaulay's basis of a finitely generated K-algebra.




Given a two-sided ideal I in a finitely generated monoid ring P=K<X|R>, we can consider the K-algebra P/I as a K-vector space. Moreover, let G be a Groebner basis of I, and let B be the set of all words which are not a multiple of any word in the leading word set MRLW{G}. Then the residue class of the words in B form a K-basis, called a Macaulay's basis, of P/I. For the sake of computing the values of the Hilbert function (see NCo.MRHF) of P/I, in this function we require that G has to be a Groebner basis with respect to a length compatible word ordering (see NCo.SetOrdering).

Please note: The function(s) explained on this page is/are using the ApCoCoAServer. You will have to start the ApCoCoAServer in order to use it/them.

Please set coefficient field via the function NCo.SetFp (or NCo.UnsetFp) before calling this function. The default coefficient field is the field of rational numbers, i.e. RAT in CoCoAL. For more information, please check the relevant functions.

  • @param X: a finite alphabet (or set of indeterminates). It is of STRING type. Note that every letter in X MUST appear only once.The order of letters in X induces word orderings.

  • @param Ordering: a length compatible word ordering induced by the order of letters in X. It is a STRING, which is a shortened-form of the name of corresponding word ordering. Note that the package currently supports two length compatible words orderings, i.e. "LLEX" (the length-lexicographic ordering) and "LRLEX" (the length-reverse-lexicographic ordering). See NCo.SetOrdering for more details.

  • @param Relations: a finite set of relations. It is of LIST type. Each element in Relations is of the form [W1, W2], where W1 and W2 are words in <X>. Each word is represented as a STRING. For example, the word xy^2x is represented as "xyyx", and the identity is represented as the empty string "". Thus, the relation (yx, xy) is represented as ["yx", "xy"], and the set of relations {(yx, xy),(zx,xz),(zy,yz)} is represented as [["yx", "xy"],["zx", "xz"],["zy", "yz"]].

  • @param G: a LIST of non-zero polynomials forming a Groebner basis with respect to the length compatible word ordering Ordering. Each polynomial is represented as a LIST of monomials, which are pairs of the form [C, W] where W is a word in <X> and C is the coefficient of W. For example, the polynomial f=xy-y+1 is represented as F:=[[1,"xy"], [-1, "y"], [1,""]]. Warning: users should take responsibility to make sure that G is indeed a Groebner basis with respect to a length compatible word ordering!

  • @return: a LIST of words forming a Macaulay's basis of the K-algebra K<X>/<G,Relations>.

Optional parameter:

  • @param DB: a positive INT which is a degree bound of the lengths of words. Note that we set DB=32 by default. Thus, in the case that K<X>/<G,Relations> has a finite Macaulay's basis, it is necessary to set DB to a large enough INT in order to compute the whole Macaulay's basis.


X :=  <quotes>xyzt</quotes>;
Ordering := <quotes>LLEX</quotes>;
Relations := [];
G:= [[[1, <quotes>yt</quotes>], [-1, <quotes>ty</quotes>]], [[1, <quotes>xt</quotes>], [-1, <quotes>tx</quotes>]], [[1, <quotes>xy</quotes>], [-1, <quotes>ty</quotes>]], [[1, <quotes>xx</quotes>], [-1, <quotes>yx</quotes>]], 
[[1, <quotes>tyy</quotes>], [-1, <quotes>tty</quotes>]], [[1, <quotes>yyx</quotes>], [-1, <quotes>tyx</quotes>]]];
NCo.MRMB(X, Ordering, Relations, G, 3);
[[<quotes></quotes>], [<quotes>t</quotes>, <quotes>z</quotes>, <quotes>y</quotes>, <quotes>x</quotes>], [<quotes>tt</quotes>, <quotes>tz</quotes>, <quotes>ty</quotes>, <quotes>tx</quotes>, <quotes>zt</quotes>, <quotes>zz</quotes>, <quotes>zy</quotes>, <quotes>zx</quotes>, <quotes>yz</quotes>, <quotes>yy</quotes>, <quotes>yx</quotes>, <quotes>xz</quotes>], 
[<quotes>ttt</quotes>, <quotes>ttz</quotes>, <quotes>tty</quotes>, <quotes>ttx</quotes>, <quotes>tzt</quotes>, <quotes>tzz</quotes>, <quotes>tzy</quotes>, <quotes>tzx</quotes>, <quotes>tyz</quotes>, <quotes>tyx</quotes>, <quotes>txz</quotes>, <quotes>ztt</quotes>, <quotes>ztz</quotes>, <quotes>zty</quotes>, 
<quotes>ztx</quotes>, <quotes>zzt</quotes>, <quotes>zzz</quotes>, <quotes>zzy</quotes>, <quotes>zzx</quotes>, <quotes>zyz</quotes>, <quotes>zyy</quotes>, <quotes>zyx</quotes>, <quotes>zxz</quotes>, <quotes>yzt</quotes>, <quotes>yzz</quotes>, <quotes>yzy</quotes>, <quotes>yzx</quotes>, <quotes>yyz</quotes>, 
<quotes>yyy</quotes>, <quotes>yxz</quotes>, <quotes>xzt</quotes>, <quotes>xzz</quotes>, <quotes>xzy</quotes>, <quotes>xzx</quotes>]]

See also







Introduction to CoCoAServer