An Axiomatic Setup for Algorithmic Homological Algebra and an Alternative Approach to Localization

Abstract

In this paper we develop an axiomatic setup for algorithmic homological algebra of Abelian categories. This is done by exhibiting all existential quantifiers entering the definition of an Abelian category, which for the sake of computability need to be turned into constructive ones. We do this explicitly for the often-studied example Abelian category of finitely presented modules over a so-called computable ring $R$, i.e., a ring with an explicit algorithm to solve one-sided (in)homogeneous linear systems over $R$. For a finitely generated maximal ideal $\mathfrak{m}$ in a commutative ring $R$ we show how solving (in)homogeneous linear systems over $R_{\mathfrak{m}}$ can be reduced to solving associated systems over $R$. Hence, the computability of $R$ implies that of $R_{\mathfrak{m}}$. As a corollary we obtain the computability of the category of finitely presented $R_{\mathfrak{m}}$-modules as an Abelian category, without the need of a Mora-like algorithm. The reduction also yields, as a by-product, a complexity estimation for the ideal membership problem over local polynomial rings. Finally, in the case of localized polynomial rings we demonstrate the computational advantage of our homologically motivated alternative approach in comparison to an existing implementation of Mora's algorithm.

Fixed a typo in the proof of Lemma 4.3 spotted by Sebastian Posur

References in corpus (1)

• Homalg: A meta-package for homological algebra

Cited by in corpus (10)

• Gauge Backgrounds and Zero-Mode Counting in F-Theory
• Coxeter and crystallographic arrangements are inductively free
• On the Ext-computability of Serre quotient categories
• Characterizing Serre quotients with no section functor and applications to coherent sheaves
• Computing the nonfree locus of the moduli space of arrangements and Terao's freeness conjecture
• On the generation of rank 3 simple matroids with an application to Terao's freeness conjecture
• An algorithmic approach to Chevalley's Theorem on images of rational morphisms between affine varieties
• Linear systems over localizations of rings
• A constructive approach to Freyd categories
• On subdirect factors of a projective module and applications to system theory