<s>[INST] Entropy of the upper and lower bits of a square number Consider a uniformly random number $x<2^n$. Let $H_{\star}(n)$ denote the (base-$2$ Shannon) entropy of the first $n$ bits of $x^2$, and let $H^{\star}(n)$ denote the entropy of the rest of the bits of $x^2$. In other words, writing $x^2 = q2^n + r$ with $r<2^n$, $H_{\star}(n)$ denotes the entropy of $r$ while $H^{\star}(n)$ denotes the entropy of $q$.
From numerical experiments up to $n=25$ it seems as though
$$
H_{\star}(n)=\left\{
  \begin{array}{@{}ll@{}}
    n + 2^{(4 - n)/2} - 3, & \text{if}\ n\equiv0\mod2 \\
    n + 3\cdot2^{(1 - n)/2} - 3, & \text{if}\ n\equiv1\mod2
  \end{array}\right.
$$
I don't have an exact expression for $H^{\star}(n)$, but it seems as though (for $n>1$), $H^{\star}(n)>n-\frac{3}{4}$, and $H^{\star}(n)$ approaches $n-\frac{3}{4}$ as $n$ gets larger.
Unfortunately I'm totally at a loss about how to prove these statements in general, and my experimentation program can't go higher because of the exponential blow-up in memory use. Do these results hold in general, and if so does anyone know how to prove them? Also is there a more exact expression for $H^{\star}(n)$?
 [/INST] With help from Peter Taylor's comment, I was able to prove the expression for $H_{\star}(n)$. I believe the approximation for $H^{\star}(n)$ could also be proven by noting that for $x>2^{n/2}$, $\sqrt{x^2-2^{n-1}}\leqslant \sqrt{q}$ or $\sqrt{q}\leqslant\sqrt{x^2+2^{n-1}}$, and then expanding these bounds as Taylor series to show that most of the higher bits of $\sqrt{q}$ are the same as the higher bits of $x$, hence the entropy of $q$ must be nearly the same as the entropy of $x$. Unfortunately the argument seems to get pretty messy so I have yet to formalize it.
Let $(x,y)$ denote the greatest common divisor of $x$ and $y$. The proof of the expression for $H_{\star}(n)$ relies on the following proposition.
Proposition. For two numbers $x,y$ with $(x,2^n)=2^m$, $x^2\equiv y^2 \mod 2^n$ iff $x\equiv\pm y\mod 2^{n-\min\{m+1,\lfloor n/2\rfloor\}}$.
proof. First suppose $(x,2^n)=2^m$ and $x\equiv\pm y\mod 2^{n-\min\{m+1,\lfloor n/2\rfloor\}}$, so that we can write $x=i2^m$ and $y = x+ k2^{n-\min\{m+1,\lfloor n/2\rfloor\}}$. Then
\begin{align}
y^2 &= \left(x+ k2^{n-\min\{m+1,\lfloor n/2\rfloor\}}\right)^2\\
&= x^2 + 2kx2^{n-\min\{m+1,\lfloor n/2\rfloor\}} + k^22^{2\left(n-\min\{m+1,\lfloor n/2\rfloor\}\right)}\\
&= x^2 + kj2^{n+m+1-\min\{m+1,\lfloor n/2\rfloor\}} + k^22^{n+\left(n-\min\{2m+2,2\lfloor n/2\rfloor\}\right)}\\
&\equiv x^2 \mod 2^n.
\end{align}
Now suppose $(x,2^n)=2^m$ and $x^2\equiv y^2 \mod 2^n$. Then $2^n|(x+y)(x-y)$. Certainly it must be the case that $2^{\lceil n/2 \rceil}=2^{n-\lfloor n/2 \rfloor}$ divides one of these terms. Now suppose $2^{m+2}$ divides both of these terms. Then we would also have $2^{m+2}|(x+y)+(x-y)=2x$, so $2^{m+1}|x$ contradicting our assumptions. Thus $2^{n-(m+1)}$ must divide either $(x+y)$ or $(x-y)$. Since $2^{n-\min\{m+1,\lfloor n/2\rfloor\}}$ equals either $2^{n-(m+1)}$ or $2^{n-\lfloor n/2 \rfloor}$, we in particular have $2^{n-\min\{m+1,\lfloor n/2\rfloor\}}$ divides $(x+y)$ or $(x-y)$, i.e. $x=\pm y\mod 2^{n-\min\{m+1,\lfloor n/2\rfloor\}}$.$$\tag*{$\blacksquare$}$$
Now back to the original problem.
\begin{align}
H_{\star}(n) &= -\frac{1}{2^n}\sum_{x=0}^{2^n-1}\log_2\left(\frac{\#\{x:x^2\equiv y^2\mod 2^n\}}{2^n}\right)\\
&=-\frac{1}{2^n}\sum_{x=0}^{2^n-1}\log_2\left(2^{\min\{\log_2((x,2^n))+1,\lfloor n/2\rfloor\}-n}\cdot\left[x\equiv 0\mod 2^{n-\min\{\log_2((x,2^n))+1,\lfloor n/2\rfloor\}}?\,1:2\right]\right)\\
&=-\frac{1}{2^n}\sum_{x=0}^{2^n-1}\log_2\left(2^{\min\{\log_2((x,2^n))+2,\lfloor n/2\rfloor\}-n}\right)\\
&=\frac{1}{2^n}\sum_{x=0}^{2^n-1}\left(n-\min\{\log_2((x,2^n))+2,\lfloor n/2\rfloor\}\right)\\
&=n-\frac{1}{2^n}\sum_{x=0}^{2^n-1}\min\{\log_2((x,2^n))+2,\lfloor n/2\rfloor\}.
\end{align}
Since the number of values less than $2^n$ for which $2^m|x$ is exactly $2^{n-m}$, the sum restricted to the $x$'s such that $(x,2^n)=2^m$ with $m+2\leqslant \lfloor n/2\rfloor$ is just $(m+2)(n^{n-m}-2^{n-m-1})=(m+2)2^{n-m-1}$. Thus we get
\begin{align}
H_{\star}(n) &=n-\sum_{m=0}^{\lfloor n/2\rfloor-2}\frac{m+2}{2^{m+1}}-\lfloor n/2\rfloor2^{-\lfloor n/2\rfloor+1}.
\end{align}
From there a simple computation suffices to show the formula I gave originally is correct.
</s>