# 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)$$?

• How do you define the entropy? – Gerry Myerson Mar 18 at 8:13
• @GerryMyerson Shannon entropy with base $2$, assuming a uniform distribution for $x$. Edited the question to clarify this. – Ethan MacBrough Mar 18 at 8:15
• Re "experimentation program can't go higher because of the exponential blow-up in memory use", n=28 with a 32-bit count per value should use 1GB and be feasible on any home PC from the past few years. You can go further by trading memory for time: e.g. split r into 8 bits and n-8 bits and go 256 time round a loop where you filter to those values of x which give a fixed value in the 8 bits, accumulating counts for the n-8 bits. This can be parallelised if you want to spend some money to get the results sooner. – Peter Taylor Mar 18 at 8:44
• @PeterTaylor I was being a bit loose. My program actually went up to $n=26$ and then crashed while working on $n=27$, presumably because node.js was set to only use 512MB. I agree I could probably get up to $n=35$ or so with sufficient effort, but it doesn't seem worth it to gain a couple more data points. – Ethan MacBrough Mar 18 at 8:50
• Throwing out an idea which I won't have time to work on in the next eight hours: for the lower bits look at the frequency table. The number of results which occur exactly 4 times goes 1,2,4,6,8,16,32,64,... from n=4. The number which occur exactly 8 times follows the same sequence from n=6. Exactly 16 times, from n=8, etc. Proof by induction? – Peter Taylor Mar 18 at 10:27

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.