# 2-adic valuation of odd harmonic sums

(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]]

• Perhaps it is related to the fact that $n^{2}=1+3+5+...2n-1$ – Sylvain JULIEN Jul 17 '16 at 12:49
• – Alexey Ustinov Jul 20 '16 at 9:05

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}$.

• Cool and elementary proof! Thanks for pointing this nice argument. – cjackal Jul 17 '16 at 13:26
• 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. – Harry Altman Jul 17 '16 at 18:57
• @HarryAltman I neglected to mention that, because of the squaring, we are summing each residue class twice. – Will Sawin Jul 20 '16 at 4:46
• 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}$. – Harry Altman Jul 20 '16 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)$.

• I'm not well understanding Faulhaber polynomials, but way more orderly proof, nice! – cjackal Jul 17 '16 at 14:06