![[arxiv]](/images/buttons/arxiv.png)
Title: Minimal weight expansions in Pisot bases
Authors: Christiane Frougny (LIAFA), Wolfgang Steiner (LIAFA)
Categories: math.CO Combinatorics (cs.CR Cryptography and Security; math.NT Number Theory)
Abstract: For applications to cryptography, it is important to represent numbers with a
small number of non-zero digits (Hamming weight) or with small absolute sum of
digits. The problem of finding representations with minimal weight has been
solved for integer bases, e.g. by the non-adjacent form in base 2. In this
paper, we consider numeration systems with respect to a real base $\beta$ which
is a Pisot number. When $\beta$ is the Golden Ratio, the Tribonacci number or
the smallest Pisot number, we determine expansions with minimal number of
digits $\pm1$ and give finite automata recognizing all these expansions. The
average weight is lower than for the non-adjacent form. In the general case of
a base $\beta$ which is a Pisot number satisfying a certain condition (D$'$),
we prove that the expansions with minimal absolute sum of digits are
recognizable by a finite automaton.
Owner: Wolfgang Steiner
Version 1: Wed, 19 Mar 2008 19:55:38 GMT
Version 2: Thu, 27 Mar 2008 16:30:49 GMT