Prime Decomposition of Highly Composite Number

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n$ be a highly composite number.

Let the prime decomposition of $n$ be expressed as:

$n = \ds \prod_{k \mathop \in \N} {p_k}^{r_k}$

where $p_k$ denotes the $k$th prime.

Then the sequence $\sequence {r_k}$ is decreasing.


That is:

$\forall k \in \N: r_k \ge r_{k + 1}$


Proof

Let $n = \ds \prod_{k \mathop \in \N} {p_k}^{r_k}$ be highly composite.

By definition of divisor count function:

$\map {\sigma_0} n = \ds \prod_{k \mathop \in \N} \paren {r_k + 1}$

Aiming for a contradiction, suppose $r_{l + 1} > r_l$ for some $l \in \N$.

Consider $m \in \Z$ whose prime decomposition of $n$ is expressed as:

$m = \ds \prod_{k \mathop \in \N} {p_k}^{s_k}$

where:

$\forall j < l: s_j = r_j$
$\forall j > l + 1: s_j = r_j$
$s_l = r_{l + 1}$
$s_{l + 1} = r_l$

We have that:

\(\ds \map {\sigma_0} m\) \(=\) \(\ds \prod_{k \mathop \in \N} \paren {s_k + 1}\) Definition of Divisor Count Function
\(\ds \) \(=\) \(\ds \prod_{k \mathop \in \N} \paren {r_k + 1}\) as all the $s$s are the same as all the $r$s, but in a different order
\(\ds \) \(=\) \(\ds \map {\sigma_0} n\) Definition of Divisor Count Function

Thus:

$\map {\sigma_0} m = \map {\sigma_0} n$


Now we have that:

$r_l < r_{l + 1}$

and so:

$s_l > s_{l + 1}$

and so:

\(\ds \frac { {p_l}^{r_l} {p_{l + 1} }^{r_{l + 1} } } { {p_l}^{s_l} {p_{l + 1} }^{s_{l + 1} } }\) \(=\) \(\ds \frac { {p_l}^{r_l} {p_{l + 1} }^{r_{l + 1} } } { {p_l}^{r_{l + 1} } {p_{l + 1} }^{r_l} }\)
\(\ds \) \(=\) \(\ds \frac { {p_l}^c} { {p_{l + 1}^c} }\) where $c = r_{l + 1} - r_l$


Then:

$p_{l + 1} > p_l$

and so:

${p_{l + 1} }^c > {p_l}^c$

from which it follows that:

$m < n$

while:

$\map {\sigma_0} m = \map {\sigma_0} n$

But $n$ is highly composite.

This means that if $\map {\sigma_0} m = \map {\sigma_0} n$, then $n \le m$.

This is contradicted by $n > m$.

Thus by Proof by Contradiction:

$\forall k \in \N: r_k \ge r_{k + 1}$

$\blacksquare$


Sources