# Circuit complexity of group actions

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.

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.
• Technically maybe I have to divide by $\log \log n$, since specifying a circuit with $t$ gates could use $\Theta(t \log t)$ bits... Commented Sep 29, 2018 at 23:30