10
$\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?

$\endgroup$
2
  • $\begingroup$ what is $\ln n$ here? which function is it? Is it usual logarithm? $\endgroup$ – Why Oct 2 '19 at 11:49
  • 1
    $\begingroup$ @M.A.SARKAR $\ln x $ denotes the natural logarithm, also denoted $\log x $. $\endgroup$ – Américo Tavares Oct 4 '19 at 21:21
8
$\begingroup$

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.

$\endgroup$
0
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks as well! To follow your proof I feel I need to learn more advanced concepts. I will try to do so. $\endgroup$ – Américo Tavares Aug 19 '10 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.