Abstract
We obtain asymptotic formulas for the number of positive integers \(n\le X\) such that the sums of digits of the expansions of \(n\) and \(n+1\) over some linear recurrent sequences have a given parity.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1. Introduction
Let \(a_1,\dots,a_d\) be positive integers satisfying the condition
Define a sequence \(\{T_n\}\) using a linear recurrent relation
The initial conditions have the form
for \(n<d\). In this case, any positive integer \(N\) admits a unique greedy expansion with respect to the sequence \(\{T_n\}\) [1]:
The expansion (1.1) being greedy means that the inequalities \(0\le N-\sum_{k=m_1}^{m(N)}\varepsilon_k(N)T_k<T_{m_1}\) hold for any \(m_1<m(N)\).
Define the sets
of positive integers with a given parity of the sum of the digits of the expansion with respect to the sequence \(\{T_n\}\).
Let
Our objective is to prove the following theorem.
Theorem 1.
There exist effectively computable \(\lambda\) , \(0<\lambda<1\) , and \(C_{ij}\) ( \(C_{00}=C_{11}=-C_{10}=-C_{01}\) ) such that
An explicit formula for the constants \(C_{ij}\) is rather complicated and is given below.
For the special case in which \(\{T_n\}\) is a Fibonacci sequence (\(d=2\), \(a_1=a_2=1\)), this problem was considered in [2], [3], where it was shown in two different ways that, in this case,
It should also be noted that, in [4], [5], an analog of this problem for the binary number system was considered.
2. Auxiliary Results
In this section, we present some auxiliary results concerning expansions with respect to a sequence \(\{T_n\}\). Some of them are of independent interest.
Let us first obtain a bound for \(m(N)\). The following assertion holds [6, Theorem 2].
Proposition 1.
Let \(a_1,\dots,a_d\) be positive integers satisfying the condition
Then the root \(\beta\) with the greatest absolute value of the equation
is real, and \(\beta>1\). The absolute value of all other roots of equation (2.1) is less than 1. In other words, \(\beta\) is a Pisot number. Moreover, if \(T_\beta(x)=\beta x\ (\operatorname{mod}1)\) and \(d(1,\beta)=t_1t_2\dots\), where \(t_k=\lfloor\beta T_\beta^{k-1}(1)\rfloor\), and the process is terminated if zero is obtained at the next step, then \(d(1,\beta)=a_1\dotsb a_d\).
Note also that, in the proof of Theorem 2 in [6], it was also shown that (2.1) is the minimal polynomial for \(\beta\) under consideration. This implies that, to different linear recurrent sequences of the class under consideration, there correspond different \(\beta\).
Using the standard theory of linear recurrence relations with constant coefficients, we immediately obtain an asymptotic formula for \(T_n\).
Corollary 1.
The following asymptotic formula holds:
with some effectively computable constant \(c\ne 0\) .
This immediately implies a bound for \(m(N)\).
Corollary 2.
We have
By induction on \(n\), we can readily show that the inequality \(T_{n+1}<(a_1+1)T_n\) holds. In combination with the greedy condition of the expansion, this gives the bound \(\varepsilon_k(n)\le a_1\), \(0\le k\le m(N)\), for the coefficients of the expansion (1.1). Therefore, for every positive integer \(N\), the expansion (1.1) generates a finite word \(w(N)=\varepsilon_{m(N)}(N)\dotsb\varepsilon_0(N)\) over the alphabet \(\{0,1,\dots,a_1\}\). Obviously, not all finite words over the given alphabet are generated by greedy expansions of positive integers. We call the words generated by such expansions admissible.. We want to describe all admissible words.
Consider a graph containing \(d\) vertices labelled with the numbers \(0,1,\dots,d-1\). The edges of the graph have the following form:
-
1)
\(a_1\) oriented loops at the vertex \(0\) that are labelled with the numbers from \(0\) to \(a_1-1\);
-
2)
oriented edges from the vertex \(i\) to the vertex \(i+1\) that are labelled by the numbers \(a_{i+1}\);
-
3)
\(a_{i+1}\) oriented edges from the vertex \(i\) to the vertex \(0\)
labelled with the numbers from \(0\) to \(a_{i+1}-1\).
The construction of this graph was taken by us from the paper [7]. Denote the graph thus constructed by \(G(\beta)\). It has the following form.
To every finite path \(v_0\stackrel{c_{0}}{\longrightarrow}v_1\stackrel{c_{1}}{\longrightarrow}\dotsb \stackrel{c_{m-1}}{\longrightarrow}v_m\) in the graph \(G(\beta)\), one can assign the word \(c_0c_1\dotsb c_{m-1}\) composed of the labels of the path edges. The following assertion holds [7, Sec. 1.1], [8, Theorem 2.1 and Section 2.2].
Proposition 2.
The following assertions are equivalent:
-
1)
a word \(w\) is admissible;
-
2)
the word \(w\) is obtained from some path of the graph \(G(\beta)\) starting at the vertex 0;
-
3)
every subword of the word \(w\) is lexicographically less than the word \(a_1\dotsb a_d\) .
3. Numbers with a specified ending of the expansion
Let \(w\) be an admissible word. Consider the set \(\mathbb N(w)\) of positive integers for which \(w(N)\) ends with the word \(w\). Let
In this section, we obtain an asymptotics for \(N_w(N)\).
The derivation of this asymptotics is based on the theory of generalized Rauzy tilings.
Let \(\beta^{(1)},\dots,\beta^{(r_1)}\) be the real conjugates to \(\beta\) and \(\beta^{(r_1+1)},\overline{\beta^{(r_1+1)}},\dots, \beta^{(r_1+r_2)}\), \(\overline{\beta^{(r_1+r_2)}}\) be the complex conjugates to \(\beta\).
Define the mapping \(\Phi\colon\mathbb N\to\mathbb R^{d-1}\) by the equality
The set
is called the Rauzy fractal (the bar denotes the closure). The above construction of the Rauzy fractal was proposed in [9]; this is an analog of the construction of the Rauzy fractal used in [10] and based on greedy \(\beta\)-expansions of real numbers. The equivalence is shown in [9, Theorem 6].
Let \(\operatorname{Adm}_n(j)\) be the set of admissible words of length \(n\) for which the corresponding paths in the graph \(G(\beta)\) end at the vertex \(j\). For any word \(u\in\operatorname{Adm}_{d-1}(j)\), denote by \(\widetilde A_n(j)\) the set of words \(w\) of length \(n\) for which the word \(uw\) is admissible. Note that the admissibility of the word \(uw\) depends only on the existence, in the graph \(G(\beta)\), of a path that starts at the vertex at which the path corresponding to \(u\) ends. This means that \(\widetilde A_n(j)\) does not depend on the choice of \(u\) and is the set of admissible words of length \(n\) for which there is a corresponding path starting at \(j\). For every \(w\in\widetilde A_n(j)\), define the set
Proposition 3.
For every \(n\) , one has the tiling
of the Rauzy fractal \(\mathscr T\) into sets \(\mathscr R_{n,j}(w)\) having no common interior points. Each of the sets \(\mathscr R_{n,j}(w)\) has a boundary of zero measure.
This assertion is proved in [11, Theorem 11]. The tiling thus constructed is called the Rauzy tiling of order \(n\).
Proposition 4.
Let \(j\in\{0,1,\dots,d-1\}\) . Then the following equality holds for any \(n\) and any word \(w\in\widetilde A_n(j)\) :
This assertion is proved in [9, Theorem 10].
Further, let us define a mapping \(S\) on the Rauzy fractal. Let \(\operatorname{Adm}(j)=\bigcup_n\operatorname{Adm}_n(j)\) be the set of words to which there correspond paths on the graph \(G(\beta)\) that begin at the vertex \(0\) and end at the vertex \(j\). Let \(\mathbb N(j)=\{n\in\mathbb N\colon w(n)\in\operatorname{Adm}(j)\}\). Here \(\mathbb N=\bigsqcup_{j=0}^{d-1}\mathbb N(j)\). As is known (see, for example, [7, Sec. 1.3]), there are vectors \(v_j\in\mathbb R^{d-1}\) such that \(\Phi(n+1)-\Phi(n)=v_j\). Write \(\mathscr T(j)=\overline{\Phi(\mathbb N(j))}\) and define the mapping \(S\colon\mathscr T\to\mathscr T\) of the Rauzy fractal into itself according to the rule \(S(x)=x+v_j\) if \(x\in\mathscr T(j)\). It turns out (see [7, Theorem 6], [12, Theorem 2]) that the mapping \(S\) is defined almost everywhere on \(\mathscr T\) (and is an exchange of the domains \(\mathscr T(j)\), \(j\in\{0,1,\dots,d-1\}\)).
Remark 1.
Usually, this assertion is proved for a more general class of Rauzy fractals that are constructed using the basis of the so-called primitive unimodular Pisot substitutions. The reduction of the case under consideration to the general case can be found in [7, Secs. 2.3, 2.4]. Here it is required that \(\beta\) is a Pisot number (of degree \(d\)) and a unit of the ring \(\mathbb Z[\beta]\) and that the length of the word \(d(1,\beta)\) is equal to \(d\). The fact that \(\beta\) is a unit of the ring \(\mathbb Z[\beta]\) holds because \(a_d=1\), and the other conditions follow from Proposition 1.
The mapping \(S\) is not defined on points in the sets of the form \(\mathscr T(j_1)\cap\mathscr T(j_2)\). Note that the points of the form \(\Phi(n)\) with \(n\in\mathbb N\) do not belong to the boundaries of the sets of the form \(\mathscr T(j)\) (and even do not belong to the boundaries of sets of the form \(\overline{\Phi(\mathbb N(w))}\) for any admissible word \(w\)) [10, Corollary 1], and hence, for such points, the mapping \(S\) is well defined. Here \(S(\Phi(n))=\Phi(n+1)\).
Note also that the diagram
is commutative [9, Theorem 7].
Remark 2.
It can be shown [7, Theorem 7], [13, Theorem 7] that the Rauzy fractal \(\mathscr T\) represents a fundamental domain of some lattice \(L\). In this case, one can consider the natural projection \(\pi\colon\mathbb R^{d-1}\to\mathbb T^{d-1}=\mathbb R^{d-1}/L\). It turns out [12, Theorem 2 and Remark 5] that there exists a vector \(l\in\mathbb T^{d-1}\) whose coordinates in the basis of the lattice \(L\) are linearly independent over \(\mathbb Q\), together with the unit, and such that the equality \(\pi(S(x))=\pi(x)+l\ (\operatorname{mod}L)\) holds for every \(x\in\mathscr T\) for which the mapping \(S\) is defined.
Proposition 5.
The sets \(\mathscr R_{n,j}(w)\) are bounded remainder sets for the mapping \(S\) ; i.e., there exists a constant \(C\) depending only on \(\beta\) and such that the following inequality holds for all positive integers \(X\) :
Moreover, \(C\) depends on \(\beta\) , but not on \(n\) , \(j\) , and \(w\) .
For the proof, see [9, Theorem 12].
Let \(w\) be an admissible word of length \(|w|\). Let \(J(w)\) be the set of vertices of the graph \(G(\beta)\) for which there is a path in \(G(\beta)\) beginning at a vertex \(j\) and labelled with the word \(w\). Let
Proposition 6.
For every admissible word \(w\) , \(n\in\mathbb N(w)\) if and only if \(S^n(0)\in\mathscr T(w)\) .
Proof.
The proof can be found in [9, Theorems 13, 14]
By Proposition 3, the sets \(\mathscr R_{|w|,j}\) contained in \(\mathscr T(w)\) have no common interior points. Therefore, taking into account Proposition 4, we have
In addition, taking into account Proposition 5, we see that the sets \(\mathscr T(w)\) are also sets of bounded remainder with respect to the mapping \(S\). Moreover, since \(\mathscr T(w)\) obviously contains at most \(d\) sets \(\mathscr R_{|w|,j}\), it follows that the corresponding bound for the remainder does not depend on the choice of the word \(w\). Combining this result with Proposition 6, we obtain the required information concerning the asymptotic of \(N_w(X)\).
Theorem 2.
There exists a constant \(C_1\) depending on \(\beta\) only and such that the following inequality holds for any admissible word \(w\) and any positive integer \(X\) :
4. Proof of the Main Theorem
Let
Then it can readily be seen that the following equality holds:
Proposition 7.
There is an effectively computable constant \(\lambda<1\) such that
For the proof of Proposition 7, see [14]. A description of \(\lambda\) in terms of the roots of some equation depending on the coefficients of the linear recurrent sequence is given ibidem. A more general result is also proved in [15]. In [16], the possibility of strengthening the bound for the remainder term to a logarithmic one is discussed.
Let
Multiplying out in (4.1), we obtain
Taking into account (4.2) and the definition of \(S(X)\), we can represent the last expression in the form
for some effectively computable \(\lambda\in(0;1)\).
Then it can readily be seen from (4.1) and (4.2) that, to prove Theorem 1, it suffices to prove the following assertion.
Proposition 8.
There exists an effectively computable constant \(C_\beta\) such that
It can readily be seen here that \(C_{00}=C_{11}=(1/4)C_\beta\) and \(C_{01}=C_{10}=-(1/4)C_\beta\).
Let us pass to the proof of Proposition 8. For \(k\in\{0,1,\dots,d-1\}\), write \(w_{\max}^{(k)}=a_1\dotsb a_k\) (for \(k=0\), \(w_{\max}^{(0)}\) is the empty word). Write \(w_{\max}^{(d)}=a_1\dotsb a_{d-1}0\). Then it is easy to see that the word \(w_{\max}^{(k)}\) is admissible for any \(k\). Moreover, it is the maximum admissible word of length \(k\) with respect to the lexicographic order.
Let \(U\) be the set of admissible words of length \(d\) corresponding to paths of the graph \(G(\beta)\) starting and ending at the vertex \(0\) and different from the word \(w_{\max}^{(d)}\). It follows from the consideration of the graph \(G(\beta)\) that an admissible word belongs to \(U\) if and only if it does not end by any of the words \(w_{\max}^{(k)}\) (\(1\le k\le d\)). For \(u\in U\), \(k\in\{0,1,\dots,d-1\}\), and an integer nonnegative \(m\), define the word
The words introduced in this way have the following important properties.
1) None of the words \(w_{u,m,k}\) ends with another word.
2) For any positive integer \(N\), the word \(w(N)\) (or a word derived from \(w(N)\) by adding a certain number of zeros from the left) ends with one of the words \(w_{u,m,k}\).
Thus, there is a representation of the set of positive integers as the disjoint union
For any admissible word \(w\), denote by \(w'\) the lexicographically next admissible word. Then it can readily be seen that the following equality holds:
For the word \(w=w_1\dotsb w_{|w|}\) (where \(w_i\in\{0,1,\dots,a_1\}\) are separate symbols of the word), write
It is clear that \(\varepsilon(N)=\varepsilon(w(N))\). Let us represent \(w(N)\) in the form \(w(N)=vw_{u,m,k}\). Then we have \((w(N))'=v(w_{u,m,k})'\). Therefore,
Then, taking into account (4.4) and the definition of \(w_{u,m,k}\), we see that the following equality holds for any \(n\in\mathbb N(w_{u,m,k})\):
Taking into account the definition of the words \(w_{\max}^{(k)}\), we obtain
Combining (4.3) and (4.5), we have
Note that the equality \(N_{w_{u,m,k}}(X)=0\) obviously holds for \(|w_{u,m,k}|>|w(X)|=m(X)\). Therefore,
Let
Then
where
Applying Theorem 2, we see that there is a constant \(C_1\) depending on \(\beta\) only and such that
Applying the triangle inequality and taking into account that
we obtain
i.e.,
Here it follows from the definition of the set \(U\) that its cardinality \(\sharp U\) does not depend on \(X\). Moreover, it follows from Corollary 2 that \(|w(X)|=O(\log X)\). Hence
Therefore, transposing the summation over \(m\) and \(k\) in the sum for \(S_1(X)\), we find that
where
Since \(|w_{u,m,k}|=(m+1)d+k\), it follows that the last equality can be represented in the form
Further, note that it is easy to derive that any path in \(G(\beta)\) corresponding to a word \(u\) must end at the vertex \(0\) from the fact that the word \(u\in U\) does not end with \(w_{\max}^{(k)}\). In addition, the word \(w_{\max}^{(k)}\) with \(k>0\) is admissible and, corresponding to it, there is a path in the graph \(G(\beta)\) starting at the vertex \(0\). Therefore, every path corresponding to the word \(u\) can be continued to a path corresponding to the word \(uw_{\max}^{(k)}\). Hence we see that \(J(w_{u,m,k})=J(u)\) and
Write
Taking into account the formula for the sum of an infinite geometric progression, we obtain
Write
Note that all constants \(C_{u,k}\), and thus also all constants \(C_\beta\), are effectively computable.
To complete the proof of Proposition 8, it remains to prove that
For the proof of this bound, it suffices to prove that
When taking into account the definitions of \(C_{u,k}\) and \(\Sigma_{u,k}\), we see that the last bound is equivalent to
Summing the infinite geometric progression again, we obtain
with some constant \(C_2\). When taking into account Corollary 2, we see that the last value is \(O(X^{1-d})\) and, therefore, \(O(\log X)\), which proves (4.7), and hence also (4.6), which completes the proof of Proposition 8, and hence also of Theorem 1.
References
G. Parry, “On the \(\beta\)-expansions of real numbers,” Acta Math. Acad. Sci. Hungar. 11 (3), 401–416 (1960).
A. Shutov, “On the sum of digits of the Zeckendorf representations of two consecutive numbers,” Fibonacci Quart. 58 (3), 203–207 (2020).
A. V. Shutov, “On one sum associated with Fibonacci numeration system,” Dal’nevost. Mat. Zh. 20 (2), 271–275 (2020).
K. Mahler, “The spectrum of an array and its application to the study of the translation properties of a simple class of arithmetical functions: part two on the translation properties of a simple class of arithmetical functions,” J. Math. and Physics 6, 158–163 (1927).
K. M. Éminyan, “A binary problem,” Math. Notes 60 (4), 478–481 (1996).
C. Frougny and B. Solomyak, “Finite beta-expansions,” Ergodic Theory Dynam. Systems 12 (4), 713–723 (1992).
V. Berthe and A. Siegel, “Tilings associated with beta-numeration and substitutions,” Integers 5 (3), A02 (2008).
S. Akiyama, G. Barat, V. Berthe, and A. Siegel, “Boundary of central tiles associated with Pisot beta-numeration and purely periodic expansions,” Monatsh. Math. 155 (3–4), 377–419 (2008).
A. V. Shutov, “Generalized Rauzy tilings and linear recurrence sequences,” Chebyshevskii Sb. 22 (2), 313–333 (2021).
S. Akiyama, “Self affine tiling and Pisot numeration system,” in Number Theory and its Applications, Kyoto, 1997, Vol. 2, Dev. Math. (Kluwer Acad. Publ., Dordrecht, 1999), pp. 7–17.
A. V. Shutov, “Generalized Rauzy tilings and bounded remainder sets,” Chebyshevskii Sb. 20 (3), 372–389 (2019).
P. Arnoux and S. Ito, “Pisot substitutions and Rauzy fractals,” Bull. Belg. Math. Soc. Simon Stevin 8 (2), 181–207 (2001).
S. Akiyama, “Pisot number system and its dual tiling,” in Physics and Theoretical Computer Science, NATO Secur. Sci. Ser. D Inf. Commun. Secur. (IOS Press, Amsterdam, 2007), Vol. 7, pp. 133–154.
M. Drmota and J. Gajdosik, “The parity of the sum-of-digits-function of generalized Zeckendorf representations,” Fibonacci Quart. 36 (1), 3–19 (1998).
M. Lamberger and J. W. Thuswaldner, “Distribution properties of digital expansions arising from linear recurrences,” Math. Slovaca 53 (1), 1–20 (2003).
A. A. Zhukova and A. V. Shutov, “On Gelfond-type problem for generalized Zeckendorf representations,” Chebyshevskii Sb. 22 (2), 104–120 (2021).
Funding
This work was financially supported by the Russian Science Foundation, project 19-11-00065, https://rscf.ru/en/project/19-11-00065/.
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Matematicheskie Zametki, 2023, Vol. 114, pp. 447–457 https://doi.org/10.4213/mzm13609.
Rights and permissions
About this article
Cite this article
Shutov, A.V. On the Sum of Digits of Expansions of a Pair of Consecutive Numbers over a Linear Recurrent Sequence. Math Notes 114, 387–396 (2023). https://doi.org/10.1134/S0001434623090092
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0001434623090092