The MultivariateCyclicVector command performs an iteration algorithm (similar to FGLM) to compute a Groebner basis with respect to M of (skew) polynomials whose normal forms under NFproc are zero.

Common uses of the MultivariateCyclicVector command are the following.

(i) - To compute Groebner bases by change of ordering (a first Groebner basis is known for a monomial order, a second one is computed for another order).

(ii) - To find equations defining a function. See the Examples section.

More specifically, NFproc takes three arguments.

It returns a normal form for the monomial m and stores it as ${\mathrm{NF}}_m$ into NF.

FDproc takes two arguments:

It returns either a nontrivial linear combination of the indices of NF that evaluates to 0 under NFproc, or FAIL when no such dependency exists.  This function must not use entries in NF corresponding to indices that are elements of the monoideal generated by mi.

The procedure TMproc is used to decide when to stop the algorithm.  It takes three arguments.

The MultivariateCyclicVector command returns an expseq NF, EQ, where NF is the table of all normal forms computed during the calculations and EQ is a table of all linear dependencies found.

Note: The algorithm cannot detect non-zero-dimensional cases; it may loop forever when called on such cases.

For the purpose of computing changes of orderings in the commutative case, the alternative command FGLM is more efficient.

$\mathrm{with}\left(\mathrm{Ore\_algebra}\right)\:$

$\mathrm{with}\left(\mathrm{Groebner}\right)\:$

$A≔\mathrm{poly\_algebra}\left(x\,y\,z\,t\right)\:$

$G≔\left[x^{31}-x^6-x-y\,x^8-z\,x^{10}-t\,x^2+y^2+z^2-t^2\right]\:$

$M\left[\mathrm{org}\right]≔\mathrm{MonomialOrder}\left(A\,\mathrm{wdeg}\left(\left[1\,31\,8\,10\right]\,\left[x\,y\,z\,t\right]\right)\right)\:$

$\mathrm{GB}\left[\mathrm{org}\right]≔\mathrm{Basis}\left(G\,M\left[\mathrm{org}\right]\right)$

${\mathrm{GB}}_{\mathrm{org}}≔\left[x^8-z\,x^{2}z-t\,-t{x}^6+z^2\,x^6-t^{3}x+x+y\,-2t^3{x}^7+t^6{x}^2+t{x}^6+2x^7-2t^3{x}^2+t{x}^2-t^2+2x^2\,-t^2{x}^6+t^{6}z-2t^4{x}^3-2t^{3}z+t^2{x}^2+2t{x}^3+tz+2z\,-2t^4{x}^5+t^7+t^2{x}^4+2t{x}^5-2t^4-t^{2}z+t^2+2t\right]$

$\mathrm{HilbertDimension}\left(\,M\left[\mathrm{org}\right]\right)$

$0$

NFproc:=proc(m,NF,MOrd)
    NF[m]:=NormalForm(m,GB[org],M[org])
end proc:

FDproc:=proc(M,NF)
    local ind_lst,term,eta,sol;
    ind_lst:=map(op,[indices(NF)]);
    for term in M do
        ind_lst:=remove(divide,ind_lst,term)
    end do;
    expand(numer(normal(add(eta[term]*NF[term],term=ind_lst))));
    sol:=[solve({coeffs(%,{x,y,z,t})},{seq(eta[term],term=ind_lst)})];
    subs(op(1,sol),add(eta[term]*term,term=ind_lst));
    `if`(%=0,FAIL,collect(primpart(numer(subs(map(n->n=1,
        map2(op,1,select(evalb,sol[1]))),%)),[x,y,z,t]),
        [x,y,z,t],distributed,factor))
end proc:

TMproc:=proc(border,monoideal,MOrd)
    border<>[]
end proc:

$M\left[\mathrm{new}\right]≔\mathrm{MonomialOrder}\left(A\&comma;\mathrm{tdeg}\left(x\&comma;y\&comma;z\&comma;t\right)\right)\&colon;$

