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!

  • $\begingroup$ The special case of permutations which are squares was addressed in a previous question: math.stackexchange.com/questions/1118/… I think this will be hard in general. $\endgroup$ – Qiaochu Yuan May 27 '11 at 17:01
  • $\begingroup$ @quiachu - The question about squares asks to characterize the squares, whereas this question asks for a count, which might be an easier task. $\endgroup$ – Thomas Andrews May 27 '11 at 17:19
  • $\begingroup$ That other question seems to be asking about functions R->R, whereas this question is about functions on a finite set. The bijective functions can probably be nailed down by looking at cycle decomposition in the symmetric group, but the others may be trickier. $\endgroup$ – MartianInvader May 27 '11 at 17:21
  • $\begingroup$ The characterization of squares I gave in my answer works for an arbitrary set and leads to a count when restricted to finite sets. $\endgroup$ – Qiaochu Yuan May 29 '11 at 9:35
  • $\begingroup$ It 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. $\endgroup$ – Arturo Magidin Jun 28 '11 at 4:46

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.



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.

  • 1
    $\begingroup$ Thanks 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. $\endgroup$ – Steven Spallone May 28 '11 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.