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

Manfred G. Madritsch; Jörg M. Thuswaldner

doi:10.5802/jtnb.1209

Manfred G. Madritsch ^1,² ; Jörg M. Thuswaldner ³

¹ Université de Lorraine, Institut Elie Cartan de Lorraine, UMR 7502, 54506 Vandoeuvre-lès-Nancy, France
² CNRS, Institut Elie Cartan de Lorraine, UMR 7502, 54506 Vandoeuvre-lès-Nancy, France
³ Department of Mathematics and Information Technology, University of Leoben, Franz-Josef-Strasse 18, A-8700 Leoben, Austria

Journal de théorie des nombres de Bordeaux, Tome 34 (2022) no. 2, pp. 449-482.

Résumé
Abstract

Soit $G = {(G_{j})}_{j \geq 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} - \dots - a_{d - 1} X - a_{d}$ son polynôme caractéristique. Il est bien connu que tout entier positif $ν$ possède une écriture glouton unique telle que $ν = ε_{0} (ν) G_{0} + \dots + ε_{ℓ} (ν) G_{ℓ}$ pour $ℓ \in ℕ$ qui satisfait $G_{ℓ} \leq ν < G_{ℓ + 1}$ . Ici les chiffres sont définis de manière récursive par la relation $0 \leq ν - ε_{ℓ} (ν) G_{ℓ} - \dots - ε_{j} (ν) G_{j} < G_{j},$ où $0 \leq j \leq ℓ$ . Dans cet article, nous étudions la somme des chiffres $s_{G} (ν) = ε_{0} (ν) + \dots + ε_{ℓ} (ν)$ 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 (a_{1} + \dots + a_{d} - 1, s) = 1$ on a

\begin{matrix} \sum_{q < x^{ϑ - ε}} max_{z < x} max_{1 \leq h \leq q} | \sum_{\begin{matrix} k < z, s_{G} (k) \equiv r mod s \\ k \equiv h mod q \end{matrix}} 1 - \frac{1}{q} \sum_{k < z, s_{G} (k) \equiv r mod s} 1 | \\ ≪ x {(log 2 x)}^{- A} \end{matrix}

pour tous $x \geq 1$ et $A, ε \in ℝ_{> 0} .$ Dans ce cas, $ϑ = ϑ (G) \geq \frac{1}{2}$ peut être calculé explicitement, et on obtient $ϑ (G) \to 1$ pour $a_{1} \to \infty$ . Comme application nous montrons que si le coefficient $a_{1}$ n’est pas trop petit, alors $# {k \leq x : s_{G} (k) \equiv r (mod s), k$ a au plus deux facteurs premiers $} ≫ x / log x$ . 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.

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

\begin{matrix} \sum_{q < x^{ϑ - ε}} max_{z < x} max_{1 \leq h \leq q} | \sum_{\begin{matrix} k < z, s_{G} (k) \equiv r mod s \\ k \equiv h mod q \end{matrix}} 1 - \frac{1}{q} \sum_{k < z, s_{G} (k) \equiv r mod s} 1 | \\ ≪ x {(log 2 x)}^{- A} . \end{matrix}

Here $ϑ = ϑ (G) \geq \frac{1}{2}$ can be computed explicitly and we have $ϑ (G) \to 1$ for $a_{1} \to \infty$ . As an application we show that $# {k \leq x : s_{G} (k) \equiv r (mod s), k$ has at most two prime factors $} ≫ x / log x$ 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.

Reçu le : 2020-11-21
Accepté le : 2021-05-07
Publié le : 2022-10-24

DOI : 10.5802/jtnb.1209

Classification : 11A63, 11L07, 11N05
Mots clés : Sum of digits, linear recurrence number system, level of distribution, almost prime

Affiliations des auteurs :

Manfred G. Madritsch ^{1, 2} ; Jörg M. Thuswaldner ³

¹ Université de Lorraine, Institut Elie Cartan de Lorraine, UMR 7502, 54506 Vandoeuvre-lès-Nancy, France
² CNRS, Institut Elie Cartan de Lorraine, UMR 7502, 54506 Vandoeuvre-lès-Nancy, France
³ Department of Mathematics and Information Technology, University of Leoben, Franz-Josef-Strasse 18, A-8700 Leoben, Austria

Licence :

CC-BY-ND 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@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/
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://jtnb.centre-mersenne.org/articles/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, Tome 34 (2022) no. 2, pp. 449-482. doi : 10.5802/jtnb.1209. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1209/

Bibliographie
Cité par

[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 $λ^{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 $β$ -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 $β$ -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 $β$ -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 $β$ -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

Cité par Sources :