<p>The number of isomorphism classes of groups of order <span class="math-container">$\leq n$</span> is asymptotically <span class="math-container">$n^{\Theta(\log^2 n)}$</span>, so to even specify all such groups requires strings of length <span class="math-container">$\Omega(\log^3 n)$</span>, so this is also a lower bound on your action complexity.</p>

CC BY-SA 4.0
2018-09-29T23:30:45.013Z
Technically maybe I have to divide by $\log \log n$, since specifying a circuit with $t$ gates could use $\Theta(t \log t)$ bits...
Joshua Grochow
CC BY-SA 4.0
2018-09-29T22:01:58.063Z
2018-09-29T22:01:58.063Z
Joshua Grochow
<p>Suppose that <span class="math-container">$G$</span> is a group with <span class="math-container">$|G|=n$</span>. Suppose that <span class="math-container">$G$</span> is generated by elements <span class="math-container">$g_{1},\dots,g_{k}$</span>. Let <span class="math-container">$\iota:G\rightarrow S_{2^{N}}$</span> be an injective group homomorphism such that <span class="math-container">$\iota(g_{i}):\{0,1\}^{N}\rightarrow\{0,1\}^{N}$</span> is computed by a reversible circuit consisting of <span class="math-container">$t_{i}$</span> reversible gates and where <span class="math-container">$t=t_{1}+\dots+t_{k}$</span> (for definiteness, assume that we can use any reversible gate on three bits). Then we shall say that <span class="math-container">$G$</span> has action complexity at most <span class="math-container">$t$</span>.</p>

<p>Let <span class="math-container">$\delta_{n}$</span> be the maximum action complexity of a group <span class="math-container">$G$</span> with <span class="math-container">$|G|\leq n$</span>. What are some bounds on <span class="math-container">$\delta_{n}$</span>?</p>

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

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

<p>There is a large gap between the lower bounds and the upper bounds which I gave, so I am looking for better bounds for <span class="math-container">$\delta_{n}$</span>.</p>

<p>Since this is CSTheory and not MathOverflow, I am interested in upper bounds which are not be obtained simply by finding smaller <span class="math-container">$r$</span> such that <span class="math-container">$G$</span> embeds in <span class="math-container">$S_{2^{r}}$</span> or by finding a smaller generating set for <span class="math-container">$G$</span>.</p>

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

<circuit-complexity><gr.group-theory>
Circuit complexity of group actions
Joseph Van Name
# Circuit complexity of group actions

(Asked by: username_0 on 2018-09-29)

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.

**Tags:** circuit-complexity, gr.group-theory

---

## 1 answers

### Answer by username_1 on 2018-09-29. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_1**: Technically maybe I have to divide by $\log \log n$, since specifying a circuit with $t$ gates could use $\Theta(t \log t)$ bits...  

---

