ACA 2022


Effective ideal theory and combinatorial techniques

in commutative and non commutative rings

and their applications

SPECIAL SESSION at the 27TH International Conference on Applications of Computer Algebra (ACA2022)

15-19 August 2022, Istanbul-Gebze, Turkey

Hilbert's and Gordan's proofs of the Basissatz, which both consisted in giving an algorithm (an algorithm, not a procedure!) for producing a Groebner basis of a given ideal, settled the elementary approach toward Buchberger Theory: from the need of a term-ordering (stated implicitly by Hilbert and explicitly by Gordan) to the introduction of a rewriting procedure, which in Gordan is exactly Buchberger's.

The first group of researchers who deeply studied the notions and the tools introduced by Hilbert in his seminal paper, as Macaulay, Gunther and (mainly) Janet (who, studying with and under Hilbert, reinterpreted Riquier's results) are, consequently, the first which introduced the most important alternatives to Buchberger Algorithm for producing Groebner bases: Macaulay's Matrix from which Faugère's F4-F5 stemmed and Janet's involutive bases.

The influence that Gröbner bases have had on Algebra and Geometry during the last 40 years cannot be overstated; however, using Buchberger's algorithm as a default method in solving problems may lead to unnecessary computations.

Consequently, alternative algorithms have been proposed: Gröbner-free Solving (or, more generally, Degröbnerization), explicitly expressed and endorsed in Mora’s books, proposes to find alternative ways to get the same solutions, using, for example, tools from Linear Algebra and from Combinatorics.

In short, this approach consists in finding new ways to solve specific problems that have been originally solved using Gröbner basis computation and Buchberger's reduction, leaving the use of the latter only to the cases where it is really necessary; usually, the ``new ways'' consist in using linear algebra and combinatorial methods.

Degröbnerization is also largely used to study the reverse problem with respect to solving, namely the bonding problem for algebras and ideals:

Given the variety associated with a 0-dimensional ideal, i.e. a finite set of points, the structure of the quotient algebra (which actually contains more information than the ideal itself) can be recovered only using Combinatorics.

The four cornerstones of Degröbnerization are Auzinger-Stetter Matrices, Mourrain's notion of connected to 1, Lundqvist's fast algorithm for merging sorted lists of monomials and adding polynomials and Cerlienco-Mureddu Correspondence.

In this session, we unify researchers working on the two approaches introduced above:

  • improve/optimize/extend/generalize/apply to different problems Buchberger's, Janet's and Macaulay's algorithms;

  • degroebnerize problems via combinatorics and linear algebra.

Talks expected in this session include, but not reduce at, the following topics:

  • to improve and optimize Buchberger's, Janet's and Macaulay's algorithms;

  • to extend them to a wider class of (not necessarily commutative) rings; for instance Moeller's reformulation of Buchberger completion/test in terms of his Lifting Theorem is today available in each effectively given ring (in the sense used by Grete Hermann and van der Waerden)

  • recent developments on the theory - started by Hilbert - on “how to concretely manipulate polynomial ideals”, e.g. ideal theory, resolutions, Hilbert function,...

  • extensions to subalgebras

  • combinatorial techniques to deal with monomial/polynomial ideals

  • 0-dimensional solving\bonding problems

  • application of classical matrices for manipulating algebras and ideals

  • extension of degrobnerization to non 0-dimensional ideals

  • extension of degrobnerization to sub-algebras

  • tag-variable techniques

  • extension of degrobnerization to non-commutative settings

  • applications of both approaches, for example to coding theory, cryptography, reverse engineering, algebraic statistics and so on.

Call for abstracts: if you are interested in participating to this session, please send to the organizers an abstract (2-3 pages, both in .tex and .pdf) by the 31st of May, using the template available here.

Talks and speakers:


Michela Ceria

Department of Mechanics, Mathematics and Management - Politecnico di Bari -

André Leroy

Faculté Jean Perrin à Lens - Université d’Artois -

Samuel Lundqvist

Department of Mathematics - Stockholm University - SE-106 91 Stockholm, Sweden,

Teo Mora

Department of Mathematics - University of Genoa -