Incorrect containment test for submodule over multivariable polynomial ring

[DaveWitteMorris]

Steps To Reproduce

From this sage-devel thread:

sage: R.<x, y> = QQ[]
sage: F = FreeModule(R, 1)
sage: G = F.submodule([F([0])])
sage: vec = F([1])
sage: vec in G
True

Expected Behavior

The answer should be False, since the 0-submodule does not contain any nonzero vectors.

Actual Behavior

The answer is True. The behaviour is the same when QQ is replaced with ZZ, GF(p), CC, etc., but we do get the correct result (False) if R.<x, y> is replaced with R.<x>.

Additional Information

Partial diagnosis. Essentially, the __contains__ method of G executes the following code:

try:
    return G(vec) == vec

For R.<x,y>, we have:

sage: G(vec) == vec
True

So the containment test returns the incorrect answerTrue. For R.<x>, the expression G(vec) raises TypeError: element [1] is not in free module, as it should, because vec is not in G. So the basic problem seems to be unexpected behaviour of the element constructor of G in the case of multivariable polynomial rings.

Environment

• OS: not relevant.
• Sage Version: 10.6 and others.

Checklist

• I have searched the existing issues for a bug report that matches the one I want to file, without success.
• I have read the documentation and troubleshoot guide

[nbruin]

It's not a problem with 0-dimensional submodules either:

sage: R.<x,y> = QQ[]
sage: F=FreeModule(R, 2)
sage: G=F.submodule([F.0])
sage: F.1 in G
True
sage: G._element_constructor_(F.1)
(0, 1)

I'm not sure sage actually has the module machinery to work with modules over polynomial rings. It requires quite complicated groebner basis tricks. Macaulay2 and probably singular have them, so it could be interfaced, but is that already done? Clearly, presently the submodule G has a broken element constructor. Fixing it might be hard.

[DisneyHogg]

When one takes R.<x> = ZZ[] or R.<x> = ZZ.extension(polygen(ZZ)^2+3) the bug persists, where the type of G is Submodule_free_ambient_with_category, whereas taking R.<x> = QQ[] the bug does not occur and the type of G is FreeModule_submodule_pid_with_category.

What is happening here is that when the ring is not a PID G has class Submodule_free_ambient which is a subclass of Module_free_ambient. It is the _element_constructor_ for this latter class which does not check to see if vec can be written in terms of the supplied basis. When the ring is a PID G ends up a subclass of FreeModule_generic, and this has the _element_constructor_ which checks (by calling .coordinates(vec)) whether vec can be written in terms of the basis.

A possible solution is to give Submodule_free_ambient its own element constructor method which does attempt to check if a given element is in the span of the generators.

Exactly how it checks whether an element is in the span might be tricky, but a solution one could imagine when R is a multivariate polynomial ring would use the .lift() method available to elements of such rings (which does use Singular as Nils suggests). That is, to test if vec is in the submodule spanned by gens the test could look as follows:

r = len(vec)
g = vec[0]
I = R.ideal([gen_i[0] for gen_i in gens])
if not g in I:
    raise TypeError("element {!r} is not in free module".format(vec))
ss = g.lift(I)
if not all(vec[j] == sum(si*gen_i[j] for si, gen_i in zip(ss, gens)) for j in range(1, r)):
    raise TypeError("element {!r} is not in free module".format(vec))

Clearly this solution cannot work on the nose as the [0] entry in vec and each element of gens could be trivial, but a modification should probably work.

For R not a multivariate polynomial ring I do not know if there is an alternative approach one could use, and so a separate class for modules over a multivariate polynomial ring might need to be made so that this new element constructor can be implemented safely.

[DisneyHogg]

Part of fixing this will involve working out exactly via which route G is contructed from F. When R is a multivariate polynomial ring it ends up as an instance of FreeModule_ambient_domain, which is a subclass of FreeModule_generic_domain and FreeModule_ambient.

F then inherits its submodule method from the FreeModule_ambient class. submodule essentially just calls span, which returns _submodule_class, which in this instance is Submodule_free_ambient as previously discussed.

It makes sense to model any proposed solution on the existing implementation that works for PIDs. In that instance F has class FreeModule_ambient_pid, which is a subclass of FreeModule_generic_pid and FreeModule_ambient_domain. The submodule method still comes from FreeModule_ambient, but now _submodule_class is set to FreeModule_submodule_pid.

This latter class is a subclass of FreeModule_submodule_with_basis_pid which itself is a subclass of FreeModule_generic_pid, which is a subclass of FreeModule_generic_domain.

Recall _element_constructor_ in the FreeModule_generic class uses a call to coordinates, which itself calls coordinate_vector. FreeModule_submodule_pid implements its own coordinate_vector method.

As such a proposed solution could be as follows.

1. Create classes FreeModule_submodule_mpolynomialring, FreeModule_submodule_with_basis_mpolynomialring, FreeModule_generic_mpolynomialring to mirror the PID construction, and give this class its own coordinate_vector method (based upon attempting to use the lift method). It's not clear to me what a method that gives coordinate_vector that is ensured to work could be, but in the event it fails it can return a message along the lines of "no valid coordinate vector found".
2. Add a warning to the _element_constructor_ of Submodule_free_ambient to warn users that containment in the span is not checked.