Browsing by Author "Krenn, Daniel"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Canonical trees, compact prefix-free codes, and sums of unit fractions: a probabilistic analysis
    (SIAM, 2015) Heuberger, Clemens; Krenn, Daniel; Wagner, Stephan
    For fixed t ≥ 2, we consider the class of representations of 1 as a sum of unit fractions whose denominators are powers of t, or equivalently the class of canonical compact t-ary Huffman codes, or equivalently rooted t-ary plane “canonical” trees. We study the probabilistic behavior of the height (limit distribution is shown to be normal), the number of distinct summands (normal distribution), the path length (normal distribution), the width (main term of the expectation and concentration property), and the number of leaves at maximum distance from the root (discrete distribution).
  • Thumbnail Image
    Item
    On the minimal Hamming weight of a multi-base representation
    (Elsevier, 2020) Krenn, Daniel; Suppakitpaisarn, Vorapong; Wagner, Stephan
    Given a finite set of bases b1, b2, ..., br (integers greater than 1), a multi-base representation of an integer n is a sum with summands dbα1 1 b α2 2 ··· bαr r , where the αj are nonnegative integers and the digits d are taken from a fixed finite set. We consider multi-base representations with at least two bases that are multiplicatively independent. Our main result states that the order of magnitude of the minimal Hamming weight of an integer n, i.e., the minimal number of nonzero summands in a representation of n, is log n/(log log n). This is independent of the number of bases, the bases themselves, and the digit set. For the proof, the existing upper bound for prime bases is generalized to multiplicatively independent bases; for the required analysis of the natural greedy algorithm, an auxiliary result in Diophantine approximation is derived. The lower bound follows by a counting argument and alternatively by using communication complexity; thereby improving the existing bounds and closing the gap in the order of magnitude.