$\mathrm{fglm}≔\left[\mathrm{MultivariateCyclicVector}\left(\mathrm{NFproc}\&comma;\mathrm{FDproc}\&comma;\mathrm{TMproc}\&comma;M\left[\mathrm{new}\right]\right)\right]\&colon;$

$\mathrm{map}\left(\mathrm{op}\&comma;\left[\mathrm{entries}\left(\mathrm{fglm}\left[2\right]\right)\right]\right)$

$\left[t^{4}z+t^{3}yx+t^2{y}^{2}x-z^{2}yx+z^4+t^3-t{y}^2-t{z}^2-t^2-tx-ty-tz-2xy\&comma;t^{3}yx-t^2{z}^{2}y+z^{3}x-z^4-t^{2}x+tyx+t^2-2y^2-z^2\&comma;-t^4-t^{2}yx+2t^2{y}^2+t{z}^3+y^{3}x+z^{2}yx-y^4+z^4+2tz-zx\&comma;-t^2+x^2+y^2+z^2\&comma;t{z}^{3}yx+2t^{3}x-t^2{z}^2-z^3+t^2+tx-ty-2x-2y\&comma;-t^{3}yx+t^2{z}^{2}x-z^4-t^3+t{y}^2+t{z}^2+t^2+2xy-z^2\&comma;t^{4}y+t^3{y}^2-t^{2}zx-tzyx+z^4+t^{2}x-t^2+tx-ty+z^2\&comma;t^{4}y-t^3{z}^2-t^{2}zx+z^{3}x+t^{2}x+tx-ty+z^2\&comma;-t^{2}z+z{y}^2+z^3+t\&comma;-t^{4}x+tx+ty+z^2\&comma;z^{4}y+t^{3}x-t^{3}z-t{y}^{2}x-t{z}^{2}x-t^{2}y-y^{2}x+y^3+z^{2}y+z\&comma;t{z}^4-t^3-tyx+t{y}^2+t{z}^2-z^{2}x\&comma;z^5-t^4\&comma;-2t^{4}y-t^{4}z+4t^2{y}^3+t{z}^{3}x+t{z}^{3}y-2y^5-2t^{3}x+2t^{3}z+2t{y}^{2}x+2t{z}^{2}x+z^{2}yx+2t^{2}y+tzx+4tzy+2y^{2}x-zyx-2y^3-2z^{2}y+tz-t-2z\&comma;-t^5+tzyx+z^{3}x+t^2\&comma;t^{4}z+zx{t}^3+t^{3}zy-t^2{z}^3-t{z}^{2}x-z^{2}yx+tzx-tz-2zy\&comma;2t^{4}y-zx{t}^3+t{y}^4-2t^{2}zx-tzyx+z^{3}x+2z^4-t^3+2t^{2}x-2t^{2}z-tyx+t{y}^2+t{z}^2-z^{2}x-t^2+2tx-2ty+zx+zy+2z^2\&comma;z^{4}x-t^{2}x-t^{2}y+y^{2}x+z^{2}x+y^3+z^{2}y-z\right]$

$\mathrm{\phi }≔\frac{1}{\mathrm{sqrt}\left(1-2xy+y^2\right)}$

$\mathrm{\phi }≔\frac{1}{\sqrt{-2xy+y^2+1}}$

`diff/P`:=proc(x,v) Q[op(1,procname)](x)*diff(args) end proc:

`diff/Q`:=proc(x,v)
    local n;
    n:=op(1,procname);
    (2*x*Q[n](x)-n*(n+1)*P[n](x))*diff(args)/(1-x^2)
end proc:

P[n+2](x):=((2*n+3)*x*P[n+1](x)-(n+1)*P[n](x))/(n+2);

$P_{n+2}\left(x\right)≔\frac{\left(2n+3\right)x{P}_{n+1}\left(x\right)-\left(n+1\right)P_n\left(x\right)}{n+2}$

Q[n+1](x):=(n+1)*(P[n](x)-x*Q[n](x))/(1-x^2);

