The Hamming weight of the non-adjacent-form under various input statistics
type: Item
instance of: scholarly article
title: The Hamming weight of the non-adjacent-form under various input statistics
zbMATH Open document ID: 1164.11009
author: Clemens Heuberger
author: Helmut Prodinger
published in: Periodica Mathematica Hungarica
publication date: 2008-10-22T00:00:00Z
review text: The Hamming weight of the integer \(\sum \varepsilon_j2^j\) with \(\varepsilon_j\in \{-1,0,+1\}\) is the number of non-zero \(\varepsilon'\)s. It is known that every integer admits a unique such representation satisfying \(\varepsilon_j\varepsilon_{j+1}=0\) for all \(j\), and that this representation minimizes the Hamming weight. It is also known that the expected weight of an integer \(< 2^n\) is \(\frac 13 n+O(1)\). In the paper under review the authors study the expected Hamming weight for integers satisfying certain properties. Two typical results are: let \(a_{k,n}\) be the normalized excepted Hamming weight for a nonnegative integer \(<2^n\) written as \(\sum\varepsilon_j 2^j\) \(\varepsilon_j \varepsilon_{j+1}=0\), and whose usual binary expansion has \(k\) nonzero digits. Then 1) if \(k\) and \(n\) tend to infinity with \(0<c\leq k/n\leq d<1\), then \[ a_{k,n}\sim\frac{1-4\big(\frac k n -\frac 12\big)^2}{3+4\big(\frac kn -\frac 12\big)^2} n\quad \text{uniformly}; \] 2) \ if \(k\) is fixed and \(n\) goes to infinity, then \[ a_{k,n}=k-\frac{k(k-1)(k-2)}{n^2}+O\left(\frac{1}{n^3}+\frac{1}{n^{k-1}}\right). \]
reviewed by: Jean-Paul Allouche
Mathematics Subject Classification ID: 11A63
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 05A16
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 5355813
zbMATH Keywords: non-adjacent form
zbMATH Keywords: binary expansion
zbMATH Keywords: Hamming weight
zbMATH Keywords: transducer
zbMATH Keywords: generating function
zbMATH Keywords: Omega operator
zbMATH Keywords: singularity analysis
zbMATH Keywords: quasi-power theorem
zbMATH Keywords: multivariate asymptotics
describes a project that uses: Omega
MaRDI profile type: Publication
full work available at URL: s10998-007-3081-z
OpenAlex ID: W2008960744
cites work: MacMahon's partition analysis: The Omega package
cites work: Central and local limit theorems applied to asymptotic enumeration
cites work: Central and local limit theorems applied to asymptotic enumeration. II: Multivariate generating functions
cites work: Asymptotic distributions and a multivariate Darboux method in enumeration problems
cites work: Singularity Analysis of Generating Functions
cites work: Q3549563
cites work: SUBBLOCK OCCURRENCES IN SIGNED DIGIT REPRESENTATIONS
cites work: Analysis of linear combination algorithms in cryptography
cites work: Hwang's Quasi-Power-Theorem in Dimension Two
cites work: On minimal expansions in redundant number systems: Algorithms and quantitative analysis
cites work: Analysis of alternative digit sets for nonadjacent representations
cites work: On convergence rates in the central limit theorems for combinatorial structures
cites work: Q3283895
cites work: Speeding up the computations on an elliptic curve using addition-subtraction chains
cites work: Summatory functions of digital sums occurring in cryptography
DOI: 10.1007/S10998-007-3081-Z
description: scientific article; zbMATH DE number 5355813