Identities in polymorphism algebras of infinite structures

An algebra consists of a set together with functions on this set. Examples are the set of integers together with the functions of addition and multiplication; the set of real numbers together with addition, multiplication, and the power function; or the set which has only two elements, 0 and 1, together with the maximum function. It is clear from their general definition that algebras are ubiquitous in mathematics, and naturally model real-world situations where we have objects (modeled by the elements of the set of the algebra) and some interaction between these objects (modeled by the functions on these elements). The structure of each algebra which appears in mathematics could, in theory, be studied separately, and this is also done for important algebras. The field of universal algebra, on the other hand, aims at understanding the structure of an algebra abstractly from the equations which hold in it, without considering a concrete algebra. For example, the set of integers together with addition satisfies the equations x-x+y=y=y-x+x, which has structural consequences in general: any algebra in which a similar equation holds for some its functions shares certain structural properties with this particular algebra. The theory of equations in finite algebras, such as the above-mentioned algebra on the set with elements 0,1 and the maximum function, has been studied since the beginnings of universal algebra, but has evolved rapidly recently since the discovery of important applications in theoretical computer science: finite algebras model the complexity of certain computational problems, and in fact the equations alone which hold in an algebra determine how complex the problem is. After almost twenty years of research on this connection, last year it was finally established precisely which equations imply that a computational problem can be computed efficiently. This project aims at lifting the strong recent methods for finite algebras to certain infinite algebras. While some sporadic surprising results for infinite algebras have been obtained recently, a general method for proving such results, as has been developed for finite algebras, is still missing. Our research is motivated by the above-mentioned application in theoretical computer science, but also has its own interest, since infinite algebras appear naturally; see the examples above. We also hope that by studying the finite methods in a wider context, we can gain a better understanding of them even in the finite.

An algebra consists of a set together with functions on this set. Examples are the set of integers together with the functions of addition and multiplication; the set of real numbers together with addition, multiplication, and the power function; or the set which has only two elements, 0 and 1, together with the maximum function. It is clear from their general definition that algebras are ubiquitous in mathematics, and naturally model real-world situations where we have objects (modeled by the elements of the set of the algebra) and some interaction between these objects (modeled by the functions on these elements). The structure of each algebra which appears in mathematics could, in theory, be studied separately, and this is also done for important algebras. The field of universal algebra, on the other hand, aims at understanding the structure of an algebra abstractly from the equations which hold in it, without considering a concrete algebra. For example, the set of integers together with addition satisfies the equations x-x+y=y=y-x+x, which has structural consequences in general: any algebra in which a similar equation holds for some its functions shares certain structural properties with this particular algebra. The theory of equations in finite algebras, such as the above-mentioned algebra on the set with elements 0,1 and the maximum function, has been studied since the beginnings of universal algebra, but has evolved rapidly recently since the discovery of important applications in theoretical computer science: finite algebras model the complexity of certain computational problems, and in fact the equations alone which hold in an algebra determine how complex the problem is. After almost twenty years of research on this connection, in 2017 it was finally established precisely which equations imply that a computational problem can be computed efficiently. This project lifted some of the strong recent methods for finite algebras to certain infinite algebras.