5
$\begingroup$

Let P(x) be a polynomial of degree n. Let H(i) represent the number of 1's in the binary expansion of the integer i. Although reasonably easy to prove, it may seem surprising that the following identity holds:

$\sum_{i=0}^{2^{n+1}-1} (-1)^{H(i)}P(i) = 0$

This was asked here on the "Complex Projective 4-Space" blog by apgoucher.

|cite|improve this question
$\endgroup$
  • $\begingroup$ This question has been handled in Math.SE at least here. I have seen the result in a number theory book. My copy of that book is in my office (if not with a student), so can't check before Monday, whether the author attributes the theorem to somebody. IOW, I'm not sure that coding theory is the best tag for this. $\endgroup$ – Jyrki Lahtonen Aug 23 '13 at 18:44
  • $\begingroup$ I added "coding theory" because apgoucher titled his post "Polynomials and Hamming Weights". $\endgroup$ – Ross Presser Aug 24 '13 at 19:28
  • 1
    $\begingroup$ There has to be a typo in the summation. The range should be either from $0$ to $2^{n+1}-1$ or from $1$ to $2^{n+1}$. Both work, I think. $\endgroup$ – Jyrki Lahtonen Aug 26 '13 at 7:35
  • $\begingroup$ You are correct, the lower bound is zero. I will fix it. $\endgroup$ – Ross Presser Aug 26 '13 at 20:41
3
$\begingroup$

I don't know if the theorem has a name. I found the result (with variations) from the very nice book Elementary Number Theory - A Problem Oriented Approach written in beautiful calligraphy by Joe Roberts, p. 88 to be precise. I warmly recommend that book to aspiring students from high school age and up.

Anyway, he indicates that the result was first published by M.E. Prouhet in an article titled Mémoire sur quelques relations entre les puissances des nombres that appeared in Comptes Rendus in 1851.

|cite|improve this answer
$\endgroup$

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.