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

Abstract

Let $G=(G_j{)}_{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(\nu )G_0+\cdots +{\epsilon }_{\ell }(\nu )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 }(\nu )G_{\ell }-\cdots -{\epsilon }_j(\nu )G_j<G_j$ holds for $0\le j\le \ell$. In the present paper we study the sum-of-digits function $s_G(\nu )={\epsilon }_0(\nu )+\cdots +{\epsilon }_{\ell }(\nu )$ 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 {\mathbb{R}}_{>0}$ that \[ \sum_{q<x^{\vartheta-\varepsilon}}\max_{z<x}\max_{1\leq h\leq q} \lvert\sum_{\substack{k<z,s_G(k)\equiv r\bmod s\\ k\equiv h\bmod q}}1 -\frac1q\sum_{k<z,s_G(k)\equiv r\bmod s}1\rvert \ll x(\log 2x)^{-A}. \] Here $\vartheta =\vartheta (G)\ge \frac{1}{2}$ can be computed explicitly and we have $\vartheta (G)\to 1$ for $a_1\to \infty$. As an application we show that $\#\{k\le x:s_G(k)\equiv r(\mathrm{mod}s),khas\; at\; most\; two\; prime\; factors\}\gg 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.

22 pages, 1 figure, 1 table