Thread: Minimum number of generator assemblies

1. Minimum number of generator assemblies

Hi everyone. I'm new, and I'm not a native speaker of english, so I hope I won't get any of the advanced algebra names wrong. This is my question:

There is a finite semigroup of functions from the set $\{1,...,n\}$ to $\{1,...,n\}$ with the operation of function composition, with a set of generators $\{f,g\}$. We know that there exists a sequence of assemblies of these generators so that it produces a constant function. What is an upper bound on the length of the minimum number of assemblies for a specified $n$?

2. Originally Posted by elytkiat
Hi everyone. I'm new, and I'm not a native speaker of english, so I hope I won't get any of the advanced algebra names wrong. This is my question:

There is a finite semigroup of functions from the set $\{1,...,n\}$ to $\{1,...,n\}$ with the operation of function composition, with a set of generators $\{f,g\}$. We know that there exists a sequence of assemblies of these generators so that it produces a constant function. What is an upper bound on the length of the minimum number of assemblies for a specified $n$?
i'm not sure i understand the question: so you have two functions $f,g : \{1, \cdots , n \} \longrightarrow \{1, \cdots , n \}.$ we know that there exists an $m \geq 1$ such that $f_1f_2 \cdots f_m = \text{id},$ where $f_j \in \{f,g \}.$

now you're looking for an upper bound on what exactly?

3. Yes, you got it right, and now the question is: what is the upper bound on the minimum number of $m$ (for a given $n$)?

In other words: what is the minimum $m$ in "the worst case scenario"?