Proof. Since $n<g^{k}$ , we have

$$\begin{align*}g^{k}m+n = \sum_{i\ge 0}\varepsilon_{i}(m)g^{i+k} + \sum_{0\le i<k}\varepsilon_{i}(n)g^{i} = \sum_{i\ge k}\varepsilon_{i-k}(m)g^{i} + \sum_{0\le i<k}\varepsilon_{i}(n)g^{i}, \end{align*}$$

and so

$$\begin{align*}\varepsilon_{i}(g^{k}m+n) = \left\{ \begin{array}{>{\displaystyle}c@{\quad}l} \varepsilon_{i}(n)&\text{for } 0\le i<k,\\[2mm] \varepsilon_{i-k}(m)&\text{for } i\ge k. \end{array} \right. \end{align*}$$

Using $0\le k\le \lambda $ , we thus have

$$ \begin{align*} f_{\lambda}^{[\mkern2mu j]}(g^{k}m+n) &= \sum_{k\le i<\lambda} \alpha_{i}^{[\mkern2mu j]}(\varepsilon_{i-k}(m)) + \sum_{0\le i<k} \alpha_{i}^{[\mkern2mu j]}(\varepsilon_{i}(n)) \\ &= \sum_{0\le i<\lambda-k} \alpha_{i+k}^{[\mkern2mu j]}(\varepsilon_{i}(m)) + f_{k}^{[\mkern2mu j]}(n) \\ &= \sum_{0\le i<\lambda-k} \alpha_{i}^{[\mkern2mu j+k]}(\varepsilon_{i}(m)) + f_{k}^{[\mkern2mu j]}(n) = f_{\lambda-k}^{[\mkern2mu j+k]}(m) + f_{k}^{[\mkern2mu j]}(n). \end{align*} $$

This completes the proof.

Proof. Let $N:= \lceil x\rceil \ge 1$ . We then have

(3.1) $$ \begin{align} \sum_{0\le n<x} e(f_{L}^{[\mkern2mu j]}(n)-\beta n) = \sum_{0\le n<N} e(f_{L}^{[\mkern2mu j]}(n)-\beta n). \end{align} $$

Let $k:= [\frac {\log N}{\log g}]$ so that $g^{k}\le N<g^{k+1}$ . Since $x\le g^{L}$ , we have $k\le L$ . We then write

(3.2) $$ \begin{align} N=g^{k}y+z \quad\text{with}\quad y\in[1,g)\cap\mathbb{Z} \ \text{and}\ z\in[0,g^{k})\cap\mathbb{Z}. \end{align} $$

We prove the assertion by induction on $k\in \{0,\ldots ,L\}$ .

Initial case $\textsf{k=0}$ . In this case, we have $N\le g-1$ , and so the trivial bound gives

$$\begin{align*}\bigg\lvert \sum_{0\le n<x} e(f_{L}^{[\mkern2mu j]}(n)-\beta n) \bigg\rvert = \bigg\lvert \sum_{0\le n<N} e(f_{L}^{[\mkern2mu j]}(n)-\beta n) \bigg\rvert \le N \le g-1. \end{align*}$$

Hence, the assertion holds.

Induction step. Assume that the assertion holds for the case $0\le k<K$ with $K\in \{1,\ldots ,L\}$ . We shall prove the case $k=K$ . By (3.2), we have

(3.3) $$ \begin{align} \begin{aligned} \sum_{0\le n<N} e(f_{L}^{[\mkern2mu j]}(n)-\beta n) &= \sum_{0\le m<y} \sum_{g^{K}m\le n<g^{K}(m+1)} e(f_{L}^{[\mkern2mu j]}(n)-\beta n)\\ &\quad + \sum_{g^{K}y\le n<N} e(f_{L}^{[\mkern2mu j]}(n)-\beta n)\\ &= \sum_{0\le m<y} \sum_{0\le n<g^{K}} e(f_{L}^{[\mkern2mu j]}(g^{K}m+n)-\beta(g^{K}m+n))\\ &\quad + \sum_{0\le n<z} e(f_{L}^{[\mkern2mu j]}(g^{K}y+n)-\beta(g^{K}y+n))\\ &=: {\sum}_{1}+{\sum}_{2},\quad\text{say}. \end{aligned} \end{align} $$

For the sum ${\sum }_{1}$ , by using Lemma 3.1 and $y\in [1,g)\cap \mathbb {Z}$ , we have

(3.4) $$ \begin{align} \Big\lvert {\sum}_{1} \Big\rvert &= \bigg\lvert \sum_{0\le m<y} e(f_{L-K}^{[\mkern2mu j+K]}(m)-\beta g^{K}m) \sum_{0\le n<g^{K}} e(f_{K}^{[\mkern2mu j]}(n)-\beta n) \bigg\rvert \\ &\le (g-1) \bigg\lvert \sum_{0\le n<g^{K}} e(f_{K}^{[\mkern2mu j]}(n)-\beta n) \bigg\rvert.\nonumber \end{align} $$

For the sum ${\sum }_{2}$ , using Lemma 3.1, we obtain

$$\begin{align*}\Big\lvert{\sum}_{2}\Big\rvert = \bigg\lvert e(f_{L-K}^{[\mkern2mu j+K]}(y)-\beta g^{K}y) \sum_{0\le n<z} e(f_{K}^{[\mkern2mu j]}(n)-\beta n) \bigg\rvert \le \bigg\lvert \sum_{0\le n<z} e(f_{K}^{[\mkern2mu j]}(n)-\beta n) \bigg\rvert. \end{align*}$$

When $z\ge 1$ , we have $0\le [\frac {\log \lceil z\rceil }{\log g}]=[\frac {\log z}{\log g}]<K$ and so the induction hypothesis implies that

(3.5) $$ \begin{align} \Big\lvert{\sum}_{2}\Big\rvert \le (g-1) \sum_{0\le\lambda<K} \bigg\lvert \sum_{0\le n<g^{\lambda}} e(f_{\lambda}^{[\mkern2mu j]}(n)-\beta n) \bigg\rvert. \end{align} $$

This holds clearly if $z=0$ . On inserting (3.4) and (3.5) into (3.3) and using (3.1), we obtain

$$\begin{align*}\bigg\lvert \sum_{0\le n<x} e(f_{L}^{[\mkern2mu j]}(n)-\beta n) \bigg\rvert \le (g-1) \sum_{0\le\lambda\le K} \bigg\lvert \sum_{0\le n<g^{\lambda}} e(f_{\lambda}^{[\mkern2mu j]}(n)-\beta n) \bigg\rvert, \end{align*}$$

that is, the assertion for the case $k=K$ .

Proof. (i). By the definition (4.5) of $\sigma _{\lambda }^{[\mkern 2mu j]}(\boldsymbol {\alpha })$ , we have

$$\begin{align*}\sigma_{\lambda-1}^{[\mkern2mu j+1]}(\boldsymbol{\alpha}) = \sum_{0\le i<\lambda-1} \gamma_{i}^{[\mkern2mu j+1]}(\boldsymbol{\alpha}) = \sum_{0\le i<\lambda-1} \gamma_{i+1}^{[\mkern2mu j]}(\boldsymbol{\alpha}) = \sum_{1\le i<\lambda} \gamma_{i}^{[\mkern2mu j]}(\boldsymbol{\alpha}) = \sigma_{\lambda}^{[\mkern2mu j]}(\boldsymbol{\alpha}) - \gamma_{0}^{[\mkern2mu j]}(\boldsymbol{\alpha}). \end{align*}$$

By using (4.4), we obtain (i).

(ii). By (i), proven above, for $\mu \in [0,\lambda -1]\cap \mathbb {Z}$ , we have

$$ \begin{align*} f(\mu+1)-f(\mu) &= A\bigg(\frac{1}{2}-\eta_{g}\bigg) + \sigma_{\lambda-(\mu+1)}^{[\mkern2mu j+\mu+1]}(\boldsymbol{\alpha}) - \sigma_{\lambda-\mu}^{[\mkern2mu j+\mu]}(\boldsymbol{\alpha}) \\ &\ge \frac{\log 2}{\log g}\bigg(\frac{1}{2}-\eta_{g}\bigg) - \frac{\log 2}{4g^{3}(\log g)^{2}}>0 \end{align*} $$

by (4.15). This proves (ii).

(iii). By (4.4) and (4.5), we have

$$\begin{align*}f(\lambda+1)-f(\lambda) = A-\gamma_{\lambda}^{[\mkern2mu j]}(\boldsymbol{\alpha}) \ge0, \end{align*}$$

and so (iii) follows.

Proof. By rewriting $mn$ as $n$ , $mt$ as $t,$ and taking care of the terms with $n=0$ and $n=t$ , we have

$$\begin{align*}S_{\mathrm{I}} \ll \sum_{1\le m\le M} \sup_{m\le t\le x} \bigg\lvert \sum_{\substack{ 0\le n<t\\ n\equiv 0\ (\mathrm{mod}\ m) }} e(f_{L}(n)) \bigg\rvert + M. \end{align*}$$

By the orthogonality, we have

(5.1) $$ \begin{align} S_{\mathrm{I}} &\ll \sum_{1\le m\le M} \sup_{m\le t\le x} \bigg\lvert \frac{1}{m} \sum_{0\le k<m} \sum_{0\le n<t} e\bigg(f_{L}(n)-\frac{kn}{m}\bigg) \bigg\rvert + M \nonumber\\ &\ll \sum_{1\le m\le M} \frac{1}{m} \sum_{0\le k<m} \sup_{m\le t\le x} \bigg\lvert \sum_{0\le n<t} e\bigg(f_{L}(n)-\frac{kn}{m}\bigg) \bigg\rvert + M. \end{align} $$

We may replace $x$ by $[x]$ in (5.1), and then, by applying Lemma 3.2, we can bound (5.1) as

$$ \begin{align*} S_{\mathrm{I}} &\ll \sum_{0\le\lambda\le\frac{\log x}{\log g}} \sum_{1\le m\le M} \frac{1}{m} \sum_{0\le k<m} \bigg\lvert \sum_{0\le n<g^{\lambda}} e\bigg(f_{\lambda}(n)-\frac{kn}{m}\bigg) \bigg\rvert + M \\ &= \sum_{0\le\lambda\le\frac{\log x}{\log g}} \sum_{1\le m\le M} \frac{g^{\lambda}}{m} \sum_{0\le k<m} \bigg\lvert F_{\lambda}\bigg(\frac{k}{m}\bigg) \bigg\rvert + M. \end{align*} $$

By classifying the terms according to the values of $(k,m)=d$ , we have

(5.2) $$ \begin{align} \begin{aligned} S_{\mathrm{I}} &\ll \sum_{0\le\lambda\le\frac{\log x}{\log g}} \sum_{1\le d\le M} \sum_{\substack{ 1\le m\le M\\ d\mid m }} \frac{g^{\lambda}}{m} \sum_{\substack{ 0\le k<m\\ (k,m)=d }} \bigg\lvert F_{\lambda}\bigg(\frac{k}{m}\bigg) \bigg\rvert + M\\ &= \sum_{0\le\lambda\le\frac{\log x}{\log g}} \sum_{1\le d\le M} \frac{1}{d} \sum_{1\le m\le M/d} \frac{g^{\lambda}}{m} \sum_{\substack{ 0\le k<m\\ (k,m)=1 }} \bigg\lvert F_{\lambda}\bigg(\frac{k}{m}\bigg) \bigg\rvert + M, \end{aligned} \end{align} $$

where, in the last equality, we made the change of variables $k\rightsquigarrow dk$ and $m\rightsquigarrow dm$ .

In order to bound the inner sum of (5.2), we bound the sum

$$\begin{align*}T := \sum_{U\le m\le2U} \frac{g^{\lambda}}{m} \sum_{\substack{ 0\le k<m\\ (k,m)=1}} \bigg\lvert F_{\lambda}\bigg(\frac{k}{m}\bigg) \bigg\rvert \end{align*}$$

for $1\le U\le M/d$ with $1\le d\le M$ by using Lemma 4.15. Write

$$\begin{align*}\mu_{U} := \bigg[\frac{\log U}{\log g}\bigg]. \end{align*}$$

When $2\mu _{U}\le \lambda $ , Lemma 4.15 gives

$$\begin{align*}T \ll g^{\lambda}U^{-1} \sum_{U\le m\le2U} \sum_{\substack{ 0\le k<m\\ (k,m)=1 }} \bigg\lvert F_{\lambda}\bigg(\frac{k}{m}\bigg) \bigg\rvert \ll g^{\lambda-(\frac{1}{2}-\eta_{g})2\mu_{U}-\sigma_{\lambda-2\mu_{U}}^{[2\mu_{U}]}(\boldsymbol{\alpha})}. \end{align*}$$

By (ii) and (iii) of Lemma 5.1, we have

(5.3) $$ \begin{align} T \ll g^{\frac{1}{2}\lambda}g^{\frac{1}{2}\lambda-\sigma_{\lambda}(\boldsymbol{\alpha})} \le g^{\frac{1}{2}\lambda}g^{\frac{1}{2}\xi_{\mathrm{I}}-\sigma_{\xi_{\mathrm{I}}}(\boldsymbol{\alpha})} \ll g^{\frac{1}{2}\lambda} x^{\frac{1}{2}} g^{-\kappa_{\mathrm{I}}}. \end{align} $$

When $0\le \lambda <2\mu _{U}$ , Lemma 4.15 gives

(5.4) $$ \begin{align} T \ll g^{\lambda}U^{-1} \sum_{U\le m\le2U} \sum_{\substack{ 0\le k<m\\ (k,m)=1}} \bigg\lvert F_{\lambda}\bigg(\frac{k}{m}\bigg) \bigg\rvert \ll Ug^{\eta_{g}\lambda} \ll \frac{M}{d}g^{\eta_{g}\lambda}. \end{align} $$

By (5.3) and (5.4), in any case, we have

(5.5) $$ \begin{align} T \ll g^{\frac{1}{2}\lambda} x^{\frac{1}{2}} g^{-\kappa_{\mathrm{I}}} + \frac{M}{d}g^{\eta_{g}\lambda}. \end{align} $$

Inserting (5.5) into (5.2) and using $\eta _{g}>0$ as seen in (4.15), we get

(5.6) $$ \begin{align} S_{\mathrm{I}} \ll (\log x)^{2} \sum_{0\le\lambda\le\frac{\log x}{\log g}} (g^{\frac{1}{2}\lambda} x^{\frac{1}{2}} g^{-\kappa_{\mathrm{I}}} + Mg^{\eta_{g}\lambda}) +M \ll (xg^{-\kappa_{\mathrm{I}}} + Mx^{\eta_{g}}) (\log x)^{2}. \end{align} $$

By using (4.6) and (4.15), we have

$$\begin{align*}\kappa_{\mathrm{I}} \le \frac{\xi_{\mathrm{I}}}{4g^{3}\log g} \le \frac{\log x}{\log g}\bigg(\frac{1}{2}-\eta_{g}\bigg). \end{align*}$$

Thus, the assumption $M\le x^{\frac {1}{2}}$ gives

$$\begin{align*}Mx^{\eta_{g}} \le x^{\frac{1}{2}+\eta_{g}} = x^{1-(\frac{1}{2}-\eta_{g})} \le xg^{-\kappa_{\mathrm{I}}}. \end{align*}$$

On inserting this estimate into (5.6), we obtain the result.

Proof. See, for example, Montgomery–Vaughan [Reference Montgomery and Vaughan12, Lemma 16.8, p. 10].

Proof. For $(m,n)\in \mathbb {N}^{2}$ , if there is no $k\in \mathbb {N}$ with

(6.3) $$ \begin{align} mn<kg^{\lambda}\le m(n+r), \end{align} $$

that is, if $[\frac {mn}{g^{\lambda }}]=[\frac {m(n+r)}{g^{\lambda }}]$ , then we have

$$\begin{align*}\varepsilon_{i}(m(n+r))=\varepsilon_{i}(mn) \quad\text{for } i\ge\lambda \end{align*}$$

since

$$\begin{align*}\sum_{i\ge\lambda}\varepsilon_{i}(m(n+r))g^{i-\lambda} = \bigg[\frac{m(n+r)}{g^{\lambda}}\bigg] = \bigg[\frac{mn}{g^{\lambda}}\bigg] = \sum_{i\ge\lambda}\varepsilon_{i}(mn)g^{i-\lambda}. \end{align*}$$

Therefore, if there is no $k\in \mathbb {N}$ with (6.3), then since $\lambda \le L$ , we have

$$ \begin{align*} f_{L}(m(n+r))-f_{L}(mn) &= \sum_{0\le i<L} \big( \alpha_{i}(\varepsilon_{i}(m(n+r))) - \alpha_{i}(\varepsilon_{i}(mn)) \big) \\ &= \sum_{0\le i<\lambda} \big( \alpha_{i}(\varepsilon_{i}(m(n+r))) - \alpha_{i}(\varepsilon_{i}(mn)) \big) = f_{\lambda}(m(n+r))-f_{\lambda}(mn). \end{align*} $$

Thus, if $(m,n)\in \mathscr {E}$ , there exists $k\in \mathbb {N}$ satisfying (6.3). Since such $k$ must satisfy

$$\begin{align*}mN<kg^{\lambda}\le m(2N+r), \end{align*}$$

we have

(6.4) $$ \begin{align} \begin{aligned} \#\mathscr{E} &\le \sum_{M<m\le 2M} \sum_{\frac{mN}{g^{\lambda}}<k\le\frac{m(2N+r)}{g^{\lambda}}} \sum_{\substack{ N<n\le 2N\\ mn<kg^{\lambda}\le m(n+r) }} 1\\ &\le \sum_{M<m\le 2M} \sum_{\frac{mN}{g^{\lambda}}<k\le\frac{m(2N+r)}{g^{\lambda}}} \sum_{\frac{kg^{\lambda}}{m}-r\le n<\frac{kg^{\lambda}}{m}} 1\\ &\ll r\sum_{M<m\le 2M} \bigg(\frac{m(N+r)}{g^{\lambda}}+1\bigg) \ll MR\bigg(\frac{M(N+R)}{g^{\lambda}}+1\bigg). \end{aligned} \end{align} $$

By (6.1) and (6.2), we have $g^{\lambda }\asymp MR^{2}\ll MN$ . Thus, we can bound (6.4) further as

$$\begin{align*}\#\mathscr{E} \ll \frac{M^{2}NR}{g^{\lambda}} \ll \frac{MN}{R} \end{align*}$$

as desired. This completes the proof.

Proof. See Lemma 6 of [Reference Mauduit and Rivat7, p. 1609].

Proof. We may assume $MN<x$ since otherwise $S_{\mathrm{II}}$ is an empty sum and the assertion is trivial. By symmetry, we may assume $M\le N$ . Since $MN<x$ , we then have $M\le x^{\frac {1}{2}}$ . Take $\mu \in \mathbb {N}$ with

(6.6) $$ \begin{align} g^{\mu-1}\le M<g^{\mu}. \end{align} $$

By (6.5) and $M\le x^{\frac {1}{2}}$ , we have

(6.7) $$ \begin{align} \theta\cdot\frac{\log x}{\log g}<\mu\le\frac{1}{2}\frac{\log x}{\log g}+1. \end{align} $$

By the Cauchy–Schwarz inequality, we have

(6.8) $$ \begin{align} \lvert S_{\mathrm{II}}\rvert^{2} \le M \sum_{M<m\le 2M} \bigg\lvert \sum_{\substack{ N<n\le 2N\\ mn\le x }} b_{n} e(f_{L}(mn)) \bigg\rvert^{2}. \end{align} $$

Take a real parameter

(6.9) $$ \begin{align} R\in[1,N^{\frac{1}{2}}]. \end{align} $$

By applying Lemma 6.1 to (6.8) with $R$ replaced by $[R]+1$ , we have

$$ \begin{align*} \begin{aligned} \lvert S_{\mathrm{II}}\rvert^{2} &\ll \frac{M(N+[R])}{[R]+1} \sum_{M<m\le 2M} \sum_{\lvert r\rvert\le R}\bigg(1-\frac{\lvert r\rvert}{[R]+1}\bigg)\\ & \cdot \sum_{\substack{ N<n,n+r\le 2N\\ mn,m(n+r)\le x }} b_{n+r}\overline{b_{n}} e\big(f_{L}(m(n+r))-f_{L}(mn)\big)\\ &\ll \frac{MN}{R} \sum_{\lvert r\rvert\le R} \sum_{\substack{ N<n,n+r\le 2N }} \bigg\lvert \sum_{\substack{ M<m\le 2M\\ mn,m(n+r)\le x }} e\big(f_{L}(m(n+r))-f_{L}(mn)\big) \bigg\rvert. \end{aligned} \end{align*} $$

Note that the contribution from the terms with $r<0$ is the same as that from the terms with $r>0$ . This can be seen by changing variables via $n\rightsquigarrow n-r$ and taking the complex conjugate inside the absolute value sign. Thus, separating off the contribution of $r=0$ and enlarging the range of $n$ by dropping the condition $n+r\le 2N$ , we have

$$ \begin{align*} \lvert S_{\mathrm{II}}\rvert^{2} \ll \frac{MN}{R} \sum_{1\le r\le R} \sum_{\substack{ N<n\le 2N }} \bigg\lvert \sum_{\substack{ M<m\le 2M\\ m(n+r)\le x }} e\big(f_{L}(m(n+r))-f_{L}(mn)\big) \bigg\rvert + \frac{M^{2}N^{2}}{R}. \end{align*} $$

We now use Lemma 6.2 to truncate $f_{L}$ . By (6.9), the condition $R\le N^{\frac {1}{2}}$ is satisfied. Take $\lambda \in \mathbb {N}$ by

(6.10) $$ \begin{align} g^{\lambda-1}\le MR^{2}<g^{\lambda} \end{align} $$

as in Lemma 6.2. Since we are assuming $MN<x$ , by using $x\le g^{L}$ and $R\le N^{\frac {1}{2}}$ , we have

$$\begin{align*}g^{\lambda-1}\le MR^{2}\le MN<x\le g^{L} \end{align*}$$

and so the condition $\lambda \le L$ is also satisfied. Thus, we can use Lemma 6.2 to truncate $f_{L}$ as

(6.11) $$ \begin{align} \begin{aligned} \lvert S_{\mathrm{II}}\rvert^{2} &\ll \frac{MN}{R} \sum_{1\le r\le R} \sum_{\substack{ N<n\le 2N }} \bigg\lvert \sum_{\substack{ M<m\le 2M\\ m(n+r)\le x }} e\big(f_{\lambda}(m(n+r))-f_{\lambda}(mn)\big) \bigg\rvert + \frac{M^{2}N^{2}}{R}\\ &\ll MN \sup_{1\le r\le R}S_{\mathrm{II}}(r) + \frac{M^{2}N^{2}}{R}, \end{aligned} \end{align} $$

where the sum $S_{\mathrm{II}}(r)$ is defined by

(6.12) $$ \begin{align} S_{\mathrm{II}}(r) := \sum_{\substack{ N<n\le 2N }}\lvert T(r,n)\rvert \quad\text{with}\quad T(r,n) := \sum_{\substack{ M<m\le 2M\\ m(n+r)\le x }} e\big(f_{\lambda}(m(n+r))-f_{\lambda}(mn)\big). \end{align} $$

Since $f_{\lambda }$ has a period $g^{\lambda }$ , by using the exponential sum (4.1), we can write

$$ \begin{align*} T(r,n) &= \sum_{0\le u<g^{\lambda}} e(f_{\lambda}(u)) \sum_{0\le v<g^{\lambda}} e(-\,f_{\lambda}(v)) \sum_{\substack{ M<m\le 2M \\ m(n+r)\le x \\ m(n+r)\equiv u\ (\mathrm{mod}\ g^{\lambda}) \\ mn\equiv v\ (\mathrm{mod}\ g^{\lambda}) }} 1 \\ &= \sum_{0\le u<g^{\lambda}} e(f_{\lambda}(u)) \sum_{0\le v<g^{\lambda}} e(-\,f_{\lambda}(v)) \\ & \cdot \frac{1}{g^{2\lambda}} \sum_{0\le h<g^{\lambda}} \sum_{0\le k<g^{\lambda}} \sum_{\substack{ M<m\le 2M \\ m(n+r)\le x }} e\bigg(\frac{h(m(n+r)-u)}{g^{\lambda}}+\frac{k(mn-v)}{g^{\lambda}}\bigg) \\ &= \sum_{0\le h<g^{\lambda}} \sum_{0\le k<g^{\lambda}} F_{\lambda}\bigg(\frac{h}{g^{\lambda}}\bigg) \overline{F_{\lambda}\bigg(-\frac{k}{g^{\lambda}}\bigg)} \sum_{\substack{ M<m\le 2M \\ m(n+r)\le x }} e\bigg(\frac{(h+k)n+hr}{g^{\lambda}}m\bigg). \end{align*} $$

Since the inner sum over $m$ is a sum of geometric sequence, we have

$$ \begin{align*} \lvert T(r,n)\rvert \ll \sum_{0\le h<g^{\lambda}} \sum_{0\le k<g^{\lambda}} \bigg\lvert F_{\lambda}\bigg(\frac{h}{g^{\lambda}}\bigg) \bigg\rvert \bigg\lvert F_{\lambda}\bigg(-\frac{k}{g^{\lambda}}\bigg) \bigg\rvert \min\bigg( M, \frac{1}{\lvert\sin(\pi\frac{(h+k)n+hr}{g^{\lambda}})\rvert} \bigg). \end{align*} $$

By taking the sum over $n$ and recalling (6.12), we have

(6.13) $$ \begin{align} \begin{aligned} S_{\mathrm{II}}(r) &\ll \sum_{0\le h<g^{\lambda}} \sum_{0\le k<g^{\lambda}} \bigg\lvert F_{\lambda}\bigg(\frac{h}{g^{\lambda}}\bigg) \bigg\rvert \bigg\lvert F_{\lambda}\bigg(-\frac{k}{g^{\lambda}}\bigg) \bigg\rvert \sum_{N<n\le2N} \min\bigg( M, \frac{1}{\lvert\sin(\pi\frac{(h+k)n+hr}{g^{\lambda}})\rvert} \bigg). \end{aligned} \end{align} $$

Since the term

$$\begin{align*}\min\bigg( M, \frac{1}{\lvert\sin(\pi\frac{(h+k)n+hr}{g^{\lambda}})\rvert} \bigg) \end{align*}$$

depends only on $n\ (\mathrm{mod}\ g^{\lambda })$ , we can bound (6.13) as

(6.14) $$ \begin{align} \begin{aligned} S_{\mathrm{II}}(r) &\ll \bigg(\frac{N}{g^{\lambda}}+1\bigg) \sum_{0\le h<g^{\lambda}} \sum_{0\le k<g^{\lambda}} \bigg\lvert F_{\lambda}\bigg(\frac{h}{g^{\lambda}}\bigg) \bigg\rvert \bigg\lvert F_{\lambda}\bigg(-\frac{k}{g^{\lambda}}\bigg) \bigg\rvert\\ & \cdot \sum_{0\le n<g^{\lambda}} \min\bigg( M, \frac{1}{\lvert\sin(\pi\frac{(h+k)n+hr}{g^{\lambda}})\rvert} \bigg) \end{aligned} \end{align} $$

by adding extra terms if necessary. By using Lemma 6.3 in (6.14), we have

(6.15) $$ \begin{align} \begin{aligned} S_{\mathrm{II}}(r) &\ll \bigg(\frac{N}{g^{\lambda}}+1\bigg) \sum_{d\mid g^{\lambda}} d \sum_{\substack{ 0\le h,k<g^{\lambda}\\ (h+k,g^{\lambda})=d }} \bigg\lvert F_{\lambda}\bigg(\frac{h}{g^{\lambda}}\bigg) \bigg\rvert \bigg\lvert F_{\lambda}\bigg(-\frac{k}{g^{\lambda}}\bigg) \bigg\rvert \min\bigg( M, \frac{1}{\sin(\pi\frac{d}{g^{\lambda}}\|\frac{hr}{d}\|)} \bigg)\\ & + \bigg(\frac{N}{g^{\lambda}}+1\bigg) g^{\lambda}(\log x) \sum_{0\le h<g^{\lambda}} \sum_{0\le k<g^{\lambda}} \bigg\lvert F_{\lambda}\bigg(\frac{h}{g^{\lambda}}\bigg) \bigg\rvert \bigg\lvert F_{\lambda}\bigg(-\frac{k}{g^{\lambda}}\bigg) \bigg\rvert\\ &=: \bigg(\frac{N}{g^{\lambda}}+1\bigg) (S_{\mathrm{II},1}(r)+S_{\mathrm{II},2}(r)). \end{aligned} \end{align} $$

We first estimate the sum $S_{\mathrm{II},1}(r)$ . Since $d\mid g^{\lambda }$ in the sum $S_{\mathrm{II},1}(r)$ , we can bound $S_{\mathrm{II},1}(r)$ as

$$ \begin{align*} S_{\mathrm{II},1}(r) \le \sum_{d\mid g^{\lambda}} d \sum_{\substack{ 0\le h,k<g^{\lambda} \\ h\equiv-k\ (\mathrm{mod}\ d) }} \bigg\lvert F_{\lambda}\bigg(\frac{h}{g^{\lambda}}\bigg) \bigg\rvert \bigg\lvert F_{\lambda}\bigg(-\frac{k}{g^{\lambda}}\bigg) \bigg\rvert \min\bigg( M, \frac{1}{\sin(\pi\frac{d}{g^{\lambda}}\|\frac{hr}{d}\|)} \bigg) \end{align*} $$

by weakening the condition $(h+k,g^{\lambda })=d$ to $h\equiv -k\ (\mathrm{mod}\ d)$ . Since the function

$$\begin{align*}\mathbb{Z}\to\mathbb{R};\ k\mapsto \bigg\lvert F_{\lambda}\bigg(\frac{k}{g^{\lambda}}\bigg) \bigg\rvert \end{align*}$$

has a period $g^{\lambda }$ , we can change variables via $k\rightsquigarrow {-k}$ to get

$$\begin{align*}S_{\mathrm{II},1}(r) \le \sum_{d\mid g^{\lambda}} d \sum_{\substack{ 0\le h,k<g^{\lambda}\\ h\equiv k\ (\mathrm{mod}\ d) }} \bigg\lvert F_{\lambda}\bigg(\frac{h}{g^{\lambda}}\bigg) \bigg\rvert \bigg\lvert F_{\lambda}\bigg(\frac{k}{g^{\lambda}}\bigg) \bigg\rvert \min\bigg( M, \frac{1}{\sin(\pi\frac{d}{g^{\lambda}}\|\frac{hr}{d}\|)} \bigg). \end{align*}$$

By classifying the values of $h\equiv k\ (\mathrm{mod}\ d)$ , we obtain

$$ \begin{align*} S_{\mathrm{II},1}(r) \le \sum_{d\mid g^{\lambda}} d \sum_{0\le a<d} \min\bigg( M, \frac{1}{\sin(\pi\frac{d}{g^{\lambda}}\|\frac{ar}{d}\|)} \bigg) \bigg( \sum_{\substack{ 0\le h<g^{\lambda} \\ h\equiv a\ (\mathrm{mod}\ d) }} \bigg\lvert F_{\lambda}\bigg(\frac{h}{g^{\lambda}}\bigg) \bigg\rvert \bigg)^{2}. \end{align*} $$

Let $v_{g}(d)$ be the largest integer satisfying $g^{v_{g}(d)}\mid d$ . By Lemma 4.11, we then have

$$\begin{align*}S_{\mathrm{II},1}(r) \ll \sum_{d\mid g^{\lambda}} d^{1-2\eta_{g}} g^{2\eta_{g}\lambda} \sum_{0\le a<d} \min\bigg( M, \frac{1}{\sin(\pi\frac{d}{g^{\lambda}}\|\frac{ar}{d}\|)} \bigg) \bigg\lvert F_{v_{g}(d)}^{[\lambda-v_{g}(d)]}\bigg(\frac{a}{g^{v_{g}(d)}}\bigg) \bigg\rvert^{2}. \end{align*}$$

By using Lemma 4.5, we have

(6.16) $$ \begin{align} S_{\mathrm{II},1}(r) \ll \sum_{d\mid g^{\lambda}} d^{1-2\eta_{g}} g^{2\eta_{g}\lambda-\sigma_{v_{g}(d)}^{[\lambda-v_{g}(d)]}(\boldsymbol{\alpha})} \sum_{0\le a<d} \min\bigg( M, \frac{1}{\sin(\pi\frac{d}{g^{\lambda}}\|\frac{ar}{d}\|)} \bigg). \end{align} $$

Since $x\mapsto \sin \pi x$ is concave for $x\in [0,\frac {1}{2}]$ , we have

$$\begin{align*}\sin\bigg(\pi\frac{d}{g^{\lambda}}\bigg\|\frac{ar}{d}\bigg\|\bigg) \ge \frac{d}{g^{\lambda}}\sin\bigg(\pi\bigg\|\frac{ar}{d}\bigg\|\bigg) = \frac{d}{g^{\lambda}}\bigg\lvert\sin\bigg(\pi\frac{ar}{d}\bigg)\bigg\rvert, \end{align*}$$

and so we can apply Lemma 6.3 to the inner sum of (6.16) to obtain

$$ \begin{align*} \sum_{0\le a<d} \min\bigg( M, \frac{1}{\sin(\pi\frac{d}{g^{\lambda}}\|\frac{ar}{d}\|)} \bigg) &\le \frac{g^{\lambda}}{d} \sum_{0\le a<d} \min\bigg( \frac{dM}{g^{\lambda}}, \frac{1}{\lvert\sin(\pi\frac{ar}{d})\rvert} \bigg) \\ &\ll \frac{g^{\lambda}}{d} \bigg( (r,d)\frac{dM}{g^{\lambda}} + d\log d \bigg) \ll MR+g^{\lambda}\log d \ll g^{\lambda}\log x \end{align*} $$

since $g^{\lambda }\asymp MR^{2}$ by (6.10). On inserting this estimate into (6.16), we get

$$\begin{align*}S_{\mathrm{II},1}(r) \ll (\log x) \sum_{d\mid g^{\lambda}} d^{1-2\eta_{g}} g^{(1+2\eta_{g})\lambda-\sigma_{v_{g}(d)}^{[\lambda-v_{g}(d)]}(\boldsymbol{\alpha})}. \end{align*}$$

We now write $d=kg^{\delta }$ with $0\le \delta \le \lambda $ and $g\nmid k$ so that $v_{g}(d)=\delta $ . This gives

(6.17) $$ \begin{align} S_{\mathrm{II},1}(r) \ll (\log x) \sum_{0\le\delta\le\lambda} g^{(1+2\eta_{g})\lambda+\delta(1-2\eta_{g})-\sigma_{\delta}^{[\lambda-\delta]}(\boldsymbol{\alpha})} \sum_{\substack{ k\mid g^{\lambda-\delta} \\ g\nmid k }} k^{1-2\eta_{g}}. \end{align} $$

For $k\mid g^{\lambda -\delta }$ with $g\nmid k$ , we have $(k,g)\le g/2$ , and so

$$\begin{align*}k = (k,g^{\lambda-\delta}) \le (k,g)^{\lambda-\delta} \le (g/2)^{\lambda-\delta}. \end{align*}$$

This gives

$$\begin{align*}\sum_{\substack{ k\mid g^{\lambda-\delta}\\ g\nmid k }} k^{1-2\eta_{g}} \le (g/2)^{(1-2\eta_{g})(\lambda-\delta)} \tau(g^{\lambda-\delta}) \ll g^{(1-2\eta_{g})(\lambda-\delta)-\omega_{g}(\lambda-\delta)} \end{align*}$$

with

$$\begin{align*}\omega_{g} := \frac{\log 2}{\log g}\bigg(\frac{1}{2}-\eta_{g}\bigg) \end{align*}$$

by using the bound $\tau (n)\ll _{\varepsilon }n^{\varepsilon }$ . On inserting this estimate into (6.17), we get

(6.18) $$ \begin{align} \begin{aligned} S_{\mathrm{II},1}(r) &\ll g^{2\lambda} (\log x)^{2} \max_{0\le\delta\le\lambda} g^{-\omega_{g}(\lambda-\delta)-\sigma_{\delta}^{[\lambda-\delta]}(\boldsymbol{\alpha})} = g^{2\lambda} (\log x)^{2} \max_{0\le\delta\le\lambda} g^{-\omega_{g}\delta-\sigma_{\lambda-\delta}^{[\delta]}(\boldsymbol{\alpha})}, \end{aligned} \end{align} $$

where we changed variables via $\delta \rightsquigarrow \lambda -\delta $ in the last equality. By (6.6) and (6.10), we have

(6.19) $$ \begin{align} g^{\mu-1}\le M\le MR^{2}<g^{\lambda}, \quad\text{and so}\quad \mu\in[0,\lambda]\cap\mathbb{Z}. \end{align} $$

Thus, by (ii) of Lemma 5.1 and (6.7), we have

$$\begin{align*}\omega_{g}\delta+\sigma_{\lambda-\delta}^{[\delta]}(\boldsymbol{\alpha}) \ge \sigma_{\lambda}(\boldsymbol{\alpha}) \ge \sigma_{\mu}(\boldsymbol{\alpha}) \ge 10\kappa_{\mathrm{II}} \end{align*}$$

in (6.18) and so

(6.20) $$ \begin{align} S_{\mathrm{II},1}(r) \ll g^{2\lambda-10\kappa_{\mathrm{II}}}(\log x)^{2}. \end{align} $$

For the sum $S_{\mathrm{II},2}(r)$ , we can simply use (4.16) of Lemma 4.11 to get

$$ \begin{align*} S_{\mathrm{II},2}(r) = g^{\lambda}(\log x) \bigg( \sum_{0\le h<g^{\lambda}} \bigg\lvert F_{\lambda}\bigg(\frac{h}{g^{\lambda}}\bigg) \bigg\rvert \bigg)^{2} \ll g^{(1+2\eta_{g})\lambda}\log x = g^{2\lambda-(1-2\eta_{g})\lambda}\log x. \end{align*} $$

By (4.6), (4.15), (6.7), and (6.19), we have

$$\begin{align*}(1-2\eta_{g})\lambda \ge \bigg(\frac{1}{2}-\eta_{g}\bigg)\xi_{\mathrm{II}} \ge \frac{\xi_{\mathrm{II}}}{4g^{3}\log g} \ge 10\kappa_{\mathrm{II}}, \end{align*}$$

we have

(6.21) $$ \begin{align} \begin{aligned} S_{\mathrm{II},2}(r) \ll g^{2\lambda-10\kappa_{\mathrm{II}}}\log x. \end{aligned} \end{align} $$

On inserting (6.20) and (6.21) into (6.15) and recalling (6.10), we obtain

$$\begin{align*}S_{\mathrm{II}}(r) \ll (Ng^{\lambda}+g^{2\lambda})g^{-10\kappa_{\mathrm{II}}}(\log x)^{2} \ll (MNR^{2}+M^{2}R^{4})g^{-10\kappa_{\mathrm{II}}}(\log x)^{2}. \end{align*}$$

Since we are assuming $M\le N$ , this can be bounded as

$$\begin{align*}S_{\mathrm{II}}(r) \ll MNR^{4}g^{-10\kappa_{\mathrm{II}}}(\log x)^{2}. \end{align*}$$

On inserting this estimate into (6.11), we obtain

(6.22) $$ \begin{align} S_{\mathrm{II}} \ll MNR^{2}g^{-5\kappa_{\mathrm{II}}}\log x + MNR^{-\frac{1}{2}}. \end{align} $$

We now choose $R=g^{2\kappa _{\mathrm{II}}}$ . By (4.6), we have

$$\begin{align*}2\kappa_{\mathrm{II}} \le \frac{\xi_{\mathrm{II}}}{2g^{3}\log g} \le \frac{\theta}{2}\frac{\log x}{\log g}, \end{align*}$$

and so, by (6.5), we have

$$\begin{align*}R=g^{2\kappa_{\mathrm{II}}}\le x^{\frac{\theta}{2}}\le N^{\frac{1}{2}} \end{align*}$$

as required in (6.9). On inserting $R=g^{2\kappa _{\mathrm{II}}}$ and $MN<x$ into (6.22), we obtain the assertion.

Proof. See formula (17.5) and the argument on pp. 55–56 of [Reference Montgomery and Vaughan12].

Proof. Let $z=x^{\frac {1}{4}}$ . By Lemma 7.1, we can decompose the sum as

(7.1) $$ \begin{align} S=S_{1}+S_{2}+S_{3}+S_{4}, \end{align} $$

where

$$ \begin{align*} S_{1} &:= \sum_{\substack{ mn\le x\\ m\le z }}\mu(m)(\log n)e(f_{L}(mn)), \qquad S_{2} := \sum_{\substack{ mn\le x\\ m,n>z }} \mu(m)c_{2}(n) e(f_{L}(mn)),\\ S_{3} &:= - \sum_{\substack{ mn\le x\\ m\le z^{2} }} c_{3}(m)e(f_{L}(mn)), \qquad\!\!\qquad S_{4} := \sum_{n\le z} \Lambda(n) e(f_{L}(n)). \end{align*} $$

We estimate these sums separately.

For the sum $S_{1}$ , since $z\le x^{\frac {1}{2}}$ , we can use partial summation and Lemma 5.2 to get

(7.2) $$ \begin{align} S_{1} \ll (\log x) \sum_{m\le z} \sup_{1\le t\le x/m} \bigg\lvert \sum_{n\le t}e(f_{L}(mn)) \bigg\rvert \ll xg^{-\kappa}(\log x)^{3}, \end{align} $$

where we used $\kappa _{\mathrm{I}}\ge \kappa $ .

For the sum $S_{2}$ , we can use Lemma 6.4. Note that

(7.3) $$ \begin{align} \lvert c_{2}(n)\rvert, \lvert c_{3}(n)\rvert \le \sum_{d\mid n}\Lambda(d) = \log n. \end{align} $$

We can take $\theta =\frac {1}{4}$ in Lemma 6.4 so $\kappa _{\mathrm{II}}=\kappa $ . Thus, by decomposing the sum dyadically, we get

(7.4) $$ \begin{align} S_{2} \ll (\log x)^{3} \sup_{\substack{ M,N\ge x^{\frac{1}{4}}\\ \lvert a(m)\rvert, \lvert b(n)\rvert\le1 }} \bigg\lvert \sum_{\substack{ mn\le x\\ M<m\le2M\\ N<n\le2N }} a(m)b(n)e(\kern0.5pt f_{L}(mn)) \bigg\rvert \ll xg^{-\kappa}(\log x)^{4}. \end{align} $$

For the sum $S_{3}$ , since $z^{2}\le x^{\frac {1}{2}}$ , Lemma 5.2 together with (7.3) gives

$$ \begin{align*} S_{3} \ll (\log x) \sum_{m\le z^{2}} \bigg\lvert \sum_{n\le x/m} e(\kern0.5pt f_{L}(mn)) \bigg\rvert \ll xg^{-\kappa}(\log x)^{3}. \end{align*} $$

Finally, the sum $S_{4}$ is bounded trivially as

(7.5) $$ \begin{align} S_{4} \ll z\log x \ll x^{1-\frac{3}{4}}\log x \ll xg^{-\kappa}\log x, \end{align} $$

where we used the bound

$$\begin{align*}\kappa \le \frac{\xi}{20} \le \frac{1}{80}\frac{\log x}{\log g} < \frac{3}{4}\frac{\log x}{\log g}, \end{align*}$$

which follows by (4.6).

On inserting (7.2) and (7.4)–(7.5) into (7.1), we obtain the assertion.

Proof. This is Lemma 2.7 of [Reference Dartyge, Martin, Rivat, Shparlinski and Swaenepoel3]. For completeness, we give a proof. We have

$$\begin{align*}g^{i_{0}}\|\alpha\| \ge g^{\frac{\log\frac{g}{(g+1)\|\alpha\|}}{\log g}-1}\|\alpha\| = \frac{1}{g}\frac{g}{(g+1)\|\alpha\|}\cdot\|\alpha\| = \frac{1}{g+1} \end{align*}$$

and

$$\begin{align*}g^{i_{0}}\|\alpha\| \le g^{\frac{\log\frac{g}{(g+1)\|\alpha\|}}{\log g}}\|\alpha\| \le \frac{g}{(g+1)\|\alpha\|}\cdot\|\alpha\| = 1-\frac{1}{g+1}. \end{align*}$$

The result now follows since $\|g^{i_{0}}\alpha \|=\|g^{i_{0}}\|\alpha \|\|$ .

Proof. By considering the contribution of $(m,n)=(0,1)$ to (4.3), for $0\le i<\lambda $ , we have

$$ \begin{align*} \gamma_{i}(\boldsymbol{\alpha}_{L}) &\gg \|(g\alpha_{L,i}(0)-\alpha_{L,i+1}(0)) - (g\alpha_{L,i}(1)-\alpha_{L,i+1}(1))\|^{2} \\ &= \|(g^{L-i}-g^{L-(i+1)-1})\alpha\|^{2} = \|g^{L-i-2}(g^{2}-1)\alpha\|^{2} \gg \|g^{L-i-1}(g^{2}-1)\alpha\|^{2}, \end{align*} $$

where we used the inequality $g\|x/g\|\ge \|x\|$ in the last step. We thus have

(8.2) $$ \begin{align} \begin{aligned} \sigma_{\lambda}(\boldsymbol{\alpha}_{L}) = \sum_{0\le i<\lambda}\gamma_{i}(\boldsymbol{\alpha}_{L}) &\gg \sum_{0\le i<\lambda} \|g^{L-i-1}(g^{2}-1)\alpha\|^{2} = \sum_{L-\lambda\le i<L} \|g^{i}(g^{2}-1)\alpha\|^{2}. \end{aligned} \end{align} $$

Let

$$\begin{align*}J := 1+\bigg[\frac{\log\frac{g}{(g+1)\sigma}}{\log g}\bigg]\ge1,\quad K := \bigg[\frac{\lambda}{J}\bigg] \quad\text{and}\quad \alpha_{k} := g^{L-\lambda+(k-1)J}(g^{2}-1)\alpha. \end{align*}$$

We then have

(8.3) $$ \begin{align} \begin{aligned} \sum_{L-\lambda\le i<L} \|(g^{2}-1)g^{i}\alpha\|^{2} &\ge \sum_{1\le k\le K} \sum_{L-\lambda+(k-1)J\le i<L-\lambda+kJ} \|g^{i}(g^{2}-1)\alpha\|^{2}\\ &\ge \sum_{1\le k\le K} \sum_{0\le i<J} \|g^{i}\alpha_{k}\|^{2}. \end{aligned} \end{align} $$

By the assumption (8.1) and $0\le \lambda \le L$ , we have $\alpha _{k}\not \in \mathbb {Z}$ for all $k\in \{1,\ldots ,K\}$ and so Lemma 8.1 is applicable to the inner sum with $\alpha := \alpha _{k}$ . Also, (8.1) implies $\|\alpha _{k}\|\ge \sigma $ . For $1\le k<K$ , let

$$\begin{align*}i_{0,k} := \bigg[\frac{\log\frac{g}{(g+1)\|\alpha_{k}\|}}{\log g}\bigg]. \end{align*}$$

We then have

$$\begin{align*}0\le i_{0,k}\le\bigg[\frac{\log\frac{g}{(g+1)\sigma}}{\log g}\bigg]<J. \end{align*}$$

Therefore, we can pick up the contribution of $i=i_{0,k}$ and use Lemma 8.1 in (8.3) to get

(8.4) $$ \begin{align} \sum_{L-\lambda\le i<L} \|(g^{2}-1)g^{i}\alpha\|^{2} \ge \sum_{1\le k\le K} \|g^{i_{0,k}}\alpha_{k}\|^{2} \ge \frac{K}{(g+1)^{2}} \gg K. \end{align} $$

By using the estimate

$$\begin{align*}K = \frac{\lambda}{J}+O(1) \ge \frac{\lambda}{1+\frac{\log\frac{1}{\sigma}}{\log 2}} +O(1) \gg \frac{\lambda}{\log\frac{1}{\sigma}} +O(1) \end{align*}$$

in (8.4), we get

$$\begin{align*}\sum_{L-\lambda\le i<L} \|(g^{2}-1)g^{i}\alpha\|^{2} \gg \frac{\lambda}{\log\frac{1}{\sigma}} + O(1). \end{align*}$$

On inserting this estimate into (8.2), we obtain the result.

Proof. We may assume that $x$ is large and $q\ge 2$ since otherwise the assertions are trivial.

We first prove (8.5). By the orthogonality of additive characters, we have

(8.9) $$ \begin{align} \begin{aligned} \overleftarrow{\mkern4.8mu\psi}\mkern-.6mu_{L}(x,a,q) &= \frac{1}{q} \sum_{0\le h<q} e\bigg(-\frac{ha}{q}\bigg) \sum_{n\le x} \Lambda(n) e\bigg(\frac{h{\mathrm{rev}}_{L}(n)}{q}\bigg)\\ &= \sum_{\substack{ 0\le h<q\\ q\mid g^{L}(g^{2}-1)h }} + \sum_{\substack{ 0\le h<q\\ q\nmid g^{L}(g^{2}-1)h }} =: S_{\mathfrak{M}}+S_{\mathfrak{m}}. \end{aligned} \end{align} $$

For the sum $S_{\mathfrak {M}}$ , by using

$$\begin{align*}q\mid g^{L}(g^{2}-1)h \iff \frac{q}{(q,g^{L}(g^{2}-1))}\mid h, \end{align*}$$

by rewriting $h$ to $\frac {q}{(q,g^{L}(g^{2}-1))}h$ and using the orthogonality, we have

(8.10) $$ \begin{align} \begin{aligned} S_{\mathfrak{M}} &= \frac{1}{q} \sum_{0\le h<(q,g^{L}(g^{2}-1))} e\bigg(-\frac{ha}{(q,g^{L}(g^{2}-1))}\bigg) \sum_{n\le x} \Lambda(n) e\bigg(\frac{h{\mathrm{rev}}_{L}(n)}{(q,g^{L}(g^{2}-1))}\bigg)\\ &= \frac{(q,g^{L}(g^{2}-1))}{q} \overleftarrow{\mkern4.8mu\psi}\mkern-.6mu_{\sharp,L}(x,a,q). \end{aligned} \end{align} $$

For the sum $S_{\mathfrak {m}}$ , we have

(8.11) $$ \begin{align} \lvert S_{\mathfrak{m}}\rvert \le \max_{\substack{ 0\le h<q\\ q\nmid g^{L}(g^{2}-1)h }} \bigg\lvert \sum_{n\le x} \Lambda(n) e\bigg(\frac{h{\mathrm{rev}}_{L}(n)}{q}\bigg) \bigg\rvert. \end{align} $$

We then use Theorem 7.1 with $\boldsymbol {\alpha }_{L}=(\alpha _{L,i})\in \mathscr {A}_{g}$ given by

$$\begin{align*}\alpha_{L,i}(n) := \alpha ng^{L-i-1} \quad\text{with}\quad \alpha := \frac{h}{q}. \end{align*}$$

This $\boldsymbol {\alpha }_{L}$ gives

$$\begin{align*}f_{L,\boldsymbol{\alpha}_{L}}(n) = \frac{h}{q}\sum_{0\le i<L}\varepsilon_{i}(n)g^{L-i-1} = \frac{h{\mathrm{rev}}_{L}(n)}{q}. \end{align*}$$

Also, since $q\nmid g^{L}(g^{2}-1)h$ in $S_{\mathfrak {m}}$ , we have

$$\begin{align*}\min_{0\le i\le L}\bigg\|g^{i}(g^{2}-1)\cdot\frac{h}{q}\bigg\| \ge \frac{1}{q} \end{align*}$$

for the quantity $\sigma $ defined by (8.1). Thus, by Lemma 8.2, $\kappa $ in Theorem 7.1 satisfies

$$ \begin{align*} \kappa = \frac{1}{10}\sigma_{\xi}(\boldsymbol{\alpha}_{L}) \gg \frac{\xi}{\log\frac{1}{\sigma}}+O(1) \gg \frac{\log x}{\log q}+O(1), \quad\text{where}\quad \xi:=\bigg[\frac{1}{4}\frac{\log x}{\log g}\bigg]. \end{align*} $$

Applying Theorem 7.1 to (8.11), we obtain

(8.12) $$ \begin{align} S_{\mathfrak{m}} \ll x(\log x)^{4}\exp\bigg(-5c\cdot\frac{\log x}{\log q}\bigg). \end{align} $$

Under the condition (8.8), we have

(8.13) $$ \begin{align} (\log x)^{4} = \exp(4\log\log x) \le \exp\bigg(4c\cdot\frac{\log x}{\log q}\bigg). \end{align} $$

On inserting this estimate into (8.12), we obtain

(8.14) $$ \begin{align} S_{\mathfrak{m}} \ll x\exp\bigg(-c\cdot\frac{\log x}{\log(q+1)}\bigg). \end{align} $$

On inserting (8.10) and (8.14) into (8.9), we obtain (8.5).

We next deduce (8.6) from (8.5). In (8.5), we may assume $c\in (0,\frac {\log 2}{2})$ to assure

$$\begin{align*}x\exp\bigg(-c\cdot\frac{\log x}{\log(q+1)}\bigg) \ge x^{\frac{1}{2}}. \end{align*}$$

We can then use

$$\begin{align*}\sum_{\substack{ p^{v}\le x\\ v\ge 2 }} \log p \ll x^{\frac{1}{2}} \end{align*}$$

in (8.5) to get (8.6).

We finally deduce (8.7) from (8.6). We first change the value of $c$ to replace it in (8.6) and the associated (8.8) by $4c$ . (We however use the same $c$ for (8.8) associated with (8.7).) We may also assume that $c\in (0,\frac {\log 2}{8})$ . Then, for $x^{\frac {1}{2}}\le u\le x$ , we have $1\le u\le g^{L}$ and

$$\begin{align*}q \le \exp\bigg(c\cdot\frac{\log x}{\log\log x}\bigg) \le \exp\bigg(4c\cdot\frac{\log u}{\log\log u}\bigg). \end{align*}$$

Thus, we can apply (8.6) with $x$ replaced by $u$ to get

$$\begin{align*}\overleftarrow{\mkern4.8mu\vartheta}\mkern-.6mu_{L}(u,a,q) = \frac{(q,g^{L}(g^{2}-1))}{q} \overleftarrow{\mkern4.8mu\vartheta}\mkern-.6mu_{\sharp,L}(u,a,q) + O\bigg(x\exp\bigg(-c\cdot\frac{\log x}{\log(q+1)}\bigg)\bigg) \end{align*}$$

for $1\le u\le x$ since this is trivial if $u\le x^{\frac {1}{2}}$ . We can then use partial summation to deduce (8.7).

Proof. We may assume that $x$ is large in terms of $g$ and $q\ge 2$ since otherwise the assertion is trivial. Let $\widetilde {c}$ be the constant $c$ of Theorem 8.1 and let $c:= \frac {\widetilde {c}}{5}$ . Since

(8.16) $$ \begin{align} g^{\ell-1}\le n<g^{\ell} \implies {\mathrm{rev}}_{\ell}(n)={\mathrm{rev}}(n) \end{align} $$

for any $\ell \in \mathbb {N}$ , we have

(8.17) $$ \begin{align} \overleftarrow{\mkern4.8mu\pi}(u,a,q)-\overleftarrow{\mkern4.8mu\pi}(g^{\ell-1}-1,a,q) = \overleftarrow{\mkern4.8mu\pi}\mkern-.6mu_{\ell}(u,a,q)-\overleftarrow{\mkern4.8mu\pi}\mkern-.6mu_{\ell}(g^{\ell-1}-1,a,q) \end{align} $$

for $g^{\ell -1}\le u<g^{\ell }$ . For $x^{\frac {1}{2}}\le g^{\ell -1}\le u<g^{\ell }$ , we have

$$\begin{align*}q \le \exp\bigg(c\cdot\frac{\log x}{\log\log x}\bigg) \le \exp\bigg(\widetilde{c}\cdot\frac{\log u}{\log\log u}\bigg). \end{align*}$$

Thus, we can apply (8.7) of Theorem 8.1 to (8.17) and use (8.16) again to get

(8.18) $$ \begin{align} \begin{aligned} &\overleftarrow{\mkern4.8mu\pi}(u,a,q)-\overleftarrow{\mkern4.8mu\pi}(g^{\ell-1}-1,a,q)\\ &\quad= \frac{(q,g^{\ell}(g^{2}-1))}{q} \sum_{\substack{ g^{\ell-1}\le p\le u\\ {\mathrm{rev}}(p)\equiv a\ (\mathrm{mod}\ (q,g^{\ell}(g^{2}-1))) }} 1 + O\bigg(x\exp\bigg(-\widetilde{c}\cdot\frac{\log x}{\log q}\bigg)\bigg) \end{aligned} \end{align} $$

for $g^{\ell -1}\le u<g^{\ell }$ with $x^{\frac {1}{2}}\le g^{\ell -1}$ and $g^{\ell }\le gx$ . By (8.15) and $\ell \gg \log x$ , we indeed have

$$\begin{align*}(q,g^{\ell}(g^{2}-1)) = (q,g^{L}(g^{2}-1)) \end{align*}$$

for all $\ell $ with $x^{\frac {1}{2}}\le g^{\ell -1}$ and $g^{\ell }\le gx$ . Thus, we can rewrite (8.18) by replacing $\ell $ by $L$ to get

(8.19) $$ \begin{align} \begin{aligned} &\overleftarrow{\mkern4.8mu\pi}(u,a,q)-\overleftarrow{\mkern4.8mu\pi}(g^{\ell-1}-1,a,q)\\ &\quad= \frac{(q,g^{L}(g^{2}-1))}{q} \sum_{\substack{ g^{\ell-1}\le p\le u\\ {\mathrm{rev}}(p)\equiv a\ (\mathrm{mod}\ (q,g^{L}(g^{2}-1))) }} 1 + O\bigg(x\exp\bigg(-\widetilde{c}\cdot\frac{\log x}{\log q}\bigg)\bigg) \end{aligned} \end{align} $$

for $g^{\ell -1}\le u<\min (g^{\ell },x)$ for any $\ell \in \mathbb {N}$ since this is trivial if $u\le x^{\frac {1}{2}}$ . Thus, by summing up (8.19) over $\ell $ and using the bound similar to (8.13), we obtain the theorem.