Analysis of the binary asymmetric joint sparse form (Q6486659)

The binary asymmetric joint sparse form is the digital expansion related to the dimension-\(d\) joint representation of a vector in \(\mathbb{Z}^d\) where each coordinate is represented in base \(2\) with digits in a set \(D\subseteq \mathbb{Z}\) of consecutive integers. The specific digits in the coordinates give rise to digital column vectors. These expansions show redundancy in terms of representations and can be used to find ``optimal'' expansions that are important, for instance, in efficient computations on elliptic curves.NEWLINENEWLINEThe authors study from various points of view the minimal Hamming weight in such expansions, i.e., the number of non-zero columns. They first give the transducer which allows to compute the Hamming weight for a given input vector. Furthermore, they show that the Hamming weight is asymptotically normally distributed, which generalizes a result by \textit{P. J. Grabner} et al. [Theor. Comput. Sci. 319, No. 1--3, 307--331 (2004; Zbl 1050.94009)]. In the expressions for both the expected value and the variance there appear continuous, 1-periodic fluctuation functions as second-order terms. The authors show that the fluctuation in the expected value is nowhere differentiable in the case of \(d=1\) and pose the non-differentiability in dimension \(d\geq 2\) as an open problem.NEWLINENEWLINEThe error terms are made more explicit in the case of the so-called width-\(w\) non-adjacent form, which is a special case of the asymmetric joint sparse form.