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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.