Orbit maximin problems - MathOverflow

Orbit maximin problems

2010-02-07T04:39:38Z

I'm interested in answering questions such as: find a permutation group of n elements restricted to the class of solvable groups for which the minimum of the sizes of orbits of subsets of size 2 is maximized. In other words, there are no "small" orbits on subsets of size two.

Here is a basic fact: if a solvable group has a 2-set-transitive action on a set, then the size of that set must be a prime power. This is because a 2-set-transitive action must be a primitive action, and so the maximal subgroup that is the stabilizer of some point has as a complement a minimal normal subgroup that turns out to be elementary abelian (because the whole group is solvable), and is in bijection with the set being acted upon. This is related to the fact that any maximal subgroup of a solvable group has prime power index.

Conversely, if n is a prime power, there exists a solvable group acting 2-transitively (on orbitals, i.e., ordered pairs of distinct elements, and hence also on unordered pairs). One natural construction for such a solvable group is as the affine group of a field with n elements (there are other constructions for some n).

Thus, the question is completely settled for prime powers. What can we say for other numbers?

This question occurred to me in the context of a related question that comes up when looking at a more restricted property of groups than solvable groups, called "Oliver's condition": groups that are q-group extensions of cyclic extensions of p-groups. In a joint paper (not yet published), my co-authors and I were able to show that for large enough n, we can use results about the distribution of prime numbers to obtain actions by groups satisfying Oliver's condition where all the orbits are of size $\Omega(n\log n)$ (unconditionally), $\omega(n^{5/4 - \epsilon})$ (conditional to the ERH) and $\omega(n^{3/2 - \epsilon})$ (conditional to Chowla's conjecture). We used this to tackle a conjecture about the decision tree complexity of graph properties. An ArXiV version of our paper (short version for conference) is available here.

Any ideas for tackling other restricted classes of solvable groups would also be much appreciated.

Answer by Jack Schmidt for Orbit maximin problems

2010-02-07T11:02:01Z

When n=2q is twice an odd prime power q, I think G = AGL(1,q) wr Sym(2) (amongst others) has the largest minimum orbit length on 2-sets. If G acts on Z = X ∪ Y, each of size q, then G has two orbits on Z⁽²⁾, { {a,b} : a,b in X } ∪ { {a,b} : a,b in Y } of size 2⋅Binomial(q,2), and { {a,b} : a in X, b in Y } of size q². When q is even, those are still the orbits, but of course AGL(1,2q) has only a single orbit.

When n=3q is three times a prime power q coprime to 3, then again AGL(1,q) wr Sym(3) looks reasonable, with only two orbits, one of size 3⋅Binomial(q,2), one of size 3⋅q². At any rate, if it is not maximal it has a fairly large minimal orbit.

Obviously you can't keep taking Sym(k) for k=2,3,4,... forever, but I think actually it suffices to use the regular permutation representation Cyclic(k) of the cyclic group of order k. The largest orbit often splits into more than one orbit, but they are all so large it appears not to matter.

In other words, you might try AGL(1,q) wr Cyclic(k) for fairly general k and q, when n=k⋅q. I think the minimum orbit size will always be the silly disjoint union one of size k⋅Binomial(q,2), which is pretty large as long as you hold k constant. You can probably replace AGL(1,q) with your paper's Γ(q,d) without too much trouble.

I am under the impression that in asymptotic group theory, it is often quite hard to find exact sharp bounds, so just having "large" examples like these might be sufficient, at least for numbers with a very large prime power factor (so that k is kept small).

Answer by Vipul Naik for Orbit maximin problems

2010-02-10T15:22:26Z

After thinking quite a bit about this, I seem to have arrived at what appears to be the best construction, though I don't know how one would prove that it is indeed optimal.

Write:

$n = p_1 + p_2 + \dots + p_r$

where $p_i$ are all primes. Then, divide the set of size n into subsets of sizes p_i and consider the permutation group to be the direct product of the affine groups corresponding to the fields of size $p_i$. In other words, on each piece, the group acts as the affine group (i.e., the semidirect product of the additive and multiplicative groups of the field). The orbit sizes of unordered pairs are $\binom{p_i}{2}$ and $p_ip_j$, hence the minimum of these is $\binom{\min_i { p_i } }{2}$. Moreover, this permutation group is solvable. In fact, it is a metabelian group (abelian normal subgroup, abelian quotient) and has polycyclic breadth $2r$.

My claim is that the best solution happens for a choice of partition where the smallest of the $p_i$s is as large as possible. A slight strengthening of Vinogradov's theorem (e.g., by Haselgrove and later by Jia Chaohua) shows that for odd n we can choose $r = 3$ and each of the primes as $n/3 + o(n)$. Extending that, for even $n$, we can choose the primes to be $n/4 + o(n)$. Thus, the orbit sizes are all at least $n^2/32 + o(n^2)$. In other words, we can always get an action where all the orbits are $\Omega(n^2)$.

I'd be curious if a similar result can be obtained without using such deep results from number theory.