-- -*- coding: utf-8-unix -*- needsPackage "SimplicialComplexes" newPackage( "BettiBounds", Version => "1.0", Date => "December 18, 2012", Authors => {{Name => "Janko Boehm", Email => "boehm@mathematik.uni-kl.de", HomePage => "http://www.mathematik.uni-kl.de/~boehm/"}, {Name => "Stavros Papadakis", Email => "papadak@math.ist.utl.pt", HomePage => "http://www.math.ist.utl.pt/~papadak/"} }, Headline => "Betti bounds for iterated stellar subdivisions of the boundary of a simplex", --PackageExports => {"SimplicialComplexes"}, DebuggingMode => false ) ------------------------------------------------------------------------------- {* Copyright [2012] [Janko Boehm, Stavros Papadakis] This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, see *} {* Installation: Put the file BettiBounds.m2 somewhere into the path of Macaulay2 (usually into the directory .Macaulay2/code inside your home directory, type path in M2 to see the path) and do inside M2 installPackage "BettiBounds" This package requires the package SimplicialComplexes.m2 Version 1.2 or higher, so install this first. *} -------------------------------------------------------------------- -- the commands available to the user: export {"stellarSubdivision","champion","bettiBounds","gradedBettiChampion","cache"} needsPackage "SimplicialComplexes" if version#"VERSION" < "1.4" then error "This package was written for Macaulay2 Version 1.4 or higher."; if (options SimplicialComplexes).Version < "1.2" then error "This package requires the SimplicialComplexes package Version 1.2 or higher." cache=new CacheTable from {}; gradedBettiChampion=method() gradedBettiChampion(ZZ):=(c)->( B:=gradedBettiChampion(c,c); scan(keys cache, j->remove(cache,j)); B); hypersurfaceBetti=method() hypersurfaceBetti(ZZ):=(d)->( x:=symbol x; R:=QQ[x]; betti res ideal(x^d)) computeq=method() computeq(ZZ):=(c)->( d:={0}; for j from 1 to c-1 do ( dj:=d#(j-1)+c-j+1; d=join(d,{dj}) ); d#(c-1)) --hypersurfaceBetti computeq 3 fixDegrees=method() fixDegrees(BettiTally):=(B)->( Bh:=new HashTable from B; Bhm:=new MutableHashTable from B; L:=apply(keys Bhm, j->((j#0,{j#2},j#2)=>Bhm#j)); new BettiTally from L) doCancelation=method() doCancelation(BettiTally):=(B)->( Bh:=new HashTable from B; Bhm:=new MutableHashTable from B; Bhm#(1, {1}, 1)=Bhm#(1, {1}, 1)-1; Bhm#(0, {1}, 1)=Bhm#(0, {1}, 1)-1; r:=regularity B; c:=pdim B; Bhm#(c-1, {r+c-1}, r+c-1)=Bhm#(c-1, {r+c-1}, r+c-1)-1; Bhm#(c, {r+c-1}, r+c-1)=Bhm#(c, {r+c-1}, r+c-1)-1; L:=apply(keys Bhm, j->(j=>Bhm#j)); new BettiTally from L); --doCancelation(BB) gradedBettiChampion(ZZ,ZZ):=(c,i)->( if member({c,i},keys cache) then ( --print(c,i); return(cache#{c,i}); ); if c==2 then ( if i==1 then return(hypersurfaceBetti(2)); if i==2 then ( x:=symbol x; y:=symbol y; z:=symbol z; R:=QQ[x,y,z]; I:=ideal(x,y*z); return(betti res I); ); ); if i==1 then ( q:=computeq(c); return(hypersurfaceBetti(q)); ); --print(c,i-1," ",c-1,i-1); bettiIdown:=gradedBettiChampion(c,i-1); bettiID:=gradedBettiChampion(c-1,i-1); B:=bettiIdown+fixDegrees(bettiIdown(-1)[-1])+fixDegrees(bettiID(-1))+fixDegrees(bettiID(-c)[-1]); B=doCancelation B; cache#{c,i}=B; B); --gradedBettiChampion(2,1) --gradedBettiChampion(2,2) {* restart installPackage "BettiBounds" time(gradedBettiChampion 20); *} {* gradedBettiChampion(BettiTally):=(bettiIdown)->( c:=1+codim Idown; bettiID:=gradedBettiChampion(c-1); bettiIdown+bettiIdown(-1)[-1]+bettiID(-1)+bettiID(-c)[-1]; ) *} champion=method() champion(ZZ):=(c)->( d:={0}; for j from 1 to c-1 do ( dj:=d#(j-1)+c-j+1; d=join(d,{dj}) ); sigma:={{}}; for j from 1 to c-1 do ( sigmaj:=toList(join(apply(1..(j-1),jj->sigma#jj#(j-2)),(d#(j-1) + 1)..(d#j))); sigma=join(sigma,{sigmaj}); ); q:=d#(c-1); if c==1 then q=q+3; if c==2 then q=q+1; x:=symbol x; R:=QQ[x_1..x_q]; I:=monomialIdeal(product(gens R)); D:=simplicialComplex I; D1:=D; for i from 1 to c-1 do ( j:=q+i; S:=QQ[x_j]; T:= ring D1; F:=face apply(sigma#i,jj->T_(jj-1)); Idown:=ideal D1; bettiIdown:=betti res Idown; D1=stellarSubdivision(D1,F,S); Iup:=ideal D1; Rup:=ring Iup; bettiID:=betti res ideal diff(sub(x_j,Rup),gens Iup); bettiIup:=betti res Iup; bettiAdd:=bettiIdown+bettiIdown(-1)[-1]+bettiID(-1)+bettiID(-c)[-1]; --print("Betti down "|net(bettiIdown)|" + Betti ID "|net(bettiID)|" -> Betti addition "|net(bettiAdd)|" Betti Iup "|net(bettiIup)); ); D1) {* champion(ZZ,ZZ):=(c,q)->( d:={0}; for j from 1 to c-1 do ( dj:=d#(j-1)+c-j+1; d=join(d,{dj}) ); sigma:={{}}; for j from 1 to c-1 do ( sigmaj:=toList(join(apply(1..(j-1),jj->sigma#jj#(j-2)),(d#(j-1) + 1)..(d#j))); sigma=join(sigma,{sigmaj}); ); x:=symbol x; R:=QQ[x_1..x_q]; I:=monomialIdeal(product(gens R)); D:=simplicialComplex I; D1:=D; for i from 1 to c-1 do ( j:=q+i; S:=QQ[x_j]; T:= ring D1; F:=face apply(sigma#i,jj->T_(jj-1)); Idown:=ideal D1; bettiIdown:=betti res Idown; D1=stellarSubdivision(D1,F,S); Iup:=ideal D1; Rup:=ring Iup; bettiID:=betti res ideal diff(sub(x_j,Rup),gens Iup); bettiIup:=betti res Iup; bettiAdd:=bettiIdown+bettiIdown(-1)[-1]+bettiID(-1)+bettiID(-c)[-1]; print("Betti down "|net(bettiIdown)|" + Betti ID "|net(bettiID)|" -> Betti addition "|net(bettiAdd)|" Betti Iup "|net(bettiIup)); ); D1) *} --------------------------------------------------------------------- -- some usefull stuff for chain complexes -- with this method also the substituted complexes -- recognize, when printed, if a name is assigned to -- the ring of the complex substitute(ChainComplex,Ring):=(cc,S)->( dual cc; cn:= new ChainComplex; cn.ring = S; for i from min(cc) to max(cc) do cn#i = S^(degrees (cc#i)); for i from min(cc)+1 to max(cc) do cn.dd_i = sub(cc.dd_i,S); cn) -------------------------------------------------------------------------- -- Stellar subdivision code stellarSubdivisionSimplex=method() stellarSubdivisionSimplex(Face,Face,PolynomialRing,PolynomialRing):=(D,s,n,R)->( if isSubface(s,D) then facets(subdivideFace (D,s,n,R),useFaceClass=>true) else {substitute(D,R)}) -- stellar subdivision of a simplicial complex with respect to the face -- introducing a new variable stellarSubdivision=method() stellarSubdivision(SimplicialComplex,Face,PolynomialRing):= (D,s0,n) -> ( R1:=ring D; s:=substitute(s0,R1); if not isFaceOf(s,D) then ( error "second argument is not a face of the first argument"; ); fc:=facets(D,useFaceClass=>true); R1=ring D; K:=coefficientRing R1; v:=join(gens R1,gens n); R:=K(monoid[v]); L:=join toSequence for i to #fc-1 list stellarSubdivisionSimplex (fc#i,s,n,R); simplicialComplex L) joinFaces=method() joinFaces(Face,Face):=(F,G)->( v1:=vertices F; v2:=vertices G; face(v1|v2)) listMinus=method() listMinus(List,List):=(L1,L2)->( for i in L1 list if member(i,L2) then continue else i) coFace=method() coFace(Face,Face):=(F,G)->( v1:=vertices F; v2:=vertices G; R:=ring G; face(listMinus(v2,v1),R)) subdivideFace=method() subdivideFace(Face,Face,PolynomialRing,PolynomialRing):= (D,s,n,R) -> ( comp := substitute(coFace(s,D),R); nface:= substitute(face {n_0},R); nc:=joinFaces(comp,nface); vs:=vertices s; L := for i to #vs-1 list joinFaces(nc,substitute(coFace(face {vs#i},s),R)); simplicialComplex L) TEST /// R=QQ[x_1..x_6] I=monomialIdeal(product(gens R)) D=simplicialComplex I Dsigma=stellarSubdivision(D,face {x_1,x_2,x_3},QQ[t]) S=ring Dsigma assert(facets Dsigma == matrix {{x_2*x_3*x_5*x_6*t, x_1*x_3*x_5*x_6*t, x_1*x_2*x_5*x_6*t, x_2*x_3*x_4*x_6*t, x_1*x_3*x_4*x_6*t, x_1*x_2*x_4*x_6*t, x_2*x_3*x_4*x_5*t, x_1*x_3*x_4*x_5*t, x_1*x_2*x_4*x_5*t, x_2*x_3*x_4*x_5*x_6, x_1*x_3*x_4*x_5*x_6, x_1*x_2*x_4*x_5*x_6}}) /// ------------------------------------------------------------------------------------------------------------------ bettiBounds=method() bettiBounds(List):=L->( L2:=append(L,0); L1:=prepend(0,L); L12:=apply(#L1,j->2*L1#j+2*L2#j); L1x:=apply(#L12,j->if j<=1 then 1 else 0); L2x:=apply(#L12,j->if j>=#L12-2 then 1 else 0); apply(#L12,j->L12#j-L1x#j-L2x#j)) bettiBounds(ZZ):=c->( L:={1,1}; for j from 2 to c do ( L=bettiBounds L ); L) -- L={1,1} -- L=bettiBound(L) ------------------------------------------------------------------------------------------------------------------ -- documentation beginDocumentation() doc /// Key BettiBounds Headline Bounds for the Betti numbers of iterated stellar subdivisions of the boundary of a simplex. Description Text Using unprojection theory we give in [6] bounds for the Betti numbers of the Stanley-Reisner ring of a stellar subdivision of a Gorenstein* simplicial complex. Applying this result we obtain a bound for the total Betti numbers of iterated stellar subdivisions of the boundary complex of a simplex. This bound depends only on the number of stellars and we construct examples which prove that it is sharp. The purpose of this package is to give an implementation of this construction. Using Kustin-Miller addition of Betti tables, we provide an efficient way to compute the graded Betti tables of the examples. This works far beyond the range in which the resolution or even ideal can be computed directly. This package requires the package @HREF{"http://www.mathematik.uni-kl.de/~boehm/Macaulay2/SimplicialComplexes/SimplicialComplexes.m2","SimplicialComplexes.m2"}@ version 1.2 or higher, so install this first. {\bf References:} For the Kustin-Miller complex see: [1] {\it A. Kustin and M. Miller, Constructing big Gorenstein ideals from small ones, J. Algebra 85 (1983), 303-322}. [2] {\it S. Papadakis, Kustin-Miller unprojection with complexes, J. Algebraic Geometry 13 (2004), 249-268}, @HREF"http://arxiv.org/abs/math/0111195"@ [3] {\it J. Boehm, S. Papadakis: Implementing the Kustin-Miller complex construction, J. Softw. Algebra Geom. 4 (2012), 6-11}, @HREF"http://arxiv.org/abs/1103.2314"@ For the stellar subdivisions and unprojection see: [5] {\it J. Boehm, S. Papadakis: Stellar subdivisions and Stanley-Reisner rings of Gorenstein complexes, to appear in Australas. J. Combin.}, @HREF"http://arxiv.org/abs/0912.2151"@ For the bounds on the Betti numbers see [6] {\it J. Boehm, S. Papadakis: Bounds on the Betti numbers of successive stellar subdivisions of a simplex}, @HREF"http://arxiv.org/abs/1212.4358"@ /// doc /// Key (substitute,ChainComplex,Ring) Headline Substitute a chain complex to a new ring. Usage substitute(cc,R) Inputs cc:ChainComplex R:Ring Outputs :ChainComplex Description Text Substitute a chain complex cc to a new ring R. Example R=QQ[x_1..x_4,z_1]; cc=res ideal(x_4*x_3, -x_1*x_2+x_4*z_1); cs=substitute(cc,QQ[x_1..x_4]) cs.dd_1 SeeAlso substitute /// doc /// Key stellarSubdivision (stellarSubdivision,SimplicialComplex,Face,PolynomialRing) Headline Compute the stellar subdivision of a simplicial complex. Usage stellarSubdivision(D,F,S) Inputs D:SimplicialComplex a simplicial complex on the variables of the polynomial ring R. F:Face a face of D S:PolynomialRing a polynomial ring in one variable corresponding to the new vertex Outputs :SimplicialComplex the stellar subdivision of D with respect to F and S Description Text Computes the stellar subdivision of a simplicial complex D by subdividing the face F with a new vertex corresponding to the variable of S. The result is a complex on the variables of R \otimes S. It is a subcomplex of the simplex on the variables of R \otimes S. Example R=QQ[x_0..x_4]; I=monomialIdeal(x_0*x_1,x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_0); betti res I D=simplicialComplex I fc=facets(D,useFaceClass=>true) S=QQ[x_5] D5=stellarSubdivision(D,fc#0,S) I5=ideal D5 betti res I5 Text Example R=QQ[x_1..x_6] I=monomialIdeal product gens R D=simplicialComplex I S=QQ[x_7] Dsigma=stellarSubdivision(D,face {x_1,x_2,x_3},S) betti res ideal Dsigma SeeAlso simplicialComplex facets ideal /// doc /// Key champion (champion,ZZ) Headline Compute simplicial complexes with maximal total Betti numbers Usage champion(c) Inputs c:ZZ codimension, positive Outputs D:SimplicialComplex Description Text Computes a simplicial complex of dimension $q$ on $q+c$ variables with maximal total Betti numbers bounds among all complexes obtained by a sequence of $c-1$ stellar subdivisions from the boundary complex of any simplex. Given $c$ the function chooses $q$ appropriately. This implements the construction given in Section 5 of [6] {\it J. Boehm, S. Papadakis: Bounds on the Betti numbers of successive stellar subdivisions of a simplex}, @HREF"http://arxiv.org/abs/1212.4358"@ Example champion 3 ideal champion 3 betti res ideal champion 1 betti res ideal champion 2 betti res ideal champion 3 betti res ideal champion 4 betti res ideal champion 5 SeeAlso gradedBettiChampion /// doc /// Key gradedBettiChampion (gradedBettiChampion,ZZ) (gradedBettiChampion,ZZ,ZZ) Headline Compute Betti tables of the examples with maximal total Betti numbers Usage gradedBettiChampion(c) gradedBettiChampion(c,i) Inputs c:ZZ codimension, positive Outputs D:SimplicialComplex Description Text Computes the Betti table of a simplicial complex of dimension $q$ on $q+c$ variables with maximal total Betti numbers bounds among all complexes obtained by a sequence of $c-1$ stellar subdivisions from the boundary complex of any simplex. By putting the additional argument $i$ one can obtain the Betti table of the $i$-th intermediate complex. For the construction of the simplicial complexes see Section 5 of [6] {\it J. Boehm, S. Papadakis: Bounds on the Betti numbers of successive stellar subdivisions of a simplex}, @HREF"http://arxiv.org/abs/1212.4358"@ Example gradedBettiChampion 3 gradedBettiChampion 4 gradedBettiChampion 5 gradedBettiChampion 6 gradedBettiChampion 10 Text Intermediate steps: Example gradedBettiChampion(3,1) gradedBettiChampion(3,2) gradedBettiChampion(3,3) SeeAlso bettiBounds champion "cache" /// doc /// Key "cache" Headline Cache table Description Text Caches the result of the function @TO gradedBettiChampion@, which uses double recursion. Once @TO (gradedBettiChampion,ZZ)@ finishes, the table is cleared. If you want to keep the results, use the method @TO (gradedBettiChampion,ZZ,ZZ)@ instead. Note that gradedBettiChampion(c,c) = gradedBettiChampion(c). Example time(gradedBettiChampion(20,20)); time(gradedBettiChampion(20)); time(gradedBettiChampion(20)); /// doc /// Key bettiBounds (bettiBounds,List) (bettiBounds,ZZ) Headline Compute the Betti bounds Usage bettiBounds(L) bettiBounds(c) Inputs L:List with the Betti bounds in codimension $c$ c:ZZ positive Outputs B:List with the Betti bounds in codimension $c+1$ Description Text Computes the Betti bounds for complexes which are obtained by $c-1$ iterated stellar subdivisions from the boundary complex of a simplex on $q+1$ vertices. The procedure can also be applied recursively to lists starting with the Betti numbers $L=\{1,1\}$ of a hypersurface. The $i$-th entry of B corresponds to the bound of the $i$-th Betti number. For example, B#1 is the bound on the number of generators. The first and the last entry of B is always $1$. The number of entries of B is $c+1$. Example bettiBounds(1) bettiBounds(2) bettiBounds(3) bettiBounds(4) bettiBounds(5) Text Alternatively one can also do: Example L={1,1} L=bettiBounds(L) L=bettiBounds(L) L=bettiBounds(L) L=bettiBounds(L) SeeAlso gradedBettiChampion /// ----------------------------------------------------------------- -- Tests -- test stellar subdivision code TEST /// K=QQ; R=K[x_0..x_4]; I=monomialIdeal(x_0*x_1,x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_0); D=simplicialComplex I S=K[x_5] D5=stellarSubdivision(D,face {x_0,x_2},S) I5=ideal D5 use ring I5 assert(I5==ideal(x_4*x_5,x_3*x_5,x_1*x_5,x_3*x_4,x_0*x_4,x_2*x_3,x_1*x_2,x_0*x_2,x_0*x_1)); /// {* check "BettiBounds" uninstallPackage("BettiBounds") installPackage("BettiBounds") installPackage("BettiBounds",RerunExamples=>true) viewHelp("BettiBounds") *}