Suppose that $G$ is a group with $|G|=n$. Suppose that $G$ is generated by elements $g_{1},\dots,g_{k}$. Let $\iota:G\rightarrow S_{2^{N}}$ be an injective group homomorphism such that $\iota(g_{i}):\{0,1\}^{N}\rightarrow\{0,1\}^{N}$ is computed by a reversible circuit consisting of $t_{i}$ reversible gates and where $t=t_{1}+\dots+t_{k}$ (for definiteness, assume that we can use any reversible gate on three bits). Then we shall say that $G$ has action complexity at most $t$.

Let $\delta_{n}$ be the maximum action complexity of a group $G$ with $|G|\leq n$. What are some bounds on $\delta_{n}$?

To obtain a trivial lower bound, we observe that if $|G|=n$, then $|G|\leq|S_{2^{N}}|=(2^{N})!$ and without loss of generality, $t\geq N/3$, so $t\geq\sqrt[1+\epsilon]{\log_{2}(\log_{2}(n))}$.

For a trivial upper bound, we can set $k\leq\log_{2}(n)$ and by Cayley's theorem, $G$ embeds into $S_{2^{N}}$ where $N=\lceil\log_{2}(n)\rceil$. Let $\iota:G\rightarrow S_{2^{N}}$ be an embedding. Now, the functions $\iota(g_{1}),...,\iota(g_{k})$ along with their inverses can each by computed by circuits of size $O(2^{N})=O(n)$ which gives an upper bound of $\delta_{n}\leq O(n\cdot\log_{2}(n))$.

There is a large gap between the lower bounds and the upper bounds which I gave, so I am looking for better bounds for $\delta_{n}$.

Since this is CSTheory and not MathOverflow, I am interested in upper bounds which are not be obtained simply by finding smaller $r$ such that $G$ embeds in $S_{2^{r}}$ or by finding a smaller generating set for $G$.

Note: I could have formulated this question in terms of conventional Boolean circuits since if $f$ is a bijective function and both $f,f^{-1}$ can be computed by conventional circuits on $n$ gates, then $f$ can be computed by a reversible circuit on $O(n)$ gates.


1 Answer 1


The number of isomorphism classes of groups of order $\leq n$ is asymptotically $n^{\Theta(\log^2 n)}$, so to even specify all such groups requires strings of length $\Omega(\log^3 n)$, so this is also a lower bound on your action complexity.

  • $\begingroup$ Technically maybe I have to divide by $\log \log n$, since specifying a circuit with $t$ gates could use $\Theta(t \log t)$ bits... $\endgroup$ Commented Sep 29, 2018 at 23:30

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.