11
$\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.

Improve this question
$\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$
    – Tom Goodwillie
    Commented 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$
    – Abdelmalek Abdesselam
    Commented 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$
    – Gerhard Paseman
    Commented Mar 28, 2017 at 18:31
  • $\begingroup$ @Gerhard: maybe with general Witt vectors? $\endgroup$
    – Abdelmalek Abdesselam
    Commented 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$
    – Jyrki Lahtonen
    Commented Feb 4, 2019 at 19:47

2 Answers 2

Reset to default
16
$\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}.$$

Improve this answer
$\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$
    – Abdelmalek Abdesselam
    Commented 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
    Commented Mar 28, 2017 at 23:05
  • $\begingroup$ @KConrad Thank you! It was backwards, and it's fixed now. $\endgroup$
    – Gjergji Zaimi
    Commented 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$
    – Joe Silverman
    Commented 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}$$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .