3

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

BHT
  • 2,215
  • How do you define the entropy? – Gerry Myerson Mar 18 '19 at 08:13
  • @GerryMyerson Shannon entropy with base $2$, assuming a uniform distribution for $x$. Edited the question to clarify this. – BHT Mar 18 '19 at 08: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 '19 at 08:44
  • 1
    @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. – BHT Mar 18 '19 at 08:50
  • If you look at $x=x_n|x_{n-1}|\dots|x_1$, that is the binary representation of $x$, then the $x_i$ are i.i.d. Bernouli random variables. expending what $x^2$ is in binary you may obtain a nice relation, for example the last 3 bits of $x^2$ are $x_2|0|x_1$, the pattern is not just $0$ and bits from $x$ but there seems to be a pattern and if you can find it, then the entropy of the last $n$ bits is essentially the amount of bits that are linearly independent in the pattern you obtain for the last $n$ bits, the same happens for the first bits. Unfortunately I could not find the pattern right awa – P. Quinton Mar 18 '19 at 09:31
  • @P.Quinton I believe the 3rd smallest bit of $x^2$ is actually $x_2\wedge\neg x_1$, which is why the entropy of the first $3$ bits is $1.5$ rather than $2$. I did try writing out boolean expressions for the first $5$ bits, but I couldn't get a good handle on the behavior. – BHT Mar 18 '19 at 09:39
  • 1
    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 '19 at 10:27

1 Answers1

1

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.

BHT
  • 2,215