Algebraic approaches to the description of Mal´cev clones

Historically, the main concern of algebra was that of solving equations. In order to describe the solvability of certain equations, N.H.Abel (1802-1829) and É. Galois computed with objects other than numbers: they collected permutations of the solutions of an equation into groups. Today, algebra studies how to compute with arbitrary mathematical objects, such as permutations, numbers, curves, files in a computer storage, or hierarchies in a group of people. Often, the number of objects used for these computations is finite. The goal of this project is to classify these finite algebraic structures. Here, we treat two algebras as equal if the operations of each of the algebras can be expressed using the operations of the other one. In technical terms, this means that the two algebras have the same "clone of term operations." For 25 years it has been known that there exist too many finite algebraic structures for representing each of them with a finite amount of information. However, many algebras actually encountered have an additional property: they are Mal`cev-algebras (named after A.I.Mal`cev (1909-1967)). It has been an open problem whether every Mal`cev algebra, even when it possesses infinitely many operations, can be represented by a finite amount of information, for example in a computer file. Since 2009 it has been known that every finite Mal`cev algebra can be described by finitely many properties of its operations. Although this implies that there does indeed exist a finite representation for each algebra, it is not yet clear how such a representation can be computed. It is one of the goals of the present proposal to clarify this point. The mathematical area that provides methods to study these problems is universal algebra, and, more specifically, the theory of function algebras (clones), the theory of polynomial interpolation in algebraic structures, and the theory of higher commutators in universal algebra. The present proposal contains some problem whose solution would contribute to the description of finite Mal`cev- clones. It is planned to develop the theory of higher commutators and to describe their relations to the polynomial functions of an algebra, to introduce and investigate new concepts of polynomial completeness, to examine the translation between the relational and functional representation of a clone, and to investigate the relational side of Mal`cev clones.

The aim of this project was to investigate the computational power of an algebra, which is captured in its set of term functions, using classic and modern algebraic structure theory. This interplay has given new results in equational logic, commutator theory, algebraic interpolation theory, classic algebraic structure theory and clone theory.In the view of the principal investigator, a major advance was a new application of clone theoretic methods to equational logic. The amount of failure of an equation, say x+y=y+x, was encoded into a function on the algebra. By comparing the possible amounts of failure, a problem in equational logic that had appeared explicitly among significant open problems in universal algebra was partially solved.The direct product of two algebraic structures is a new structure that arises from computing in both structures in parallel. It is interesting how these two algebras influence each other. We described how to test whether these algebras are independent, meaning that there is no influence of one to the other.Certain functions on arbitrary algebraic structures can be interpolated by well- behaved polynomial functions. It is an interesting question to determine those structures on which every congruence preserving function is a polynomial. The classicfication for groups of size at most 100 was completed.The theory of higher commutators in universal algebra was pushed further in two papers: one paper delimits the amount of possible commutator operations on a finite algebras, the other one describes the higher commutator in terms of preservation properties. Several results contribute to the description of the structure of nilpotent universal algebras.With an algebraic structure, one associates certain operations on this structure; these are called the clone of the algebra. Some new results describe when this clone can be represented by a finite amount of information. It has been attempted to broaden the language of clone theory so that it comprises certain gates used in theory of reversible computation, and it has been shown how to build arbitrary operations from basic logical gates, so called Toffoli-gates.