From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math.research
Subject: Re: number of conjugacy classes in finite groups
Date: 8 Sep 1995 08:13:58 GMT

In article <42n3fh$ij0@nef.ens.fr>,
Philippe Crocy <crocy@clipper.ens.fr> wrote:
>Is it possible to give an explicit upper bound to the order of a finite
>group, depending only on the number of conjugacy classes of this group?
>(that is, to give a function f such that the order of any finite group
>containing x conjugacy classes should be at most f(x) ?)

One upper bound (which I doubt can be sharp) can be shown to exist 
using group theory, and perhaps can be made explicit using number theory.

Consider the class equation counting the number of group elements in
each conjugacy class:  |G| = Sum( [G:C_G(x_i)], i=1..k ). Dividing by
|G|  gives a sum of unit fractions adding to  1: 
(*)	1 = Sum( 1/ n_i,  i=1..k )
where the  n_i = |C(x_i)|  may be arranged in increasing order, say.

Now, it is easy to see that for each  k,  equation (*) has only a 
finite number of solutions. (Indeed,  n_1  is at most  k; then  n_2  is
at most  (k-1)/(1 - 1/n_1), and in general  n_m  is at most
(k+1-m)/(1-Sum(1/n_i, i<m)); the denominators must be positive.)
For example, I count  14  solutions when k=4; in lexicographic order,
from  2 3 7 42  to  4 4 4 4. The largest  n_i  in any of these is 42.
Likewise when k=5 I count 148 solutions; the largest  n_i  in any is  1806.

But this number is key: since every group has a center (at least including
{1}), at least one of the centralizers has order  |G|; thus, the largest
n_i  will be the order of the group, and so the largest  n_i appearing
in any solution will be an upper bound on the order of a group with
k  conjugacy classes. This approach gives the bounds
	1,  2,  6,  42,  1806, ...
for |G|,  for the cases  k=1, 2, 3, 4, 5, ...

Thus an upper bound exists. In order to determine it explicitly, one has to 
know something about the terms in this (finite) solution set.

I would imagine, but cannot prove right now, that the first solution
lexicographically has the largest n_k. This solution always begins
	2, 3, 7, 43, 1807, ...
where each term is one more than the product of the ones before it,
that is,  n_(i+1)=n_i^2-n_i+1  (until the k-th and last term, which is
one less). If I am right, that the largest value f(k) of all the  n_k's
is the  n_k  in the first solution, then we have
	f(k+1)=f(k)^2+f(k),
which then gives an exponential bound, of the form  log(f(k)) < a * 2^k.

This seems rather dramatic. I would conjecture that a polynomial bound on 
log(f(k)) exists. Surely the number-theoretic constraints on the degrees
of the characters (there are also  k  of them of course) would give more
information.

I'm sure the number theorists have looked at  (*), too.

dave

==============================================================================

From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math.research
Subject: Re: number of conjugacy classes in finite groups
Date: 8 Sep 1995 22:22:06 GMT

In article <42n3fh$ij0@nef.ens.fr>,
Philippe Crocy <crocy@clipper.ens.fr> wrote:
>Is it possible to give an explicit upper bound to the order of a finite
>group, depending only on the number of conjugacy classes of this group?
>(that is, to give a function f such that the order of any finite group
>containing x conjugacy classes should be at most f(x) ?)

Then in article <42ou06$20b@watson.math.niu.edu>, I wrote:
[naive upper bound attained...]
>which then gives an exponential bound, of the form  log(f(k)) < a * 2^k.
>
>This seems rather dramatic. I would conjecture that a polynomial bound on 
>log(f(k)) exists. 

But I knew I had seen this general problem before. A paper by some guy
named Rusin included a reference to
	Erdos and Turan, "On some problems of a statistical group theory IV"
	Acta Math Acad Sci Hung  19 (1968) 413-435
which shows that the number of conjugacy classes is at least
	k >= log log |G|
giving a solution more or less as good as the one I outlined in the previous
article. I guess if Erdos and Turan are willing to give up when they
get this far, then I should too. However, there are papers by Bertam (1974)
and Sherman (1978) which get better mileage by discussing "almost all"
groups, and nilpotent groups, respectively.

dave