Are the high-order bits of $n^2$ as likely to be zeroes as ones?

Question

Let $B_i(n)$ be the $i$th bit in the binary expansion of $n$, so that $n=\sum B_i(n)2^i$. Now let $n$ be randomly and uniformly chosen from some large range, and let $E(j)$ be the expected value of $B_j\bigl(n^2\bigr)$, the $j$th bit in the expansion of $n^2$. That is:

$$E(j) = \lim_{M\to\infty} \frac1M \sum_{n=0}^{M-1}B_j\bigl(n^2\bigr)$$

if this limit exists. It is not hard to see that it must exist for any fixed $j$, since the function $B_j\bigl(n^2\bigr)$ is completely determined by the value of $n\bmod 2^{j+1}$, and so is periodic with period at most $2^{j+1}$. In fact we can get rid of the limit:

$$E(j) = \frac1{2^{j+1}} \sum_{n=0}^{2^{j+1}-1}B_j\bigl(n^2\bigr)$$

For example, the first few values of $E$ are $\frac12, 0, \frac14, \frac14$.

Numerical evidence suggests that:

$$\lim_{j\to\infty} E(j) = \frac12$$

Is this true?

Answer 1

According to "Distribution of the figures 0 and 1 in the various orders of binary representation of kth powers of integers", W. Gross and R. Vacca (Mathematics of Computation, April 1968, 22, #102, 423–427), the answer is yes.

On page 423 they define a function $N_k(h)$, which is the count of 1 bits in the $h$th position of the sequence $n^k$ over one of its periods, so my $E(j)$ is exactly $N_2(j)2^{-(j+1)}$. They then show (page 424) that

$$E(j) = \frac12\left(1 - 2^{-\lfloor j/2\rfloor}\right)$$

except for $j=0$. A similar result holds for arbitrary $k$th powers—the density of high-order bits approaches $\frac12$ for all $k$.

Answer 2

By Hensel's lemma, you can show that the nonzero squares in the $2$-adics $\Bbb Z_{(2)}$ are exactly the numbers of the form $4^n(8k+1)$ : the numbers whose binary expansion ends with "001" and an even number of zeroes.

The squares mod $2^j$ are again those numbers. Thus, the number of squares modulo $2^j$ is $1 + 2^{j-3} + 2^{j-5} + \ldots \approx 2^{j-1}/3$.
Out of those squares, those where flipping the $2^{j-1}$ bit doesn't result again in a square are either $0$ or $2^{2k}$ with $j \le 2k+3$, so they are at most $3$, which is negligible compared to all the other squares.