## 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:

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

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

## Legendre’s formula:

For any prime $$p$$ and any integer $$n$$,

$$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$$

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:

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

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

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

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:

$$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)$$

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

$$n \pmod{p_j} \equiv 0 \implies 2n \pmod{p_j} \equiv 0$$

$$2n \pmod{p_j} \equiv 1 \implies n \pmod{p_j} \equiv 1$$

$$2n \pmod{p_j} \equiv 0 \quad \text{and} \quad n \pmod{p_j} \equiv 1$$

and as a result we have:

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

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

$$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)$$

and therefore:

$$p^R \leq 2n$$

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

$${2n \choose n} = \frac{(2n)!}{(n!)^2}$$

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.