10
$\begingroup$

Kummer's formula
https://en.wikipedia.org/w/index.php?title=Kummer%27s_theorem&oldid=745783657 says that $$ \text{ord}_p \binom{n}{k} $$ is the number of carries required when adding the base-$p$ expansions of $k$ and $n-k$. Is there a similar formula for the $p$-adic valuation of a multinomial coefficient $$ \binom{n}{k_1,\ldots,k_r} := \frac{n!}{k_1!\cdots k_r!} ? $$ If so, is there a good reference (free online for preference, but failing that, in a book)?

There is a related question Reference needed for Lucas' Theorem for multinomial coefficients modulo a prime, but it involves the value of the multinomial coefficient modulo $p$, not the $p$-adic valuation.

$\endgroup$
6
  • 7
    $\begingroup$ Isn't it just going to be the total number of carries required when first adding $k_1$ and $k_2$, then adding $k_1+k_2$ and $k_3$, then adding $k_1+k_2+k_3$ and $k_4$, etc.? $\endgroup$ Mar 28, 2017 at 18:08
  • 7
    $\begingroup$ Tom's argument also shows the total number of carries does not depend on the order of summation. If one asked me to prove that last statement, I don't know how one would start without having Joe's question in mind. $\endgroup$ Mar 28, 2017 at 18:21
  • $\begingroup$ If I had to prove the statement @Abdelmalek made regarding order of summation, I would use induction on the number of summands, making sure I did the case of three summands carefully. Gerhard "Is Feeling Rather Recursiony Today" Paseman, 2017.03.28. $\endgroup$ Mar 28, 2017 at 18:31
  • $\begingroup$ @Gerhard: maybe with general Witt vectors? $\endgroup$ Mar 28, 2017 at 18:39
  • 1
    $\begingroup$ Yes, this is just the total carry. Reminds me of the following result due to Steve Doty: When we view the space of homogeneous polynomials of degree $n$ in $r$ variables as a module over $SL_r(\overline{\Bbb{F}_p})$, acting on the variables by linear substitutions, the various carry patters (=which carrys appear at which digit positions) determines the irreducible composition factors. Yours truly had the pleasure of extending and refining (to the extent it was feasible) those results to algebraic groups of types $B,C,D$. $\endgroup$ Feb 4, 2019 at 19:47

2 Answers 2

15
$\begingroup$

Denote the sum of the digits of $n$ in base $b$ by $S(n)$. Then the number of carries when adding $k_1+k_2$ is $$\frac{1}{b-1}\big(S(k_1)+S(k_2)-S(k_1+k_2)\big).$$ This shows that the number of carries when successively adding $(((k_1+k_2)+k_3)+\cdots +k_r)$ is $$\frac{1}{b-1}\left(\sum_{i=1}^r S(k_i)-S\left(\sum_{i=1}^r k_i\right)\right),$$ and this last expression is clearly independent of the order in which they are added. The formula for the multinomial coefficient can thus be written as $$\operatorname{ord}_p \binom{n}{k_1,\ldots,k_r}=\frac{\sum_{i=1}^rS(k_i)-S(n)}{p-1}.$$

$\endgroup$
4
  • 1
    $\begingroup$ Nice! Do you know analogues of Kummer's formula for more exotic integer-valued ratios of factorials as in mathoverflow.net/questions/26336/… ? meaning a relation between order in $p$ and carries when doing arithmetic with arguments of the factorials. $\endgroup$ Mar 28, 2017 at 22:41
  • 3
    $\begingroup$ Using the formula ${\rm ord}_p(n!) = (n - S(n))/(p-1)$, your last formula follows from taking the $p$-adic valuation of each factorial appearing in the multinomial coefficient: $(n - S(n))/(p-1) - \sum_{i=1}^r (k_i - S(k_i))/(p-1)$: since $n = k_1 + \cdots + k_r$, in that difference the $n$ and $\sum k_i$ cancel out. Also it shows the order of subtraction in your formula is backwards: it should be $(\sum_{i=1}^r S(k_i) - S(n))/(p-1)$. $\endgroup$
    – KConrad
    Mar 28, 2017 at 23:05
  • $\begingroup$ @KConrad Thank you! It was backwards, and it's fixed now. $\endgroup$ Mar 28, 2017 at 23:16
  • 3
    $\begingroup$ @GjergjiZaimi I hope you won't mind that I added this formula to the Wikipedia page on Kummer's theorem. $\endgroup$ Mar 29, 2017 at 18:30
6
$\begingroup$

You can write:

$$\binom{n}{k_1,\ldots,k_r} = \frac{n!}{k_1!\cdots k_r!}$$

as:

$$\binom{n}{k_1,\ldots,k_r} = \binom{n}{k_1}\binom{n-k_1}{k_2}\ldots\binom{n-k_1\ldots-k_{r-1}}{k_r}$$

$\endgroup$
3
  • 1
    $\begingroup$ What does this have to do with the question being asked about p-adic valuations? $\endgroup$
    – Yemon Choi
    Mar 28, 2017 at 19:23
  • 3
    $\begingroup$ @YemonChoi; apply $ord_p$ to each component on the RHS $\endgroup$
    – JMP
    Mar 28, 2017 at 19:37
  • 3
    $\begingroup$ this is basically the idea given by Tom in a comment above. $\endgroup$ Mar 28, 2017 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.