A quick, cool result to distract you from finals

If you are like me, you’ve probably got lots to do for final exams and things of the like as the semester (trimester, quarter, whatever your school uses) comes to a close. In an effort to take a bit of break, I would like to present you with a cute little result I came across in my studies. It’s a nice little number theory fact with a cute combinatorial proof. I found the result in Hatcher’s book on algebraic topology, and I’ll present an adapted version of his proof (though I’m sure it’s in many other books).

First we need to remember a little about p-adic representations of integers. If n is any integer (technically we should assume n\geq0, it doesn’t really matter), and if p is a prime number, then n can be written (uniquely) as n=\sum_{l} n_lp^l, where 0\leq n_l<p are integers. This is easy to prove using the fundamental theorem of arithmetic and the division algorithm. Without further adieu I give you the following

Proposition: Let p be a prime number and n,k\in\mathbb{N}. Then

\binom{n}{k}=\prod_l\binom{n_l}{k_l}\mod p

where n=\sum_l n_lp^l and k=\sum_l k_lp^l are the p-adic representations of n and k.
Proof: Recall that in the polynomial ring \mathbb{Z_p}[x], we have the identity (1+x)^{p^j}=1+x^{p^j}. Working modulo p, we have

(1+x)^n=(1+x)^{n_0}(1+x^p)^{n_1}(1+x^{p^2})^{n_2}\dots

=\left(1+\binom{n_0}{1}x+\binom{n_0}{2}x^2+\dots+\binom{n_0}{p-1}x^{p-1}\right)\times

\left(1+\binom{n_1}{1}x^p+\binom{n_1}{2}x^{2p}+\dots+\binom{n_1}{p-1}x^{(p-1)p}\right)\times\dots

On one hand, we know that the coefficient of x^k in this expansion is \binom{n}{k}. On the other hand, if we expand the product on the right, it’s easy to see that no two terms in the product will have the same power of x^j. Thus, to compute the coefficient of x^k in the expansion, we need to choose x^{l_i} from each factor so that \sum_i l_i=k. But we also know that in the i‘th factor, we have terms of the for j_ip^i. In other words, we simply pick l_i so that \sum_l j_lp^l=k, which is exactly the p-adic representation of k. The coefficient on each of these terms if precisely \binom{n_i}{k_i}, and so taking the product gives the result.

And that’s it! I hope you enjoyed it, and now I’ve got to get back to work!

Advertisements

About Ryan

I'm a software developer at Hudl where I work on awesome software. Before that, I was a grad student in mathematics, interested in probability theory as well as analysis, more on the side of functional analysis and less on the side of PDEs. Apart from that I'm pretty lame. Though I do enjoy watching football, playing golf, and playing the trumpet.
This entry was posted in Asides, Combinatorics. Bookmark the permalink.

One Response to A quick, cool result to distract you from finals

  1. Jay Cummings says:

    It warms my heart that all of you are semi-sorta doing some combinatorics in your respective fields.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s