5
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ $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. $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 11, 2016 at 18:36
  • $\begingroup$ 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... $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 11, 2016 at 18:42
  • $\begingroup$ 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 :-) $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 11, 2016 at 19:08
  • $\begingroup$ @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. $\endgroup$
    – Jack D'Aurizio
    Commented Jul 11, 2016 at 19:12
  • $\begingroup$ A reference is mathworld.wolfram.com/SparsePolynomialSquare.html $\endgroup$
    – Jack D'Aurizio
    Commented Jul 11, 2016 at 19:14

1 Answer 1

Reset to default
5
$\begingroup$

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

  1. Yes.
  2. No.
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 11, 2016 at 19:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .