Clonoids: a unifying approach to equational logic and clones

In many areas of science, we encounter formal expressions: H2O in chemistry, www.jku.at in computer science, mv2 in physics, or x(y + 2) in mathematics. The last two expressions are terms; after assigning values to the variables, they represent a new value. Very often, the objects that are substiuted fort he variables and with which we compute are just numbers. However, for modeling many phenomena, one has to compute with objects other than numbers: vectors represent points in space, matrices can model movements of points, and a function can represent a quantity that changes over time. Even pocket calculators can nowadays compute with letters; in doing so, they calculate in an algebraic structure that is called the field of rational functions. The discipline algebra deals with calculations involving such objects; its subdomain universal algebra tries to provide a common view on all conceivable ways of calculating. In this area, we encounter terms such as x2 - y2 in two different roles: on one hand, they represent a quantity that depends on x and y, on the other hand they are parts of assertions such as (x+y)(x-y) = x2 - y2. These roles of terms are studied in two central areas of universal algebra, in the theory of function algebras or clones 1 and in equational logic. In clone theory, one asks which functions can be composed from given ones. For instance, from the logical gates and and not, we can compose circuits for each desired switching behaviour; the conjunctions or and not allow to represent every possible logical connection, for example by using (not A) or B as an expression to represent if A, then B. Clone theory describes which functions can be composed from given ones by revealing their intrinsic proberties. The second area, equational logic, investigates the calculation rules for given functions, such as the distributive law. In both areas, we find finiteness results at prominent places: for instance, sometimes all valid calculation rules in an algebra can be derived from just a few laws. During the last years, the authors of this proposal have proved two new finiteness results, and it came as a surprise that the same method could be applied to both clone theory and equational logic. The aim of this project is to investigate the observed parallelism, and to establish a new flow of information between these two areas. From this viewpoint, we plan to answer the following questions: which classes of algebraic structures can be described as those that avoid certain forbidden patterns? Is the reason that we cannot yet translate the functional description of a clone into its relational description that the underlying problem is algorthmically undecidable? How long does an expression have to be to express certain functions? For answering these questions, we plan to develop further some theoretical tools, such as commutator theory, and we want to capture the parallelism betwenn the two areas more prescisely. 1 The word clone is presumably a coinage derived from the closed one.

Clonoids: a unifying approach to equational logic and clones Which logical circuits can be constructed using only AND and OR-gates (but no NOT-gate)? Why can linear equations be solved much faster than nonlinear ones? Which functions can one compose using only addition and squaring (but no multiplication)? In all these questions, an algebraic approach is to collect different functions in one algebraic structure. Such structures are, e.g., near-rings, clones, or, if the functions map one domain into another one, clonoids. Clonoids have been introduced in 2014 and allowed to use algebraic methods for the solution of a problem in equational logic. In the present project, we started a more systematic investigation of such clonoids. In two dissertations, all clonoids between simple abelian groups were determined. The main tool was a representation of the functions by polynomials. Such a representation is possible when the given algebraic structure can be coordinatized by some other structure in which computation is easy; the essence is to assign a name from the easy structure to each element of the difficult structure, and to compute with these names. We could give several examples in which this method provides the fastest way of solving equations. Of course, the solution sets of equations depend on the complexity of the functions they contain. One measure of complexity is the degree of a function, which we studied in detail. Our paper on the connection between degree and solution sets was published in the well-established Journal of Algebra. Clonoids have provided a new view on Universal Algebraic Geometry, which considers the shape of solution sets of algebraic equations. We could use clonoids to show that the geometry of an algebra is often determined by the shape of some solution sets in low dimensions. As substructures of clones, clonoids also provide an insight into possible extensions of given algebras. Many questions in this area lead to the determination of those functions that can be composed from certain given ones. A remarkable result from the present project describes which polynomials can be obtained from x using only squaring and addition - surprisingly, a power x^i can be constructed best if the digit sum of i in its binary representation is low.