Ideal membership testing raises ValueError

[mcncm]

An exception can be raised by testing membership of an element contained in a ring ideal, perhaps due to a bug in the Groebner basis algorithms.

The following minimal working example exercises the bug in Sympy 1.12:

from sympy import Symbol, QQ
x = Symbol('x')
R = QQ.old_poly_ring(x)
I = R.ideal(0, x)
I.contains(x)

The final line should evaluate to true, but instead raises an exception, with a stack trace ending in:

File /path/to/python3.11/site-packages/sympy/polys/distributedmodules.py:341, in sdm_deg(f)
    327 def sdm_deg(f):
    328     """
    329     Degree of ``f``.
    330 
   (...)
    339     7
    340     """
--> 341     return max(sdm_monomial_deg(M[0]) for M in f)

ValueError: max() arg is an empty sequence

Curiously, the error does not occur if the ideal is replaced with any of R.ideal(0), R.ideal(x), R.ideal(0, 0) or R.ideal(x, x), and the correct result is obtained in all of these cases.

[oscarbenjamin]

I guess it just needs a special case for zero as a generator. Maybe zeros should be removed at instantiation.

[mcncm]

I think you're right that removing zero generators would relieve the symptom, but it's not obvious without deep knowledge of the codebase—which I lack!—that it would solve the problem robustly. For example, is it definitely the case that an ideal generated by x and x will never be transformed into one generated by x and x - x = 0? It seems plausible to me that a safer, root-cause fix could be to ensure that sympy.polys.distributedmodules.sdm_deg assigns a degree of (e.g.) negative infinity to the zero polynomial, and to regard zero-removal-at-instantiation as a sort of optimization. But if you know the project well (forgive me if you're a core contributor and I'm just an interloper here!), and you're confident in the correctness of your solution, I'd be thrilled to see a pull request; I could even make it myself, if you like.

[oscarbenjamin]

For example, is it definitely the case that an ideal generated by x and x will never be transformed into one generated by x and x - x = 0?

The ideal is an immutable object that represents the mathematical ideal. I don't think it ever gets transformed into anything else but we could simplify it at creation time using various basic identities:

<0,f(x)>  ->   <f(x)>
<f(x),f(x)>  ->  <f(x)>

More generally the ideal for the Groebner basis should be the same as the ideal for the original generating set:

In [1]: groebner([x, 0], [x])
Out[1]: GroebnerBasis([x], x, domain=ℤ, order=lex)

In [2]: groebner([0], [x])
Out[2]: GroebnerBasis([], x, domain=ℤ, order=lex)

Computing a Groebner basis can be expensive though so probably should not be done automatically. Maybe in general it is better just to the ideal be as defined by the user without any canonicalisation though.

It seems plausible to me that a safer, root-cause fix could be to ensure that sympy.polys.distributedmodules.sdm_deg assigns a degree of (e.g.) negative infinity to the zero polynomial

Yes, that's what I meant by a special case for zero as a generator.

Feel free to submit a pull request with that as a fix.

[sylee957]

root-cause fix could be to ensure that sympy.polys.distributedmodules.sdm_deg assigns a degree of (e.g.) negative infinity to the zero polynomial, and to regard zero-removal-at-instantiation as a sort of optimization.

sympy/sympy/polys/distributedmodules.py

Line 332 in 999fd9b

Invalid if ``f`` is zero.

The documentation of sdm_deg says that it should be invalid when it is zero,
(This is hidden in your stack trace)
so I'm not sure if we fix it by extending the function to sentinel values, like float('-inf'), that may be reasonable, however, may be beyond any mathematical justification, so I'm not sure about it.

However, if the function should raise errors at zero, it may be reasonable to fix it from the preconditions where the function is used.

It is reasonable to check the loop of sdm_groebner and find if we should ignore zero polynomial in the loop there.
However, I think that the original article should also be read meticulously, such that we can find whether it is bug of sdm_groebner to fix, or zero polynomial is also excluded from the precondition of sdm_groebner. So the point to add to the discussion is, not only to fix the code, but also where to fix the code, such that it can be fixed most robustly.

[sylee957]

Computing a Groebner basis can be expensive though so probably should not be done automatically.

For even basic things like ideal.contains, computing groebner basis is needed, and I don't know much about any more efficient algorithms, depite that there can be incomplete algorithms (like using shallow heuristics)