The carry propagation of the successor function

DOI10.1016/J.AAM.2020.102062MaRDI QIDQ2197902zbMATH OpenOpenAlexFDO

Authors Christiane Frougny, Michel Rigo, Jacques Sakarovitch, Valérie Berthé

Publication date 1 September 2020

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.01464

zbMATH Keywords

generating functiondynamical systemnumeration systemsuccessor functioncarry propagationgreedy numeration systemlanguage signaturepositive rational seriesrational base numeration system

Mathematics Subject Classification ID

Radix representation; digital problems (11A63) Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc. (11K16) Symbolic dynamics (37B10) Algebraic theory of languages and automata (68Q70) Combinatorics on words (68R15) Relations between ergodic theory and harmonic analysis (37A46)

Abstract: Given any numeration system, we call carry propagation at a number $N$ the number of digits that are changed when going from the representation of $N$ to the one of $N+1$, and amortized carry propagation the limit of the mean of the carry propagations at the first $N$ integers, when $N$ tends to infinity, if this limit exists. In the case of the usual base $p$ numeration system, it can be shown that the limit indeed exists and is equal to $p/(p-1)$. We recover a similar value for those numeration systems we consider and for which the limit exists. We address the problem of the existence of the amortized carry propagation in non-standard numeration systems of various kinds: abstract numeration systems, rational base numeration systems, greedy numeration systems and beta-numeration. We tackle the problem by three different types of techniques: combinatorial, algebraic, and ergodic. For each kind of numeration systems that we consider, the relevant method allows for establishing sufficient conditions for the existence of the carry propagation and examples show that these conditions are close to being necessary conditions.

Recommendations

• Carry propagation in signed digit representations
• scientific article; zbMATH DE number 1055635
• Analysis of Carry Propagation in Addition: An Elementary Approach
• Carries and the arithmetic progression structure of sets
• Analysis of carries in signed digit expansions

Cites work

• scientific article; zbMATH DE number 3593676 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 3799981 (Why is no real title available?)
• scientific article; zbMATH DE number 891076 (Why is no real title available?)
• Abstract numeration systems
• Analysis of Carry Propagation in Addition: An Elementary Approach
• Combinatorial Complexity of Regular Languages
• Combinatorial and probabilistic properties of systems of numeration
• Dynamiques associees a une echelle de numeration
• Elements of automata theory. Translated from the French by Reuben Thomas
• Formal Languages, Automata and Numeration Systems 1
• How to write integers in a non-integral basis
• Noncommutative rational series with applications
• Number representation and finite automata
• Numeration systems on a regular language
• Numeration systems, linear recurrences, and regular sets
• Odometers and systems of numeration
• Odometers on regular languages
• On the sequentiality of the successor function
• On theβ-expansions of real numbers
• Powers of rationals modulo 1 and rational base number systems
• Representations for real numbers and their ergodic properties
• Substitutions in dynamics, arithmetics and combinatorics
• Systems of Numeration
• The signature of rational languages
• Trees and languages with periodic signature

Cited in

(2)

• Regular sequences and synchronized sequences in abstract numeration systems
• Analysis of carries in signed digit expansions

This page was built for publication: The carry propagation of the successor function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197902)