Searching the symmetric group

Question

You want to design a set of yes/no questions for quickly searching the symmetric group. The questions have to be of the form "Does your permutation move $a_1$ to $b_1$ or $a_2$ to $b_2$ or ... or $a_k$ to $b_k$?" Given a random permutation, you will ask all of your questions about that permutation, and your goal is to know what the permutation is once you know the answers to your questions.

In particular, note that you aren't allowed to have later questions depend on the answers to earlier questions. You always ask the same questions of whichever random permutation you get.

Here's a slightly different way to phrase the type of question you're allowed to ask. If we represent the elements of the symmetric group by permutation matrices, then the questions you can ask involve picking a (0,1)-matrix and asking if the random permutation matrix has any 1 where your chosen matrix has a 1 (i.e., if I apply the componentwise AND function to the random matrix and your chosen matrix, do I get 0 or 1?)

Two questions:

1. How many such questions are needed in order to search $S_n$? How much bigger than $log_2 n!$ is this?
2. Are there "good" strategies for designing sets of questions that can be used for any n? Can we achieve the minimum number of questions for each n with a single strategy?

Answer 1

It certainly isn't difficult to obtain an upper bound of $n\lceil \log_2 n \rceil = O(\log_2 n!)$. All you need to do is to separately learn each bit of each value of the permutation. This looks like it is only roughly optimal, but actually it is already $(1+o(1))(\log_2 n!)$. (Thanks to t3suji for noticing this.) However, the $o(1)$ term only decays logarithmically in this algorithm, so you could ask whether you could make it $(1+O(n^{-\alpha}))(\log_2 n!)$.

I agree with Michael that it seems similar to the asymptotic question of sorting with comparisons. However, in the usual version of that problem, you are allowed to move elements based on an incomplete list of comparisons, which then amounts to adaptive comparisons. You could call this new question "non-adaptive Mastermind for permutations with matrix guesses". Michael also suggested the restricted problem of permutation guesses, which seems like a more difficult problem to me.

Answer 2

This is likely to be a difficult problem. It feels analogous to determining the minimal number of comparisons needed to sort n elements, which appears to only be known up to n = 13. In particular, in both cases we're getting information about a permutation one bit at a time.

However, I think it's known that asymptotically the number of comparisons needed to sort n elements is $(1+o(1)) log_2 (n!)$; I wouldn't be surprised to learn that the same is true for your problem. However, your constraint that later questions can't depend on earlier questions makes things tricky, because it's hard to think of "orthogonal" questions.

Call the unknown permutation $\sigma$. Then one sort of question that could be asked is "does your permutation satisfy $\sigma(k) = \tau(k)$ for any $k$", where $\tau$ is some fixed permutation. In general, the answer will be "yes" with probability about 1-1/e. Perhaps a clever choice of permutations $\tau$ would lead to a solution requiring $C log_2 (n!)$ questions, where $C = 1.0537...$ is the reciprocal of the entropy (in bits) of a Bernoulli(1-1/e) random variable.

Answer 3

(The question was updated after this answer and Alon's comment below were written)

If you ask $p$ questions, then the string of answers is a sequence of $p$ bits, with at most $2^p$ different answers. If the string of answers is supposed to identify a unique permutation, then you need that $2^p\geq n!$ or, equivalently, that $p\geq\log_2n!$.