6
$\begingroup$

$\DeclareMathOperator\End{End}$Let $T_n$ be the full transformation semigroup/monoid of $[n]=\{1,\dots,n\}$. Let $\End(T_n)$ be the set of [endomorphisms][1] of $T_n$. Then, $\# T_n=n^n$ and $$\# \End(T_n)=n!\left[1+\sum_{m=1}^n\sum_{k=0}^{\lfloor\frac{m-1}2\rfloor}\sum_{r=1}^{m-2k}\frac{m^{n-m}r^{m-k-r}}{2^k(n-m)!(m-2k-r)!k!r!}\right].$$

Question. (a) Is this limit true? $$\lim_{n\rightarrow\infty}\frac{\# \End(T_n)}{\# T_n}=0.$$ Clearly, the automorphism group of $T_n$ is isomorphic to $\mathfrak{G}_n$, the symmetric group on $[n]$.

(b) If part (a) holds, then it is reasonable to ask how does $\End(T_n)$ embed (in some sense, say injects) in $T_n$? [1]: https://en.wikipedia.org/wiki/Endomorphism

$\endgroup$
14
  • $\begingroup$ "Let $T_n$ be the monoid/semigroup of self-maps of $[n]$". Just to make clear you mean endomorphisms of $T_n$ as a semigroup (still there is an ambiguity on whether you require endomorphisms to map identity to itself). $\endgroup$
    – YCor
    Jan 1, 2017 at 16:14
  • $\begingroup$ Do you require $1\mapsto 1$? when not required, it's not true for endomorphisms of arbitrary monoids. $\endgroup$
    – YCor
    Jan 1, 2017 at 16:29
  • 1
    $\begingroup$ I'm still a little confused here - do you mean the endomorphisms of $T_n$, or the endomorphisms within $T_n$? Your question makes it seem like the latter (you ask about the 'ratio' of endomorphisms to all transformations) but you haven't imposed any structure on $[n]$ that you're morphing. Otherwise, perhaps it's the hour but I'm just not seeing how you have $End(T_n)\subseteq T_n$ in the first place. $\endgroup$ Jan 1, 2017 at 16:30
  • $\begingroup$ @StevenStadnicki: No, you're not mistaken. I fixed the title. $\endgroup$ Jan 1, 2017 at 16:52
  • $\begingroup$ @YCor: For example, $\# End(T_2)=7, \# End(T_3)=40$. $\endgroup$ Jan 1, 2017 at 16:53

1 Answer 1

2
$\begingroup$

Looking at the exponential series, we have $\frac{r^k}{k!}\leq e^r$. Hence we have $$ \frac{r^{m-k-r}}{(m-2k-r)!r!k!} = \frac{1}{r!}\frac{r^k}{k!}\frac{r^{m-2k-r}}{(m-2k-r)!} \leq\frac{e^{2r}}{r!}=\mathcal{O}(1). $$ From this we obtain $$ \#End(T_n)\leq Cn! n^3\max_m\frac{m^{n-m}}{(n-m)!} \leq Cn! n^3\max_m\frac{m^{n-m}}{(n-m)!}. $$ Put $m=\alpha n$. Then $$ \frac{m^{n-m}}{(n-m)!}\leq \left(\frac{e\alpha}{1-\alpha}\right)^{(1-\alpha)n}. $$ The maximum of $\left(\frac{e\alpha}{1-\alpha}\right)^{(1-\alpha)}$ is about $1.763$, thus for large $n$ we have $\#End(T_n)\leq 1.77^n n!$, which is a lot smaller than $n^n\sim \frac{e^n n!}{\sqrt{2\pi n}}$.

$\endgroup$
1
  • $\begingroup$ I noticed that when computing the maximum in the second to last line I left out the factor $e$, which lead to the value 1.33, which is too small. The new value should be correct ,and is still small enough. Note that the upper bound $e^{(1-c)n}$ for some $c>0$ follows from the bound $r^k/k!\leq e^r$ again. $\endgroup$ Jan 5, 2017 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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