Equations in Universal Algebra

Solving equations comprises an astonishingly large part of mathematics. Many fundamental scientific insights consist in capturing physical observations in simple equations, and solving equations allows us to predict the outcomes of many processes such as the falling of a solid body or the spread of a desease without experimentation. Solving equations can also be used for proving theorems in geometry: one determines those equations that a counterexample to the claimed assertion would have to fulfill and proves that these equations have no solution. In this case we are not so much interested in the concrete solutions, but just whether any solutions exist at all. Also in many other instances, one can replace logical reasoning by solving equations. In this case, one often calculates with object other than numbers, such as truth values, and uses new arithmetic operations for them: the operation OR, which computes false OR true as true is an operation describing that the assertion Paris lies in Switzerland or France is correct. We want to solve equations involving such new arithmetic operations. A first idea to solve any equation is to guess the solutions or to test all possible candidates. What seldom works in a maths test is a feasible strategy if the solutions can be picked out of a few candidates. For many operations, we are not aware of signifcantly better methods, and for some we can even prove that there is probably no more efficient method. For others, we have much faster solution methods. We try to classify some arithmetic operations into solving equations involving them is a nightmare and solving equations involving them is a simple task. Often, there is a logical connection between different equations: for example, every solution of the first equation may be a solution of the second one, but never of the third one. We aim at detecting such connections. The collection of all solutions of a given equation can be seen as geometric object. We investigate which objects arise in this way. A rather creative way to solve an equation is inventing a solution rather than finding it. A way to express this is: let x be a solution of . The invention of complex numbers can be seen this way: the imaginary unit i is just a number with i*i= -1. This does not always work: in some cases, the invented solution contradicts the laws of arithmetic, but in other cases the damage is smaller. In the present project, we strive for solving 17 concrete problems on equations formulated in the proposal.

Solving equations, through formulae or algorithms, is one of the fundamental problems of algebra. The difficulty of solving equations depends very much on which arithmetic operations occur in the equations. For example, if you only use addition and subtraction in the integers, you only have to solve linear systems for which there are good solution methods (such as Hermite decomposition). If multiplication is added, the problem of solving equations is already so difficult that there can no longer be a solution method: A famous result from 1972 by Matiyasevich says that there is no algorithm that determines whether such an equation has a solution in the integers. In many parts of mathematics, such as in coding theory or cryptology, we do not calculate with numbers, but with only a finite number of objects, such as 0 and 1 or 'true' and 'false'. However, if we are only looking for solutions in a finite pool of possibilities, we can simply try out all of these possibilities. Unfortunately, this is often too time-consuming: In an equation with n unknowns, for each of which 2 values are possible, we get 2^n possible solutions; that's already a billion of candidates for solutions for n=30. In this project, we were able to describe some circumstances that allow us to test far fewer candidates. We were able to show that the following statements hold for certain types of equations: 'If the equation has one solution, it has many solutions' and 'A solution can be found near every point'. Both of these statements are fulfilled, for example, in polynomial equations over finite fields. Thus, solutions are found either by randomly selecting candidates for solutions: if there are many solutions, there will soon be a solution among the candidates. Or you can search the entire neighbourhood of a point: if there is a solution, there is also a solution in the vicinity of this point. Instead of solving equations, one sometimes seeks to find logical connections between equations, for example in the form that every solution to an equation is also a solution to another equation. We showed that for certain algebraic structures, we proved that finding such connections is just as difficult as solving systems of equations. In the course of the project, the project members gave 4 invited plenary lectures and 27 lectures at international conferences or other universities and published 13 articles in scientific journals (including Journal of Algebra, International Journal of Algebra and Computation, Finite Fields and their Applications) and 8 conference articles (including the International Symposium on Theoretical Aspects of Computer Science (STACS) and the Mathematical Foundations of Computer Science (MFCS) conference). (Translated from the German version with the help of DeepL)