On the minimal Hamming weight of a multi-base representation

DOI10.1016/J.JNT.2019.07.023zbMATH Open1472.11045arXiv1808.06330OpenAlexW2970327410MaRDI QIDQ2009155FDOQ2009155

Authors: Daniel Krenn, Vorapong Suppakitpaisarn, Stephan Wagner 

Publication date: 27 November 2019

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

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.

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

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

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)

Cites Work

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

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)