Re: Krull dimension

*To*: mathgroup at smc.vnet.net*Subject*: [mg18538] Re: [mg18382] Krull dimension*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Sat, 10 Jul 1999 02:18:41 -0400*References*: <199906301813.OAA02862@smc.vnet.net.>*Sender*: owner-wri-mathgroup at wolfram.com

Eric Rowell wrote: > > Is there a way to compute the Krull dimension of a quotient of a polynomial ring > using mathematica? > Eric Rowell Classic case of a short query with an outrageously long response. The implementation below is based on an algorithm in Becker, T., V. Weispfenning (with H. Kredel). Groebner Bases: A Computational Approach to Commutative Algebra. Springer Verlag (Graduate Texts in Mathematics 141). 1993. Ch.9 section 3 p 449. It is unlikely that I can do justice to the explanation. So far as correctness goes, let's just say the code is on the honor system. First a brief intro to the background for those almost but not quite familiar with the ideas. The dimension we want is in this case equivalent to the transcendence degree of the quotient algebra K[vars]/I where I is the ideal, K is the base field (say the rationals as in the examples at the end), and vars are the variables for our polynomial algebra. As Eric reminded me in private e-mail, more generally the Krull dimension can be defined in terms of maximal chains of prime ideals. I believe this definition may be found in some of the standard commutative algebra references but I do not have one handy to check at the moment. There is related material in Ch. 7, sec. 5 of the Becker/Weispfenning text though alas is somewhat divorced from the definitions of dimension that appear elsewhere in that book. Anyway, the idea is this. The transcendence degree is given by the size of any largest set of variables S such that K[S] intersect I is empty (the proper phraseology involves "elimination ideals"). For example, if you have a "random" ideal generated by two polynomials in three variables, then there will be no polynomials in that ideal that are univariate, but there will be polynomials that involve all pairs of variables, hence the dimension will be one. There is a notion of strong dimension that is more readily computed. It is a function of a specified term ordering for the ideal and may be computed using the head terms of the Groebner bases computed with that term ordering. For each head term we extract the set of variables it uses; any set of variables that contains NONE of these head term sets is strongly independent of the ideal with respect to that term ordering. It is shown in the reference above that this coincides with ordinary dimension (transcendence degree). Actually they show alot more. But all we need to find is a largest maximal subset of variables S that does not contain any of the head term variable subsets. The phrase "largest maximal" is not redundant, by the way. Largest refers to length, while maximal is in the sense of partial ordering by inclusion. I'll try to give a brief explanation of the code. I'd not advise paying any attention to the code without first checking the reference (even then, for what was about half-a-dozen lines of pseudocode, I found it no easy matter to understand). The function isIndependentSet will take a set of subsets that comprises the variable sets used in each head term, and it will check whether a given subset of variables contains none of those subsets. This gives the strong independence criterion noted above. The main function is getMaxIndependentSets. It is based on the DIMREC algorithm in the reference but as we are only interested in dimension I take one or two shortcuts. (Note the pseudocode has a typo, it is missing a T(...) around the U union {X_i}, for those of you who are dutifully checking the text). Anyway, the idea is that we successively augment a given independent set with a new variable (we begin with the empty set which is vacuously independnet). If this augmented set is also independent then call recursively to see if we can augment by more variables. If not, we add this one to a list of maximal (by inclusion ordering) independent sets. For efficiency we keep tabs on the largest thus far because we can take an early exit from the main loop if there is no hope of beating that max (the algorithm in the text finds all maximal subsets of independent variables, hence does not do this). So while we do not necessarily find all maximal-by-inclusion independent subsets we will get at least one such with longest length. This suffices for our purposes. The driver routine, krullDimension, finds the subsets of variables that appear in each head term as given by a particular term order. (To get at this we use an internal function, Internal`DistributedTermsList. It is only in version 4 of Mathematica and replaces the never-officially-documented MonomialList of version 3. If anyone wants to know more detail about this newcomer just ask me. But keep in mind that it is not in a documented context and may change in later versions.) To see how the subsets are formed you could experiment with the lines below. I know that's a flimsy excuse but the relevant code is a bit too ugly to explain. polys = {x^2*y + 3*x*z - 4, y^2 - x*y + z + 2}; vars = {x,y,z}; ord = MonomialOrder->DegreeReverseLexicographic; gb = GroebnerBasis[polys, vars, ord]; pheads = Map[First[First[#]]&, First[Internal`DistributedTermsList[gb, vars, ord]]] crushedheads = (Map[(vars*#)&, (pheads /. _?Positive->1)] /. 0->Sequence[]) One last remark is that I did not code this for super efficiency. For most purposes, say when the number of variables is less than a dozen or so, it would make more sense just to generate the subsets ordered by decreasing size, then successvely test for strong independence and stop as soon as you get an inde[pendent subset. Chances are with that many variables you'll hang in the GroebnerBasis computation anyway. Moreover even adopting the strategy I used, roughly that of the Becker&Weispfenning algorithm, one might still chose other ways to represent the variable subsets, say as bit vectors, and this could give greater efficiency from the point of view of algorithmic complexity. None of which is terribly important because the main bottleneck, as I said, lies elsewhere. firstContainsSecond[l1_, l2_] := (Union[l1,l2]===l1) isIndependentSet[set_, sets_] := Map[!firstContainsSecond[set,#]&, sets] getMaxIndependentSets[vars_, inset_, heds_, maxlen_, indx_, sets_] := Module[ {currentset, vlen=Length[vars], ilen=Length[inset], enlarged=False, newmax=maxlen, maxsets=sets}, Do [ If [ilen+vlen-i+1 <= maxlen, Break[]]; currentset = Append[inset, vars[[i]]]; If [isIndependentSet[currentset, heds], {maxsets, enlarged, newmax} = getMaxIndependentSets[vars, currentset, heds, newmax, i+1, maxsets]; If [!enlarged, maxsets = {maxsets, currentset}; newmax = Max[newmax,Length[currentset]]; enlarged = True; ]; ], {i,indx,vlen}]; {maxsets, enlarged, newmax} ] krullDimension[ideal_, vars_] := Module[ {ord=MonomialOrder->DegreeReverseLexicographic, gb, pheads, heds, maxsets, el, mlen}, gb = GroebnerBasis[ideal, vars, ord]; pheads = Map[First[First[#]]&, First[Internal`DistributedTermsList[gb, vars, ord]]]; heds = Apply[And, (Map[(vars*#)&, (pheads /. _?Positive->1)] /. 0->Sequence[])]; {maxsets, el, mlen} = getMaxIndependentSets[vars, {}, heds, 0, 1, {}]; mlen ] I'll illustrate with a pair of "random" examples. The first is an ideal generated by two polynomials in three variables so we expect the dimension to be 1. The second is generated by three polynomials in five variables so the expected dimension is two. In[5]:= polys1 = {x^2*y + 3*x*z - 4, y^2 - x*y + z + 2}; In[6]:= vars1 = {x,y,z}; In[7]:= Timing[krullDimension[polys1, vars1]] Out[7]= {0.07 Second, 1} In[8]:= polys2 = {x^2*y + 3*w*x*z - 4, t*y^2 - w^2*x*y + t*z + 2*x-3, w*x^2*y + 2*t^2*x*z^2 - 5*w*y*z^2 +7}; In[9]:= vars2 = {t,w,x,y,z}; In[10]:= Timing[krullDimension[polys2, vars2]] Out[10]= {0.96 Second, 2} I hope this is helpful or at least answers a question somehow related to the one that was asked. Feel free to send along any problems/questions/complaints/suggestions/remarks. Daniel Lichtblau Wolfram Research

**Linear Interpolation**

**Problem with "Run" command on WindowsNT**

**Re: Krull dimension**

**Re: trig asymptotics**