# Infinitude of palindromic almost-prime numbers

Aleksandr Tuxanidy † and  Daniel Panario  School of Mathematics and
Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, K1S
5B6, Canada<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

It is proven that, in any given base, there are infinitely many palindromic
numbers having at most six prime divisors, each relatively large. The work
involves equidistribution estimates for the palindromes in residue classes to
large moduli, offering upper bounds for moments and averages of certain
products closely related to exponential sums over palindromes.

† Corresponding author

###### Contents

  1. 0 Notation
  2. 1 Introduction
  3. 2 Acknowledgments
  4. 3 Paper structure
  5. 4 Technical lemmas
  6. 5 Exponential sums over $\mathscr{P}_{b}^{0}(x)$
  7. 6 Bounding moments of $\Phi_{N}$
  8. 7 Bounding the average
  9. 8 Equidistribution estimate
  10. 9 Palindromic almost-primes

##  0\. Notation

###  0.1. Literary notation

We use the asymptotic notations $X\ll Y$, $Y\gg X$, $X=O(Y)$, all signifying
here that $|X|\leq C|Y|$ for some unspecified constant $C>0$. The notation
$X\asymp Y$ is used to assert that both $X\ll Y$ and $Y\ll X$, simultaneously.
Dependence of the implied constants on parameters will be denoted by a
subscript. The symbol $o(X)$ denotes a quantity satisfying $o(X)/X\to 0$ as
$X\to\infty$.

The letters $\mu,\tau,\varphi$ denote the Möbius, divisor and Euler’s totient
functions, respectively. For an integer $n\geq 1$, the symbol $\Omega(n)$
denotes the total number of prime factors of $n$, counting their multiplicity.
The symbol $P^{-}(n)$ denotes the smallest prime factor of $n$. The letter $p$
is reserved to denote a prime number and $b$ denotes an integer larger than
$1$.

The notation $n\equiv a(q)$ denotes the assertion that $n$ is congruent to $a$
modulo $q$. We use $d\mid n$ to assert that $d$ divides $n$, and $(m,n)$ to
represent the greatest common divisor of $m$ and $n$. If $(m,n)=1$, we use the
notation $\text{ord}_{m}(n)$ for the multiplicative order of $n$ modulo $m$.

The symbol

$\sum_{a(q)}$

denotes a summation over all the residue classes $a$ modulo $q$, whereas

$\sum_{a(q)}^{*}$

denotes a sum over the invertible residue classes $a$ modulo $q$.

Given a function $f:\mathbb{R}\to\mathbb{C}$, we denote by $\|f\|_{1}$ its
$L^{1}$-norm and by $\|f\|_{\infty}$ its $L^{\infty}$-norm (whenever these
exist).

For a real number $x$ and an integer $q\geq 1$, we use the notation
$e(x):=e^{2\pi ix}$ for the complex exponential, $e_{q}(x):=e(x/q)$ for the
additive character modulo $q$ and $\exp(x):=e^{x}$ for the exponential. If
$x>0$, its natural logarithm is denoted by $\log x$ and its base-$b$ logarithm
by $\log_{b}x$.

We use $\|x\|$ to symbolize the distance from $x$ to its nearest integer; that
is, $\|x\|:=\min_{k\in\mathbb{Z}}|x-k|$. Moreover $\lfloor x\rfloor$ denotes
the floor of $x$ and $\\{x\\}:=x-\lfloor x\rfloor$ denotes its fractional
part.

Given a statement $E$, we use $\mathbf{1}_{E}$ to symbolize the indicator
function of $E$; that is, $\mathbf{1}_{E}=1$ if $E$ is true and
$\mathbf{1}_{E}=0$ if $E$ is false. For example, $\mathbf{1}_{n\equiv a(q)}$
equals $1$ if $n\equiv a(q)$ and is zero otherwise.

Given real numbers $\alpha_{1},\ldots,\alpha_{N}$, their discrepancy
$D_{N}(\alpha_{1},\ldots,\alpha_{N})$ is defined by

(1) $D_{N}(\alpha_{1},\ldots,\alpha_{N}):=\sup_{0\leq c\leq d\leq
1}\left|\dfrac{\\#\left\\{1\leq n\leq N\ :\
c\leq\\{\alpha_{n}\\}<d\right\\}}{N}-(d-c)\right|$

and their star-discrepancy $D_{N}^{*}(\alpha_{1},\ldots,\alpha_{N})$ is
defined as

(2) $D_{N}^{*}(\alpha_{1},\ldots,\alpha_{N}):=\sup_{0\leq d\leq
1}\left|\dfrac{\\#\left\\{1\leq n\leq N\ :\
\\{\alpha_{n}\\}<d\right\\}}{N}-d\right|.$

###  0.2. Non-standard notation

Let $b\geq 2$ be an integer. The notation $\mathscr{P}_{b}$ symbolizes the set
of all positive $b$-palindromic integers. We define the sets
$\mathscr{P}_{b}^{0},\mathscr{P}_{b}^{*}$, as follows:

(3) $\displaystyle\mathscr{P}_{b}^{0}$
$\displaystyle:=\left\\{n\in\mathscr{P}_{b}\ :\
\lfloor\log_{b}(n)\rfloor\equiv 0(2)\right\\},$ (4)
$\displaystyle\mathscr{P}_{b}^{*}$
$\displaystyle:=\left\\{n\in\mathscr{P}_{b}\ :\ (n,b^{3}-b)=1\right\\}.$

From the definition above one observes that $\mathscr{P}_{b}^{0}$ is comprised
exactly of all positive $b$-palindromes with an odd number of digits (in their
$b$-adic expansion). Since every $b$-palindrome with an even number of digits
is divisible by $b+1$, and $b+1$ is a divisor of $b^{3}-b$, it follows
$\mathscr{P}_{b}^{*}\subset\mathscr{P}_{b}^{0}$. In fact

$\displaystyle\mathscr{P}_{b}^{0}$
$\displaystyle=\bigcup_{N=0}^{\infty}\Pi_{b}(2N),$
$\displaystyle\mathscr{P}_{b}^{*}$
$\displaystyle=\bigcup_{N=0}^{\infty}\Pi_{b}^{*}(2N),$

where for an integer $N\geq 0$,

(5) $\displaystyle\Pi_{b}(N)$
$\displaystyle:=\mathscr{P}_{b}\cap\left[b^{N},b^{N+1}\right),$ (6)
$\displaystyle\Pi_{b}^{*}(N)$ $\displaystyle:=\left\\{n\in\Pi_{b}(N)\ :\
(n,b^{3}-b)=1\right\\}.$

Given a set $\mathscr{A}$ of integers, a real number $x$ and integers $a,q$,
we define the sets

$\displaystyle\mathscr{A}(x)$
$\displaystyle:=\mathscr{A}\cap\left\\{n\in\mathbb{Z}\ :\ n\leq x\right\\},$
$\displaystyle\mathscr{A}(x,a,q)$ $\displaystyle:=\left\\{n\in\mathscr{A}(x)\
:\ n\equiv a(q)\right\\}.$

Thus for instance

(7) $\displaystyle\mathscr{P}_{b}^{*}(x)$
$\displaystyle:=\mathscr{P}_{b}^{*}\cap[1,x],$ (8)
$\displaystyle\mathscr{P}_{b}^{*}(x,a,q)$
$\displaystyle:=\left\\{n\in\mathscr{P}_{b}^{*}(x)\ :\ n\equiv a(q)\right\\},$

with our notation.

Given a real number $\alpha$ and an integer $N\geq 0$, we define

(9) $\phi_{b}(\alpha):=\left|\sum_{0\leq m<b}e(\alpha m)\right|$

and

(10) $\Phi_{N}(\alpha):=\prod_{1\leq
n<N}\phi_{b}\left(\alpha\left(b^{n}+b^{2N-n}\right)\right)$

with the convention $\Phi_{N}(\alpha)=1$ for $N\leq 1$. The definition of
$\Phi_{N}$ also depends on $b$ but for the sake of brevity we omit it on the
left hand side above.

Finally given integers $n,K,b$ with $K,b\geq 2$, we let

(11)
$r(n;K,b):=\left\\{(m_{1},\ldots,m_{K})\in\left([0,b)\cap\mathbb{Z}\right)^{K}\
:\ m_{1}+\cdots+m_{K}=n\right\\}$

be the number of additive compositions of $n$ into $K$ integers $m_{j}$, each
satisfying $0\leq m_{j}<b$.

##  1\. Introduction

###  1.1. Tattarrattat

Generally speaking, a palindrome is a finite sequence of objects which reads
the same forwards as backwards. Any such sequence is said to be palindromic.
For example the sequence of the (decimal) digits of the prime number

$9609457639843489367549069$

is a palindrome. According to [29] (see also [15]) it is the largest known
palindromic prime appearing in the decimal expansion of the digits of $\pi$.

One of the earliest historical palindromic objects, a SATOR square, was found
in the remains of the ancient city of Pompeii (see for instance [28])
destroyed in the year 79 AD after the eruption of Mount Vesuvius. Palindromes
appear in several facets of human endeavor, for instance in music (e.g. Joseph
Haydn’s Symphony No. 47, “The Palindrome”) in literature (e.g. Georges Perec’s
“Le Grand Palindrome”). In recent decades, palindromes are studied intensively
in various areas of research [2, 3, 4, 7, 8, 9, 12, 13, 16, 26, 27]. They also
appear in nature; for example, large portions of the human X and Y chromosomes
are palindromic (in a slightly different sense; see [21]).

###  1.2. Conjecture and previous work

On the topic of palindromic numbers, perhaps one of the most difficult
unsolved problems is the following conjecture (see for instance the concluding
remarks in [3, 4]). First from here on out, $b$ denotes an integer larger than
$1$. One says that a natural number is $b$-palindromic, or is a
$b$-palindrome, if the sequence of its $b$-adic digits is palindromic. For a
real number $x>0$, we let $\mathscr{P}_{b}(x)$ be the set of all positive
$b$-palindromic integers at most $x$ in size.

######  Conjecture 1.1.

Let $b\geq 2$ be an integer. Then there are infinitely many prime numbers that
are $b$-palindromic. In fact

$\\#\left\\{p\in\mathscr{P}_{b}(x)\right\\}\asymp_{b}\dfrac{\\#\mathscr{P}_{b}(x)}{\log
x}$

for $x$ large.

Conjecture 1.1 seems far out of reach with current methods. As pointed out by
Banks-Shparlinski [4], one of the main difficulties stems from the large
sparsity of $b$-palindromic numbers, hindering the efficacy of analytic
methods. The sparsity of these is, in essence, as large as that of numbers
with form $n^{2}+1$. However Landau’s problem (posed in the year 1912) of
whether or not there are infinitely many such primes, remains unsolved. On the
other hand, Iwaniec [18] proved there are infinitely many integers $n$ such
that $n^{2}+1$ is the product of at most two primes. In view of recent results
(see the discussion below and the following subsection) we believe that
proving the analogous result, for $b$-palindromes, may be feasible over the
upcoming years.

Some progress was made in the direction of Conjecture 1.1. In the year 2004,
Banks-Hart-Sakata [3] showed that for $x$ large enough,

(12) $\\#\left\\{p\in\mathscr{P}_{b}(x)\right\\}\ll_{b}\dfrac{\log\log\log
x}{\log\log x}\\#\mathscr{P}_{b}(x).$

In 2009, Col [8] improved this to the expected

(13)
$\\#\left\\{p\in\mathscr{P}_{b}(x)\right\\}\ll_{b}\dfrac{\\#\mathscr{P}_{b}(x)}{\log
x}.$

Col also obtained (see Theorem 1.2 below) a lower bound for the amount of
$b$-palindromic almost-primes, when the number of prime divisors is bounded
above by a certain value depending only on $b$. This was the first, and up to
now unique, result of its kind.

######  Theorem 1.2 (Col [8], Corollary 2).

We have

$\\#\left\\{n\in\mathscr{P}_{b}(x)\ :\ \Omega(n)\leq
k_{b}\right\\}\gg_{b}\dfrac{\\#\mathscr{P}_{b}(x)}{\log x}$

for some value $k_{b}>0$ depending only on $b$ and satisfying $k_{b}\sim 24\pi
b$ as $b\to\infty$. In particular $k_{2}=60$ and $k_{10}=372$.

Theorem 1.2 was a consequence of Col’s equidistribution estimate (see Theorem
1.3 below) for $b$-palindromes in residue classes to large moduli, combined
with well-established facts from sieve theory. First recall the notation

$\mathscr{P}_{b}(x,a,q):=\left\\{n\in\mathscr{P}_{b}(x)\ :\ n\equiv
a(q)\right\\}.$

######  Theorem 1.3 (Col [8], Theorem 2).

There exists some value $\beta>0$, depending only on $b$, such that for any
$\epsilon,A>0$,

$\sum_{\begin{subarray}{c}q\leq x^{\beta-\epsilon}\\\
(q,b^{3}-b)=1\end{subarray}}\sup_{y\leq
x}\max_{a\in\mathbb{Z}}\left|\\#\mathscr{P}_{b}(y,a,q)-\dfrac{\\#\mathscr{P}_{b}(x)}{q}\right|\ll_{\epsilon,A,b}\dfrac{\\#\mathscr{P}_{b}(x)}{\log^{A}x}.$

For $b$ large, we may take $\beta\sim 1/6\pi b$. Setting
$\beta_{b}=\beta-\epsilon$, the inequality above holds for the following
particular values.

$b$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$
---|---|---|---|---|---|---|---|---|---
$\beta_{b}$ | $1/30$ | $1/94$ | $1/74$ | $1/122$ | $1/114$ | $1/158$ | $1/150$ | $1/194$ | $1/186$

Theorem 1.3 (see also Proposition 5.2 here) considerably improved over
previous estimates of Banks-Hart-Sakata [3] valid for $\beta\ll(\log\log
x)/\log x$ with the implied constant small enough (see Corollary 4.5 in [3]).

###  1.3. Statement of results

In the present work we obtain the following improved versions of Theorems 1.2
and 1.3.

######  Theorem 1.4.

Let $b\geq 2$ be an integer. Then for $x\gg_{b}1$ large enough,

$\\#\left\\{n\in\mathscr{P}_{b}(x)\ :\ \Omega(n)\leq 6,\ P^{-}(n)\geq
x^{1/21}\right\\}\asymp_{b}\dfrac{\\#\mathscr{P}_{b}(x)}{\log x}.$

Theorem 1.4 is a consequence of Theorem 1.5 below and machinery from sieve
theory (see Lemma 9.1 for the latter). Here $\mathscr{P}_{b}^{*}(x)$ and
$\mathscr{P}_{b}^{*}(x,a,q)$ are defined as in (7), (8), respectively.

######  Theorem 1.5.

Let $b\geq 2$ be an integer and let $x\geq 1$. Then for any $\epsilon>0$,

(14) $\sum_{\begin{subarray}{c}q\leq x^{1/5-\epsilon}\\\
(q,b^{3}-b)=1\end{subarray}}\sup_{y\leq
x}\max_{a\in\mathbb{Z}}\left|\\#\mathscr{P}^{*}_{b}(y,a,q)-\dfrac{\\#\mathscr{P}^{*}_{b}(y)}{q}\right|\ll_{b,\epsilon}\dfrac{\\#\mathscr{P}_{b}^{*}(x)}{e^{\sigma(b,\epsilon)\sqrt{\log
x}}},$

where $\sigma(b,\epsilon)>0$ is some value depending only on $b$ and
$\epsilon$.

Let us now discuss some of the main ingredients in the proof of Theorem 1.5.

###  1.4. Setup

For the sake of brevity we denote by $E$ the left hand side of the inequality
in Theorem 1.5. Let $\mathscr{P}_{b}^{0}$, $\mathscr{P}_{b}^{*}$ be defined as
in (3), (4), respectively. Set
$\mathscr{P}_{b}^{0}(x):=\mathscr{P}_{b}^{0}\cap[1,x]$. From the observation
$\mathscr{P}_{b}^{*}=\left\\{n\in\mathscr{P}_{b}^{0}\ :\
(n,b^{3}-b)=1\right\\}$, the Möbius inversion formula

$\mathbf{1}_{(n,b^{3}-b)=1}=\sum_{r\mid(n,b^{3}-b)}\mu(r),$

