3
$\begingroup$

Suppose that $f_{1},...,f_{k}:\{0,1\}^{r}\rightarrow\{0,1\}^{r}$ are bijective functions.

For all $n\geq r$, let $G_{f_{1},...,f_{k};r}=\subseteq S(\{0,1\}^{n})$ be the subgroup generated by

i. the functions $f_{i}\times Id_{n-r}$ where $Id_{n-r}:\{0,1\}^{n-r}\rightarrow\{0,1\}^{n-r}$ is the indetity function, and

ii. the mappings $\pi_{\sigma}$ for permutations $\sigma\in S_{n}$ where $\pi_{\sigma}(x_{1},...,x_{n})=(x_{\sigma(1)},...,x_{\sigma(n)})$.

Let $t_{f_{1},...,f_{k};n}$ be the largest natural number $m$ such that the symmetry group $S_{m}$ embeds in the group $G_{f_{1},...,f_{k};r}$. We say that $(f_{1},...,f_{k})$ is of exponential growth if there is some $\alpha>1$ and $c>0$ where $t_{f_{1},...,f_{k};n}>c\cdot\alpha^{n}$ for all $n\geq r$. We say that $(f_{1},...,f_{k})$ is of polynomial growth if there is some polynomial $p$ where $t_{f_{1},...,f_{k};n}<p(n)$ for all $n\geq r$. We say that $(f_{1},...,f_{k})$ is of intermediate growth if it is not of polynomial nor exponential growth. Does there exist a collection of bijective functions $(f_{1},...,f_{k})$ of intermediate growth?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.