ITEM VIEW

On the minimal Hamming weight of a multi-base representation

dc.contributor.authorKrenn, Danielen_ZA
dc.contributor.authorSuppakitpaisarn, Vorapongen_ZA
dc.contributor.authorWagner, Stephanen_ZA
dc.date.accessioned2023-01-19T07:50:33Z
dc.date.available2023-01-19T07:50:33Z
dc.date.issued2020
dc.identifier.citationKrenn, 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.
dc.identifier.issn1096-1658 (online)
dc.identifier.issn0022-314X (print)
dc.identifier.otherdoi:10.1016/j.jnt.2019.07.023
dc.identifier.urihttp://hdl.handle.net/10019.1/126249
dc.descriptionCITATION: 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.
dc.descriptionThe original publication is available at https://www.sciencedirect.com
dc.description.abstractGiven 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.en_ZA
dc.description.sponsorshipAustrian Science Fund
dc.description.urihttps://www.sciencedirect.com/science/article/pii/S0022314X19302768
dc.format.extent12 pagesen_ZA
dc.language.isoen_ZAen_ZA
dc.publisherElsevier
dc.subjectHamming weighten_ZA
dc.subjectMulti-base representationsen_ZA
dc.subjectMinimal weighten_ZA
dc.subjectInteger programming -- Mathematical modelsen_ZA
dc.titleOn the minimal Hamming weight of a multi-base representationen_ZA
dc.typeArticleen_ZA
dc.description.versionPublisher's version
dc.rights.holderAuthors retain copyright


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

ITEM VIEW