Front for the arXiv
Fri, 9 May 2008
Front > math > CO > 0803 > arXiv:0803.2874
search | register | submit
journals | about | iFAQ

arXiv:0803.2874

[pdf] [ps] [dvi] [src] [arxiv]

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

[help e-mail] - for questions or comments about the Front
arXiv contact page - for questions about downloading and submitting e-prints