9
$\begingroup$

In section 4 of the article by Afred van der Poorten's A Proof That Euler Missed ... the following inequality is used:

$$\nu_{p}\displaystyle\binom{n}{m}\leq\left\lfloor\dfrac{\ln n}{\ln p}\right\rfloor-\nu_{p}(m)\qquad(\ast)$$

(In the original denoted $\text{ord}$ $_{p}(\cdot)$ instead of $\nu_p(\cdot)$).

where $\nu_{p}(k)$ is the $p$-adic valuation of $k\in\mathbb{Q}$, i. e. the exponent of the prime $p$ in the prime factorization of $k$. I know some properties of the foor function and that

$$\nu_{p}(a/b)=\nu_{p}(a)-\nu_{p}(b),$$

$$\nu_{p}(a\cdot b)=\nu_{p}(a)\cdot \nu_{p}(b)$$

and

$$\nu_{p}(n!)=\displaystyle\sum_{i\geq 1}\left\lfloor \dfrac{n}{p^{i}}\right\rfloor $$

but I didn't convince myself on the correct argument I should use to prove $(\ast )$.

Question: How can this inequality be proven?

2 Answers 2

7

Since $\nu_p(n!)=\sum_i\lfloor n/p^i\rfloor$, $\nu_p\binom nm=\sum_i(\lfloor n/p^i\rfloor-\lfloor m/p^i\rfloor-\lfloor (n-m)/p^i\rfloor)$. Observe that each summand is $\le 1$, and for $i>\left\lfloor\frac{\ln n}{\ln p}\right\rfloor$ it's clearly $0$. That gives $v_{p}\binom{n}{m}\le \left\lfloor\frac{\ln n}{\ln p}\right\rfloor$.

Finally observe that for $i\le\nu_p(m)$ $\lfloor m/p^i\rfloor=m/p^i$, so ($\lfloor m/p^i\rfloor+\lfloor x/p^i\rfloor=\lfloor(m+x)/p^i\rfloor$ and) the corresponding summand is also $0$. That gives the inequality in question.

5

Theorem (Kummer): $\nu_p {n \choose m}$ is the number of carries it takes to add $m$ and $n-m$ in base $p$.

Now note that $\lfloor \frac{\ln n}{\ln p} \rfloor$ is the maximum possible number of carries and the last $\nu_p(m)$ digits of $m$ cannot be associated to any carries.

Kummer's theorem itself is not hard to prove; it more or less follows from the last identity you list.

  • 0
    Thanks as well! To follow your proof I feel I need to learn more advanced concepts. I will try to do so.2010-08-19