Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

We say that an positive integer $n$ is a

  • simple number if there exist a non abelian simple group of order $n$. Denote by $\mathfrak{s}$ this set.
  • prime-power number if it is of the form $n=p^a$, with $p$ prime. Denote by $\mathfrak{pp}$ this set.
  • Sylow congruent number if it is a non prime-power number for which the congruence conditions of Sylow's theorem do not force at least one Sylow subgroup to be normal. In other words we can have $n_p\neq 1$ for all primes $p$ dividing $n$. Denote by $\mathfrak{sc}$ this set.

Also denote by $\mathfrak{p}$ the set of prime numbers.

Even though we know of the finite simple groups (I don't but some do), it seems unrealistic to expect an clean characterization of $\mathfrak{s}$.

For a set of positive integers $\mathfrak{t}$ we define $\pi_{\mathfrak{t}}$ the counting function of that set, i.e. $\pi_{\mathfrak{t}}(x)$ gives the number of elements in $\mathfrak{t}$ less than or equal to $x$, for any real number $x$.

It is well-known that $\pi_{\mathfrak{p}}(x)\sim\frac{x}{\ln x}$ (Prime number theorem).

Do we know the asymptotic laws of distribution for the other sets defined above, i.e. asymptotic behaviors of $\pi_{\mathfrak{pp}}(x)$, $\pi_{\mathfrak{s}}(x)$ and $\pi_{\mathfrak{sc}}(x)$, or $\pi_{\mathbb{N}\setminus \mathfrak{pp}}(x)$, $\pi_{\mathbb{N}\setminus \mathfrak{s}}(x)$ and $\pi_{\mathbb{N}\setminus \mathfrak{sc}}(x)$?

I suspect that we have $\pi_{\mathbb{N}\setminus \mathfrak{sc}}(x)\sim x$, or $\pi_{\mathbb{N}\setminus \mathfrak{sc}}(x)\sim k x$ for some $0<k<1$ (based on some computation). At least if we restrict to odd numbers.

share|cite|improve this question
I have not thought much about it, but I strongly suspect that the simple numbers are dominated by the orders $p(p^2-1)/2$ of the groups ${\rm PSL}(2,p)$ for odd primes $p$. – Derek Holt Oct 20 '11 at 15:50
@Nathan: is 12 in SC? – Jack Schmidt Oct 20 '11 at 15:57
@Jack: Yes 12 is in SC based only on the congruence criterion of Sylow Theorem, so are 24, 30, 36, 48, 56,... – Nathan Portland Oct 20 '11 at 16:30
@Derek: you are right, very strongly dominated by these numbers. There are 493 non abelian simple groups of order $<10^{10}$, of which 428 are of the type PSL($2,p$) for odd primes $p$. How does one prove it though? – Nathan Portland Oct 20 '11 at 18:04
@Nathan: I show how to prove a similar domination for pp. s is the same idea, just the sum is over more indices. All but finitely many simple groups are in families of the form X(r,p,k) and their orders are well approximated by a prime power (usually some large power of p^k), and so the only ones that don't wash out are the ones where r=k=1. – Jack Schmidt Oct 20 '11 at 18:20
up vote 2 down vote accepted

Here is a simpler problem that should get you going: Instead of counting prime powers, let's just count prime squareds.

$$\pi_{\mathfrak{p}^2}(x) = \#\{ p^2 : p^2 < x, p \in \mathfrak{p} \} = \#\{ p^2 : p < \sqrt{x}, p \in \mathfrak{p} \} = \pi_{\mathfrak{p}}(\sqrt{x})$$

You can estimate this using the good ole PNT:

$$\pi_{\mathfrak{p}^2}(x) \sim \frac{2\sqrt{x}}{\ln(x)}$$

Now several of your sets are basically counting prime powers. $\mathfrak{pp}$ for instance has a nice expression as:

$$\pi_{\mathfrak{pp}}(x) = \sum_{k=1}^{\log_2(x)} \pi_{\mathfrak{p}^k}(x) = \sum_{k=1}^{\log_2(x)} \pi_{\mathfrak{p}}(x^{(1/k)})$$

The asymptotics are the same:

$$\pi_{\mathfrak{pp}}(x) \sim \frac{x}{\ln(x)}$$

Similarly, I suspect there is no trouble with:

$$\pi_{\mathfrak{s}}(x) \sim \frac{3\sqrt[3]{x}}{\ln(x)}$$

Calculus fun:

$$\lim_{x\to\infty} \frac{ x/\ln(x) } { \sum_{k=1}^{\log_2(x)} kx^{(1/k)}/\ln(x) } = \lim_{x\to\infty} \frac{x}{\sum_{k=1}^{\log_2(x)} kx^{(1/k)}}$$

Clearly the operand of the limit is less than 1 for all $x > 1$, so we squeeze from below:

$$\begin{align} 1 &\geq \lim_{x\to\infty} \frac{x}{\sum_{k=1}^{\log_2(x)} k x^{(1/k)}} \\ \\ &\geq \lim_{x\to\infty} \frac{x}{x + \sqrt{x} \sum_{k=2}^{\log_2(x)} k} \\ \\ &\geq \lim_{x\to\infty} \frac{x}{x+\sqrt{x} (\log_2(x))^2} = 1 \end{align}$$ In the second line, I use that $\sqrt{x} \geq x^{(1/k)}$ for $k \geq 2$, and then in the third line I overestimate an arithmetic series. In the last line, we divide top and bottom by x and the second term of the denominator goes to 0.

share|cite|improve this answer
Thanks a lot Jack, I am skeptical about $\pi_{\mathfrak{s}}(x) \sim \frac{\sqrt{x}}{2\ln(x)}$, because $\pi_{\mathfrak{s}}(10^{10})= 493$, which is about 5 times smaller than the right side of $\sim$. I know it grows slowly, so it may be correct after all... – Nathan Portland Oct 20 '11 at 18:46
@Nathan: Oh sorry, PSL(2,p) has order about p^3 not p^2. I also had the k in the wrong place. All fixed now. The calculus is less fun (arithmetic series instead of harmonic), but no big change. – Jack Schmidt Oct 20 '11 at 19:14
Thanks again Jack. – Nathan Portland Oct 20 '11 at 20:36

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.