# A simple question about the Hamming weight of a square

Let we define the Hamming weight $H(n)$ of $n\in\mathbb{N}^*$ as the number of $1$s in the binary representation of $n$. Two questions:

1. Is it possible that $H(n^2)<H(n)$ ?
2. If so, is there an absolute upper bound for $H(n)-H(n^2)$?

It is interesting to point out that, quite non-trivially, the answers to the same questions for polynomials $\in\mathbb{R}[x]$, with the Hamming weigth being replaced by the number of non-zero coefficients, are yes and no, but I am inclined to believe that the situation for the Hamming weigth is radically different, due to the non-negativity of coefficients. What are your thoughts about it?

• $n=23$ is the smallest example with $H(23)=4>3=H(23^2)$. A minute with Mathematica tells me that $H(479)-H(479^2)=3$, and that is the largest value when $n\le1000$. Also achieved when $n=958=2\cdot479$ (D'uh!) and when $n=959$. I think that this may be due to the fact that $479=2^9-2^5-2^0$, and $23=2^5-2^3-2^0$. A promising pattern worth a closer look I think. Commented Jul 11, 2016 at 18:36
• With $n=1983=2^{11}-2^6-2^0$ we get $H(n)-H(n^2)=4$. It may be too early to conjecture, but... Commented Jul 11, 2016 at 18:42
• Jack, the carries make the game with $H(n^2)$ interesting also. Can you outline what happens with polynomials? That may turn out to be the even more interesting variant :-) Commented Jul 11, 2016 at 19:08
• @JyrkiLahtonen: with polynomials, we may consider a truncation of the Taylor series of $\sqrt{1\pm x}$ around $x=0$. That gives a class of polynomials such that $H(p^2)=H(p)+1$. With some tweaking we may reach $H(p^2)=H(p)$, too, and with a tensor trick we may establish what I wrote above. Commented Jul 11, 2016 at 19:12
• A reference is mathworld.wolfram.com/SparsePolynomialSquare.html Commented Jul 11, 2016 at 19:14

Let $n_k=2^{2k-1}-2^k-1$. We have $$H(2^{2k-1}-2^k-1)=2k-2,$$ because we flip one of the $2k-1$ ones of $2^{2k-1}-1$ to a zero.
On the other hand $$n_k^2=2^{4k-2}-2^{3k}+2^{k+1}+1.$$ Here the integer $m_k=2^{4k-2}-2^{3k}$ has Hamming weight $k-2$, so $H(n_k^2)=k$.
Therefore $$H(n_k)-H(n_k^2)=k-2,$$ and the answers are
• OEIS gives this interesting hit. I missed the value $n=1471$ as the smallest $n$ with $H(n)-H(n^2)=4$. That sequence looks at the ratios of Hamming weights, and there may be much more to this than what we get with my sequence. Commented Jul 11, 2016 at 19:36