Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

My Definition: The finite sequence $x_1,x_2,...,x_m$ of nonnegative integers is said to be generated by a finite group $G$ iff

  1. $n:=|G|=x_1+x_2+\cdots+x_m$.
  2. $n$ has $m$ divisors.
  3. if $d_1<d_2<\cdots<d_m$ are all divisors of $n$, for every $k = {1,...,m}$ we have $$x_k=\left|\{x \in G \mid o(x)=d_k\}\right|.$$

What are all conditions on a finite sequence $x_1,x_2,...,x_m$ such that it is generated by some group $G$?

Some conditions I found:

  • For $k = {1,...,m}$ we have $$\phi(d_k)\mid x_k$$ where $m$ and $d_k$ are as above.
  • $x_1=1$.
  • $x_m\leq\phi(n)$ and if $x_m=\phi(d_m)$ then for $k = {1,...,m}$, $$x_k=\phi(d_k) $$
  • If $x_k\ne 0$ then for every $i$ such that $d_i|d_k$, we have $$x_i\ne 0$$
  • If $d_k$ is a prime, $$x_k\ne 0$$
share|cite|improve this question
Relevant: If you really want all conditions, I suspect a complete answer would be very long and complicated. – MartianInvader Jan 29 '13 at 0:38
up vote 8 down vote accepted

I'm afraid that your question is very broad, and I doubt that it is answerable in full.

Let's start here.

For $n\in \mathbb{N}$, denote by $\pi(n)$ the set of prime divisors of $n$.

Definition. The prime graph of a finite group $G$, denoted $\Gamma(G)$, is a graph with vertex set $\pi(|G|)$ with an edge between primes $p$ and $q$ if and only if there is an element of order $pq$ in $G$.

Your question requires, among other things, knowing how many elements of order $pq$ there are in the group for every two primes $p,q$ dividing $|G|$, and in particular whether that number is nonzero. So answering your question would also tell us the answer to, "What are all the possible prime graphs of a finite group?" (In fact, it would be but a small corollary.) However, prime graphs are the subject of ongoing research, and there are still many unsolved problems in the world of prime graphs (most of which are easier than a full characterization).

We can perhaps reformulate your question into this language, though. Graphs can be generalized to hypergraphs, which are comprised of a vertex set $V$ and an edge set $E\subseteq \mathcal{P}(V)$ (i.e. the restriction that edges must connect at most two vertices in $V$ is removed).

For $n\in \mathbb{N}$, denote by $\overline{\pi}(n)$ the set of prime power divisors of $n$.

Definition. Define the weighted prime power hypergraph of a finite group $G$ as the hypergraph $\Gamma_H(G)$ with vertex set $\overline{\pi}(n)$ with a hyperedge $S$ if and only if the elements of $S$ are pairwise coprime and there exists an element of order $\prod_{s\in S}s$ in $G$. Furthermore, let each edge $S$ be given the weight $w_S$, which is equal to the number of elements of order $\prod_{s\in S}s$ in $G$.

Note that $\sum_{S\in E}w_S=|G|$. Naturally we can additionally define a strict total order on the edgeset of $\Gamma_H(G)$ where $S<T\Leftrightarrow \prod_{s\in S}s<\prod_{t\in T}t$. Sorting the weights by this order is equivalent to your $x_k$ sequence.

Thus your question is precisely "what are all possible ordered weight sequences of the prime power hypergraph of a finite group?" which is clearly a very complicated question.

The only thing I can say about really say about it is the following. For solvable groups $G$, it has been proven that $|\pi(|G|)|\leq 4\text{rank}(\Gamma_H(G))$ asymptotically. Additionally, it is conjectured that $|\pi(|G|)|\leq 3\operatorname{rank}(\Gamma_H(G))$ for all solvable groups. So, for solvable groups, you will always have to the count weights of edges whose size is up to at least one third the size of the vertex set.

To move forward, I would suggest you try to substantially narrow your question. You could restrict your question to a certain class of groups ($p$-groups? abelian groups? symmetric groups?). Furthermore I think it would be more likely to find an answer if you removed the ordering condition on $x_k$, as it adds a level of difficulty to the problem that I suspect outweighs any possible insight it would afford.

For further reading I'd recommend my answer to this similar question concerning sets of element orders, a related notion to yours.

share|cite|improve this answer
+1. When I saw this question had one answer already, there was no doubt in my mind about its author. I should also mention that the similar question you linked to is particularly well-posed. – Benjamin Dickman Feb 2 '13 at 1:13
Your answer was a surprise for me. So this is an open problem. I already have a paper from Maria Silvia Lucido about prime graphs. But didn't think it's related to this problem much. However, I have to study graph theory before trying to use prime graphs to solve the problem. Thanks. – user59671 Feb 2 '13 at 22:46
Oh which paper? I love Lucido's work. – Alexander Gruber Feb 2 '13 at 23:22
Groups in which the prime graph is a tree/ Bollettino dell’Unione Matematica Italiana, Serie 8, Vol. 5-B (2002), n.1, p. 131–148. Unione Matematica Italiana/Maria Silvia Lucido – user59671 Feb 3 '13 at 0:24
@CutieKrait Very good. I also recommend her paper on diameter of prime graphs. – Alexander Gruber Feb 3 '13 at 2:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.