4
$\begingroup$

I'm trying to work through this proof of the prime number theorem.

Def: Let $P_p(x)$ be the prime power of $p$ in the prime factorization of $x$. I.e. for any natural number $x$, $x = \prod_{p\in \text{primes}} p^{P_p(x)}$.

I am trying to prove the following lemma.

Lemma: $\forall p \in \text{primes}, \forall n\in \mathbb N: P_p\left({2n \choose n}\right) \leq \log_p(2n)$

My attempt at a proof: (tldr, I end up getting $P_p\left({2n \choose n} \right) \leq \log_p(n^2) + \frac{1}{p-1}$, how do I get the $2n$ in the log instead of the $n^2$?)

For any $a, b \in \mathbb N$, we have that $P_p(ab) = P_p(a) + P_p(b)$. Similarly, if $a/b \in \mathbb N$ then $P_p(a/b) = P_p(a) - P_p(b)$. Consider the $p=2$ case:

\begin{align*} P_2(n!) &= P_2(1) + P_2(2) + P_2(3) + P_2(4) + \dots\\ &= P_2(2) + P_2(4) + \dots\\ &= P_2(2\cdot 1)+ P_2(2\cdot 2) + \dots\\ &= \lfloor n/2 \rfloor \cdot P_2(2) + P_2(1) + P_2(2) + \dots + P_2(\lfloor n/2 \rfloor)\\ &= \lfloor n/2 \rfloor + P_2(\lfloor n/2 \rfloor !) \end{align*}

Similarly, for general $p$, \begin{align*} P_p(n!) &= \lfloor n/p \rfloor + P_p(\lfloor n/p \rfloor!)\\ &= \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + P_p(\lfloor n/p^2 \rfloor !)\\ &= \sum_{i=1}^{\log_p n} \lfloor n/p^i \rfloor \end{align*}

Then we can bound it as $P_p(n!) \leq \sum_{i=1}^{\log_p n} n/p^i$ and $P_p(n!) > \sum_{i=1}^{\log_p n}\left(n/p^i-1 \right)$. So then $$\frac{n-1}{p-1} - \log_p n < P_p(n!) \leq \frac{n-1}{p-1}$$

Then we finally get that \begin{align*} P_p\left({2n \choose n} \right) &= P_p((2n)!) - 2P_p(n!)\\ &< \frac{2n-1}{p-1} - 2\frac{n-1}{p-1} + 2\log_p n\\ &= 2\log_p n + \frac{1}{p-1} \end{align*}

How can I fix this so that I prove the desired lemma?

$\endgroup$
4
  • 4
    $\begingroup$ Instead of estimating $\lfloor n/q\rfloor$ and $\lfloor 2n/q\rfloor$ separately, try estimating the specific combination you care about. What are the possible values of $\lfloor 2n/q\rfloor - 2\lfloor n/q\rfloor$ (indeed, of the function $\lfloor 2t\rfloor - 2\lfloor t\rfloor$)? $\endgroup$ Dec 29, 2020 at 21:59
  • $\begingroup$ Oh beautiful, thank you! $\endgroup$
    – Joe
    Dec 29, 2020 at 22:02
  • $\begingroup$ @Joe Consider Kummer's theorem. $\endgroup$ Dec 29, 2020 at 22:02
  • 1
    $\begingroup$ A proof of this fact is given in Wikipedia here: en.wikipedia.org/wiki/…. $\endgroup$ Dec 30, 2020 at 0:50

1 Answer 1

2
$\begingroup$

Thanks to @Greg Martin for his answer. For completeness, I'll include the result here. As I have above, $P_p\left(n!\right) = \sum_{i=1}^{\lfloor \log_p n\rfloor } \lfloor n/p^i\rfloor$. So

\begin{align*} P_p\left({2n \choose n}\right) &= P_p((2n)!) - 2P_p(n!)\\ &= \sum_{i=1}^{\lfloor\log_p2n\rfloor}\lfloor 2n/p^i\rfloor - 2\sum_{i=1}^{\lfloor\log_p n\rfloor}\lfloor n/p^i\rfloor\\ &= \sum_{i=1}^{\lfloor\log_p2n\rfloor} \left(\lfloor 2n/p^i\rfloor - 2\lfloor n/p^i\rfloor \right)\\ &\leq \sum_{i=1}^{\lfloor\log_p2n\rfloor}1\\ &\leq \log_p2n \end{align*}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .