Translated from french by Grok

The purpose of this note is to analyze, from a methodological standpoint, our research on symmetric groups, alternating groups, and minimal chains (see our joint article with Robert Erra and Nigel Stewart: *On minimal strings containing by decimation the elements of Sₙ*).

The origin of our study is connected to the problem of representing three-dimensional images on a computer. More specifically, we became interested in strings that contain, by decimation, on the one hand all elements of the symmetric group (i.e., all permutations of an alphabet) and on the other hand all elements of the alternating group (i.e., all even permutations of an alphabet). In this approach, the objects to be represented by computer are simply encoded by letters, and by “decimation” we mean that if we remove certain letters from the considered string, we recover the letters of an element of the symmetric group or the alternating group, in the same order. Our study focused on minimal chains—in the sense of length—that satisfy this property. A minimal chain is of course not unique, since its reverse is also minimal. Moreover, since any minimal chain can be relabeled, we study only the normalized minimal chains.

The initial phase of our research consisted of, on one hand, implementing an exhaustive search algorithm in C++ to find solution strings and, on the other hand, establishing a theoretical upper bound on the sufficient length of the chain. It was this first phase that allowed us to obtain the first values of the formula we were seeking: 1, 3, 7, 12, and 19. We also noticed that it was easy to improve from the trivial length of n·n! down to (n·n) and especially to (n·n – n + 1). Thus we were operating within the framework of quadratic formulas. However, the values obtained through exhaustive search showed that even this last formula was not optimal. We therefore decided to systematically generate all solution strings for a given length. And there, as often happens in computer-involved research, we ended up with a multitude of solutions (more than a hundred). To better grasp the essential in this mass of results, we introduced constraints.

At this point, it is necessary to make a remark about introducing constraints in solving a given problem. A generic example of applying this method is the following problem: Using dominoes that each cover two squares, how many different tilings are there of an 8×8 chessboard from which two opposite corners (on the same diagonal) have been removed? Solving this problem, which may seem difficult at first glance (especially after an experimental phase), turns out to be elementary once constraints are introduced. In this case, the constraints are the colors! Indeed, if we consider the chessboard as a set of black and white squares, it is obvious that a domino, once placed, covers two squares of different colors. Yet the two removed corners, being on the same diagonal, are the same color. Q.E.D.

Thus we solved a problem by adding constraints and then removed them while preserving the solution! To proceed analogously, we selected a particular family among all the obtained solutions in order to recognize a pattern. It is, however, difficult to explain our choice except to say that the family was symmetric: in any case, in a certain way our pattern was intelligible, and that is probably the most important thing. From there, we explored the restricted research domain defined by this model, which allowed us to push the computer calculations much further than before. Seeing that our model provided solution strings for much larger values of n, we studied its degrees of freedom using formal computation systems such as Maple and MuPAD. From a heuristic standpoint, this phase was long, like a difficult test where one must constantly question one’s assumptions in order to eventually find the solution. In this specific problem, the contribution of non-uniform reasoning was fundamental (see our article: *La suite de Douglas Hofstadter : un paradigme de raisonnement non uniforme*). As for the final phase of our research on symmetric groups—namely, proving the optimality of our model—it is essentially based on an algorithmic approach (see our article: *Sur les styles abstrait et algorithmique en mathématiques*).

By contrast, for the alternating groups, lacking an optimal formula, we developed a new heuristic approach using a genetic algorithm (the one from MIT). Given the current state of our theoretical knowledge about the intrinsic nature of this process, and since a demonstrative proof approach was ruled out, it seemed interesting to exploit this type of algorithm as an extreme case of non-uniform reasoning—but this time developed by the computer. Moreover, our problem was a typical case for the applicability of a genetic algorithm. Indeed, for lengths strictly less than l there is no solution, and starting from l there are many solutions, so it is a priori easy for the computer to find a minimal solution among them. Thus, while not being demonstrative, the genetic algorithm heuristically confirmed our entire set of conjectures regarding the alternating groups.

Post to X