Affine maps on finite groups

Nowadays, one often wants to simulate randomness on electronic devices (imagine, for example, an MP3 player randomly playing tracks from a certain playlist). To this end, one uses certain computation procedures to compute the next output from the previous such that the resulting list of outputs looks random to someone who does not know the computation rule. Furthermore, in modern cryptography, one uses certain computation procedures to transform the information which one wants to protect into something potential eavesdroppers cannot convert back because they lack some secret information related to the computation and only known to the intended receiver. Both examples have in common that they are practical applications of certain computation procedures designed by mathematicians, with different formal requirements on the procedure in each case. These computations are not the usual computations with numbers, but they are carried out in certain finite algebraic structures called groups. So far, certain aspects of such computation procedures suitable for practice are well-studied and well-understood only on certain finite groups with a particularly nice structure (those in which the commutativity law holds), and it is of interest to know whether or not one could do equally well or even better by using groups with a more complicated structure. Inter alia, our project Affine maps on finite groups is about this. More precisely, we will investigate three issues, two of them motivated by practice, and attack them by proving exact results with mathematical methods. Firstly, we will aim at a theoretical justification for several classical computation procedures used to simulate randomness, namely through a classification of all so-called affine maps (a particular kind of computation procedure) satisfying a certain minimum requirement for practical applicability. Secondly, motivated by cryptography, we will derive bounds on measures for how far from being affine a computation procedure on a finite group is. Inter alia, we hope to answer the question if one can do better with respect to this aspect in the groups where the commutativity law does not hold by this approach. Finally, we will also investigate the problem of reconstructing a particularly nice kind of affine map (called automorphism) on a finite group from certain fragments of information on it. This is an important (and difficult) problem, and we will establish a relationship with a similar and well-studied problem from group theory.

A computation structure is a collection of objects (such as numbers) with which one can compute (for example, because any two of these objects can be added or multiplied). Finite groups in the mathematical sense are certain kinds of computation structures that have applications in the study of the symmetries of geometrical objects and in the encryption of messages, among other things. However, finite groups also have symmetries themselves (in a certain abstract sense), and just as the investigation of the symmetries of a geometrical object allows one to learn things about that object, finite groups too can be better understood through studying their symmetries. Many known results concerning the symmetries of finite groups are of a qualitative nature - for example, they are concerned with assumptions on all symmetries, or they assume that certain measures with regard to symmetries are as large as possible. This project, on the other hand, dealt with quantitative questions concerning symmetries of finite groups, respectively concerning a slightly more general concept called "affine maps" (which gave this project its name). Many of the results obtained in this project can be viewed as quantitative generalizations of known qualitative results. In what follows, I present an example that I count among the most significant results of this project. Let us say that a geometric object, such as a cube, is called "maximally symmetric" if through its symmetries, the said object can be reflected and rotated such that any two corners of the object can be moved into each other. This is a qualitative definition, and in a more general, quantitative sense, one can define a geometric object as "highly symmetric" if not necessarily all, but at least "many" of the corners of the object can be moved into each other in that way. This is deliberately formulated vaguely, to allow the freedom of choosing and investigating different definitions of "many corners", such as "more than half of the corners", or "at least ten percent of the corners". For finite groups, there are analogously defined concepts, and it is very easy to understand the "maximally symmetric" finite groups completely. This project, however, investigated "highly symmetric" finite groups, which is considerably harder, had never been done before, and led to very interesting results, which were published in the internationally highly regarded "Journal of Algebra". Beside these and other quantitative results on symmetries and affine maps of finite groups, the project also generated efficient computation methods in the context of affine maps, and (in the framework of national and international collaborations) three research articles on other group-theoretic topics were written.