(This question is cross-posted on math.stackexchange)

I'm playing with p-adic valuations, and find that the odd harmonic sums, $\tilde{H}_k=\sum_{i=1}^{k}\frac{1}{2i-1}$, has 2-adic valuation $||k^2||_2=2||k||_2$.

E.g.) $\tilde{H}_4=\frac{176}{85}$ has $||\tilde{H}_4||_2=||176||_2=4=2||4||_2$.

$\tilde{H}_6=\frac{6508}{3465}$ has $||\tilde{H}_6||_2=2$. $||\tilde{H}_8||_2=||\frac{91072}{45045}||_2=6$. $\cdots$

How can I prove this?

(Some simple observation I have tried: As $||H_k||_2 =-r$ for $2^r\leq k <2^{r+1}$, $||H_k||_2=||H_{2k}||_2+1=||\frac{1}{2}H_k||_2$. Thus ultrametric ineq for $\tilde{H}_k=H_{2k}-\frac{1}{2}H_k$ doesn't help at all, yielding trivial result $\tilde{H}_k\in \mathbb{Z}_2$.)

(That $||\tilde{H}_k||_2=2||k||_2$ for odd $k$ is almost trivial, so the problem can be reduced to show $||\tilde{H}_{2k}||_2=||\tilde{H}_k||_2+2$, still have no idea)

(I've checked this holds up to $\sim 1000$ using Mathematica, and Mathematica spits the result almost immediately for $n\sim 1000$ and takes about a minute for $n\sim 10000$. )

For anyone interested : I've used the following Mathematica code, try it yourself

a = Table[ IntegerExponent[ Numerator[HarmonicNumber[2 n] - HarmonicNumber[n]/2], 2]/2, {n, 10000}]; b = Table [IntegerExponent[n, 2], {n, 10000}]; NonNegative[Min[a - b]]


2 Answers 2


It is sufficient to prove this result for the sum where $i$ ranges from $m 2^n + 1$ to $(m+1)2^n$. That is because $\tilde{H}_k$ is a sum of an odd number of terms of this form with $n= ||k||_2$, so if they all have $2$-adic valuation $2||k||_2$ then $\tilde{H}_k$ does as well.

To that end, consider what happens to the sum if we decrease each $i$ by $2^{n-1}$. That is the same as decreasing the denominator $1/(2i-1)$ by $2^n$.

$1/x - 1/(x-2^n) = 2^n/( x^2)+2^{2n}/( x^3) + \dots$

The terms with a factor of $2^{3n}$ or more are irrelevant, as is the $2^{2n}$ term because the sum over all odd numbers in an interval of length $2^n$ of $1/x$ is clearly even.

Now in $\sum_{i=r}^{r+2^n-1} \frac{2^n}{ (2i-1)^2}$, $1/(2i-1)$ ranges over all odd residue classes modulo $2^{n+1}$, so its square ranges over all residue classes modulo $2^{n+2}$ that are congruent to $1$ mod $8$, hitting each one twice. The sum of all those residue classes is $2^n + 16 \binom{2^{n-1}}{2} \equiv 2^n$ mod $2^{n+1}$. So the sum is $2^{2n}$ mod $2^{2n+1}$.

After performing this decrease an odd number of times, we are left with $\sum_{i=-2^{n-1}+1}^{i=2^{n-1}} \frac{1}{2i-1}=0$ because the positive and negative terms cancel.

Hence the original sum is $2^{2n}$ mod $2^{2n+1}$.

  • $\begingroup$ Cool and elementary proof! Thanks for pointing this nice argument. $\endgroup$
    – cjackal
    Jul 17, 2016 at 13:26
  • $\begingroup$ I'm confused about something here -- in the sum over congruence classes that are 1 mod 8, we're adding up $2^{n-1}$ terms, right? So shouldn't it be $2^{n-1}+8\binom{2^{n-1}}{2}$? Which doesn't seem to yield the same result. $\endgroup$ Jul 17, 2016 at 18:57
  • $\begingroup$ @HarryAltman I neglected to mention that, because of the squaring, we are summing each residue class twice. $\endgroup$
    – Will Sawin
    Jul 20, 2016 at 4:46
  • $\begingroup$ I see, thanks! And it would be four times, except we're starting just with each odd residue class mod $2^{n+1}$ rather than $2^{n+2}$. $\endgroup$ Jul 20, 2016 at 17:36

Here is a more direct approach. We split the sum into $$ -\tilde{H}_k = \sum_{i=1}^{k} \frac{1}{1-2i} = \sum_{i=1}^{k} \frac{1}{1-4i^2} + \sum_{i=1}^{k} \frac{2i}{1-4i^2}. $$

The first sum can be computed as $$ \sum_{i=1}^{k} \frac{1}{1-4i^2} = \frac{1}{2} \sum_{i=1}^{k} \frac{1}{1-2i} - \frac{1}{-1-2i} = \frac{1}{-2} - \frac{1}{-2-4k} = -\frac{k}{2k+1}. $$

To compute the second sum, we expand the fraction in $\mathbb{Z}_{2}$: $$\sum_{i=1}^{k} \frac{2i}{1-4i^2} = 2 \sum_{i=1}^{k} i + 2^3 \sum_{i=1}^{k} i^3 + 2^5 \sum_{i=1}^{k} i^5 + 2^7 \sum_{i=1}^{k} i^7 + \cdots. $$ Because all the Faulhaber polynomials have odd denominator, for each odd $p \ge 3$ the sum $\sum_{i=1}^{k} i^p$ has $2$-adic valuation at least $\nu_2(k^2) - 2$. Hence all terms except for the first one has valuation strictly greater than $k^2$.

Hence $$ -\tilde{H}_k = -\frac{k}{2k+1} + k^2 + k = \frac{2k^3 + 3k^2}{2k+1} + (\text{even multiple of } k^2) $$ has $2$-adic valuation exactly $\nu_2(k^2)$.

  • $\begingroup$ I'm not well understanding Faulhaber polynomials, but way more orderly proof, nice! $\endgroup$
    – cjackal
    Jul 17, 2016 at 14: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.