1
$\begingroup$

I am currently going through a proof by Erdős and I am having difficulty understanding one of his arguments. He first gives the following Lemma:

If ${n}\choose{k}$ is divisible by a prime power $p^a$, then $p^a \leq n$.

Now he says this:

Let $\pi(k)$ denote the number of primes less than or equal to $k$. It is clear that for $k \geq 8$, $\pi(k) \leq k/2$. Hence, if ${n}\choose{k}$ does not have prime factors greater than $k$, we should have, from the lemma, ${n}\choose{k}$ $\leq n^{k/2}$.

I do not follow this argument. Any help would be greatly appreciated.

$\endgroup$
1
$\begingroup$

The first statement (that $\pi(k) \leq \frac{k}{2}$) comes from the fact that prime numbers (except 2) are odd.

Now suppose that $\binom{n}{k}$ has only prime factors $\leq k$. There are at most $\frac{k}{2}$ such factors by the above statement. On the other hand, by the lemma, for each such prime factor $p$, $p^a \leq n$ where $a$ is largest such that $p^a | \binom{n}{k}$.

Therefore, $\displaystyle \binom{n}{k} = \prod_{i=1}^m p_i^{a_i} \leq \prod_{i=1}^m n = n^m \leq n^{\frac{k}{2}}$, where $\{p_i\}_{1\leq i\leq m}$ are the prime factors of $\binom{n}{k}$ and $a_i$ are the powers to which they appear in its prime factorization.

$\endgroup$
0
$\begingroup$

Suppose that $\binom{n}k$ has no prime factors greater than $k$, where $k\ge 8$; $\pi(k)\le\frac{k}2$, so $\binom{n}k$ has at most $\frac{k}2$ prime factors. Let these prime factors be $p_1,\ldots,p_m$, where $m\le\frac{k}2$, and for $i=1,\ldots,m$ let $p_i^{a_i}$ be the highest power of $p_i$ dividing $\binom{n}k$. Then by the lemma $p_i^{a_i}\le n$ for $i=1,\ldots,m$, so

$$\binom{n}k=\prod_{i=1}^mp_i^{a_i}\le n^m\le n^{k/2}\;$$

$\endgroup$
  • $\begingroup$ Thanks! Also, I couldn't figure out how to write the hungarian umlaut in Erdos' name. My usual \H{o} doesn't work. $\endgroup$ – ernest Nov 28 '13 at 16:28
  • $\begingroup$ @ernest: You’re welcome! For special characters I use a little Windows app called UniChars that works like the Linux Compose key. $\endgroup$ – Brian M. Scott Nov 28 '13 at 16:38

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.