# What classes of groups can arise as "symmetry groups of terms"?

Let $$\mathfrak{A}$$ be an algebra (in the sense of universal algebra). To each term $$t(x_1,...,x_n)$$ in the language of $$\mathfrak{A}$$ in which each variable actually appears we can assign a group $$G_\mathfrak{A}(t)\subseteq S_n$$ consisting of all permutations of the variables which results in the same function: $$G_\mathfrak{A}(t)=\{\sigma\in S_n: \forall a_1,...,a_n\in\mathfrak{A}(t(a_1,...,a_n)=t(a_{\sigma(1)},...,a_{\sigma(n)})\}.$$

Now let $$\mathbb{G}(\mathfrak{A})$$ be the class of isomorphism types of groups of the form $$G_\mathfrak{A}(t)$$ for some term $$t$$. I'm curious which classes of groups can arise this way.

Originally I asked for a complete answer to this question, but in retrospect that was overly ambitious. To keep things reasonably answerable, let me restrict to the following natural candidates (playing fast and loose with isomorphism-type-vs.-group issues for simplicity) - I would love an answer, or even partial progress, to either question (or anything similar really, I'm profoundly stuck-in-the-weeds here):

Q1: Is there an $$\mathfrak{A}$$ such that $$\mathbb{G}(\mathfrak{A})$$ consists exactly of the finite $$p$$-groups for some prime $$p$$?

Certainly it's possible to get only $$2$$-groups - see e.g. this MSE answer of Eric Wofsey. However, getting exactly the $$2$$-groups, or $$p$$-groups for any fixed $$p$$, seems much harder.

Q2: Is there a $$\mathfrak{B}$$ such that $$\mathbb{G}(\mathfrak{B})$$ consists exactly of the finite abelian groups?

I really have no relevant information for this question, but it seems like a natural one to ask.

Note that Keith Kearnes' answer below addresses a variant of this question, in which variable appearance is replaced by variable dependence, and does not seem to immediately generalize to address this version.

Here are some example $$\mathbb{G}(\mathfrak{A})$$s (ignoring up-to-isomorphism details):

• If $$\mathfrak{A}=(A;\star)$$ where $$\star:A^2\rightarrow A$$ is a bijection, then $$\mathbb{G}(\mathfrak{A})$$ consists only of the trivial group.

• If $$\mathfrak{A}=(\mathbb{N};\max)$$, then $$\mathbb{G}(\mathfrak{A})=\{S_n:n\in\mathbb{N}\}$$.

• Although in the natural numbers with exponentiation alone there is essentially only one nontrivial equation, it turns out that every finite group shows up - see here.

• One of the few negative results I know is that the class of finite cyclic groups is not of the form $$\mathbb{G}(\mathfrak{A})$$ for any $$\mathfrak{A}$$. To see this, suppose $$t(x_1,...,x_k)$$ is a $$\mathfrak{A}$$-term with $$G_\mathfrak{A}(t)\cong C_2$$. Then the term $$s(x_{1,1},...,x_{k,k}):=t(t(x_{1,1},...,x_{1,k}), ..., t(x_{k,1},...,x_{k,k}))$$ has $$G_\mathfrak{A}(s)$$ having too many elements of order $$2$$ to be cyclic. In fact, tweaking this argument we get that $$\mathbb{G}(\mathfrak{A})$$ consists entirely of cyclic groups iff $$\mathbb{G}(\mathfrak{A})$$ consists only of trivial groups. However, this sort of idea doesn't seem to be useful for either Q1 or Q2 above.

• Why asking about isomorphism type as groups, rather than isomorphism type as permutation groups (which sounds more meaningful — I guess this is what's meant by "isomorphism types of subgroups of symmetric group" in Keith Kearnes' answer?
– YCor
Dec 27, 2021 at 0:54
• @YCor I would also be interested in that version of the question, but right now at least I'm primarily thinking about the groups on their own. (And besides, a coarser invariant is also easier to fully analyze.) Dec 27, 2021 at 2:24
• What's the significance of restricting to varieties, rather than (say) arbitrary first-order theories? Is it meant to make the problem more tractable? Jan 30, 2022 at 5:30
• @TimCampion I don't talk about varieties anywhere; everything is about individual algebras, not collections of algebras. As to why I'm looking at algebras as opposed to arbitrary first-order structures, they just seem particularly interesting. Jan 30, 2022 at 5:32
• Ah, I see. So you could equally have said "structure in a functional language" everywhere rather than "algebra". Jan 30, 2022 at 5:34

Let me edit this response in order to clarify what I am showing.

First, I will begin with an example: $$t(x_1,x_2,x_3,x_4,x_5,x_6) = ((((x_1x_2)x_3^{-1})x_3)x_4)x_4^{-1}$$ is a group term. If you want to associate this term to a particular group, let it be the free group $$F_6$$ on $$\{x_1,\ldots,x_6\}$$. The term $$t$$ depends on $$x_1$$ and $$x_2$$. The variables $$x_3$$ and $$x_4$$ occur, but $$t$$ does not depend on them. The variables $$x_5$$ and $$x_6$$ do not occur. The permutations of indices that are symmetries of the original term $$t$$ are those from the full symmetric group $$\textrm{Sym}(\{3,4,5,6\})$$. One may eliminate fictitious variables by defining a term $$s(x_1,x_2,x_3,x_4) = t(x_1,x_2,x_3,x_4,x_4,x_4)$$. The terms $$s$$ and $$t$$ are the same, all variables of $$s$$ occur in $$s$$, and $$s$$ does not depend on its last two variables. The symmetries of $$s$$ are $$\textrm{Sym}(\{3,4\})$$. The term $$r(x_1,x_2) = t(x_1,x_2,x_2,x_2,x_2,x_2)$$ depends on all of its variables, which are the same variables that $$t$$ depends on, and $$r$$ acts the same way as $$t$$ with respect to those variables. The symmetry group of $$r$$ is trivial.

More generally, suppose that $$t(x_1,\ldots,x_i,\ldots,x_j,\ldots,x_n)$$ depends on $$x_1$$--$$x_i$$, does not depend on $$x_{i+1}$$--$$x_j$$ although these variables occur, and the variables $$x_{j+1}$$--$$x_n$$ do not occur. The term $$r(x_1,\ldots,x_i):=t(x_1,\ldots,x_i,x_i,\ldots,x_i)$$ will be a term that depends on all variables and will have symmetry group equal to some $$G\leq S_i$$. The term $$s(x_1,\ldots,x_j):=t(x_1,\ldots,x_i,\ldots,x_j,x_j,\ldots,x_j)$$ will be a term equal to $$t$$, where all variables occur, and will have the symmetry group $$G\times S_{j-i}$$. The original term $$t(x_1,\ldots,x_i,\ldots,x_j,\ldots,x_n)$$ will have the symmetry group $$G\times S_{n-i}$$.
The symmetry groups of terms are determined, up to symmetric group factors, by the symmetry groups of just those terms that depend on all variables. Moreover, the symmetric group factors can be determined if you know which variables of the term occur and which variables the term depends on.

There are various questions that could be asked, such as

• What are the possible symmetry groups of terms? (Answer below: any concrete subgroup of $$S_n$$ is the symmetry group of an $$n$$-ary term that depends on all variables.)
• What are the possible classes of permutation groups on finite sets which are the symmetry groups of those terms of an algebra (i) which depend on all variables? (ii) in which all variables occur? (iii) are arbitrary? The question asked is (ii), but I will answer (i) here.

I am going to explain why, if $$\mathcal K$$ is any class of groups whose members are subgroups of finite symmetric groups and $$\mathcal K$$ contains $$S_1$$, then there is an algebra $$A$$ such that the symmetry groups $$G(t)$$ of terms $$t$$ of $$A$$ that depend on all variables are exactly the groups in $$\mathcal K$$. (More precisely, if $$G\in {\mathcal K}$$ is a subgroup of $$S_n$$, then we will realize $$G$$ and all of its conjugates in $$S_n$$ as symmetry groups of terms of $$A$$ which depend on all variables.) We need to include $$S_1$$ in $$\mathcal K$$ because $$t(x)=x$$ has symmetry group $$S_1$$.

For a given $$G\in\mathcal K$$, where $$G\leq S_n$$, define an $$n$$-ary operation $$f_G(x_1,\ldots,x_n)$$ on the set $$\{a, b\}\cup \mathbb N^+ = \{a, b, 1, 2, 3, \ldots\}$$ as follows: $$f_G(\bar{u}) = \begin{cases} a & \textrm{if \bar{u} = (\sigma(1),\ldots,\sigma(n)) for some \sigma\in G;}\\ b & \textrm{otherwise.} \end{cases}$$ Let $$A$$ be the algebra on $$\{a,b\}\cup \mathbb N^+$$ whose operations are all operations of the form $$f_G$$, $$G\in\mathcal K$$.

I claim that the following are true.

• Each $$f_G$$ depends on all of its variables.
• The symmetry group of $$f_G(x_1,\ldots,x_n)$$ is $$G\;(\leq S_n)$$.
• any term operation of $$A$$ that depends on all of its variables is obtained from one of the $$f_G$$'s by permuting the variables. Hence, its symmetry group is conjugate to $$G$$ in $$S_n$$.

If $$f_G(x_1,\ldots,x_n)$$ is defined as above, and we identify two variables: $$f_G(\underline{x_2},\underline{x_2},x_3,x_4,\ldots,x_n)$$, then this operation is constant and its variable-set is $$\{x_2,\ldots,x_n\}$$. Its symmetry group in Noah's sense is $$S_{n-1}$$. Similarly, the composite $$f_G(f_G(x_1,\ldots,x_n),y_2,\ldots,y_n)$$ is constant and its variable-set is $$\{x_1,\ldots,x_n,y_2,\ldots,y_n\}$$, so its symmetry group is $$S_{2n-1}$$. Using tricks like this one can obtain every finite symmetric group as a symmetry group of a term of $$A$$, as long as $$A$$ has at least one operation $$f_G$$ of arity greater than $$1$$. The isomorphism types of Noah-symmetry groups turn out to be exactly those in $$\mathcal K\cup \{S_n\;|\;n=1, 2, \ldots\}$$.

• This is interesting but I don't think it answers my question. Shifting to terms which depend on all variables changes the situation quite a bit: for the $\mathbb{G}(\mathfrak{A})$s as defined in my question, having a single nontrivial group automatically forces us to have groups of arbitrarily large finite order. And dropping the variable-appearance restriction **does** change the question: if we don't require every variable to actually appear in each term, then $\mathbb{G}(\mathfrak{A})$ must be closed under taking direct products with $S_n$s via dummy variables. Dec 26, 2021 at 23:28
• I've added a more focused subquestion to hopefully clarify the sort of thing I'm looking for. Dec 27, 2021 at 4:15
• Just to clarify: this answer’s argument “the variable-appearance condition doesn’t restrict” shows that “for any algebra $A$, there’s an expanded algebra $A'$ such that the symmetry-groups of Noah-restricted terms of $A'$ are the symmetry groups of arbitrary terms of $A$” . But it doesn’t imply the converse, as Noah’s first comment here shows. Dec 30, 2021 at 6:53
• Note that if you allow your structure to have two sorts, you can modify the example to have $\{a,b\}$ be the carrier for one sort and $\{1,2,\dots\}$ be the carrier for a second sort. Then I think you get that $G(\mathfrak A)$ in Noah's sense is precisely $\mathcal K$ (where all of the $f_G$'s go from the second sort to the first) Jan 30, 2022 at 6:16