the Fourier expansions

$\mathbf{1}_{r\mid n}=\dfrac{1}{r}\sum_{k(r)}e_{r}(nk)$

and

(15) $\mathbf{1}_{n\equiv a(q)}=\dfrac{1}{q}\sum_{h(q)}e_{q}(-ah)e_{q}(nh),$

one derives

$E\ll\tau(b^{3}-b)(\log x)\max_{k\in\mathbb{Z}}\sum_{\begin{subarray}{c}2\leq
q\leq x^{1/5-\epsilon}\\\
(q,b^{3}-b)=1\end{subarray}}\dfrac{1}{q}\sum_{h(q)}^{*}\sup_{\begin{subarray}{c}y\leq
x\end{subarray}}\left|\sum_{n\in\mathscr{P}_{b}^{0}(y)}e\left(\dfrac{hn}{q}+\dfrac{kn}{b^{3}-b}\right)\right|.$

The use of the decomposition in (15) is rather typical in the literature and
it will shortly lead to qualitative gains in multiplicative algebraic
structures, with the appearance of the products $\Phi_{N}$ defined in (10).
Unfortunately we pay the price of a quantitative loss of roughly
$x^{1/5-\epsilon}$ in the trivial bound. Thus in order for such a Fourier-type
approach to succeed, we must not only be able to recover the lost
$x^{1/5-\epsilon}$, but gain much more (in fact gain an extra
$\exp(\sigma\sqrt{\log x})$).

From the works of Banks-Hart-Sakata [3] and Col [8] (see Lemma 5.1 here) the
inner sum admits a decomposition into linear combinations of the products
$\Phi_{N}$ with $0\leq N\leq\frac{1}{2}\log_{b}x$. After a dyadic subdivision
of the interval $2\leq q\leq x^{1/5-\epsilon}$, the problem of bounding $E$
then boils down to bounding averages of the form

$S=\sum_{\begin{subarray}{c}2\leq q\leq Q\\\
(q,b^{3}-b)=1\end{subarray}}\sum_{h(q)}^{*}\Phi_{N}\left(\dfrac{h}{q}+\dfrac{k}{b^{3}-b}\right)$

for $Q\ll x^{1/5-\epsilon}$. The trivial bound gives $S\leq Q^{2}b^{N}\leq
Q^{2}\sqrt{x}$ and our job is to beat this by much more than a factor of $Q$.

Thanks to the work of Col [8] (see Proposition 5.2 here) we can readily
dispose of the cases with $Q$ relatively small, say $Q\ll\exp(c\sqrt{\log
x})$. We are thus left with considering $S$, or more strongly the average

(16) $T=\sum_{\begin{subarray}{c}q\leq Q\\\
(q,b)=1\end{subarray}}\sum_{h(q)}^{*}\Phi_{N}\left(\dfrac{h}{q}+\beta\right),$

for $\exp(c\sqrt{\log x})\ll Q\ll x^{1/5-\epsilon}$ and $\beta\in\mathbb{R}$.

As a first rough thought, one could envision splitting the product $\Phi_{N}$
into two products, one over $1\leq n\leq M$ and the other over $M<n<N$,
applying Cauchy-Schwarz and end up considering averages of squares (just as
Bombieri-Vinogradov’s treatment of the Type II sums). These could be attacked
say via direct arguments (see for instance Lemma 7.2) or the large sieve
inequality (see Lemma 1.6 below). The direct arguments (namely that of
expanding the square, switching orders of summation, using the orthogonality
of the additive characters and bounding the resulting sums trivially) can at
best aid in recovering a $Q$ from the trivial bound, and are thus
insufficient. This brings us to the large sieve inequality.

###  1.5. Large sieve

First given a real number $0<\delta\leq 1/2$, one says that a set of points
$\alpha_{1},\ldots,\alpha_{R}\in\mathbb{R}/\mathbb{Z}$ is $\delta$-spaced if
$\|\alpha_{r}-\alpha_{s}\|\geq\delta$ whenever $r\neq s$.

######  Lemma 1.6 (Large sieve inequality).

For any set of $\delta$-spaced points
$\alpha_{1},\ldots,\alpha_{R}\in\mathbb{R}/\mathbb{Z}$ and any complex numbers
$a_{n}$ with $M<n\leq M+N$, where $0<\delta\leq 1/2$ and $N\geq 1$ is an
integer, we have

(17) $\sum_{r=1}^{R}\left|\sum_{M<n\leq
M+N}a_{n}e(\alpha_{r}n)\right|^{2}\leq\left(\delta^{-1}+N-1\right)\sum_{M<n\leq
M+N}|a_{n}|^{2}.$

###### Proof.

See for instance Theorem 7.7 in [19]. ∎

The large sieve inequality is a powerful and useful tool for tackling averages
of exponential sums and has enjoyed several applications in the literature
(see for instance [11, 19, 23, 24, 31] to name a few). Unfortunately the
quality of the bounds it offers highly depends on the density
$\eta=\\#\mathcal{S}/N$ of the set $\mathcal{S}\subseteq(M,M+N]$ in which the
sequence $(a_{n})$ is supported on, with better bounds for denser
$\mathcal{S}$ and worse bounds for sparser $\mathcal{S}$. For example in the
case when each $a_{n}\ll 1$ and $R\asymp Q^{2}\asymp\delta^{-1}\asymp N$, the
large sieve inequality beats the trivial bound by a factor of
$\\#\mathcal{S}=\eta N\asymp Q\eta\sqrt{N}$. In particular in order for the
large sieve to beat the trivial bound by much more than $Q$ (which is what we
seek) one needs $\eta$ to be much larger than $1/\sqrt{N}$. Unfortunately
sparse sets such as, say, the $b$-palindromes or close relatives, have density
$\ll 1/\sqrt{N}$ on $(M,M+N]$. For sequences supported on such sets, direct
use of the large sieve proves insufficient.

An important idea for the case of the sparse sequences is to consider instead
larger moments such as

$\sum_{r=1}^{R}\left|\sum_{M<n\leq M+N}a_{n}e(\alpha_{r}n)\right|^{2K}$

for some integer $K\geq 2$; see for example [19]. One may arrive at these from
smaller moments in a variety of ways, say via Hölder’s inequality. To explain
the concept, note we may write

$\left(\sum_{M<n\leq M+N}a_{n}e(\alpha_{r}n)\right)^{K}=\sum_{KM<n\leq
K(M+N)}b_{n}e(\alpha_{r}n),$

where the coefficients $b_{n}$ are now supported on the set $K\mathcal{S}$
comprised of the additions of any $K$ elements from $\mathcal{S}$. If the set
$\mathcal{S}$ is sufficiently dissociated additively, then $K\mathcal{S}$ is
much denser in $(KM,K(M+N)]$. In this case we can make a more effective use of
the large sieve.

###  1.6. Approach

Let us now return to (16). Motivated by the discussion above, we split the
product $\Phi_{N}$ into three pieces as $\Phi_{N}=P_{1}P_{2}P_{3}$, where
$P_{1}$ is the product over $1\leq n\leq M$, $P_{2}$ is the product over
$M<n\leq 2M$ and $P_{3}$ is the product over $2M<n<N$ (actually this is our
approach for the case when $Q\gg b^{(\frac{2}{5}-\epsilon_{0})N}$; the case
$Q\ll b^{(\frac{2}{5}-\epsilon_{0})N}$ is treated in a slightly different
way). The choice of $M$ is optimized later. Applying Hölder’s inequality with
the triple $(\ell,\ell,2K)$ (where $K\geq 2$ is an integer to be chosen later
and $\ell>2$ is such that $2/\ell+1/2K=1$) one obtains

$T\leq\left(\sum_{\begin{subarray}{c}q\leq Q\\\
(q,b)=1\end{subarray}}\sum_{h(q)}^{*}P_{1}^{\ell}\right)^{1/\ell}\left(\sum_{\begin{subarray}{c}q\leq
Q\\\
(q,b)=1\end{subarray}}\sum_{h(q)}^{*}P_{2}^{\ell}\right)^{1/\ell}\left(\sum_{\begin{subarray}{c}q\leq
Q\\\ (q,b)=1\end{subarray}}\sum_{h(q)}^{*}P_{3}^{2K}\right)^{1/2K}.$

For $K$ somewhat large (although bounded in terms of some parameters for our
purposes) $\ell$ is close to $2$. The first two sums corresponding to
$P_{1},P_{2}$ are then treated by us in direct fashion (as in Lemma 7.2). Here
we avoid using the large sieve which, given the sparsity of the coefficient
sequences corresponding to $P_{1},P_{2}$, gives no significant gains over the
direct approach.

There is a reason why we have chosen to raise $P_{3}$ to the $2K$-th power and
not $P_{1}$ nor $P_{2}$, namely, the following algebraic identity

$\sum_{\begin{subarray}{c}q\leq Q\\\
(q,b)=1\end{subarray}}\sum_{h(q)}^{*}P_{3}^{2K}=\sum_{\begin{subarray}{c}q\leq
Q\\\
(q,b)=1\end{subarray}}\sum_{h(q)}^{*}\Phi_{N-2M}^{2K}\left(\dfrac{h}{q}+\beta
b^{2M}\right).$

The trivial bound shows the above is at most $Q^{2}b^{2K(N-2M)}\leq
Q^{2}x^{K(1-\frac{2M}{N})}$ and our main goal then boils down to beating this
by much more than $Q$ for certain suitable choices of $M,K$. This is
accomplished via Proposition 6.1 giving upper bounds for moments of $\Phi_{N}$
for any $N\geq 1$. Its proof relies partly on the large sieve.

##  2\. Acknowledgments

We would like to express our gratitude to Qiang Wang for useful advices and to
Igor E. Shparlinski for notifying us of Col’s work [8]. D. Panario was funded
by the Natural Science and Engineering Research Council of Canada (NSERC),
reference number RPGIN-2018-05328.

##  3\. Paper structure

The rest of the work goes as follows. In Section 4 we compile several
technical tools needed in the following two sections. In Section 5 we discuss
the current (but limited) state of knowledge on exponential sums over
palindromes, as well as slightly add to the literature via Proposition 5.5 and
Corollary 5.6 there. These are applications of Bourgain’s bound in [5]. In
Section 6 we prove Proposition 6.1 giving an upper bound for moments of
$\Phi_{N}$. In Section 7 we prove Proposition 7.1 bounding an average of
$\Phi_{N}$. In Section 8 we prove Theorem 1.5 giving average equidistribution
estimates for palindromes in residue classes. We then conclude the work in
Section 9 with a proof of Theorem 1.4.

##  4\. Technical lemmas

In this section we go over several technical tools needed in the following two
sections. The first two are classical in the theory of uniform distribution of
sequences modulo $1$.

######  Lemma 4.1 (Koksma-Hlawka).

Suppose $f:[0,1]\to\mathbb{R}$ is a bounded integrable function of bounded
variation $V(f)$. Then for any real numbers $\alpha_{1},\ldots,\alpha_{N}$
with $N\geq 1$ an integer,

$\left|\dfrac{1}{N}\sum_{n=1}^{N}f(\\{\alpha_{n}\\})-\int_{0}^{1}f(x)dx\right|\leq
V(f)D_{N}^{*}(\alpha_{1},\ldots,\alpha_{N}),$

where $D_{N}^{*}(\alpha_{1},\ldots,\alpha_{N})$ is their star-discrepancy as
defined in (2).

###### Proof.

See [20]. ∎

######  Lemma 4.2 (Erdős-Turán).

Let $\alpha_{1},\ldots,\alpha_{N}$ be real numbers with $N\geq 1$ an integer.
Then

$D_{N}(\alpha_{1},\ldots,\alpha_{N})\ll\dfrac{1}{H}+\sum_{1\leq h\leq
H}\dfrac{1}{h}\left|\dfrac{1}{N}\sum_{n=1}^{N}e(h\alpha_{n})\right|$

for any $H\geq 1$, where $D_{N}(\alpha_{1},\ldots,\alpha_{N})$ is the
discrepancy defined in (1).

###### Proof.

See [20]. ∎

######  Lemma 4.3 (Smooth exponential sum bounds).

Let $f:\mathbb{R}\to\mathbb{C}$ be a smooth compactly supported function and
let $\alpha$ be a real number. Then

(18) $\left|\sum_{n\in\mathbb{Z}}f(n)e(\alpha
n)\right|\leq\|f\|_{1}+\dfrac{\|f^{\prime}\|_{1}}{2}$

and

(19) $\left|\sum_{n\in\mathbb{Z}}f(n)e(\alpha
n)\right|\leq\dfrac{\|f^{(k)}\|_{1}}{|2\sin(\pi\alpha)|^{k}}$

for all natural numbers $k\geq 1$.

###### Proof.

See for instance Lemma 3.1 in [30]. ∎

The following lemma appears, either implicitly or explicitly, on several works
on digital functions. See for instance [6, 8, 23, 24, 25]. We give a proof for
the convenience of the reader.

######  Lemma 4.4 (Ergodic-type integral bound).

Let $f:\mathbb{R}\to\mathbb{R}_{0}^{+}$ be a bounded integrable $1$-periodic
function. Then for any integer $N\geq 1$,

$\int_{0}^{1}\prod_{0\leq n<N}f(\alpha
b^{n})d\alpha\leq\left(\sup_{0\leq\theta\leq
1}\dfrac{1}{b}\sum_{n(b)}f\left(\dfrac{n+\theta}{b}\right)\right)^{N}.$

###### Proof.

By induction on $N\geq 1$. For $N=1$, we have

$\int_{0}^{1}f(\alpha)d\alpha=\dfrac{1}{b}\sum_{0\leq
h<b}\int_{0}^{1}f\left(\dfrac{h+\theta}{b}\right)d\theta$

and the claim follows. Suppose now that the claim holds for some $N\geq 1$. We
have

$\displaystyle\int_{0}^{1}\prod_{0\leq n<N+1}f(\alpha b^{n})d\alpha$
$\displaystyle=\dfrac{1}{b}\sum_{0\leq h<b}\int_{0}^{1}\prod_{0\leq
n<N+1}f\left(\left(\dfrac{h+\theta}{b}\right)b^{n}\right)d\theta$
$\displaystyle=\int_{0}^{1}\dfrac{1}{b}\sum_{0\leq
h<b}f\left(\dfrac{h+\theta}{b}\right)\prod_{0\leq n<N}f\left(\theta
b^{n}\right)d\theta.$

The last equality holds since $f$ is $1$-periodic by assumption. The above is

$\leq\sup_{0\leq\theta\leq 1}\dfrac{1}{b}\sum_{0\leq
h<b}f\left(\dfrac{h+\theta}{b}\right)\int_{0}^{1}\prod_{0\leq
n<N}f\left(\alpha b^{n}\right)d\alpha$

and the claim for $N+1$ now follows from the inductive hypothesis. ∎

The following lemma gives asymptotics for the number of compositions with some
restrictions. We were unable to obtain a reference in the literature and we
thus give a proof. If one allows the error term to depend on $n$, one should
be able to considerably improve it with a more detailed analysis of the
integrals involved. Nevertheless the error term here suffices for our
purposes.

######  Lemma 4.5 (Compositions with restrictions).

Let $n,K,b$ be integers with $K,b\geq 2$ and let $r(n;K,b)$ be as defined in
(11). We have

$\dfrac{r(n;K,b)}{b^{K}}=\sqrt{\dfrac{6}{\pi(b^{2}-1)K}}\exp\left(-\dfrac{6}{(b^{2}-1)K}\left(n-\dfrac{(b-1)K}{2}\right)^{2}\right)+O\left(\dfrac{1}{bK^{3/2}}\right).$

###### Proof.

An application of the identity

(20) $\mathbf{1}_{\ell=0}=\int_{-1/2}^{1/2}e(\ell\alpha)d\alpha$

valid for integers $\ell$, yields

$r(n;K,b)=\int_{-1/2}^{1/2}e(-\alpha n)\left(\sum_{0\leq m<b}e(\alpha
m)\right)^{K}d\alpha.$

In what follows $\delta$ denotes a fixed real number satisfying
$1/2<\delta<1$. We allow implied constants to depend on $\delta$. To evaluate
the integral above we split it into two pieces, one over
$|\alpha|\leq\delta/b$ and the other over $\delta/b<|\alpha|\leq 1/2$. We
treat each separately.

