Let $X_n$ be a set with $n$ elements. Write $F(X_n,X_n)$ for the set of maps from $X_n$ to itself. We give it the operation of composition. I am curious if there is a nice formula for the following question. Let $m$ be a positive integer. How many maps in $F(X_n,X_n)$ are $m$th powers of other maps? In other words, how big is the image of the function which takes each map to its $m$th power? This is just for fun. Thanks!
Roots of maps of finite sets
-
0It might be worth noting that given a set $X$, the semigroup of all maps $X\to X$ is called "the full transformation semigroup on $X$", often denoted by $\mathcal{T}_X$, and plays a role in semigroups analogous to the role played by symmetric groups in group theory; in particular, there is a "Cayley's Theorem" for semigroups, which says that every semigroup is a subsemigroup of a full-transformation semigroup. – 2011-06-28
2 Answers
As I mentioned in comments, what you denote $F(X_n,X_n)$ is known as the full transformation semigroup on $X_n$, often denoted by $\mathcal{T}_{X_n}$, or simply $\mathcal{T}_n$.
One reference I found is Digraphs and the semigroup of all functions on a finite set, by Peter M. Higgins, Glasgow J. Math. 30 (1988), pp. 41-57; available here. There he considers, inter alia, the problem of finding all solutions to $x^m = c$ in the full transformation semigroup.
Having the standard name for the object you are looking at may faciliate finding references.
Addendum. Another reference handles the case $m=2$, and provides a characterization of exactly when an element of the full transformation semigroup is a square; this is a 1982 paper of Howie and Snowden, Square roots in finite full transformation semigroups, Glasgow J. Math. 23 (1982), 137-149 (available here). As the authors note, the characterization is "disappointingly complicated", and I don't know how amenable it is to trying to count the number of squares in $\mathcal{T}_n$. It would seem that this is actually a fairly difficult problem, though of course a lot of progresss may have been made in the past 20-30 years.
Steven,
I wrote a little program for you. Here is some sample data (hopefully but not guaranteed correct) to guide you on your way:
N=1: Presumably I don't need to write this down
N=2: 4, 3, 4, 3, 4, 3, ... (this is for m=1,2,3, ... --- this easy to see by hand of course)
N=3: 27, 12, 19, 12, 21, 10, 21, 12, 19, 12, 21, 10, ...
N=4: 256, 100, 116, 73, 148, 44, 148, 73, 116, 76, 148, 41, 148, 76, 116, 73, 148, 44, 148, 73, 116, 76, ...
N=5: 3125, 1075, 985, 580, 1281, 296, 1305, 580, 925, 631, 1305, 220, 1305, 655, 901, 580, ...
N=6: 46656, 13356, 11026, 5721, 12942, 3136, 13806, 5601, 9286, 5952, 13806, 1921, 13806, 6816, ...
I can send you the code if you like, though it might not be correct and it is certainly not efficient. Based on the $N \le 4$ cases, it appears that after some point, these sequences are periodic in m of period N!, which may be easy to see algebraically (it is when N=2), but I haven't really thought about it.
-
1Thanks Kimball! I used your data to locate the sequence as A102709 at the Encyclopedia of Integer Sequences. I then e-mailed the author of the entry, who believes it is a nice but "unsolved" problem to find a formula. – 2011-05-28