4
$\begingroup$

Does multiplication increase entropy?

The Shannon entropy of a number $k$ in binary digits is defined as $$ H = -\log(\frac{a}{l})\cdot\frac{a}{l} - \log(1-\frac{a}{l})\cdot (1-\frac{a}{l})$$ where $l = 1+\text{ floor }(\frac{\log(k)}{\log(2)})$ is the number of binary digits of $k$ and $a$ is the number of $1$-s in the binary expansion of $k$. So we view the number $k$ as a "random variable".

Suppose that $n,m$ are uniformly randomly chosen in the interval $1 \le N$.

Hypothesis 1):

$H_{m \cdot n}$ is "significantly" larger then $H_n$.

Hypothesis 2):

$H_{m + n}$ is not "significantly" larger then $H_n$.

Here is some empirical statistical test indicating that multiplication increases entropy, but addition does not:

from collections import Counter

def entropyOfCounter(c):
    S = 0
    for k in c.keys():
        S += c[k]
    prob = []
    for k in c.keys():
        prob.append(c[k]/S)
    H = -sum([ p*log(p,2) for p in prob]).N()
    return H

def HH(l):
    return entropyOfCounter(Counter(l))

N  = 10^4
HN = []
HmXn = []
HmPn = []
for k in range(N):
    n = randint(1,17^50)
    m = randint(1,17^50)
    Hn = HH(Integer(n).digits(2))
    Hm = HH(Integer(m).digits(2))
    HmXn.append(HH(Integer(n*m).digits(2)))
    HmPn.append(HH(Integer(n+m).digits(2)))
    HN.append(Hn)

X = mean(HN)
Y = mean(HmPn)
Z = mean(HmXn)
n = len(HN)
m = n
SX2 = variance(HN)
SY2 = variance(HmPn)
SZ2 = variance(HmXn)
SXY2 = ((n-1)*SX2 + (m-1)*SY2)/(n+m-2)
SXZ2 = ((n-1)*SX2 + (m-1)*SZ2)/(n+m-2)
TXY = sqrt((m*n)/(n+m)).N()*(X-Y)/sqrt(SXY2).N()
TXZ = sqrt((m*n)/(n+m)).N()*(X-Z)/sqrt(SXZ2).N()
print TXY,TXZ,n+m-2

Output: -1.43265218355297 -32.5323306851490 19998

The second case (multiplication) increases entropy significantly. The first case ( addition) does not.

Is there a way to give a heuristic explanation why this is so in general (if it is), or is this empirical obervation in general $1 \le N$ wrong?

Related:

https://math.stackexchange.com/questions/3275096/does-entropy-increase-when-multiplying-two-numbers

https://physics.stackexchange.com/questions/487780/increase-in-entropy-and-integer-factorization-how-much-work-does-one-have-to-do

$\endgroup$
17
  • $\begingroup$ What is underlying behind your definition if you are trying to give meaning to entropy here? $\endgroup$
    – Turbo
    Jun 24, 2019 at 15:46
  • $\begingroup$ @Turbo: see the linked question $\endgroup$
    – user6671
    Jun 24, 2019 at 15:48
  • $\begingroup$ Why the focus on the specific digit $1$? Also, you are using $a$ for two different things. $\endgroup$ Jun 24, 2019 at 16:04
  • 3
    $\begingroup$ (Integer) Multiplication "significantly increases" the number of binary digits, where as addition does not. Perhaps that is what you are seeing. Gerhard "Bigger Feet Means Smarter Kids?" Paseman, 2019.06.24. $\endgroup$ Jun 24, 2019 at 16:25
  • 1
    $\begingroup$ The distribution is skewed by the fact that you consider the digits of $k$ starting from the first occurrence of $1$ onwards, which artificially increases the probability of $1$. Presumably the picture might become clearer if you skip the most-significant digit, or alternatively, if you fix the number of digits in advance and include leading $0$’s in the entropy calculation for shorter $k$’s. $\endgroup$ Jun 25, 2019 at 9:26

1 Answer 1

3
$\begingroup$

Simulations suggest that most of this phenomenon can be explained by bit length (as suggested by Gerhard Paseman). Let $G(k)$ be the expected 'entropy' of a random $k$-bit number (i.e. chosen uniformly from $0\dots 2^k -1$). Of course, on average $H_n = G(k)$. My point is that $H_{n\cdot m}$ is not very distinguishable from $G(2k)$, i.e. the entropy of a random $2k$-bit integer.

If we just plot the average of $H_{n+m}$ and $H_{n\cdot m}$, we seem to observe the phenomenon you mention:

G(k), H_{n+m}, H_{nm}

But now if we compare $H_{n+m}$ to the entropy of random $k+1$ bit integers, and compare $H_{n\cdot m}$ to the entropy of random $2k$ bit integers:

G(k+1), H_{n+m}

G(2k), H_{nm}

So if there's anything interesting to study, it's either (a) for small values of $k$, or (b) why $nm$ has such close entropy to a truly random $2k$-bit number. Here's the same plots for larger $k$.

G(k), H_{n+m}, H_{nm}

G(k+1), H_{n+m}

G(2k), H_{nm}

Code: https://pastebin.com/CdLyhY93

$\endgroup$
1
  • $\begingroup$ thank you for your answer $\endgroup$
    – user6671
    Jun 27, 2019 at 5:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.