# The level of distribution of the sum-of-digits function in arithmetic progressions

Nathan Toumi

<figure><img src="image_1.png" /></figure>

► To cite this version:

Nathan Toumi. The level of distribution of the sum-of-digits function in arithmetic progressions. 2024. hal-05033996

HAL Id: hal-05033996

https://hal.science/hal-05033996v1

Preprint submitted on 14 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The level of distribution of the sum-of-digits function in arithmetic progressions

Nathan Toumi

## Abstract

For $q \ge 2$, $n \in \mathbb{N}$, let $s_q(n)$ denote the sum of the digits of $n$ written in base $q$. Spiegelhofer (2020) proved that the Thue-Morse sequence has level of distribution 1, improving on a former result of Fouvry and Mauduit (1996). In this paper we generalize this result to sequences of type $\{\exp(2\pi i \ell s_q(n)/b)\}_{n \in \mathbb{N}}$ and provide an explicit exponent in the upper bound.

## Contents

<table><tr><td>1</td><td>Introduction</td><td>2</td></tr><tr><td>1.1</td><td>Results on the level of distribution of the sum of digits</td><td>3</td></tr><tr><td>1.2</td><td>Notation</td><td>5</td></tr><tr><td>1.3</td><td>Main results</td><td>6</td></tr><tr><td>2</td><td>Tools</td><td>8</td></tr><tr><td>2.1</td><td>Some technical lemmas</td><td>9</td></tr><tr><td>2.2</td><td>The discrepancy of a real number</td><td>9</td></tr><tr><td>2.3</td><td>The van der Corput inequality</td><td>10</td></tr><tr><td>3</td><td>Base-q generalization of several lemmas</td><td>10</td></tr><tr><td>4</td><td>Proof of Theorem 1.7</td><td>14</td></tr><tr><td>4.1</td><td>Recursion formula and setting up the graph</td><td>14</td></tr><tr><td>4.2</td><td>An effective value of the exponent η₀ in Theorem 1.7</td><td>21</td></tr><tr><td>4.2.1</td><td>Trivial path and Konieczny's path</td><td>21</td></tr><tr><td>4.2.2</td><td>Coding the paths by words</td><td>23</td></tr><tr><td>4.2.3</td><td>Partitioning of the set of the words</td><td>24</td></tr><tr><td>4.2.4</td><td>Switching and coupling with Konieczny's path</td><td>25</td></tr><tr><td>4.2.5</td><td>Final estimates</td><td>26</td></tr><tr><td>5</td><td>Proof of Theorem 1.6</td><td>27</td></tr><tr><td>5.1</td><td>Step 1: Iterating the van der Corput inequality</td><td>28</td></tr><tr><td>5.1.1</td><td>The first iteration</td><td>28</td></tr><tr><td>5.1.2</td><td>The further iterations</td><td>29</td></tr><tr><td>5.2</td><td>Step 2: Digits shifting and cutting</td><td>33</td></tr><tr><td>6</td><td>Proof of Theorem 1.4</td><td>43</td></tr><tr><td>7</td><td>Proof of Theorem 1.2</td><td>46</td></tr><tr><td>A</td><td>Choosing the parameters</td><td>49</td></tr></table>
# 1 Introduction

For $q \ge 2$, each integer $n$ can be uniquely written as

$$n = \sum_{k=0}^{\infty} n_k q^k,$$

where $n_k \in \{0, \dots, q-1\}$ for all $k \ge 0$ are the digits which are zero starting from some finite rank. The sum-of-digits function $s_q$ is a well-studied object in number theory, it is defined for all $n \in \mathbb{N}$ by

$$s_q(n) = s_q\left(\sum_{k=0}^{\infty} n_k q^k\right) = \sum_{k=0}^{\infty} n_k.$$

Although quite simple to define, the sum-of-digits function has raised many questions. A natural question that could be asked is how this function distributes itself within arithmetic progressions. In an influential paper, Gelfond [10] provided a new method to study the sum-of-digits function via exponential sums and product representations. He obtained the following result concerning the distribution of the sum-of-digits function in arithmetic progressions.

**Theorem A** (Gelfond, 1967/68). Let $q, b, m \ge 2$ be integers such that $(b, q-1) = 1$. Then, for all $a \in \{0, \dots, b-1\}$ and for all $r \in \{0, \dots, m-1\}$, we have

$$|\{n < N : s_q(n) \equiv a \pmod b, n \equiv r \pmod m\}| = \frac{N}{bm} + O(N^{\lambda}),$$

where

$$\lambda = \frac{1}{2 \log(q)} \log \frac{q \sin(\pi/2b)}{\sin(\pi/2bq)} < 1.$$

**Remark 1.1.** Rebuilding on work of Morgenbesser, Shallit and Stoll [18] it can be shown that there exist infinitely many $m \ge 1$ such that $\min\{n \ge 1 : s_q(n) \equiv 1 \pmod b, n \equiv 0 \pmod m\} \ge c_b m^{1/(b-1)}$, for some $c_b > 0$ only depending on $b$ (one may consider $m = q^{\ell(b-1)} + q^{\ell(b-2)} + \dots + q^1 + 1$, for instance). Therefore, the implied constant cannot be independent of $m$ (at least for the Thue-Morse sequence). This dependence of the constant on the modulus $m$ is the object of our Bombieri-Vinogradov-type average result, see Theorem 1.2.

In addition to his results in [10], Gelfond proposed several open questions related to the sum-of-digits function. In particular, can we substitute in Theorem A, $s_q(n)$ by $s_q(p)$ for $p$ primes or by $s_q(P(n))$ where $P$ is a polynomial $P$ such that $P(n) \in \mathbb{N}$ for all $n \in \mathbb{N}$? These questions have been addressed in many recent works.

The most emblematic instance of a sequence related to the sum-of-digits function is the (Prouhet-)Thue-Morse sequence defined (for instance) in its multiplicative way by

$$t(n) = (-1)^{s_2(n)} = e\left(\frac{1}{2}s_2(n)\right),$$

where $s_2(n)$ is the sum of the binary digits of the integer $n$, and $e(t) = e^{2\pi it}$. The Thue-Morse sequence is a fundamental object in various areas of mathematics, and in particular in number theory and combinatorics on words (see [1] for an overview). Mauduit and Rivat [17] solved Gelfond's problem on the distribution of $s_q(p)$, $p$ primes, in arithmetic progressions. In the proof of their breakthrough result, the authors introduced several new tools, and most notably an ingenious use of the van der Corput inequality paired with a "carry
propagation lemma”, which, simply put, states that in the addition of a large and a small integer expressed in base-q, the highly significant digits of the large number are rarely affected by the addition. In respect of Gelfond’s problem, we cite the result of Drmota, Mauduit and Rivat [6], who showed that the Thue–Morse sequence is normal along squares.

Spiegelhofer [21] observed that an iterative use of the van der Corput inequality followed by several digits shiftings leads to Gowers norms. He then was able to use the estimate of Gowers norms for the Thue–Morse provided by Konieczny in [13] to conclude. Bounds on these norms have far-reaching applications (see, for instance, [22] for an application for the sum of digits of cubes).

## 1.1 Results on the level of distribution of the sum of digits

Fouvry and Mauduit [9] started the investigation of the level of distribution of the Thue–Morse sequence and its generalizations along arithmetic progressions. For q, b two integers such that $(b, q-1) = 1$, let

$$A_q(y, z; a, b, r, m) = \left| \{ y \le n < z : s_q(n) \equiv a \pmod b, n \equiv r \pmod m \} \right|.$$

The paper [9] is devoted to the base 2.

**Theorem B** (Fouvry/Mauduit, 1996). Let $C_b$ be a constant such that for all $\xi \in \{1/b, \dots, (b-1)/b\}$ we have

$$\int_0^1 \prod_{0 \le n < N} |\cos(\pi(2^n t + \xi))| dt = O(C_b^N), \quad N \to \infty.$$

Let

$$\gamma(\alpha) = 1 + \frac{\log(\beta(\alpha))}{\log 2},$$

where

$$\beta(\alpha) := \sqrt{\max_{t \in \mathbb{R}} |\cos(\pi(t+\alpha)) \cos(\pi(2t+\alpha))|},$$

and set

$$\gamma_b = \max\{\gamma(\alpha) : e(\alpha)^b = 1, \alpha \notin \mathbb{Z}\}.$$

For $A \in \mathbb{R}$, we set $D = x^{1/2} \log(x)^{-A}$. Then, as $x \to +\infty$,

$$\sum_{1 \le m \le D} \max_{1 \le z \le x} \max_{0 \le r < m} \left| A_2(0, z; a, b, r, m) - \frac{z}{bm} \right| = O \left( x^{1+\log(C_b)/\log(2)} D + x^{\gamma_b} \left( D^{3-2\gamma_b+2\log(C_b)/\log(2)} + \log x \right) \right).$$

**Theorem B** allowed them to show that 0.5924 is a level of distribution of the Thue–Morse sequence $t$. More precisely, they showed in [9] the following theorem:

**Theorem C** (Fouvry/Mauduit, 1996). Let $A \in \mathbb{R}$ and $D = x^{0.5924}$. There exists $C > 0$ such that

$$\sum_{1 \le m \le D} \max_{1 \le z \le x} \max_{0 \le r < m} \left| A_2(0, z; 0, 2, r, m) - \frac{z}{2m} \right| \le C x (\log 2x)^{-A}, \quad x \to \infty.$$

They also investigated the level of distribution of the sequence $(s_q(n))_{n \in \mathbb{N}}$ for general base of numeration $q$. In their paper [8, p.340] they proved the following result.

**Theorem D** (Fouvry/Mauduit, 1996). Let $q \ge 2$, $a, b$ be integers such that $(b, q-1) = 1$. Then, for all $x \ge 1$, for all $A \in \mathbb{R}$ and for all $\varepsilon > 0$, we have

$$\sum_{1 \le m \le x^{\theta_q - \varepsilon}} \max_{1 \le z \le x} \max_{0 \le r < m} \left| \sum_{\substack{n < y \\ s_q(n) \equiv a \pmod b \\ n \equiv r \pmod m}} 1 - \frac{1}{m} \sum_{n < y} 1 \right| = O(x(\log 2x)^{-A}), \quad x \to \infty,$$
where $\theta_q$ is defined by

$$ \theta_q = 1 - \frac{\log(M(q))}{\log(q)}, $$

where

$$ M(q) = \begin{cases} \frac{1}{n} \sum_{k=0}^{n-1} \cos\left(\frac{2k+1}{4n}\pi\right)^{-1}, & \text{if } q = 2n; \\ \frac{1}{2n+1} \left(1 + 2 \sum_{k=1}^{n} \cos\left(\frac{k}{2n+1}\pi\right)^{-1}\right), & \text{if } q = 2n+1. \end{cases} $$

Moreover, $\theta_q \to 1$ for $q \to \infty$.

Spiegelhofer [21] improved largely Theorem C in 2020. He obtained that the Thue–Morse sequence has level of distribution equal to 1, which can be seen as an optimal result. This means that for all $\varepsilon > 0$ there exists $\eta > 0$ such that

$$ \sum_{1 \le m \le x^{1-\varepsilon}} \max_{\substack{y,z \ge 0 \\ z-y \le x}} \max_{0 \le r < m} \left| \sum_{\substack{y \le n < z \\ n \equiv r \pmod m}} (-1)^{s_2(n)} \right| \ll_{\varepsilon} x^{1-\eta}. \quad (1) $$

Since $(-1)^{s_2(n)} = 1 - 2(s_2(n) \text{ mod } 2)$ for all $n \ge 0$, the bound (1) follows at once from [21, Theorem 2.1] recalled below

**Theorem E** (Spiegelhofer, 2020). Let $\varepsilon > 0$. There exists $\eta > 0$ such that

$$ \sum_{1 \le m \le x^{1-\varepsilon}} \max_{\substack{y,z \ge 0 \\ z-y \le x}} \max_{0 \le r < m} \left| A(y, z; r, m) - \frac{z-y}{2m} \right| \ll x^{1-\eta}, \quad x \to \infty, $$

where

$$ A(y, z; r, m) = \left| \{ y \le n < z : t(n) = 0, n \equiv r \pmod m \} \right|. $$

The very remarkable part in this theorem is that $m$ can be almost as large as $x$ and there is a maximum over the residues $r$ modulo $m$. The proof of Spiegelhofer allows in principle to get a lower bound for $\eta$ as a function of $\varepsilon$. Explicit results existed before the work of Spiegelhofer. In 2014, Martin, Mauduit, and Rivat [14, Proposition 3] determined such an estimate for sums of type II. Although Spiegelhofer did not provide an explicit value for $\eta$, as we will see, his method allows us to do so. The main challenge in obtaining an explicit value of $\eta$ is to have an effective version of the estimate of the Gowers norm associated with the generalization of the Thue–Morse sequence.

**Theorem F** (Martin/Mauduit/Rivat, 2014). Let $\alpha \in \mathbb{R}/\mathbb{Z}$. Let $(a_n)_{n \in \mathbb{N}}$ and $(b_n)_{n \in \mathbb{N}}$ be sequences of complex numbers such that for all $n \ge 1$, we have $|a_n| \le 1$ and $|b_n| \le 1$. Let $x \ge 2$, $0 < \varepsilon \le 1/2$, $x^\varepsilon \le M$, $N \le x$ and $MN \le x$. We set

$$ \Theta_q := \left(1 - \frac{1}{q}\right) \left(1 - \sqrt{1 - \frac{2q-1}{3q(q-1)}}\right), \\ \eta_q := \max \left( \frac{1}{2} - \frac{\log(4 - 2\sqrt{2})}{2\log 2}, \frac{1}{2} + \frac{\log(1 - \Theta_q)}{4\log 2} \right) $$

and let $\gamma_q \in \mathbb{R}$ be such that

$$ q^{\gamma_q} := 2 \max_{t \in \mathbb{R}} \sqrt{\left| \frac{\sin(q(\alpha - qt)\pi) \sin(q(\alpha - t)\pi)}{\sin((\alpha - qt)\pi) \sin((\alpha - t)\pi)} \right|}. $$

Finally, set

$$ \xi_{q,\varepsilon} := \min \left( \frac{\varepsilon}{6}, \frac{1}{20} \right) \min \left( \frac{1}{2} - \eta_q, 2(1 - \gamma_q) \right). \quad (2) $$

Then

$$ \sum_{M < m \le 2M} \sum_{N < n \le 2N} a_m b_n e(\alpha s_q(mn)) \ll x^{1-\xi_{q,\varepsilon}} \log(x). $$
The number $\xi_{q,\varepsilon}$ is entirely explicit. Spiegelhofer showed that Theorem F allows to get a weak version of Theorem 1.1 in [21]:

For $0 < \varepsilon < 1/2$ and for $D = x^{\varepsilon}$ we have

$$ \sum_{1 \le m \le D} \left| \sum_{\substack{0 \le n \le x \\ n \equiv 0 \pmod m}} (-1)^{s_2(n)} \right| \le C x^{1-\xi'_{2,\varepsilon}}, $$

where

$$ \xi'_{2,\varepsilon} = \frac{1}{1+\varepsilon} \min \left( \frac{\varepsilon}{6}, \frac{1}{20} \right) \min \left( \frac{1}{2} - \eta_2, 2(1-\gamma_2) \right). $$

Since $\alpha$ defined in Theorem F belongs to $\mathbb{R}/\mathbb{Z}$, Theorem F gives information for more general sequences than the Thue–Morse sequence (case $\alpha = 1/2$).

The aim of the present article is to establish the distribution result for the base-$q$ generalization of the Thue–Morse sequence of the strength of Theorem E.

Let $b$ be a nonnegative integer<fnref n="1" /> and $\ell$ be an integer such that

$$ (b, q-1) = 1 \text{ and } 0 < \ell < b. \qquad (3) $$

We consider the sequence $(t_q(n))_{n \ge 0}$ defined by

$$ t_q(n) = e \left( \frac{\ell}{b} s_q(n) \right). \qquad (4) $$

This generalization of the classical Thue–Morse sequence has been studied for a long time under various angles. The first appearance of this sequence was in the framework of $q$-multiplicative sequences in work of Bellman and Shapiro [2] in 1948. Since then, many mathematicians have been interested in the properties of the sequence $(e(\alpha s_q(n)))_{n \in \mathbb{N}}$ (for $\alpha \in \mathbb{R}$). We mention Queffélec in 1979 (see [20]) or Coquet in the same year (see [4]). Mauduit and Rivat [16] obtained a result of Gelfond type for $q$-multiplicative functions along sequences of the form $(\lfloor n^c \rfloor)_{n \in \mathbb{N}}$ for $c > 1$ (so-called Piatetski–Shapiro sequences). Their result has been sharpened by Müllner and Spiegelhofer and coauthors in a series of papers, see [19] or [5]. More recent references can be found in the article of Spiegelhofer [21]. The main difficulties of generalization in base-$q$ lie particularly in handling the Gowers norm associated with our sequence. We require a new recurrence relation (see 4.1) and the weights involved in it are complex without necessarily being real, which makes the proof more difficult since we can no longer use ergodic theorems on Markov chains as it was the case in the work of Konieczny [13, Corollary 2.4].

## 1.2 Notation

This section gathers some notation that will be used in this article. First of all, truncations of the sum-of-digits function play a crucial part in recent works, it will be essential as well in our work. For $\alpha > 0$ an integer, we write

$$ s_q^{\alpha}(n) = s_q(n'), $$

where $n' \equiv n \bmod q^{\alpha}$ and $0 \le n' < q^{\alpha}$; moreover, for $\beta > \alpha$, we write

$$ s_{q}^{\alpha, \beta}(n) = s_{q}^{\beta}(n) - s_{q}^{\alpha}(n). $$

Here is a list of more standard notation.

* $\mathbb{N}$ denotes the set of the integers $\ge 1$.

<footnote n="1">¹Note that we do not impose any condition on $\gcd(\ell, b)$.</footnote>
• $\mathbb{P}$ denotes the set of prime numbers.

• Unless stated otherwise, $p$ will denote a prime number.

• For $A \subset \mathbb{R}$ and $x \in \mathbb{R}$, $1_A(x) = 1$ if $x \in A$ and 0 otherwise.

• For sets $A_i \subset \mathbb{R}$ for $1 \le i \le N$, $\cup A_i$ is $\cup A_i$ and indicates that $A_i \cap A_j = \emptyset$ for all $i \ne j$.

• For $x \in \mathbb{R}$, $\{x\} = x - \lfloor x \rfloor$ and $\langle x \rangle = \lfloor x + \frac{1}{2} \rfloor$.

• For $x \in \mathbb{R}$, $\|x\| = \min_{n \in \mathbb{Z}} |x - n|$.

• For $x > 0$, $\log^+(x) = \max(1, \log(x))$.

• For $x > 0$ and $q > 0$, $\log_q(x) = \frac{\log(x)}{\log(q)}$.

• For two integers $a$ and $b$, the number $(a, b)$ denotes the greatest common divisor of $a$ and $b$.

• For $n \in \mathbb{N}$, $\omega(n)$ denotes the number of prime divisors of $n$ without multiplicity.

• For $n \ge 2$, $P^-(n)$ is the smallest prime divisor of $n$.

• For $n \ge 2$ and for $p \in \mathbb{P}$, $v_p(n)$ is the largest integer $s$ such that $p^s | n$.

• For $n \in \mathbb{N}$, $u_q(n) = s_q^1(n)$.

• For $w = \sum_{i=0}^{k-1} w_i 2^i$, where $w_i \in \{0, 1\}$, we will write

$$ \mathbf{w} = (w_0, \dots, w_{k-1}) $$

as a shorthand (to emphasize the binary digit expansion of the integer $w$). We will sometimes, without further notice, use both the digits vector $\mathbf{w}$ and the represented integer $w$.

• We write, as usual, $e(t) = e^{2\pi it}$.

## 1.3 Main results

The aim of this work is to generalize the result of Spiegelhofer [21] to base-$q$ and general modulus. Moreover, we want to find a value of $\eta$ that is almost optimal (as $\varepsilon$ approaches 0) with respect to the implemented method. Let $m, b \ge 2$ be two integers and $r \in \{0, \dots, m-1\}$. Let $x, y, z$ be three real numbers such that $0 \le y < z$ with $z - y \le x$. We define

$$ N_{y,z}(a, b; r, m) = \left| \{y \le n < z : s_q(n) \equiv a \pmod b, n \equiv r \pmod m\} \right|. \quad (5) $$

**Theorem 1.2.** Let $0 < \varepsilon < 1$. Let $b, q \ge 2$ be two integers such that $(b, q-1) = 1$. There exist a constant $C = C(\varepsilon, b, q) > 0$ and an exponent $\eta = \eta(\varepsilon, b, q) > 0$ such that

$$ \sum_{1 \le m \le x^{1-\varepsilon}} \max_{\substack{y,z \\ 0 \le y \le z \\ z-y \le x}} \max_{r \ge 0} \left| N_{y,z}(a, b; r, m) - \frac{z-y}{bm} \right| \le Cx^{1-\eta}. $$

An admissible value for $\eta$ is given for $\varepsilon < \frac{2}{3}(1 - \lambda)$ (where $\lambda$ is defined in Theorem A) by

$$ \eta(\varepsilon) = \frac{\varepsilon^3 \min(1/4, 3 \log_q(P^-(q)))}{7200 \times 8^{1/\varepsilon} (\log(4q/\varepsilon) + 5b \log(q)/\varepsilon)} \times \exp\left(-\frac{5}{\varepsilon}\left(\log(4q/\varepsilon) + \frac{5b \log(q)}{\varepsilon}\right)\right). \quad (6) $$
Spiegelhofer [21, p.2568, (i)] asked whether we can choose $D = x \log(x)^{-B}$ for some $B > 0$, and have $x \log(x)^{-A}$ as an error term. For our result, it might be possible to get an explicit $\varepsilon$ depending on $x$ tending to 0 ($\varepsilon = 1/(A \log \log x)$), for instance, for some constant $A$). However, our method gives $C$ as a function of $\varepsilon$. It would be interesting to study $C$ in Theorem 1.2 and its degree of dependence in $\varepsilon$.

**Remark 1.3.** For $\varepsilon \to 0$, we have the following equivalent for $\eta$,

$$ \eta \sim \frac{\varepsilon^4 \exp(-\varepsilon^{-2}(25b \log(q) + o(1)))}{36000b \log(q) 8^{\varepsilon^{-1}}} \min(1/4, 3 \log_q(P^{-}(q))). $$

This is evidently a very small quantity. For $q = b = 2$, we used a Python-program to calculate some approximate values for $\eta$ given by (6), see Annexe C.

In order to prove Theorem 1.2, we will prove the following theorem, which is at the heart of the article of Spiegelhofer [21].

**Theorem 1.4.** Let $0 < \delta_1 \le \delta_2 < 1$ be real numbers. Let $b, q \ge 2$ be two integers such that $(b, q - 1) = 1$. Let $x > 0$ be a real number and $D$ be an integer such that

$$ x^{\delta_1} \le D \le x^{\delta_2}. $$

Then there exist a constant $C = C(\delta_1, \delta_2, b, q) > 0$ and an exponent $\eta = \eta(\delta_1, \delta_2, b, q) > 0$ such that

$$ \sum_{D<m \le qD} \max_{\substack{y,z \\ 0 \le y \le z \\ z-y \le x}} \max_{r \ge 0} \left| N_{y,z}(a, b; r, m) - \frac{z-y}{bm} \right| \le Cx^{1-\eta}. $$

An admissible value for $\eta$ is given by

$$ \eta := \frac{\delta_1(1 - \delta_2)^2 \min(1/4, 3 \log_q(P^{-}(q)))}{1800 \times 8^{(1-\delta_2)^{-1}} \left( \log(4q/(1-\delta_2)) + 5b \log(q)/(1-\delta_2) \right)} \\ \times \exp \left( -\frac{5}{1-\delta_2} \left( \log(4q(1-\delta_2)^{-1}) + \frac{5b \log(q)}{1-\delta_2} \right) \right). \qquad (7) $$

**Remark 1.5.** For $\delta_2 \to 1$, we have the following equivalent for $\eta$,

$$ \eta \sim \frac{\delta_1(1 - \delta_2)^3}{9000b \log(q) 8^{(1-\delta_2)^{-1}}} \times \exp \left( \frac{-25b \log(q) + o(1)}{(1 - \delta_2)^2} \right) \times \min(1/4, 3 \log_q(P^{-}(q))). $$

To prove this theorem, we will follow Spiegelhofer's approach [21]. A standard way to detect arithmetic progressions is to use exponential sums. In the following theorems we prove some cancellation on average over the modulus of the arithmetic progression. Theorem 1.4 is a consequence of Theorem 1.6 below, which might have applications in other problems as well.

**Theorem 1.6.** Let $\rho_2 \ge \rho_1 > 0$. Let $b, q \ge 2$ be two integers such that $(b, q - 1) = 1$ and let $N, D > 1$ be two integers such that

$$ N^{\rho_1} \le D \le N^{\rho_2}. $$

Let $\ell \in \{1, \dots, b-1\}$. and $\xi$ be a real number. We define $S_0(N, D, \xi)$ by

$$ S_0 = S_0(N, D, \xi) = \sum_{D \le m < qD} \max_{a \ge 0} \left| \sum_{0 \le n < N} e \left( \frac{\ell}{b} s_q(nm + a) \right) e(n\xi) \right|. $$

Then there exist $C = C(b, q, \rho_1, \rho_2) > 0$ and $\eta = \eta(b, q, \rho_1, \rho_2) > 0$ such that

$$ \left| \frac{S_0(N, D, \xi)}{D} \right| \le CN^{1-\eta}. $$
An admissible value for $\eta$ is given by

$$ \eta = \frac{\rho_1 \min(1/4, 3 \log_q (P^-(q)))}{8^{1+\rho_2}(288\rho_2 + 300)(3\rho_2 + 2)(\log((3\rho_2 + 4)q) + b\log(q)(3\rho_2 + 5))} \times \exp(-(3\rho_2 + 5)(\log((3\rho_2 + 4)q) + (3\rho_2 + 5)b\log(q))). $$

The proof idea is to apply the van der Corput inequality (and variations thereof) a certain number of times in order to remove digits in the underlying quantities and to reduce the estimate of the exponential sums to estimates of Gowers norms for the sequence $(t_q(n))_{n \ge 1}$. In this article, we prove the following property of Gowers norms for this sequence.

**Theorem 1.7.** Let $k \ge 3$ be an integer and $0 < \ell < b$. and set

$$ K = \left\lfloor \frac{\log(k)}{\log(q)} \right\rfloor + 1. $$

Let $b, q$ be two integers such that $(b, q - 1) = 1$. We define

$$ \eta_0 := \frac{1}{\log(q)(K + (k + 1)b)q^{(k+1)(K+b(k+1)})} $$

Then, as $\rho \to \infty$,

$$ \frac{1}{q^{(k+1)\rho}} \sum_{\substack{0 \le n < q^\rho \\ 0 \le h_0, \dots, h_{k-1} < q^\rho}} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q(n + \mathbf{w} \cdot \mathbf{h}) \right) \ll q^{-\eta_0 \rho}. $$

