I've recently started trying to teach myself some basic theory of permutation groups. I wanted to compute the minimum base size of the permutation group $G=S_d\,wr\,S_r$ equipped with the product action of degree $d^r$. I'm not super familiar with wreath products so I've had a bit of trouble (this is an exercise from Dixon and Mortimer, chapter 3). Here is what I've tried:
Think about the objects $G$ acts on as tuples rather than functions. Now, if we 'stack' some of these tuples, we see that the action of $G$ is essentially permuting the columns of this stack, and then, within each column, it is applying some permutation to each of the entries. Therefore, a base will simply be a stack such that no column is fixed by a nontrivial permutation in $S_d$, and that no two distinct columns are permutation-equivalent, ie no column can be obtained from another by applying a permutation in $S_d$.
In order to ensure no column is fixed by a nontrivial permutation we need that $d-1$ distinct entries appear in each column. Let $a(n)$ be the number of possible $n$-tuples such that $d-1$ of the elements of $[d]$ appear at least once. Then each permutation-equivalence class of these $n$-tuples has $d!$ elements since every nontrivial permutation acts nontrivially on them, and so there are $a(n)/d!$ possible equivalence classes. Therefore, the minimum base size is the minimum $n$ such that $r\leq a(n)/d!$.
Is this all correct? I would like to get a closed form so where I'm at right now is not particularly helpful. Any ideas are greatly appreciated.
Best Answer
I would class this as a research level problem, so you should ask it on mathoverflow, including a link to your post here.
There has been a lot of research on mimimal base sizes of primitive groups $G$ of degree $n$, by Babai, Liebeck, and others. Unfortunately, typical results say (roughly) that either $G$ is contained in a primitive wreath product $S_d \wr S_r$ with $S_d$ acting on $k$-element subsets for some $k$, or the minimal base size is at most $9 \log_2 n$.
I could not find any precise results on $S_d \wr S_r$ with the natural actions of $S_d$ and $S_r$. It could be difficult to get a closed formula, but that might be possible. Generally good upper and lower bounds are sufficient for applications.
I couldn't follow your argument completely - I think you would need to make it a bit more formal and precise. It is not hard to see that $d-1$ is the minimal base size for the base group of the wreath product, and the minimal base size for the standard complement is (I think) $\lceil \log_2 r \rceil$.
So that would give a lower bound of $\max(d-1, \lceil \log_2 r \rceil)$ for the minimal base size of $G$.
On the other hand, you could combine bases of the base group and complement to get a base of $G$ of size $d-1 +\lceil \log_2 r \rceil$, so that would be an upper bound.
I did a few computer calculations for small $d$ and $r$, and my impression is that the answer is closer to (but not equal to) the lower bound, but I don't have enough data to make reasonable conjecture for the exact answer.