When $\alpha\not\in\mathbb{Z}$, the sum inside the brackets above equals

$\dfrac{e(\alpha
b)-1}{e(\alpha)-1}=e\left(\dfrac{b-1}{2}\alpha\right)\dfrac{\sin(\pi\alpha
b)}{\sin(\pi\alpha)}.$

By Euler’s product formula,

$\dfrac{\sin(\pi\alpha
b)}{\sin(\pi\alpha)}=b\prod_{m=1}^{\infty}\left(1-\dfrac{\alpha^{2}b^{2}}{m^{2}}\right)\left(1-\dfrac{\alpha^{2}}{m^{2}}\right)^{-1}.$

If $|\alpha|<1/b$, the logarithm of the product over $m\geq 1$ equals

(21) $-\sum_{m\geq 1}\sum_{k\geq
1}\dfrac{(b^{2k}-1)\alpha^{2k}}{m^{2k}k}=-\sum_{k\geq
1}\dfrac{\zeta(2k)}{k}\left(b^{2k}-1\right)\alpha^{2k},$

where $\zeta$ is the Riemann zeta function. For $|\alpha|\leq\delta/b$, the
terms with $k\geq 2$ contribute $\ll\alpha^{4}b^{4}$ to the sum. Then it
follows

$\left(\dfrac{\sin(\pi\alpha
b)}{\sin(\pi\alpha)}\right)^{K}=b^{K}e^{-\zeta(2)(b^{2}-1)K\alpha^{2}}\left(1+O\left(\alpha^{4}b^{4}K\right)\right)$

for $0<|\alpha|\leq\delta/b$. Thus, after dividing by $b^{K}$,

$\displaystyle\dfrac{1}{b^{K}}\int_{-\delta/b}^{\delta/b}e(-\alpha
n)\left(\sum_{0\leq m<b}e(\alpha m)\right)^{K}d\alpha$
$\displaystyle=\int_{-\delta/b}^{\delta/b}e\left(\dfrac{b-1}{2}\alpha K-\alpha
n\right)e^{-\zeta(2)(b^{2}-1)K\alpha^{2}}\left(1+O\left(\alpha^{4}b^{4}K\right)\right)d\alpha$
$\displaystyle=\int_{\mathbb{R}}e\left(\dfrac{b-1}{2}\alpha K-\alpha
n\right)e^{-\zeta(2)(b^{2}-1)K\alpha^{2}}d\alpha$
$\displaystyle\qquad+O\left(b^{4}K\int_{\mathbb{R}}e^{-\zeta(2)(b^{2}-1)K\alpha^{2}}\alpha^{4}d\alpha+\int_{\delta/b}^{\infty}e^{-\zeta(2)(b^{2}-1)K\alpha^{2}}d\alpha\right).$

The expression inside of the $O$-brackets can be shown to be $\ll
b^{-1}K^{-3/2}$ after substitutions of variables. By the well-known formula

$\int_{\mathbb{R}}e^{-at^{2}}e(-\theta
t)dt=\sqrt{\dfrac{\pi}{a}}e^{-\pi^{2}\theta^{2}/a}\hskip
20.00003pt(\theta\in\mathbb{R},\ a>0)$

for the Fourier transform of the Gaussian $e^{-at^{2}}$ and the fact
$\zeta(2)=\pi^{2}/6$, the integral outside of the $O$-brackets equals

$\sqrt{\dfrac{6}{\pi(b^{2}-1)K}}\exp\left(-\dfrac{6}{(b^{2}-1)K}\left(n-\dfrac{(b-1)K}{2}\right)^{2}\right).$

To conclude it suffices to show that

$\int_{\delta/b<|\alpha|\leq 1/2}e(-\alpha n)\left(\sum_{0\leq m<b}e(\alpha
m)\right)^{K}d\alpha\ll\dfrac{b^{K-1}}{K^{3/2}}.$

The sum inside the brackets is at most $|\csc(\pi\alpha)|\leq 1/2|\alpha|$
(for $|\alpha|\leq 1/2$) in absolute value. Then the absolute value of the
integral above is

$\leq
2^{1-K}\int_{\delta/b}^{1/2}\alpha^{-K}d\alpha\leq\dfrac{b^{K-1}}{(2\delta)^{K-1}(K-1)}\ll\dfrac{b^{K-1}}{K^{3/2}}$

for $\delta>1/2$ fixed. ∎

We also need some trigonometric facts involving the function $\phi_{b}$
defined as in (9). It will be useful to note that

$\phi_{b}(\alpha)=\begin{cases}b&\mbox{ if }\alpha\in\mathbb{Z},\\\
|\sin(\pi\alpha b)/\sin(\pi\alpha)|&\mbox{ otherwise.}\end{cases}$

Clearly $\phi_{b}$ is $1$-periodic and even; thus
$\phi_{b}(\alpha)=\phi_{b}(\\{\alpha\\})=\phi_{b}(\|\alpha\|)$ for any real
$\alpha$.

The following fact, but with $\|\alpha\|$ in the range $\|\alpha\|^{2}\leq
6/\pi^{2}(b^{2}-1)$, appears in [22] (see their Lemma 3).

######  Lemma 4.6.

If $\|\alpha\|\leq 1/b$, then

$\phi_{b}(\alpha)\leq
b\exp\left(-\dfrac{\pi^{2}}{6}(b^{2}-1)\|\alpha\|^{2}\right).$

###### Proof.

We have $\phi_{b}(0)=b$ and $\phi_{b}(1/b)=0$, whence the result holds for
$\|\alpha\|\in\\{0,1/b\\}$. For $0<\|\alpha\|<1/b$, the claim follows from
(21). ∎

######  Lemma 4.7.

If $\alpha$ and $0\leq\delta\leq 2/3b$ are real numbers with
$\|\alpha\|\geq\delta$, then $\phi_{b}(\alpha)\leq\phi_{b}(\delta)$.

###### Proof.

See Lemma 5 in [22]. ∎

######  Lemma 4.8.

Let $\alpha,\beta,\gamma$ be real numbers. Then either

$\left\|\alpha\left(b^{\beta}+b^{\gamma+1}\right)\right\|\geq\dfrac{\|\alpha(b^{2}-1)b^{\gamma}\|}{b+1}$

or

$\left\|\alpha\left(b^{\beta+1}+b^{\gamma}\right)\right\|\geq\dfrac{\|\alpha(b^{2}-1)b^{\gamma}\|}{b+1}$

(or both). Moreover

$\phi_{b}\left(\alpha\left(b^{\beta}+b^{\gamma+1}\right)\right)\phi_{b}\left(\alpha\left(b^{\beta+1}+b^{\gamma}\right)\right)\leq
b\phi_{b}\left(\dfrac{\|\alpha(b^{2}-1)b^{\gamma}\|}{b+1}\right).$

###### Proof.

We closely follow the argument in Lemma 6 of Mauduit-Rivat [22]. Making the
substitutions $u=\alpha(b^{\beta}+b^{\gamma+1})$ and
$\delta=\|\alpha(b^{2}-1)b^{\gamma}\|/(b+1)$, we need to show that either
$\|u\|\geq\delta$ or $\|bu-\alpha(b^{2}-1)b^{\gamma}\|\geq\delta$, and that

(22) $\phi_{b}(u)\phi_{b}(bu-\alpha(b^{2}-1)b^{\gamma})\leq
b\phi_{b}(\delta).$

Suppose $\|bu-\alpha(b^{2}-1)b^{\gamma}\|<\delta$. The triangle inequality
yields

$\displaystyle b\|u\|\geq\|bu\|$
$\displaystyle=\left\|bu-\alpha(b^{2}-1)b^{\gamma}+\alpha(b^{2}-1)b^{\gamma}\right\|$
$\displaystyle\geq\left\|\alpha(b^{2}-1)b^{\gamma}\right\|-\left\|bu-\alpha(b^{2}-1)b^{\gamma}\right\|$
$\displaystyle\geq(b+1)\delta-\delta=b\delta.$

Thus $\|u\|\geq\delta$. Consequently either $\|u\|\geq\delta$ or
$\|bu-\alpha(b^{2}-1)b^{\gamma}\|\geq\delta$, while (22) now follows from
Lemma 4.7. ∎

######  Lemma 4.9 (Weyl product bound).

There exists an absolute constant $A>0$ such that, for any real numbers
$\alpha_{1},\ldots,\alpha_{N}$ with $N\geq 1$ an integer,

$\prod_{1\leq n\leq
N}\phi_{b}(\alpha_{n})\leq\left(\dfrac{2}{D_{N}^{*}}\right)^{AbND_{N}^{*}},$

where $D_{N}^{*}=D_{N}^{*}(\alpha_{1},\ldots,\alpha_{N})$ is their star-
discrepancy as defined in (2).

###### Proof.

We adapt an argument of Aistleitner et al [1] (see the proof of Theorem 1
there). Let $0<\epsilon\leq 1/2b$ to be chosen later. For a real number $x$,
we define

$\phi_{b,\epsilon}(x):=\begin{cases}\sin(\pi b\epsilon)/|\sin(\pi x)|&\mbox{
if }|x-\frac{k}{b}|<\epsilon\text{ for some integer $k\not\equiv 0(b)$}\\\
\phi_{b}(x)&\mbox{ otherwise.}\end{cases}$

Clearly $\phi_{b,\epsilon}$ is $1$-periodic and continuous satisfying
$\phi_{b,\epsilon}(x)\asymp_{b,\epsilon}1$ and
$\phi_{b,\epsilon}(x)\geq\phi_{b}(x)$ for every $x$. In particular

$\prod_{1\leq n\leq N}\phi_{b}(\alpha_{n})\leq\prod_{1\leq n\leq
N}\phi_{b,\epsilon}(\alpha_{n}).$

Denoting by $P_{N}$ the product on the right hand side above, taking
logarithms and applying the Koksma-Hlawka inequality (Lemma 4.1) one has

$\dfrac{\log P_{N}}{N}=\dfrac{1}{N}\sum_{1\leq n\leq
N}\log\phi_{b,\epsilon}(\alpha_{n})\leq\int_{0}^{1}\log\phi_{b,\epsilon}(x)dx+V(\log\circ\phi_{b,\epsilon})D^{*}_{N},$

where $V(\log\circ\phi_{b,\epsilon})$ is the total variation of
$\log\circ\phi_{b,\epsilon}$ on $[0,1]$. It satisfies

$\displaystyle V(\log\circ\phi_{b,\epsilon})$ $\displaystyle\leq
2\pi\int_{0}^{\epsilon}\left|b\cot(\pi bx)-\cot(\pi
x)\right|dx+2\pi\int_{\epsilon}^{1/2}\cot(\pi x)dx$ $\displaystyle\qquad+\pi
b\sum_{0\leq k<b}\int_{\frac{k}{b}+\epsilon}^{\frac{k+1}{b}-\epsilon}|\cot(\pi
bx)|dx$ $\displaystyle\ll b\log(1/b\epsilon).$

Note we used $|\cot(\pi x)|=\cot(\pi\|x\|)$ and $\cot(x)=x^{-1}+O(x)$ for
$0<|x|\leq\pi/2$.

Splitting the range of integration according to the definition of
$\phi_{b,\epsilon}$, using $\phi_{b}(x)\leq b$, the additivity of the
logarithm, and ignoring the terms $\log|\sin(\pi b\epsilon)|$ (these are non-
positive) one derives

$\displaystyle\int_{0}^{1}\log\phi_{b,\epsilon}(x)dx$ $\displaystyle\leq
2\epsilon\log b+2\int_{\epsilon}^{1/2}\log\csc(\pi x)dx+\sum_{0\leq
k<b}\int_{\frac{k}{b}+\epsilon}^{\frac{k+1}{b}-\epsilon}\log|\sin(\pi bx)|dx$
$\displaystyle=2\epsilon\log b+2\int_{\epsilon}^{b\epsilon}\log\csc(\pi x)dx$
$\displaystyle\ll b\epsilon\log(1/b\epsilon).$

The result then follows if we let $\epsilon=D_{N}^{*}/2b$. ∎

Our final tool is the following version of Vinogradov’s lemma.

######  Lemma 4.10 (Vinogradov-type lemma).

Let $A,B,\theta$ be real numbers, $A,B>0$, and let $q\geq 2$ be an integer.
Then

$\sum_{n(q)}\min\left(A,B\csc^{2}\left(\pi\dfrac{n+\theta}{q}\right)\right)\leq\min\left(A,B\csc^{2}\left(\dfrac{\pi\|\theta\|}{q}\right)\right)+\left(1-\dfrac{4}{\pi^{2}}\right)Bq^{2}.$

###### Proof.

We can write $\theta=m+r$ for some integer $m$ and real number $-1/2<r\leq
1/2$. In fact $|r|=\|\theta\|$. Since $m+n$ uniquely covers each residue class
modulo $q$ when so does $n$, the sum equals

$S:=\sum_{0\leq
n<q}\min\left(A,B\csc^{2}\left(\pi\dfrac{n+r}{q}\right)\right).$

If $r<0$, we may replace $n$ with $-n$ in the summand. Thus without loss of
generality we may assume that $r\geq 0$. Now note

$S\leq\min\left(A,B\csc^{2}\left(\dfrac{\pi r}{q}\right)\right)+BH_{q}(r),$

where for $0\leq r\leq 1/2$,

$H_{q}(r):=\sum_{1\leq n<q}\csc^{2}\left(\pi\dfrac{n+r}{q}\right).$

Since $x\mapsto\csc^{2}(\pi x)$ is convex in $0<x<1$, so is $H_{q}(r)$ in
$0\leq r\leq 1/2$. From the well-known identity

$\pi^{2}\csc^{2}(\pi x)=\sum_{n\in\mathbb{Z}}\dfrac{1}{(n+x)^{2}}$

for $x\not\in\mathbb{Z}$, one derives (see for instance [17])

$H_{q}(r)=\begin{cases}(q^{2}-1)/3&\mbox{ if }r=0,\\\ q^{2}\csc^{2}(\pi
r)-\csc^{2}(\pi r/q)&\mbox{ if }0<r\leq 1/2.\end{cases}$

One can show that $H_{q}(0)\leq H_{q}(1/2)$ (say by using the inequality
$\sin(\pi x)\geq 2^{3/2}x$ valid for $0\leq x\leq 1/4$) and thus $H_{q}(r)\leq
H_{q}(1/2)$ for $0\leq r\leq 1/2$ by the convexity of $H_{q}(r)$ in $[0,1/2]$.
We also have $H_{q}(1/2)=q^{2}-\csc^{2}(\pi/2q)\leq q^{2}(1-4/\pi^{2})$ since
$\sin(x)\leq x$ for $x\geq 0$. The result now follows. ∎

##  5\. Exponential sums over $\mathscr{P}_{b}^{0}(x)$

The current state of knowledge on exponential sums over palindromes,
specifically on bounds for these, is rather limited. To our understanding, the
literature on this topic is thus far comprised of the works of Banks-Hart-
Sakata [3], Banks-Shparlinski [4] and Col [8]. Here we give a brief exposition
of what is known, as well as add slightly to the literature via the results in
Proposition 5.5 and Corollary 5.6 for special prime moduli. These are
consequences of a result of Bourgain [5] giving upper bounds for certain types
of exponential sums over finite fields with prime order.

For the sake of simplicity, and indeed, for our purposes, we focus exclusively
on exponential sums over $\mathscr{P}_{b}^{0}(x)$; that is, over
$b$-palindromes, at most $x$ in size, with an odd number of digits in their
$b$-adic expansion. Sums over palindromes with an even number of digits are
rather similar in nature and all results here extend naturally, albeit with
minor differences, to these.

The starting point, just as that in the works [3], [8], is that such sums can
essentially be decomposed into linear combinations of objects enjoying rather
useful multiplicative and algebraic structures. These properties are crucial
in the upcoming sections. In this regard we have the following lemma, implicit
in the works [3], [8]. We give a proof for the convenience of the reader.

######  Lemma 5.1.

For any $\alpha,x\in\mathbb{R}$, $x\geq 1$,

$\left|\sum_{n\in\mathscr{P}_{b}^{0}(x)}e(\alpha n)\right|\leq
b^{2}\sum_{0\leq N\leq\frac{1}{2}\log_{b}x}\sum_{0\leq M\leq
N}\Phi_{M}\left(\alpha b^{N-M}\right),$

