## 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}$$.

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.