The average amount of information lost in multiplication
| dc.creator | Pippenger, Nicholas | |
| dc.date | 2004-08-03 | |
| dc.date.accessioned | 2026-07-07T05:10:59Z | |
| dc.date.available | 2026-07-07T05:10:59Z | |
| dc.description | 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 | XY)), is of order 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 | XY) = 0 implies that 2log_2 N - H(X, Y) is of order at least 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 | XY) = 0 with log_2 N - H(X) and log_2 N - H(Y) each of order at most log log N. Second, we show that however X and Y are distributed, H(X,Y | XY) is of order at most 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 H(X,Y | XY) is of order log log N. | |
| dc.description | i+11 pp | |
| dc.identifier | https://arxiv.org/abs/math/0408043 | |
| dc.identifier | http://arxiv.org/abs/math/0408043 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/72098 | |
| dc.subject | Probability | |
| dc.subject | 94A15 | |
| dc.title | The average amount of information lost in multiplication | |
| dc.type | text |