where $\Phi_{M}$ is as defined in (10).

###### Proof.

From the definition of $\mathscr{P}_{b}^{0}(x)$ and the triangle inequality,
we have

$\left|\sum_{n\in\mathscr{P}^{0}_{b}(x)}e(\alpha n)\right|\leq\sum_{0\leq
N\leq\frac{1}{2}\log_{b}x}\left|\sum_{\begin{subarray}{c}n\in\Pi_{b}(2N)\\\
n\leq x\end{subarray}}e(\alpha n)\right|,$

where

(23) $\Pi_{b}(2N):=\left\\{n\in\mathscr{P}_{b}\ :\
\lfloor\log_{b}n\rfloor=2N\right\\}=\mathscr{P}_{b}\cap[b^{2N},b^{2N+1}).$

The sum inside the vertical brackets equals

$\sum_{\begin{subarray}{c}n\in\Pi_{b}(2N)\\\ n\leq y\end{subarray}}e(\alpha
n),$

where $y$ is the largest palindrome in $\Pi_{b}(2N)$ satisfying $y\leq x$. If
no such palindrome $y$ exists, the sum is trivially zero. Otherwise we may
write

$y=y_{N}b^{N}+\sum_{0\leq j<N}y_{j}\left(b^{j}+b^{2N-j}\right)$

for some digits $0\leq y_{j}<b$ with $y_{0}>0$. We now seek to establish the
inequality

(24) $\left|\sum_{\begin{subarray}{c}n\in\Pi_{b}(2N)\\\ n\leq
y\end{subarray}}e(\alpha n)\right|\leq b^{2}\sum_{0\leq M\leq
N}\Phi_{M}\left(\alpha b^{N-M}\right).$

To this end, we first define for an integer $\lambda\geq 0$,

$\Psi_{\lambda}(\alpha):=\sum_{0\leq c_{N}<b}e\left(\alpha
c_{N}b^{N}\right)\prod_{\lambda<n<N}\sum_{0\leq c<b}e\left(\alpha
c\left(b^{n}+b^{2N-n}\right)\right).$

We have

$\displaystyle\sum_{\begin{subarray}{c}n\in\Pi_{b}(2N)\\\ n\leq
y\end{subarray}}e(\alpha n)$ $\displaystyle=\Psi_{0}(\alpha)\sum_{1\leq
c<y_{0}}e\left(\alpha c\left(1+b^{2N}\right)\right)$
$\displaystyle+\Psi_{1}(\alpha)e\left(\alpha
y_{0}\left(1+b^{2N}\right)\right)\sum_{0\leq c<y_{1}}e\left(\alpha
c\left(b+b^{2N-1}\right)\right)$ $\displaystyle+\Psi_{2}(\alpha)e\left(\alpha
y_{0}\left(1+b^{2N}\right)+\alpha
y_{1}\left(b+b^{2N-1}\right)\right)\sum_{0\leq c<y_{2}}e\left(\alpha
c\left(b^{2}+b^{2N-2}\right)\right)$ $\displaystyle+\cdots$
$\displaystyle+\Psi_{N-1}(\alpha)e\left(\sum_{0\leq
j<N-1}y_{j}\left(b^{j}+b^{2N-j}\right)\right)\sum_{0\leq
c<y_{N-1}}e\left(\alpha c\left(b^{N-1}+b^{2N-(N-1)}\right)\right)$
$\displaystyle+e\left(\sum_{0\leq
j<N}y_{j}\left(b^{j}+b^{2N-j}\right)\right)\sum_{0\leq c\leq
y_{N}}e\left(\alpha cb^{N}\right).$

Now the result follows when we note that

$\prod_{\lambda<n<N}\sum_{0\leq c<b}e\left(\alpha
c\left(b^{n}+b^{2N-n}\right)\right)=\prod_{1\leq n<N-\lambda}\sum_{0\leq
c<b}e\left(\alpha b^{\lambda}c\left(b^{n}+b^{2(N-\lambda)-n}\right)\right)$

and take absolute values. ∎

From the lemma above it is clear that to study upper bounds for sums such as
$\sum_{n\in\mathscr{P}_{b}^{0}(x)}e(\alpha n)$, it is sufficient to study the
products $\Phi_{N}$ or, more generally, products such as

(25) $P_{M}(\alpha):=\prod_{1\leq n\leq
M}\phi_{b}\left(\alpha\left(b^{n}+b^{2N-n}\right)\right)$

with $M\leq 2N$. Of course the product’s definition depends also on $b,N$, but
for the sake of brevity we omit these on the left hand side above.

Let us now state Col’s result in our context. This will be needed later on. We
give a proof somewhat different to that of Col [8] in its initial steps,
although it ultimately boils to considering lower bounds for sums such as
$\sum_{n\leq M}\|ab^{n}/q\|^{2}$, just as in Col’s argument.

######  Proposition 5.2 (Col [8], Corollary 4).

Let $h,q,k,M,N$ be integers with $q\geq 2$, $(q,h(b^{3}-b))=1$ and $0\leq
M\leq 2N$. Then for $P_{M}$ defined as in (25),

$P_{M}\left(\dfrac{h}{q}+\dfrac{k}{b^{3}-b}\right)\ll_{b}b^{M}\exp\left(-\sigma_{\infty}(b)\dfrac{M}{\log
q}\right)$

uniformly in $h,k,N$, where $\sigma_{\infty}(b)>0$ is some value depending
only on $b$.

###### Proof.

We may assume that $M\geq\log_{b}q$ as otherwise the statement is trivial. Now
for the sake of brevity let $\alpha:=\frac{h}{q}+\frac{k}{b^{3}-b}$. Grouping
the factors in the product by pairs of adjacent factors, we have

$\displaystyle P_{M}(\alpha)\leq b\prod_{1\leq
n<M}\sqrt{\phi_{b}\left(\alpha\left(b^{n}+b^{2N-n}\right)\right)\phi_{b}\left(\alpha\left(b^{n+1}+b^{2N-n-1}\right)\right)}.$

By Lemma 4.8 with $\beta=2N-n-1$ and $\gamma=n$,

$\phi_{b}\left(\alpha\left(b^{n}+b^{2N-n}\right)\right)\phi_{b}\left(\alpha\left(b^{n+1}+b^{2N-n-1}\right)\right)\leq
b\phi_{b}\left(\dfrac{\|\alpha(b^{2}-1)b^{n}\|}{b+1}\right).$

Thus

$P_{M}(\alpha)\leq b^{\frac{M-1}{2}+1}\sqrt{\prod_{1\leq
n<M}\phi_{b}\left(\dfrac{\|\alpha(b^{2}-1)b^{n}\|}{b+1}\right)}.$

By Lemma 4.6 and the $1$-periodicity of $\|\cdot\|$, the above is

$\displaystyle\ll b^{M}\exp\left(-\dfrac{\pi^{2}(b-1)}{12(b+1)}\sum_{1\leq
n\leq M}\left\|\dfrac{h(b^{2}-1)b^{n}}{q}\right\|^{2}\right)$

uniformly in $k,N$. Since $q\geq 2$ and $(q,h(b^{3}-b))=1$ by assumption, each
term in the sum above is $\geq 1/q^{2}$. In particular the result holds if
$q<b$. Consider now the case when $q\geq b$. Here we argue as done by Maynard
[24] in Lemma 10.1 there. Dividing the sum above into sums over segments of
length $\lfloor\log_{b}q\rfloor$, we observe it is

$\geq\left\lfloor\dfrac{M}{\log_{b}q}\right\rfloor\min_{(a,q)=1}\sum_{1\leq
n\leq\log_{b}q}\left\|\dfrac{ab^{n}}{q}\right\|^{2}.$

Note we used the assumption $(q,h(b^{3}-b))=1$. Since $q\geq 2$ and
$(q,ab)=1$, we have $\|ab^{n}/q\|\geq 1/q$ for each $n$. Moreover if
$\|ab^{n}/q\|\leq 1/2b$, then $\|ab^{n+1}/q\|=b\|ab^{n}/q\|$. Consequently
there exists an integer $1\leq n\leq\log_{b}q$ for which $\|ab^{n}/q\|\geq
1/2b^{2}$. Hence the sum is $\geq 1/4b^{4}$ and the result follows. ∎

The bound due to Col [8] in Proposition 5.2 is non-trivial in the range $q\ll
e^{o(M)}$ and is rather general in the sense of the lack of restrictions on
the arithmetic shape of $q$. As such, it considerably improved over the
corresponding general bound due to Banks-Hart-Sakata [3] (see Lemma 3.2 there)
non-trivial only in the range $q=o(\sqrt{M})$ (strictly speaking, the bounds
of Banks-Hart-Sakata were essentially given for products such as $\Phi_{N}$
and not the product over $1\leq n\leq M$ in Proposition 5.2, but their work
easily extends to this).

In the range $q\ll M^{2}$ with $(q,b)=1$ satisfying
$\tau(q)\sqrt{q}\ll\text{ord}_{q}(b)\ll M$ (with suitable implied constants)
and $P^{-}(q)>b$, the arguments of Banks-Hart-Sakata [3] (see Lemma 3.1 there)
yield power-saving bounds of the form $P_{M}(h/q)\ll b^{\delta M}$ with
$0<\delta<1$ fixed or depending only on $b$. Although applicable only on the
much smaller range $q\ll M^{2}$, this is superior in strength over that in
Proposition 5.2 for such $q$. Indeed, the latter attains (at best) power-
savings only for $q\ll 1$. In few words, their argument can be explained as
follows:

Assume $(h,q)=1$. Squaring $P_{M}(h/q)$, applying the inequality of the
arithmetic and geometric means, expanding the square and switching orders of
summation, all in turn, one has

(26) $\displaystyle P_{M}^{2/M}(h/q)$ $\displaystyle=\sum_{0\leq
c_{1},c_{2}<b}\dfrac{1}{M}\sum_{1\leq n\leq
M}e_{q}\left(h(c_{1}-c_{2})\left(b^{n}+b^{2N-n}\right)\right)$
$\displaystyle=b+\sum_{0\leq c_{1}\neq c_{2}<b}\dfrac{1}{M}\sum_{1\leq n\leq
M}e_{q}\left(h(c_{1}-c_{2})\left(b^{n}+b^{2N-n}\right)\right).$

If we impose the restriction $P^{-}(q)>b$, we have $(c_{1}-c_{2},q)=1$ for
$0\leq c_{1}\neq c_{2}<b$. In this case

(27) $P_{M}^{2/M}(h/q)\leq
b+\dfrac{b^{2}}{M}\max_{a,k\in(\mathbb{Z}/q\mathbb{Z})^{\times}}S_{q}(M,a,k),$

where

(28) $S_{q}(M,a,k):=\left|\sum_{1\leq n\leq
M}e_{q}\left(ab^{n}+k\bar{b}^{n}\right)\right|.$

Here $\overline{b}$ denotes the multiplicative inverse of $b$ modulo $q$.
Using well-known bounds for twisted Kloosterman sums, one derives (see Lemma
2.1 in [3])

$S_{q}(M,a,k)\leq\dfrac{M\tau(q)\sqrt{q}}{\text{ord}_{q}(b)}+\text{ord}_{q}(b).$

For this to be non-trivial, it is necessary that
$\tau(q)\sqrt{q}\ll\text{ord}_{q}(b)\ll M$; hence their assumptions on $q$.
One thus obtains

$P_{M}^{2/M}(h/q)\leq
b+b^{2}\left(\dfrac{\tau(q)\sqrt{q}}{\text{ord}_{q}(b)}+\dfrac{\text{ord}_{q}(b)}{M}\right).$

Banks-Shparlinski [4] also studied the sum $S_{q}(M,a,k)$ after the work of
Banks-Hart-Sakata [3] and obtained a bound for $P_{M}(h/p)$, with $p$ prime,
essentially comparable to Col’s result in Proposition 5.2 for $q=p\ll
M^{2}/\log^{4}M$ with no restrictions on $\text{ord}_{p}(b)$; see their
Theorem 6.

From the argument above, it is clear that improving bounds for $S_{q}(M,a,k)$
and/or enlarging the range of applicability of such bounds, may yield stronger
results. However due to the presence of the $b$ term in (27) coming from the
diagonal cases $c_{1}=c_{2}$ in (26), one can never do better than $P_{M}\ll
b^{M/2}$ via this argument, regardless of the quality of the bounds available
for $S_{q}(M,a,k)$.

Soon after the works of Banks-Hart-Sakata [3] and Banks-Shparlinski [4],
Bourgain [5] obtained the following result. First given a prime $p$, let
$\mathbb{F}_{p}$ be the finite field with $p$ elements and let
$\mathbb{F}_{p}^{*}$ be its subset of non-zero elements, endowed with the
usual properties of $\mathbb{F}_{p}$. Given $\theta\in\mathbb{F}_{p}^{*}$, we
use the notation $\text{ord}(\theta)$ to denote its multiplicative order.

######  Theorem 5.3 (Bourgain [5], Theorem 2).

Let $\epsilon>0$, let $p$ be a prime number and let
$\theta_{1},\ldots,\theta_{r}\in\mathbb{F}_{p}^{*}$ satisfying
$\text{ord}(\theta_{j})>p^{\epsilon}$ and
$\text{ord}(\theta_{i}\theta_{j}^{-1})>p^{\epsilon}$ for each $1\leq i\neq
j\leq r$. Then for any integer $N>p^{\epsilon}$ and any
$a_{1},\ldots,a_{r}\in\mathbb{F}_{p}^{*}$,

$\left|\sum_{n=1}^{N}e_{p}\left(\sum_{j=1}^{r}a_{j}\theta_{j}^{n}\right)\right|<\dfrac{N}{p^{\delta}},$

where $0<\delta=\delta(\epsilon)<1$ is some value depending only on
$\epsilon$.

We recognize that the sum, in Theorem 5.3, with
$r=2,a_{1}=a,a_{2}=k,\theta_{1}=b,\theta_{2}=\bar{b}$, $N=M$, is precisely
$S_{p}(M,a,k)$. Thus we have the following.

######  Corollary 5.4.

Let $M$ be an integer. Then for any prime $p$ satisfying $(p,b)=1$ and
$p^{\epsilon}<\min(M,\text{ord}_{p}(b^{2}))$ for some $\epsilon>0$, we have

$\max_{a,k\in(\mathbb{Z}/p\mathbb{Z})^{\times}}S_{p}(M,a,k)<\dfrac{M}{p^{\delta(\epsilon)}},$

where $\delta(\epsilon)>0$ depends only on $\epsilon$, and $S_{p}(M,a,k)$ is
defined as in (28).

###### Proof.

Suffices to note $\text{ord}_{p}(b^{\pm 1})\geq\text{ord}_{p}(b^{\pm
2})>p^{\epsilon}$, the last holding by assumption. ∎

From this and (27) we may then obtain, under the same assumptions of Corollary
5.4 with $p>b$,

$P_{M}\left(\dfrac{h}{p}\right)\leq
b^{M}\left(\dfrac{1}{b}+\dfrac{1}{p^{\delta}}\right)^{M/2}.$

One may improve this considerably, in Corollary 5.6 below, by combining use of
Lemma 4.9, the Erdős-Túran inequality and Bourgain’s bound. More generally we
have the following.

######  Proposition 5.5.

With the same assumptions of Theorem 5.3,

$\prod_{1\leq n\leq
N}\phi_{b}\left(\dfrac{1}{p}\sum_{j=1}^{r}a_{j}\theta_{j}^{n}\right)\leq\exp\left(A(\epsilon)b\dfrac{N}{p^{\delta(\epsilon)}}\right),$

where $A(\epsilon),\delta(\epsilon)>0$ are some values depending only on
$\epsilon$.

###### Proof.

For each integer $1\leq n\leq N$, let

$\alpha_{n}=\dfrac{1}{p}\sum_{j=1}^{r}a_{j}\theta_{j}^{n}.$

By Lemma 4.9,

$\prod_{1\leq n\leq
N}\phi_{b}(\alpha_{n})\leq\exp\left(AbND_{N}^{*}\log\left(\dfrac{2}{D_{N}^{*}}\right)\right)$

