-- Various routines for dealing with monomial ideals -- SP 11/01/98 (preliminary version) -- (Code should change after the type MonomialIdeal gets complete) -- routines in this file: -- -- lcm -- lcmM -- alexanderDual -- primaryDec -- ass -- gin -- randomMonomialIdeal -- algShift -- sqalgShift -- polarize -- standardPairs -- frobeniusPower Ideal^List := (I,d)-> ( if not all(d, i -> instance(i,ZZ) and i >= 0) then error "expected positive integers"; if numgens I=!=#d then error("supplied list has wrong size"); ideal apply(numgens I, i->(I_i^(d#i)))) lcm2 = (f,g) -> ( lift(f*g/gcd(f,g), ring f) ) lcm = (L) -> ( R:=ring L_0; lcmL:=1_R; scan(L, k->(lcmL=lcm2(lcmL,k))); lcmL ) document{quote lcm, TT "lcm"," -- given a list of polynomials the script returns their least common multiple"} lcmM = (L) -> ( m := gens intersect toSequence (L/(i -> monomialIdeal(matrix{{i}}))); m_(0,0)) document{quote lcmM, TT "lcmM(L)"," -- given a list L of monomials the script returns their least common multiple"} alexanderDual = (I) -> ( R:=ring I; if not isPolynomialRing(R) then error "expected an ideal in a polynomial ring"; L:=flatten entries gens I; scan(L, f->(if size(f)=!=1 then error("the input is not a monomial ideal"))); lcmI:=lcmM(L); expo:=flatten exponents(lcmI); J:=I+(ideal vars R)^(expo+toList(numgens R:1)); S:=R/J; ideal contract(lift(syz transpose vars S, R), product flatten entries gens (ideal vars R)^expo) ) document{quote alexanderDual, TT "alexanderDual(I)"," -- given a monomial ideal I, the script returns the Alexander Dual monomial ideal (over the same polynomial ring as I). In the square free case this is the Stanley-Reisner ideal associated to the Alexander Dual simplicial complex; in the general case this is E. Miller's dual, which is not quite a dual ! "} primaryDec = (I) -> ( R :=ring I; if not isPolynomialRing(R) then error "expected an ideal in a polynomial ring"; L :=flatten entries gens I; scan(L, f->(if size(f)=!=1 then error("the input is not a monomial ideal"))); expo :=flatten exponents(lcmM(L))+toList(numgens R:1); M :=flatten entries gens alexanderDual(I); N :=apply(#M, i->expo-flatten exponents(M_i)); apply(N, i->(trim ideal apply(#i, j->(if (i_j==0 or i_j==expo_j) then 0_R else R_j^(i_j))))) ) document{quote primaryDec, TT "primaryDec(I)"," -- given a monomial ideal I, the script returns a list of ideals which form the primary decomposition of I. "} ass = (I) -> ( R :=ring I; if not isPolynomialRing(R) then error "expected an ideal in a polynomial ring"; L :=flatten entries gens I; scan(L, f->(if size(f)=!=1 then error("the input is not a monomial ideal"))); expo :=flatten exponents(lcmM(L))+toList(numgens R:1); M :=flatten entries gens alexanderDual(I); N :=apply(#M, i->expo-flatten exponents(M_i)); unique apply(N, i->(delete(0_R,flatten apply(#i, j->(if (i_j==0 or i_j==expo_j) then 0_R else R_j )))))) document{quote ass, TT "ass(I)"," -- given a monomial ideal I, the script returns the list of the associated prime ideals for I. "} randomMonIdeal = (R, n, d) -> ( m := numgens R; ideal apply(n, i -> product(m, j-> R_j^(random d))) ) document{quote randomMonIdeal, TT "randomMonIdeal(R,n.d)"," -- returns a random monomial ideal in the polynomial ring R, generated by n monomials in which each variable is raised at power at most d. However, quite often this is NOT a generic monomial ideal !"} gin = (I) -> ( R:=ring I; ideal leadTerm gens gb substitute(I, random(R^{1},R^(numgens R))) ) document{quote gin, TT "gin(I)"," -- given an ideal I in a polynomial ring R it returns the generic initial ideal of I, with respect to the current monomial order in R"} in = (I) -> ( if not isPolynomialRing(ring(I)) then error "expected an ideal in a polynomial ring"; ideal leadTerm gens gb(I) ) document{quote in, TT "in(I)"," -- returns the initial ideal of I with respect to the current monomial order in the ring of I"} algShift = (I)-> ( S:= ring I; if not isPolynomialRing(S) then error "expected an ideal in a polynomial ring"; kk:=S.baseRings#1; var:=flatten entries vars S; SE:=kk[var, MonomialOrder=>GRevLex, SkewCommutative =>true]; J:=gin substitute(I,SE); substitute(J, S)) document{quote algShift, TT "algShift(I)"," -- given a square free monomial ideal I in a polynomial ring R, it returns the square free monomial ideal in R corresponding to its (deg-rev-lex) algebraic shifting `a la Kalai.", PARA, "The ideal I is the Stanley-Reisner ideal of a simplicial complex X on a vertex set corresponding to the variables in R. To X one associates also a monomial ideal in the exterior algebra on these variables, whose deg-rev-lex gin in the exterior algebra corresponds to a new simplicial complex Y, called the algebraic shifting of X. The script returns the Stanley-Reisner ideal corresponding to Y, which is called the algebraic shifting of the square free monomial ideal I."} sqalgShift = (I)-> ( S:=ring I; if not isPolynomialRing(S) then error "expected an ideal in a polynomial ring"; kk:=S.baseRings#1; var:=flatten entries vars S; SR:=kk[var, MonomialOrder=>GRevLex]; squares:=(ideal vars SR)^(toList(numgens SR:2)); SQ:=SR/squares; J:=gin substitute(I,SQ); substitute(J, vars S) ) document{quote sqalgShift, TT "sqalgShift(I)"," -- given a square free monomial ideal I in a polynomial ring R, it returns the square free monomial ideal in R corresponding to its (deg-rev-lex) algebraic shifting in R mod the squares of the variables.", PARA, "The ideal I is the Stanley-Reisner ideal of a simplicial complex X on a vertex set corresponding to the variables in R. To X one associates also a monomial ideal in R modulo the squares of the variables, whose deg-rev-lex gin in this ring corresponds to a new simplicial complex Y. The script returns the Stanley-Reisner ideal corresponding to Y."} frobeniusPower = (I,p) -> ( if p<0 then error("the power needs to be a positive integer"); I^(toList(numgens I:p)) ) document{quote frobeniusPower, TT "frobeniusPower(I,p)"," -- returns the ideal generated by the p-th powers of the generators of the ideal I."} TEST /// R=ZZ/101[x_0 .. x_4] I=ideal(x_0*x_2, x_0*x_3, x_1*x_4, x_1*x_3, x_2*x_4) J=alexanderDual(I) primaryDec(I) KS=sqalgShift(I) betti res KS KE=algShift(I) betti res KE R=ZZ/101[a,b,c,d] I=ideal(a^2, c^2) J=alexanderDual(I) primaryDec(I) R=ZZ/101[x,y,z] I=ideal(z^5,x^2*z^2, x^4*y^3, x^3*y^5, y^4*z^3, y^2*z^4, x*y*z) J=alexanderDual(I) Idd=alexanderDual(J) Idd==I primaryDec(I) -- Example of a monomial ideal such that -- Ass(I) is not contained in Ass(I^2) R=ZZ/101[x,y,z] I = ideal(x^2*y^6, x^3*y^5, x^5*y^3, x^6*y^2, x^4*y^4*z) primaryDec(I) ass(I) primaryDec(I^2) ass(I^2) ass(I^3) --another example I=ideal(x^2*y^4, x^4*y^2, x*y^5, x^5*y, x^3*y^3*z) ass(I) ass(I^2) --Triangulation of RP^2, Counterexample to reg(I)<=2 reg(I) R=ZZ/101[a,b,c,d,e,f] I=ideal(a*b*d, a*b*e, a*c*d, a*c*f, a*e*f, b*c*e, b*c*f, b*d*f, c*d*e, d*e*f) J=alexanderDual(I^2) betti res frobeniusPower(I,2) R=ZZ/101[a,b,c,d, MonomialSize => 16] I=randomMonIdeal(R,10,4) J=alexanderDual(I) betti res I betti res J ass(I) ass(I^2) ass(I^3) ass(I^4) ass(I^5) -- Kalai's Algebraic shifting preserves extremal Betti numbers ! R=ZZ/101[x_0 .. x_6, MonomialOrder=>GRevLex] I=ideal( x_0*x_1*x_2, x_0*x_1*x_4, x_0*x_1*x_6, x_0*x_2*x_4, x_0*x_2*x_5, x_0*x_3*x_4, x_0*x_3*x_5, x_0*x_3*x_6, x_0*x_5*x_6, x_1*x_2*x_3, x_1*x_2*x_5, x_1*x_3*x_5, x_1*x_3*x_6, x_1*x_4*x_5, x_1*x_4*x_6, x_2*x_3*x_4, x_2*x_3*x_6, x_2*x_4*x_6, x_2*x_5*x_6, x_3*x_4*x_5, x_4*x_5*x_6) betti res I -- total: 1 21 49 42 15 2 -- 0: 1 . . . . . -- 1: . . . . . . -- 2: . 21 49 42 14 2 -- 3: . . . . 1 . betti res algShift(I) -- total: 1 22 53 48 18 2 -- 0: 1 . . . . . -- 1: . . . . . . -- 2: . 21 50 45 17 2 -- 3: . 1 3 3 1 . betti res sqalgShift(I) -- total: 1 21 49 42 14 1 -- 0: 1 . . . . . -- 1: . . . . . . -- 2: . 21 49 42 14 1 -- So however sq-algebraic shifting doesn't -- preserve extremal Betti numbers ! ///