Group Theory – Possible Symmetry Groups of Power Terms

finite-groupsgr.group-theorylo.logicuniversal-algebra

Previously asked and bountied at MSE:


Let $\mathfrak{E}=(\mathbb{N};\mathit{exp})$ be the algebra in the sense of universal algebra consisting of the natural numbers with just exponentiation. To each term $t(x_1,…,x_n)$ in which each variable $x_i$ ($1\le i\le n$) actually appears$^1$ we can assign the group $$E_t=\{\sigma\in S_n:\forall a_1,…,a_n\in\mathbb{N}[t(a_1,…,a_n)=t(a_{\sigma(1)},…,a_{\sigma(n)})]\}.$$ For example, allowing standard notational conveniences we have $E_{x^y}$ is trivial but $E_{(x^y)^z}\cong S_2$.

I'm curious which groups arise, up to isomorphism, as $E_t$s (in the language of this earlier question of mine, I'm asking for a description of $\mathbb{G}(\mathfrak{E})$). The above trick is the only useful thing I can think of, and in a sense is in fact all there is, but it already gives rise to some complexity: for example, at a glance the term $$[[((a^b)^c)^d]^{[((p^q)^r)^s]}]^{[((w^x)^y)^z]}$$ yields a semidirect product of $(S_3)^3$ and $S_2$, but we can then "carve out" some of that group by reusing the same variable multiple times. Intuitively I suspect that each $E_t$ can be built up from full permutation groups via semidirect products + [something else rather simple], but it seems potentially messy. There are many specific groups which seem (to me) to be plausible counterexample candidates, including the $A_n$s and $C_n$s for "large enough" values of $n$, but I haven't had any luck figuring out the situation with even such fairly simple low-complexity groups.


$^1$The answer to this specific question would not change if we allowed terms in which some variables don't appear; however, for general structures $\mathfrak{A}$ this restriction can be impactful (e.g. if we take $\mathfrak{A}$ to be an algebra consisting of a single bijection from the square of the underlying set to itself), so I've included it here for consistency.

Best Answer

Based on an observation by MSE user Pilcrow, it seems I've been overcomplicating this:

For simplicity, let "$[x_1,x_2,...,x_k]$" be shorthand for the right-associating exponent term $$x_1^{(x_2^{(...^{x_k})})}.$$ Then for each $k\in\mathbb{N}$ and each subgroup $G$ of $S_k$, we can consider the term $$t_G:=w^{\prod_{\sigma\in G}[x_{\sigma(1)},x_{\sigma(2)}...,x_{\sigma(k)}]}$$ (allowing the obvious abuse of notation for brevity), with $w,x_1,x_2,...,x_k$ distinct variables.

Since $w$ obviously can't be swapped with any of the $x_i$s there is a canonical embedding $i:E_{t_G}\rightarrow S_k$, and it's not hard (if a bit tedious) to show that in fact we have $i[E_{t_G}]=G$. So every finite group occurs as the symmetry group of some exponentiation-only term. For example, $C_4$ is represented by $w^{[x_1,x_2,x_3,x_4]\cdot[x_2,x_3,x_4,x_1]\cdot[x_3,x_4,x_1,x_2]\cdot[x_4,x_1,x_2,x_3]}$, or a bit less abbreviatedly by $$w^{[x_1^{(x_2^{(x_3^{x_4})})}]\cdot[x_2^{(x_3^{(x_4^{x_1})})}]\cdot[x_3^{(x_4^{(x_1^{x_2})})}]\cdot[x_4^{(x_1^{(x_2^{x_3})})}]}.$$