The level of distribution of the sum-of-digits function of linear recurrence number systems

Madritsch, Manfred G.; Thuswaldner, Jörg M.

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 \mathbb{N}$ 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 \mathbb{N}$ with $gcd(a_1+\cdots +a_d-1,s)=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<x}{max}\underset{1\le h\le q}{max}|\sum _{\begin{array}{c}k<z,s_G\left(k\right)\equiv rmods\\ k\equiv hmodq\end{array}}1-\frac{1}{q}\sum _{k<z,s_G\left(k\right)\equiv rmods}1|\hfill \\ \hfill \ll x{(log2x)}^{-A}.\end{array}$$

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 $\#\{k\le x:s_G\left(k\right)\equiv r(mods),k$ has at most two prime factors$\}\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 \mathbb{N}$ 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,$ où $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 \mathbb{N}$ avec $gcd(a_1+\cdots +a_d-1,s)=1$ on a

$$\begin{array}{c}\sum _{q<x^{\vartheta -\epsilon }}\underset{z<x}{max}\underset{1\le h\le q}{max}|\sum _{\begin{array}{c}k<z,s_G\left(k\right)\equiv rmods\\ k\equiv hmodq\end{array}}1-\frac{1}{q}\sum _{k<z,s_G\left(k\right)\equiv rmods}1|\hfill \\ \hfill \ll x{(log2x)}^{-A}\end{array}$$

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 $\#\{k\le x:s_G\left(k\right)\equiv r(mods),k$ a au plus deux facteurs premiers$\}\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.

Classification: 11A63, 11L07, 11N05
Keywords: Sum of digits, linear recurrence number system, level of distribution, almost prime

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

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

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

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

[5] Berthé, Valérie 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] Best, Andrew; Dynes, Patrick; Edelsbrunner, Xixi; McDonald, Brian; Miller, Steven J.; Tor, Kimsy; Turnage-Butterbaugh, Caroline; Weinstein, Madeleine 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] Coquet, Jean; Rhin, Georges; Toffin, Philippe 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] Drmota, Michael; Gajdosik, Johannes 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] Drmota, Michael; Gajdosik, Johannes 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] Drmota, Michael; Müllner, Clemens; Spiegelhofer, Lukas 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] Drmota, Michael; Steiner, Wolfgang The Zeckendorf expansion of polynomial sequences, J. Théor. Nombres Bordeaux, Volume 14 (2002) no. 2, pp. 439-475 | DOI | Numdam | MR | Zbl

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

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

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

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

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

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

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

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

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

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

[22] Mauduit, Christian; Rivat, Joël 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] Montgomery, Hugh L. Topics in multiplicative number theory, Lecture Notes in Mathematics, 227, Springer, 1971, ix+178 pages | DOI

[24] Ninomiya, Syoiti 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] Parry, William On the $\beta$-expansions of real numbers, Acta Math. Acad. Sci. Hung., Volume 11 (1960), pp. 401-416 | DOI | MR | Zbl

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

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

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

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

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

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

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

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

[34] Wagner, Stephan G. 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] Zeckendorf, Edouard 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