An introduction to p-adic analysis via Paul Erdős:

Paul Erdős has been historically accused of being a good problem solver that didn’t do any deep mathematics. I think this is a very biased characterisation and while going over his proof of Bertrand’s postulate I encountered two interesting results on p-adic orders which increased my general level of interest in the field of p-adic analysis.

I shall represent these results by Erdős-BP1 and Erdős-BP2 but I shall first go over a couple lemmas as well as Legendre’s formula for p-adic orders.

What is a p-adic order?

For any prime \(p\) and any integer \(n\), let \(v_p(n)\) denote the largest power of \(p\) that divides \(n\).

Lemmas:

\begin{equation} \forall a,b \in \mathbb{N}, v_p(a \cdot b) = v_p(a) + v_p(b) \end{equation}

\begin{equation} \forall a,b \in \mathbb{N}^*, v_p(\frac{a}{b}) = v_p(a) - v_p(b) \end{equation}

Legendre’s formula:

For any prime \(p\) and any integer \(n\),

\begin{equation} v_p(n!) = \sum_{k=1}^\infty \big\lfloor \frac{n}{p^k} \big\rfloor = \sum_{k=1}^{\lfloor \text{log}_p (n) \rfloor} \big\lfloor \frac{n}{p^k} \big\rfloor \end{equation}

where \(\lfloor x \rfloor\) is the floor function.

Proof:

Since \(n!\) is the product of integers \(1\) through \(n\), we have at least one factor of \(p\) in \(n!\) for each multiple of \(p\) in \(\{1,2,...,n\}\) of which there are \(\lfloor \frac{n}{p} \rfloor\).

Each multiple of \(p^2\) contributes an additional factor of \(p\), each multiple of \(p^3\) contributes yet another factor of \(p\). By induction, this yields the infinite sum for \(v_p(n!)\) so we have:

\begin{equation} v_p(n!) = \sum_{k=1}^\infty \big\lfloor \frac{n}{p^k} \big\rfloor \end{equation}

and given that \(k > \text{log}_p(n) \implies \big\lfloor \frac{n}{p^k} \big\rfloor=0\) we have:

\begin{equation} v_p(n!) = \sum_{k=1}^{\lfloor \text{log}_p (n) \rfloor} \big\lfloor \frac{n}{p^k} \big\rfloor \end{equation}

which completes our proof.

Erdős-BP1:

For any prime \(p\), if \(R = v_p({2n \choose n})\) then \(p^R \leq 2n\).

Proof:

Using Legendre’s formula:

\begin{equation} R = \sum_{j=1}^\infty \big\lfloor \frac{2n}{p^k} \big\rfloor - 2 \sum_{j=1}^\infty \big\lfloor \frac{n}{p^k} \big\rfloor = \sum_{j=1}^\infty \Big(\big\lfloor \frac{2n}{p^k} \big\rfloor - 2 \big\lfloor \frac{n}{p^k} \big\rfloor \Big) \end{equation}

Now, we’ll note that there are three possible cases for each term in our summation:

\begin{equation} n \pmod{p_j} \equiv 0 \implies 2n \pmod{p_j} \equiv 0 \end{equation}

\begin{equation} 2n \pmod{p_j} \equiv 1 \implies n \pmod{p_j} \equiv 1 \end{equation}

\begin{equation} 2n \pmod{p_j} \equiv 0 \quad \text{and} \quad n \pmod{p_j} \equiv 1 \end{equation}

and as a result we have:

\begin{equation} \forall j, \big\lfloor \frac{2n}{p^k} \big\rfloor - 2 \big\lfloor \frac{n}{p^k} \big\rfloor \leq 1 \end{equation}

and since all terms with \(j > \text{log}_p (2n)\) are zero we have:

\begin{equation} R = \sum_{j=1}^{\lfloor \text{log}_p (2n) \rfloor} \Big(\big\lfloor \frac{2n}{p^k} \big\rfloor - 2 \big\lfloor \frac{n}{p^k} \big\rfloor \Big) \leq \text{log}_p (2n) \end{equation}

and therefore:

\begin{equation} p^R \leq 2n \end{equation}

QED.

Erdős-BP2:

If \(p\) is an odd prime and \(\frac{2n}{3} < p \leq n\), then \(R = v_p({2n \choose n}) = 0\).

Proof:

There are exactly two factors of \(p\) in the numerator of

\begin{equation} {2n \choose n} = \frac{(2n)!}{(n!)^2} \end{equation}

due to the terms \(p\) and \(2p\).

Now, there are also two factors of \(p\) in the denominator due to \((n!)^2\). As these factors cancel, there are no factors of \(p\) in \({2n \choose n}\).

References:

  1. Aigner, Martin; Ziegler, Günter (2009). Proofs from THE BOOK (4th ed.). Berlin, New York: Springer-Verlag.

  2. P. Ërdos, Beweis eines Satzes von Tschebyshef, Acta Sci. Math (Szeged) 5 (1930-1932)

  3. Khrennikov, A.; Nilsson, M. (2004). p-adic Deterministic and Random Dynamics. Kluwer Academic Publishers.