# Equivalence classes induced on binary strings by set of permutations

Let $\mathbb{F}_2^{n}$ be the set of binary strings of length $n$ and let $f: \mathbb{F}_2^{n} \rightarrow \mathbb{R}$ be a function from the set of binary strings of length $n$ to the reals.

Let's say we are given a set of permutations $\pi = \{\pi_1,...,\pi_k\}$ under which the value $f(s)$ is invariant. This set of permutations can be any subset of the set of all permutations.

For example, consider the set of binary strings of length $4$ and let $\{(s_1 s_2)\}$ be a set of permutations (in cycle notation) under which $f$ is invariant. Then, we have that $f(0101)=f(1001), f(0110)=f(1010), f(0100)=f(1000)$, and $f(0111)=f(1011)$.

Question: Is there an elegant way of finding a canonical representation of the equivalence classes induced on $\mathbb{F}_2^{n}$ by $f$ (and, therefore, by $\pi$)? I envision a representation that lists one member of each class and the number of strings in each class.

The naive algorithmic approach would apply the permutations exhaustively to all strings to find these classes. Note that, in the worst case, this would require the explicit enumeration of all $2^n$ strings, which is exactly what I want to avoid. I have a feeling that this should be possible in a more elegant way. For instance, if we know that $\pi$ is the set of all permutations then the strings can be classified by looking at the number of $1$s: two strings with the same number of $1$s would be invariant under $f$. Thus, one possible canonical representation would be to pick the smallest representative (lexicographically) of each class.

My intuition tells me that there is probably a connection to Invariant Theory. Any answers and/or pointers would be greatly appreciated.

Cheers, Mathias

-
I advise caution. In universal algebra, one is concerned with relations that preserve the function f. Thus equivalence classes respecting f are level sets of f, and are related to congruences of the algebra < U,f >. The equivalence classes are not necessarily invariant under the permutation groups you describe, which in your case preserve the number of 1-bits an argument to f has. So in looking through the literature, you need to keep your special property in mind; I don't know where to find that property. Gerhard "Ask Me About System Design" Paseman, 2011.08.16 –  Gerhard Paseman Aug 16 '11 at 18:09
Also, if you know there are indices which are fixed, then your problem boils down to looking at subgroups of permutation groups on the subset of non-fixed indices and that are generated by your list of permutations. You might look at that bit of basic group theory for guidance. Gerhard "Ask Me About System Design" Paseman, 2011.08.16 –  Gerhard Paseman Aug 16 '11 at 18:14
Your $f$ is a linear functions from $V:=(\mathbb{R}^2)^{\otimes n} \to \mathbb{R}$ and the $G$ group that the $\pi$'s generate acts on the tensor places. The irreducible decomposition of $V$ as a representation of $G$ is easy to compute (using Schur-Weyl duality and restriction from $S_n$ to $G$). It should be easy to figure $f$ into this, although I haven't done this. –  Andy B Aug 16 '11 at 21:47
Thank you both very much for your comments. Especially Andy's remarks are right to the point. As a computer scientist, who doesn't have a background in representation theory, it'll probably take me a couple of weeks to understand the implications of the comment and to come up with the algorithm that accomplishes what I'm looking for. Can you recommend some accessible literature on representation theory for finite groups and the Schur-Weyl duality? –  Mathias Aug 17 '11 at 9:56
You don't need the full power of SW duality here, since you're looking at tensor products of a two-dimensional space. Still, I would recommend a subset of Chapters 1--6 in Fulton and Harris. –  Andy B Aug 17 '11 at 15:47
show 1 more comment