for some absolute constant $A>0$, where $D_{N}^{*}$ is the star-discrepancy of
$(\alpha_{n})_{n=1}^{N}$. By the Erdős-Turán inequality (Lemma 4.2) and the
fact $D_{N}^{*}\leq D_{N}$, we have

$D_{N}^{*}\ll\dfrac{1}{H}+\sum_{1\leq h\leq
H}\dfrac{1}{h}\left|\dfrac{1}{N}\sum_{1\leq n\leq N}e(h\alpha_{n})\right|$

for any $H\geq 2$. The contribution of the terms with $p\mid h$ to the series
above is trivially $\ll\log(H)/p$. By Bourgain’s bound in Theorem 5.3, the
terms with $p\nmid h$ contribute $\ll\log(H)/p^{\delta}$ to the sum, where
$0<\delta=\delta(\epsilon)<1$ is some value depending only on $\epsilon$. Thus

$D_{N}^{*}\ll\dfrac{1}{H}+\dfrac{\log H}{p^{\delta}}\ll\dfrac{\log
p}{p^{\delta}}$

after letting $H=p$. Hence

$D_{N}^{*}\log(2/D_{N}^{*})\ll\dfrac{\log^{2}p}{p^{\delta}}\ll_{\delta}p^{-\delta/2}$

and the result follows. ∎

Specializing to the palindromes we have the following immediate consequence.

######  Corollary 5.6.

With the same assumptions of Corollary 5.4 and $M\leq 2N$ there, we have

$\max_{(h,p)=1}\prod_{1\leq n\leq
M}\phi_{b}\left(\dfrac{h}{p}\left(b^{n}+b^{2N-n}\right)\right)\leq\exp\left(A(\epsilon)b\dfrac{M}{p^{\delta(\epsilon)}}\right),$

where $A(\epsilon),\delta(\epsilon)>0$ are some values depending only on
$\epsilon$.

##  6\. Bounding moments of $\Phi_{N}$

In this section we prove Proposition 6.1.

######  Proposition 6.1 ($2K$-th moment).

For any integers $N,K,b\geq 2$, we have

(29) $\int_{0}^{1}\Phi_{N}^{2K}(\alpha)d\alpha\leq
b^{2(K-1)N+2}\left(1+O\left(\dfrac{1}{\sqrt{K}}+\dfrac{b^{2}}{K}\right)\right)^{2N}.$

If $\alpha_{1},\ldots,\alpha_{R}\in\mathbb{R}/\mathbb{Z}$ are $\delta$-spaced
for some $0<\delta\leq 1/2$, then

(30)
$\sum_{r=1}^{R}\Phi_{N}^{2K}\left(\alpha_{r}\right)\leq\left(\delta^{-1}+Kb^{2N}\right)b^{2(K-1)N+2}\left(1+O\left(\dfrac{1}{\sqrt{K}}+\dfrac{b^{2}}{K}\right)\right)^{2N}.$

In particular for any $Q\geq 1$ and uniformly in
$\beta\in\mathbb{R/\mathbb{Z}}$,

(31) $\sum_{q\leq
Q}\sum_{h(q)}^{*}\Phi_{N}^{2K}\left(\dfrac{h}{q}+\beta\right)\leq\left(Q^{2}+Kb^{2N}\right)b^{2(K-1)N+2}\left(1+O\left(\dfrac{1}{\sqrt{K}}+\dfrac{b^{2}}{K}\right)\right)^{2N}.$

###### Proof.

We first note that (31) follows from (30) since the points $h/q+\beta$ with
$1\leq h\leq q\leq Q$ and $(h,q)=1$ are $Q^{-2}$-spaced modulo $1$. Indeed,
for any two distinct such fractions $h_{1}/q_{1},h_{2}/q_{2}$, we have

$\left\|\dfrac{h_{1}}{q_{1}}-\dfrac{h_{2}}{q_{2}}\right\|\geq\dfrac{1}{q_{1}q_{2}}\geq\dfrac{1}{Q^{2}}.$

Let us now set $\psi_{b}(\alpha):=\sum_{0\leq m<b}e(\alpha m)$. By definition,

$\Phi_{N}^{2K}(\alpha)=\left|\prod_{1\leq
n<N}\psi_{b}^{K}\left(\alpha\left(b^{n}+b^{2N-n}\right)\right)\right|^{2}.$

We have

$\prod_{1\leq
n<N}\psi_{b}\left(\alpha\left(b^{n}+b^{2N-n}\right)\right)=\sum_{0\leq
c_{1},\ldots,c_{N-1}<b}e\left(\alpha\sum_{1\leq
n<N}c_{n}\left(b^{n}+b^{2N-n}\right)\right)$

and one observes

$\displaystyle\prod_{1\leq
n<N}\psi_{b}^{K}\left(\alpha\left(b^{n}+b^{2N-n}\right)\right)$
$\displaystyle=\sum_{0\leq v_{1},\ldots,v_{N-1}\leq(b-1)K}\left(\prod_{1\leq
n<N}r(v_{n};K,b)\right)e\left(\alpha\sum_{1\leq
m<N}v_{m}\left(b^{m}+b^{2N-m}\right)\right),$

where $r(v;K,b)$ is defined as in (11). We can rewrite this as

$\prod_{1\leq
n<N}\psi_{b}^{K}\left(\alpha\left(b^{n}+b^{2N-n}\right)\right)=\sum_{0\leq\ell\leq
Kb^{2N}}a_{\ell}e(\alpha\ell),$

where

$a_{\ell}:=\sum_{\begin{subarray}{c}0\leq v_{1},\ldots,v_{N-1}\leq(b-1)K\\\
\sum_{1\leq m<N}v_{m}(b^{m}+b^{2N-m})=\ell\end{subarray}}\prod_{1\leq
n<N}r(v_{n};K,b).$

Thus

$\Phi_{N}^{2K}\left(\alpha\right)=\left|\sum_{0\leq\ell\leq
Kb^{2N}}a_{\ell}e(\alpha\ell)\right|^{2}.$

Parseval’s identity then gives

$\int_{0}^{1}\Phi_{N}^{2K}\left(\alpha\right)d\alpha=\sum_{0\leq\ell\leq
Kb^{2N}}a_{\ell}^{2}$

while the large sieve inequality (Lemma 1.6) yields

$\sum_{r=1}^{R}\Phi_{N}^{2K}\left(\alpha_{r}\right)\leq\left(\delta^{-1}+Kb^{2N}\right)\sum_{0\leq\ell\leq
Kb^{2N}}a_{\ell}^{2}$

for any $\delta$-spaced points
$\alpha_{1},\ldots,\alpha_{R}\in\mathbb{R}/\mathbb{Z}$. Thus to prove the
proposition we must show that

(32) $\sum_{0\leq\ell\leq Kb^{2N}}a_{\ell}^{2}\leq
b^{2(K-1)N+2}\left(1+O\left(\dfrac{1}{\sqrt{K}}+\dfrac{b^{2}}{K}\right)\right)^{2N}.$

Expanding the square and switching orders of summation, we have

$\sum_{0\leq\ell\leq Kb^{2N}}a_{\ell}^{2}=\sum_{\begin{subarray}{c}0\leq
u_{1},\ldots,u_{N-1}\leq(b-1)K\\\ 0\leq v_{1},\ldots,v_{N-1}\leq(b-1)K\\\
\sum_{1\leq m<N}(u_{m}-v_{m})(b^{m}+b^{2N-m})=0\end{subarray}}\prod_{1\leq
n<N}r(u_{n};K,b)r(v_{n};K,b).$

It will be convenient later on to introduce extra variables $u_{N},v_{N}$ to
the sum. To this end, we claim that

$\displaystyle\sum_{\begin{subarray}{c}0\leq u_{1},\ldots,u_{N-1}\leq(b-1)K\\\
0\leq v_{1},\ldots,v_{N-1}\leq(b-1)K\\\ \sum_{1\leq
m<N}(u_{m}-v_{m})(b^{m}+b^{2N-m})=0\end{subarray}}\prod_{1\leq
n<N}r(u_{n};K,b)r(v_{n};K,b)$ $\displaystyle\leq\sum_{\begin{subarray}{c}0\leq
u_{1},\ldots,u_{N}\leq(b-1)K\\\ 0\leq v_{1},\ldots,v_{N}\leq(b-1)K\\\
\sum_{1\leq m\leq N}(u_{m}-v_{m})(b^{m}+b^{2N-m})=0\end{subarray}}\prod_{1\leq
n\leq N}r(u_{n};K,b)r(v_{n};K,b).$

Indeed, any solution
$(u_{1}^{\prime},\ldots,u_{N-1}^{\prime})\times(v_{1}^{\prime},\ldots,v_{N-1}^{\prime})$
to the equation

$\sum_{1\leq m<N}(u_{m}-v_{m})(b^{m}+b^{2N-m})=0$

yields the solution
$(u_{1}^{\prime},\ldots,u_{N-1}^{\prime},0)\times(v_{1}^{\prime},\ldots,v_{N-1}^{\prime},0)$
to the equation

$\sum_{1\leq m\leq N}(u_{m}-v_{m})(b^{m}+b^{2N-m})=0.$

Since $r(0;K,b)=1$ additionally, the claim follows.

For any integer $n$, Lemma 4.5 implies

$r(n;K,b)\leq\dfrac{b^{K}\mathbf{1}_{0\leq
n\leq(b-1)K}}{\sqrt{(b^{2}-1)K}}\left(\sqrt{\dfrac{6}{\pi}}\exp\left(-\dfrac{6}{(b^{2}-1)K}\left(n-\dfrac{(b-1)K}{2}\right)^{2}\right)+\dfrac{c}{K}\right)$

for some absolute constant $c>0$. We fix a smooth function
$\nu:\mathbb{R}\to[0,1]$ compactly supported on $[-2,2]$ satisfying $\nu(t)=1$
for $0\leq t\leq 1$ and $\|\nu^{(j)}\|_{\infty}\ll_{j}1$ for each $j\geq 0$.
In particular $\mathbf{1}_{0\leq n\leq(b-1)K}\leq\nu(n/(b-1)K)$ and

$r(n;K,b)\leq\dfrac{b^{K}\nu(\frac{n}{(b-1)K})}{\sqrt{(b^{2}-1)K}}\left(\sqrt{\dfrac{6}{\pi}}\exp\left(-\dfrac{6}{(b^{2}-1)K}\left(n-\dfrac{(b-1)K}{2}\right)^{2}\right)+\dfrac{c}{K}\right).$

We can rewrite this as

$r(n;K,b)\leq\dfrac{b^{K}}{\sqrt{(b^{2}-1)K}}\eta_{K,b}\left(\dfrac{n}{\sqrt{(b^{2}-1)K}}\right),$

where $\eta_{K,b}:\mathbb{R}\to\mathbb{R}^{+}_{0}$ is the smooth compactly
supported function defined by

(33)
$\eta_{K,b}(t)=\left(\sqrt{\dfrac{6}{\pi}}\exp\left(-6\left(t-\dfrac{1}{2}\sqrt{\dfrac{(b-1)K}{b+1}}\right)^{2}\right)+\dfrac{c}{K}\right)\nu\left(t\sqrt{\dfrac{b+1}{(b-1)K}}\right).$

Then we have

$\sum_{\begin{subarray}{c}0\leq u_{1},\ldots,u_{N}\leq(b-1)K\\\ 0\leq
v_{1},\ldots,v_{N}\leq(b-1)K\\\ \sum_{1\leq m\leq
N}(u_{m}-v_{m})(b^{m}+b^{2N-m})=0\end{subarray}}\prod_{1\leq n\leq
N}r(u_{n};K,b)r(v_{n};K,b)\leq\dfrac{b^{2KN}}{(b^{2}-1)^{N}K^{N}}J,$

where $J$ is the sum

$\sum_{\begin{subarray}{c}u_{1},\ldots,u_{N}\in\mathbb{Z}\\\
v_{1},\ldots,v_{N}\in\mathbb{Z}\\\ \sum_{1\leq m\leq
N}(u_{m}-v_{m})(b^{m}+b^{2N-m})=0\end{subarray}}\prod_{1\leq n\leq
N}\eta_{K,b}\left(\dfrac{u_{n}}{\sqrt{(b^{2}-1)K}}\right)\eta_{K,b}\left(\dfrac{v_{n}}{\sqrt{(b^{2}-1)K}}\right).$

In view of (32) we complete the proof if we show that

(34) $J\leq
b^{2}\dfrac{(b^{2}-1)^{N}K^{N}}{b^{2N}}\left(1+O\left(\dfrac{1}{\sqrt{K}}+\dfrac{b^{2}}{K}\right)\right)^{2N}.$

To this end we proceed as follows.

An application of the identity

$\mathbf{1}_{k=0}=\int_{0}^{1}e(k\alpha)d\alpha$

valid for integers $k$, gives

$J=\int_{0}^{1}\left|\prod_{1\leq n\leq
N}\sum_{v\in\mathbb{Z}}\eta_{K,b}\left(\dfrac{v}{\sqrt{(b^{2}-1)K}}\right)e\left(\alpha
v\left(b^{n}+b^{2N-n}\right)\right)\right|^{2}d\alpha.$

Let us set

(35) $A:=\sqrt{(b^{2}-1)K}\|\eta_{K,b}\|_{1}+\|\eta_{K,b}^{\prime}\|_{1}.$

By the symmetry of $n\mapsto b^{n}+b^{2N-n}$ around $n=N$ and the bound

$\left|\sum_{v\in\mathbb{Z}}\eta_{K,b}\left(\dfrac{v}{\sqrt{(b^{2}-1)K}}\right)e\left(2\alpha
vb^{N}\right)\right|\leq A$

coming from (18) in Lemma 4.3, note

$J\leq A\int_{0}^{1}\prod_{1\leq
n<2N}\left|\sum_{v\in\mathbb{Z}}\eta_{K,b}\left(\dfrac{v}{\sqrt{(b^{2}-1)K}}\right)e\left(\alpha
v\left(b^{n}+b^{2N-n}\right)\right)\right|d\alpha.$

Grouping by pairs of adjacent factors and bounding square roots of two
endpoint factors, we have

$\displaystyle\prod_{1\leq
n<2N}\left|\sum_{v\in\mathbb{Z}}\eta_{K,b}\left(\dfrac{v}{\sqrt{(b^{2}-1)K}}\right)e\left(\alpha
v\left(b^{n}+b^{2N-n}\right)\right)\right|$ $\displaystyle\leq A\prod_{1\leq
n\leq
2(N-1)}\sqrt{\left|\sum_{u\in\mathbb{Z}}\eta_{K,b}\left(\dfrac{u}{\sqrt{(b^{2}-1)K}}\right)e\left(\alpha
u\left(b^{n}+b^{2N-n}\right)\right)\right|}$
$\displaystyle\qquad\times\sqrt{\left|\sum_{v\in\mathbb{Z}}\eta_{K,b}\left(\dfrac{v}{\sqrt{(b^{2}-1)K}}\right)e\left(\alpha
v\left(b^{n+1}+b^{2N-n-1}\right)\right)\right|}.$

By Lemma 4.3 with $k=4$, the product over $1\leq n\leq 2(N-1)$ is at most

$\displaystyle\prod_{1\leq n\leq
2(N-1)}\sqrt{\min\left(A,\dfrac{\|\eta_{K,b}^{(4)}\|_{1}}{(b^{2}-1)^{3/2}K^{3/2}\sin^{4}(\pi\alpha(b^{n}+b^{2N-n}))}\right)}$
$\displaystyle\qquad\times\sqrt{\min\left(A,\dfrac{\|\eta_{K,b}^{(4)}\|_{1}}{(b^{2}-1)^{3/2}K^{3/2}\sin^{4}(\pi\alpha(b^{n+1}+b^{2N-n-1}))}\right)}.$

By Lemma 4.8 with $\beta=2N-n-1$ and $\gamma=n$, the fact that
$t\mapsto\sin(\pi t)$ is increasing on $[0,1/2]$ and $|\sin(\pi
t)|=\sin(\pi\|t\|)$, we have either

$\left|\sin\left(\pi\alpha\left(b^{n}+b^{2N-n}\right)\right)\right|\geq\sin\left(\pi\dfrac{\|\alpha(b^{2}-1)b^{n}\|}{b+1}\right)$

or

