The probability of conjugacy

Last week John Britnell spoke in the London Algebra Colloquium. He talked about joint work with Simon Blackburn and Mark Wildon (the preprint is here), and remarked that since they are both at Royal Holloway and he is in Bristol, it would have been cheaper for the Colloquium to have invited one of them instead.

The talk was on a very natural question which, remarkably, has not been considered before:

Given a finite group G, what is the probability κ(G) that two (independent uniform) random elements of G are conjugate?

The talk was in three parts, of which the most substantial part concerned groups for which this probability is “large”. It is at most 1/2 for any non-trivial group, since given the first element, the size of its conjugacy class is not more than half of the group order. On the other hand, the main theorem of BBW asserts that, if κ(G) ≥ 1/4, then either G is the semi-direct product of an abelian group A of odd order with a group of order 2 inverting A, or G is one of finitely many exceptions (the largest of which has order 60). It follows that 1/4 is the largest limit point of values of κ(G).

More generally, if H is a finite group which is a Frobenius complement, then the number κ(H)−1/|H|2 is a limit point of the values of κ(G) over Frobenius groups G having Frobenius complement H.

This provoked some discussion. Charles Leedham-Green remarked that these limit points are values of κ(G) (suitably defined) for profinite groups G, and wondered if perhaps every limit point was the value of κ for some profinite group. This is a question for which a proof seems out of reach with present knowledge; but perhaps a counterexample would be easier.

The second topic concerned groups for which the probability is “small”. In these cases it is better to consider the parameter |G|κ(G) instead. The value of this parameter is at least 1, with equality if and only if G is abelian. They show that, if G is non-abelian, then the value of the parameter is at least 7/4, with equality if and only if the centre of G has index 4.

This is reminiscent of a result for the probability that two random elements commute, which is 1 for abelian groups, and for non-abelian groups is at most 5/8, with equality if and only if the centre has index 4. It is not coincidence that something like this happens; John remarked that both |G|κ(G) and the probability that two elements commute are invariant under isoclinism.

[In any group G, the commutator map induces a function from (G/Z(G))×(G/Z(G)) to the derived group G‘; two groups G and H are isoclinic if there are isomorphisms G/Z(G)→H/Z(H) and G‘→H‘ which respect the commutator map.]

The final part concerned an intermediate class of groups, the symmetric groups. Here, John admitted that they had been scooped by a French team consisting of Flajolet, Fusy, Gourdon, Panario and Pouyanne. (This doesn’t contradict the statement that nobody had looked at the problem before, since for the symmetric group it is purely combinatorial: what is the probability that two random permutations have the same cycle structure?) The result is that κ(Sn) is asymptotically c/n2, where (in a nice piece of self-reference) the constant c is the sum, over all n, of the values of κ(Sn). (The constant is about 4.26.) The proof by FFGPP, as you would expect, uses methods of analytic combinatorics, whereas BBW have a more elementary, though computational, proof. Incidentally, the value of n2κ(Sn) is maximised when n=13, the maximum being about 5.48.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, mathematics and tagged , , . Bookmark the permalink.

2 Responses to The probability of conjugacy

  1. pvhegarty says:

    Dear Peter,

    I wonder if every value in [0,1/4) is a limit point for values of k(G) ? And is every rational numebr in the interval an actual value of k(G) ? I was asking myself the same questions for the commuting probability, and when I googled for information, all that came up was your blogpost. One interesting thing about the commuting probability is that 1/2 is the largest limit point, but then there is a new gap below 1/2, down to 7/16.

    Cheers,
    Peter Hegarty (Gothenburg, Sweden)

    • Dear Peter,

      I don’t know the answer, though I would guess that it is no. Perhaps one of the three authors of the paper would know more? If I have any thoughts, I will report them. Certainly any cyclic group is a Frobenius complement, so (n−1)/n2 is a limit point for every n.

      Peter.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s