9
$\begingroup$

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.

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

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2016 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, 2016 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, 2016 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, 2016 at 4:32
3
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2013 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.