$\left|\sin\left(\pi\alpha\left(b^{n+1}+b^{2N-n-1}\right)\right)\right|\geq\sin\left(\pi\dfrac{\|\alpha(b^{2}-1)b^{n}\|}{b+1}\right).$

Then the product above is

$\displaystyle\leq A^{N-1}\prod_{1\leq n\leq
2(N-1)}\sqrt{\min\left(A,\dfrac{\|\eta_{K,b}^{(4)}\|_{1}}{(b^{2}-1)^{3/2}K^{3/2}\sin^{4}(\pi\|\alpha(b^{2}-1)b^{n}\|/(b+1))}\right)}$
$\displaystyle\leq A^{N-1}\prod_{1\leq n\leq
2(N-1)}\sqrt{\min\left(A,\dfrac{(b+1)^{4}\|\eta_{K,b}^{(4)}\|_{1}}{(b^{2}-1)^{3/2}K^{3/2}\sin^{4}(\pi\alpha(b^{2}-1)b^{n})}\right)}.$

Note in the last line we used the inequality $r\sin(\pi t/r)\geq\sin(\pi t)$
valid for $r\geq 1$ and $0\leq t<1$ (which may be shown to hold, say, via
Euler’s product formula). Thus

$\displaystyle\prod_{1\leq
n<2N}\left|\sum_{v\in\mathbb{Z}}\eta_{K,b}\left(\dfrac{v}{\sqrt{(b^{2}-1)K}}\right)e\left(\alpha
v\left(b^{n}+b^{2N-n}\right)\right)\right|$ $\displaystyle\leq
A^{N}\prod_{1\leq n\leq
2(N-1)}\sqrt{\min\left(A,\dfrac{(b+1)^{4}\|\eta_{K,b}^{(4)}\|_{1}}{(b^{2}-1)^{3/2}K^{3/2}\sin^{4}(\pi\alpha(b^{2}-1)b^{n})}\right)}.$

Inserting this in the integral, substituting $\alpha b(b^{2}-1)$ with $\alpha$
and using the $1$-periodicity of the integrand, we obtain

$\displaystyle J$ $\displaystyle\leq A^{N+1}\int_{0}^{1}\prod_{0\leq
n<2(N-1)}\sqrt{\min\left(A,\dfrac{(b+1)^{4}\|\eta_{K,b}^{(4)}\|_{1}}{(b^{2}-1)^{3/2}K^{3/2}\sin^{4}(\pi\alpha
b^{n})}\right)}d\alpha.$

By Lemma 4.4 and the fact $\sqrt{\min(A,B)}=\min(\sqrt{A},\sqrt{B})$ for
$A,B\geq 0$, this integral is

$\leq\left(\sup_{\theta\in\mathbb{R}}\dfrac{1}{b}\sum_{n(b)}\min\left(A^{1/2},\dfrac{(b+1)^{2}\|\eta_{K,b}^{(4)}\|_{1}^{1/2}}{(b^{2}-1)^{3/4}K^{3/4}\sin^{2}(\pi(n+\theta)/b)}\right)\right)^{2(N-1)}$

while Lemma 4.10 implies this is

$\leq\left(\dfrac{A^{1/2}}{b}+\dfrac{b(b+1)^{2}\|\eta_{K,b}^{(4)}\|_{1}^{1/2}}{(b^{2}-1)^{3/4}K^{3/4}}\right)^{2(N-1)}.$

Factoring $\frac{1}{b}(b^{2}-1)^{1/4}K^{1/4}$ out in the estimate, it follows

$J\leq b^{2}\dfrac{(b^{2}-1)^{N}K^{N}}{b^{2N}}\mathcal{E}(N,K,b),$

where

$\displaystyle\mathcal{E}(N,K,b)$
$\displaystyle:=\left(\dfrac{A}{\sqrt{(b^{2}-1)K}}\right)^{N+1}\left(\dfrac{A^{1/2}}{(b^{2}-1)^{1/4}K^{1/4}}+\dfrac{b^{2}(b+1)^{2}\|\eta_{K,b}^{(4)}\|_{1}^{1/2}}{(b^{2}-1)K}\right)^{2(N-1)}$
$\displaystyle\leq\left(\dfrac{A}{\sqrt{(b^{2}-1)K}}\right)^{N}\left(\dfrac{A^{1/2}}{(b^{2}-1)^{1/4}K^{1/4}}+\dfrac{3b^{2}\|\eta_{K,b}^{(4)}\|_{1}^{1/2}}{K}\right)^{2N}$
$\displaystyle=\left(\|\eta_{K,b}\|_{1}+\dfrac{\|\eta_{K,b}^{\prime}\|_{1}}{\sqrt{(b^{2}-1)K}}+\dfrac{3b^{2}\|\eta_{K,b}^{(4)}\|_{1}^{1/2}}{K}\sqrt{\|\eta_{K,b}\|_{1}+\dfrac{\|\eta_{K,b}^{\prime}\|_{1}}{\sqrt{(b^{2}-1)K}}}\right)^{2N}$

for $b\geq 2$. The last holds by the definition of $A$ in (35). From the
definition of $\eta_{K,b}$ in (33) and the assumptions on $\nu$, we have
$\|\eta_{K,b}^{\prime}\|_{1},\|\eta_{K,b}^{(4)}\|_{1}\ll 1$ uniformly in
$K,b$. Moreover the fact $\int_{\mathbb{R}}e^{-t^{2}}dt=\sqrt{\pi}$ and the
assumption $\nu\leq 1$ imply

$\|\eta_{K,b}\|_{1}\leq
1+\dfrac{c\|\nu\|_{1}}{\sqrt{K}}=1+O\left(\dfrac{1}{\sqrt{K}}\right).$

Hence

$\mathcal{E}(N,K,b)\leq\left(1+O\left(\dfrac{1}{\sqrt{K}}+\dfrac{b^{2}}{K}\right)\right)^{2N}$

and

$J\leq
b^{2}\dfrac{(b^{2}-1)^{N}K^{N}}{b^{2N}}\left(1+O\left(\dfrac{1}{\sqrt{K}}+\dfrac{b^{2}}{K}\right)\right)^{2N}.$

We have shown that (34) holds and the proof is thus complete. ∎

##  7\. Bounding the average

In this section we prove Proposition 7.1 combining results from the previous
two sections.

######  Proposition 7.1 ($L^{1}/L^{2}/L^{2K}/L^{\infty}$ hybrid bound).

Let $N\geq 0$ be an integer and let $Q\geq 1$. For any
$0<\epsilon\leq\frac{1}{15}$ and
$\frac{1}{3}\leq\delta\leq\frac{2}{5}-\epsilon$,

(36) $\sup_{\beta\in\mathbb{R}}\sum_{\begin{subarray}{c}q\leq Q\\\
(q,b)=1\end{subarray}}\sum_{h(q)}^{*}\Phi_{N}\left(\dfrac{h}{q}+\beta\right)\ll_{b,\epsilon}Q^{2}b^{N(1-\delta-\sigma_{1}(b,\epsilon))}+Q^{1-\frac{\sigma_{1}(b,\epsilon)}{\delta}}b^{N},$

where $\sigma_{1}(b,\epsilon)>0$ is some value depending only on $b$ and
$\epsilon$. Moreover

(37) $\sum_{\begin{subarray}{c}2\leq q\leq Q\\\
(q,b^{3}-b)=1\end{subarray}}\sum_{h(q)}^{*}\Phi_{N}\left(\dfrac{h}{q}+\dfrac{k}{b^{3}-b}\right)\ll_{b,\epsilon}\left(Q^{2}b^{N(1-\delta-\sigma_{1}(b,\epsilon))}+Q^{1-\frac{\sigma_{1}(b,\epsilon)}{\delta}}b^{N}\right)e^{-\frac{\sigma_{\infty}(b)N}{\log
Q}}$

uniformly in $k\in\mathbb{Z}$, where $\sigma_{\infty}(b)>0$ is some value
depending only on $b$.

We will need the following bound.

######  Lemma 7.2 ($L^{2}$-bound).

Let $0\leq L<M<N$ be integers and let $Q\geq 1$. Then

$\sup_{\beta\in\mathbb{R}}\sum_{q\leq Q}\sum_{h(q)}\prod_{L<n\leq
M}\phi_{b}^{2}\left(\left(\dfrac{h}{q}+\beta\right)\left(b^{n}+b^{2N-n}\right)\right)\ll_{\epsilon}\left(Q+b^{M-L+\epsilon
N}\right)Qb^{M-L}$

for any $\epsilon>0$.

###### Proof.

Expanding the square, switching orders of summation, using the orthogonality
of the additive characters modulo $q$ and taking absolute values, we have that
the left hand side above is

$\leq Q\sum_{\begin{subarray}{c}0\leq u_{L+1},\ldots,u_{M}<b\\\ 0\leq
v_{L+1},\ldots,v_{M}<b\end{subarray}}\sum_{\begin{subarray}{c}q\leq Q\\\ q\mid
S(\mathbf{u},\mathbf{v})\end{subarray}}1,$

where

$S(\mathbf{u},\mathbf{v}):=\sum_{L<n\leq
M}\left(u_{n}-v_{n}\right)\left(b^{n}+b^{2N-n}\right).$

By the uniqueness of the representation of integers in base $b$, we have
$S(\mathbf{u},\mathbf{v})=0$ if and only if $u_{n}=v_{n}$ for each $L<n\leq
M$. The contribution to the overall sum of such (diagonal) terms is $\leq
Q^{2}b^{M-L}$. For the off-diagonal terms with $u_{n}\neq v_{n}$ for some $n$,
the inner sum is $\leq\tau(S(\mathbf{u},\mathbf{v}))\ll_{\epsilon}b^{\epsilon
N}$ for any $\epsilon>0$, where $\tau(m):=\sum_{d\mid m}1$ is the divisor
function. Thus these contribute $\ll_{\epsilon}Qb^{2(M-L)+\epsilon N}$ for any
$\epsilon>0$. ∎

###### Proof of Proposition 7.1.

We may assume that $N\geq 100$, say, as otherwise the statement is trivial.
Let us treat the cases when $Q\ll_{b,\epsilon}b^{\delta N}$ and
$Q\gg_{b,\epsilon}b^{\delta N}$ separately.

We begin by considering the case when $Q\gg_{b,\epsilon}b^{\delta N}$. Here
one can check that both right hand sides of (36) and (37) are
$\gg_{b,\epsilon}Q^{2}b^{N(1-\delta-\sigma_{1}(b,\epsilon))}$ (in particular
the exponential factor in (37) is $\asymp_{b,\epsilon}1$ since $\delta\geq
1/3$ by assumption). Thus to prove (36) and (37) when
$Q\gg_{b,\epsilon}b^{\delta N}$ it suffices to show that the left hand side of
(36) is $\ll_{b,\epsilon}Q^{2}b^{N(1-\delta-\sigma_{1}(b,\epsilon))}$ in this
case. To this end we proceed as follows.

Let $M=\lfloor\delta N\rfloor$ and split the product as

$\Phi_{N}\left(\dfrac{h}{q}+\beta\right)=P_{1}\left(\dfrac{h}{q}\right)P_{2}\left(\dfrac{h}{q}\right)P_{3}\left(\dfrac{h}{q}\right),$

where

$\displaystyle P_{1}\left(\dfrac{h}{q}\right)$ $\displaystyle=\prod_{1\leq
n\leq
M}\phi_{b}\left(\left(\dfrac{h}{q}+\beta\right)\left(b^{n}+b^{2N-n}\right)\right),$
$\displaystyle P_{2}\left(\dfrac{h}{q}\right)$ $\displaystyle=\prod_{M<n\leq
2M}\phi_{b}\left(\left(\dfrac{h}{q}+\beta\right)\left(b^{n}+b^{2N-n}\right)\right),$
$\displaystyle P_{3}\left(\dfrac{h}{q}\right)$
$\displaystyle=\prod_{2M<n<N}\phi_{b}\left(\left(\dfrac{h}{q}+\beta\right)\left(b^{n}+b^{2N-n}\right)\right).$

Let $K\geq 2$ be an integer to be specified later and set $\ell:=4K/(2K-1)>2$.
Note that $2/\ell+1/2K=1$. Then by Hölder’s inequality with the triple
$(\ell,\ell,2K)$, we have

$\displaystyle\sum_{\begin{subarray}{c}q\leq Q\\\
(q,b)=1\end{subarray}}\sum_{h(q)}^{*}\Phi_{N}\left(\dfrac{h}{q}+\beta\right)$
$\displaystyle\leq\left(\sum_{\begin{subarray}{c}q\leq
Q\end{subarray}}\sum_{h(q)}P_{1}^{\ell}\left(\dfrac{h}{q}\right)\right)^{1/\ell}\left(\sum_{\begin{subarray}{c}q\leq
Q\end{subarray}}\sum_{h(q)}P_{2}^{\ell}\left(\dfrac{h}{q}\right)\right)^{1/\ell}\left(\sum_{\begin{subarray}{c}q\leq
Q\\\
(q,b)=1\end{subarray}}\sum_{h(q)}^{*}P_{3}^{2K}\left(\dfrac{h}{q}\right)\right)^{1/2K}.$

Note $P_{1}^{\ell}(h/q)=P_{1}^{\ell-2}(h/q)P_{1}^{2}(h/q)\leq
b^{(\ell-2)M}P_{1}^{2}(h/q)$ while Lemma 7.2 gives

$\sum_{q\leq
Q}\sum_{h(q)}P_{1}^{2}\left(\dfrac{h}{q}\right)\ll_{\gamma}\left(Q+b^{M}\right)Qb^{M+\gamma
N}$

for any $\gamma>0$. Thus

$\left(\sum_{\begin{subarray}{c}q\leq
Q\end{subarray}}\sum_{h(q)}P_{1}^{\ell}\left(\dfrac{h}{q}\right)\right)^{1/\ell}\ll_{\gamma}\left(Q+b^{M}\right)^{1/\ell}Q^{1/\ell}b^{M(1-1/\ell)+\gamma
N}$

for any $\gamma>0$. Similarly we can show that

$\left(\sum_{\begin{subarray}{c}q\leq
Q\end{subarray}}\sum_{h(q)}P_{2}^{\ell}\left(\dfrac{h}{q}\right)\right)^{1/\ell}\ll_{\gamma}\left(Q+b^{M}\right)^{1/\ell}Q^{1/\ell}b^{M(1-1/\ell)+\gamma
N}.$

Consider now the third sum with $P_{3}$. We have

$\displaystyle\sum_{h(q)}^{*}P_{3}^{2K}\left(\dfrac{h}{q}\right)$
$\displaystyle=\sum_{h(q)}^{*}\prod_{1\leq
n<N-2M}\phi_{b}^{2K}\left(\left(\dfrac{h}{q}+\beta\right)\left(b^{2M+n}+b^{2N-2M-n}\right)\right)$
$\displaystyle=\sum_{h(q)}^{*}\prod_{1\leq
n<N-2M}\phi_{b}^{2K}\left(\left(\dfrac{hb^{2M}}{q}+\beta
b^{2M}\right)\left(b^{n}+b^{2(N-2M)-n}\right)\right)$
$\displaystyle=\sum_{h(q)}^{*}\Phi_{N-2M}^{2K}\left(\dfrac{hb^{2M}}{q}+\beta
b^{2M}\right).$

If $(q,b)=1$, we may substitute $hb^{2M}$ with $h$ above. Thus

$\sum_{\begin{subarray}{c}q\leq Q\\\
(q,b)=1\end{subarray}}\sum_{h(q)}^{*}P_{3}^{2K}\left(\dfrac{h}{q}\right)=\sum_{\begin{subarray}{c}q\leq
Q\\\
(q,b)=1\end{subarray}}\sum_{h(q)}^{*}\Phi_{N-2M}^{2K}\left(\dfrac{h}{q}+\beta
b^{2M}\right).$

Removing now the constraint $(q,b)=1$ via positivity, Proposition 6.1 implies
the above is

$\leq\left(Q+\sqrt{K}b^{N-2M}\right)^{2}b^{2(K-1)(N-2M)+2}\left(1+\dfrac{c}{\sqrt{K}}+\dfrac{cb^{2}}{K}\right)^{2(N-2M)}$

for some absolute constant $c>0$. Multiplying the three bounds together and
recalling the assumptions $M=\lfloor\delta N\rfloor$ and $2/\ell+1/2K=1$ gives

