On the minimal Hamming weight of a multi-base representation
Date
2020
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Abstract
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.
Description
CITATION: Krenn, D., Suppakitpaisarn, V. & Wagner, S. 2020. On the minimal Hamming weight of a multi-base representation. Journal of Number Theory, 208:168–179, doi:10.1016/j.jnt.2019.07.023.
The original publication is available at https://www.sciencedirect.com
The original publication is available at https://www.sciencedirect.com
Keywords
Hamming weight, Multi-base representations, Minimal weight, Integer programming -- Mathematical models
Citation
Krenn, D., Suppakitpaisarn, V. & Wagner, S. 2020. On the minimal Hamming weight of a multi-base representation. Journal of Number Theory, 208:168–179, doi:10.1016/j.jnt.2019.07.023.