Moreover, we get the same formula for the function $s_q^\rho$: as $\rho \to +\infty$,

$$ \frac{1}{q^{(k+1)\rho}} \sum_{\substack{0 \le n < q^\rho \\ 0 \le h_0, \dots, h_{k-1} < q^\rho}} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^\rho(n + \mathbf{w} \cdot \mathbf{h}) \right) \ll q^{-\eta_0 \rho}. $$

This theorem generalizes the result obtained by Konieczny in his article [13] in 2019. As Konieczny commented in [13, Remark 2.5], the calculation of the spectral gap of the matrix $(p_{\mathbf{r}_0, \mathbf{r}_1})_{(\mathbf{r}_0, \mathbf{r}_1) \in \Re^2}$, where $p_{\mathbf{r}_0, \mathbf{r}_1}$ is defined in (28) and $\Re$ is defined Lemma 4.4, yields another admissible value for $q = b = 2$. However, we will use a different approach, since $p_{\mathbf{r}_0, \mathbf{r}_1}$ is not necessarily a real number for general $q$ and $b$. The case $q = b = 2$ leads us to the Gowers norm estimate for the classical Thue-Morse sequence. We mention also the result of Byszewski, Konieczny and Müllner [[3], Theorem A]. They showed that all automatic sequence orthogonal to periodic sequences are highly Gowers uniform (in the sense of [[3], (1), p.2]). Note that $\eta_0$ is not explicit in their work (as it is in Konieczny's result in [13]), and the case $s_q \bmod b$ is not mentioned explicitly.

The structure of the article is as follows. In Sections 2 and 3 we collect several lemmas of a technical nature that we use throughout our article. They concern classical (or standard) results on discrepancy estimates, various types of the van der Corput inequality, as well as base-$q$ generalizations of some lemmas of [21] regarding carry propagations, the cutting procedure of digits etc. We will proceed along the lines of [21] and will make frequent use of Farey fractions. The reader will find a short account on Farey fractions in Annexe B. Section 4 is devoted to the Proof of Theorem 1.7, in Section 5 we prove Theorem 1.6. Finally, in Sections 6 and 7 we give the proofs of Theorem 1.4 and Theorem 1.2.

## 2 Tools

In this section we collect various definitions and lemmas that will be used throughout the article.
## 2.1 Some technical lemmas

The following lemma will be used at the end of the proof of Theorem 1.6. This inequality allows us to reduce it to Theorem 1.4.

**Lemma 2.1.** Let $x \le y \le z$ be real numbers and $(a_n)_{n \in \mathbb{N}} \in \mathbb{C}^\mathbb{N}$ for $x \le n < z$. Then,

$$ \left| \sum_{x \le n < y} a_n \right| \le \int_0^1 \min(y - x + 1, \|\xi\|^{-1}) \left| \sum_{x \le n < z} a_n e(n\xi) \right| d\xi. $$

*Proof.* We refer the reader to [19, Lemma 3.7]. □

The following elementary lemma gives a bound on the number of solutions of a certain congruence. It will be used during the proof of Theorem 1.6.

**Lemma 2.2.** Let $k \in \mathbb{N}^*$, $\rho \ge \gamma > 0$ be integers. Let $q = p_1^{\alpha_1} \cdots p_r^{\alpha_r} \ge 2$ and $M \in \mathbb{N}^*$ such that for all $1 \le i \le r$, $\alpha_i \ge 1$, $p_i^\gamma \nmid M$. Then, for all $0 \le a < q^\rho$, we have

$$ |\{h \in \{0, \dots, q^\rho - 1\} : hM \equiv a \pmod{q^\rho}\}| \le q^\gamma. $$

*Proof.* If $(M, q^\rho) \nmid a$, then the congruence $hM \equiv a \pmod{q^\rho}$ has no solution $h$. Otherwise this congruence is equivalent to

$$ h \frac{M}{(M, q^\rho)} \equiv \frac{a}{(M, q^\rho)} \pmod{\frac{q^\rho}{(M, q^\rho)}}. $$

Since $(\frac{M}{(M, q^\rho)}, \frac{q^\rho}{(M, q^\rho)}) = 1$ the number of solutions $h \in \{0, \dots, q^\rho - 1\}$ is $(M, q^\rho)$. Since $p_i^\gamma \nmid M$ for all $1 \le i \le r$, we have $v_{p_i}(M) < \gamma$. Moreover, $v_{p_i}(q^\rho) \ge \rho$. Therefore, $(M, q^\rho) \le q^\gamma$. □

**Proposition 2.3.** The following properties hold true:

(1) Let $0 < \varepsilon \le \frac{1}{2}$. We suppose that $a, b \in \mathbb{R}$ such that $\|a\| < \varepsilon$ and $\|b\| \ge \varepsilon$. Then

$$ |a+b| = \left\lfloor a + \frac{1}{2} \right\rfloor + |b|. \qquad (8) $$

(2) Let $a \in \mathbb{R}$ and $n \in \mathbb{N}$. Then

$$ \|na\| \le n\|a\|. \qquad (9) $$

(3) Let $a \in \mathbb{R}$, $\varepsilon > 0$ and $n \in \mathbb{N}$ such that $\|a\| < \varepsilon$ and $2n\varepsilon < 1$. Then

$$ \langle na \rangle = n\langle a \rangle. \qquad (10) $$

*Proof.* We refer the reader to [21, Lemma 4.1]. □

## 2.2 The discrepancy of a real number

**Definition 2.4.** Let $\alpha \in \mathbb{R}$ and $N \ge 1$ be an integer. We define the $N$-discrepancy of $\alpha$, denoted as $D_N(\alpha)$, by

$$ D_N(\alpha) = \sup_{0 \le x \le 1} \left| \frac{1}{N} \sum_{0 \le n < N} \mathbb{1}_{[0, x[+y+\mathbb{Z}]}(n\alpha) - x \right|. $$

The notion of $N$-discrepancy appears naturally in the following result which is used by Müllner and Spiegelhofer [19, Lemma 3.3].

**Proposition 2.5.** Let $J$ be an interval in $\mathbb{R}$ containing $N$ integers. Let $\alpha, \beta \in \mathbb{R}$. Let $t, T, \ell, L$ be integers such that $0 \le t < T$ and $0 \le \ell < L$. Then

$$ \left| \{n \in J : \frac{t}{T} \le \{n\alpha + \beta\} < \frac{t+1}{T}, \lfloor n\alpha + \beta \rfloor \equiv \ell \pmod{L} \} \right| = \frac{N}{LT} + O\left(ND_N\left(\frac{\alpha}{L}\right)\right) $$

with an absolute implied constant.
## 2.3 The van der Corput inequality

As in previous articles on the sum-of-digits function, the van der Corput inequality and its variations play a major role. The original version can for example be found in the book of Graham/Kolesnik [11, (2.3.4)].

**Lemma 2.6.** Let $0 \le a < b$ be two integers and set $I = [a, b]$. Let $f: \mathbb{N} \to \mathbb{C}$ be a complex-valued function such that $f(n) = 0$ for $n \notin I$. Let $0 < H \le |I|$ be an integer. We have

$$ \left| \sum_{n \in I} e(f(n)) \right|^2 \le 2 \frac{|I|^2}{H} + 4 \frac{|I|}{H} \sum_{1 \le h < H} \left| \sum_{\substack{n \in I \\ n+h \in I}} e(f(n+h) - f(n)) \right|. $$

Mauduit and Rivat [15, Lemme 17] generalized the van der Corput inequality for general shifts, and showed that it can be used, in an elegant manner, to remove lower-placed digits. As we will see later, removing iteratively windows of digits via this inequality, allows to get a small window of digits only to consider in the end. For the purpose of handling better these iterations, we rewrite their inequality with a single sum over all $h \in \{0, \dots, H-1\}$, without isolating the diagonal term ($h=0$).

**Lemma 2.7.** Let $0 \le a < b$ be two integers and set $I = [a, b]$. Let $f: \mathbb{N} \to \mathbb{C}$ be a complex valued function such that $f(n) = 0$ for $n \notin I$. Let $K > 0$ be an integer. Let $0 < H \le |I|$ be an integer. We have

$$ \left| \sum_{n \in I} e(f(n)) \right|^2 \le 2 \frac{|I| + K(H-1)}{H} \sum_{0 \le h < H} \left| \sum_{\substack{n \in I \\ n+Kh \in I}} e(f(n+Kh) - f(n)) \right|. $$

# 3 Base-q generalization of several lemmas

In this section, we generalize to base-q several lemmas used by Spiegelhofer in [21] for the base 2. We refer the reader to the beginning of Section 1.2 for the notation that we use in the following lemmas. The first lemma will be used when we begin to perform many digits shiftings, in order to remove a large portion of the digits of the integers and to be able to concentrate our attention to a small window of digits only (see [21, p.2575]).

**Lemma 3.1** (Cutting out digits). Let $\alpha, u_0, u_1 \ge 0$ be integers. Let $\beta > \alpha$. We have the equality

$$ s_q^{\beta}(u_0 + q^{\alpha}u_1) - s_q^{\beta}(u_0) = s_q^{\alpha, \beta}(u_0 + q^{\alpha}u_1) - s_q^{\alpha, \beta}(u_0). $$

*Proof.* By the definition of $s_q^{\alpha, \beta}$, we have

$$ s_q^{\alpha, \beta}(u_0 + q^{\alpha}u_1) - s_q^{\alpha, \beta}(u_0) = s_q^{\beta}(u_0 + q^{\alpha}u_1) - s_q^{\beta}(u_0) - (s_q^{\alpha}(u_0 + q^{\alpha}u_1) - s_q^{\alpha}(u_0)), $$

and we observe that $s_q^{\alpha}(u_0 + q^{\alpha}u_1) - s_q^{\alpha}(u_0) = 0$ since $u_0 + q^{\alpha}u_1 \equiv u_0 \pmod{q^{\alpha}}$. $\square$

The next Lemma allows us to justify the stability of the recursion formula when we work with $s_q^{\rho}$ instead of $s_q$ in the proof of 1.7.

**Lemma 3.2.** Let $\rho \ge 2$. For all $n \in \mathbb{N}$, we have

$$ s_q^{\rho}(n) = s_q^{\rho-1}\left(\left\lfloor \frac{n}{q} \right\rfloor\right) + u_q(n). $$

The following property is useful to transform the sum-of-digits function $s_q$ into a periodic function $s_q^{\lambda}$, at the expense of a manageable error. This transformation will occur during the first iteration of the van der Corput inequality. Mauduit and Rivat [17, Lemme 5, p.1607] have used this method in their resolution of the problem of Gelfond regarding the distribution of $s_q$ along primes. It has since then be applied in various contexts and shown to be very useful. The following version is a generalization of [21, Lemma 4.5]. Note that we will only use the case $\alpha, \beta \in \mathbb{N}$ but we state the more general (Beatty sequence) version since the proof is not more difficult and the analogy to [21] is more apparent in that way.
**Lemma 3.3** (Carry propagation lemma). Let $r > 0$, $\lambda \ge 1$, $N \ge 1$ be integers and $\alpha, \beta \in \mathbb{R}$ with $\alpha > 0$ and $\beta \ge 0$. Let $I \subset [0, +\infty[$ be an interval in $\mathbb{R}$ containing exactly $N$ consecutive integers. Then

$$ \left| \left\{ n \in I : s_q(\lfloor \alpha(n+r) + \beta \rfloor) - s_q(\lfloor \alpha n + \beta \rfloor) \neq s_q^{\lambda}(\lfloor \alpha(n+r) + \beta \rfloor) - s_q^{\lambda}(\lfloor \alpha n + \beta \rfloor) \right\} \right| < r \left( \frac{N\alpha}{q^{\lambda}} + 2 \right). \quad (11) $$

*Proof.* If $r\alpha \ge q^{\lambda}$ then $r \left( \frac{N\alpha}{q^{\lambda}} + 2 \right) \ge N$ and the result follows immediately. We may therefore suppose that $r\alpha < q^{\lambda}$. Let $n \in I$ such that $n\alpha + \beta \in [kq^{\lambda}, (k+1)q^{\lambda}]$ for some $k \in \mathbb{N}$ that we will make precise later. If $n\alpha + \beta + r\alpha \in [kq^{\lambda}, (k+1)q^{\lambda}]$, then $n$ is not in the set involved on the left hand side of (11). We therefore only need to consider the integers $n$ such that

$$ n\alpha + \beta + r\alpha \ge (k+1)q^{\lambda}. $$

This second condition (combined with the condition $n\alpha + \beta \in [kq^{\lambda}, (k+1)q^{\lambda}]$) allows us to estimate $n$. We obtain

$$ \frac{(k+1)q^{\lambda} - \beta - r\alpha}{\alpha} \le n < \frac{(k+1)q^{\lambda} - \beta}{\alpha}, $$

and the number of such integers is therefore bounded by

$$ \frac{(k+1)q^{\lambda} - \beta}{\alpha} - \frac{(k+1)q^{\lambda} - \beta - r\alpha}{\alpha} = r. $$

Finally, we need to bound the number of possible $k$. Write $I = [a_1, a_2[$. Since $n \le a_2$, we have

$$ a_2\alpha + \beta + r\alpha \ge (k+1)q^{\lambda}, $$

which implies

$$ k \le \frac{a_2\alpha + \beta + r\alpha}{q^{\lambda}} - 1. $$

Moreover, we have

$$ (k+1)q^{\lambda} > a_1\alpha + \beta, $$

and

$$ k > \frac{a_1\alpha + \beta}{q^{\lambda}} - 1. $$

Therefore, the number of possible $k$ is bounded by

$$ \frac{(a_2 - a_1)\alpha + r\alpha}{q^{\lambda}} \le \frac{(N+1)\alpha}{q^{\lambda}} + 1 < \frac{N\alpha}{q^{\lambda}} + 2, $$

where in the last step we used $\alpha \le r\alpha < q^{\lambda}$. This concludes the proof.

□

The following lemma provides a bound on the number of $n < N$ such that $\|n\alpha + \beta\|$ is close to an integer. It is the analogue in base-$q$ of the arguments given by Spiegelhofer [21, p.2575]. This lemma will be useful to us during the digit-shifting phase.

**Lemma 3.4.** Let $N > 1$ be an integer, $\sigma > 1$ and $H \in \mathbb{N}$ such that $H < q^{\sigma-1}$. Moreover, let $\alpha, \beta \in \mathbb{R}$. We have

$$ |\{n \in \{0, \dots, N-1\} : \|n\alpha + \beta\| < H/q^{\sigma}\}| \le N D_N(\alpha) + \frac{2HN}{q^{\sigma}}. $$
Proof. This follows by elementary interval translations and the definition of the discrepancy, i.e.

$$
\begin{align*}
|\{n \in \{0, \dots, N-1\} : \|n\alpha + \beta\| < H/q^{\sigma}\}| &= |\{n \in \{0, \dots, N-1\} : n\alpha + \beta \in (\mathbb{Z} + [-H/q^{\sigma}, H/q^{\sigma}])\}|, \\
&= |\{n \in \{0, \dots, N-1\} : n\alpha \in (\mathbb{Z} + [0, 2H/q^{\sigma}] - \beta - H/q^{\sigma})\}| \\
&\le \frac{2HN}{q^{\sigma}} + N D_N(\alpha).
\end{align*}
$$

□

As each digit shift introduces an error term involving the discrepancy, and since we perform (k - 1) such shifts, the following lemma will be used to estimate the overall error generated by multiple digit shifts. The proof is available in the article of Müllner and Spiegelhofer [19, Lemma 3.4, p.704] for q = 2, but holds for each q ≥ 2 (with the obvious modifications in the proof).

**Proposition 3.5.** Let $q \ge 2$. There exists an absolute constant $C$, such that for all $m, n, N \in \mathbb{N}$,

$$
\sum_{0 \le d < q^m} D_N \left( \frac{d}{q^m} \right) \le C \frac{N + q^m}{N} (\log^+ N)^2.
$$

The following lemma is at the heart of the approximation process when we discard digits in the iterations of
the van der Corput inequality, see [21, Lemma 5.1]. We use standard notation concerning Farey fractions,
see Annexe B.

**Lemma 3.6.** Let $\mu, \nu, \sigma, \gamma$ be integers with $\nu + 1 \ge 3\gamma$ and $k \ge 3$ be an integer.
We define, for $m \in \{0, \dots, q^{\nu+1} - 1\}$,

$$
\mathfrak{M}_1 = P_{q^\sigma} \left( \frac{P_{q^{2\mu+2\sigma}} (m/q^{2\mu})}{q^{(k-2)\mu}} \right).
$$

For $1 < i < k - 1$ we set

$$
\mathfrak{M}_i = P_{q^\sigma} \left( \frac{P_{q^{\mu+2\sigma}} (m/q^{(i+1)\mu})}{q^{(k-i-1)\mu}} \right)
$$

and

$$
\mathfrak{M}_{k-1} = P_{q^{\sigma}} \left( \frac{P_{q^{\mu+\sigma}} (m/q^{k\mu})}{q^{k\mu}} \right),
$$

where $P_n(\alpha)$ is the numerator of the Farey fraction of order $n$ “closest” to $\alpha$, according to Definition B.5.
Let

$$
A = \{m \in \{0, \dots, q^{\nu+1} - 1\} : \exists i \in \{1, \dots, k-1\}, \exists p \mid q, p^{3\gamma} \mid \mathfrak{M}_i\}.
$$

Then

$$
|A| = O_q(q^{\nu+1-3\gamma \log_q(P^-(q))}). \tag{12}
$$

Proof. To make the proof easier to read, we will work only with $\mathfrak{M}_1$, the other cases ($2 \le i \le k-1$) are handled almost similarly. We refer the reader to the article by Spiegelhofer [21, Lemma 5.1] to see the slight changes that appear for the cases $2 \le i \le k-1$. We first deal with the case where $(m,q)=1$ (Case 1). Some minor changes and estimates will allow us to handle the general case (Case 2).

Case 1: $(m, q) = 1$.

As a first step, we establish the following formula for $\mathfrak{M}_1$:

$$
\mathfrak{M}_1 = P_{q^{\sigma}}(m_0/q^{(k-2)\mu}) + m_1 Q_{q^{\sigma}}(m_0/q^{(k-2)\mu}), \quad (13)
$$
with $m_0$ defined below. To begin with, we remark that $\frac{m}{q^{2\mu}} \in \mathcal{F}_{q^{2\mu+2\sigma}}$, thus

$$ \frac{m}{q^{2\mu}} = \frac{P_{q^{2\mu+2\sigma}}(m/q^{2\mu})}{Q_{q^{2\mu+2\sigma}}(m/q^{2\mu})}. $$

Moreover, since $(m, q) = 1$, we have

$$ P_{q^{2\mu+2\sigma}}(m/q^{2\mu}) = m. \qquad (14) $$

By performing the Euclidean division of $m$ by $q^{(k-2)\mu}$ and using the condition $m < q^{\nu+1}$, we get

$$ m = m_0 + q^{(k-2)\mu}m_1, $$

with

$$ \begin{aligned} m_0 &\in \{0, \dots, q^{(k-2)\mu} - 1\}, \\ m_1 &\in \{0, \dots, q^{\nu+1-(k-2)\mu} - 1\}. \end{aligned} $$

We write

$$ \frac{P}{Q} \le \frac{m_0}{q^{(k-2)\mu}} \le \frac{P'}{Q'}, $$

where $\frac{P}{Q}$ and $\frac{P'}{Q'}$ are neighbours in $\mathcal{F}_{q^\sigma}$. Thus, by adding $m_1$ to each term in the double inequality, we have

$$ \frac{P + m_1 Q}{Q} \le \frac{m}{q^{(k-2)\mu}} \le \frac{P' + m_1 Q'}{Q'}. \qquad (15) $$

Since $(P, Q) = 1$ and $(P', Q') = 1$, all the fractions are irreducible. Also, since $\frac{P}{Q}$ and $\frac{P'}{Q'}$ are neighbours in $\mathcal{F}_{q^\sigma}$, then, by translation, $(P + m_1 Q)/Q$ and $(P' + m_1 Q')/Q'$ are still neighbours in $\mathcal{F}_{q^\sigma}$. We distinguish two cases according to the place of $m_0/q^{(k-2)\mu}$ with respect to the midpoint of the Farey interval $[P/Q, P'/Q']$. First we suppose that

$$ \frac{m_0}{q^{(k-2)\mu}} \le \frac{P + P'}{Q + Q'} \qquad (16) $$

Then, by Definition B.5, we have

$$ \frac{P}{Q} = \frac{P_{q^\sigma}(m_0/q^{(k-2)\mu})}{Q_{q^\sigma}(m_0/q^{(k-2)\mu})}. $$

Moreover, since we have

$$ \begin{aligned} \frac{m}{q^{(k-2)\mu}} &= \frac{m_0}{q^{(k-2)\mu}} + m_1 \\ &\le \frac{P + P'}{Q + Q'} + m_1 \\ &\le \frac{(P + m_1 Q) + (P' + m_1 Q')}{Q + Q'}, \end{aligned} $$

the number $\frac{m}{q^{(k-2)\mu}}$ is smaller than the midpoint of $\frac{P + m_1 Q}{Q}$ and $\frac{P' + m_1 Q'}{Q'}$. This implies by (14) and (15) that

$$ \begin{aligned} \mathfrak{M}_1 &= P_{q^\sigma} \left( \frac{P_{q^{2\mu+2\sigma}}(m/q^{2\mu})}{q^{(k-2)\mu}} \right) \\ &= P + m_1 Q \\ &= P_{q^\sigma}(m_0/q^{(k-2)\mu}) + m_1 Q_{q^\sigma}(m_0/q^{(k-2)\mu}), \end{aligned} $$
as announced in (13). For the second case, we suppose now that

$$ \frac{m_0}{q^{(k-2)\mu}} > \frac{P + P'}{Q + Q'} \qquad (17) $$

A similar calculation as above shows that

$$ \begin{aligned} \mathfrak{M}_1 &= P_{q^\sigma} \left( \frac{P_{q^{2\mu+2\sigma}}(m/q^{2\mu})}{q^{(k-2)\mu}} \right) \\ &= P' + m_1 Q' \\ &= P_{q^\sigma}(m_0/q^{(k-2)\mu}) + m_1 Q_{q^\sigma}(m_0/q^{(k-2)\mu}). \end{aligned} $$

In both cases we arrive at the same conclusion, identity (13).

We now turn our attention to (12). We suppose that there exists $p|q$ such that $p^{3\gamma} | \mathfrak{M}_1$. We observe that $p \nmid Q_{q^\sigma}(m_0/q^{(k-2)\mu})$ since otherwise, by (13), $p$ would divide $P_{q^\sigma}(m_0/q^{(k-2)\mu})$ which contradicts

$$ (Q_{q^\sigma}(m_0/q^{(k-2)\mu}), P_{q^\sigma}(m_0/q^{(k-2)\mu})) = 1. $$

For a fixed number $m_0 \in \{0, \dots, q^{(k-2)\mu} - 1\}$, the number of $m_1 \in \{0, \dots, q^{\nu+1-(k-2)\mu} - 1\}$ such that

$$ m_1 Q_{q^\sigma}(m_0/q^{(k-2)\mu}) \equiv -P_{q^\sigma}(m_0/q^{(k-2)\mu}) \pmod{p^{3\gamma}} $$

is bounded by $q^{\nu+1-(k-2)\mu}/p^{3\gamma}$. Thus, the number of $m \in \{0, \dots, q^{\nu+1} - 1\}$ such that $p^{3\gamma} | \mathfrak{M}_1$ is at most $q^{\nu+1}/p^{3\gamma}$.

**Case 2:** $(m, q) > 1$.

The only difference here with respect to the former case lies in the beginning of the argument. The fraction $m/q^{2\mu}$ is no longer irreducible but it suffices to reduce it to $m'/q'$ (where $(m', q') = 1$) and to proceed exactly in the same way as above with the previous argument with $q', m'$ in place of $q, m$.

We now collect all the information to estimate the cardinality of the set $A$ of the statement. We get

$$ \begin{aligned} |A| &\le \sum_{\substack{p \in \mathbb{P} \\ p|q}} |\{m \in \{0, \dots, q^{\nu+1} - 1\} : \exists i \in \{1, \dots, k-1\}, p^{3\gamma} | \mathfrak{M}_i\}| \\ &\le q^{\nu+1} \sum_{\substack{p \in \mathbb{P} \\ p|q}} p^{-3\gamma} \\ &\le \omega(q) q^{\nu+1} P^{-}(q)^{-3\gamma}. \end{aligned} $$

□

# 4 Proof of Theorem 1.7

## 4.1 Recursion formula and setting up the graph

Throughout this section, in view of a further use of Lemma 3.6, we use $k \ge 3$ (The arguments of this section still remain valid for $k = 2$). Recall that we use throughout the article the assumption (3),

$$ (b, q-1) = 1 \text{ and } 0 < \ell < b. $$
For $w \in \{0, \dots, 2^k - 1\}$ we write $w = \sum_{0 \le i \le k-1} w_i 2^i$ with $w_i \in \{0, 1\}$ and $\mathbf{w} = (w_0, \dots, w_{k-1})$ the vector of the binary digits of the integer $w$ (we will often switch from the vector representation to the integer without giving further indication.) We denote

$$t_q^{(w)}(n) = e\left((-1)^{s_2(w)} \frac{\ell}{b} s_q(n)\right). \qquad (18)$$

We observe that (18) is a generalization of (4). The factor $(-1)^{s_2(w)}$ appears naturally in the context of Gowers norms, as we will see later. Let $\mathbf{r}_0 = (r_{0,w})_{w \in \{0, \dots, 2^k-1\}} \in \mathbb{Z}^{2^k}$. For $\rho \ge 0$, we consider

$$A(\rho, \mathbf{r}_0) = \frac{1}{q^{(k+1)\rho}} \sum_{\substack{0 \le n < q^\rho \\ \mathbf{h}=(h_0, \dots, h_{k-1}) \in \{0, \dots, q^\rho-1\}^k}} \prod_{w=0}^{2^k-1} t_q^{(w)}(n + \mathbf{w} \cdot \mathbf{h} + r_{0,w}), \qquad (19)$$

where $\mathbf{w} \cdot \mathbf{h}$ is the usual dot-product defined by

$$\mathbf{w} \cdot \mathbf{h} = \sum_{i=0}^{k-1} w_i h_i.$$

In the first step we establish a recurrence formula for $A(\rho, \mathbf{r}_0)$ based on the $q$-multiplicativity of $(t_q^{(w)}(n))_{n \in \mathbb{N}}$. This recurrence relation can be interpreted as a recurrence relation of the type

$$X_{\rho} = M X_{\rho-1},$$

where $X_\rho$ is a vector and $M$ a matrix such that $|M|$ is stochastic. This will lead us to examine the underlying “probabilistic graph” related to $M$. For the first step, we follow the argument given by Konieczny in the proof of [13, Lemma 2.1, p.1902].

**Lemma 4.1.** Let $k \ge 3$ be an integer. For any fixed $\mathbf{r}_0 \in \mathbb{Z}^{2^k}$, the sequence $(A(\rho, \mathbf{r}_0))_{\rho \ge 1}$ satisfies the recursion formula

$$A(\rho, \mathbf{r}_0) = \frac{1}{q^{k+1}} e\left(\frac{\ell}{b} \sum_{w=0}^{2^k-1} (-1)^{s_2(w)} r_{0,w}\right) \\ \times \sum_{\mathbf{e}=(e_0, \dots, e_k) \in \{0, \dots, q-1\}^{k+1}} A(\rho-1, \delta(\mathbf{r}_0; \mathbf{e})) e\left(-\frac{q\ell}{b} \sum_{w=0}^{2^k-1} (-1)^{s_2(w)} \delta(\mathbf{r}_0; \mathbf{e})_w\right),$$

where $\delta(\mathbf{r}_0; \mathbf{e}) = (\delta(\mathbf{r}_0; \mathbf{e})_w)_{w \in \{0, \dots, 2^k-1\}} \in \mathbb{Z}^{2^k}$ is the vector defined by

$$\delta(\mathbf{r}_0; \mathbf{e})_w = \left\lfloor \frac{r_{0,w} + (1, \mathbf{w}) \cdot \mathbf{e}}{q} \right\rfloor, \qquad (20)$$

for all $w \in \{0, \dots, 2^k - 1\}$, with the shorthand notation $(1, \mathbf{w}) \cdot \mathbf{e} = e_0 + \sum_{i=1}^k w_{i-1} e_i$.

*Proof.* Let $0 \le n < q^\rho$ and $h = (h_0, \dots, h_{k-1})$ with $0 \le h_i < q^\rho$ for $0 \le i \le k-1$. Using the Euclidean division, there exists a unique $(2k+2)$-tuple of integers $(n', h'_0, \dots, h'_{k-1}, e'_0, \dots, e'_k)$ satisfying $0 \le n' < q^{\rho-1}$, $0 \le h'_i < q^{\rho-1}$ ($1 \le i \le k-1$) and $0 \le e'_i < q$ ($0 \le i \le k$) and such that

$$\begin{align*} n &= qn' + e_0, \\ h_0 &= qh'_0 + e_1, \\ \vdots \\ h_{k-1} &= qh'_{k-1} + e_k. \end{align*}$$
Summing up, for all $\mathbf{w} = (w_0, \dots, w_{k-1})$, we have

$$n + \mathbf{w} \cdot \mathbf{h} = q(n' + \mathbf{w} \cdot \mathbf{h}') + (1, \mathbf{w}) \cdot \mathbf{e}.$$

By the uniqueness of the parameters involved in the Euclidean division, we then observe that

$$Q := \{n + \mathbf{w} \cdot \mathbf{h} | w \in \{0, \dots, 2^k - 1\} \\ = \{q(n' + \mathbf{w} \cdot \mathbf{h}') + (1, \mathbf{w}) \cdot \mathbf{e} | w \in \{0, \dots, 2^k - 1\}\}$$

is in bijection with the cube

$$Q' = \{n' + \mathbf{w} \cdot \mathbf{h}' | w \in \{0, \dots, 2^k - 1\}\}.$$

By the definition of $A(\rho, \mathbf{r}_0)$ (see (19)),

$$A(\rho, \mathbf{r}_0) = \frac{1}{q^{(k+1)\rho}} \sum_{\substack{0 \le n' < q^{\rho-1} \\ \mathbf{h}' = (h'_0, \dots, h'_{k-1}) \in \{0, \dots, q^{\rho-1}-1\}^k \\ \mathbf{e} = (e_0, \dots, e_k) \in \{0, \dots, q-1\}^{k+1}}} \prod_{w=0}^{2^k-1} t_q^{(w)}(q(n' + \mathbf{w} \cdot \mathbf{h}') + (1, \mathbf{w}) \cdot \mathbf{e} + r_{0,w}). \quad (21)$$

For all $0 \le n' < q^{\rho-1}$, $\mathbf{h}' \in \{0, \dots, q^{\rho-1}-1\}^k$ and $\mathbf{e} \in \{0, \dots, q-1\}^{k+1}$, we recall that

$$t_q^{(w)}(q(n' + \mathbf{w} \cdot \mathbf{h}') + (1, \mathbf{w}) \cdot \mathbf{e} + r_{0,w}) = e \left( (-1)^{s_2(w)} \frac{\ell}{b} s_q(q(n' + \mathbf{w} \cdot \mathbf{h}') + (1, \mathbf{w}) \cdot \mathbf{e} + r_{0,w}) \right).$$

Since for all $n \in \mathbb{N}$ we have

$$s_q(n) = s_q\left(\left\lfloor \frac{n}{q} \right\rfloor\right) + u_q(n), \quad (22)$$

where $u_q(n)$ is the unit place digit of $n$ in base-$q$, we obtain

$$t_q^{(w)}(q(n' + \mathbf{w} \cdot \mathbf{h}') + (1, \mathbf{w}) \cdot \mathbf{e} + r_{0,w}) = e \left( (-1)^{s_2(w)} \frac{\ell}{b} \left( s_q(n' + \mathbf{w} \cdot \mathbf{h}' + \delta(\mathbf{r}_0; \mathbf{e})_w \right) + u_q((1, \mathbf{w}) \cdot \mathbf{e} + r_{0,w}) \right), \quad (23)$$

where

$$\delta(\mathbf{r}_0; \mathbf{e})_w = \left\lfloor \frac{r_{0,w} + (1, \mathbf{w}) \cdot \mathbf{e}}{q} \right\rfloor.$$

Inserting the identity (23) into (21), we get

$$A(\rho, \mathbf{r}_0) = \frac{1}{q^{(k+1)\rho}} \sum_{\substack{0 \le n' < q^{\rho-1} \\ \mathbf{h}' = (h'_0, \dots, h'_{k-1}) \in \{0, \dots, q^{\rho-1}-1\}^k \\ \mathbf{e} = (e_0, \dots, e_k) \in \{0, \dots, q-1\}^{k+1}}} \prod_{w=0}^{2^k-1} e \left( (-1)^{s_2(w)} \frac{\ell}{b} u_q((1, \mathbf{w}) \cdot \mathbf{e} + r_{0,w}) \right) \\ \times \prod_{w=0}^{2^k-1} t_q^{(w)}(n' + \mathbf{w} \cdot \mathbf{h}' + \delta(\mathbf{r}_0; \mathbf{e})_w).$$

Since the first product is independent of $n'$ and $\mathbf{h}'$, it follows that

$$A(\rho, \mathbf{r}_0) = \frac{1}{q^{k+1}} \sum_{\mathbf{e}=(e_0, \dots, e_k) \in \{0, \dots, q-1\}^{k+1}} e\left(\frac{\ell}{b} S(\mathbf{r}_0, \mathbf{e})\right) A(\rho-1, \delta(\mathbf{r}_0; \mathbf{e})), \quad (24)$$
where

$$S(\mathbf{r}_0, \mathbf{e}) = \sum_{w=0}^{2^k-1} (-1)^{s_2(w)} u_q((1, \mathbf{w}) \cdot \mathbf{e} + r_{0,w}).$$

We note that Lemma 3.2 provides the same recursion formula (24) when we handle $s_q^\rho$ instead of $s_q$. Until the end of the proof, we will only consider $s_q$ knowing that we can replace any occurrence of $s_q$ by $s_q^\rho$. We now rewrite the sum $S(\mathbf{r}_0, \mathbf{e})$ in a more convenient way. By (20),

$$u_q((1, \mathbf{w}) \cdot \mathbf{e} + r_{0,w}) = (1, \mathbf{w}) \cdot \mathbf{e} + r_{0,w} - q\delta(\mathbf{r}_0; \mathbf{e})_w$$

and therefore

$$S(\mathbf{r}_0, \mathbf{e}) = \sum_{w=0}^{2^k-1} (-1)^{s_2(w)}((1, \mathbf{w}) \cdot \mathbf{e} + r_{0,w} - q\delta(\mathbf{r}_0; \mathbf{e})_w) \\ = \sum_{w=0}^{2^k-1} (-1)^{s_2(w)}(r_{0,w} - q\delta(\mathbf{r}_0; \mathbf{e})_w) - \sum_{w=0}^{2^k-1} (1, \mathbf{w}) \cdot \mathbf{e} + \sum_{w=0}^{2^k-1} (1, \mathbf{w}) \cdot \mathbf{e}.$$

We claim that

$$\sum_{w=0}^{2^k-1} (1, \mathbf{w}) \cdot \mathbf{e} = \sum_{w=0}^{2^k-1} (1, \mathbf{w}) \cdot \mathbf{e}.$$

To see this, we write

$$\begin{align}
\sum_{\substack{w=0 \\ 2|s_2(w)}}^{2^k-1} (1, \mathbf{w}) \cdot \mathbf{e} &= e_0 |\{0 \le w < 2^k : 2 \nmid s_2(w)\}| + \sum_{\substack{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k \\ 2^k \sum_{i=0}^{k-1} w_i}} \sum_{r=1}^{k} w_{r-1} e_r \nonumber \\
&= e_0 |\{0 \le w < 2^k : 2 \nmid s_2(w)\}| + \sum_{r=1}^{k} e_r \sum_{\substack{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k \\ 2^k \sum_{i=0}^{k-1} w_i}} w_{r-1} \nonumber \\
&= e_0 |\{0 \le w < 2^k : 2 \nmid s_2(w)\}| + \sum_{r=1}^{k} e_r \sum_{\substack{w_0, \dots, w_{k-1} \in \{0,1\} \\ w_{r-1}=1 \\ 2| \sum_{i \neq r-1} w_i}} 1. \tag{25}
\end{align}$$

Analogously, we have

$$\sum_{\substack{w=0 \\ 2|s_2(w)}}^{2^k-1} (1, \mathbf{w}) \cdot \mathbf{e} = e_0 |\{0 \le w < 2^k : 2 \nmid s_2(w)\}| + \sum_{r=1}^{k} e_r \sum_{\substack{w_0, \dots, w_{k-1} \in \{0,1\} \\ w_{r-1}=1 \\ 2^k \sum_{i \neq r-1} w_i}} 1. \quad (26)$$

We notice that the sets $\{0 \le w < 2^k : 2 \mid s_2(w)\}$ and $\{0 \le w < 2^k : 2 \nmid s_2(w)\}$ are in bijection. Indeed, when we switch one fixed binary digit of $w$, we pass from one set to the other (or, equivalently, we can use $\sum_{0 \le j < 2^k} (-1)^{s_2(j)} = 0$). A similar digit switching argument (noticing that $k \ge 2$) works to show that for fixed $r$ both inner sums in (25) and (26) are equal.
We therefore get

$$ \sum_{\substack{w=0 \\ 2|s_2(w)}}^{2^k-1} (1, \mathbf{w}) \cdot \mathbf{e} = \sum_{\substack{w=0 \\ 2|s_2(w)}}^{2^k-1} (1, \mathbf{w}) \cdot \mathbf{e} $$

and

$$ S(\mathbf{r}_0, \mathbf{e}) = \sum_{w=0}^{2^k-1} (-1)^{s_2(w)} (r_{0,w} - q\delta(\mathbf{r}_0; \mathbf{e})_w). $$

Plugging this into (24) we get the stated recursion formula.

<figure><img src="image_3.png" /></figure>

**Remark 4.2.** For the case $b = q = 2$, which corresponds to the Thue–Morse sequence, the recursion formula in Lemma 4.1 becomes

$$ A(\rho, \mathbf{r}_0) = \frac{(-1)^{|\mathbf{r}_0|}}{2^{k+1}} \sum_{\mathbf{e}=(e_0, \dots, e_{k-1}) \in \{0,1\}^{k+1}} A(\rho-1, \delta(\mathbf{r}_0; \mathbf{e})), $$

where $|\mathbf{r}_0| := \sum_{w \in \{0, \dots, 2^{k-1}\}} r_{0,w}$. This is the same formula as in the article of Konieczny [13, (2.1)] and of Spiegelhofer [21, (5.13)]. We note that in our more general case, the corresponding formula is more involved since there are additional multiplicative weights (bth roots of unity) attached to the sum and the arguments. Somewhat surprisingly, these bth roots of unity are connected to the binary digit sum of the summation index $w$.

In order to have a summation ranging over the whole set $\mathbb{Z}^{2^k}$, we gather the $\mathbf{e} \in \{0, \dots, q-1\}^{k+1}$ such that $\mathbf{r}_1 = \delta(\mathbf{r}_0; \mathbf{e})$. The formula in Lemma 4.1 becomes a recursion with normalized weights attached to its terms.

**Lemma 4.3.** For $\mathbf{r}_0 \in \mathbb{Z}^{2^k}$, the sequence $(A(\rho, \mathbf{r}_0))_{\rho>0}$ satisfies the recursion formula

$$ A(\rho, \mathbf{r}_0) = \sum_{\mathbf{r}_1 \in \mathbb{Z}^{2^k}} A(\rho - 1, \mathbf{r}_1) p_{\mathbf{r}_0, \mathbf{r}_1}, \qquad (27) $$

where

$$ p_{\mathbf{r}_0, \mathbf{r}_1} = e \left( \frac{\ell}{b} \left( q \tilde{S}(\mathbf{r}_1) - \tilde{S}(\mathbf{r}_0) \right) \right) \frac{|\{\mathbf{e} \in \{0, \dots, q-1\}^{k+1} : \delta(\mathbf{r}_0; \mathbf{e}) = \mathbf{r}_1\}|}{q^{k+1}}, \qquad (28) $$

with

$$ \tilde{S}(\mathbf{r}) = - \sum_{w=0}^{2^k-1} (-1)^{s_2(w)} r_w $$

for

$$ \mathbf{r} = (r_w)_{w \in \{0, \dots, 2^k-1\} \in \mathbb{Z}^{2^k}}. $$

The vector $\mathbf{r} = (r_w)_{w \in \{0,1\}^k}$ such that $r_w = 0$ for all $w \in \{0, \dots, 2^k - 1\}$ will be written as

$$ \mathbf{0} := (0, 0, \dots, 0) \in \mathbb{Z}^{2^k}. $$

The recursion formula (27) and the weights that can be seen as transition complex random variables, suggests to consider a directed graph modelled in the set $\mathbb{Z}^{2^k}$ consisting of the vectors $\mathbf{r}$ as vertices and being connected to each other whenever a specific condition on the associated weights is verified: there is an edge between $\mathbf{r}_0$ and $\mathbf{r}_1$ if and only if there exists $\mathbf{e} \in \{0, \dots, q-1\}^{k+1}$ such that

$$ \delta(\mathbf{r}_0; \mathbf{e}) = \mathbf{r}_1. $$
A vertex $\mathbf{r}_1 = (r_{1,w})_w$ is said to be reachable from a vertex $\mathbf{r}_0$ if there exists $d > 0$ and $\mathbf{r}^{(1)}, \dots, \mathbf{r}^{(d)} \in \mathbb{Z}^{2^k}$ such that

$$p_{\mathbf{r}_0, \mathbf{r}^{(1)}} \times p_{\mathbf{r}^{(1)}, \mathbf{r}^{(2)}} \times \dots \times p_{\mathbf{r}^{(d-1)}, \mathbf{r}^{(d)}} \times p_{\mathbf{r}^{(d)}, \mathbf{r}_1} \neq 0.$$

We write

$$\mathbf{r}_0 \to \mathbf{r}^{(1)} \to \mathbf{r}^{(2)} \to \dots \to \mathbf{r}^{(d)} \to \mathbf{r}_1,$$

whenever $\mathbf{r}_1$ is reachable from $\mathbf{r}_0$ via $\mathbf{r}^{(1)}, \mathbf{r}^{(2)}, \dots, \mathbf{r}^{(d)}$. We now turn our attention to the graph built by the elements $\mathbf{r}_1 \in \mathbb{Z}^{2^k}$ reachable from 0. The following result shows that this is a finite subgraph in above graph.

**Lemma 4.4.** Let $\mathfrak{R}$ be the set of elements $\mathbf{r} \in \mathbb{Z}^{2^k}$ reachable from 0. Then $\mathfrak{R}$ is finite and for $\mathbf{r} = (r_w)_{w \in \{0, \dots, 2^k-1\}}$ reachable from 0 and for $0 \le w < 2^k$ we have

$$0 \le r_w \le s_2(w).$$

Furthermore,

$$|\mathfrak{R}| \le \prod_{i=0}^{k} (i+1)^{\binom{k}{i}}.$$

*Proof.* We suppose that

$$0 \to \mathbf{r}^{(1)} \to \mathbf{r}^{(2)} \to \dots \to \mathbf{r}^{(d)} \to \mathbf{r}_1.$$

Since $p_{\mathbf{r}^{(d)}, \mathbf{r}_1} \neq 0$, there exists an element $\mathbf{e}^{(d)} \in \{0, \dots, q-1\}^{k+1}$ such that for all $w \in \{0, \dots, 2^k-1\}$,

$$\delta(\mathbf{r}^{(d)}; \mathbf{e}^{(d)})_w = \left\lfloor \frac{r_w^{(d)} + (1, \mathbf{w}) \cdot \mathbf{e}^{(d)}}{q} \right\rfloor = r_{1,w}.$$

In the same way, when $d \ge 2$ and if $p_{\mathbf{r}^{(d-1)}, \mathbf{r}^{(d)}} \neq 0$, we deduce the existence of $\mathbf{e}^{(d-1)} \in \{0, \dots, q-1\}^{k+1}$ such that

$$r_{1,w} = \left\lfloor \frac{\frac{r_w^{(d-1)} + (1, \mathbf{w}) \cdot \mathbf{e}^{(d-1)}}{q}}{q} + (1, \mathbf{w}) \cdot \mathbf{e}^{(d)} \right\rfloor.$$

For all $\mathbf{e} \in \{0, \dots, q-1\}^{k+1}$ and all $0 \le w < 2^k$ we have the simple bound

$$(1, \mathbf{w}) \cdot \mathbf{e} \le (q-1)(1 + s_2(w)).$$

Iterating the process above, we will reach the point 0, after a finite number of steps. We therefore have the bound

$$r_{1,w} < (q-1)(1 + s_2(w)) \sum_{r=1}^{\infty} \frac{1}{q^r} = 1 + s_2(w)$$

and we get $r_{1,w} \le s_2(w)$. Moreover, we notice that for all $w \in \{0, \dots, 2^k-1\}$, we have

$$r_w^{(1)} = \left\lfloor \frac{(1, \mathbf{w}) \cdot \mathbf{e}^{(0)}}{q} \right\rfloor \ge 0,$$

and therefore $r_w^{(2)}, \dots, r_w^{(d)}$, $r_{1,w} \ge 0$ for all $w \in \{0, \dots, 2^k-1\}$. This implies that the set $\mathfrak{R}$ of the vertices reachable from 0 is finite and for all $\mathbf{r} = (r_w)_w \in \mathfrak{R}$ we have

$$0 \le r_w \le s_2(w).$$

For the cardinality of $\mathfrak{R}$, we observe that for any $\mathbf{r} = (r_w)_{w \in \{0, \dots, 2^k-1\}} \in \mathfrak{R}$ and any fixed $0 \le i \le k$, there are $\binom{k}{i}$ choices of elements $w$ such that $s_2(w) = i$. Thus, there are $(i+1)\binom{i}{i}$ possible choices for the coordinates of $\mathbf{r}$ indexed by a number $w$ such that $s_2(w) = i$, leading to the stated bound. $\square$
In addition to the finiteness, our graph is strongly connected. To prove this, we introduce a new notation. For $e \in \{0, \dots, q-1\}^{k+1}$, we define the function $\delta_e: \mathbb{Z}^{2^k} \to \mathbb{Z}^{2^k}$ by

$$ \delta_e(\mathbf{r}) = \delta(\mathbf{r}; e). $$

**Lemma 4.5.** For $K := \left\lfloor \frac{\log(k)}{\log(q)} \right\rfloor + 1$ we have for all $\mathbf{r} \in \mathfrak{R}$:

$$ \underbrace{(\delta_0 \circ \delta_0 \circ \dots \circ \delta_0)}_{K \text{ times}}(\mathbf{r}) = \mathbf{0}. $$

*Proof.* Let $\mathbf{r} \in \mathfrak{R}$ and $w \in \{0, \dots, 2^k - 1\}$. Then

$$ 0 \le \delta_0(\mathbf{r})_w = \left\lfloor \frac{r_w}{q} \right\rfloor \le \frac{r_w}{q}. $$

Thus,

$$ 0 \le \delta_0(\delta_0(\mathbf{r}))_w \le \frac{r_w}{q^2}. $$

By induction on the number of iterations of $\delta_0$, and using the fact that $r_w \le s_2(w) \le k$, we have

$$ 0 \le \underbrace{(\delta_0 \circ \delta_0 \circ \dots \circ \delta_0)}_{K \text{ times}}(\mathbf{r})_w \le \frac{k}{q^K}. $$

Since $k < q^K$ and $\underbrace{(\delta_0 \circ \delta_0 \circ \dots \circ \delta_0)}_{K \text{ times}}(\mathbf{r})_w \in \mathbb{N}$, we have $\underbrace{(\delta_0 \circ \delta_0 \circ \dots \circ \delta_0)}_{K \text{ times}}(\mathbf{r})_w = 0$. $\square$

**Lemma 4.5** assures us that after applying $K$ times the operator $\delta_0$ to any vertex of the graph, we inevitably end up at vertex $\mathbf{0}$ (this is sometimes also described as the property that the graph is synchronizing).

**Proposition 4.6.** Let $\mathbf{r}_0, \mathbf{r}_1 \in \mathfrak{R}$. Then, $\mathbf{r}_1$ is reachable from $\mathbf{r}_0$.

*Proof.* Lemma 4.5 allows us to reach $\mathbf{0}$ in a finite number of steps. Then, the definition of the graph enables us to reach $\mathbf{r}_1$ in a finite number of steps from $\mathbf{0}$. We can thus concatenate the two previous paths and connect $\mathbf{r}_0$ to $\mathbf{r}_1$. $\square$

We can now interpret formula (27) in Lemma 4.3 in a recursive way in our graph setting. For $1 \le j \le \rho$, and for $\mathbf{r}_0 \in \mathfrak{R}$, we have

$$ A(\rho, \mathbf{r}_0) = \sum_{\mathbf{r}_j \in \mathfrak{R}} A(\rho - j, \mathbf{r}_j) p_{\mathbf{r}_0, \mathbf{r}_j}^{(j)}, \quad (29) $$

where $p_{\mathbf{r}_0, \mathbf{r}_j}^{(j)}$ denotes the sum of all weights of paths connecting $\mathbf{r}_0$ to $\mathbf{r}_j$ of length $j$. Recall that the weight $p(\gamma)$ of a path $\gamma$ connecting $\mathbf{r}_0$ to $\mathbf{r}_j$,

$$ \gamma: \mathbf{r}_0 \to \mathbf{r}^{(1)} \to \mathbf{r}^{(2)} \to \dots \to \mathbf{r}^{(d)} \to \mathbf{r}_j $$

is defined by

$$ p(\gamma) = p_{\mathbf{r}_0, \mathbf{r}^{(1)}} \times p_{\mathbf{r}^{(1)}, \mathbf{r}^{(2)}} \times \dots \times p_{\mathbf{r}^{(d-1)}, \mathbf{r}^{(d)}} \times p_{\mathbf{r}^{(d)}, \mathbf{r}_j}. $$

Since $\mathfrak{R}$ is finite, the quantity $v_\rho = \max_{\mathbf{r} \in \mathfrak{R}} (|A(\rho, \mathbf{r})|) < +\infty$ is well-defined. We obtain, for all $1 \le j \le \rho$,

$$ v_\rho \le v_{\rho-j} \max_{\mathbf{r}_0 \in \mathfrak{R}} \left( \sum_{\mathbf{r}_j \in \mathfrak{R}} |p_{\mathbf{r}_0, \mathbf{r}_j}^{(j)}| \right). \quad (30) $$

In order to proceed with the proof of Theorem 1.7, we will show in the next section that there exists an integer $j \ge 1$ such that

$$ \sum_{\mathbf{r}_j \in \mathfrak{R}} |p_{\mathbf{r}_0, \mathbf{r}_j}^{(j)}| < 1 \quad (31) $$

for all $\mathbf{r}_0 \in \mathfrak{R}$.
## 4.2 An effective value of the exponent $\eta_0$ in Theorem 1.7

The aim of this section is to prove (31), and, more precisely, to provide an effective value for $\eta_0$. This allows us to get the effective version of Theorem 1.7 with an explicit value for $\eta_0$ in the end. We will show that there exists $j \ge 1$ such that

$$M = \max_{\mathbf{r}_0 \in \mathfrak{R}} \left( \sum_{\mathbf{r}_j \in \mathfrak{R}} |p_{\mathbf{r}_0, \mathbf{r}_j}^{(j)}| \right) < 1$$

with an effective bound on $M$ by a constant $< 1$. Let $k$ and $j$ be two integers. Let $K$ be as defined in Lemma 4.5. We suppose that $j \ge K + b(k + 1)$. We use two paths connecting $0$ to $0$ of length $(k + 1)$ with different weights to get a saving.

We recall that a path of length $(k + 1)$ connecting a point $\mathbf{r}^{(0)}$ to $\mathbf{r}^{(k+1)}$ by means of $\delta$ (which is defined in (20)) is specified by $(k + 1)$ vectors $\mathbf{e}^{(0)}, \dots, \mathbf{e}^{(k)} \in \{0, \dots, q-1\}^{k+1}$ and $k$ vectors $\mathbf{r}^{(1)}, \dots, \mathbf{r}^{(k)} \in \mathbb{Z}^{2k}$ such that $\mathbf{r}^{(1)} = \delta(\mathbf{r}^{0}; \mathbf{e}^{(0)}), \dots, \mathbf{r}^{(k+1)} = \delta(\mathbf{r}^{(k)}; \mathbf{e}^{(k)})$. This could be written as follows

$$\mathbf{r}^{(0)} \xrightarrow{\mathbf{e}^{(0)}} \mathbf{r}^{(1)} \xrightarrow{\mathbf{e}^{(1)}} \dots \xrightarrow{\mathbf{e}^{(k-2)}} \mathbf{r}^{(k-1)} \xrightarrow{\mathbf{e}^{(k-1)}} \mathbf{r}^{(k)} \xrightarrow{\mathbf{e}^{(k)}} \mathbf{r}^{(k+1)}$$

### 4.2.1 Trivial path and Konieczny's path

As for the first path (trivial path), we take $(k+1)$ (little) loops at $0$, i.e. at each step $1 \le t \le k+1$ we choose $\mathbf{e}^{(t)} = 0$,

$$0 \xrightarrow{0} 0 \xrightarrow{0} \dots \xrightarrow{0} 0 \xrightarrow{0} 0 \xrightarrow{0} 0. \qquad (32)$$

For the second path (Konieczny's path), we proceed via a great loop. For that purpose, we adapt the construction given in the proof of Proposition 2.3 by Konieczny [13]. We set $\mathbf{r}^{(0)} = 0 = \mathbf{r}^{(k+1)}$. For $1 \le t \le k$, we define $\mathbf{r}^{(t)} = (r_w^{(t)})_w$ by

$$\forall w \in \{0, \dots, 2^k - 1\}, \quad r_w^{(t)} = \begin{cases} 1, & \text{if } w_0 = \dots = w_{t-1} = 1; \\ 0, & \text{otherwise.} \end{cases}$$

Case $t = 0$. We take $\mathbf{e}_{\mathbf{K}_0}^{(0)} = (q - 1, 1, 0, \dots, 0)$. We have

$$\delta(\mathbf{r}^{(0)}; \mathbf{e}_{\mathbf{K}_0}^{(0)}) = \mathbf{r}^{(1)}.$$

To prove this, we observe that for $w \in \{0, \dots, 2^k - 1\}$ we have

$$\delta(\mathbf{r}^{(0)}; \mathbf{e}_{\mathbf{K}_0}^{(0)})_w = \left\lfloor \frac{0 + q - 1 + w_0}{q} \right\rfloor.$$

This is equal to 1 if $w_0 = 1$, and 0 if $w_0 = 0$. Hence, in this case,

$$\delta(\mathbf{r}^{(0)}; \mathbf{e}_{\mathbf{K}_0}^{(0)})_w = r_w^{(1)}.$$

The transition weight from $\mathbf{r}_0$ to $\mathbf{r}_1$ is given by

$$e^{\left(\frac{\ell}{b}\left(q\tilde{S}(\mathbf{r}^{(1)}) - \tilde{S}(\mathbf{r}^{(0)})\right)\right)},$$

where

$$\tilde{S}(\mathbf{r}^{(1)}) = - \sum_{w=0}^{2^k-1} (-1)^{s_2(w)} r_w^{(1)} = - \sum_{\substack{w=0 \\ w_0=1}}^{2^k-1} (-1)^{s_2(w)} = 0$$
and

$$ \tilde{S}(\mathbf{r}^{(0)}) = - \sum_{w=0}^{2^k-1} (-1)^{s_2(w)} r_w^{(0)} = 0. $$

Case $1 \le t < k-1$. We choose $\mathbf{e}_{\text{Ko}}^{(t)} = (q-2, 0, \dots, 0, 1, 0, \dots, 0)$, where 1 is at the $(t+1)$ position. For $w \in \{0, \dots, 2^k-1\}$, we have

$$ \delta(\mathbf{r}^{(t)}; \mathbf{e}_{\text{Ko}}^{(t)})_w = \left\lfloor \frac{r_w^{(t)} + (1, \mathbf{w}) \cdot \mathbf{e}_{\text{Ko}}^{(t)}}{q} \right\rfloor = \left\lfloor \frac{r_w^{(t)} + q - 2 + w_t}{q} \right\rfloor. $$

Thus, $\delta(\mathbf{r}^{(t)}; \mathbf{e}_{\text{Ko}}^{(t)})_w = 1$ if and only if $r_w^{(t)} = 1$ and $w_t = 1$. By definition of $r_w^{(t)}$,

$$ \delta(\mathbf{r}^{(t)}; \mathbf{e}_{\text{Ko}}^{(t)})_w = 1 \iff w_0 = \dots = w_t = 1. $$

We deduce that

$$ \delta(\mathbf{r}^{(t)}; \mathbf{e}_{\text{Ko}}^{(t)}) = \mathbf{r}^{(t+1)}. $$

According to (28), the weight attached to the transition from $\mathbf{r}^{(t)}$ to $\mathbf{r}^{(t+1)}$ is given by

$$ e\left(\frac{\ell}{b}\left(q\tilde{S}(\mathbf{r}^{(t+1)}) - \tilde{S}(\mathbf{r}^{(t)})\right)\right), $$

where

$$ \tilde{S}(\mathbf{r}^{(t+1)}) = - \sum_{w=0}^{2^k-1} (-1)^{s_2(w)} r_w^{(t+1)} = - \sum_{w_0=\dots=w_t=1}^{2^k-1} (-1)^{s_2(w)} = 0 $$

and

$$ \tilde{S}(\mathbf{r}^{(t)}) = - \sum_{w=0}^{2^k-1} (-1)^{s_2(w)} r_w^{(t)} = - \sum_{w_0=\dots=w_{t-1}=1}^{2^k-1} (-1)^{s_2(w)} = 0. $$

Hence,

$$ e\left(\frac{\ell}{b}\left(q\tilde{S}(\mathbf{r}^{(t+1)}) - \tilde{S}(\mathbf{r}^{(t)})\right)\right) = 1. $$

Let $t=k-1$. We set $\mathbf{e}_{\text{Ko}}^{(k-1)} = (q-2, 0, \dots, 0, 0, 1)$.

For $w \in \{0, \dots, 2^k-1\}$, we have

$$ \delta(\mathbf{r}^{(t)}; \mathbf{e}_{\text{Ko}}^{(t)})_w = \left\lfloor \frac{r_w^{(k-1)} + (1, \mathbf{w}) \cdot \mathbf{e}_{\text{Ko}}^{(k-1)}}{q} \right\rfloor = \left\lfloor \frac{r_w^{(k-1)} + q - 2 + w_{k-1}}{q} \right\rfloor. $$

Thus, $\delta(\mathbf{r}^{(k-1)}; \mathbf{e}_{\text{Ko}}^{(k-1)})_w = 1$ if and only if $r_w^{(k-1)} = 1$ and $w_{k-1} = 1$. By definition of $r_w^{(k-1)}$ we have

$$ \delta(\mathbf{r}^{(k-1)}; \mathbf{e}_{\text{Ko}}^{(k-1)})_w = 1 \iff w_0 = \dots = w_{k-1} = 1. $$

We deduce that

$$ \delta(\mathbf{r}^{(k-1)}; \mathbf{e}_{\text{Ko}}^{(k-1)}) = \mathbf{r}^{(k)}. $$

Here, we have a change regarding the transition weights. While

$$ \tilde{S}(\mathbf{r}^{(k-1)}) = - \sum_{w=0}^{2^k-1} (-1)^{s_2(w)} r_w^{(t)} = \sum_{w_0=\dots=w_{k-2}=1}^{2^k-1} (-1)^{s_2(w)} = 0 $$
we here have

$$
\tilde{S}(\mathbf{r}^{(\mathbf{k})}) = - \sum_{w=0}^{2^k-1} (-1)^{s_2(w)} r_w^{(t)} = - \sum_{w_0=\cdots=w_{k-1}=1}^{2^k-1} (-1)^{s_2(w)} = -(-1)^k = (-1)^{k+1}.
$$

Thus, the weight attached to the transition from $\mathbf{r}^{(k-1)}$ to $\mathbf{r}^{(k)}$ equals

$$
e\left(\frac{\ell}{b} \left(q\tilde{S}(\mathbf{r}^{(\mathbf{k})}) - \tilde{S}(\mathbf{r}^{(\mathbf{k}-1)})\right)\right) = e\left((-1)^{k+1} \frac{q\ell}{b}\right).
$$

Let $t = k$. Here we set $\mathbf{e}_{\mathrm{Ko}}^{(k)} = \mathbf{0}$. Thus,

$$
\delta(\mathbf{r}^{(k)}; \mathbf{e}_{\mathrm{Ko}}^{(k)}) = \mathbf{0} = \mathbf{r}^{(k+1)}.
$$

The weight attached to the transition from $\mathbf{r}^{(k)}$ to $\mathbf{r}^{(k+1)}$ is given by

$$
e\left(\frac{\ell}{b}\left(q\tilde{S}(\mathbf{r}^{(k+1)}) - \tilde{S}(\mathbf{r}^{(k)})\right)\right) = e\left((-1)^k \frac{\ell}{b}\right).
$$

Note that the weights $\tilde{S}$ only depend on $\mathbf{r}^{(t)}$ (not on $\mathbf{e}$). We therefore have

$$
p_{\mathbf{r}^{(t)}, \mathbf{r}^{(t+1)}} = \frac{|\{\mathbf{e} \in \{0, \dots, q-1\}^{k+1} : \delta(\mathbf{r}^{(t)}; \mathbf{e}) = \mathbf{r}^{(t+1)}\}|}{q^{k+1}}, \quad 0 \le t < k,
$$

$$
p_{\mathbf{r}^{(k-1)}, \mathbf{r}^{(k)}} = e\left((-1)^{k+1} \frac{q\ell}{b}\right) \frac{|\{\mathbf{e} \in \{0, \dots, q-1\}^{k+1} : \delta(\mathbf{r}^{(k-1)}; \mathbf{e}) = \mathbf{r}^{(k)}\}|}{q^{k+1}}, \quad (33)
$$

$$
p_{\mathbf{r}^{(k)}, \mathbf{r}^{(k+1)}} = e\left((-1)^k \frac{\ell}{b}\right) \frac{|\{\mathbf{e} \in \{0, \dots, q-1\}^{k+1} : \delta(\mathbf{r}^{(k)}; \mathbf{e}) = \mathbf{r}^{(k+1)}\}|}{q^{k+1}}.
$$

4.2.2 Coding the paths by words

Let $\mathbf{r}_0, \mathbf{r}_j \in \mathfrak{R}$. Consider the set of all paths of length $j$ connecting $\mathbf{r}_0$ to $\mathbf{r}_j$. Proposition 4.6 shows that this set is non-empty. A path $\gamma$ belonging to this set can be described by words $\omega_\gamma$ of length $j$ over the alphabet $\{0, 1, \dots, q^{k+1} - 1\}$ where we identify $\mathbf{e}^{(i)} \in \{0, \dots, q-1\}^{k+1}$ to the letter $\sum_{j=0}^{k+1} e_j^{(i)} q^j$. Note that there might be several different words that describe the same path. We illustrate the word by

$$
\omega_{\gamma} : \boxed{\mathbf{e}^{(0)}} \quad \boxed{\mathbf{e}^{(1)}} \quad \dots \quad \boxed{\mathbf{e}^{(j)}}
$$

which relates to the path

$$
\mathbf{r}_0 \rightarrow \mathbf{r}_1 \rightarrow \dots \rightarrow \mathbf{r}_{j-1} \rightarrow \mathbf{r}_j,
$$

via

$$
\mathbf{r}_1 = \delta(\mathbf{r}_0; \mathbf{e}^{(0)}), \quad \dots, \quad \mathbf{r}_j = \delta(\mathbf{r}_{j-1}; \mathbf{e}^{(j-1)}).
$$

We now define the concatenation of two paths.

**Definition 4.7.** Let $\omega$ and $\omega'$ be two words of length $\alpha$ and $\beta$, respectively.

$$
\omega : \boxed{\mathbf{e}^{(0)}} \quad \boxed{\mathbf{e}^{(1)}} \quad \dots \quad \boxed{\mathbf{e}^{(\alpha)}}
$$
$$ \omega' : \boxed{\mathbf{e}'(0)} \quad \boxed{\mathbf{e}'(1)} \quad \dots \quad \boxed{\mathbf{e}'(\beta)} $$

We define $\omega \circ \omega'$ by

$$ \omega \circ \omega' : \boxed{\mathbf{e}^{(0)}} \quad \boxed{\mathbf{e}^{(1)}} \quad \dots \quad \boxed{\mathbf{e}^{(\alpha)}} \quad \boxed{\mathbf{e}'^{(0)}} \quad \boxed{\mathbf{e}'^{(1)}} \quad \dots \quad \boxed{\mathbf{e}'^{(\beta)}} $$

In a similar manner, we define, for a word $\omega$ and for $n \in \mathbb{N}$, the word $\omega^n$ by

$$ \omega^n = \begin{cases} \omega \circ \omega, & \text{if } n = 2; \\ \omega^{n-1} \circ \omega, & \text{if } n \ge 3. \end{cases} $$

Let us define some words which will be useful in the argument. First, we define the trivial word of length 1 $\omega_0$ by

$$ \omega_0 : \boxed{0} $$

When $\mathbf{r}_0 = \mathbf{0}$ then this word is related to the first (trivial) path from $\mathbf{0}$ to itself, and $\omega_0^{k+1}$ encodes the path consisting of $(k+1)$ (little) loops at $\mathbf{0}$. Similarly, we define the word $\omega_1$ with respect to the second path, which is linked to Konieczny's path [13] using the previous definition of $\mathbf{e}_{\mathbf{K}_0}^{(t)}$:

$$ \omega_1 : \boxed{\mathbf{e}_{\mathbf{K}_0}^{(0)}} \quad \boxed{\mathbf{e}_{\mathbf{K}_0}^{(1)}} \quad \dots \quad \boxed{\mathbf{e}_{\mathbf{K}_0}^{(k)}} $$

Let us define the fundamental word of length $(K + b(k + 1))$

$$ \omega_0^{K+b(k+1)} : \boxed{0} \quad \dots \quad \boxed{0} \quad \boxed{0} \quad \boxed{0} \quad \dots \quad \boxed{0} $$

The first $K \mathbf{0}$'s appearing on the left side in $\omega_0^{K+b(k+1)}$ (until the bold vertical line) indicate the “free fall” of our path, i.e. the path leading to the vertex $\mathbf{0}$. The $b(k+1)$ other $\mathbf{0}$'s indicate the first (trivial) path from $\mathbf{0}$ to itself, defined in (32).

### 4.2.3 Partitioning of the set of the words

The set $W^*$ of words of length $j \ge K + b(k + 1)$ which do not contain the subword $\omega_0^{K+b(k+1)}$ satisfies the inequality

$$ |W^*| \le (q^{(k+1)(K+b(k+1))} - 1)^{\frac{j}{K+b(k+1)}}. \quad (34) $$

Indeed, when subdividing a word of length $j$ into contiguous subwords of length $K + b(k + 1)$ (leaving a possibly short subword at the end), each word not containing the word $\omega_0^{K+b(k+1)}$ must necessarily not contain $\omega_0^{K+b(k+1)}$ as these subwords. There are $q^{(k+1)(K+b(k+1))} - 1$ different choices of words other than $\omega_0^{K+b(k+1)}$ per subword, and there are fewer than $j/(K + b(k + 1))$ full subwords.

In what follows, we will focus on words containing $\omega_0^{K+b(k+1)}$, those that do not contain this subword will be trivially estimated.

We have

$$ p_{\mathbf{r}_0, \mathbf{r}_j}^{(j)} = \frac{1}{q^{(k+1)j}} \sum_{\substack{\mathbf{e}=(\mathbf{e}^{(1)}, \dots, \mathbf{e}^{(j)}) \in (\{0, \dots, q-1\}^{k+1})^j \\ \mathbf{r}_j = \delta_{\mathbf{e}^{(j)}} \circ \dots \circ \delta_{\mathbf{e}^{(1)}}(\mathbf{r}_0)}} W(\mathbf{e}), $$
where

$$W(\mathbf{e}) = e \left( \frac{\ell}{b} \sum_{t=1}^{j} \left( q \tilde{S}(\delta_{\mathbf{e}^{(t)}} \circ \cdots \circ \delta_{\mathbf{e}^{(1)}}(\mathbf{r}_0)) - \tilde{S}(\delta_{\mathbf{e}^{(t-1)}} \circ \cdots \circ \delta_{\mathbf{e}^{(1)}}(\mathbf{r}_0)) \right) \right), \quad (35)$$

with the initialization, for $t = 1$:

$$\delta_{\mathbf{e}^{(t-1)}} \circ \cdots \circ \delta_{\mathbf{e}^{(1)}}(\mathbf{r}_0) = \mathbf{r}_0.$$

Let us define $F(\mathbf{r}_j) (= F(\mathbf{r}_0, \mathbf{r}_j)$, to avoid cumbersome notation we will omit the dependency in $\mathbf{r}_0$) the set of the elements $\mathbf{e} = (\mathbf{e}^{(1)}, \dots, \mathbf{e}^{(j)})$ such that there exists $1 \le m \le j - K - b(k+1) + 1$ such that $\mathbf{e}^{(m)} = \dots = \mathbf{e}^{(m+K+b(k+1)-1)} = \mathbf{0}$. For $0 < m \le j - K - b(k+1) + 1$, we note $F_m(\mathbf{r}_j) \subset F(\mathbf{r}_j)$ the set of the elements $\mathbf{e} = (\mathbf{e}^{(1)}, \dots, \mathbf{e}^{(j)})$ such that $m$ is the smallest integer satisfying $\mathbf{e}^{(m)} = \dots = \mathbf{e}^{(m+K+b(k+1)-1)} = \mathbf{0}$. With these definitions, we have the partition

$$F(\mathbf{r}_j) = \bigcup_{m=1}^{j-K-b(k+1)} F_m(\mathbf{r}_j).$$

In the following subsection, we will associate to each $\mathbf{e}$ containing the subword $\omega_0^{K+b(k+1)}$, ($b-1$) words $\varphi_1(\mathbf{e}), \dots, \varphi_{b-1}(\mathbf{e})$ such that for $\lambda = 1, \dots, b-1$, $\varphi_\lambda$ replaces the $\lambda$ first subwords $\omega_0^{k+1}$ by $\lambda$ subwords $\omega_1$. Roughly speaking, $\varphi_\lambda$ replaces $\lambda$ little loops at $\mathbf{0}$ by $\lambda$ great loops at $\mathbf{0}$. Next we will get some cancellation between the weights corresponding to all these words.

### 4.2.4 Switching and coupling with Konieczny's path

**Definition 4.8 (λ-switching function).** For $\lambda \in \{1, \dots, b-1\}$, we define the function $\varphi_\lambda : F(\mathbf{r}_j) \to (\{0, \dots, q-1\}^{k+1})^j$ as follows:

For $\mathbf{e} = (\mathbf{e}^{(1)}, \dots, \mathbf{e}^{(j)}) \in F_m(\mathbf{r}_j)$, we set $\varphi_\lambda(\mathbf{e}) = (\mathbf{g}^{(1)}, \dots, \mathbf{g}^{(j)})$, with

$$\left\{ \begin{array}{ll} \mathbf{g}^{(m+K+t)} = \mathbf{e}_{\mathbf{Ko}}^{t \bmod (k+1)} & \text{if } t \in \{0, \dots, \lambda(k+1) - 1\}; \\ \mathbf{g}^{(t)} = \mathbf{e}^{(t)} & \text{if } t \in \{0, \dots, m-1\} \cup \{m+K+b(k+1), \dots, j\}, \end{array} \right.$$

where $\mathbf{e}_{\mathbf{Ko}}^{(0)}, \dots, \mathbf{e}_{\mathbf{Ko}}^{(k)}$ are the vectors defined in the beginning of Section 4.2 and corresponding to Konieczny's path.

We write

$$p_{\mathbf{r}_0, \mathbf{r}_j}^{(j)} = \frac{1}{q^{(k+1)j}} \sum_{\mathbf{e} \in F(\mathbf{r}_j) \cup \varphi_1(F(\mathbf{r}_j)) \cup \dots \cup \varphi_{b-1}(F(\mathbf{r}_j))} W(\mathbf{e}) + \frac{1}{q^{(k+1)j}} \sum_{\mathbf{e} \notin F(\mathbf{r}_j) \cup \varphi_1(F(\mathbf{r}_j)) \cup \dots \cup \varphi_{b-1}(F(\mathbf{r}_j))} W(\mathbf{e}). \quad (36)$$

For all $1 \le m \le j - K - b(k+1) + 1$, let us denotes $H_m(\mathbf{r}_j)$ the set of the elements $\mathbf{e} = (\mathbf{e}^{(1)}, \dots, \mathbf{e}^{(j)}) \in F(\mathbf{r}_j) \cup \varphi_1(F(\mathbf{r}_j)) \cup \dots \cup \varphi_{b-1}(F(\mathbf{r}_j))$ such that $m$ is the smallest integer such that the word linked to $(\mathbf{e}^{(m)}, \dots, \mathbf{e}^{(m+K+b(k+1)-1)})$ belongs to the set

$$\{\omega_0^{K+k+1}, \omega_0^K \circ \omega_1 \circ \omega_0^{(k+1)(b-1)}, \dots, \omega_0^K \circ \omega_1^{b-1} \circ \omega_0\}.$$

With this definition, we have the partition

$$F(\mathbf{r}_j) \cup \varphi_1(F(\mathbf{r}_j)) \cup \dots \cup \varphi_{b-1}(F(\mathbf{r}_j)) = \bigcup_{m=1}^{j-K-b(k+1)+1} H_m(\mathbf{r}_j).$$

Thus,

$$\sum_{\mathbf{e} \in F(\mathbf{r}_j) \cup \varphi_1(F(\mathbf{r}_j)) \cup \dots \cup \varphi_{b-1}(F(\mathbf{r}_j))} W(\mathbf{e}) = \sum_{m=1}^{j-K-b(k+1)+1} \sum_{\mathbf{e} \in H_m(\mathbf{r}_j)} W(\mathbf{e}) \\ = \sum_{m=1}^{j-K-b(k+1)+1} \sum_{\mathbf{e} \in F_m(\mathbf{r}_j)} (W(\mathbf{e}) + W(\varphi_1(\mathbf{e}))) + \dots + W(\varphi_{b-1}(\mathbf{e})).$$
Moreover, we have the following lemma.

**Lemma 4.9.** For all $\mathbf{e} \in F_m(\mathbf{r}_j)$ and for $1 \le m \le j - K - b(k+1) + 1$, we have

$$W(\mathbf{e}) + W(\varphi_1(\mathbf{e})) + \dots + W(\varphi_{b-1}(\mathbf{e})) = 0. \quad (37)$$

*Proof.* We prove the case $2 \le m \le j - K - b(k+1)$. The cases $m = 1$ and $m = j - K - b(k+1) + 1$ are proven in the same way. The only difference lies in the number of parts unchanged by our function (only one unchanged part).

According to (35) and the definition of $\varphi_\lambda$, we have, for $2 \le m \le j - K - b(k+1)$, $\lambda \in \{0, \dots, b-1\}$ and for $t \in \{0, \dots, m-1\} \cup \{m + K + b(k+1), \dots, j\}$,

$$\begin{aligned} & q\tilde{S}(\delta_{\varphi_{\lambda}(\mathbf{e}^{(t)})} \circ \dots \circ \delta_{\varphi_{\lambda}(\mathbf{e}^{(1)})}(\mathbf{r}_0)) - \tilde{S}(\delta_{\varphi_{\lambda}(\mathbf{e}^{(t-1)})} \circ \dots \circ \delta_{\varphi_{\lambda}(\mathbf{e}^{(1)})}(\mathbf{r}_0)) \\ & = q\tilde{S}(\delta_{\mathbf{e}^{(t)}} \circ \dots \circ \delta_{\mathbf{e}^{(1)}}(\mathbf{r}_0)) - \tilde{S}(\delta_{\mathbf{e}^{(t-1)}} \circ \dots \circ \delta_{\mathbf{e}^{(1)}}(\mathbf{r}_0)). \end{aligned} \quad (38)$$

These two quantities, which are unchanged by the function $\varphi_\lambda$, will constitute the common weights (of modulus 1) for the numbers $W(\mathbf{e})$, $W(\varphi_1(\mathbf{e}))$, \dots, $W(\varphi_{b-1}(\mathbf{e}))$. They will not intervene in the calculation of the quantity

$$|W(\mathbf{e}) + W(\varphi_1(\mathbf{e})) + \dots + W(\varphi_{b-1}(\mathbf{e}))|.$$

Moreover, the part changed by the function $\varphi_\lambda$ (which corresponds to $\lambda$ Konieczny's paths) has, according to Definition 4.8 and (33), a weight which is equal to

$$e^{((-1)^{k+1}\lambda(q-1)\ell/b)},$$

since one Konieczny's path has a weight equal to $e^{((-1)^{k+1}(q-1)\ell/b)}$. We then deduce that

$$\begin{aligned} & |W(\mathbf{e}) + W(\varphi_1(\mathbf{e})) + \dots + W(\varphi_{b-1}(\mathbf{e}))| \\ & = \left|1 + e^{\left((-1)^{k+1} \frac{q-1}{b}\right)} + e^{\left((-1)^{k+1} \frac{2(q-1)}{b}\right)} + \dots + e^{\left((-1)^{k+1} \frac{(b-1)(q-1)}{b}\right)}\right| \\ & = 0. \end{aligned} \quad \square$$

Since $(b, q-1) = 1$ and $0 < \ell < b$ (see (3)), the number $(q-1)\ell/b$ is not an integer. Hence,

$$\sum_{\mathbf{e} \in F(\mathbf{r}_j) \cup \varphi_1(F(\mathbf{r}_j)) \cup \dots \cup \varphi_{b-1}(F(\mathbf{r}_j))} W(\mathbf{e}) = 0.$$

### 4.2.5 Final estimates

We write $F = \bigcup_{\mathbf{r}_j} F(\mathbf{r}_j)$ and reconsider equation (36). We trivially bound the second sum in (36). We have, according to the inequality (34),

$$\begin{aligned} \sum_{\mathbf{r}_j \in \Re} \left| \sum_{\mathbf{e} \notin F(\mathbf{r}_j) \cup \varphi_1(F(\mathbf{r}_j)) \cup \dots \cup \varphi_{b-1}(F(\mathbf{r}_j))} W(\mathbf{e}) \right| & \le \sum_{\mathbf{r}_j \in \Re} \sum_{\mathbf{e} \notin F(\mathbf{r}_j) \cup \varphi_1(F(\mathbf{r}_j)) \cup \dots \cup \varphi_{b-1}(F(\mathbf{r}_j))} 1 \\ & \le \left| \sum_{\mathbf{e} \notin F \cup \varphi_1(F) \cup \dots \cup \varphi_{b-1}(F)} 1 \right| \\ & \le (q^{(k+1)(K+b(k+1))} - 1)^{\frac{j}{K+b(k+1)}}. \end{aligned}$$
We insert this information in (36) and get

$$ \sum_{\mathbf{r}_j \in \mathfrak{R}} |p_{\mathbf{r}_0, \mathbf{r}_j}^{(j)}| \le \frac{1}{q^{(k+1)j}} (q^{(k+1)(K+b(k+1))} - 1)^{\frac{j}{K+b(k+1)}}. $$

At this point, we take

$$ j = K + b(k + 1). $$

By taking the maximum over $\mathbf{r}_0 \in \mathfrak{R}$, we obtain

$$ M = \max_{\mathbf{r}_0 \in \mathfrak{R}} \left( \sum_{\mathbf{r}_j \in \mathfrak{R}} |p_{\mathbf{r}_0, \mathbf{r}_j}^{(j)}| \right) \le 1 - \frac{1}{q^{(k+1)(K+b(k+1))}}. \quad (39) $$

Using inequality (30), we get, for each term of the sequence $(v_\rho)_{\rho \ge 0} = (\max_{\mathbf{r} \in \mathfrak{R}} |A(\rho, \mathbf{r})|)_{\rho \ge 0}$, the bound

$$ \begin{aligned} v_\rho &\le v_{\rho-j} \max_{\mathbf{r}_0 \in \mathfrak{R}} \left( \sum_{\mathbf{r}_j \in \mathfrak{R}} |p_{\mathbf{r}_0, \mathbf{r}_j}^{(j)}| \right) \\ &\le M v_{\rho-j}. \end{aligned} $$

Thus, by iterating, and using the fact that for all $r \ge 0$, $v_r \le 1$, we get

$$ v_{\rho} \le M^{\lfloor \frac{\rho}{K+b(k+1)} \rfloor} \quad (40) $$

and

$$ A(\rho, \mathbf{r}_0) \le \left( 1 - \frac{1}{q^{(k+1)(K+b(k+1))}} \right)^{\lfloor \frac{\rho}{K+b(k+1)} \rfloor} \le 2 \left( 1 - \frac{1}{q^{(k+1)(K+b(k+1))}} \right)^{\frac{\rho}{K+b(k+1)}} \ll q^{-\eta_0 \rho}, $$

with

$$ \eta_0 = - \frac{\log\left(1 - \frac{1}{q^{(k+1)(K+b(k+1))}}\right)}{(\log q)(K + b(k + 1))}. $$

Using the inequality $\log(1-x) \le -x$ (valid for all $0 \le x < 1$), we have

$$ \eta_0 \ge \frac{1}{(\log q)(K + b(k + 1))q^{(k+1)(K+b(k+1))}}. $$

# 5 Proof of Theorem 1.6

Let $\rho_2 \ge \rho_1 > 0$ and let $N, D > 1$ be two integers such that

$$ N^{\rho_1} \le D \le N^{\rho_2}. $$

We recall that

$$ S_0(N, q^{\nu}, \xi) = \sum_{q^{\nu} \le m < q^{\nu+1}} \max_{a \ge 0} \left| \sum_{0 \le n < N} e \left( \frac{\ell}{b} s_q(nm + a) \right) e(n\xi) \right|. $$

It is sufficient to show that there exists $\eta_1 = \eta_1(\rho_1, \rho_2) > 0$ and $C = C(\rho_1, \rho_2) > 0$ such that

$$ \frac{S_0(N, q^{\nu}, \xi)}{N q^{\nu}} \le C N^{-\eta_1} \quad (41) $$
for $\nu \in \mathbb{N}$ satisfying $D < q^{\nu} \le qD$. Indeed, if we suppose that the inequality (41) is true, then we have

$$
\begin{aligned}
S_0(N, D, \xi) &= \sum_{D \le m < qD} \max_{a \ge 0} \left| \sum_{0 \le n < N} e \left( \frac{\ell}{b} s(nm + a) \right) e(n\xi) \right| \\
&\le \sum_{q^{\nu-1} \le m < q^{\nu}} \max_{a \ge 0} \left| \sum_{0 \le n < N} e \left( \frac{\ell}{b} s(nm + a) \right) e(n\xi) \right| + \sum_{q^{\nu} \le m < q^{\nu+1}} \max_{a \ge 0} \left| \sum_{0 \le n < N} e \left( \frac{\ell}{b} s(nm + a) \right) e(n\xi) \right| \\
&\le S_0(N, q^{\nu-1}, \xi) + S_0(N, q^{\nu}, \xi) \\
&\le CN^{1-\eta_1} q^{\nu-1} + CN^{1-\eta_1} q^{\nu} \\
&\le (q+1)CN^{1-\eta_1} D.
\end{aligned}
$$

We follow the proof method of [21]. As a first step we iterate the van der Corput inequality $k$ times. After that, the next step consists in rewriting the final expression as a Gowers norm. In the last step, we will choose the various parameters and use the Gowers norm estimate to conclude the proof.

## 5.1 Step 1: Iterating the van der Corput inequality

### 5.1.1 The first iteration

The first iteration of the van der Corput inequality allows to reduce the initial problem to a problem where $s_q$ is replaced by the periodic function $s_q^{\lambda}$ with

$$ \lambda > \nu + 1, \tag{42} $$

at the cost of an error generated by carry propagation (Lemma 3.3). We rewrite the error term in a form that is convenient with respect to the iterations that we wish to perform.

**Lemma 5.1.** Let $1 < H_0 \le N$ and $\lambda > \nu + 1$ be integers. We define for $h_0 \in \mathbb{N}$,

$$ S_1 = S_1(h_0) = \sum_{0 \le n < N} e \left( \frac{\ell}{b} \left( s_q^{\lambda}((n+h_0)m+a) - s_q^{\lambda}(nm+a) \right) \right) $$

and

$$ E_0 = \frac{3}{H_0} + \frac{4H_0}{q^{\lambda-\nu-1}} + \frac{8H_0}{N}. \tag{43} $$

Then, we have

$$ \left| S_0(N, q^{\nu}, \xi) \right|^2 \le (q^{\nu+1} N)^2 E_0 + \frac{2^2 N q^{\nu+1}}{H_0} \sum_{m=q^{\nu}}^{q^{\nu+1}} \max_{a \ge 0} \sum_{1 \le h_0 < H_0} |S_1|. $$

*Proof.* By the Cauchy–Schwarz inequality, we have

$$
\begin{aligned}
\left| S_0(N, q^{\nu}, \xi) \right|^2 &\le (q^{\nu+1} - q^{\nu}) \sum_{m=q^{\nu}}^{q^{\nu+1}} \left( \max_{a \ge 0} \left| \sum_{0 \le n < N} e \left( \frac{\ell}{b} s_q(nm + a) \right) e(n\xi) \right| \right)^2 \\
&\le q^{\nu+1} \sum_{m=q^{\nu}}^{q^{\nu+1}} \left( \max_{a \ge 0} \left| \sum_{0 \le n < N} e \left( \frac{\ell}{b} s_q(nm + a) \right) e(n\xi) \right| \right)^2.
\end{aligned}
$$
Let $1 < H_0 \le N$ be an integer. We apply Lemma 2.6 and get

$$ \begin{aligned} \left| \sum_{0 \le n < N} e\left(\frac{\ell}{b} s_q(nm + a)\right) e(n\xi) \right|^2 &\le \frac{2N^2}{H_0} + \frac{4N}{H_0} \sum_{1 \le h_0 < H_0} \left| \sum_{0 \le n < N - h_0} e\left(\frac{\ell}{b} (s_q((n+h_0)m+a) - s_q(nm+a))\right) \right| \\ &\le \frac{2N^2}{H_0} + \frac{4N}{H_0} \sum_{1 \le h_0 < H_0} \left| \sum_{0 \le n < N} e\left(\frac{\ell}{b} (s_q((n+h_0)m+a) - s_q(nm+a))\right) \right| \\ &\quad + \frac{4N}{H_0} \sum_{1 \le h_0 < H_0} h_0. \end{aligned} $$

Thus, by the carry propagation lemma (Lemma 3.3) we get, for $\lambda > \nu + 1$,

$$ \left| \sum_{0 \le n < N} e\left(\frac{\ell}{b} s_q(nm + a)\right) e(n\xi) \right|^2 \le \frac{2N^2}{H_0} + \frac{4N}{H_0} \sum_{1 \le h_0 < H_0} \left| \sum_{0 \le n < N} e\left(\frac{\ell}{b} (s_q^{\lambda}((n+h_0)m+a) - s_q^{\lambda}(nm+a))\right) \right| \\ + \frac{4N}{H_0} \sum_{1 \le h_0 < H_0} h_0 \left( \frac{Nm}{q^{\lambda}} + 3 \right). $$

This implies

$$ \left| \sum_{0 \le n < N} e\left(\frac{\ell}{b} s_q(nm + a)\right) e(n\xi) \right|^2 \le \frac{2N^2}{H_0} + 4NH_0 \left( \frac{Nm}{q^{\lambda}} + 3 \right) \\ + \frac{4N}{H_0} \sum_{1 \le h_0 < H_0} \left| \sum_{0 \le n < N} e\left(\frac{\ell}{b} (s_q^{\lambda}((n+h_0)m+a) - s_q^{\lambda}(nm+a))\right) \right|. $$

This leads to

$$ \left| S_0(N, q^{\nu}, \xi) \right|^2 \le (q^{\nu+1}N)^2 E_0 + \frac{2^2 N q^{\nu+1}}{H_0} \sum_{m=q^{\nu}}^{q^{\nu+1}} \max_{a \ge 0} \sum_{1 \le h_0 < H_0} |S_1|, $$

where

$$ S_1 = \sum_{0 \le n < N} e\left(\frac{\ell}{b} (s_q^{\lambda}((n+h_0)m+a) - s_q^{\lambda}(nm+a))\right) $$

and

$$ E_0 = \frac{3}{H_0} + \frac{4H_0}{q^{\lambda-\nu-1}} + \frac{8H_0}{N}. $$

□

### 5.1.2 The further iterations

Following Spiegelhofer [21], we continue to apply the van der Corput inequality. At this point, for the $(k-1)$ next applications of the van der Corput inequality, we will use Lemma 2.7. Let $\mu > 0$, and another parameter

$$ \sigma < \mu. \qquad (44) $$

For $q^{\nu} \le m \le q^{\nu+1}$, we define

$$ K_1 = Q_{q^{2\mu+2\sigma}} \left( \frac{m}{q^{2\mu}} \right) Q_{q^{\sigma}} \left( \frac{P_{q^{2\mu+2\sigma}}(m/q^{2\mu})}{q^{(k-2)\mu}} \right), \quad M_1 = P_{q^{2\mu+2\sigma}} \left( \frac{m}{q^{2\mu}} \right) Q_{q^{\sigma}} \left( \frac{P_{q^{2\mu+2\sigma}}(m/q^{2\mu})}{q^{(k-2)\mu}} \right) \quad (45) $$

and for $2 \le i < k - 1$, we define
$$ K_i = Q_{q^{\mu+2\sigma}} \left( \frac{m}{q^{(i+1)\mu}} \right) Q_{q^{\sigma}} \left( \frac{P_{q^{\mu+2\sigma}}(m/q^{(i+1)\mu})}{q^{(k-1-i)\mu}} \right), \qquad M_i = P_{q^{\mu+2\sigma}} \left( \frac{m}{q^{(i+1)\mu}} \right) Q_{q^{\sigma}} \left( \frac{P_{q^{\mu+2\sigma}}(m/q^{(i+1)\mu})}{q^{(k-i-1)\mu}} \right). \tag{46} $$

Finally, we define

$$ K_{k-1} = Q_{q^{\mu+\sigma}} \left( \frac{m}{q^{k\mu}} \right), \qquad M_{k-1} = P_{q^{\mu+\sigma}} \left( \frac{m}{q^{k\mu}} \right). \tag{47} $$

The numbers $K_1, \dots, K_{k-1}$ will be the shifts appearing in Lemma 2.7. The choice of these shifts is motivated by our wish to approximate, during the numerous digit cutting phases, the emerging fractions by integers (multiples of powers of $q$), using Proposition B.6. Classical results on Farey fractions will later allow us to count the number of repetitions of an element modulo $q^\rho$, by Lemma 3.6. To begin with, since $Q_n(\alpha) \le n$ for all $\alpha \in \mathbb{R}$ and for all $n > 0$, we see that

$$ K_1 \le q^{2\mu+3\sigma} \tag{48} $$

and for all $2 \le i \le k - 1$, we have

$$ K_i \le q^{\mu+3\sigma}. \tag{49} $$

The second iteration of the van der Corput inequality is described in the following lemma. This time, we use Lemma 2.7.

**Lemma 5.2.** We take the same notations as in Lemma 5.1, with the additional condition $E_0 \le 1$. Let $1 < H_1 \le N$ be an integer. We define for $h_0, h_1 \in \mathbb{N}$,

$$ S_2 = S_2(h_0, h_1) = \sum_{0 \le n < N} e \left( \frac{\ell}{b} \sum_{w_0, w_1 \in \{0, 1\}} (-1)^{w_0+w_1} s_q^{\lambda}((n+w_0h_0+w_1h_1K_1)m + a) \right) $$

and

$$ E_1 = \frac{3 \times 2^5 H_1 q^{2\mu+3\sigma}}{N}. $$

Then, we have

$$ \left|S_0(N, q^{\nu}, \xi)\right|^4 \le 2(q^{\nu+1}N)^4(E_0 + E_1) + \frac{2^6 N^3 q^{3(\nu+1)}}{H_0 H_1} \sum_{m=q^{\nu}}^{q^{\nu+1}} \max_{\substack{a \ge 0 \\ 1 \le h_0 < H_0 \\ 0 \le h_1 < H_1}} \sum_{1 \le h_0 < H_0} |S_2|. $$

*Proof.* By the inequality $(a+b)^2 \le 2a^2 + 2b^2$, valid for $a, b \ge 0$, we square both sides of the inequality in Lemma 5.1 to get

$$ \begin{aligned} \left|S_0(N, q^{\nu}, \xi)\right|^4 &\le \left( (q^{\nu+1}N)^2 E_0 + \frac{2^2 N q^{\nu+1}}{H_0} \sum_{m=q^{\nu}}^{q^{\nu+1}} \max_{a \ge 0} \sum_{1 \le h_0 < H_0} |S_1| \right)^2 \\ &\le 2(q^{\nu+1}N)^4 E_0^2 + \frac{2^5 N^2 q^{2(\nu+1)}}{H_0^2} \left( \sum_{m=q^{\nu}}^{q^{\nu+1}} \max_{a \ge 0} \sum_{1 \le h_0 < H_0} |S_1| \right)^2. \end{aligned} $$

By the Cauchy-Schwarz inequality (applied twice in order to handle the “$\max_{a \ge 0}$”),

$$ \left( \sum_{m=q^{\nu}}^{q^{\nu+1}} \max_{a \ge 0} \sum_{1 \le h_0 < H_0} |S_1| \right)^2 \le q^{\nu+1} H_0 \sum_{m=q^{\nu}}^{q^{\nu+1}} \max_{a \ge 0} \sum_{1 \le h_0 < H_0} |S_1|^2, $$
we have

$$ \left| S_0(N, q^{\nu}, \xi) \right|^4 \le 2(q^{\nu+1}N)^4 E_0^2 + \frac{2^5 N^2 q^{3(\nu+1)}}{H_0} \sum_{m=q^{\nu}}^{q^{\nu+1}} \max_{a \ge 0} \sum_{1 \le h_0 < H_0} |S_1|^2. \quad (50) $$

We will use this inequality later. We apply Lemma 2.7 for $S_1$, $H = H_1$ and $K = K_1$, and we get

$$ \begin{aligned} |S_1|^2 &\le 2 \frac{N + K_1(H_1 - 1)}{H_1} \sum_{0 \le h_1 < H_1} \left( \underbrace{\left| \sum_{0 \le n < N} e \left( \frac{\ell}{b} \sum_{w_0, w_1 \in \{0,1\}} (-1)^{w_0+w_1} s_q^{\lambda}((n+w_0h_0+w_1h_1K_1)m+a) \right) \right|}_{S_2} + h_1 K_1 \right) \\ &\le 2 \frac{N + K_1(H_1 - 1)}{H_1} \left( \sum_{0 \le h_1 < H_1} |S_2| + H_1^2 K_1 \right) \\ &\le \frac{2N}{H_1} \sum_{0 \le h_1 < H_1} |S_2| + \frac{2}{H_1} \left( N H_1^2 K_1 + H_1^2 K_1^2 (H_1 - 1) + K_1(H_1 - 1) \sum_{0 \le h_1 < H_1} |S_2| \right). \end{aligned} $$

We trivially estimate

$$ \sum_{0 \le h_1 < H_1} |S_2| \le NH_1 $$

and get

$$ \begin{aligned} |S_1|^2 &\le \frac{2N}{H_1} \sum_{0 \le h_1 < H_1} |S_2| + \frac{2}{H_1} (NH_1^2 K_1 + H_1^2 K_1^2 (H_1 - 1) + NH_1 K_1 (H_1 - 1)) \\ &\le \frac{2N}{H_1} \sum_{0 \le h_1 < H_1} |S_2| + 2 (NH_1 K_1 + H_1 K_1^2 (H_1 - 1) + NK_1 (H_1 - 1)). \end{aligned} $$

Since $H_1 \le N$, $K_1 \ge 2$ and $K_1(H_1 - 1) < N$ we have

$$ |S_1|^2 \le \frac{2N}{H_1} \sum_{0 \le h_1 < H_1} |S_2| + 6NH_1K_1. $$

Using the inequalities (48) and (49), we get

$$ \sum_{m=q^{\nu}}^{q^{\nu+1}} \max_{a \ge 0} \sum_{1 \le h_0 < H_0} |S_1|^2 \le \frac{2N}{H_1} \sum_{m=q^{\nu}}^{q^{\nu+1}} \max_{a \ge 0} \sum_{\substack{1 \le h_0 < H_0 \\ 0 \le h_1 < H_1}} |S_2| + 6Nq^{\nu+1}H_1H_0q^{2\mu+3\sigma}. \quad (51) $$

Since $E_0 \le 1$, we have $E_0^2 \le E_0$. Hence, injecting this inequality and (51) in (50), we have

$$ \left| S_0(N, q^{\nu}, \xi) \right|^4 \le 2(q^{\nu+1}N)^4 (E_0 + E_1) + \frac{2^6 N^3 q^{3(\nu+1)}}{H_0 H_1} \sum_{m=q^{\nu}}^{q^{\nu+1}} \max_{a \ge 0} \sum_{\substack{1 \le h_0 < H_0 \\ 0 \le h_1 < H_1}} |S_2|, $$

where

$$ S_2 = \sum_{0 \le n < N} e \left( \frac{\ell}{b} \sum_{w_0, w_1 \in \{0,1\}} (-1)^{w_0+w_1} s_q^{\lambda}((n+w_0h_0+w_1h_1K_1)m+a) \right) $$
and

$$E_1 = \frac{3 \times 2^5 H_1 q^{2\mu+3\sigma}}{N}.$$

<figure><img src="image_4.png" /></figure>

Until the end of the proof, we set

$$\rho = \lambda - k\mu. \tag{52}$$

We choose $H_1 = q^\rho$. This choice will allow us to use the bound $E_1 + E_0 \le 1$ and thus $(E_1 + E_0)^2 \le E_1 + E_0$. By applying exactly the same argument as before, we have, by a second application of Lemma 2.7, the following lemma:

**Lemma 5.3.** We take the same notations as in Lemma 5.1 and Lemma 5.2, with the condition $E_0 + E_1 \le 1$. Let $1 < H_2 \le N$ be an integer. We set

$$S_3 = \sum_{0 \le n < N} e \left( \frac{\ell}{b} \sum_{w_0, w_1, w_2 \in \{0,1\}} (-1)^{w_0+w_1+w_2} s_q^{\lambda} \left( (n + w_0 h_0 + w_1 h_1 K_1 + w_2 h_2 K_2)m + a \right) \right)$$

and

$$E_2 = \frac{3 \times 2^{12} H_2 K_2}{N}.$$

Then, we have

$$|S_0(N, q^\nu, \xi)|^8 \le 2^2 (q^\nu N)^8 (E_0 + E_1 + E_2) + \frac{2^{14} N^7 q^{7(\nu+1)}}{H_0 H_1 H_2} \sum_{\substack{1 \le h_0 < H_0 \\ 0 \le h_1 < H_1 \\ 0 \le h_2 < H_2}} \sum_{m=q^\nu}^{q^{\nu+1}} \max_{a \ge 0} |S_3|.$$

At this point, we can have a recursive formula for the k-th iteration of the van der Corput inequality. In the following lemma, we first sum over $m$. The next step will consist in carrying out some digits shiftings for a fixed parameter $m$.

**Lemma 5.4.** Let $k \ge 2$ be an integer. Let $H_0, H_1, \dots, H_{k-1} > 1$ be integers. We set

$$\begin{align}
E_0 &= \frac{3}{H_0} + \frac{4H_0}{q^{\lambda-\nu}} + \frac{8H_0}{N}, \\
E_i &= \frac{3 \times 2^{2^{i+2}-1}}{2^{i+1}} \frac{H_i q^{2\mu+3\sigma}}{N}, \quad 1 \le i \le k-1. \tag{53}
\end{align}$$

Moreover, we assume that

$$E_0 + E_1 + \dots + E_{k-1} \le 1. \tag{54}$$

Set

$$S_4 = \sum_{0 \le n < N} e \left( \frac{\ell}{b} \sum_{w = (w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^{\lambda} \left( nm + a + w_0 h_0 m + \sum_{i=1}^{k-1} w_i K_i m \right) \right).$$

Then we have the inequality

$$\left| \frac{S_0(N, q^\nu, \xi)}{q^{\nu+1} N} \right|^2 \le 2^{k-1} (E_0 + \dots + E_{k-1}) + \frac{2^{2^{k+2}-2}}{H_0 \dots H_{k-1} q^{\nu+1} N} \sum_{m=q^\nu}^{q^{\nu+1}} \sum_{\substack{1 \le h_0 < H_0 \\ 0 \le h_i < H_i, \ 1 \le i \le k-1}} \max_{a \ge 0} |S_4|. \tag{55}$$

Lemma 5.4 finishes the first step. Our final choice of the parameters will well respect (54). We will verify all arising inequalities in Annexe A.
## 5.2 Step 2: Digits shifting and cutting

The next goal is to transform $S_4$ in order to discard many blocks of digits by digits shifting. We recall the notation from Lemma 3.6:

$$ \mathfrak{M}_1 = P_{q^\sigma} \left( \frac{P_{q^{2\mu+2\sigma}}(m/q^{2\mu})}{q^{(k-2)\mu}} \right). $$

For $1 < i < k - 1$,

$$ \mathfrak{M}_i = P_{q^\sigma} \left( \frac{P_{q^{\mu+2\sigma}}(m/q^{(i+1)\mu})}{q^{(k-i-1)\mu}} \right) $$

and

$$ \mathfrak{M}_{k-1} = P_{q^\sigma} \left( \frac{P_{q^{\mu+\sigma}}(m/q^{k\mu})}{q^{k\mu}} \right). $$

We have the following lemma, which is the first transformation of $S_4$.

**Lemma 5.5.** We take the same notations as in Lemma 5.4 and the definition (52) of $\rho$. Then, we have

$$ S_4 = S_5 + O_k \left( N \sum_{i=2}^{k-1} D_N \left( \frac{m}{q^{i\mu}} \right) + \frac{2N}{q^\sigma} (H_1 + H_2 + \cdots + H_{k-1}) \right), \quad (56) $$

where

$$ S_5 = \sum_{0 \le n < N} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^\rho \left( \left\lfloor \frac{nm + a + w_0 h_0 m}{q^{k\mu}} + \sum_{i=1}^{k-1} w_i h_i \mathfrak{M}_i \right\rfloor \right) \right). \quad (57) $$

*Proof.* By (45), and by the definition of Farey sequences (see Annexe B), we have

$$ \frac{M_1}{K_1} = \frac{m}{q^{2\mu}}, $$

so that

$$ K_1 m = q^{2\mu} M_1. $$

In $S_4$, defined in (5.4), we replace $w_1h_1K_1m$ by $w_1h_1q^{2\mu}M_1$ and apply Lemma 3.1 with $u_1 = h_1M_1$ and $\alpha = 2\mu$. This gives for any $w_0, w_2, \dots, w_{k-1}, n, h_i$:

$$ \begin{aligned} & -s_q^{\lambda}(nm + a + w_0h_0m + h_1q^{2\mu}m + \sum_{j=2}^{k-1} w_ih_iK_im) + s_q^{\lambda}(nm + a + w_0h_0m + \sum_{j=2}^{k-1} w_ih_iK_im) \\ & = -s_q^{2\mu,\lambda}(nm + a + w_0h_0m + h_1q^{2\mu}m + \sum_{j=2}^{k-1} w_ih_iK_im) + s_q^{2\mu,\lambda}(nm + a + w_0h_0m + \sum_{j=2}^{k-1} w_ih_iK_im). \end{aligned} $$

We insert this in $S_4$ and recall that in the previous formula the first term of the right side corresponds to $w_1 = 1$, the second to $w_1 = 0$, with the “-” sign associated to the corresponding $(-1)^{s_2(w)}$. Furthermore, in the second line below we will use the fact that for $u \in \mathbb{N}$, $s_q^{2\mu,\lambda}(u) = s_q^{\lambda-2\mu}(\lfloor u/q^{2\mu} \rfloor)$:
$$
\begin{align}
S_4 &= \sum_{0 \le n < N} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^{2\mu,\lambda} (nm + a + w_0 h_0 m + w_1 h_1 q^{2\mu} m + \dots + w_{k-1} h_{k-1} K_{k-1} m) \right) \nonumber \\
&= \sum_{0 \le n < N} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^{\lambda-2\mu} \left( \left\lfloor \frac{1}{q^{2\mu}} \left( nm + a + w_0 h_0 m + \sum_{i=1}^{k-1} w_i h_i K_i m \right) \right\rfloor \right) \right) \nonumber \\
&= \sum_{0 \le n < N} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^{\lambda-2\mu} \left( \left\lfloor \frac{nm + a + w_0 h_0 m}{q^{2\mu}} + w_1 h_1 M_1 + w_2 h_2 \frac{K_2 m}{q^{2\mu}} + \sum_{i=3}^{k-1} w_i \frac{h_i K_i m}{q^{2\mu}} \right\rfloor \right) \right). \tag{58}
\end{align}
$$

We now wish to substitute $K_2m/q^{2\mu}$ by a multiple of a power of $q$. We first use Proposition B.6 to approximate the fraction $K_2m/q^{2\mu}$ by the integer $q^\mu M_2$ at the cost of an admissible error. By (46) we have

$$
\begin{align}
\left| \frac{K_2 m}{q^{2\mu}} - q^{\mu} M_2 \right| &= q^{\mu} Q_{q^{\sigma}} \left( \frac{P_{q^{\mu+2\sigma}}(m/q^{3\mu})}{q^{(k-3)\mu}} \right) \left| \frac{m}{q^{3\mu}} Q_{q^{\mu+2\sigma}} \left( \frac{m}{q^{3\mu}} \right) - P_{q^{\mu+2\sigma}} \left( \frac{m}{q^{3\mu}} \right) \right| \nonumber \\
&< q^{\sigma+\mu} \times \frac{1}{q^{\mu+2\sigma}} \nonumber \\
&= q^{-\sigma}. \tag{59}
\end{align}
$$

Moreover, we introduce the set

$$
A = \left\{ 0 \le n < N : \left\| \frac{nm + a + w_0 h_0 m}{q^{2\mu}} + w_1 h_1 M_1 + \sum_{i=3}^{k-1} w_i \frac{h_i K_i m}{q^{2\mu}} \right\| \ge \frac{H_2}{q^{\sigma}} \right\}.
$$

For $n \in A$, the inequality (59) shows that

$$
\left\| \frac{K_2 m}{q^{2 \mu}} \right\| < q^{- \sigma}.
$$

At this point, we assume that for all $1 \le i \le k-1$,

$$
H_i < q^{\sigma-1}. \tag{60}
$$

In Annexe A, we choose for all $1 \le i \le k-1$, $H_i = q^\rho$. Hence, we have the condition

$$
\rho < \sigma - 1. \tag{61}
$$

As $0 \le h_2 \le H_2 < q^{\sigma-1}$, we have by the inequality (10) in Proposition 2.3,

$$
\left\langle \frac{h_2 K_2 m}{q^{2\mu}} \right\rangle = h_2 \left\langle \frac{K_2 m}{q^{2\mu}} \right\rangle = h_2 q^{\mu} M_2.
$$

Hence, by the inequality (8) in Proposition 2.3, we get
$$
\begin{align*}
& \left\lfloor \frac{nm + a + w_0 h_0 m}{q^{2\mu}} + w_1 h_1 M_1 + \sum_{i=3}^{k-1} w_i \frac{h_i K_i m}{q^{2\mu}} + w_2 \frac{h_2 K_2 m}{q^{2\mu}} \right\rfloor \\
&= \left\lfloor \frac{nm + a + w_0 h_0 m}{q^{2\mu}} + w_1 h_1 M_1 + \sum_{i=3}^{k-1} w_i \frac{h_i K_i m}{q^{2\mu}} \right\rfloor + w_2 \left\langle \frac{h_2 K_2 m}{q^{2\mu}} \right\rangle \\
&= \left\lfloor \frac{nm + a + w_0 h_0 m}{q^{2\mu}} + w_1 h_1 M_1 + \sum_{i=3}^{k-1} w_i \frac{h_i K_i m}{q^{2\mu}} \right\rfloor + w_2 h_2 q^\mu M_2 \\
&= \left\lfloor \frac{nm + a + w_0 h_0 m}{q^{2\mu}} + w_1 h_1 M_1 + w_2 h_2 q^\mu M_2 + \sum_{i=3}^{k-1} w_i \frac{h_i K_i m}{q^{2\mu}} \right\rfloor.
\end{align*}
$$

By separating the sum in (58) on whether $n \in A$ or not, and by using Lemma 3.4 in order to bound the sum for $n \notin A$, we get

$$
S_4 = \sum_{0 \le n < N} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^{\lambda-2\mu} \left( \left\lfloor \frac{nm + a + w_0 h_0 m}{q^{2\mu}} + w_1 h_1 M_1 + w_2 h_2 q^\mu M_2 + \sum_{i=3}^{k-1} w_i \frac{h_i K_i m}{q^{2\mu}} \right\rfloor \right) \right) \\
+ O \left( N D_N \left( \frac{m}{q^{2\mu}} \right) + \frac{2H_1 N}{q^\sigma} \right).
$$

Repeating the same argument as before, we have

$$
S_4 = \sum_{0 \le n < N} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^{\lambda-3\mu} \left( \left\lfloor \frac{nm + a + w_0 h_0 m}{q^{3\mu}} + w_1 h_1 \frac{M_1}{q^\mu} + w_2 h_2 M_2 + \sum_{i=3}^{k-1} w_i \frac{h_i K_i m}{q^{3\mu}} \right\rfloor \right) \right) \\
+ O \left( N \left( D_N \left( \frac{m}{q^{2\mu}} \right) + D_N \left( \frac{m}{q^{3\mu}} \right) \right) + \frac{2N}{q^\sigma} (H_1 + H_2) \right).
$$

We continue the process and get

$$
S_4 = \sum_{0 \le n < N} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^{\lambda-k\mu} \left( \left\lfloor \frac{nm + a + w_0 h_0 m}{q^{k\mu}} + \sum_{i=1}^{k-1} w_i \frac{h_i M_i}{q^{(k-1-i)\mu}} \right\rfloor \right) \right) \\
+ O \left( N \sum_{i=2}^{k-1} D_N \left( \frac{m}{q^{i\mu}} \right) + \frac{2N}{q^\sigma} (H_1 + \dots + H_{k-1}) \right).
$$

In order to remove $M_i/q^{(k-1-i)\mu}$ ($1 \le i \le k-1$), we use the Farey approximation again (Proposition B.6).
We have,

$$
\left| \underbrace{\frac{P_{q^{2\mu+2\sigma}}\left(\frac{m}{q^{2\mu}}\right)}{q^{(k-2)\mu}} Q_{q^\sigma} \left( \frac{P_{q^{2\mu+2\sigma}}(m/q^{2\mu})}{q^{(k-2)\mu}} \right)}_{M_1/q^{(k-2)\mu}} - P_{q^\sigma} \left( \frac{P_{q^{2\mu+2\sigma}}(m/q^{2\mu})}{q^{(k-2)\mu}} \right) \right| < q^{-\sigma}.
$$

For $1 < i < k - 1$, we have

$$
\left| \underbrace{\frac{P_{q^{\mu+2\sigma}}\left(\frac{m}{q^{(i+1)\mu}}\right)}{q^{(k-i-1)\mu}} Q_{q^{\sigma}}\left(\frac{P_{q^{\mu+2\sigma}}(m/q^{(i+1)\mu})}{q^{(k-i-1)\mu}}\right)}_{M_i/q^{(k-i-1)\mu}} - P_{q^{\sigma}}\left(\frac{P_{q^{\mu+2\sigma}}(m/q^{(i+1)\mu})}{q^{(k-i-1)\mu}}\right) \right| < q^{-\sigma}
$$
and

$$ \left| \underbrace{\frac{P_{q^{\mu+\sigma}}\left(\frac{m}{q^{k\mu}}\right)}{q^{k\mu}} Q_{q^{\sigma}}\left(\frac{P_{q^{\mu+\sigma}}(m/q^{k\mu})}{q^{k\mu}}\right)}_{M_{k-1}/q^{k\mu}} - P_{q^{\sigma}}\left(\frac{P_{q^{\mu+\sigma}}(m/q^{k\mu})}{q^{k\mu}}\right) \right| < q^{-\sigma}. $$

With the same argument as before, we get

$$ S_4 = \underbrace{\sum_{0 \le n < N} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^{\lambda-k\mu} \left( \left\lfloor \frac{nm+a+w_0h_0m}{q^{k\mu}} + \sum_{i=1}^{k-1} w_i h_i \mathfrak{M}_i \right\rfloor \right) \right)}_{S_5} \\ + O_k \left( N \sum_{i=2}^{k-1} D_N \left( \frac{m}{q^{i\mu}} \right) + \frac{2N}{q^{\sigma}} (H_1 + H_2 + \dots + H_{k-1}) \right), $$

which ends the proof of Lemma 5.5.

<figure><img src="image_5.png" /></figure>

Our next goal is to handle the term

$$ \left\lfloor \frac{nm+a}{q^{k\mu}} \right\rfloor $$

present in $S_5$ in order to simplify even further the argument of $s_q^{\lambda-k\mu}$. Recall that $\rho = \lambda - k\mu$, by (52).

**Lemma 5.6.** Let $T, h_0, m \ge 2$ be integers. We set

$$ \Lambda = \Lambda(h_0, m) = \{0 \le t < T : \left[ \frac{t}{T} + \frac{h_0 m}{q^{k\mu}}, \frac{t+1}{T} + \frac{h_0 m}{q^{k\mu}} \right[ \cap \mathbb{Z} = \emptyset \right\}. \quad (62) $$

Then for all $k \ge 1$,

$$ \left| \frac{S_0(N, \nu, \xi)}{q^{\nu+1}N} \right|^{2^k} \le 2^{k-1}(E_0 + \dots + E_{k-1}) + \frac{2^{2^{k+2}-2}}{T} + \frac{2^{2^{k+2}-2}}{H_0 \dots H_{k-1} q^{\nu+1+\rho} T} \sum_{m=q^{\nu}}^{q^{\nu+1}} \sum_{1 \le i \le k-1, 0 \le h_i < H_i} \sum_{t \in \Lambda} |S_8| \\ + 2^{2^{k+2}-2} O \left( \frac{T}{q^{\nu+1-\rho}} \sum_{m=q^{\nu}}^{q^{\nu+1}} D_N \left( \frac{m}{q^{\lambda}} \right) + \frac{1}{q^{\nu+1}} \sum_{m=q^{\nu}}^{q^{\nu+1}} \sum_{i=2}^{k-1} D_N \left( \frac{m}{q^{i\mu}} \right) + \frac{2(H_1 + \dots + H_{k-1})}{q^{\sigma}} \right), $$

where

$$ S_8 = \sum_{0 \le n' < q^\rho} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^\rho \left( n' + \left\lfloor \frac{t}{T} + \frac{w_0 h_0 m}{q^{k\mu}} \right\rfloor + \sum_{1 \le i \le k-1} w_i h_i \mathfrak{M}_i \right) \right). $$

*Proof.* For all $0 \le n \le N$, there exists a unique couple $(t, n')$ such that $0 \le t < T$ and $0 \le n' < q^\rho$ where $t/T \le \{(nm + a)/q^{k\mu}\} < (t+1)/T$ and $\lfloor \frac{nm+a}{q^{k\mu}} \rfloor \equiv n' \pmod{q^\rho}$. We rewrite $S_5$ (cf. (57)) and split the sum
into two parts according to the values of $1 \le t < T$ whether they lie in $\Lambda$ or not:

$$
\begin{align*}
S_5 &= \sum_{0 \le t < T} \sum_{0 \le n' < q^\rho} \sum_{\substack{0 \le n < N \\ t/T \le \frac{(nm+a)}{q^{k\mu}} < (t+1)/T \\ \lfloor \frac{nm+a}{q^{k\mu}} \rfloor \equiv n' \pmod{q^\rho}}} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^\rho \left( \lfloor \frac{nm+a}{q^{k\mu}} + \frac{w_0 h_0 m}{q^{k\mu}} \rfloor \right. \right. \\
&\qquad \left. \left. + \sum_{1 \le i \le k-1} w_i h_i \mathfrak{M}_i \right) \right) \\
&= \sum_{t \in \Lambda} + \sum_{t \notin \Lambda} =: S_6 + S_7.
\end{align*}
$$

Since

$$
\bigcup_{t=0}^{T-1} \left[ \frac{t}{T} + \frac{h_0 m}{q^{k\mu}}, \frac{t+1}{T} + \frac{h_0 m}{q^{k\mu}} \right] = \left[ \frac{h_0 m}{q^{k\mu}}, \frac{h_0 m}{q^{k\mu}} + 1 \right]
$$

is an interval of length 1, this interval contains exactly one integer that must fall into exactly one of the T subintervals. Thus, $|\Lambda| = T - 1$.

• For $t \notin \Lambda$ (one single value of $t$), we trivially bound $S_7$ with Proposition 2.5:

$$
\begin{align*}
|S_7| &\le \sum_{0 \le n' < q^\rho} \sum_{\substack{0 \le n < N \\ t/T \le \frac{(nm+a)}{q^{k\mu}} < (t+1)/T \\ \lfloor \frac{nm+a}{q^{k\mu}} \rfloor \equiv n' \pmod{q^\rho}}} 1 \\
&\le q^\rho \left( \frac{N}{Tq^\rho} + O \left( N D_N \left( \frac{m}{q^{\rho+k\mu}} \right) \right) \right) \\
&= \frac{N}{T} + O \left( N q^\rho D_N \left( \frac{m}{q^\lambda} \right) \right).
\end{align*}
$$

• For $t \in \Lambda$ (which is, for $T-1$ values of $t$), we write

$$
\frac{nm + a}{q^{k\mu}} = \left\lfloor \frac{nm + a}{q^{k\mu}} \right\rfloor + \underbrace{\left\{ \frac{nm + a}{q^{k\mu}} \right\}}_{\in[t/T, (t+1)/T]} ,
$$

we deduce that for $w_0 \in \{0, 1\}$

$$
\left\lfloor \frac{nm + a}{q^{k\mu}} \right\rfloor + \frac{t}{T} + \frac{w_0 h_0 m}{q^{k\mu}} \le \frac{nm + a + w_0 h_0 m}{q^{k\mu}} < \left\lfloor \frac{nm + a}{q^{k\mu}} \right\rfloor + \frac{t+1}{T} + \frac{w_0 h_0 m}{q^{k\mu}}.
$$

Since $t \in \Lambda$, we have for $w_0 = 1$,

$$
\left\lfloor \frac{nm + a}{q^{k\mu}} \right\rfloor + \frac{t}{T} + \frac{h_0 m}{q^{k\mu}}, \left\lfloor \frac{nm + a}{q^{k\mu}} \right\rfloor + \frac{t+1}{T} + \frac{h_0 m}{q^{k\mu}} \cap \mathbb{Z} = \emptyset
$$

and therefore necessarily

$$
\left\lfloor \frac{nm + a}{q^{k\mu}} + \frac{w_0 h_0 m}{q^{k\mu}} \right\rfloor = \left\lfloor \frac{nm + a}{q^{k\mu}} \right\rfloor + \left\lfloor \frac{t}{T} + \frac{w_0 h_0 m}{q^{k\mu}} \right\rfloor. \quad (63)
$$
We note that (63) is true also in the case of $w_0 = 0$ and all $0 \le t < T$ with one exception. Thus, we have by periodicity of $s_q^\rho$,

$$
\begin{align*}
S_6 &= \sum_{t \in \Lambda} \sum_{0 \le n' < q^\rho} \sum_{\substack{0 \le n < N \\ t/T \le \frac{(nm+a)}{q^{k\mu}} < (t+1)/T \\ [(nm+a)/q^{k\mu}] \equiv n' \pmod{q^\rho}}} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^\rho \left( n' + \left\lfloor \frac{t}{T} + \frac{w_0 h_0 m}{q^{k\mu}} \right\rfloor + \sum_{1 \le i \le k-1} w_i h_i \mathfrak{M}_i \right) \right) \\
&= \sum_{t \in \Lambda} \sum_{0 \le n' < q^\rho} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^\rho \left( n' + \left\lfloor \frac{t}{T} + \frac{w_0 h_0 m}{q^{k\mu}} \right\rfloor + \sum_{1 \le i \le k-1} w_i h_i \mathfrak{M}_i \right) \right) \\
&\qquad \times \sum_{\substack{0 \le n < N \\ t/T \le \frac{(nm+a)}{q^{k\mu}} < (t+1)/T \\ [(nm+a)/q^{k\mu}] \equiv n' \pmod{q^\rho}} 1.
\end{align*}
$$

By Proposition 2.5, the sum over $n$ is $N/Tq^\rho + O(ND_N(q^{\rho+k\mu}))$. We trivially bound $|S_8|$ by $q^\rho$ in the estimate of the contribution of the error term $ND_N(q^{\rho+k\mu})$,

$$
\begin{aligned}
|S_6| &= \left| \sum_{t \in \Lambda} S_8 \left( \frac{N}{q^\rho T} + O \left( N D_N \left( \frac{m}{q^{\rho+k\mu}} \right) \right) \right) \right| \\
&\le \frac{N}{T q^\rho} \sum_{t \in \Lambda} |S_8| + O \left( q^\rho N T D_N \left( \frac{m}{q^\lambda} \right) \right).
\end{aligned}
$$

Hence, using the triangular inequality, we get

$$
\begin{align*}
|S_4| &\le |S_6| + |S_7| + O \left( N \sum_{i=2}^{k-1} D_N \left( \frac{m}{q^{i\mu}} \right) + \frac{2N}{q^\sigma} (H_1 + \dots + H_{k-1}) \right) \\
&\le \frac{N}{T q^\rho} \sum_{t \in \Lambda} |S_8| + \frac{N}{T} + O \left( q^\rho N T D_N \left( \frac{m}{q^\lambda} \right) + N \sum_{i=2}^{k-1} D_N \left( \frac{m}{q^{i\mu}} \right) + \frac{2N}{q^\sigma} (H_1 + \dots + H_{k-1}) \right).
\end{align*}
$$

We inject the last inequality in the equation (55) and get

$$
\begin{align}
\left| \frac{S_0(N, \nu, \xi)}{q^{\nu+1} N} \right|^{2^k} &\le 2^{k-1} (E_0 + \dots + E_{k-1}) + \frac{2^{2^{k+2}-2}}{H_0 \dots H_{k-1} q^{\nu+1} N} \sum_{m=q^\nu}^{q^{\nu+1}} \sum_{\substack{1 \le h_0 < H_0 \\ 0 \le h_i < H_i, \ 1 \le i \le k-1}} \max_{a \ge 0} |S_4| \nonumber \\
&\le 2^{k-1} (E_0 + \dots + E_{k-1}) + \frac{2^{2^{k+2}-2}}{T} \nonumber \\
&\quad + \frac{2^{2^{k+2}-2}}{H_0 \dots H_{k-1} q^{\nu+1+\rho} T} \sum_{m=q^\nu}^{q^{\nu+1}} \sum_{\substack{1 \le h_0 < H_0 \\ 0 \le h_i < H_i, \ 1 \le i \le k-1}} \sum_{t \in \Lambda} |S_8| \tag{64} \\
&\quad + 2^{2^{k+2}-2} O \left( \frac{T}{q^{\nu+1-\rho}} \sum_{m=q^\nu}^{q^{\nu+1}} D_N \left( \frac{m}{q^\lambda} \right) + \frac{1}{q^{\nu+1}} \sum_{m=q^\nu}^{q^{\nu+1}} \sum_{i=2}^k D_N \left( \frac{m}{q^{i\mu}} \right) \right. \nonumber \\
&\qquad \left. + \frac{2(H_1 + \dots + H_{k-1})}{q^\sigma} \right), \nonumber
\end{align}
$$
where for the last term we use a very rough bound.

<figure><img src="image_6.png" /></figure>

Until the end of the proof, for all $1 \le i \le k - 1$, we take

$$H_i = q^\rho. \tag{65}$$

(We note that since $\rho \in \mathbb{N}$ we also have $H_i \in \mathbb{N}$.) In order to bound (64), we will focus on the quantity

$$S_9 := \sum_{m=q^\nu}^{q^{\nu+1}} \sum_{0 \le h_1, \dots, h_{k-1} < q^\rho} |S_8| \le \sum_{m=0}^{q^{\nu+1}} \sum_{0 \le h_1, \dots, h_{k-1} < q^\rho} |S_8|.$$

For a fixed integer $\gamma > 0$ (to be chosen later), let

$$B = \{m \in \{0, \dots, q^{\nu+1}\} : \exists p | q, \exists i \in \{1, \dots, k-1\}, p^{3\gamma} | \mathfrak{M}_i\}. \tag{66}$$

We first split the sum $S_9$ based on whether $m \in B$ or not. For $m \notin B$, we replace $h_i \mathfrak{M} i$ (for $1 \le i < k$) by $h'_i$ and count the number of repetitions with Lemma 2.2. For $m \in B$, we bound the sum with Lemma 3.6. We will choose

$$\nu + 1 \ge 3\gamma, \tag{67}$$

see Annexe A. We therefore get

$$S_9 \le q^{3\gamma(k-1)} \sum_{m=0}^{q^{\nu+1}} \sum_{0 \le h'_1, \dots, h'_{k-1} < q^\rho} |S_{10}| + q^{\nu+1+k\rho-3\gamma \log_q(P^-(q))}, \tag{68}$$

where

$$S_{10} := \sum_{0 \le n' < q^\rho} e \left( \frac{\ell}{\bar{b}} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^\rho \left( n' + \left\lfloor \frac{t}{T} + \frac{w_0 h_0 m}{q^{k\mu}} \right\rfloor + \sum_{1 \le i \le k-1} w_i h'_i \right) \right).$$

We now want to simplify the terms $\theta_{h_0,m} := \lfloor t/T + w_0 h_0 m / q^{k\mu} \rfloor$ when $w_0 = 1$. Since $s_q^\rho$ is $q^\rho$-periodic, it is convenient to split the sums on the parameters $h_0$ and $m$ according to classes modulo $q^\rho$ of the $\theta_{h_0,m}$:

$$\sum_{m=0}^{q^{\nu+1}} |S_{10}| = \sum_{0 \le m' < q^\rho} a(m') \left| \sum_{0 \le n' < q^\rho} e \left( \frac{\ell}{\bar{b}} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^\rho \left( n' + w_0 m' + \sum_{1 \le i \le k-1} w_i h'_i \right) \right) \right|,$$

with

$$a(m') = \left| \{m \in \{0, \dots, q^{\nu+1}\} : \lfloor t/T + h_0 m / q^{k\mu} \rfloor \equiv m' \pmod{q^\rho}\} \right|.$$

Next we observe<fnref n="2" /> that for any $1 \le h_0 \le H_0$ we have

$$\left| \{m \in \{0, \dots, q^{\nu+1}\} : \lfloor t/T + h_0 m / q^{k\mu} \rfloor \equiv m' \pmod{q^\rho}\} \right| \ll q^{\nu+1-\rho}.$$

We deduce that

$$\sum_{m=0}^{q^{\nu+1}} |S_{10}| \ll q^{\nu+1-\rho} \sum_{0 \le m' < q^\rho} \left| \sum_{0 \le n' < q^\rho} e \left( \frac{\ell}{\bar{b}} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^\rho \left( n' + m' w_0 \sum_{1 \le i \le k-1} w_i h'_i \right) \right) \right|.$$

<footnote n="2">²For $h_0 \le q^{k\mu}$ and $w_0 = 1$, the set of $m \in \{0, \dots, q^{\nu+1}\}$ such that $\lfloor t/T + h_0 m / q^{k\mu} \rfloor \equiv m' \pmod{q^\rho}$ is the set of $m \in \{0, \dots, q^{\nu+1}\}$ such that $\lfloor t/T + h_0 m / q^{k\mu} \rfloor = m' + \alpha q^\rho$ for some $\alpha \in \mathbb{Z}$. For fixed $\alpha$, the number of $m$ satisfying $m' + \alpha q^\rho \le t/T + h_0 m / q^{k\mu} < m' + \alpha q^\rho + 1$ is $O(q^{k\mu}/h_0)$. Moreover, by the inequalities $m' + \alpha q^\rho \le t/T + h_0 m / q^{k\mu}$ and $m \le q^{\nu+1}$, we have $\alpha \ll h_0 q^{\nu+1} / q^{k\mu+\rho}$. Therefore, we have $\ll q^{k\mu}/h_0 \times h_0 q^{\nu+1} / q^{k\mu+\rho} = q^{\nu+1-\rho}$ integers $m \in \{0, \dots, q^{\nu+1}\}$ such that $\lfloor t/T + w_0 h_0 m / q^{k\mu} \rfloor \equiv m' \pmod{q^\rho}$.</footnote>
Injecting this in (68), we have (replacing $m'$ by $h_0$)

$$S_9 \ll q^{3\gamma(k-1)+\nu+1-\rho} \sum_{0 \le h_0, h_1, \dots, h_{k-1} < q^\rho} |S_{10}(h_0, \dots, h_k)| + q^{\nu+1+k\rho-3\gamma \log_q(P^-(q))}, \quad (69)$$

with

$$S_{10}(h_0, \dots, h_{k-1}) = \sum_{0 \le n' < q^\rho} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^{\rho} \left( n' + \sum_{0 \le i \le k} w_i h_i \right) \right).$$

We choose

$$H_0 \le q^{k\mu}. \quad (70)$$

We rewrote $h_i$ instead of $h_i'$ for clarity. Now, we want to remove the absolute values around $S_{10}$. For that purpose, we will use the following result.

**Lemma 5.7.** We have

$$|S_{10}(h_0, h_1, \dots, h_{k-1})|^2 = \sum_{0 \le h_k < q^\rho} S_{10}(h_0, h_1, \dots, h_{k-1}, h_k).$$

*Proof.* For $n' \in \{0, \dots, q^\rho - 1\}$, we define $g(n')$ by

$$g(n') = \sum_{\mathbf{w}=(w_0, \dots, w_{k-1}) \in \{0,1\}^k} (-1)^{s_2(w)} s_q^{\rho} \left( n' + \sum_{0 \le i \le k-1} w_i h_i \right).$$ $$|S_{10}(h_0, \dots, h_{k-1})|^2 = S_{10}(h_0, \dots, h_{k-1}) \overline{S_{10}(h_0, \dots, h_{k-1})}$$ $$= \sum_{0 \le n_1 < q^\rho} \sum_{0 \le n_2 < q^\rho} e \left( \frac{\ell}{b} (g(n_1) - g(n_2)) \right).$$

For $n_1 \in \{0, \dots, q^\rho - 1\}$, we perform the linear transformation $h_k = n_2 - n_1$ in the second sum. Thus, we have

$$|S_{10}(h_0, \dots, h_{k-1})|^2 = \sum_{0 \le n_1 < q^\rho} \sum_{-n_1 \le h_k < q^\rho - n_1} e \left( \frac{\ell}{b} (g(n_1) - g(n_1 + h_k)) \right).$$

For $n_1 \in \{0, \dots, q^\rho - 1\}$, the function $h_k \mapsto e \left( \frac{\ell}{b} (g(n_1) - g(n_1 + h_k)) \right)$ is $q^\rho$-periodic, since $g$ is $q^\rho$-periodic. Furthermore, the support of the sum over $h_k$ has length $q^\rho$. We conclude that

$$\sum_{-n_1 \le h_k < q^\rho - n_1} e \left( \frac{\ell}{b} (g(n_1) - g(n_1 + h_k)) \right) = \sum_{0 \le h_k < q^\rho} e \left( \frac{\ell}{b} (g(n_1) - g(n_1 + h_k)) \right).$$

Hence, by interchanging the sums, we deduce that

$$|S_{10}(h_0, \dots, h_{k-1})|^2 = \sum_{0 \le h_k < q^\rho} \sum_{0 \le n_1 < q^\rho} e \left( \frac{\ell}{b} (g(n_1) - g(n_1 + h_k)) \right)$$ $$= \sum_{0 \le h_k < q^\rho} \sum_{0 \le n_1 < q^\rho} e \left( \frac{\ell}{b} \sum_{\mathbf{w}=(w_0, \dots, w_k) \in \{0,1\}^{k+1}} (-1)^{s_2(w)} s_q^\rho \left( n' + \sum_{1 \le i \le k} w_i h_i \right) \right)$$ $$= \sum_{0 \le h_k < q^\rho} S_{10}(h_0, \dots, h_{k-1}, h_k).$$

□
We come back to (69). We use Cauchy-Schwarz inequality and Lemma 5.7 to obtain

$$
\sum_{0 \le h_0, \dots, h_{k-1} < q^\rho} |S_{10}(h_0, \dots, h_{k-1})| \le q^{k\rho/2} \left( \sum_{0 \le h_0, \dots, h_{k-1} < q^\rho} |S_{10}(h_0, \dots, h_{k-1})|^2 \right)^{1/2} \cdot \\
\le q^{k\rho/2} \left( \sum_{0 \le h_0, \dots, h_{k-1}, h_k < q^\rho} S_{10}(h_0, \dots, h_{k-1}, h_k) \right)^{1/2} .
$$

Thus, by Theorem 1.7 (for $k+1$ instead of $k$), we get

$$
\sum_{0 \le h_1, \dots, h_{k-1} < q^\rho} |S_{10}(h_1, \dots, h_{k-1})| \le q^{k\rho/2} \times q^{((k+2)\rho - \eta_0\rho)/2} = q^{k\rho + \rho - \rho\eta_0/2}. \quad (71)
$$

Summing up, we finally get<fnref n="3" />

$$
\begin{align*}
S_9 \le q^{3\gamma(k-1)+\nu+1-\rho} \sum_{0 \le h_1, \dots, h_{k-1} < q^\rho} |S_{10}(h_1, \dots, h_{k-1})| + q^{\nu+1+k\rho-3\gamma \log_q(P^-(q))} \\
\ll q^{3\gamma(k-1)+\nu+1+k\rho-\rho\eta_0/2} + q^{\nu+1+k\rho-3\gamma \log_q(P^-(q))}.
\end{align*}
$$

Since $H_i = q^\rho$ for all $1 \le i \le k-1$ (cf. (65)), we get

$$
\begin{align*}
& \frac{1}{H_0 \cdots H_{k-1} q^{\nu+1+\rho T}} \sum_{m=q^{\nu}}^{q^{\nu+1}} \sum_{0 \le h_i < H_i, 1 \le i \le k-1} \sum_{t \in \Lambda} |S_8| \\
& \le \frac{1}{H_0 \cdots H_{k-1} q^{\nu+1+\rho T}} \sum_{1 \le h_0 < H_0} \sum_{t \in \Lambda} S_9 \\
& \ll q^{3\gamma(k-1)-\rho\eta_0/2} + q^{-3\gamma \log_q(P^-(q))}.
\end{align*}
$$

Recall that (cf. Lemma 5.6)

$$
\left| \frac{S_0(N, q^\nu, \xi)}{q^{\nu+1} N} \right|^2 \le 2^{k-1} (E_0 + \dots + E_{k-1}) + \frac{2^{2^{k+2}-2}}{T} + \frac{2^{2^{k+2}-2}}{H_0 \cdots H_{k-1} q^{\nu+1+\rho T}} \sum_{m=q^\nu}^{q^{\nu+1}} \sum_{1 \le i \le k-1, 0 \le h_i < H_i} \sum_{t \in \Lambda} |S_8| \\
+ 2^{2^{k+2}-2} O \left( \frac{T}{q^{\nu+1-\rho}} \sum_{m=q^\nu}^{q^{\nu+1}} D_N \left( \frac{m}{q^\lambda} \right) + \frac{1}{q^{\nu+1}} \sum_{m=q^\nu}^{q^{\nu+1}} \sum_{i=2}^{k-1} D_N \left( \frac{m}{q^{i\mu}} \right) + \frac{H_1 + \dots + H_{k-1}}{q^\sigma} \right).
$$

Until the end of the proof, we suppose

$$
\nu + 1 \geq k\mu. \tag{72}
$$

Using Proposition 3.5 we have, for all $2 \le i \le k-1$,

$$
\begin{align*}
\sum_{m=q^{\nu}}^{q^{\nu+1}} D_N \left( \frac{m}{q^{i\mu}} \right) &\le q^{\nu+1-i\mu} \sum_{m=0}^{q^{i\mu}} D_N \left( \frac{m}{q^{i\mu}} \right) \\
&\ll q^{\nu+1-i\mu} \frac{N+q^{i\mu}}{N} (\log^+ N)^2 \\
&\ll q^{\nu+1} (\log^+ N)^2 \left( \frac{1}{N} + \frac{1}{q^{2\mu}} \right).
\end{align*}
$$

<footnote n="3">³By means of Theorem 1.7 and Lemma 5.7 we succeed to compensate the term $q^{3\gamma(k-1)}$ by $q^{-\rho\eta_0/2}$. Indeed, Lemma 5.7 allows us to remove the absolute value without losing the full summation over $\{0, \dots, q^\rho - 1\}$, which is necessary to apply Theorem 1.7.</footnote>
Moreover,

$$ \sum_{m=q^{\nu}}^{q^{\nu+1}} D_N \left( \frac{m}{q^{\lambda}} \right) \le \sum_{m=0}^{q^{\lambda}} D_N \left( \frac{m}{q^{\lambda}} \right) \ll \frac{N+q^{\lambda}}{N} (\log^+ N)^2 = q^{\lambda} (\log^+ N)^2 \left( \frac{1}{N} + \frac{1}{q^{\lambda}} \right). $$

According to (42), we have $\lambda > \nu + 1$.

Finally, using (43), (53) and (65), we have

$$ \begin{aligned} \left| \frac{S_0(N, q^{\nu}, \xi)}{q^{\nu+1} N} \right|^{2k} & \ll 2^k \left( \frac{1}{H_0} + \frac{H_0}{q^{\lambda-\nu}} + \frac{H_0}{N} + k 2^{2^{k+1}} \frac{q^{\rho+2\mu+3\sigma}}{N} \right) + \frac{2^{2^{k+2}}}{T} \\ & \quad + 2^{2^{k+2}} (q^{-3\gamma \log_q P^-(q)} + q^{3\gamma(k-1)-\eta_0 \rho/2}) \\ & \quad + 2^{2^{k+2}} \left( T q^{\lambda-\nu-1+\rho} (\log^+ N)^2 \left( \frac{1}{N} + \frac{1}{q^{2\mu}} \right) + \frac{k}{q^{\sigma-\rho}} \right). \end{aligned} \quad (73) $$

It remains to choose the parameters introduced in the proof in order to get Theorem 1.4 from (73). This is the aim of the next section. Since the principle of convexity applied for $H_0$ in (73) gives similar results as in [21, p.2581], we follow the choice of Spiegelhofer.

In order to define $\mu$, we recall that, by hypothesis (see beginning of Section 5), we have

$$ N^{\rho_1} < q^{\nu} \le q N^{\rho_2}. \quad (74) $$

We set $k = 3(\lfloor \rho_2 \rfloor + 1) \ge 3$ and define

$$ \mu = \left\lfloor \frac{\nu - 1}{k + 1/8} \right\rfloor, $$

and observe that $\mu \le \nu/k$ (thus, this choice respects (72)). Furthermore, we set

$$ \sigma = \left\lfloor \frac{\mu}{4} \right\rfloor, \quad \tilde{\rho} = \nu - k\mu. \quad (75) $$

With the definition of $\tilde{\rho}$, we set

$$ \gamma = \left\lfloor \frac{\eta_0 \tilde{\rho}}{12(k-1)} \right\rfloor. \quad (76) $$

Then, with the definition of $\gamma$, we define

$$ T = q^{\gamma}, \quad H_0 = \lfloor q^{\gamma/4} \rfloor. $$

With this definition of $H_0$, the condition (70) is satisfied for large enough $\gamma$ (we refer the reader to Corollary A.2). Moreover, we set

$$ \lambda = \nu + \left\lfloor \frac{\gamma}{2} \right\rfloor. $$

Condition (42) is satisfied, since $\gamma \to +\infty$. We recall again that

$$ \rho = \lambda - k\mu. \quad (77) $$

The reader will find the somewhat tedious calculations in Annexe A leading to the following estimate:

$$ \left| \frac{S_0(N, q^{\nu}, \xi)}{q^{\nu+1} N} \right|^{2k} \ll N^{-\frac{\rho_1 \eta_0}{(384k+48)(k-1)}} + N^{-\frac{3\eta_0 \log_q P^-(q)}{(k-1)(96k+12)}} \rho_1. $$

By noticing that $384k + 48 = 4 \times (96k + 12)$, we conclude that

$$ \frac{S_0(N, q^{\nu}, \xi)}{q^{\nu+1} N} \ll N^{-\eta_1}, $$
where

$$ \eta_1 = \frac{\rho_1 \eta_0 \min(1/4, 3 \log_q (P^-(q)))}{2^k (k-1)(96k+12)}. \quad (78) $$

Now, we bound $\eta_0$

given by Theorem 1.7 from below (we recall that we applied this theorem for $k+1$ instead of $k$). Using the fact that

$$ k+1 = 3(\lfloor \rho_2 \rfloor + 1) + 1 \le 3\rho_2 + 4, $$

we have

$$ K = \left\lfloor \frac{\log(k+1)}{\log(q)} \right\rfloor + 1 \le \frac{\log((3\rho_2 + 4)q)}{\log(q)}. $$

Hence, we get

$$ \begin{aligned} K + (k + 2)b &\le \frac{\log((3\rho_2 + 4)q)}{\log(q)} + b(3\rho_2 + 5) \\ &\le \frac{\log((3\rho_2 + 4)q) + b \log(q)(3\rho_2 + 5)}{\log(q)}. \end{aligned} $$

Therefore, we can bound from below $\eta_0$ by

$$ \begin{aligned} \eta_0 &= \frac{1}{\log(q)(K + (k + 2)b)q^{(k+2)(K+(k+2)b)}} \\ &\ge \frac{1}{\log((3\rho_2 + 4)q) + b \log(q)(3\rho_2 + 5)} \exp(-(3\rho_2 + 5)(\log((3\rho_2 + 4)q) + b \log(q)(3\rho_2 + 5))). \end{aligned} $$

Therefore, injecting all theses inequalities into (78), we have

$$ \begin{aligned} \eta_1 &\ge \frac{\rho_1 \eta_0 \min(1/4, 3 \log_q (P^-(q)))}{8^{1+\rho_2}(288\rho_2 + 300)(3\rho_2 + 2)} \\ &\ge \frac{\rho_1 \min(1/4, 3 \log_q (P^-(q)))}{8^{1+\rho_2}(288\rho_2 + 300)(3\rho_2 + 2)(\log((3\rho_2 + 4)q) + b \log(q)(3\rho_2 + 5))} \\ &\times \exp(-(3\rho_2 + 5)(\log((3\rho_2 + 4)q) + (3\rho_2 + 5)b \log(q))) \\ &= \eta(\rho_1, \rho_2). \end{aligned} $$

This ends the proof of Theorem 1.6.

# 6 Proof of Theorem 1.4

Let $0 < \delta_1 \le \delta_2 < 1$ be two real numbers and $0 < \varepsilon_1, \varepsilon_2 < 1$. Let $D$ be an integer such that $x^{\delta_1} \le D \le x^{\delta_2}$ and $r \in \{0, \dots, m-1\}$. Let $y, z$ be two real numbers such that $0 \le y < z$ and $z - y \le x$. Recall (5),

$$ N_{y,z}(a, b; r, m) = \left| \{ y \le n < z : n \equiv r \pmod m, s_q(n) \equiv a \pmod b \} \right|. $$

We have

$$ N_{y,z}(a, b; r, m) - \frac{z-y}{bm} = \sum_{\substack{y \le n < z, \\ n \equiv r \pmod m}} 1_{b\mathbb{Z}}(s_q(n) - a) - \frac{z-y}{bm}. $$

Writing $n = r + km$ and detecting the congruence with an exponential sum, we get
$$
\begin{align}
N_{y,z}(a, b; r, m) - \frac{z-y}{bm} &= \sum_{\substack{y-r \\ m \le k < \frac{z-r}{m}}} \mathbb{1}_{b\mathbb{Z}}(s_q(r+km) - a) - \frac{z-y}{bm} \\
&= \frac{1}{b} \sum_{\ell=1}^{b-1} \sum_{\substack{y-r \\ m \le k < \frac{z-r}{m}}} e\left(\frac{\ell}{b}(s_q(r+km) - a)\right) + O(1). \tag{79}
\end{align}
$$

With the change of variable

$k' = k - \left\lfloor \frac{y-r}{m} \right\rfloor,$

we get

$$
N_{y,z}(a, b; r, m) - \frac{z-y}{bm} = \frac{1}{b} \sum_{\ell=1}^{b-1} \sum_{0 \le k < \frac{z-y}{m}} e \left( \frac{\ell}{b} \left( s_q \left( r + m \left\lfloor \frac{y-r}{m} \right\rfloor + km \right) - a \right) \right) + O(1).
$$

By taking absolute values and applying the triangle inequality we have

$$
\begin{align*}
|N_{y,z}(a, b; r, m) - \frac{z-y}{bm}| &\le \frac{1}{b} \sum_{\ell=1}^{b-1} \left| \sum_{k \le \frac{z-y}{m}} e\left(\frac{\ell}{b}\left(s_q\left(r+m\left\lfloor \frac{y-r}{m} \right\rfloor + km\right) - a\right)\right) \right| + O(1) \\
&\le \frac{1}{b} \sum_{\ell=1}^{b-1} \max_{u \le x} \max_{r' \ge 0} \left| \sum_{k \le \frac{u}{m}} e\left(\frac{\ell}{b}s_q(r' + km)\right) \right| + O(1).
\end{align*}
$$

Thus, by taking the maximum over $r$, we deduce that

$$
\max_{r \ge 0} \left| N_{y,z}(a, b; r, m) - \frac{z-y}{bm} \right| \le \frac{1}{b} \sum_{\ell=1}^{b-1} \max_{u \le x} \max_{r \ge 0} \left| \sum_{k \le \frac{u}{m}} e \left( \frac{\ell}{b} s_q (r + km) \right) \right| + O(1).
$$

Taking the maximum over $y, z$ and summing over $m \in \{D+1, \dots, qD\}$, we have

$$
\sum_{D<m \le qD} \max_{\substack{y,z \\ 0 \le y \le z \\ z-y \le x}} \max_{r \ge 0} \left| N_{y,z}(a,b;r,m) - \frac{z-y}{bm} \right| \le \frac{1}{b} \sum_{\ell=1}^{b-1} \sum_{D<m \le qD} \max_{\substack{u \le x \\ r \ge 0}} \max_{k \le \frac{u}{m}} \left| \sum_{k \le \frac{u}{m}} e\left(\frac{\ell}{b}s_q(r+km)\right) \right| + O(D). \quad (80)
$$

For $D < m \le qD$, we apply Lemma 2.1, with $x = 0, y = u/m$ and $z = x/D$, and we get

$$
\left| \sum_{k \le \frac{u}{m}} e \left( \frac{\ell}{b} s_q (r + km) \right) \right| \le \int_0^1 \min \left( \frac{u}{m} + 1, \|\xi\|^{-1} \right) \left| \sum_{k \le \frac{x}{D}} e \left( \frac{\ell}{b} s_q (r + km) \right) e(n\xi) \right| d\xi.
$$

We use

$$
\min \left( \frac{u}{m} + 1, \|\xi\|^{-1} \right) \le \min \left( \frac{x}{D} + 1, \|\xi\|^{-1} \right)
$$

to get

$$
\max_{u \le x} \left| \sum_{k \le \frac{u}{m}} e \left( \frac{\ell}{b} s_q (r + km) \right) \right| \le \int_0^1 \min \left( \frac{x}{D} + 1, \|\xi\|^{-1} \right) \left| \sum_{k \le \frac{x}{D}} e \left( \frac{\ell}{b} s_q (r + km) \right) e(n\xi) \right| d\xi.
$$
Injecting this in (80), we deduce that

$$
\sum_{D<m \le qD} \max_{\substack{y,z \\ 0 \le y < z \\ z-y \le x}} \left| N_{y,z}(a, b; r, m) - \frac{z-y}{bm} \right| \\
\le \frac{1}{b} \sum_{1 \le l < b} \int_0^1 \min \left( \frac{x}{D} + 1, \|\xi\|^{-1} \right) \sum_{D<m \le qD} \max_{r \ge 0} \left| \sum_{k \le \frac{x}{D}} e \left( \frac{l}{b} s_q(r+km) \right) e(n\xi) \right| d\xi + O(D).
$$

Using Theorem 1.6, with $\rho_1 = \frac{\delta_1}{1 - \delta_1}$ and $\rho_2 = \frac{\delta_2}{1 - \delta_2}$ there exists $C = C(\eta) > 0$ such that

$$
\sum_{D<m \le qD} \max_{r \ge 0} \left| \sum_{k \le \frac{x}{D}} e \left( \frac{l}{b} s_q(r+km) \right) e(n\xi) \right| \le C D \left( \frac{x}{D} \right)^{1-\eta},
$$

with $\eta = \eta(\rho_1, \rho_2)$ defined in Theorem 1.6. Hence, it follows that

$$
\sum_{D<m \le qD} \max_{\substack{y,z \\ 0 \le y < z \\ z-y \le x}} \max_{r \ge 0} \left| N_{y,z}(a,b;r,m) - \frac{z-y}{bm} \right| \le C D \left(\frac{x}{D}\right)^{1-\eta} \int_0^1 \min \left(\frac{x}{D} + 1, \|\xi\|^{-1}\right) d\xi + O(D).
$$

Since $D \le x^{\delta_2} < x$, we have $x/D > 1$ and using

$$
\int_0^1 \min (A, \|\xi\|^{-1}) d\xi \ll \log(A),
$$

there exists $C_1 = C_1(\rho_1, \rho_2) > 0$ such that

$$
\sum_{D<m \le qD} \max_{\substack{y,z \\ 0 \le y < z \\ z-y \le x}} \max_{r \ge 0} \left| N_{y,z}(a,b;r,m) - \frac{z-y}{bm} \right| \le C_1 D \left(\frac{x}{D}\right)^{1-\eta} \log \left(\frac{x}{D}\right) + O(D). \quad (81)
$$

Moreover, by hypothesis, we have

$x^{\delta_1} \le D \le x^{\delta_2}.$

Injecting this in (81), we have for any $0 < \varepsilon_2 < 1$,

$$
\begin{align*}
\sum_{D<m \le qD} \max_{\substack{y,z \\ 0 \le y < z \\ z-y \le x}} \max_{r \ge 0} \left| N_{y,z}(a,b;r,m) - \frac{z-y}{bm} \right| &= C_1 D^{\eta} x^{1-\eta} (\log(x) - \log(D)) + O(D) \\
&\le C_1 x^{\delta_2 \eta} x^{1-\eta} (1 - \delta_1) \log(x) + O(D) \\
&\le C_2 x^{1-(1-\delta_2)\eta/(1+\varepsilon_2)} + O(D) \\
&\le C_3 x^{1-(1-\delta_2)\eta/(1+\varepsilon_2)},
\end{align*}
$$

since $D \le x^{\delta_2}$ and $1 - (1 - \delta_2)\eta/(1 + \varepsilon_2) \ge 1 - (1 - \delta_2) = \delta_2$, because $\delta_2, \eta/(1 + \varepsilon_2) < 1$.

In order to end the proof of Theorem 1.4, we are going to bound from below $(1 - \delta_2)\eta/(1 + \varepsilon_2)$. We first use
the explicit value of $\eta = \eta(\rho_1, \rho_2)$,

$$
\eta = \frac{\rho_1 \min \left( \frac{1}{4}, 3 \log_q (P^{-}(q)) \right)}{8^{1+\rho_2} (288\rho_2 + 300)(3\rho_2 + 2) \left( \log\left(\frac{3\rho_2 + 4}{q}\right) + \frac{b \log(q)}{3\rho_2 + 5} \right)} \times \exp\left( -(3\rho_2 + 5) \left( \log\left(\frac{3\rho_2 + 4}{q}\right) + \frac{b \log(q)}{3\rho_2 + 5} \right) \right).
$$
Using the definition of $\rho_1 = \frac{\delta_1}{1 - \delta_1}$ and $\rho_2 = \frac{\delta_2}{1 - \delta_2}$, we have

$$ \frac{(1 - \delta_2)\eta}{1 + \varepsilon_2} = \frac{\delta_1(1 - \delta_2)^2 \min(1/4, 3 \log_q(P^-(q)))}{(1 - \delta_1)8^{(1-\delta_2)^{-1}}(300 - 12\delta_2)(2 + \delta_2)(\log((4 - \delta_2)q/(1 - \delta_2)) + b \log(q)(5 - 2\delta_2)/(1 - \delta_2))(1 + \varepsilon_2)} \\ \times \exp\left(-\frac{5 - 2\delta_2}{1 - \delta_2}\left(\log(q(4 - \delta_2)(1 - \delta_2)^{-1}) + \frac{5 - 2\delta_2}{1 - \delta_2}b \log(q)\right)\right). $$

Since $1 - \delta_1 \le 1$, $300 - 12\delta_2 \le 300$, $2 + \delta_2 \le 3$, $4 - \delta_2 \le 4$, $5 - 2\delta_2 \le 5$ and $1 + \varepsilon_2 \le 2$, in order to simplify the expression, we remove the dependence of the numerators of $\delta_2$ of the appearing fractions at the cost of a slightly less precise bound:

$$ \frac{(1 - \delta_2)\eta}{1 + \varepsilon_2} \ge \frac{\delta_1(1 - \delta_2)^2 \min(1/4, 3 \log_q(P^-(q)))}{1800 \times 8^{(1-\delta_2)^{-1}}(\log(4q/(1 - \delta_2)) + 5b \log(q)/(1 - \delta_2))} \\ \times \exp\left(-\frac{5}{1 - \delta_2}\left(\log(4q(1 - \delta_2)^{-1}) + \frac{5b \log(q)}{1 - \delta_2}\right)\right) \\ =: \eta(\delta_1, \delta_2), $$

as stated. This ends the proof of Theorem 1.4.

# 7 Proof of Theorem 1.2

Let $0 < \varepsilon < 1$. We set $\delta_2 = 1 - \varepsilon$ and $\delta_1 = \frac{\varepsilon}{2}$ (we note that the condition $\delta_1 \le \delta_2$ implies $\varepsilon \le 2/3$.) For $m \in [1, x^{1-\varepsilon}] \cap \mathbb{N}$, we set

$$ E(m) = \max_{\substack{y,z \\ 0 \le y < z \\ z - y \le x}} \max_{r \ge 0} \left| N_{y,z}(a, b; r, m) - \frac{z - y}{bm} \right|. $$

We split

$$ \sum_{1 \le m \le x^{1-\varepsilon}} E(m) = \sum_{1 \le m < x^{\delta_1}} E(m) + \sum_{x^{\delta_1} \le m \le x^{\delta_2}} E(m). $$

According to Theorem A we have for $y, z$ such that $0 \le y < z$ and $z - y \le x$,

$$ N_{y,z}(a, b; r, m) = \left| \{ y \le n < z : n \equiv r \pmod m, s_q(n) \equiv a \pmod b \} \right| \\ = \frac{z - y}{bm} + O((z - y)^\lambda). $$

Since $z - y \le x$, we have

$$ N_{y,z}(a, b; r, m) - \frac{z - y}{bm} = O(x^{\lambda}), $$

where the implied constant depends on $b$ and $q$. We deduce that

$$ \sum_{1 \le m < x^{\delta_1}} E(m) = O(x^{\delta_1 + \lambda}). $$

Concerning the second sum, we split the interval into $q$-adic intervals

$$ [x^{\delta_1}, x^{\delta_2}] \subset \bigcup_{\alpha=A_1}^{A_2} [q^{\alpha}, q^{\alpha+1}], $$
where

$$A_1 = \left\lfloor \frac{\delta_1 \log(x)}{\log(q)} \right\rfloor, \quad A_2 = \left\lfloor \frac{\delta_2 \log(x)}{\log(q)} \right\rfloor - 1.$$

Thus,

$$\sum_{x^{\delta_1} \le m \le x^{\delta_2}} E(m) \le \sum_{\alpha=A_1}^{A_2} \sum_{q^{\alpha} \le m \le q^{\alpha+1}} E(m).$$

Moreover, for $\alpha \in \{A_1, \dots, A_2\}$, and for large $x$, we have

$$x^{\delta_1/2} \le q^{\alpha} \le x^{\delta_2}.$$

Applying Theorem 1.4 for $D = q^{\alpha}$, with $\delta_1/2$ and $\delta_2$ in place of $\delta_1$ and $\delta_2$,

$$\sum_{1 \le m \le x^{1-\varepsilon}} E(m) = \sum_{1 \le m < x^{\delta_1}} E(m) + \sum_{x^{\delta_1} \le m \le x^{\delta_2}} E(m) \le O(x^{\delta_1+\lambda}) + Cx^{1-\frac{\eta}{1+\varepsilon_3}}, \quad (82)$$

for all $0 < \varepsilon_3 < 1$ and for $\eta = \eta(\delta_1, \delta_2)$ defined in Theorem 1.4. Recalling $\delta_2 = 1 - \varepsilon$ and $\delta_1 = \varepsilon/2$, we get with (7),

$$\begin{aligned} \frac{\eta}{1 + \varepsilon_3} &:= \frac{(\delta_1/2)(1 - \delta_2)^2 \min(1/4, 3 \log_q(P^-(q)))}{1800 \times 8^{(1-\delta_2)^{-1}} (\log(4q/(1-\delta_2)) + 5b \log(q)/(1-\delta_2)) (1+\varepsilon_3)} \\ & \times \exp\left(-\frac{5}{1-\delta_2}\left(\log(4q(1-\delta_2)^{-1}) + \frac{5b \log(q)}{1-\delta_2}\right)\right) \\ &= \frac{\varepsilon^3 \min(1/4, 3 \log_q(P^-(q)))}{3600 \times 8^{1/\varepsilon} (\log(4q/\varepsilon) + 5b \log(q)/\varepsilon) (1+\varepsilon_3)} \\ & \times \exp\left(-\frac{5}{\varepsilon}\left(\log(4q/\varepsilon) + \frac{5b \log(q)}{\varepsilon}\right)\right). \end{aligned} \quad (83)$$

In particular, $\frac{\eta}{1 + \varepsilon_3} \le \varepsilon$. Indeed, since $0 < \varepsilon < 1$, we have $\log(4q/\varepsilon) > 0$ and $5b \log(q)/\varepsilon > 5b \log(q) > 1$.

Thus,

$$3600 \times 8^{1/\varepsilon} (\log(4q/\varepsilon) + 5b \log(q)/\varepsilon) > 1$$

and $\varepsilon^3 < \varepsilon$. Therefore,

$$\frac{\eta}{1 + \varepsilon_3} \le \varepsilon.$$

Now, we want to compare the two exponents appearing in (82). We write

$$\delta_1 + \lambda - \left(1 - \frac{\eta}{1 + \varepsilon_3}\right) \le \frac{\varepsilon}{2} + \lambda - 1 + \varepsilon.$$

For $\varepsilon < \frac{2}{3}(1 - \lambda)$, the last quantity is negative. Thus, we deduce that there exists $C' > 0$ such that

$$\sum_{1 \le m \le x^{1-\varepsilon}} E(m) \le C' x^{1-\frac{\eta}{1+\varepsilon_3}}.$$

In order to have the $\eta$ announced in Theorem 1.2, we use the equation (83) and we use the fact that $1 + \varepsilon_3 \le 2$.

Finally,

$$\frac{\eta}{1 + \varepsilon_3} \ge \frac{\varepsilon^3 \min(1/4, 3 \log_q(P^-(q)))}{7200 \times 8^{1/\varepsilon} (\log(4q/\varepsilon) + 5b \log(q)/\varepsilon)} \\ \times \exp\left(-\frac{5}{\varepsilon}\left(\log(4q/\varepsilon) + \frac{5b \log(q)}{\varepsilon}\right)\right)$$
and we can therefore take

$$ \eta(\varepsilon) = \frac{\varepsilon^3 \min(1/4, 3 \log_q(P^-(q)))}{7200 \times 8^{1/\varepsilon} (\log(4q/\varepsilon) + 5b \log(q)/\varepsilon)} \times \exp\left(-\frac{5}{\varepsilon}\left(\log(4q/\varepsilon) + \frac{5b \log(q)}{\varepsilon}\right)\right) $$

as stated. This ends the proof of Theorem 1.2.

**Remark 7.1.** Instead of applying Theorem A for the first sum of (82) we could also use a result on average in the spirit of Theorem B. However, it requires a generalization of Theorem B to any base $q$. This would give us another condition for $\varepsilon$ but the explicit value for $\eta$ would not change.
# Annexes

## A Choosing the parameters

First, let us give an inventory of all the parameters used along this paper with their roles and restrictions.

### Parameters introduced during the iterations of the van der Corput inequality

* $k \ge 3$ the number of iterations of the van der Corput inequality (Subsection 5.1.2),

* $H_0 \le q^{k\mu}$ appearing in the first iteration of the van der Corput inequality (Lemma 5.1). The bound appears in (70),

* $\lambda > \nu + 1$ used to apply the carry propagation lemma (42),

* $H_1 = \dots = H_{k-1} = q^\rho$ appearing in Subsection 5.1.2 (see (65)); we will discuss the size of $E_i$ and (54) later (see (94)).

### Parameters used to define the shifts $K_1, \dots, K_{k-1}$

* $\mu > 0$ such that $\nu + 1 \ge k\mu$ (see (72)),

* $\rho + 1 < \sigma < \mu$ (see (61) and (44)).

### Parameters introduced during the various digit shifts

* $\rho = \lambda - k\mu$ (see (52)),

* $T \ge 2$ defined in Lemma 5.6,

* $0 < \gamma \le \rho$ used to define the set $B$ (see (66)).

In order to define $\mu$, we recall that, by hypothesis (see beginning of Section 5), we have

$$N^{\rho_1} < q^{\nu} \le qN^{\rho_2}. \qquad (84)$$

We set $k = 3(\lfloor \rho_2 \rfloor + 1) \ge 3$ and define

$$\mu = \lfloor \frac{\nu - 1}{k + 1/8} \rfloor,$$

and observe that $\mu \le \nu/k$ (thus, this choice respects (72)). Furthermore, we set

$$\sigma = \lfloor \frac{\mu}{4} \rfloor, \quad \tilde{\rho} = \nu - k\mu. \qquad (85)$$

With the definition of $\tilde{\rho}$, we set

$$\gamma = \lfloor \frac{\eta_0 \tilde{\rho}}{12(k-1)} \rfloor. \qquad (86)$$

Then, with the definition of $\gamma$, we define

$$T = q^{\gamma}, \quad H_0 = \lfloor q^{\gamma/4} \rfloor.$$

Moreover, we set

$$\lambda = \nu + \lfloor \frac{\gamma}{2} \rfloor. \qquad (87)$$

Condition (42) is satisfied, since $\gamma \to +\infty$. We recall again that

$$\rho = \lambda - k\mu. \qquad (88)$$

We first give some asymptotic equivalents of our parameters which will be of importance to prove that our choice of parameters is admissible. Since $\nu \to +\infty$, these equivalents will be useful to determine the rate of convergence for every term in (73). This will be sufficient to conclude.
**Lemma A.1.** For $\mu \to +\infty$, we have the following equivalents:

$$ (1) \qquad \tilde{\rho} \sim \frac{\mu}{8}, \qquad (89) $$

$$ (2) \qquad \gamma \sim \frac{\eta_0 \mu}{96(k-1)}, \qquad (90) $$

$$ (3) \qquad \rho \sim \frac{\mu}{8} + \frac{\eta_0 \mu}{192(k-1)}. \qquad (91) $$

*Proof.* For (89), since $k$ is constant, we have

$$ \tilde{\rho} = \nu - k \left\lfloor \frac{\nu - 1}{k + 1/8} \right\rfloor \sim \nu - k \frac{\nu - 1}{k + 1/8} \sim \frac{1}{8} \left( \frac{\nu - 1 + 1 + 8k}{k + 1/8} \right) \sim \frac{\mu}{8}. $$

For (90), we use the definition of $\gamma$ and (89). We get

$$ \gamma \sim \frac{\eta_0 \tilde{\rho}}{12(k-1)} \sim \frac{\eta_0 \mu}{96(k-1)}. $$

As for (91), we use (89), (90) and the definition (87) of $\lambda$, to get

$$ \rho = \lambda - k\mu = \tilde{\rho} + \left\lfloor \frac{\gamma}{2} \right\rfloor \sim \frac{\mu}{8} + \frac{\eta_0 \mu}{192(k-1)}. $$

□

Since $k \ge 3$ and $0 < \eta_0 < 1$ we get the following explicit inequalities.

**Corollary A.2.** For sufficiently large $\mu$,

$$ \gamma \le \mu/192 \quad \text{and} \quad \rho \le \mu/8 + \mu/384. $$

We first note that condition (67) is satisfied. Indeed, by (85) and (86) we have

$$ 3\gamma \le \frac{\tilde{\rho}}{8} < \frac{\nu}{8} < \nu + 1. $$

Moreover, the condition (70) is satisfied for $H_0$ for sufficiently large $\mu$. In order to proceed with the proof of Theorem 1.6, we need bounds for $N$ in terms of $q^\mu$.

**Lemma A.3.** We have the following bounds for $N$ and $q^\mu$:

$$ (1) \qquad N \ge q^{3\mu}, \qquad (92) $$

$$ (2) \qquad q^{\mu} \gg N^{\frac{\rho_1}{k+1/8}}, \qquad (93) $$

where the implied constant depends only on $k$ and $q$.
Proof. Using (84) we get

$$N \geq q^{\frac{\nu-1}{\rho_2}} \geq q^{\frac{\nu-1}{\lfloor \rho_2 \rfloor+1}} = q^{3\frac{\nu-1}{k}} \geq q^{3\mu},$$

which is (92). Also, again using (84), we get $N^{\rho_1} < q^{\nu}$ and

$$\frac{1}{q^{(k+1/8)-1}} N^{\frac{\rho_1}{k+1/8}} < q^{\frac{\nu-1}{k+1/8}} < q^{\lfloor \frac{\nu-1}{k+1/8} \rfloor+1} = q^{\mu+1}.$$

We conclude that

$$q^{\mu} > C N^{\frac{\rho_1}{k+1/8}},$$

with $C = 1/(q^{(k+1/8)^{-1}}+1)$.

□

After this preliminary work, we now focus on bounding each term in (73).

$$\bullet \text{ Bounding } \frac{1}{H_0}.$$

To begin with, we note that

$$H_0 = \lfloor q^{\frac{\gamma}{4}} \rfloor \leq q^{\mu/768} \leq q^{3\mu} \leq N,$$

a condition that we imposed on $H_0$ in Lemma 5.1. Now, we use (90) and (93),

$$\frac{1}{H_0} = \frac{1}{\lfloor q^{\gamma/4} \rfloor} \sim q^{-\gamma/4} \ll q^{-\frac{\eta_0 \mu}{384(k-1)}} \ll N^{\frac{-\rho_1 \eta_0}{(384k+48)(k-1)}}.$$

$$\bullet \text{ Bounding } \frac{H_0}{q^{\lambda-\nu}}.$$

$$\frac{H_0}{q^{\lambda-\nu}} = \frac{\lfloor q^{\gamma/4} \rfloor}{q^{\lfloor \gamma/2 \rfloor}} \ll q^{-\gamma/4}.$$

We note that $\frac{1}{H_0}$ and $\frac{H_0}{q^{\lambda-\nu}}$ have the same rate of convergence.

$$\bullet \text{ Bounding } \frac{H_0}{N}.$$

We notice that $\frac{H_0}{N} < \frac{1}{H_0}$. Indeed, by (92) we have

$$\frac{H_0}{N} \leq \frac{q^{\gamma/4}}{q^{3\mu}}.$$

Using the fact that $\mu \geq 192\gamma$ (see Corollary (A.2)), we have

$$\frac{H_0}{N} \leq q^{-\frac{2303}{4}\gamma}.$$

The above estimates show that $E_0$ defined in Lemma 5.4 is smaller than 1 for sufficiently large $\nu$.

$$\bullet \text{ Bounding } \frac{q^{\rho+2\mu+3\sigma}}{N}.$$

Using (92) we have

$$\frac{q^{\rho+2\mu+3\sigma}}{N} \leq q^{\rho-\mu+3\sigma}.$$
Furthermore, by Corollary (A.2), we get, for sufficiently large $\mu$,

$$ \rho - \mu + 3\sigma \leq \frac{-335\mu}{384} + 3\sigma. $$

By the fact that $\mu \geq 4\sigma$ (see (85)), we find

$$ \rho - \mu + 3\sigma \leq \frac{-47}{384}\mu. $$

The inequality (93) then gives

$$ \frac{q^{\rho+2\mu+3\sigma}}{N} \leq q^{-\frac{47}{384}\mu} \ll N^{-\frac{47\rho_1}{384k+48}}. \quad (94) $$

This estimate also assures that $E_1, \dots, E_{k-1}$ defined in Lemma 5.4 satisfy the condition (54) for sufficiently large $\nu$.

* Bounding $\frac{1}{T}$.

As before, we use (90) and (93), and get

$$ \frac{1}{T} = \frac{1}{q^{\gamma}} \ll q^{-\frac{\eta_0}{96(k-1)}\mu} \ll N^{-\frac{\eta_0 \rho_1}{96(k-1)(k+1/8)}} = N^{-\frac{\eta_0 \rho_1}{96(k+12)(k-1)}}. $$

* Bounding $q^{-3\gamma \log_q P^{-}(q)}$.

Once again, we use (90) and (93) and get

$$ q^{-3\gamma \log_q P^{-}(q)} \ll q^{-\frac{3\eta_0 \log_q P^{-}(q)}{96(k-1)}} \mu \ll N^{-\frac{3\eta_0 \log_q P^{-}(q)}{(96k+12)(k-1)} \rho_1}. $$

* Bounding $q^{3\gamma(k-1)-\eta_0/2\rho}$.

We first bound the exponent. Since $\lambda > \nu$, we note that $\tilde{\rho} \leq \rho$ (see (85) and (88)). We use the definition of $\gamma$ and get

$$ 3\gamma(k-1) - \eta_0\rho/2 \leq 3(k-1)\frac{\eta_0\rho}{12(k-1)} - \eta_0\rho/2 = -\frac{\eta_0\rho}{4}. $$

We use (91) together with (93) to get

$$ q^{3\gamma(k-1)-\eta_0\rho/2} \leq q^{-\frac{\eta_0\rho}{4}} \ll N^{-\frac{\eta_0}{4}(\frac{1}{8} + \frac{\eta_0}{192(k-1)})\frac{\rho_1}{k+1/8}} \ll N^{-\frac{\eta_0\rho_1}{32(k+1/8)}}. $$

* Bounding $Tq^{\lambda-\nu-1+\rho}(\log^+ N)^2(\frac{1}{N} + \frac{1}{q^{2\mu}})$.

Since by (92) we have $N \geq q^{2\mu}$, we just need to estimate the term

$$ Tq^{\lambda-\nu-1+\rho-2\mu}(\log^+ N)^2. $$

Since $T = q^{\gamma}$ we get

$$ Tq^{\lambda-\nu-1+\rho-2\mu}(\log^+ N)^2 \leq q^{\lambda-\nu+\rho+\gamma-2\mu}(\log^+ N)^2. $$

Using Corollary (A.2) we have, for sufficiently large $\mu$,

$$ \begin{aligned} \lambda - \nu + \rho + \gamma - 2\mu &= \left\lfloor \frac{\gamma}{2} \right\rfloor + \rho + \gamma - 2\mu \\ &\leq \frac{\mu}{384} + \frac{\mu}{8} + \frac{\mu}{384} + \frac{\mu}{192} - 2\mu \\ &\leq \frac{-179}{96}\mu. \end{aligned} $$
Thus,

$$Tq^{\lambda-\nu-1+\rho-2\mu}(\log^+ N)^2 \le \frac{(\log N)^2}{q^{(179/96)\mu}}.$$

By the inequality (93) and since $\log(N) \le N^{1/4}$, we get

$$ \begin{aligned} Tq^{\lambda-\nu-1+\rho-2\mu}(\log^+ N)^2 &\ll (\log N)^2 N^{-\frac{179\rho_1}{96k+12}} \\ &\ll N^{-\frac{179\rho_1}{192k+24}}. \end{aligned} $$

$$ \bullet \text{ Bounding } \frac{1}{q^{\sigma-\rho}}. $$

We use $\sigma = \lfloor \frac{\mu}{4} \rfloor$ and Corollary (A.2). This yields

$$ \frac{1}{q^{\sigma-\rho}} \le \frac{1}{q^{\lfloor \mu/4 \rfloor - \mu/8 - \mu/384}} \ll q^{-(47/384)\mu} \ll N^{-\frac{47\rho_1}{384k+48}}, $$

which is the same bound as in (94).

Finally, we collect all these bounds and reconsider (73). We have

$$ \left| \frac{S_0(N, q^{\nu}, \xi)}{q^{\nu+1}N} \right|^{2k} \ll N^{-\frac{\rho_1 \eta_0}{(384k+48)(k-1)}} + N^{-\frac{47\rho_1}{384k+48}} + N^{-\frac{\rho_1 \eta_0}{(96k+12)(k-1)}} + N^{-\frac{3\eta_0 \log_q P^{-}(q)}{(96k+12)(k-1)}} \rho_1 + N^{-\frac{\rho_1 \eta_0}{32k+4}} + N^{-\frac{179\rho_1}{192k+24}}. $$

By comparing the summands, we get

$$ \left| \frac{S_0(N, q^{\nu}, \xi)}{q^{\nu+1}N} \right|^{2k} \ll N^{-\frac{\rho_1 \eta_0}{(384k+48)(k-1)}} + N^{-\frac{3\eta_0 \log_q P^{-}(q)}{(k-1)(96k+12)}} \rho_1. $$

# B Farey sequences

The following results are standard and can be found in [12].

**Definition B.1 (Farey sequence).** Let $n \ge 1$ be an integer. We call the Farey sequence of order $n$, denoted by $F_n$, the sequence formed by irreducible fractions $0 \le \frac{a}{b} \le 1$ with $b \le n$. Two fractions are said to be neighbours in the sequence $F_n$ if they are consecutive in $F_n$.

**Remark B.2.** By translation, we define the Farey sequence of order $n$ over $\mathbb{R}$, which we will continue to denote as $F_n$ hereafter.

**Lemma B.3 (Midpoint lemma).** Let $\frac{a}{b} < \frac{c}{d}$ be two irreducible fractions. Then

$$ \frac{a}{b} < \frac{a+c}{b+d} < \frac{c}{d}. $$

The fraction $\frac{a+c}{b+d}$ is called the midpoint of the fractions $\frac{a}{b}$ and $\frac{c}{d}$.

**Proposition B.4 (Farey's criterion).** Let $\frac{a}{b} < \frac{c}{d}$ be two neighbouring fractions in $F_n$. Then,

$$ \Delta = bc - ad = 1 \quad \text{and} \quad b+d > n. $$

Additionally,

$$ \frac{a+c}{b+d} - \frac{a}{b} < \frac{1}{bn}. $$

and

$$ \frac{c}{d} - \frac{a+c}{b+d} < \frac{1}{dn}. $$
**Definition B.5.** Let $\alpha \in \mathbb{R}$ and let $\frac{a}{b}, \frac{c}{d} \in \mathcal{F}_n$ be two neighbouring fractions such that

$$ \frac{a}{b} \le \alpha < \frac{c}{d}. $$

If $\alpha < \frac{a+c}{b+d}$, then we define

$$ \frac{P_n(\alpha)}{Q_n(\alpha)} = \frac{a}{b}. $$

Otherwise, we define

$$ \frac{P_n(\alpha)}{Q_n(\alpha)} = \frac{c}{d}. $$

**Proposition B.6 (Farey approximation).** For $\alpha \in \mathbb{R}$ and for $n \in \mathbb{N}$, we have

$$ |Q_n(\alpha)\alpha - P_n(\alpha)| < \frac{1}{n}. $$

## C Graph of the function $\varepsilon \mapsto \log(\eta(\varepsilon))$

A straightforward Python program allows to plot the graph of the quantity defined in (6), seen as a function of $\varepsilon$.

<figure><img src="image_7.png" /><figcaption>FIGURE 1. The graph of the function $\varepsilon \mapsto \log \eta(\varepsilon)$ in $]0.01, 0.5[$ for $q = b = 2$.</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>FIGURE 2. The graph of the function $\varepsilon \mapsto \log \eta(\varepsilon)$ in $]0.025, 0.5[$ for $q = 10$ and $b = 7$.</figcaption></figure>

We remark that $\eta(\varepsilon)$ becomes extremely small as $\varepsilon$ approaches 0. Furthermore, we observe that for larger parameters $q$ and $b$, it becomes very difficult to calculate $\eta(\varepsilon)$ for small values of $\varepsilon$. Indeed, the domain taken for the simulation of the second graph is more restricted than that of the first because of the increased complexity of the computation. The following table gives (for $q = b = 2$) some values for the exponents $\eta(\varepsilon)$ defined by (6), and $\xi'_{2,\varepsilon}$ defined by (2). We notice that the exponent provided in [14] is much larger

<table><caption>FIGURE 3. Few values of $\log \eta(\xi)$ and $\log \xi'_{2,\varepsilon}$ (case $b = q = 2$).</caption><thead><tr><td>ε</td><td>log η(ε)</td><td>log ξ'_{2,ε}</td></tr></thead><tbody><tr><td>0.3</td><td>-270.77</td><td>-5.85</td></tr><tr><td>0.2</td><td>-553.97</td><td>-6.26</td></tr><tr><td>0.1</td><td>-1993.60</td><td>-6.95</td></tr><tr><td>0.05</td><td>-7504.14</td><td>-7.65</td></tr><tr><td>0.01</td><td>-176 866.99</td><td>-9.25</td></tr><tr><td>0.005</td><td>-700 973.54</td><td>-9.95</td></tr><tr><td>0.001</td><td>-17 375 734.08</td><td>-11.56</td></tr></tbody></table>

than ours. One of reasons is the fact that we handle the max over the residue classes, while [14] deals with individual bounds.

## Acknowledgements

The author would like to greatly thank my thesis supervisors Cécile Dartyge and Thomas Stoll for their teaching and advice, which have greatly helped me throughout my work. Moreover, he is very grateful to the referee for the careful reading of the paper and for the comments and suggestions. The author is supported by the French projects ANR-18-CE40-0018 (EST) and ANR-20-CE91-0006 (ArithRand).
References

[1] J.-P. Allouche and J. O. Shallit. The ubiquitous Prouhet-Thue-Morse sequence. In: *Sequences and their Applications (Singapore, 1998)*, Springer Ser. Discrete Math. Theor. Comput. Sci. (1999), 1-16.

[2] R. Bellman and H. N. Shapiro. A problem in additive number theory, *Ann. of Math. 49* (1948), 333-340.

[3] J. Byszewski, J. Konieczny and C. Müllner, Gowers norms for automatic sequences. *Discrete Anal. 62* (2023), no.4.

[4] J. Coquet, Corrélation de suites arithmétiques. Séminaire Delange-Pisot-Poitou. Théorie des nombres **20** (1978-1979), no.1, Exposé no.1.

[5] J.-M. Deshouillers, M. Drmota, C. Müllner, A. Shubin, L. Spiegelhofer. Synchronizing automatic sequences along Piatetski-Shapiro sequences, preprint. arXiv:2211.01422.

[6] M. Drmota, C. Mauduit and J. Rivat, Normality along squares. *J. Eur. Math. Soc.* **21** (2019), no.2, 507-548.

[7] M. Drmota and J. Rivat, The Sum-of-Digits Function of Squares. *J. Lond. Math. Soc.* **72** (2005), no.2, 273-292.

[8] E. Fouvry and C. Mauduit, Méthodes de crible et fonctions sommes des chiffres. *Acta Arith.* **77** (1996), no.4, 339-351.

[9] E. Fouvry and C. Mauduit, Sums of digits and almost primes, *Math. Ann.* **305** (1996), no. 3, 571-599.

[10] A. Gelfond, Sur les nombres qui ont des propriétés additives et multiplicatives données. *Acta Arith.*, **13** (1968), no.3, 259-265.

[11] S. W. Graham and G. Kolesnik, Van der Corput's Method of Exponential Sums. *London Mathematical Society Lecture Note Series*. Cambridge University Press, 1991.

[12] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. *Oxford, fourth edition* (1975).

[13] J. Konieczny, Gowers norms for the Thue-Morse and Rudin-Shapiro sequences. *Ann. Inst. Fourier (Grenoble)*, **69** (2019), no.4, 1897-1913.

[14] B. Martin, C. Mauduit, and J. Rivat. Théorème des nombres premiers pour les fonctions digitales. *Acta Arith.* **165** (2014), no.1, 11-45.

[15] C. Mauduit and J. Rivat, The sum of digits of squares. *Acta Math.* **203** (2009), no.1, 107-148.

[16] C. Mauduit and J. Rivat, Répartition des fonctions $q$-multiplicatives dans la suite $([n^c])_{n \in \mathbb{N}}$, $c > 1$. *Acta Arith.* **71** (1995), no.2, 171-179.

[17] C. Mauduit and J. Rivat, On a problem of Gelfond: the sum of digits of prime numbers. *Ann. Math. (2)*, **171** (2010), no.3, 1591-1646.

[18] J. Morgenbesser, J. Shallit, T. Stoll, Thue-Morse at multiples of an integer. *J. Number Theory* **131** (2011), no.8, 1498-1515.

[19] C. Müllner and L. Spiegelhofer, Normality of the Thue-Morse sequence along Piatetski-Shapiro sequences. II. *Israel J. Math.* **220** (2017), no.2, 691-738.

[20] M. Queffélec. Mesures spectrales associées à certaines suites arithmétiques. *Bull. Soc. Math. France* **107** (1979), 385-421.
[21] L. Spiegelhofer, The level of distribution of the Thue–Morse sequence. *Compositio Math.* **156** (2020), no.12, 2560–2587.

[22] L. Spiegelhofer, Thue–Morse along the sequence of cubes sequence. *preprint*, arXiv:2308.09498.

UNIVERSITÉ DE LORRAINE, CNRS, INSTITUT ELIE CARTAN DE LORRAINE, UMR 7502, VANDOEUVRE-LÈS-NANCY, F-54506, FRANCE

Email address: nathan.toumi@univ-lorraine.fr