On the minimal Hamming weight of a multi-base representation

DOI10.1016/J.JNT.2019.07.023MaRDI QIDQ2009155zbMATH OpenOpenAlexFDO

Authors Daniel Krenn, Vorapong Suppakitpaisarn, Stephan Wagner

Publication date 27 November 2019

Published in Journal of Number Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Hamming weightminimal weightmulti-base representations

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Information theory (general) (94A15) Radix representation; digital problems (11A63) Diophantine inequalities (11J25)

Abstract: Given a finite set of bases $b_1$, $b_2$, dots, $b_r$ (integers greater than $1$), a multi-base representation of an integer~$n$ is a sum with summands $d{b}_1^{alph{a}_1}{b}_2^{alph{a}_2}cdots{b}_r^{alph{a}_r}$, where the $alph{a}_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 $logn/(loglogn)$. 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. This implies also that the greedy algorithm terminates after $mathcalO(logn/loglogn)$ steps, and that this bound is sharp.

Recommendations

• On the number of multi-base representations of an integer
• Multi-base representations of integers: asymptotic enumeration and central limit theorems
• Redundancy of minimal weight expansions in Pisot bases
• Minimal weight expansions in Pisot bases
• Minimal expansions in redundant number systems and shortest paths in graphs

Cites work

• scientific article; zbMATH DE number 47603 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• scientific article; zbMATH DE number 3443726 (Why is no real title available?)
• scientific article; zbMATH DE number 3193698 (Why is no real title available?)
• An algorithm for modular exponentiation.
• Analysis of the sliding window powering algorithm
• Communication Complexity
• Diophantine approximation, Ostrowski numeration and the double-base number system
• Effective irrationality measures for quotients of logarithms of rational numbers
• Efficient arithmetic on Koblitz curves
• Extending Scalar Multiplication Using Double Bases
• Lower bounds on the lengths of double-base representations
• Minimality and other properties of the width-𝑤 nonadjacent form
• Multi-base representations of integers: asymptotic enumeration and central limit theorems
• On the expansion length of triple-base number systems
• On the number of multi-base representations of an integer
• On the number of non-zero digits of integers in multi-base representations
• On the number of optimal base 2 representations of integers
• Optimality of the width-w non-adjacent form: general characterisation and the case of imaginary quadratic bases
• Representing integers as sums or differences of general power products
• Speeding up the computations on an elliptic curve using addition-subtraction chains
• Summatory functions of digital sums occurring in cryptography
• The double-base number system and its application to elliptic curve cryptography
• Three distance theorems and combinatorics on words
• Unbalanced digit sets and the closest choice strategy for minimal weight integer representations

Cited in

(5)

• Multi-base representations of integers: asymptotic enumeration and central limit theorems
• Minimal expansions in redundant number systems and shortest paths in graphs
• Finding Hamming weights without looking at truth tables
• Tight lower bound for average number of terms in optimal double-base number system using information-theoretic tools
• Analysis of low Hamming weight products

This page was built for publication: On the minimal Hamming weight of a multi-base representation

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