$Q_{n+1}\left(x\right)≔\frac{\left(n+1\right)\left(P_n\left(x\right)-x{Q}_n\left(x\right)\right)}{-x^2+1}$

$A≔\mathrm{skew\_algebra}\left(\mathrm{shift}=\left[\mathrm{Sn}\&comma;n\right]\&comma;\mathrm{diff}=\left[\mathrm{Dx}\&comma;x\right]\&comma;\mathrm{diff}=\left[\mathrm{Dy}\&comma;y\right]\right)\&colon;$

$M≔\mathrm{MonomialOrder}\left(A\&comma;\mathrm{tdeg}\left(\mathrm{Sn}\&comma;\mathrm{Dx}\&comma;\mathrm{Dy}\right)\right)\&colon;$

NFproc:=proc(t,NF,MOrd)
    NF[t]:=normal(eval(subs(n=n+degree(t,Sn),
        diff(P[n](x)*phi,[x$degree(t,Dx),y$degree(t,Dy)]))))
end proc:

FDproc:=proc(M,NF)
    local ind_lst,t,eta,sol;
    ind_lst:=map(op,[indices(NF)]);
    for t in M do
        ind_lst:=remove(divide,ind_lst,t)
    end do;
    expand(numer(normal(add(eta[t]*NF[t],t=ind_lst))));
    coeffs(%,[P[n](x),P[n+1](x),Q[n](x)]);
    sol:=[solve({%},{seq(eta[t],t=ind_lst)})];
    subs(op(1,sol),add(eta[t]*t,t=ind_lst));
    `if`(%=0,FAIL,collect(primpart(numer(subs(map(n->n=1,
        map2(op,1,select(evalb,sol[1]))),%)),[Dx,Dy,Sn]),
        [Dx,Dy,Sn],distributed,factor))
end proc:

TMproc:=proc(border,monoideal,MOrd)
    border<>[]
end proc:

$\mathrm{fglm}≔\left[\mathrm{MultivariateCyclicVector}\left(\mathrm{NFproc}\&comma;\mathrm{FDproc}\&comma;\mathrm{TMproc}\&comma;M\right)\right]\&colon;$

$\mathrm{map}\left(\mathrm{op}\&comma;\left[\mathrm{entries}\left(\mathrm{fglm}\left[2\right]\right)\right]\right)$

$\left[\left(2xy-y^2-1\right)\mathrm{Dy}+x-y\&comma;\left(x-1\right)\left(x+1\right){\left(2xy-y^2-1\right)}^2{\mathrm{Dx}}^2+2\left(3x^{2}y-y^{2}x-x-y\right)\left(2xy-y^2-1\right)\mathrm{Dx}-4n^2{x}^2{y}^2+4n^{2}x{y}^3-n^2{y}^4-4n{x}^2{y}^2+4nx{y}^3-n{y}^4+4n^{2}xy-2n^2{y}^2+3x^2{y}^2-2y^{3}x+4nxy-2n{y}^2-n^2-2xy+y^2-n\&comma;\left(x-1\right)\left(x+1\right)\left(2xy-y^2-1\right)\mathrm{Dx}\mathrm{Sn}-x\left(n+1\right)\left(2xy-y^2-1\right)\mathrm{Dx}+y\left(x-1\right)\left(x+1\right)\mathrm{Sn}+\left(xy-y^2-1\right)\left(n+1\right)\&comma;{\mathrm{Sn}}^2\left(n+2\right)-x\left(2n+3\right)\mathrm{Sn}+n+1\right]$

$\mathrm{normal}\left(\mathrm{eval}\left(\mathrm{map}\left(\mathrm{applyopr}\&comma;\&comma;\mathrm{\phi }P\left[n\right]\left(x\right)\&comma;A\right)\right)\right)$

$\left[0\&comma;0\&comma;0\&comma;0\right]$

Faugere, J. C.; Gianni, P.; Lazard, D.; and Mora, T. "Efficient Computation of Zero-dimensional Grobner Bases by Change of Ordering." J. Symbolic Comput., Vol. 16, (1993): 329-344.