Let $p$ be an odd prime. Then if $1<n<r$, $$p^{r-n}\,\left|\,\binom{p^{r-2}}{n}\right.$$ Does anyone have a clever combinatorial proof of this fact? There's an easy argument just by counting multiples of $p$ (with multiplicity) in the numerator and denominator, but it feels a bit clumsy, and this sort of thing ought to have a more elegant argument.

This problem arises naturally when looking at the structure of groups of the form $(\mathbb{Z}/n)^*$, which is why I've posted the above problem with what appears to be a stronger-than-necessary hypothesis and what is certainly a weaker-than-necessary conclusion.

  • $\begingroup$ I changed the $p^r$ in the title to $p^{r-n}$ as in the body. Please verify that this is correct. $\endgroup$ – Alex Becker Jan 29 '13 at 5:42
  • $\begingroup$ @AlexBecker It is, thank you. $\endgroup$ – Brett Frankel Jan 29 '13 at 5:45
  • $\begingroup$ There goes 20 minutes trying to induct on $n$ and then $r$... $\endgroup$ – tacos_tacos_tacos Jan 29 '13 at 6:34
  • $\begingroup$ It appears I've been downvoted. I'd be interested in knowing why. $\endgroup$ – Brett Frankel Jan 30 '13 at 1:02

First, let $n = mp^{k}$ with $p^k$ the highest power of $p$ dividing $n$. I claim that $r-2-k \ge r-n$. Indeed, this is the requirement that $n\ge 2+k$. This can be proven using induction on $k$, starting from the base case of $k=1$ when $m=1$, and from $k=0$ when $m>1$.

Let $G = (\mathbb{Z}_p)^{r-2}$, and let $S$ denote the set of $n$ element subsets of $G$. Then $|S| = {p^{r-2} \choose n}$. Let $G$ act on $S$ by translation. That is, for $s \in S$, $s$ is some subset $\{g_1,\dots,g_n\} \subseteq G$. We define the action of $g \in G$ by $gs = \{g+ g_1,\dots,g+g_n\}$.

For any given $s \in S$, the size of the stabilizer $G_s$ must divide $n$. Indeed, since $G_s s = s$, we can think of $G_s$ as actually acting on the set $s = \{g_1,\dots,g_n\}$ by translation. Since $G_s$ acts freely, we see that $|G_s|$ divides $|s| = n$. Moreover, since $|G_s|$ must divide $|G| = p^{r-2}$, $|G_s|$ must be a power of $p$. So $|G_s|$ is a power of $p$ dividing $n=mp^k$, so in fact it divides $p^k$.

Now we can look at the size of the orbits of $S$ using the orbit-stabilizer theorem. Since the size of every stabilizer $G_s$ divides $p^k$, the size of every orbit must be a multiple of $|G|/p^k = p^{r-2-k}$. Since $r-n \le r-2-k$, we have that $p^{r-n}$ divides the order of every orbit. $|S|$ is a union of all the orbits, so $p^{r-n}$ must also divide $|S| = {p^{r-2} \choose n}$, and the proof is complete.

  • $\begingroup$ Why can't $S$ have more than k independent stabilizers? I don't get "$S$ is a disjoint union of orbits of its own stabilizer". (If $v \in G$ stabilizes $S$, so $v+S=S$, its orbit $G+v$ is not contained in $S$, so what does this sentence mean?) $\endgroup$ – Emolga Jan 24 '16 at 18:41
  • 1
    $\begingroup$ @Leullame Did a big rewrite, let me know if you still have questions. Hopefully I'm better at writing math these days. $\endgroup$ – Carl Jan 29 '16 at 19:25
  • 1
    $\begingroup$ Thank you very much for your effort. I don't see why $G_s$ acts transitively on $s$; for given $g_i,g_j \in s$, the element sending $g_i$ to $g_j$ is $g_j-g_i$ which is not necessarily in $G_s$. Furthermore, being transitive seems to imply the reverse direction: $n \big| |G_s|$. However, thanks to your explanations I think the original wording shows $|G_s| \big| n$: for each $g_i \in s$, the stabilizer of $g_i$ is $0$, since we require $g+g_i=g_i$. Thus the orbit of $g_i$ is of size $|G_s|$, and $s$ is a disjoint union of orbits, each of size $G_s$. Hence $n=|s|$ is divisible by $|G_s|$. $\endgroup$ – Emolga Jan 30 '16 at 20:58
  • 1
    $\begingroup$ @Leullame Thanks, you're right.. I changed the word "transitively" to "freely", and that is probably what I meant by that "union of the orbits of its stabilizer" line. $\endgroup$ – Carl Feb 1 '16 at 4:32

There is a nice result of Kummer that says that if $p^e$ is the highest power of the prime $p$ which divides $\dbinom{a}{b}$, then $e$ equals the number of carries in the sum $b + (a-b) = a$, where $b, a-b, a$ are written in base $p$.

So in your case it seems to me that you have only to show that $n < p^{n-1}$ (which guarantees that you will need at least $r - n$ carries when doing the sum $n + (p^{r-2} - n)$ in base $p$), and this holds indeed for $n > 1$ and $p$ odd.

  • $\begingroup$ Another way of saying this is $$e=\frac{\sigma_p(b)+\sigma_p(a-b)-\sigma_p(a)}{p-1}$$ where $\sigma_p(n)$ is the sum of the digits in the base-$p$ representation of $n$. $\endgroup$ – robjohn Feb 4 '13 at 1:06

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.