3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How do you define the entropy? $\endgroup$ – Gerry Myerson Mar 18 at 8:13
  • $\begingroup$ @GerryMyerson Shannon entropy with base $2$, assuming a uniform distribution for $x$. Edited the question to clarify this. $\endgroup$ – Ethan MacBrough Mar 18 at 8:15
  • $\begingroup$ 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. $\endgroup$ – Peter Taylor Mar 18 at 8:44
  • 1
    $\begingroup$ @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. $\endgroup$ – Ethan MacBrough Mar 18 at 8:50
  • 1
    $\begingroup$ 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? $\endgroup$ – Peter Taylor Mar 18 at 10:27
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.