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