#### Title

The Average Amount of Information Lost in Multiplication

#### Document Type

Article

#### Department

Mathematics (HMC)

#### Publication Date

2-2005

#### Abstract

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|XmiddotY)), is Theta(loglogN). 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|XmiddotY)=0 implies 2log_{2}N-H(X,Y)=Omega(loglogN). Furthermore, if X and Y are independent and uniformly distributed on disjoint sets of primes, it is possible to have H(X,Y|XmiddotY)=0 with log_{2}N-H(X) and log_{2}N-H(Y) each O(loglogN). Second, we show that no matter how X and Y are distributed, H(X,Y|XmiddotY)=O(logN/loglogN). 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|XmiddotY)=Omega(logN/loglogN)

#### Rights Information

© 2005 IEEE

#### DOI

10.1109/TIT.2004.840866

#### Recommended Citation

Pippenger, N.; , "The average amount of information lost in multiplication," Information Theory, IEEE Transactions on , vol.51, no.2, pp.684-687, Feb. 2005