My question is a reference request about symmetries on sets of strings. I'm not a mathematician, so the terminology I use below is probably very non-standard. My apologies.

Terminology. Let $[n] = \{0, 1, ..., n-1\}$. A permutation of a string $\sigma = (s_0, ..., s_{n-1})$ over an alphabet $\Sigma$ is a permutation of $[n]$. We write $p\; \sigma$ for the string obtained from $\sigma$ using $p$, i.e. $p\; \sigma = (s_{p\; 0}, ..., s_{p\; (n-1)})$ Let's call such a permutation $p$ with $p\ \sigma = \sigma$ a symmetry. We call a permutation that only exchanges $i$ and $j$, leaving everything else fixed, a flip and write flips as $(i, j)$. For example

$$ (2,4)\; hello = heoll $$

Clearly, we can reconstruct any permutation on strings as the composition of some flips. Let's call a flip a flip-symmetry if it is a symmetry and non-trivial, ie. not $(i, i)$. We call a set $B$ of flip-symmetries of a fixed string $s$ a basis if any (flip-)symmetry of $s$ can be build up from $B$. We can use the basis $B$ to specify a group (maybe we should call it the automorphism group of $\sigma$?) $G$ by it's presentation. Clearly, strings, their bases and the induced group are in one-to-one correspondence, up to injective renaming of the alphabet $\Sigma$.

Problem. What I want to do is lift this treatment from strings to sets of equal-length strings. Let me give an example. Consider the set $S$, consisting of the following strings:

  • $ababbc$ with basis $(0,2), (1, 3), (3, 4)$.

  • $abcbba$ with basis $(0,5), (1, 3), (3, 4)$.

  • $cbabba$ with basis $(2,5), (1, 3), (3, 4)$.

The obvious definition of symmetry for such a set is to say a permutation $p : [6] \rightarrow [6]$ is a permutation of $S$ provided $s \in S$ implies $p\; s \in S$. We can extend the concept of flip, basis etc to sets of strings. If we make this choice, the only non-trivial flips of $S$ are

$$ (0, 2) \quad (0, 5) \quad (2, 5) $$

But now we have lost a lot of information: we can no longer recover $S$ from such flips. That's because these flips ignore that the symmetries of the members of $S$ are systematically related: From the basis $(0,2), (1, 3), (3, 4)$ of $ababbc$ and the flip $ (0, 5)$ of $S$, I can obtain the basis $(0,5), (1, 3), (3, 4)$ of $abcbba$ and so forth. This can be written as a commutative diagram, for example like so:

$$ \begin{array}{rcl} ababbc & \stackrel{25}{\longrightarrow} & abcbba \\ \downarrow _{05} & & \downarrow _{02} \\ cbabba & \stackrel{25}{\longrightarrow} & cbabba \\ \end{array} $$

Sorry for the poor type-setting.

It seems to be the case that the non-trivial flips $(0, 2), (0, 5), (2, 5)$ of $S$ somehow permute the bases of the underlying strings: we have permutations of $S$ working on permutations of the members of $S$. Let's call this phenomenon higher-order permutations on strings. They crop up in my work all the time.

Question. I wonder what the right framework is to think about higher-order permutations on strings. I'm sure they have been thoroughly investigated already. What terms should I google for? Googling "strings" or "symmetries" always leads to physics. I'm particularly interested in the kinds of groups and geometric objects such higher-order symmetries induce.


1 Answer 1


This idea has indeed been studied extensively. You are basically talking about what is usually called the group action of a group $G$ on a set $S$, and that's probably the missing google term you want.

What you are calling a "flip" is usually called a transposition; and you have $G$ as the group generated by (in your terms, 'can be built up from') all transpositions $(i,j)$ for $i,j \in [n]$ (the "trivial" transpositions of the form $(i,i)$ are identical and are typically denoted as the identity element $e$).

What you are calling a "basis of $s$" for $s \in S$ is any set of transpositions which generate what is called the stabilizer of $s$ in $G$ defined as $G_s = \{g \in G : g(s) = s\}$. Note that more than one of your 'basis' sets can generate the same of $G_s$; e.g. $(0,2)(1,3)(3,4)$ is the same as $(0,2)(1,3)(1,4)$; so usually we are more interested in the properties of $G_s$ than which set of transpositions generated it.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .