Re: commutative polynomial ideals in Mathematica and Maple



Roman Pearce wrote:
> [...]
> To test whether a zero-dimensional ideal is radical the algorithm that
> you have in mind is this: compute each univariate polynomial and check
> that it is square free (Seidenburg 1974). If you happen to find that a
> lexicographic Groebner basis contains one univariate polynomial and
> linear polynomials in the other variables, then as you observed the
> ideal is maximal and you can deduce that it is also radical. However,
> in the cases of kinema and katsura-6 this doesn't happen and you will
> actually have to compute each univariate polynomial using this method.
> So you will have to do more work. Both of these ideals are radical.

Thank you for the correction.

What I did appears to be a prime ideal test for zero dimensional
ideals. This amounts to testing for maximal ideals, as you observe.
About the only advantage this offers (as a maximal ideal test) is that
there is no longer a general position requirement or reliance on a
generic linear change of coordinates in one variable.

At least what I sent was better than my earlier attempt. In that one I
mistakenly was testing that an ideal is contained in its radical. Far
simpler would have been something like f[x_]:=True...

Anyway, here is the corrected zero dimensional radical ideal test,
along the lines of the code I previously showed. The change is to
insist that all univariates be square free.

zeroDimensionalRadicalQ[polys_] := Catch[Module[
{gb, vars=Variables[polys], len, leadvecs, pureterms, dtl},
len = Length[vars];
gb = GroebnerBasis[polys, vars,
MonomialOrder->DegreeReverseLexicographic];
dtl = First[Internal`DistributedTermsList[gb, vars,
MonomialOrder->DegreeReverseLexicographic]];
leadvecs = Map[#[[1,1]]&, dtl];
pureterms = Select[leadvecs, Count[#,a_ /;a=!=0]===1&];
If [Length[pureterms]<len, Throw[False]];
checkUnivariatePolynomials[gb,vars]
]]

checkUnivariatePolynomials[basis_,vars_] := Module[
{unipolys, len=Length[vars], newgb, poly},
Do [
newvars = RotateRight[vars,j];
newgb = GroebnerBasis[basis, newvars,
Method->{"GroebnerWalk"}];
poly = First[GroebnerBasis[newgb, newvars]];
fax = Rest[FactorSquareFreeList[poly]];
If [Apply[Times,fax[[All,2]]]!=1, Throw[False]];
, {j,len}];
True
]

To see that an ideal is radical now involves finding univariates in all
variables, and this is time consuming.

polys4 = {z1^2+z2^2+z3^2-12*z1-68, z4^2+z5^2+z6^2-12*z5-68,
z7^2+z8^2+z9^2-24*z8-12*z9+100, z1*z4+z2*z5+z3*z6-6*z1-6*z5-52,
z1*z7+z2*z8+z3*z9-6*z1-12*z8-6*z9+64, z1+z3-2*z4+z5-z6+2*z7-2*z8+8,
2*z2+2*z3-z4-z5-2*z6-z7-z9+18, z1+z2+2*z3+2*z4+2*z6-2*z7+z8-z9-38,
z4*z7+z5*z8+z6*z9-6*z5-12*z8-6*z9+32};

In[6]:= Timing[zeroDimensionalRadicalQ[polys4]]
Out[6]= {166.78 Second, True}

polys7 = {2*z*t+2*u*y+2*x*v+2*w*y-v,
x^2+2*y^2+2*z^2+2*t^2+2*u^2+2*v^2+2*w^2-x,
x+2*y+2*z+2*t+2*u+2*v+2*w-1, 2*y*z+2*x*t+2*u*y+2*z*v+2*t*w-t,
2*x*y+2*y*z+2*z*t+2*t*u+2*u*v+2*v*w-y,
y^2+2*x*z+2*y*t+2*z*u+2*v*t+2*w*u-z, z^2+2*y*t+2*u*x+2*y*v+2*w*z-u};

In[8]:= Timing[zeroDimensionalRadicalQ[polys7]]
Out[8]= {251.125 Second, True}

So we now obtain correct results, but not too quickly.


> Maple 10 doesn't use this algorithm. We compute a prime decomposition
> of the radical (similar to primary decomposition, but you remove powers
> from the factors as you go). A little bookeeping allows us to
> determine what generators need to be added to the original ideal to
> make it radical. Thus we compute one lexicographic Groebner basis for
> this test. In the absence of modular methods this is significantly
> faster, because the time to compute one univariate polynomial is often
> comparable to the time for a full lexicographic Groebner basis.

Good method.


Daniel Lichtblau
Wolfram Research

.

Relevant Pages

  • Re: commutative polynomial ideals in Mathematica and Maple
    ... For primary decomposition of a zero-dimensional ideal, ... that's the basic idea of Maple's algorithm. ... Both of these ideals are radical. ...
    (sci.math.symbolic)
  • Re: hilberts nullstellensatz
    ... the intersection of all maximal ideals of R containing I. ... For every R in CC every prime ideal P is the intersection of all ... intersection of the prime ideals which strictly contain P. ...
    (sci.math)
  • Re: [Question] Dedekind Domain
    ... >> is a product of maximal ideals. ... is a unit in all but a finite number of the valuation rings; ... Commutative rings with restricted minimum condition. ...
    (sci.math)
  • Re: About characters on H^{oo}
    ... I'm interested in the following question: are there any other characters on H^, ... of commuttative Banach algebras shows that the maximal ideals ... If A is a Banach algebra with identity and I is a maximal ...
    (sci.math)
  • Re: The Maximal Ideal Quest
    ... ideals whose unions are all the nonunits. ... If M_1, .., M_k are maximal ideals and union of those M_is are ... nonunits, then there is no -th maximal ideal. ...
    (sci.math)