6

Basic group theory tells us that the order of each element divides the order of the group. What is known about the distribution of the orders of group elements?

For example, say we are working in $\mathbb{Z}^*_{11}$. The possible orders of the elements are: $1,2, 5, 10$. The actual orders of the elements are: (element, order)
(1,1)
(2,10)
(3,5)
(4,5)
(5,10)
(6,10)
(7,10)
(8,5)
(9,5)
(10,2)

From this data, there are 4 elements of order 10, 4 elements of order 5, but only 1 element of order 2 and one element of order 1. Thus, the order appear to be skewed more towards higher values. In a general sense does this hold, or is is more uniform?

mikeazo
  • 412
  • 4
    For cyclic groups like $\mathbb{Z}_p^\ast$, there are exactly $\varphi(d)$ elements of order $d$ for each divisor of the group order ($\varphi$ is Euler's totient function). For finitely generated abelian groups, you can find the distribution from that. – Daniel Fischer Jul 29 '13 at 17:54
  • @DanielFischer, looks like a good answer to me. Please post as an answer! – mikeazo Jul 29 '13 at 17:59
  • Hmm, it doesn't say anything about the distribution of orders for non-abelian groups, so I'd have thought it's only a partial answer. Wouldn't you like to wait a bit and see if somebody knows something about the non-abelian case? – Daniel Fischer Jul 29 '13 at 18:03
  • @DanielFischer Good point. I am most interested in the abelian case so if nothing else comes up your answer is definitely sufficient. – mikeazo Jul 29 '13 at 18:06
  • Okay, so I'll check back later, and if nothing better has been posted, expand my comment to an answer. – Daniel Fischer Jul 29 '13 at 18:08
  • 1
    Note that for the abelian case, you get two "extreme" cases, namely that of the cyclic group, where generally get more elements of larger orders, and the elementary abelian case where you only have elements of the smallest order. – Tobias Kildetoft Jul 29 '13 at 18:08
  • 1
    @mikeazo If you are only interested in groups of the form $\mathbb Z_p^\times$ that might be okay, because those groups are cyclic. The more general case of abelian groups becomes messier. And non-abelian groups are messier still. – Thomas Andrews Jul 29 '13 at 18:10

1 Answers1

7

For cyclic groups, the distribution of orders is simple (if we ignore the difficulty of factorisation of the group's order to find the divisors).

A cyclic group of order $n$ has exactly $\varphi(n)$ generators ($\varphi$ is Euler's totient function), and for each divisor $d$ of $n$ exactly one subgroup of order $d$ - if $g$ is a generator of the entire group, $\{ g^{k\cdot n/d} : 0 \leqslant k < d\}$ is the subgroup of order $d$, and $g^{n/d}$ is a generator of that subgroup - that subgroup is also cyclic, hence has $\varphi(d)$ generators. Conversely, in any group, an element of order $k$ generates a cyclic subgroup of order $k$, so in a cyclic group of order $n$, for each divisor $d$ of $n$, there are exactly $\varphi(d)$ elements of order $d$.

Since $a \mid b \Rightarrow \varphi(a) \leqslant \varphi(b)$, cyclic groups tend to have more elements with large orders than with small orders (but of course, the count does in general not increase monotonically with the order, a cyclic group with $1140$ elements has $18$ elements of order $19$, but only $16$ elements of order $60$ and only $8$ of order $30$).

From the cyclic case, you can obtain the distributions for finite(ly generated) abelian groups. Such a group is (isomorphic to) a direct sum of cyclic groups, and the order of an element is the least common multiple of the orders of the components. So to find the number of elements of order $k$ in

$$G \cong \bigoplus_{i=1}^m \mathbb{Z}/(n_i),$$

find all sequences $(d_1,\,\ldots,\, d_m)$ with $d_i \mid n_i$ and $\operatorname{lcm} (d_1,\,\ldots,\,d_m) = k$, and sum up the partial counts

$$\prod_{i=1}^m \varphi(d_i)$$

you get from choosing elements of order $d_i$ in each summand.

For small $m$, that is quite doable, but it becomes unwieldy rather fast if the number of summands grows.

Daniel Fischer
  • 206,697