$\displaystyle\sum_{\begin{subarray}{c}q\leq Q\\\
(q,b)=1\end{subarray}}\sum_{h(q)}^{*}\Phi_{N}\left(\dfrac{h}{q}+\beta\right)$
$\displaystyle\ll_{b,\gamma}\left(Q+b^{M}\right)^{\frac{2}{\ell}}\left(Q+b^{N-2M}\right)^{\frac{1}{K}}Q^{\frac{2}{\ell}}b^{N-\frac{N}{K}-\frac{2M}{\ell}+\frac{2M}{K}+\gamma
N}\left(1+\dfrac{cb^{2}}{K}+\dfrac{c}{\sqrt{K}}\right)^{\frac{N-2M}{K}}$ (38)
$\displaystyle\ll_{b}\left(Q+b^{\delta
N}\right)^{1-1/2K}\left(Q+b^{N(1-2\delta)}\right)^{1/K}Q^{1-1/2K}b^{N(1-\delta-\frac{1}{K}L(\delta,b,K,\gamma))},$

where

$\displaystyle L(\delta,b,K,\gamma)$
$\displaystyle:=1-\dfrac{5\delta}{2}-\gamma
K-(1-2\delta)\log_{b}\left(1+\dfrac{cb^{2}}{K}+\dfrac{c}{\sqrt{K}}\right)$
$\displaystyle\geq\dfrac{5\epsilon}{2}-\gamma
K-\dfrac{1}{3}\log_{b}\left(1+\dfrac{cb^{2}}{K}+\dfrac{c}{\sqrt{K}}\right).$

The last line holds by the assumption
$\frac{1}{3}\leq\delta\leq\frac{2}{5}-\epsilon$. We may choose
$K\asymp_{b,\epsilon}1$ large enough and $\gamma\ll_{b,\epsilon}1$ small
enough so that

$\gamma
K+\dfrac{1}{3}\log_{b}\left(1+\dfrac{cb^{2}}{K}+\dfrac{c}{\sqrt{K}}\right)\leq\dfrac{3\epsilon}{2},$

say. For any such choice, $L(\delta,b,K,\gamma)\geq\epsilon$. This and the
assumption $Q\gg_{b,\epsilon}b^{\delta N}\geq b^{(1-2\delta)N}$ for
$\delta\geq 1/3$ implies (38) is
$\ll_{b,\epsilon}Q^{2}b^{N(1-\delta-\epsilon/K)}.$ Thus if we take
$\sigma_{1}(b,\epsilon)=\epsilon/K$ we see that (36) and hence (37) hold in
our case of $Q\gg_{b,\epsilon}b^{\delta N}$.

Next we treat the case when $Q\ll_{b,\epsilon}b^{\delta N}$. Here one observes
that the right hand sides of (36) and (37) are
$\gg_{b,\epsilon}b^{N}Q^{1-\frac{\sigma_{1}(b,\epsilon)}{\delta}}$ and
$\gg_{b,\epsilon}b^{N}Q^{1-\frac{\sigma_{1}(b,\epsilon)}{\delta}}e^{-\sigma_{\infty}(b)N/\log
Q}$, respectively. It thus suffices to show that the left hand sides of (36)
and (37) are
$\ll_{b,\epsilon}b^{N}Q^{1-\frac{\sigma_{1}(b,\epsilon)}{\delta}}$ and
$\ll_{b,\epsilon}b^{N}Q^{1-\frac{\sigma_{1}(b,\epsilon)}{\delta}}e^{-\sigma_{\infty}(b)N/\log
Q}$, respectively. We treat these two in similar fashion (but with a small
difference) as follows.

Since $Q\ll_{b,\epsilon}b^{\delta N}$ by assumption, we can find an integer
$1\leq M<N-1$ such that $b^{\delta(N-M)}\asymp_{b,\epsilon}Q$. For any such
choice of $M$, we split the products according to whether $n\leq M$ or
$M<n<N$. This yields that the left hand sides of (36) and (37) are $\leq
b^{M}\mathscr{Z}$ (with $\mathscr{Z}$ defined below in (39)) and

$\leq\mathscr{Z}\max_{\begin{subarray}{c}h\in\mathbb{Z}\\\ 2\leq q\leq Q\\\
(q,h(b^{3}-b))=1\end{subarray}}\prod_{1\leq n\leq
M}\phi_{b}\left(\left(\dfrac{h}{q}+\dfrac{k}{b^{3}-b}\right)\left(b^{n}+b^{2N-n}\right)\right)$

respectively, where

(39) $\mathscr{Z}:=\sup_{\beta\in\mathbb{R}}\sum_{\begin{subarray}{c}q\leq
Q\\\
(q,b)=1\end{subarray}}\sum_{h(q)}^{*}\prod_{M<n<N}\phi_{b}\left(\left(\dfrac{h}{q}+\beta\right)\left(b^{n}+b^{2N-n}\right)\right).$

With regards to the product over $1\leq n\leq M$ above, Proposition 5.2
implies it is

$\ll_{b}b^{M}\exp\left(-\sigma_{\infty}(b)\dfrac{M}{\log
Q}\right)\ll_{b,\epsilon}b^{M}\exp\left(-\sigma_{\infty}(b)\dfrac{N}{\log
Q}\right).$

Note we used the assumption $b^{\delta(N-M)}\asymp_{b,\epsilon}Q$ implying
$M=N-\frac{1}{\delta}\log_{b}Q+O_{b,\epsilon}(1)$. Similarly as done
previously, one can show that

$\sum_{\begin{subarray}{c}q\leq Q\\\
(q,b)=1\end{subarray}}\sum_{h(q)}^{*}\prod_{M<n<N}\phi_{b}\left(\left(\dfrac{h}{q}+\beta\right)\left(b^{n}+b^{2N-n}\right)\right)=\sum_{\begin{subarray}{c}q\leq
Q\\\
(q,b)=1\end{subarray}}\sum_{h(q)}^{*}\Phi_{N-M}\left(\dfrac{h}{q}+b^{M}\beta\right).$

Recall that $b^{\delta(N-M)}\asymp_{b,\epsilon}Q$ by assumption. Since we
already showed above that (36) holds for arbitrary $N\geq 1$ when
$Q\gg_{b,\epsilon}b^{\delta N}$ (and in particular when
$Q\asymp_{b,\epsilon}b^{\delta N}$) we may apply this to our case of
$Q\asymp_{b,\epsilon}b^{\delta(N-M)}$ (substituting $N$ there with $N-M$
here). This shows

$\mathscr{Z}\ll_{b,\epsilon}Q^{2}b^{(N-M)(1-\delta-\sigma_{1}(b,\epsilon))}+Q^{1-\frac{\sigma_{1}(b,\epsilon)}{\delta}}b^{N-M}\asymp_{b,\epsilon}Q^{1-\frac{\sigma_{1}(b,\epsilon)}{\delta}}b^{N-M}.$

It follows that (36) and (37) also hold when $Q\ll_{b,\epsilon}b^{\delta N}$
and we thus conclude the proof. ∎

##  8\. Equidistribution estimate

In this section we prove Theorem 1.5. First we need the following fact.

######  Lemma 8.1.

For an integer $N\geq 0$, let $\Pi_{b}(2N)$ be as defined in (23) and let

$\Pi_{b}^{*}(2N):=\left\\{n\in\Pi_{b}(2N)\ :\ (n,b^{3}-b)=1\right\\}.$

We have $\\#\Pi_{b}(2N)=(b-1)b^{N}$ and

(40)
$\\#\Pi_{b}^{*}(2N)=\gamma_{2}(b)\dfrac{\varphi(b^{3}-b)}{b^{3}-b}\\#\Pi_{b}(2N)+O\left(b^{2}\tau(b^{2}-1)\right),$

where

$\gamma_{2}(b):=\begin{cases}b/(b-1)&\mbox{ if $b$ is even,}\\\ 1&\mbox{
otherwise.}\end{cases}$

Moreover $\\#\mathscr{P}_{b}^{*}(x)\asymp_{b}\sqrt{x}$ for $x\geq 1$.

###### Proof.

Every integer $n\in\Pi_{b}(2N)$ can be written uniquely as

$\displaystyle n$ $\displaystyle=n_{N}b^{N}+\sum_{0\leq
j<N}n_{j}\left(b^{j}+b^{2N-j}\right)$ $\displaystyle=n_{N}b^{N}+2\sum_{0\leq
j<N}n_{j}b^{j}+\sum_{0\leq j<N}n_{j}\left(b^{2N-j}-b^{j}\right)$

for some unique digits $0\leq n_{j}<b$ with $n_{0}>0$. Thus
$\\#\Pi_{b}(2N)=(b-1)b^{N}$. We note that every term of the right-most sum
above is divisible by $b^{2}-1$. Then

$(n,b^{2}-1)=\left(n_{N}b^{N}+2\sum_{0\leq j<N}n_{j}b^{j},\ b^{2}-1\right).$

Since $(n,b)=(n_{0},b)$ and $b^{3}-b=b(b^{2}-1)$, it follows

$\displaystyle\\#\Pi_{b}^{*}(2N)$
$\displaystyle=\sum_{\begin{subarray}{c}0\leq n_{0},\ldots,n_{N}<b\\\
(n_{0},b)=(n_{N}b^{N}+2\sum_{0\leq j<N}n_{j}b^{j},b^{2}-1)=1\end{subarray}}1$
$\displaystyle=\sum_{\begin{subarray}{c}0\leq n_{0}<b\\\
(n_{0},b)=1\end{subarray}}\sum_{0\leq n_{N}<b}\sum_{\begin{subarray}{c}0\leq
n<b^{N-1}\\\ (n_{N}b^{N}+2n_{0}+2bn,b^{2}-1)=1\end{subarray}}1$
$\displaystyle=\sum_{\begin{subarray}{c}0\leq n_{0}<b\\\
(n_{0},b)=1\end{subarray}}\sum_{\begin{subarray}{c}0\leq n_{N}<b\\\
(n_{N},2)=1\text{ if }(b,2)=1\end{subarray}}\sum_{\begin{subarray}{c}0\leq
n<b^{N-1}\\\ (n_{N}b^{N}+2n_{0}+2bn,b^{2}-1)=1\end{subarray}}1.$

The equality before the last follows from the unique representation of
integers in base $b$. The last equality follows from the fact that if $b$ is
odd, whence $b^{2}-1$ is even, then

$\left(n_{N}b^{N}+2n_{0}+2bn,\ b^{2}-1\right)=1$

implies $n_{N}$ is odd.

The inner sum equals $S(n_{N}b^{N}+2n_{0})$, where for an integer $a$,

$S(a):=\sum_{\begin{subarray}{c}0\leq n<b^{N-1}\\\
(a+2bn,b^{2}-1)=1\end{subarray}}1.$

If $b$ odd and $a$ is even, $S(a)=0$. Thus we assume $a$ is odd if so is $b$.
By the Möbius inversion formula
$\mathbf{1}_{(m,n)=1}=\sum_{d\mid(m,n)}\mu(d)$, we have

$S(a)=\sum_{d\mid(b^{2}-1)}\mu(d)\sum_{\begin{subarray}{c}0\leq n<b^{N-1}\\\
2bn\equiv-a(d)\end{subarray}}1.$

If $b$ is odd and $2bn\equiv-a(d)$, then $d$ is odd as so is $a$ by
assumption. In the case when $b$ is even, $b^{2}-1$ is odd and so is any
divisor $d$ of $b^{2}-1$. Thus $d$ runs over odd divisors of $b^{2}-1$
regardless. These are also coprime to $b$ as $(b^{2}-1,b)=1$. Letting
$\overline{2b}$ denote the inverse of $2b$ modulo $d$, the above is

$\displaystyle S(a)$ $\displaystyle=\sum_{\begin{subarray}{c}d\mid(b^{2}-1)\\\
(d,2)=1\end{subarray}}\mu(d)\sum_{\begin{subarray}{c}0\leq n<b^{N-1}\\\
n\equiv-\overline{2b}a(d)\end{subarray}}1=\sum_{\begin{subarray}{c}d\mid(b^{2}-1)\\\
(d,2)=1\end{subarray}}\mu(d)\left(\dfrac{b^{N-1}}{d}+O(1)\right)$
$\displaystyle=\gamma(b)\dfrac{\varphi(b^{2}-1)}{b^{2}-1}b^{N-1}+O(\tau(b^{2}-1))$

uniformly in $a$, where

$\gamma(b):=\begin{cases}1&\mbox{ if $b$ is even}\\\ 2&\mbox{ if $b$ is
odd}.\end{cases}$

Now (40) follows after we insert this into the expression for
$\\#\Pi_{b}^{*}(2N)$ above, compute the resulting sum and recall that
$\\#\Pi_{b}(2N)=(b-1)b^{N}$.

We now establish $\sqrt{x}\ll_{b}\\#\mathscr{P}_{b}^{*}(x)\ll_{b}\sqrt{x}$ for
$x\geq 1$. Since $\mathscr{P}_{b}^{*}(x)\subseteq\mathscr{P}_{b}(x)$ and
$\\#\mathscr{P}_{b}(x)\asymp_{b}\sqrt{x}$, the upper bound holds. To show
$\\#\mathscr{P}_{b}^{*}(x)\gg_{b}\sqrt{x}$, we first note that since
$1\in\mathscr{P}_{b}^{*}(x)$, the lower bound holds for $\log_{b}x$ bounded
and we may assume then that $\log_{b}x$ is arbitrarily large. In this case,
let $N$ be the largest integer such that
$\Pi_{b}(2N)\subseteq\mathscr{P}_{b}(x)$. Clearly $b^{N}\asymp_{b}\sqrt{x}$
and $\\#\mathscr{P}_{b}^{*}(x)\geq\\#\Pi_{b}^{*}(2N)\asymp_{b}b^{N}$ for $N$
large. ∎

###### Proof of Theorem 1.5.

Let $y\leq x$. Since every $b$-palindromic integer $n\geq 1$ with
$\lfloor\log_{b}n\rfloor$ odd is divisible by $b+1$, and $b+1>1$ is a divisor
of $b^{3}-b$, it follows

$\mathscr{P}^{*}_{b}(y)=\left\\{n\in\mathscr{P}_{b}^{0}(y)\ :\
(n,b^{3}-b)=1\right\\}.$

Then by this and the Möbius inversion formula
$\mathbf{1}_{(b^{3}-b,n)=1}=\sum_{r\mid(b^{3}-b,n)}\mu(r)$, we have

$\\#\mathscr{P}_{b}^{*}(y,a,q)-\dfrac{\\#\mathscr{P}_{b}^{*}(y)}{q}=\sum_{r\mid(b^{3}-b)}\mu(r)\sum_{\begin{subarray}{c}n\in\mathscr{P}_{b}^{0}(y)\\\
r\mid n\end{subarray}}\left(\mathbf{1}_{n\equiv a(q)}-\dfrac{1}{q}\right).$

Note

$\mathbf{1}_{r\mid n}=\dfrac{1}{r}\sum_{k(r)}e_{r}(nk)$

and

$\mathbf{1}_{n\equiv a(q)}-\dfrac{1}{q}=\dfrac{1}{q}\sum_{1\leq
h<q}e_{q}(-ah)e_{q}(nh).$

Inserting these expressions above, switching orders of summation and taking
absolute values, we obtain

$\displaystyle\left|\\#\mathscr{P}_{b}^{*}(y,a,q)-\dfrac{\\#\mathscr{P}_{b}^{*}(y)}{q}\right|\leq\sum_{r\mid(b^{3}-b)}\dfrac{1}{r}\sum_{k(r)}\dfrac{1}{q}\sum_{1\leq
h<q}\left|\sum_{n\in\mathscr{P}_{b}^{0}(y)}e\left(\left(\dfrac{h}{q}+\dfrac{k}{r}\right)n\right)\right|$
$\displaystyle\leq b^{2}\sum_{0\leq N\leq\frac{1}{2}\log_{b}x}\sum_{0\leq
M\leq N}\sum_{r\mid(b^{3}-b)}\dfrac{1}{r}\sum_{k(r)}\dfrac{1}{q}\sum_{1\leq
h<q}\Phi_{M}\left(\dfrac{b^{N-M}h}{q}+\dfrac{b^{N-M}k}{r}\right)$

