RFC: Maximal ideal in FriCAS

[Grégory Vanuxem]

Hello,

To continue, here is an implementation in PolynomialIdeal (file attached), to check if an ideal is maximal. I used Gemini first, checked its code manually (shape lemma for example that I didn't know), fixed 3 groebner basis computations to 1 computation for example, some improvements/issues remain I guess, and finally asked Claude to check the code. The algorithm is not totally deterministic for multi-variables (5 random attempts, Tschirnhaus) and uses the shape lemma that you should know. The rest is academic I think.

I assume it could be improved, and it might even contain some bugs. If you have any comments, improvements or fixes, I would be happy to read them.

Greg

     maximal?(I : Ideal, lvar : List VarSet) : Boolean ==

       element?(1, I) => false

       empty? lvar => empty? (groebner I).idl

       not zeroDim?(I, lvar) => false

       n : NNI := #lvar

       J := groebner I

       Jd := J.idl

       n = 1 =>

         empty? Jd => false

         g := Jd.first

         x := lvar.first

         deg := degree(univariate(g, x))

         deg = 0 => false

         deg = 1 => true

         if F has PolynomialFactorizationExplicit then -- TODO: implement for Nemo

           fl := factorList(factor(g)$DPoly)

           #fl = 1 and fl(1).exponent = 1

         else

           false

       x := lvar.last

       lv1 := remove(x, lvar)

       for attempt in 1..5 repeat

         if #Jd = n then

           ok : Boolean := true

           i : NNI := 1

           for f in Jd while ok repeat

             if i < n then

               if not isMonic?(f, lvar(i)) or degree(univariate(f, lvar(i))) ~= 1 then

                 ok := false

             i := i + 1

           if ok then

             g := Jd(n)

             deg := degree(univariate(g, x))

             deg = 0 => return false

             deg = 1 => return true

             if F has PolynomialFactorizationExplicit then

               fl := factorList(factor(g)$DPoly)

               return (#fl = 1 and fl(1).exponent = 1)

             else

               return false

         ranvals : List Z := [random(23)$Z for vv in lv1] -- use #lv1 ?

         val : DPoly := _+/[rv * (vv::DPoly) for vv in lv1 for rv in ranvals] + (x::DPoly)

         J := groebnerIdeal groebner [(univariate(p, x)).val for p in J.idl]

         Jd := J.idl

       false

     maximal?(I : Ideal) : Boolean == maximal?(I, "setUnion"/[variables g for g in I.idl])

[Grégory Vanuxem]

I finally managed to return an Union(Boolean, "failed") and added a more robust version that I have to work on it if this one fails:

(61) -> Id := ideal [x,y]

   (61)  [x, y]
        Type: PolynomialIdeal(Fraction(Integer),IndexedExponents(Symbol),Symbol,Polynomial(Fraction(Integer)))
(62) -> maximal? Id

   (62)  "failed"
                                                                                     Type: Union("failed",...)
(63) -> maximalCertified? Id

   (63)  true

Regards,

Greg

[Ralf Hemmecke]

Sorry, I have not really followed, but why should the signature be

maximal? : PolynomialIdeal(...) -> Union(Boolean, "failed")

? The ideal is either maximal or it is not. Am I wrong?

Ralf

[Grégory Vanuxem]

Le ven. 3 juil. 2026 à 14:54, 'Ralf Hemmecke' via FriCAS - computer algebra system <fricas...@googlegroups.com> a écrit :

Sorry, I have not really followed, but why should the signature be

maximal? : PolynomialIdeal(...) -> Union(Boolean, "failed")

? The ideal is either maximal or it is not. Am I wrong?

maximal? is heuristic (~probabilistic) for n>1 indeterminates but not expensive. For univariate cases, my need, actually it's enough. In the example above [x,y] with coefficients over a field the algorithm used in maximal? does not return true (falsely). I should probably improve it. So later, if I use multivariates, something like:

maximal?(Id) case "failed" =>  maximalCertified? Id

should do the job.

Greg

[Waldek Hebisch]

On Fri, Jul 03, 2026 at 01:50:32AM +0200, Grégory Vanuxem wrote:
> Hello,
>
> To continue, here is an implementation in PolynomialIdeal (file attached),
> to check if an ideal is maximal. I used Gemini first, checked its code
> manually (shape lemma for example that I didn't know), fixed 3 groebner
> basis computations to 1 computation for example, some improvements/issues
> remain I guess, and finally asked Claude to check the code. The algorithm
> is not totally deterministic for multi-variables (5 random attempts,
> Tschirnhaus) and uses the shape lemma that you should know. The rest is
> academic I think.
>
> I assume it could be improved, and it might even contain some bugs. If you
> have any comments, improvements or fixes, I would be happy to read them.

AFAICS the function 'zeroDimPrime?' in IdealDecompositionPackage promises
to do almost what you want (the difference is that it returns true for
ideal generated by 1, while normally such ideal is not considered to be
a maximal ideal).

You probably would be interested in 'prime?', but it is not
implemented in IdealDecompositionPackage.



--
Waldek Hebisch

[Grégory Vanuxem]

Hi,

Frankly speaking, I am not a mathematician, but when I first read you you seemed to me a 

--
                              Waldek Hebisch

--
You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/akf_V3jbqNNPRDwH%40fricas.org.