Bits and orbits

Question

I know this title makes what I am about to ask sound like an off topic CS theory question but please bear with me because I assure you that it is not! (Well mostly, actually I am about ~90% certain that this is a perhaps routine application of representation theory...) If you just want the problem without the backstory, skip to the bottom.

Anyway, I would like to get some way to uniquely encode tuples of finite sets of bits up to a some type of reordering. In other words, let's suppose I have k binary strings all of equal length n, or in other words $a_1, a_2, ... a_k \in \mathbb{F}_2^n$, and I want to find some way to encode them uniquely as a binary string of minimal length so that I can insert them into a dictionary for later use.

Now if I care about the order of each of these guys, then there is really only one way to go, which is to just concatenate each of the bit strings together into one big string of length $nk$.

However, suppose that I don't care about the ordering (for example, I consider these things to be sets not sequences), then instead I only want to encode the orbit of this sequence under the usual action of $S_k$. Now there are at least a couple of ways to do this; for example I could sort the sequence lexicographically, or by being more clever I could re-encode them using symmetric polynomials. As a simple application, I could use the usual basis and write the result equivalently as:

$b_1 = a_1 + a_2 + ... a_k$

$b_2 = (a_1 a_2) + (a_1 a_3) + ...$

....

$b_k = a_1 a_2 ... a_k$

Of course this can be computed in time on the order of $nk \log^2(k)$ by divide and conquer and FFT polynomial multiplication. Ignoring the subtleties of the time complexity of computing all these sums for the moment, this suggests the following interesting question:

Question 1: On average, what is the smallest length binary string needed to encode $k$ length $n$ binary strings up to permutation? (which can be computed in polynomial time).

It should be about $nk - k \: \log (k)$, since there are $k!$ permutations, but I am not exactly sure how to get there.

Now, as a follow up question, what is the best you can do for an arbitrary group? For example, if you only care about encoding the binary sequences up to alternation, what is the best way to do it? One possibility is to use the Vandermonde polynomials, however there is a need to be a bit careful here, since if this is done directly over $\mathbb{F}_2^n$, then one runs into the small problem that $a_k = -a_k$. So this leads to the following pair of questions:

Let $G$ be a group acting faithfully on the indices of a finite set of binary strings $a_1, a_2, ... a_k$ whose individual lengths are at most $n$:

Question 2: Is there an efficiently computable encoding of the orbit of $a_1, a_2, ... a_k$ under $G$ of length at most $nk$? (In other words, two sequences in the same orbit would map to the same string, and this encoding can be found in time polynomial in $\log(G), n$ and $k$.)

Question 3: Is there an efficiently computable encoding on the order of length $O(nk - \log(|G|))$ of the orbit?

EDIT: Adjusted the wording of the first question to be more specific. Also fixed my brain fart with dividing out by the entropy of G instead of subtracting (in my defense, it was about 3am my local time when I wrote this).

EDIT 2: I tried to be a bit more specific with the time complexity requirements to rule out silly things like "take lexicographically first element of the orbit".

Answer 1

I suspect the problem is intended to include some requirement that the coding scheme be efficiently computable, because if one doesn't care at all about efficiency then the following (rather silly) scheme would provide codes of the shortest possible length. By the "first member" of an orbit, I mean the lexicographically first string (of length $nk$) that is the concatenation of a $k$-tuple in that orbit. Imagine a list of all these first members, listed in lexicographic order; the length of this list is the number $Q$ of orbits and each of the $Q$ entries is a bit string of length $nk$. Code any orbit by (the binary representation of) the position of its first member in this list of all first members. So the code is an integer in the range from 1 to $Q$ and its length in bits is therefore essentially $\log Q$. That's the best you can hope for when you're coding $Q$ things using binary digits.

I'm quite confident the OP intended some computability (or other reasonableness) requirement that would exclude such a coding. It's not obvious, though, what the requirement should be. Should one be able to easily compute, given a $k$-tuple $a_1,\dots,a_k$, which orbit it belongs to? Or is it enough to be able to easily decide, given a tuple and an orbit, whether the tuple belongs to the orbit? One can probably imagine other computability criteria as well.

EDIT to take into account the edited version of the question:

Now that a computability requirement has been added, the problem has become considerably more difficult. In particular, it subsumes the graph isomorphism problem as follows. Let $n=1$ and $k=v(v-1)/2$ for some big integer v, so we're dealing with bit strings of length equal to the number of two-element subsets of $\{1,2,\dots,v\}$. Identify the indices 1 through $k$ with these 2-element sets in some canonical way (e.g. lexicographic). A bit string of length $k$ is thereby identified with a graph on the vertex set $\{1,2,\dots,v\}$. Let $G$ be the symmetric group of permutations of $\{1,2,\dots,v\}$, acting in the obvious way on the 2-element subsets and thus on $\{1,2,\dots,k\}$. Then the orbits amount to the isomorphism classes of graphs. If we had an efficient way to encode orbits, and to compute the code of an orbit from any member of the orbit, then we'd have an efficient test for graph isomorphism. In particular, the proposed computability requirement in the revised question, polynomial time in $n$, $k$, and $\log(|G|)$, would amount in this case to polynomial time in $v$.

Since it is still (as far as I know) open whether graph isomorphism can be computed in polynomial time, there is no known coding of orbits in this example, subject to the propoosed computability requirements.

Answer 2

EDIT - now that the question has been made more precise, my answer is out-of-date.

OLD - Your first question

Question 1: What is the smallest length binary string needed to encode k length n binary strings up to permutation?

has no definitive answer, as Kolmogorov complexity is not computable. One more point - if you don't want the smallest answer, but just a reasonable answer, then knowing the relative size of $k$ is very important. For example, when $k$ is around $2^n$ Gerhard's scheme works well. If $k \gg 2^n$ then one could think of the strings as $n$-bit binary numbers, sort the numbers by size, and count the number of each number.

As for question 2 - given $A = (a_1, a_2, \ldots, a_k)$ compute the orbit $G \cdot A$. Let $B$ be the lexicograpically first element of $G \cdot A$; use this as the representative of $A$.