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

Improve this question
$\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
    Commented 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
    Commented 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$
    – Steven Stadnicki
    Commented Jan 1, 2017 at 16:30
  • $\begingroup$ @StevenStadnicki: No, you're not mistaken. I fixed the title. $\endgroup$
    – T. Amdeberhan
    Commented Jan 1, 2017 at 16:52
  • $\begingroup$ @YCor: For example, $\# End(T_2)=7, \# End(T_3)=40$. $\endgroup$
    – T. Amdeberhan
    Commented Jan 1, 2017 at 16:53

1 Answer 1

Reset to default
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}}$.

Improve this answer
$\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-Christoph Schlage-Puchta
    Commented Jan 5, 2017 at 15:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .