MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\sigma_p(m,n)$ (resp. $\pi_p(m,n)$) denote the sum of the carries when adding (resp. multiplying) the numbers $m=\sum_{k\ge0}m_kp^k$ and $n=\sum_{k\ge0}n_kp^k$ using base-$p$ arithmetic where $m_k,n_k\in\{0,\dots,p-1\}$ for $k\ge0$. Let $s_p(m)=\sum_{k\ge0}m_k$ be the sum of the base-$p$ digits.

Question 1. Does someone know a reference for the following (cohomological) formulas? $$\sigma_p(m,n)=\frac{s_p(m)+s_p(n)-s_p(m+n)}{p-1},\quad \pi_p(m,n)=\frac{s_p(m)s_p(n)-s_p(mn)}{p-1}.$$

Question 2. Does someone know what $\pi_p(m,n)$ counts (besides the number of carries)?

I will happily type my (short) proofs if there is interest, and there is no obvious reference. A famous result of Kummer says that $\sigma_p(m,n)$ is the exponent of the largest power of $p$ dividing $\binom{m+n}{n}$. (The formula for $\pi_p(m,n)$ arose from a problem in finite geometry.)

Edit: Typo corrected ($\alpha$ changed to $\sigma$). Thanks R. Also, replaced `number of carries' with 'sum of carries' as $c_k>1$ happens, see proof below.

share|cite|improve this question
Where did $\alpha$ come from? – R.. Sep 4 '14 at 4:20

In their article "Stolarsky's conjecture and the sum of digits of polynomial values"( ), Hare, Laishram and Stoll show in Proposition 2.2 that the sum of digits is subadditive and submultiplicative. Although the proposition does not contain the formulae you gave, the proof proceeds by giving your formulae, and then concluding with the remark that the number of carries is non-negative.

Can you explain what these equation have to do with cohomology?

share|cite|improve this answer
Thanks Jan-Christoph. Prop 2.2 of the preprint states the formula for $\sigma_p(m,n)$, but not the formula for $\pi_p(m,n)$. (If it did then the proof of $s_p(mn)\le s_p(m)s_p(n)$ would be even shorter.) – Glasby Sep 5 '14 at 1:01
It implicitly does. The displayed formula in their proof has two $\leq$-signs, each of which comes from sub-additivity. If you insert the more precise formula for $\sigma_p(m, n)$ at these places, you get the formula for $\pi_p(m,n)$. – Jan-Christoph Schlage-Puchta Sep 6 '14 at 9:34

I was asked (offline) for a proof of the formula for the sum of the carries $\pi_p(a,b)$ when multiplying $a$ and $b$ in base $p$.

Proof. Multiplying the base-$p$ expansions $a=\sum_{k\ge0}a_kp^k$ and $b=\sum_{k\ge0}b_kp^k$ generates carries $c_0,c_1,\dots$ where $c_k$ is the carry generated by adding multiples of $p^k$. The base-$p$ expansion of the product $ab=\sum_{k\ge0}(ab)_kp^k$ is related to the $a_i$, $b_j$ and $c_k$ via the equations: \begin{align*} (ab)_0&=a_0b_0-pc_0\\ (ab)_1&=a_0b_1+a_1b_0+c_0-pc_1\\ (ab)_2&=a_0b_2+a_1b_1+a_2b_0+c_1-pc_2\\ &\ \vdots \end{align*} where $(ab)_k=\left(\sum_{i+j=k}a_ib_j\right)+c_{k-1}-pc_k$ for $k\ge1$. Adding these equations gives $$ s_p(ab)=\left(\sum_{i\ge0}a_i\right)\left(\sum_{j\ge0}b_j\right) -(p-1)\sum_{k\ge0}c_k=s_p(a)s_p(b)-(p-1)\pi_p(a,b). $$ Rearranging gives the desired formula for $\pi_p(a,b)$. The formula for $\sigma_p(a,b)$ is obtained similarly by adding $(a+b)_0=a_0+b_0-pc_0$ and $(a+b)_k=a_k+b_k+c_{k-1}-pc_k$ for $k\ge1.\ \ \square$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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