Composing Functions to Reduce Image Size

If \(f\) and \(g\) are self-maps on a finite set \(M\) with \(n = |M|\), then the images of various composite functions such as \(f^2gf\) and \(g^2 f^2 g\) may have different sizes. There is, of course, a minimal image size which can be achieved by the composition of particular functions. It can be difficult, however, to discover the size of this minimal image. We seek to determine “words” over a finite alphabet \(S \) which, by specifying function compositions when letters are interpreted as functions, allow one to test for each \(k\) whether or not there exists among all compositions an image of size \(n – k\) or less. For two functions \(f\) and \(g\), \(W_1 = fg\) is clearly such a “word” for \(k = 1\), since no composition of functions \(f\) and \(g\) has an image smaller than or equal to \(|M| – 1\), if \(W_1 = fg\) fails to do so. We prove the existence of such a word \(W_k\) for each \(k\), and exhibit a recursive procedure for the generation of \(W_{k+1}\) from \(W_k\). The words \(W_k\) depend only upon the finite alphabet \( S \), and are independent of the size of the finite set \(M\) over which the symbols from \( S \) are to be interpreted as functions.