Redundancy of minimal weight expansions in Pisot bases

preprint2011arXivOpen access

Abstract

Motivated by multiplication algorithms based on redundant number representations, we study representations of an integer nn as a sum n=∑kεkUkn=\sum_k ε_k U_k, where the digits εkε_k are taken from a finite alphabet ΣΣ and (Uk)k(U_k)_k is a linear recurrent sequence of Pisot type with U0=1U_0=1. The most prominent example of a base sequence (Uk)k(U_k)_k is the sequence of Fibonacci numbers. We prove that the representations of minimal weight ∑k∣εk∣\sum_k|ε_k| are recognised by a finite automaton and obtain an asymptotic formula for the average number of representations of minimal weight. Furthermore, we relate the maximal order of magnitude of the number of representations of a given integer to the joint spectral radius of a certain set of matrices.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.