Maximizing a lower bound on the computational complexity

We solve a combinatorial problem that arises in determining by a method due to Engeler lower bounds for the computational complexity of algorithmic problems. Denote by G_d the class of permutation groups G of degree d that are iterated wreath products of symmetric groups, i.e. G = S_dh?11?1S_d0 with Π^h?1_i=0d_i = d for some natural number h and some sequence (d₀,…,d_h?1) of natural numbers greater than 1. The problem is to characterize those G = S_dh?11?1S_d0 in G_d on which k(G):=log|G|/max_0≤i≤h?1log(d_i!) assumes its maximum. Our solution consists of two necessary conditions for this, namely that d₀≤d₁≤?≤d_h and that d_h is the largest prime divisor of d. Consequently, if d is a prime power, say d = p^h with p prime, then a necessary and sufficient condition is that d_i = p, 0 ≤ i ≤ h ? 1.