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.

Soit G=(Gj)j0 une suite strictement croissante des entiers définie par récurrence et telle que G0=1. Soit Xd-a1Xd-1--ad-1X-ad son polynôme caractéristique. Il est bien connu que tout entier positif ν possède une écriture glouton unique telle que ν=ε0(ν)G0++ε(ν)G pour qui satisfait Gν<G+1. Ici les chiffres sont définis de manière récursive par la relation 0ν-ε(ν)G--εj(ν)Gj<Gj,0j. Dans cet article, nous étudions la somme des chiffres sG(ν)=ε0(ν)++ε(ν) 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 avec gcd(a1++ad-1,s)=1 on a

q<xϑ-εmaxz<xmax1hq|k<z,sG(k)rmodskhmodq1-1qk<z,sG(k)rmods1|x(log2x)-A

pour tous x1 et A,ε>0. Dans ce cas, ϑ=ϑ(G)12 peut être calculé explicitement, et on obtient ϑ(G)1 pour a1. Comme application nous montrons que si le coefficient a1 n’est pas trop petit, alors #{kx:sG(k)r(mods),k a au plus deux facteurs premiers}x/logx. En outre, en utilisant le crible de Bombieri, on en déduit un théorème des nombres presque premiers pour sG.

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=(Gj)j0 be a strictly increasing linear recurrent sequence of integers with G0=1 having characteristic polynomial Xd-a1Xd-1--ad-1X-ad. It is well known that each positive integer ν can be uniquely represented by the so-called greedy expansion ν=ε0(ν)G0++ε(ν)G for satisfying Gν<G+1. Here the digits are defined recursively in a way that 0ν-ε(ν)G--εj(ν)Gj<Gj holds for 0j. In the present paper we study the sum-of-digits function sG(ν)=ε0(ν)++ε(ν) 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 with gcd(a1++ad-1,s)=1 we have for each x1 and all A,ε>0 that

q<xϑ-εmaxz<xmax1hq|k<z,sG(k)rmodskhmodq1-1qk<z,sG(k)rmods1|x(log2x)-A.

Here ϑ=ϑ(G)12 can be computed explicitly and we have ϑ(G)1 for a1. As an application we show that #{kx:sG(k)r(mods),k has at most two prime factors}x/logx provided that the coefficient a1 is not too small. Moreover, using Bombieri’s sieve an “almost prime number theorem” for sG 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 :
Accepté le :
Publié le :
DOI : 10.5802/jtnb.1209
Classification : 11A63, 11L07, 11N05
Mots-clés : Sum of digits, linear recurrence number system, level of distribution, almost prime
Madritsch, Manfred G. 1, 2 ; Thuswaldner, Jörg M. 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
@article{JTNB_2022__34_2_449_0,
     author = {Madritsch, Manfred G. and Thuswaldner, J\"org M.},
     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://www.numdam.org/articles/10.5802/jtnb.1209/}
}
TY  - JOUR
AU  - Madritsch, Manfred G.
AU  - Thuswaldner, Jörg M.
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://www.numdam.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 Madritsch, Manfred G.
%A Thuswaldner, Jörg M.
%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://www.numdam.org/articles/10.5802/jtnb.1209/
%R 10.5802/jtnb.1209
%G en
%F JTNB_2022__34_2_449_0
Madritsch, Manfred G.; Thuswaldner, Jörg M. 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://www.numdam.org/articles/10.5802/jtnb.1209/

[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 λ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 β-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 β-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 β-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 β-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

  • Drmota, Michael; Müllner, Clemens; Spiegelhofer, Lukas Primes as Sums of Fibonacci Numbers, Memoirs of the American Mathematical Society, Volume 305 (2025) no. 1537 | DOI:10.1090/memo/1537

Cité par 1 document. Sources : Crossref