uniformly in $a\in\mathbb{Z}$ and $y\leq x$, by Lemma 5.1 and a switch in the
order of summation. If $(q,b)=1$, we may substitute $b^{N-M}h$ with $h$ above.
Thus for any $Q\geq 1$,

$\displaystyle\sum_{\begin{subarray}{c}q\leq Q\\\
(q,b^{3}-b)=1\end{subarray}}\sup_{y\leq
x}\max_{a\in\mathbb{Z}}\left|\\#\mathscr{P}_{b}^{*}(y,a,q)-\dfrac{\\#\mathscr{P}_{b}^{*}(y)}{q}\right|$
$\displaystyle\leq b^{2}\sum_{0\leq N\leq\frac{1}{2}\log_{b}x}\sum_{0\leq
M\leq
N}\sum_{r\mid(b^{3}-b)}\dfrac{1}{r}\sum_{k(r)}\sum_{\begin{subarray}{c}q\leq
Q\\\ (q,b^{3}-b)=1\end{subarray}}\dfrac{1}{q}\sum_{1\leq
h<q}\Phi_{M}\left(\dfrac{h}{q}+\dfrac{b^{N-M}k}{r}\right)$ $\displaystyle\leq
b^{2}\tau(b^{3}-b)\sum_{0\leq N\leq\frac{1}{2}\log_{b}x}\sum_{0\leq M\leq
N}\max_{\begin{subarray}{c}r\mid(b^{3}-b)\\\
k\in\mathbb{Z}\end{subarray}}\sum_{\begin{subarray}{c}q\leq Q\\\
(q,b^{3}-b)=1\end{subarray}}\dfrac{1}{q}\sum_{1\leq
h<q}\Phi_{M}\left(\dfrac{h}{q}+\dfrac{k}{r}\right)$ (41)
$\displaystyle=b^{2}\tau(b^{3}-b)\sum_{0\leq
N\leq\frac{1}{2}\log_{b}x}\sum_{0\leq M\leq
N}\max_{\begin{subarray}{c}k\in\mathbb{Z}\end{subarray}}S(M,Q,k),$

where

$S(M,Q,k):=\sum_{\begin{subarray}{c}q\leq Q\\\
(q,b^{3}-b)=1\end{subarray}}\dfrac{1}{q}\sum_{1\leq
h<q}\Phi_{M}\left(\dfrac{h}{q}+\dfrac{k}{b^{3}-b}\right).$

Splitting the sum according to the GCD of $h,q$ and substituting variables, we
have

$S(M,Q,k)\leq\sum_{d\leq Q/2}\dfrac{1}{d}\sum_{\begin{subarray}{c}2\leq q\leq
Q/d\\\
(q,b^{3}-b)=1\end{subarray}}\dfrac{1}{q}\sum_{h(q)}^{*}\Phi_{M}\left(\dfrac{h}{q}+\dfrac{k}{b^{3}-b}\right).$

We now split the sum over $2\leq q\leq Q/d$ into $\ll\log Q/d$ sums over
dyadic segments $(R/2,R]$ with $2\leq R\leq Q/d$. Let $0<\epsilon\leq 1/15$
and consider the contribution of those $q$ in any one such interval $(R/2,R]$.
Bounding $1/q$ and applying Proposition 7.1 with $\delta=2/5-\epsilon$, we get

$\displaystyle\sum_{\begin{subarray}{c}R/2<q\leq R\\\
(q,b^{3}-b)=1\end{subarray}}\dfrac{1}{q}\sum_{h(q)}^{*}\Phi_{M}\left(\dfrac{h}{q}+\dfrac{k}{b^{3}-b}\right)\leq\dfrac{2}{R}\sum_{\begin{subarray}{c}2\leq
q\leq R\\\
(q,b^{3}-b)=1\end{subarray}}\sum_{h(q)}^{*}\Phi_{M}\left(\dfrac{h}{q}+\dfrac{k}{b^{3}-b}\right)$
$\displaystyle\ll_{b,\epsilon}\left(Rb^{(\frac{3}{5}+\epsilon-\sigma_{1}(b,\epsilon))M}+\dfrac{b^{M}}{R^{\sigma_{1}(b,\epsilon)}}\right)\exp\left(-\sigma_{\infty}(b)\dfrac{M}{\log
R}\right)$ $\displaystyle\leq
Rb^{(\frac{3}{5}+\epsilon)M}+b^{M}\exp\left(-c(b,\epsilon)\sqrt{M}\right)$

for some $\sigma_{1}(b,\epsilon),c(b,\epsilon),\sigma_{\infty}(b)>0$ depending
at most on $b,\epsilon$. Note we used $e^{-\sigma_{1}(b,\epsilon)\log
R-\sigma_{\infty}(b)M/\log R}\leq e^{-c(b,\epsilon)\sqrt{M}}$ for $R\geq 2$
and $M\geq 0$. Then the combined contribution of the $\ll\log(Q/d)$ dyadic
pieces to the sum over $2\leq q\leq Q/d$ is

$\ll_{b,\epsilon}\dfrac{Q}{d}b^{(\frac{3}{5}+\epsilon)M}+b^{M}\exp\left(-c(b,\epsilon)\sqrt{M}\right)\log
Q.$

Dividing this by $d$ and summing over $1\leq d\leq Q/2$ we obtain

$S(M,Q,k)\ll_{b,\epsilon}Qb^{(\frac{3}{5}+\epsilon)M}+b^{M}\exp\left(-c(b,\epsilon)\sqrt{M}\right)\log^{2}Q$

uniformly in $k\in\mathbb{Z}$. Performing the summations over $M,N$ on the
right hand side of (8) yields, for any $1\leq Q\leq x^{1/5}$ and any
$0<\epsilon\leq 1/30$,

$\sum_{\begin{subarray}{c}q\leq Q\\\ (q,b^{3}-b)=1\end{subarray}}\sup_{y\leq
x}\max_{a\in\mathbb{Z}}\left|\\#\mathscr{P}_{b}^{*}(y,a,q)-\dfrac{\\#\mathscr{P}_{b}^{*}(y)}{q}\right|\ll_{b,\epsilon}Qx^{\frac{3}{10}+\epsilon}+\sqrt{x}\exp\left(-k_{b,\epsilon}\sqrt{\log
x}\right),$

where $k_{b,\epsilon}>0$ is some value depending only on $b,\epsilon$. Since
the above holds for $0<\epsilon\leq 1/30$, it also holds for $\epsilon>1/30$.
Now the result follows when we let $Q=x^{1/5-\epsilon_{0}}$ with
$\epsilon_{0}>0$ arbitrary, fix $\epsilon=\epsilon_{0}/2$, say, and use the
fact $\sqrt{x}\ll_{b}\\#\mathscr{P}_{b}^{*}(x)$ from Lemma 8.1. ∎

##  9\. Palindromic almost-primes

We conclude the work with a proof of Theorem 1.4. To this end we use the
following version of the almost-prime sieve.

######  Lemma 9.1 (Almost-prime linear sieve with Richert’s weights).

Let $(a_{n})$ be a sequence of non-negative real numbers and let $x>2$. For
each integer $d\geq 1$, set

$A_{d}:=\sum_{\begin{subarray}{c}n\leq x\\\ d\mid n\end{subarray}}a_{n}.$

Suppose for each such $d$ that

$A_{d}=Xg(d)+r_{d}$

for some $r_{d}$, real number $X$ and some multiplicative function $g$
satisfying $0\leq g(p)<1$ for each prime $p$ and

$\prod_{u\leq p<v}(1-g(p))^{-1}\leq K\dfrac{\log v}{\log u}$

for any $2\leq u<v\leq x$, where $K>1$ is some constant.

Let $r\geq 2$ be an integer and set

$\Delta_{r}:=r+\dfrac{1}{\log
3}\log\left(\dfrac{3}{4}\left(1+3^{-r}\right)\right).$

Suppose that

$\sum_{d\leq D}|r_{d}|\ll\dfrac{X}{\log^{3}x}$

for some $D$ satisfying $D\geq x^{1/\Delta_{r}+\epsilon}$ for some
$\epsilon>0$. Then for $z=D^{1/4}$, we have

$\sum_{\begin{subarray}{c}n\leq x\\\ P^{-}(n)\geq z\\\ \Omega(n)\leq
r\end{subarray}}a_{n}\asymp_{r,\epsilon}X\prod_{p<x}(1-g(p)).$

###### Proof.

See Chapter 25 in [11]. In particular see Theorem 25.1 and Equations 25.23,
25.25, page 479. ∎

###### Proof of Theorem 1.4.

We may assume that $x\gg_{b}1$ is large enough so that $z:=x^{1/21}$ is much
larger than $b^{3}-b$. For each integer $n\geq 1$, define
$a_{n}:=\mathbf{1}_{n\in\mathscr{P}^{*}_{b}}$ and note

$S:=\sum_{\begin{subarray}{c}n\in\mathscr{P}_{b}(x)\\\ P^{-}(n)\geq z\\\
\Omega(n)\leq
6\end{subarray}}1=\sum_{\begin{subarray}{c}n\in\mathscr{P}_{b}^{*}(x)\\\
P^{-}(n)\geq z\\\ \Omega(n)\leq
6\end{subarray}}1=\sum_{\begin{subarray}{c}n\leq x\\\ P^{-}(n)\geq z\\\
\Omega(n)\leq 6\end{subarray}}a_{n}.$

For any integer $d\geq 1$, set

$A_{d}:=\sum_{\begin{subarray}{c}n\leq x\\\ d\mid
n\end{subarray}}a_{n}=\\#\mathscr{P}_{b}^{*}(x,0,d).$

We can write this as

$A_{d}=g(d)\\#\mathscr{P}_{b}^{*}(x)+r_{d},$

where

$g(d)=\dfrac{\mathbf{1}_{(d,b^{3}-b)=1}}{d}$

and

$r_{d}=\\#\mathscr{P}_{b}^{*}(x,0,d)-g(d)\\#\mathscr{P}_{b}^{*}(x).$

Clearly $g$ is multiplicative, satisfies $0\leq g(p)<1$ for each prime $p$ and

$\prod_{u\leq p<v}(1-g(p))^{-1}\leq\prod_{u\leq
p<v}\left(1-\dfrac{1}{p}\right)^{-1}=\dfrac{\log v}{\log
u}\left(1+O\left(\dfrac{1}{\log u}\right)\right)$

for any $2\leq u<v\leq x$, by the Mertens’ theorems.

Set $D:=z^{4}=x^{4/21}=x^{1/5-1/105}$. Since every number in
$\mathscr{P}_{b}^{*}$ is coprime to $b^{3}-b$,

$\sum_{d\leq D}|r_{d}|=\sum_{\begin{subarray}{c}d\leq D\\\
(d,b^{3}-b)=1\end{subarray}}\left|\\#\mathscr{P}_{b}^{*}(x,0,d)-\dfrac{\\#\mathscr{P}_{b}^{*}(x)}{d}\right|\ll_{b}\dfrac{\\#\mathscr{P}_{b}^{*}(x)}{\log^{10}x}$

by Theorem 1.5. For $\Delta_{6}$ defined as in Lemma 9.1, one can check that
$x^{1/\Delta_{6}+1/100}\leq D$. Then all the assumptions of Lemma 9.1 are
satisfied. It gives

$S\asymp_{b}\\#\mathscr{P}_{b}^{*}(x)\prod_{p<x}\left(1-g(p)\right)\asymp_{b}\dfrac{\\#\mathscr{P}_{b}(x)}{\log
x}$

as required. ∎

## References

  * [1] C. Aistleitner, G. Larcher, F. Pillichshammer, S. S. Eddin, R. F. Tichy, On Weyl products and uniform distribution modulo one, Monatshefte für Mathematik (2018), 185, 365–395
  * [2] W.D. Banks, Every natural number is the sum of forty-nine palindromes, Preprint, 2015, arXiv 1508.04721v1.pdf
  * [3] W.D. Banks, D. Hart and M. Sakata, Almost all palindromes are composite, Mathematical Research Letters 11 (2004) nos.5-6, pp.853–868
  * [4] W.D. Banks, I.E. Shparlinski, Prime divisors of palindromes, Period. Math. Hungar. 51 (2005), 1–10.
  * [5] J. Bourgain, Mordell’s exponential sum estimate revisited, Journal of AMS (2005) v.18, n.2, 477–499
  * [6] J. Bourgain, Prescribing the binary digits of primes, II, Israel Journal of Mathematics, v. 206, p. 165–182 (2015)
  * [7] J. Cilleruelo, F. Luca, L. Baxter, Every positive integer is a sum of three palindromes, Math. of Comput. 87(314), (2018)
  * [8] S. Col, Palindromes dans les progressions arithmétiques, Acta Arith. 137, n.1, (2009), 1–41
  * [9] G. Fici, L.Q. Zamboni, On the least number of palindromes contained in an infinite word, Theoretical Computer Science v.481 (2013), 1–8
  * [10] K. Ford, Sieve methods lecture notes, 2020 https://faculty.math.illinois.edu/~ford/sieve2020.pdf
  * [11] J. Friedlander and H. Iwaniec, Opera de Cribro, Colloquium Publications, v.57, Providence, RI, 2010
  * [12] Z. Gao, Enumeration of self-reciprocal irreducible monic polynomials with prescribed leading coefficients over a finite field, Finite Fields and their Application, v.83, (2022), 102083
  * [13] T. Garefalakis and G. Kapetanakis, On the Hansen-Mullen conjecture for self-reciprocal irreducible polynomials, Finite Fields Appl. 69 (2012), 832–841
  * [14] A. O. Gelfond, Sur les nombres qui ont des propriétés additives et multiplicatives données, Acta Arithmetica, 13, (1968), p.259–265
  * [15] Google Cloud Blog, Even more pi in the sky: Calculating 100 trillion digits of pi on Google Cloud, 2022 (last visited on July 29, 2023)
  * [16] D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, New York, 1997
  * [17] J. Hofbauer, A simple proof of $1+1/2^{2}+1/3^{2}+\cdots=\pi^{2}/6$ and related identities, Am. Math. Mon., v.109, n.2 (2002), p.196–200.
  * [18] H. Iwaniec, Almost-primes represented by quadratic polynomials, Inventiones Mathematicae. 47 (2), (1978), 178–188
  * [19] H. Iwaniec and E. Kowalski, Analytic number theory, Colloquium Publications, v.53, American Mathematical Society, Providence, RI, 2004
  * [20] L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley, New York, 1974
  * [21] S. Larionov, A. Loskutov, E. Ryadchenko, Chromosome evolution with naked eye: palindromic context of the life origin, Chaos. 18, n.1, 013105 (2008)
  * [22] C. Mauduit and J. Rivat, La somme des chiffres des carrés, Acta Math., 203 (2009), 107–148
  * [23] C. Mauduit and J. Rivat, Sur un problème de Gelfond : la somme des chiffres des nombres premiers, Annals of Math., v.171 no.3 (2010), http://annals.math.princeton.edu/wp-content/uploads/annals-v171-n3-p04-p.pdf
  * [24] J. Maynard, Primes with restricted digits, Inventiones Mathematicae, v.217, p. 127–218 (2019)
  * [25] J. Morgenbesser, Gelfond’s sum of digits problems, Vienna University of Tech., Diploma thesis, http://dmg.tuwien.ac.at/drmota/morgenbesserda.pdf
  * [26] A.H.L. Porto, V.C. Barbosa, Finding approximate palindromes in strings, Pattern recognition, v.35 n.11 (2002), 2581–2591
  * [27] A. Rajasekaran, J. Shallit, T. Smith, Additive number theory via automata theory, Theory of Computing Systems 64 (2020), 542–567
  * [28] R.M. Sheldon, The SATOR rebus: An unsolved cryptogram?, Cryptologia, v.27 (2003), 233–287
  * [29] SigmaGeek, Find large palindromic prime numbers in the decimal expansion of $\pi$ ($3,1415\ldots$), 2022 (last visited on July 29, 2023)
  * [30] T. Tao, Every odd number greater than $1$ is the sum of at most five primes, Math. of Comput., v.83, n.286, (2014), p. 997–1038
  * [31] G. Tenenbaum, Introduction to analytic and probabilistic number theory, Cambridge studies in advanced mathematics: 46, Cambridge University press, 1995