Signature Gröbner bases and cofactor computation in the free algebra,
Gröbner bases are a fundamental tool for solving systems of
polynomial equations, and performing arithmetic operations on
ideals. The most recent generation of algorithms computing Gröbner
bases are computing bases with so-called signatures. Those
signatures have proved to be useful far beyond their initial
purpose of eliminating reductions to zero: they also allow to
certify the results of a Gröbner basis computation, by
reconstructing coordinates of the basis elements, as well as
In the non-commutative case, Gröbner bases are used for evaluating
formulas in abstract algebra. A signature Gröbner basis of the
ideal, in addition to answering the question, would also give
sufficient data to reconstruct a proof of the computed
In this talk, we present signature Gröbner basis algorithms for
pure non-commutative polynomials, in the free algebra, and we show
that those algorithms can be used to reconstruct cofactors and
syzygies like in the commutative case.
A common difficulty with non-commutative Gröbner bases is that the
algorithms do not in general terminate. We show how signatures
allow to work around an obstruction to termination, and we
conjecture a characterization of ideals with a finite signature
(Joint work with Clemens Hofstadler).
Simone Naldi and Vincent Neiger,
Gröbner bases of syzygy modules and multivariate Padé approximation,
slides part 1 and
Given elements f_1,…,f_m in a quotient module R^n / N of finite dimension as a K-vector space, where R = K[x_1…x_r] and N is an R-submodule of R^n, we consider the problem of computing a Gröbner basis of the module of syzygies of (f_1,…,f_m). This is the set of vectors (p_1,…,p_m) in R^m such that p_1f_1+…+p_mf_m = 0. An iterative algorithm for this problem was given by Marinari, Möller, and Mora (1993) using a dual representation of quotient as the kernel of a collection of linear functionals.
We will present two recent complexity improvements upon this approach. One incorporates fast linear algebra operations, by leveraging the multiplication matrices of the variables in the quotient module. The other one introduces a divide-and-conquer scheme which generalizes to several variables Beckermann-Labahn's recursive approach for matrix Padé and rational interpolation problems. To highlight the interest of the latter method, we show a complexity improvement in the specific case of bivariate Padé approximation.
Categorifying Intersection Types,
We study a family of distributors-induced bicategorical models of lambda-calculus, proving that they can be syntactically presented via intersection type systems. We first introduce a class of 2-monads whose algebras are monoidal categories modelling resource management. We lift these monads to distributors and define a parametric Kleisli bicategory, giving a sufficient condition for its cartesian closure. In this framework we define a proof-relevant semantics: the interpretation of a term associates to it the set of its typing derivations in appropriate systems. We prove that our model characterize solvability, adapting reducibility techniques to our setting. We conclude by describing wo examples of our construction.
A formal description of coherence in abstract rewriting,
In higher-dimensional representation theory, categorification is a tool consisting in replacing representations of an algebra by vector spaces and linear maps by higher-dimensional categories and linear functors to obtain an enriched structure. Given an algebra A, a natural setting to categorify A is to define a 2-category presented by diagrammatic generators and relations in terms of string diagrams, and to prove the isomorphism between its Grothendieck group and the algebra. To that extent, a relevant question is to compute a set of linear bases for all the sets of 2-cells of the category. In this talk, we will show how these problems can be tackled using 3-dimensional linear rewriting theory. In particular, we describe the difficulties occuring in the proofs of termination and confluence in that context. We will illustrate these methods for the family of Khovanov-Lauda-Rouquier algebras arising in the process of categorifying a quantum group. We will discuss the construction of the categorification in that case, and how usual rewriting methods can be extend to compute bases for this latter
A formal description of coherence in abstract rewriting,
Kleene algebras have their origins in the theory of regular languages, but have more recently been used to describe properties of abstract rewriting systems (ARS). The latter capture equivalences between elements of a set via directed transformations. On the other hand, polygraphic rewriting techniques provide information about equivalences between higher dimensional objects such as paths. In particular, the question of coherence arises: are any two undirected paths equivalent modulo higher dimensional cells? In this talk we will see how the formal description of ARS via Kleene algebras may be combined with a higher dimensional approach. After explaining how properties of ARS may be expressed in Kleene algebras, we will introduce a notion of 2-Kleene algebra and describe how coherence properties may be captured therein. Finally, we will discuss the main result of this work: a formal coherence theorem for ARS. These are the fruits of a joint work with Eric Goubault, Philippe Malbos and Georg Struth.
Operads with compatible CL-shellable partition posets admit a PBW basis,
In 2007, Bruno Vallette built a bridge between posets and operads, linking a topological property for partition posets (Cohen-Macaulay) with an algebraic property for operads (being Koszul). While there are mainly one property refining being Koszul (admitting a PBW basis), there are several topological properties on posets refining Cohen-Macaulayness. In a joint work with Joan Bellier-Millès and Eric Hoffeck, we studied the link between admitting a PBW-basis and topological properties on posets. After recalling the needed notions on posets and operads, I will present our results.
Clone realizations of semigroup varieties,
Given a variety V of algebras (presented by generating operations and relations between
some of their compositions), a natural question consists in building a clone realization of
V. This consists in encoding the operations of V by combinatorial objects in such a way
that two equivalent ones have the same representation, and in providing an algorithm to
compute the representation of the functional composition of several operations. We introduce
the clone of colored words, which is a clone containing several substructures providing
clone realizations of some varieties. We obtain in this way clone realizations of various
classes of semigroups (commutative, left/right-regular bands, semilattices, etc.).
Presenting isomorphic finitely presented modules by equivalent matrices: a constructive approach,
A multidimensional linear system can be studied by means of its
associated module, presented by the unknown functions of this system
subject to the equations. Testing whether two linear systems/modules are
isomorphic (the so-called equivalence problem) is an important issue. In
this presentation, I will first recall from a previous work of
Thomas Cluzeau and Alban Quadrat an explicit characterisation for a
module morphism to be an isomorphism. Then, I will recall how they
obtained a constructive version of a result due to Fitting, which shows
how to enlarge matrices presenting isomorphic modules by blocks of zeros
and identities to get equivalent matrices. Finally, I will present an
inductive procedure for reducing the size of these two equivalent
matrices. It turns out that this procedure enables us to recover a result
due to Warfield.
Rewriting for Gray categories,
Recent works have extended the use of classical rewriting to higher dimensions. Among them, several (Lafont, Guiraud, Malbos, ...) have used strict categories as a framework for studying presentations of higher structures. Even though the simplicity of strict categories made them a prime candidate for such generalization, their use for this task is problematic in several aspects. In particular, since strict categories are not equivalent to weak categories starting from dimension 3, they can not be used to give the most general definition of weak structures. In this presentation, I will show how to extend the rewriting toolkit to 3-dimensional weak categories, which are known to be equivalent to Gray categories.
Diamond lemma through homotopical algebra,
The Diamond Lemma is a result indispensable to those studying associative (and other types of) algebras defined by generators and relations. In this talk, I will explain how to approach this celebrated result through the lens of homotopical algebra: we will see how every multigraded resolution of a monomial algebra leads to "its own" Diamond Lemma, which is hard-coded into the Maurer-Cartan equation of its tangent complex. For the reader familiar with homotopical algebra, we hope to provide a conceptual explanation of a very useful but perhaps technical result that guarantees uniqueness of normal forms through the analysis of "overlapping ambiguities". For a reader familiar with Gröbner bases or term rewriting theory, we hope to offer some intuition behind the Diamond Lemma and at the same time a framework to generalize it to other algebraic structures and optimise it. This is joint work with Vladimir Dotsenko (arXiv:2010.14792).
Diagrammatic sets and homotopically sound rewriting,
I will give an introduction to the theory of diagrammatic sets, a combinatorial framework for higher-dimensional rewriting, designed to be as close as possible to polygraphs in practice, but remain provably “sound for homotopical algebra”, thanks to a tighter connection to combinatorial models of homotopy types. I will sketch how diagrammatic sets support a model of weak higher categories, specialising to a model of higher groupoids that satisfies a version of the homotopy hypothesis. If there is time, I will discuss the “smash product of pointed diagrammatic sets” and its application to universal algebra, which initially motivated the whole project.
Computing noncommutative Gröbner bases and certifying operator identities,
We will recall the main results of the theory of Gröbner bases in the free
algebra. Additionally, we discuss an adaption of Faugère’s F4 algorithm to
this setting, which allows us to compute noncommutative Gröbner bases
using linear algebra. As an application of noncommutative Gröbner bases,
we also present a recently developed framework to rigorously prove operator
identities by verifying ideal membership of noncommutative polynomials.
Gröbner Bases in Cryptography through the example of the Rank Decoding Problem,
In this talk, I will briefly explain the purpose of asymmetric cryptography and why one is looking for hard problems in order to design secure cryptographic schemes. Then, I will introduce the celebrated post-quantum cryptography which is a response to the threat of quantum computers. Gröbner Basis can be used in cryptanalysis (the "attack" part of cryptography) and I will present our attack against one of the main problem in post-quantum cryptography, namely the Rank Decoding Problem.
Polygraphic homology of strict omega-categories,
In this talk, I will present the main results of my PhD thesis, which revolved around the polygraphic homology of strict omega-categories. After recalling the definition of polygraphic homology of strict omega-categories and its link to rewriting theory, I will explain how it compares but generally differs from another homology for strict omega-categories, which is the one defined via the Street nerve functor (which I will recall too). I will then try to give abstract and concrete criteria to detect the strict omega-categories for which both homologies do coincide, and I will use these criteria to give many examples of such strict omega-categories. I will end the talk by introducing the notion of "bubble-free 2-polygraph" and states the "bubble-free conjecture", which roughly says that these 2-polygraphs have good homological and homotopical properties.
Operadic rewriting and Koszulness,
Shuffle operads were introduced to make explicit the symmetric actions on symmetric operads. Rewriting methods were then applied to symmetric operads via these shuffle operads: in particular, a notion of Gröbner basis was introduced by Dotsenko and Khoroshkin for shuffle operads using a given monomial order.
First, we recall the definitions of Gröbner bases and Koszulness for shuffle operads. Then, we fit this rewriting approach in the more general framework of higher dimensional rewriting for shuffle operads. This framework allows us to explicitly construct an operadic resolution à la Anick, and we show a sufficient condition for Koszulness for operads.
March 4th and 11th:
February, 25th and March 4th:
Introduction to linear rewriting: Gröbner bases and reduction operators,
Strategies and resolutions,
Homotopical motivations of higher-dimensional rewriting,
3-polygraphs and Squier's completion Theorem,
2-polygraphs and string rewriting,
Cameron Calk and Benjamin Dupont,
Abstract rewriting and String rewriting systems, slides
part 1 and