Redundancy of minimal weight expansions in Pisot bases
type: Item
instance of: scholarly article
title: Redundancy of minimal weight expansions in Pisot bases
zbMATH Open document ID: 1261.11004
author: Peter J. Grabner
author: Wolfgang Steiner
published in: Theoretical Computer Science
publication date: 2012-01-09T00:00:00Z
review text: Let \(\beta\) be a Pisot number, i.e., an algebraic integer \(\beta>1\) such that all conjugates have modulus less than one. Let \(U=(U_j)_{j\geq 0}\) be a strictly increasing sequence of integers with \(U_0=1\) eventually satisfying a linear recurrence whose characteristic polynomial is equal to the minimal polynomial of \(\beta\). The authors study digital expansions to the base of \(U\) with integer digits, i.e., words \(z=z_kz_{k-1}\ldots z_0\) over the alphabet \({\mathbb Z}\) and their values \(\sum_j z_jU_j\). The weight of a word is defined to be the sum of the absolute values of the digits. Let \(L_U\) be the set consisting of those words that minimize the weight over all expansions of the same value. The authors prove that \(L_U\) is recognized by a finite automaton. They give an asymptotic expression for the summatory function of the number of representations of \(n\) with minimal weight. It consists of a fluctuating main term and an error term. Finally, they show that there is a regular language \(G_U\subseteq L_U\) such that every integer is uniquely representable by an element of \(G_U\). This generalizes \textit{C. Frougny} and \textit{W. Steiner} [J. Math. Cryptol. 2, No. 4, 365--392 (2008; Zbl 1170.11003)] and \textit{P. Grabner} and \textit{C. Heuberger} [``On the number of optimal base 2 representations of integers'', Des. Codes Cryptogr. 40, 25--39 (2006)].
reviewed by: Clemens Heuberger
Mathematics Subject Classification ID: 11A63
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 11B39
Mathematics Subject Classification ID: 11B83
zbMATH DE Number: 5995823
zbMATH Keywords: Redundant numeration systems
zbMATH Keywords: linear recurrent base sequence
zbMATH Keywords: Fibonacci numbers
zbMATH Keywords: Pisot numbers
zbMATH Keywords: representation of minimal weight
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.08.018
OpenAlex ID: W1969388096
cites work: Q3559177
cites work: Handbook of Elliptic and Hyperelliptic Curve Cryptography
cites work: Analysis of digital functions and applications
cites work: Q3867876
cites work: Q5798359
cites work: Linear numeration systems, θ-developments and finite automata
cites work: Representations of numbers and finite automata
cites work: Q4529547
cites work: Minimal weight expansions in Pisot bases
cites work: Number representation and finite automata
cites work: On the number of optimal base 2 representations of integers
cites work: Distribution results for low-weight binary representations for pairs of integers
cites work: Functional iterations and stopping times for Brownian motion on the Sierpiński gasket
cites work: Matrix Analysis
cites work: An Introduction to Symbolic Dynamics and Coding
cites work: On digit expansions with respect to linear recurrences
cites work: Q5730090
cites work: Q3272731
cites work: Q3644388
cites work: Modern computer algebra
Wikidata QID: Q38880905
DBLP publication ID: journals/tcs/GrabnerS11
DOI: 10.1016/J.TCS.2011.08.018
Recommended article: Bertrand numeration systems and recognizability
Recommended article: Minimal weight expansions in Pisot bases
Recommended article: Greedy expansions and sets with deleted digits
Recommended article: On minimal expansions in redundant number systems: Algorithms and quantitative analysis
Recommended article: Q4412134
Recommended article: On the number of optimal base 2 representations of integers
Recommended article: Q4708608
Recommended article: On multiplicatively dependent linear numeration systems, and periodic points
Recommended article: Q3044316
Recommended article: Numeration systems, linear recurrences, and regular sets
description: scientific article; zbMATH DE number 5995823