I ask the question about semigroup in here
The semigroup of all order-preserving and decreasing transformations in full transformations semigroup $T_n$ is denoted $C_n$.
I consider the idempotent set $A=\{\begin{bmatrix}2\\1 \end{bmatrix},\begin{bmatrix}3\\2 \end{bmatrix},\cdots, \begin{bmatrix}n\\n-1 \end{bmatrix}\}$. It is well known that $\langle A \rangle = C_n$.
I want to determine smallest $k$ suct that $C_n=\bigcup\limits_{i=1}^{k} A^k$.
Answer is the following:
$\DeclareMathOperator\im{im}$For ease of notation, let me denote $a_i=\genfrac[]{0pt}{}{i+1}i$, so that $A=\{a_1,\dots,a_{n-1}\}$. I will write multiplication so that $(fg)(x)=f(g(x))$; reverse everything if you want the opposite convention.
Proposition: For any $f\in C_n$, the least $k$ such that $f$ can be written in the form $$f=a_{i_1}a_{i_2}\cdots a_{i_k}\tag1$$ for some $i_1,\dots,i_k\in[n-1]$ is $$k=\sum_{y\in\im(f)}\bigl(\max(f^{-1}(y))-y\bigr).\tag2$$ Moreover, for each $i\in[n-1]$, the minimal number of occurrences of $a_i$ in (1) is $$\bigl|\{y\in[n]:\exists x\in[n]\,(f(x)=y\le i<x)\}\bigr|.\tag3$$
Proof:
To prove the upper bound, let me fix $f\in C_n$ with image $$\im(f)=\{y_1,\dots,y_l\},\qquad1=y_1<y_2<\dots<y_l\le n.$$ Putting $x_j=\max(f^{-1}(y_j))$, we have $$1\le x_1<x_2<\dots<x_l=n,$$ and if we also define $x_0=0$, then for each $i\in[l]$: $$f^{-1}(y_i)=[x_{i-1}+1,x_i].$$ In particular, $y_i\le x_{i-1}+1$. Now it remains to observe that $$f=(a_{y_l}a_{y_l+1}\cdots a_{x_l-1})\cdots(a_{y_2}a_{y_2+1}\cdots a_{x_2-1})(a_{y_1}a_{y_1+1}\cdots a_{x_1-1}).$$
For the lower bound, assume $f$ is written as in (1), and let $i\in[n-1]$ and $x\in[n]$ be such that $f(x)\le i<x$. Then $$x,a_{i_k}(x),(a_{i_{k-1}}a_{i_k})(x),\dots,(a_{i_1}a_{i_2}\cdots a_{i_k})(x)=f(x)$$ is a nonincreasing sequence which may decrease by at most $1$ at each step, hence there is a unique step where it goes from $i+1$ to $i$: that is, there is $j(x)\in[k]$ such that $$(a_{i_{j(x)+1}}\cdots a_{i_k})(x)=i+1,\qquad (a_{i_{j(x)}}a_{i_{j(x)+1}}\cdots a_{i_k})(x)=i.$$ Clearly, we must have $i_{j(x)}=i$. Moreover, if $x'$ is such that $f(x')\le i<x'$, then $$f(x)\ne f(x')\implies j(x)\ne j(x').\tag4$$ Indeed, if we had $j(x)=j(x')=j$, then $$(a_{i_j}\cdots a_{i_k})(x)=(a_{i_j}\cdots a_{i_k})(x')=i,$$ hence $$f(x)=(a_{i_1}\cdots a_{i_k})(x)=(a_{i_1}\cdots a_{i_{j-1}})(i)=(a_{i_1}\cdots a_{i_k})(x')=f(x').$$ Now, (4) implies that the number of occurrences of $a_i$ in (1) is at least (3). Summing over all $i$, we have $$\begin{align*} k&\ge\sum_i\bigl|\{y\le i:\exists x\in f^{-1}(y)\,(i<x)\}\bigr|\\ &=\bigl|\{(i,y):y\le i\land\exists x\in f^{-1}(y)\,(i<x)\}\bigr|\\ &=\sum_y\bigl|\{i:y\le i\land\exists x\in f^{-1}(y)\,(i<x)\}\bigr|\\ &=\sum_{y\in\im(f)}\bigl(\max(f^{-1}(y))-y\bigr), \end{align*}$$ proving (2). QED
If $f\in C_n$ of image size $l$ is written as in the proof of the upper bound, (2) gives $$k=\sum_{j=1}^l(x_j-y_j).$$ This expression is maximized (for a given $l$) when the $x_j$ are maximized, i.e., $x_j=n+j-l$, and $y_j$ are minimized, i.e., $y_j=j$. Thus, $$k\le\sum_{j=1}^l(n+j-l-j)=l(n-l)\le\lfloor n/2\rfloor\lceil n/2\rceil=\lfloor n^2/4\rfloor.$$ This bound is attained for the function $f(x)=\max(1,x-\lfloor n/2\rfloor)$. Thus:
- Why it is enough to observe that $$f=(a_{y_l}a_{y_l+1}\cdots a_{x_l-1})\cdots(a_{y_2}a_{y_2+1}\cdots a_{x_2-1})(a_{y_1}a_{y_1+1}\cdots a_{x_1-1})$$ for uppper bound(what does upper bound for this question mean? it is $k\leq$ something?)?
- I couldn't understand anything for lower bound? -In the last step why $x_j=n+j-l$ and $$k\le\sum_{j=1}^l(n+j-l-j)=l(n-l)\le\lfloor n/2\rfloor\lceil n/2\rceil=\lfloor n^2/4\rfloor.$$
- what does this bound is attained for the function $f(x)=\max(1,x-\lfloor n/2\rfloor)$ mean? why do we use the transformation $f(x)=\max(1,x-\lfloor n/2\rfloor)$
- Can you advice any article or book to more understand concept?