The average amount of information lost in multiplication
We show that if X and Y are integers independently and uniformly distributed in the set {1,..., N}, then the information lost in forming their product (which is given by the equivocation H(X, Y \ X . Y)), is Theta(log log N). We also prove two extremal results regarding cases in which X and Y are not necessarily independently or uniformly distributed. First, we note that the information lost in multiplication can of course be 0. We show that the condition H(X, Y \ X . Y) = 0 implies 2 log(2) N-H(X, Y) = Omega(log log N). Furthermore, if X and Y are independent and uniformly distributed on disjoint sets of primes, it is possible to have H(X, Y \ X . Y) = 0 with log(2) N - H(X) and log(2) N - H(Y) each O(log log N). Second, we show that no matter how X and Y are distributed, H(X, Y \ X . Y) = O(log N/ log log N). Furthermore, there are distributions (in which X and Y are independent and uniformly distributed over sets of numbers having only small and distinct prime factors) for which we have H(X, Y \ X . Y) = Omega(log N/ log log N).
equivocation entropy multiplicative channel multiplier