On the Variation of the Sum of Digits in the Zeckendorf Representation:

an Algorithm to Compute the Distribution and Mixing Properties

Yohan Hosten

Laboratoire Amiénois de Mathématique Fondamentale et Appliquée Université de Picardie Jules Verne 33, rue Saint Leu 80000 Amiens France

               yohan.hosten@math.cnrs.fr

Abstract

We study probability measures defined by the variation of the sum of digits in the Zeckendorf representation. For r ≥ 0 and d ∈ ℤ, we consider μ^{(r)}(d) the density of integers n ∈ ℕ for which the sum of digits increases by d when r is added to n. We give a probabilistic interpretation of μ^{(r)} via the dynamical system provided by the odometer of Zeckendorf-adic integers and its unique invariant measure. We give an algorithm for computing μ^{(r)} and we prove the exponential decay of μ^{(r)}(d) as d → −∞, as well as the formula μ^{(F_{ℓ})} = μ^{(1)} where F_{ℓ} is a term in the Fibonacci sequence. Finally, we decompose the Zeckendorf representation of an integer r into so-called “blocks” and show that when added to an adic Zeckendorf integer, the successive actions of these blocks can be seen as a sequence of mixing random variables.

1 Introduction

1.1 Framework, notations and main results

Throughout this article, we let ℕ := \{0, 1, 2, …\} denote the set of integers and φ := \frac{1+\sqrt{5}}{2} represents the golden ratio. We also define the well-known Fibonacci sequence as follows:

F_{k} := \begin{cases}1, & if k = 1; \\ 1, & if k = 2; \\ F_{k−1} + F_{k−2}, & if k ≥ 3. \end{cases}  (1)

By Zeckendorf’s theorem (proved by Lekkerkerker [?, Theorem 1] and Zeckendorf [?, Theorem I.a, p. 179]), every integer can be uniquely written as a sum of non-consecutive Fibonacci terms. That is: for every n ∈ ℕ, there exists a unique sequence of digits (n_{k})_{k≥2} ∈ {0, 1}^{∞} without two consecutive 1’s, finitely many of them being equal to 1 and such that

n = ∑_{k≥2} n_{k}F_{k}.  (2)

For n ≠ 0 and ℓ := max{k : n_{k} ≠ 0}, we introduce the notation [n_{ℓ} ⋯ n_{2}] := n that generalizes the usual way we write numbers in an integer base, and that we refer to as the (Zeckendorf) expansion of n. This way to expand numbers is actually a particular case of an Ostrowski numeration system [?, ?, ?]. By convention, we set [0] := 0. Then we define the (Zeckendorf-)sum-of-digits function as

s(n) := ∑_{k≥2} n_{k}.

A central object in our paper is the variation of the sum of digits when we add a fixed integer r to n: for r, n ∈ ℕ, we set

Δ^{(r)}(n) := s(n + r) − s(n).  (3)

The analogous variation in an integer base has been studied extensively. The first appearance in the integer base case is in a paper from Bésineau [?] in 1970. Using a statistical vocabulary, he showed the existence of the asymptotic density for the set of integers such that the variation is some integer d ∈ ℤ. Given an integer r, these densities can be seen as a probability law. The variance of this law was studied, in binary base, by Emme and Prikhod’ko [?] or Spiegelhofer and Wallner [?]. Emme and Hubert [?] proved a central limit theorem in the binary case that was improved by Spiegelhofer and Wallner [?] (still in binary) or by the author in collaboration with Janvresse and de la Rue [?] (in arbitrary integer base). We also refer to [?, ?, ?, ?] for connected results. Some theorems were proved for the Zeckendorf expansion of an integer: for instance, Griffiths [?] about the digit proportions; or Labbé and Lepšovà [?] about the addition in this numeration system. Drmota, Müllner and Spiegelhofer [?] obtained results about the existence of primes numbers with a fixed Zeckendorf sum-of-digits. However, not much has been done about this variation in the Zeckendorf representation except the work from Dekking [?] that characterizes the integers such that Δ^{(1)} is > 0 (or < 0 or = 0) and from Spiegelhofer [?, Lemma 1.30], which adapted Bésineau’s techniques and proved that, for all d ∈ ℤ, the following asymptotic density exists

μ^{(r)}(d) := lim_{N→+∞} \frac{1}{N} |\{n < N : Δ^{(r)}(n) = d\}| .

In the present paper, we adapt the ergodic theory point of view introduced in an integer base case [?] to the Zeckendorf expansion, recovering Spiegelhofer’s result and getting new results about μ^{(r)} and Δ^{(r)}. In particular, we provide an algorithm that computes μ^{(r)}(d)