Localizations of modules over computable rings

For localizations of modules, there exists a generic implementation of the common methods such as membership tests, kernel computations, etc. based on the work of Barakat, Posur, et. al; see Sebastian Posur (2018).

Let $R$ be a ring of type <:Ring, $U \subset R$ a multiplicative set of type <:AbsMultSet and $S = R[U^{-1}]$ the localization of $R$ at $U$. Recall that $R$ is computable if one can compute syzygies and lifts over $R$. The results from Sebastian Posur (2018), Theorem 3.9, assert that then also the localization $S$ is computable, provided that there exists a solution to the localization problem (Definition 3.8, Sebastian Posur (2018) and below).

The user who wishes to use the generic code for localizations therefore has to make sure the following two requirements are met:

The code for finitely generated modules and ideals must be functional over $R$, including the computation of coordinates and kernel.
The user has to solve the localization problem by implementing has_nonempty_intersection(U::MultSetType, I::IdealType) for the type MultSetType of multiplicative sets and the type IdealType of ideals in R that they would like to consider.

has_nonempty_intersection — Method

has_nonempty_intersection(U::AbsMultSet, I::Ideal)

For a finitely generated ideal $I ⊂ R$ and a multiplicative set $U ⊂ R$, this checks whether the intersection $U ∩ I$ is nonempty and returns a triple

(success, f, a).

In the affirmative case, success is true, $f ∈ U ∩ I$ is some element in the intersection and $a ∈ R¹ˣᵏ$ is a Vector{elem_type(R)} such that $f = ∑ᵢ aᵢ⋅gᵢ$ where $gᵢ$ are the elements in gens(I).

When the intersection is empty, this returns (false, f, a) with meaningless values for $f$ and $a$.

Note: When implementing methods of this function, it is recommended to choose $f$ to be the 'least complex' in an appropriate sense for $R$.

source

Note: In order to clear denominators of row vectors, the generic code uses the method lcm(v::Vector{T}) where T = elem_type(R). If no such method already exists, this has to also be provided; in the worst case by simply returning the product of the denominators.

As soon as the above requirements are met, the methods

   represents_element(u::FreeModElem{T}, M::SubquoModule{T}) where {T<:AbsLocalizedRingElem}
   coordinates(u::FreeModElem{T}, M::SubquoModule{T}) where {T<:AbsLocalizedRingElem}
   kernel(f::FreeModuleHom{DomType, CodType, Nothing}) where {T, DomType<:FreeMod{T}, CodType<:SubquoModule{T}}
   kernel(f::SubQuoHom{DomType, CodType, Nothing}) where {T, DomType<:FreeMod{T}, CodType<:SubquoModule{T}}
   iszero(a::SubquoModuleElem{T}) where {T<:AbsLocalizedRingElem}

will be available for modules over $S$, i.e. for T = elem_type(S). As can easily be seen, having the first three of these methods is already equivalent to $S = R[U^{-1}]$ being computable; hence all higher methods can be derived from these basic ones.

The generic code makes use of a simple caching mechanism for the SubquoModules as follows. For a module $M = (G + N)/N$ with submodules $G, N \subset R^n$ of some free module, the localization $M[U^{-1}]$ over $S = R[U^{-1}]$ has an associated saturated module over $R$:

\[ M' = (G' + N')/N', \quad G' = \{ a \in R^n | \exists u \in U : u \cdot a \in G + N\},\quad N' = \{ b \in R^n | \exists u \in U : u \cdot b \in N\}.\]

While it might be difficult to compute such saturations, we have a generic algorithm to check membership for elements in $M'$ (via represents_element for $M[U^{-1}]$). It is assumed that such membership tests are cheaper for modules over $R$ compared to modules over $S$. For instance in the case where $R$ is a multivariate polynomial ring, once a (relative) groebner basis has been computed for $M$, membership test for $M$ is merely a reduction while for the localization $M[U^{-1}]$ it triggers another groebner basis computation a priori.

But for every element $a \in R^n$ that has already been shown to represent an element in the saturation $M'$, we can cache the results of the computation in an intermediate pre-saturated module $M \subset \tilde M \subset M'$ by adding the necessary generators to $G$ and $N$ for a representation of $a$. Then, checking membership for $a$ a second time will fall back to a membership test in $\tilde M$. For the latter, we assume some caching to already be implemented as, for instance, for the use of groebner bases in the polynomial case.

A sample implementation for various localizations of multivariate polynomial rings can be found in src/Modules/mpoly-localizations.jl. A modified version for localizations of affine algebras which also overwrites some of the generic methods, is in src/Modules/mpolyquo-localizations.jl.