12
$\begingroup$

We have had many questions here about the divisibility of $\binom{n}{k}$, many of them dealing with divisibility by powers of primes, or expressions involving the $\textrm{gcd}(n,k)$ (I originally gave several more examples but took TheSimpliFire's advice to shorten the list, and many other examples can still be found by looking at this question's edit history):

The topic has also lead to some interesting research papers recently:

There's also many associated theorems:

However I've come across a related problem which is expressed completely in the title, and is remarkably not covered by the above extensive body of literature. In MathJax, if $s>0$ is an integer (let's also make it the largest one for which $2^s$ divides $n$), under what conditions of $k$ do we have the following:

$$ 2^s \mid n \implies 2^s \left\vert \binom{n}{k} \right. . \tag{1} $$

Since $\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}$ and $2^s \mid n$ we are left with determining when $\frac{q}{k} \binom{n-1}{k-1}$ is an integer ($q$ being the result when $n$ is divided by $2^s$).

The implication works for a remarkable number of cases, but not always (for example if $\binom{n}{k}$ is odd).

$\endgroup$
2
  • $\begingroup$ You can try to take a look to Lucas' Theorem for Prime Powers. $\endgroup$
    – BillyJoe
    Nov 12, 2020 at 21:30
  • $\begingroup$ @BillyJoe Thank you for that paper!!! I have attempted an answer based on it, which you can look at below. If you have any idea how to simplify this for my special case of $n=2$ and $2^s \mid n$, I would be most grateful! $\endgroup$ Nov 12, 2020 at 23:22

2 Answers 2

7
$\begingroup$

This is a comment, but a little long comment.

Recall the definition of the $2-$adic valuation of $n,$ $\nu _2(n),$ meaning the biggest exponent of $2$ that divides $n.$

Your problem, then, can be stated as $s\leq \nu _2(n)$ implies $s\leq \nu _2 \left( \binom{n}{k}\right ).$ From legendre's theorem (i.e., $\nu _2(n!)=n-S_2(n)$ where $S_2(n)$ is the sum of the $1$'s in the $2-$adic expansion of $n$) is not hard to show that $$\nu _2 \left( \binom{n}{k}\right )=n-S_2(n)-(k-S_2(k))-(n-k-S_2(n-k))=S_2(n-k)+S_2(k)-S_2(n).$$ and $$\nu _2(n)=\nu_2(n!)-\nu _2((n-1)!)=1+S_2(n-1)-S_2(n).$$ So your proposition becomes

$s-1\leq S_2(n-1)-S_2(n)$ implies $s\leq S_2(n-k)+S_2(k)-S_2(n).$

this can be, at least, be satisfied if $S_2(n-1)+1\leq S_2(n-k)+S_2(k).$ This is trivial if $k=1.$ For example, if $n$ is odd, this is equivalent to $S_2(n)\leq S_2(n-k)+S_2(k)$ which is always the case, for example if the expansion of $k$ has $1'$s where there is a $1$ in the expansion of $n.$

$\endgroup$
3
  • 1
    $\begingroup$ Thank you for the insight here. I gave you +1! I added a clarifying edit to the question, saying that $s$ is the largest integer such that $2^s$ divides $n$. So really $s$ is fixed and the question is about which values of $k$ allow the proposition to be valid. While it's true that it works for $k=1$, it also works for $k=3,5,7,\ldots.$ Finally I may say that the question has come up for a 1st year undergrad Math course that I'm teaching, so Legendre's theorem and "p-adic valuation" will be a little bit advanced for the students! $\endgroup$ Nov 11, 2020 at 18:07
  • $\begingroup$ so if $s=\nu _2(n)$ then we are in the case of the one to last inequality. For this my gut tells me to try to use automatic sequences. Probably in the book by Allouche and Shallit there should be something about this. In the last remark I am not sure if all the bibliography and thms that you cite are more elementary than this. Legendre was one of the first theorems I encountered during my undergrad. I will try, tho, to change the language if something comes to mind. Thanks for the feedback! $\endgroup$
    – Phicar
    Nov 11, 2020 at 18:44
  • 2
    $\begingroup$ Interesting, since Shallit is at my university (Waterloo) but he's in the CS department and had nothing to do with this Math course. The theorems and papers that I cited, are far more advanced than the level of these 1st year undergrads, but it was to show some context on what I found so far in the research I did before asking the question, and to show that questions on the divisibility of binomial coefficients are still a very interesting and active topic. About Legendre's formula: the students haven't learned it, or p-adic anything yet, unfortunately. $\endgroup$ Nov 11, 2020 at 18:51
4
$\begingroup$

With the very helpful tip from user BillyJoe, we can say that for any prime $p$,

$$\tag{1} \binom{n}{k} \equiv \left\langle {n_{s-1}\cdots n_0 \atop k_{s-1}\cdots k_0} \right\rangle \prod_{j=1}^{r-s+1}\left\langle {n_{j+s-1}\cdots n_j \atop k_{j+s-1}\cdots k_j} \right\rangle\left\langle {n_{j+s-2}\cdots n_j \atop k_{j+s-2}\cdots _j} \right\rangle^{-1} \left( \textrm{mod} ~ p^s \right), $$

where the indices 0 and $r$ represent the terms corresponding to the lowest and highest powers (respectively) in the $p$-adic expansions of $n$ and $k$, and the angular brackets correspond to a slight modification (described in more detail here) of the ordinary binomial coefficient symbols.

We then have that:

$$ \left\langle {n_{s-1}\cdots n_0 \atop k_{s-1}\cdots k_0} \right\rangle \prod_{j=1}^{r-s+1}\left\langle {n_{j+s-1}\cdots n_j \atop k_{j+s-1}\cdots k_j} \right\rangle\left\langle {n_{j+s-2}\cdots n_j \atop k_{j+s-2}\cdots _j} \right\rangle^{-1} \equiv 0 \left( \textrm{mod} ~ p^s \right),\tag{2} $$

if and only if $p^s \mid \binom{n}{k}$.

We therefore have a general condition for when $p^s$ divides $\binom{n}{k}$, whether or not $p^s \mid n$.

For the special case where $p=2$ and $2^s \mid n$, which was the premise of the original question, we may be able to get a cleaner expression than what I have above in Eq. 2.

$\endgroup$

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.