The Average Amount of Information Lost in Multiplication

DOI10.1109/TIT.2004.840866zbMATH Open1307.94022arXivmath/0408043OpenAlexW2115223783MaRDI QIDQ3547490FDOQ3547490

Authors: Nicholas Pippenger 

Publication date: 21 December 2008

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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 | 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.

Full work available at URL: https://arxiv.org/abs/math/0408043

Recommendations

• Information Distance in Multiples
• The complexity of iterated multiplication
• The distributions of individual bits in the output of multiplicative operations
• scientific article; zbMATH DE number 3601518
• Information amount and higher-order efficiency in estimation
• scientific article; zbMATH DE number 3623433
• scientific article; zbMATH DE number 3916433
• scientific article

zbMATH Keywords

entropymultiplierequivocationmultiplicative channel

Mathematics Subject Classification ID

Information theory (general) (94A15) Combinatorial probability (60C05)

Cited In (2)

• Emulating primality with multiset representations of natural numbers
• Towards a generic view of primality through multiset decompositions of natural numbers

This page was built for publication: The Average Amount of Information Lost in Multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3547490)