The level of distribution of the sum-of-digits function of linear recurrence number systems
Journal de théorie des nombres de Bordeaux, Volume 34 (2022) no. 2, pp. 449-482.

Let $G={\left({G}_{j}\right)}_{j\ge 0}$ be a strictly increasing linear recurrent sequence of integers with ${G}_{0}=1$ having characteristic polynomial ${X}^{d}-{a}_{1}{X}^{d-1}-\cdots -{a}_{d-1}X-{a}_{d}$. It is well known that each positive integer $\nu$ can be uniquely represented by the so-called greedy expansion $\nu ={\epsilon }_{0}\left(\nu \right){G}_{0}+\cdots +{\epsilon }_{\ell }\left(\nu \right){G}_{\ell }$ for $\ell \in ℕ$ satisfying ${G}_{\ell }\le \nu <{G}_{\ell +1}$. Here the digits are defined recursively in a way that $0\le \nu -{\epsilon }_{\ell }\left(\nu \right){G}_{\ell }-\cdots -{\epsilon }_{j}\left(\nu \right){G}_{j}<{G}_{j}$ holds for $0\le j\le \ell$. In the present paper we study the sum-of-digits function ${s}_{G}\left(\nu \right)={\epsilon }_{0}\left(\nu \right)+\cdots +{\epsilon }_{\ell }\left(\nu \right)$ under certain natural assumptions on the sequence $G$. In particular, we determine its level of distribution ${x}^{\vartheta }$. To be more precise, we show that for $r,s\in ℕ$ with $gcd\left({a}_{1}+\cdots +{a}_{d}-1,s\right)=1$ we have for each $x\ge 1$ and all $A,\epsilon \in {ℝ}_{>0}$ that

 $\begin{array}{c}\sum _{q<{x}^{\vartheta -\epsilon }}\underset{z

Here $\vartheta =\vartheta \left(G\right)\ge \frac{1}{2}$ can be computed explicitly and we have $\vartheta \left(G\right)\to 1$ for ${a}_{1}\to \infty$. As an application we show that $#\left\{k\le x\phantom{\rule{0.166667em}{0ex}}:\phantom{\rule{0.166667em}{0ex}}{s}_{G}\left(k\right)\equiv r\phantom{\rule{4.44443pt}{0ex}}\left(mod\phantom{\rule{0.277778em}{0ex}}s\right),\phantom{\rule{0.277778em}{0ex}}k$ has at most two prime factors$\right\}\gg x/logx$ provided that the coefficient ${a}_{1}$ is not too small. Moreover, using Bombieri’s sieve an “almost prime number theorem” for ${s}_{G}$ follows from our result.

Our work extends earlier results on the classical $q$-ary sum-of-digits function obtained by Fouvry and Mauduit.

Soit $G={\left({G}_{j}\right)}_{j\ge 0}$ une suite strictement croissante des entiers définie par récurrence et telle que ${G}_{0}=1.$ Soit ${X}^{d}-{a}_{1}{X}^{d-1}-\cdots -{a}_{d-1}X-{a}_{d}$ son polynôme caractéristique. Il est bien connu que tout entier positif $\nu$ possède une écriture glouton unique telle que $\nu ={\epsilon }_{0}\left(\nu \right){G}_{0}+\cdots +{\epsilon }_{\ell }\left(\nu \right){G}_{\ell }$ pour $\ell \in ℕ$ qui satisfait ${G}_{\ell }\le \nu <{G}_{\ell +1}$. Ici les chiffres sont définis de manière récursive par la relation $0\le \nu -{\epsilon }_{\ell }\left(\nu \right){G}_{\ell }-\cdots -{\epsilon }_{j}\left(\nu \right){G}_{j}<{G}_{j},$$0\le j\le \ell$. Dans cet article, nous étudions la somme des chiffres ${s}_{G}\left(\nu \right)={\epsilon }_{0}\left(\nu \right)+\cdots +{\epsilon }_{\ell }\left(\nu \right)$ sous certains conditions naturelles sur la suite $G$. En particulier, nous déterminons son niveau de distribution. Pour être plus précis, nous montrons que pour $r,s\in ℕ$ avec $gcd\left({a}_{1}+\cdots +{a}_{d}-1,s\right)=1$ on a

 $\begin{array}{c}\sum _{q<{x}^{\vartheta -\epsilon }}\underset{z

pour tous $x\ge 1$ et $A,\epsilon \in {ℝ}_{>0}.$ Dans ce cas, $\vartheta =\vartheta \left(G\right)\ge \frac{1}{2}$ peut être calculé explicitement, et on obtient $\vartheta \left(G\right)\to 1$ pour ${a}_{1}\to \infty$. Comme application nous montrons que si le coefficient ${a}_{1}$ n’est pas trop petit, alors $#\left\{k\le x\phantom{\rule{0.166667em}{0ex}}:\phantom{\rule{0.166667em}{0ex}}{s}_{G}\left(k\right)\equiv r\phantom{\rule{4.44443pt}{0ex}}\left(mod\phantom{\rule{0.277778em}{0ex}}s\right),\phantom{\rule{0.277778em}{0ex}}k$ a au plus deux facteurs premiers$\right\}\gg x/logx$. En outre, en utilisant le crible de Bombieri, on en déduit un théorème des nombres presque premiers pour ${s}_{G}$.

Notre travail étend les résultats antérieurs sur la fonction somme des chiffres classique en base $q$ obtenus par Fouvry and Mauduit.

Received:
Accepted:
Published online:
DOI: 10.5802/jtnb.1209
Classification: 11A63, 11L07, 11N05
Keywords: Sum of digits, linear recurrence number system, level of distribution, almost prime
Manfred G. Madritsch 1, 2; Jörg M. Thuswaldner 3

1 Université de Lorraine, Institut Elie Cartan de Lorraine, UMR 7502, 54506 Vandoeuvre-lès-Nancy, France
2 CNRS, Institut Elie Cartan de Lorraine, UMR 7502, 54506 Vandoeuvre-lès-Nancy, France
3 Department of Mathematics and Information Technology, University of Leoben, Franz-Josef-Strasse 18, A-8700 Leoben, Austria
License: CC-BY-ND 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
@article{JTNB_2022__34_2_449_0,
author = {Manfred G. Madritsch and J\"org M. Thuswaldner},
title = {The level of distribution of the sum-of-digits function of linear recurrence number systems},
journal = {Journal de th\'eorie des nombres de Bordeaux},
pages = {449--482},
publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
volume = {34},
number = {2},
year = {2022},
doi = {10.5802/jtnb.1209},
language = {en},
url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1209/}
}
TY  - JOUR
AU  - Manfred G. Madritsch
AU  - Jörg M. Thuswaldner
TI  - The level of distribution of the sum-of-digits function of linear recurrence number systems
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2022
SP  - 449
EP  - 482
VL  - 34
IS  - 2
PB  - Société Arithmétique de Bordeaux
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1209/
UR  - https://doi.org/10.5802/jtnb.1209
DO  - 10.5802/jtnb.1209
LA  - en
ID  - JTNB_2022__34_2_449_0
ER  - 
%0 Journal Article
%A Manfred G. Madritsch
%A Jörg M. Thuswaldner
%T The level of distribution of the sum-of-digits function of linear recurrence number systems
%J Journal de théorie des nombres de Bordeaux
%D 2022
%P 449-482
%V 34
%N 2
%I Société Arithmétique de Bordeaux
%U https://doi.org/10.5802/jtnb.1209
%R 10.5802/jtnb.1209
%G en
%F JTNB_2022__34_2_449_0
Manfred G. Madritsch; Jörg M. Thuswaldner. The level of distribution of the sum-of-digits function of linear recurrence number systems. Journal de théorie des nombres de Bordeaux, Volume 34 (2022) no. 2, pp. 449-482. doi : 10.5802/jtnb.1209. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1209/

[1] Morton Abramson Restricted combinations and compositions, Fibonacci Q., Volume 14 (1976) no. 5, pp. 439-452 | MR | Zbl

[2] Guy Barat; Peter J. Grabner Distribution properties of $G$-additive functions, J. Number Theory, Volume 60 (1996) no. 1, pp. 103-123 | DOI | MR | Zbl

[3] Guy Barat; Peter J. Grabner Combinatorial and probabilistic properties of systems of numeration, Ergodic Theory Dyn. Syst., Volume 36 (2016) no. 2, pp. 422-457 | DOI | MR | Zbl

[4] Olivia Beckwith; Amanda Bower; Louis Gaudet; Rachel Insoft; Shiyu Li; Steven J. Miller; Philip Tosteson The average gap distribution for generalized Zeckendorf decompositions, Fibonacci Q., Volume 51 (2013) no. 1, pp. 13-27 | MR | Zbl

[5] Valérie Berthé Autour du système de numération d’Ostrowski, Bull. Belg. Math. Soc. Simon Stevin, Volume 8 (2001), pp. 209-239 Journées Montoises d’Informatique Théorique (Marne-la-Vallée, 2000) | Zbl

[6] Andrew Best; Patrick Dynes; Xixi Edelsbrunner; Brian McDonald; Steven J. Miller; Kimsy Tor; Caroline Turnage-Butterbaugh; Madeleine Weinstein Gaussian behavior of the number of summands in Zeckendorf decompositions in small intervals, Fibonacci Q., Volume 52 (2014) no. 5, pp. 47-53 | MR | Zbl

[7] Jean Coquet; Georges Rhin; Philippe Toffin Représentations des entiers naturels et indépendance statistique. II, Ann. Inst. Fourier, Volume 31 (1981) no. 1, pp. 1-15 | DOI | Numdam | Zbl

[8] Michael Drmota; Johannes Gajdosik The distribution of the sum-of-digits function, J. Théor. Nombres Bordeaux, Volume 10 (1998) no. 1, pp. 17-32 | DOI | Numdam | MR | Zbl

[9] Michael Drmota; Johannes Gajdosik The parity of the sum-of-digits-function of generalized Zeckendorf representations, Fibonacci Q., Volume 36 (1998) no. 1, pp. 3-19 | MR | Zbl

[10] Michael Drmota; Clemens Müllner; Lukas Spiegelhofer Möbius orthogonality for the Zeckendorf sum-of-digits function, Proc. Am. Math. Soc., Volume 146 (2018) no. 9, pp. 3679-3691 | DOI | Zbl

[11] Michael Drmota; Wolfgang Steiner The Zeckendorf expansion of polynomial sequences, J. Théor. Nombres Bordeaux, Volume 14 (2002) no. 2, pp. 439-475 | DOI | Numdam | MR | Zbl

[12] Étienne Fouvry; Christian Mauduit Méthodes de crible et fonctions sommes des chiffres, Acta Arith., Volume 77 (1996) no. 4, pp. 339-351 | DOI | Zbl

[13] Étienne Fouvry; Christian Mauduit Sommes des chiffres et nombres presque premiers, Math. Ann., Volume 305 (1996) no. 3, pp. 571-599 | DOI | MR | Zbl

[14] John Friedlander; Henryk Iwaniec Opera de cribro, Colloquium Publications, 57, American Mathematical Society, 2010, xx+527 pages

[15] Christiane Frougny; Boris Solomyak Finite beta-expansions, Ergodic Theory Dyn. Syst., Volume 12 (1992) no. 4, pp. 713-723 | DOI | MR | Zbl

[16] Peter J. Grabner; Pierre Liardet; Robert F. Tichy Odometers and systems of numeration, Acta Arith., Volume 70 (1995) no. 2, pp. 103-123 | DOI | MR | Zbl

[17] Peter J. Grabner; Robert F. Tichy Contributions to digit expansions with respect to linear recurrences, J. Number Theory, Volume 36 (1990) no. 2, pp. 160-169 | DOI | MR | Zbl

[18] George Greaves The weighted linear sieve and Selberg’s ${\lambda }^{2}$-method, Acta Arith., Volume 47 (1986) no. 1, pp. 71-96 | DOI | MR

[19] George Greaves Sieves in number theory, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge., 43, Springer, 2001 | MR

[20] Markus Hofer; Maria Rita Iacò; Robert F. Tichy Ergodic properties of $\beta$-adic Halton sequences, Ergodic Theory Dyn. Syst., Volume 35 (2015) no. 3, pp. 895-909 | DOI | MR | Zbl

[21] Mario Lamberger; Jörg M. Thuswaldner Distribution properties of digital expansions arising from linear recurrences, Math. Slovaca, Volume 53 (2003) no. 1, pp. 1-20 | MR | Zbl

[22] Christian Mauduit; Joël Rivat Sur un problème de Gelfond: la somme des chiffres des nombres premiers, Ann. Math., Volume 171 (2010) no. 3, pp. 1591-1646 | DOI | Zbl

[23] Hugh L. Montgomery Topics in multiplicative number theory, Lecture Notes in Mathematics, 227, Springer, 1971, ix+178 pages | DOI

[24] Syoiti Ninomiya Constructing a new class of low-discrepancy sequences by using the $\beta$-adic transformation, Math. Comput. Simul., Volume 47 (1998) no. 2-5, pp. 403-418 IMACS Seminar on Monte Carlo Methods (Brussels, 1997) | DOI | MR

[25] William Parry On the $\beta$-expansions of real numbers, Acta Math. Acad. Sci. Hung., Volume 11 (1960), pp. 401-416 | DOI | MR | Zbl

[26] Attila Pethő; Robert F. Tichy On digit expansions with respect to linear recurrences, J. Number Theory, Volume 33 (1989) no. 2, pp. 243-256 | DOI | MR | Zbl

[27] Alfréd Rényi Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci. Hung., Volume 8 (1957), pp. 477-493 | DOI | MR | Zbl

[28] Peter Sarnak Mobius randomness and dynamics, Not. South Afr. Math. Soc., Volume 43 (2012) no. 2, pp. 89-97 | MR | Zbl

[29] Lukas Spiegelhofer Correlations for numeration systems, Ph. D. Thesis, Technical University of Vienna and Aix-Marseille Université (2014)

[30] Lukas Spiegelhofer The level of distribution of the Thue–Morse sequence (2018) (Preprint, available under https://arxiv.org/abs/1803.01689)

[31] Wolfgang Steiner Digit expansions and the distribution of related functions, 2000 (Master thesis, Technical University of Vienna)

[32] Wolfgang Steiner Parry expansions of polynomial sequences, Integers, Volume 2 (2002), A14, 28 pages | MR | Zbl

[33] Jörg M. Thuswaldner Discrepancy bounds for $\beta$-adic Halton sequences, Number theory—Diophantine problems, uniform distribution and applications, Springer, 2017, pp. 423-444 | DOI | Zbl

[34] Stephan G. Wagner Numbers with fixed sum of digits in linear recurrent number systems, Ramanujan J., Volume 14 (2007) no. 1, pp. 43-68 | DOI | MR | Zbl

[35] Edouard Zeckendorf Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. R. Sci. Liège, Volume 41 (1972), pp. 179-182 | Zbl

Cited by Sources: