2. Uniform bounds on the partial sums of multiplicative functions: Proof of Theorem 1.1

We start by removing $n \le x$ that are either z-smooth or have a repeated prime factor exceeding y. Since $|f(n)| \le 1$, the contribution of the former n is bounded in absolute value by $\Psi(x, z)$, while that of the latter n is absolutely bounded by

\begin{equation*}\sum_{p \gt y} \sum_{\substack{n \le x\\p^2\mid n}} 1 \le x\sum_{p \gt y} \frac1{p^2} \ll \frac x{y \log y},\end{equation*}

which is also absorbed in the expressions given in the claimed bounds.

It remains to deal with the sum of f(n) over the surviving n, namely, those that have $P^+(n) \gt z$ and no repeated prime factor exceeding y; we denote this sum by ${\sum\nolimits_{n \le x}^* f(n)}$. Such n can be uniquely written in the form $m P_j \cdots P_1$ for some $j \ge 1$, where $P_1 := P^+(n) \gt z$ and $P^+(m) \le y \lt P_j \lt \dots \lt P_1$. As such $f(n) = f(m) f(P_j) \cdots f(P_1)$ and

\begin{align*} {\sum\nolimits_{n \le x}^* f(n)} &= \sum_{j \ge 1} {\sum_{\substack{m \le x\\P^+(m) \le y}}} f(m) \sum_{\substack{P_1, \dots, P_j\\ P_1 \gt z,\ P_j \cdots P_1 \le x/m\\y \lt P_j \lt \dots \lt P_1}} f(P_j) \cdots f(P_1)\nonumber\\ &= {\sum_{j \ge 1}} {\sum_{\substack{m \le x\\P^+(m) \le y}}} f(m) \sum_{\substack{P_2, \dots, P_j\\P_j \cdots P_2 \le x/mz\\y \lt P_j \lt \dots \lt P_2\\}} f(P_j) \cdots f(P_2) \nonumber\\ &\quad \times\sum_{\max\{P_2, z\} \lt P_1 \le x/m P_2 \cdots P_j} f(P_1). \end{align*}

Here $\max\{P_2, z\}$ is to be replaced by ‘z’ in the case j = 1. In that case, the sum on $P_2, \dots, P_j$ should also be interpreted as $1$. The same applies in analogous expressions below.

Invoking the hypothesis (1.1) for the innermost sum on P ₁, the total size of the resulting error term is

\begin{equation*}\ll Mx {\mathcal E}(y) {\sum_{j \ge 1}} \sum_{\substack{m, P_2, \dots, P_j\\ mP_2 \cdots P_j \le x/z\\P^+(m) \le y \lt P_j \lt \dots \lt P_2}} \frac1{mP_2 \cdots P_j} \le Mx {\mathcal E}(y) \sum_{n \le x/z} \frac1n \ll Mx{\mathcal E}(y) \log x.\end{equation*}

We now obtain

(2.1)\begin{align} {\sum\nolimits_{n \le x}^* f(n)} &= \varrho{\sum_{j \ge 1}} \frac1{(j-1)!} {\sum_{\substack{m \le x\\P^+(m) \le y}}} f(m) \sum_{z \lt P_1 \le x/m} {\sum_{\substack{P_2, \dots , P_j \in (y, P_1)\\P_2, \dots, P_{j}\, \text{distinct}\\P_2 \cdots P_j \le x/mP_1}}} f(P_2) \cdots f(P_j)\nonumber\\ &\quad+ O(Mx{\mathcal E}(y) \log x). \end{align}

Now for $j \ge 2$ and each $i \in \{2, \dots, j\}$, the hypothesis (1.1) yields

(2.2)\begin{align} \sum_{\substack{y \lt P_i \le x/mP_1 \cdots P_{i-1}P_{i+1} \cdots P_j \\ P_i \lt P_1,\ r \ne i \implies P_r \ne P_i}} f(P_i) &= \sum_{\substack{y \lt P_i \le x/mP_1 \cdots P_{i-1}P_{i+1} \cdots P_j\\P_i \lt P_1}} f(P_i) + O(j)\nonumber\\ &= \varrho\sum_{\substack{y \lt P_i \le x/mP_1 \cdots P_{i-1}P_{i+1} \cdots P_j\\P_i \lt P_1,\ r \ne i \implies P_r \ne P_i}} 1 \nonumber\\ &\quad+ O\left(j + \frac{Mx}{mP_1 \cdots P_{i-1}P_{i+1} \cdots P_j} {\mathcal E}(y)\right). \end{align}

In order to estimate the innermost sum in the main term of (2.1), we invoke this estimate successively for all $j \ge 2$ and each $i \in \{2, \dots, j\}$. Indeed

\begin{align*} {\sum_{\substack{P_2, \dots , P_j \in (y, P_1)\\P_2, \dots, P_{j}\, \text{distinct}\\P_2 \cdots P_j \le x/mP_1}}} f(P_2) \cdots f(P_j) &= \sum_{\substack{P_3, \dots, P_j \in (y, P_1)\\P_3, \dots, P_{j}\, \text{distinct}\\P_3 \cdots P_j \le x/myP_1}} f(P_3) \cdots f(P_j) \sum_{\substack{y \lt P_2 \le x/mP_1 P_3 \cdots P_j \\ P_2 \lt P_1,\ r \ne 2 \implies P_2 \ne P_r}} f(P_2)\nonumber\\ &= \varrho \sum_{\substack{P_2, \dots, P_j \in (y, P_1)\\P_2, \dots, P_{j}\,\text{distinct}\\P_2 \cdots P_j \le x/mP_1}} f(P_3) \cdots f(P_j) + O(\widetilde{{\mathcal E}}), \end{align*}

where

\begin{equation*}\widetilde{{\mathcal E}} := j {\sum_{\substack{P_2, \dots, P_{j-1} \in (y, P_1)\\P_2, \dots, P_{j-1}\, \text{distinct}\\P_2 \cdots P_{j-1} \le x/myP_1}}} 1 + \frac{Mx {\mathcal E}(y)}{mP_1} {\sum_{\substack{P_2, \dots, P_{j-1} \in (y, P_1)\\P_2, \dots, P_{j-1}\, \text{distinct}\\P_2 \cdots P_{j-1} \le x/myP_1}}} \frac1{P_2 \cdots P_{j-1}},\end{equation*}

and we have noted that the error term resulting from the application of (2.2) for i = 2 is, by relabelling, equal to $\widetilde{{\mathcal E}}$. Likewise, invoking (2.2) for $i = 3, \dots, j$ to successively remove the $f(P_3), \dots, f(P_j)$, we obtain

\begin{equation*}{\sum_{\substack{P_2, \dots , P_j \in (y, P_1)\\P_2, \dots, P_j \, \text{distinct}\\P_2 \cdots P_j \le x/mP_1}}} f(P_2) \cdots f(P_j) = \varrho^{j-1} {\sum_{\substack{P_2, \dots , P_j \in (y, P_1)\\P_2, \dots, P_j \, \text{distinct}\\P_2 \cdots P_j \le x/mP_1}}} 1 + O((j-1) \widetilde{{\mathcal E}}).\end{equation*}

Substituting this into (2.1) for each $j \ge 2$, we obtain an error term of size

\begin{equation*} \begin{array}{l} \ll \sum_{j \ge 2} \frac1{(j-1)!} \sum\limits_{\substack{m \le x\\P^+(m) \le y}} \sum\limits_{z \lt P_1 \le \frac{x}{my^{j-1}}} \Bigg\{j^2 {\sum_{\substack{P_2, \dots, P_{j-1} \in (y, P_1)\\P_2, \dots, P_{j-1}\, \text{distinct}\\P_2 \cdots P_{j-1} \le x/myP_1}}} 1 + \frac{Mxj {\mathcal E}(y)}{mP_1} \\ \quad\times{\sum_{\substack{P_2, \dots, P_{j-1} \in (y, P_1)\\P_2, \dots, P_{j-1}\, \text{distinct}\\P_2 \cdots P_{j-1} \le x/myP_1}}} \frac1{P_2 \cdots P_{j-1}}\Bigg\}\\ \ll \sum_{j \ge 2} \frac1{(j-2)!} {\sum_{\substack{m \le x\\P^+(m) \le y}}} \sum_{z \lt P_1 \le \frac{x}{my^{j-1}}} {\sum_{\substack{P_2, \dots, P_{j-1} \in (y, P_1)\\P_2, \dots, P_{j-1}\, \text{distinct}\\P_2 \cdots P_{j-1} \le x/myP_1}}} \Bigg\{\frac{\log x}{\log y} + \frac{Mx {\mathcal E}(y)}{mP_1 \cdots P_{j-1}}\Bigg\}\\ \ll \sum_{j \ge 2} \sum_{\substack{m, P_1, \dots, P_{j-1}\\ mP_1 \cdots P_{j-1} \le x/y\\P_1 \gt z, P^+(m) \le y \lt P_{j-1} \lt \dots \lt P_1}} \left(\frac{\log x}{\log y} + \frac{Mx {\mathcal E}(y)}{m P_1 \cdots P_{j-1}} \right)\\ \ll \frac{\log x}{\log y} \cdot \sum_{n \le x/y} 1 + M x {\mathcal E}(y) \sum_{n \le x/y} \frac1n \ll {Mx(\log x}) \left({\mathcal E}(y) + \frac1{y\log y}\right), \end{array} \end{equation*}

where we have noted that $y^j \le x$ and omitted $(j-2)!$ to reintroduce the ordering on $P_2, \dots, P_{j-1}$. This leads to the estimate

(2.3)\begin{align} {\sum\nolimits_{n \le x}^* f(n)} = \varrho{\sum_{j \ge 1}} \frac{\varrho^{j-1}}{(j-1)!} {\sum_{\substack{m \le x\\P^+(m) \le y}}} f(m) \sum_{\substack{P_1, \dots, P_j\\P_1 \gt z;\ P_1 \cdots P_j \le x/m\\P_2 \cdots P_j \in (y, P_1)\, \text{distinct}}} 1\nonumber \\ + O\left(Mx (\log x) \left({\mathcal E}(y) + \frac1{y\log y}\right)\right). \end{align}

Now the main term above is absolutely bounded by

\begin{equation*} \begin{array}{ll} |\varrho|{\sum_{j \ge 1}} \frac{|\varrho|^{j-1}}{(j-1)!} {\sum_{\substack{m \le x\\P^+(m) \le y}}} |f(m)| &\sum_{\substack{P_2, \dots, P_j \in (y, x)\\P_2 \cdots P_j \le x/mz}} \sum_{z \lt P_1 \le x/mP_2 \cdots P_j} 1\\ &\ll \frac{|\varrho| x}{\log z}{\sum_{j \ge 1}} \frac{|\varrho|^{j-1}}{(j-1)!} \\ &\quad\times{\sum_{\substack{m \le x\\P^+(m) \le y}}} \frac{|f(m)|}m \sum_{\substack{P_2, \dots, P_j \in (y, x)}} \frac1{P_2 \cdots P_j}. \end{array} \end{equation*}

Since $|f(n)|\le 1$ for all n, the sum on m above is no more than

\begin{equation*}\prod_{p \le y} \left(1+\sum_{v \ge 0} \frac{|f(p^v)|}{p^v}\right) \le \exp\left(\sum_{p \le y} \frac{|f(p)|}p + O\left(\sum_{p \le y}\frac1{p^2}\right)\right) \ll \exp\left(\sum_{p \le y} \frac{|f(p)|}p\right).\end{equation*}

On the other hand, the sum on $P_2, \dots, P_j$ is

\begin{equation*}\le \left(\sum_{y \lt p \le x} \frac1p\right)^{j-1} \le \left(\log\left(\frac{\log x}{\log y}\right) + O(1)\right)^{j-1}.\end{equation*}

Collecting estimates, we find that the main term in (2.3) is

\begin{equation*} \begin{array}{ll} \ll \frac{|\varrho| x}{\log z} \exp\left(\sum_{p \le y} \frac{|f(p)|}p\right) {\sum_{j \ge 1}} \frac1{(j-1)!} &\left(|\varrho| \log\left(\frac{\log x}{\log y}\right) + O(1)\right)^{j-1}\\ &\ll \frac{|\varrho| x}{\log z} \left(\frac{\log x}{\log y}\right)^{|\varrho|} \exp\left(\sum_{p \le y} \frac{|f(p)|}p\right), \end{array} \end{equation*}

completing the proof of the theorem.

Remark: We can extend Theorem 1.1 to the case when our multiplicative function f is bounded by some divisor function τ_κ at all positive integers and when $|\varrho| \le \kappa$ (here $\kappa \ge 1$ is a fixed real number). Footnote ¹ We get uniformly for such f satisfying (1.1),

(2.4)\begin{equation} \begin{array}{rcl} \sum_{n \le x} f(n) &\ll& \frac{|\varrho|x}{\log z} \left(\frac{\log x}{\log y}\right)^{|\varrho|} \exp\left(\sum_{p \le y} \frac{|f(p)|}p \right)\\ &&+ \left(x\Psi(x, z) (\log x)^{\kappa^2-1}\right)^{1/2} + Mx \left(\log x\right)^\kappa \left({\mathcal E}(y)+\frac1{y\log y}\right), \end{array} \end{equation}

where $x, y, z, {\mathcal E}$ are as in Theorem 1.1 and the implied constant depends at most on κ and on the implied constant in (1.1).

Indeed by Cauchy–Schwarz and [Reference Hall, Tenenbaum and Divisors10, Theorem 00], the contribution of the z-smooth $n \le x$ is no more (in size) than

\begin{equation*}\sum_{n \le x} {\tau_\kappa}(n) {\mathbb 1}_{P(n) \le z} \le \left(\Psi(x, z) \sum_{n \le x} {\tau_\kappa}(n)^2\right)^{1/2} \ll \left(\frac{x\Psi(x, z)}{\log x} \sum_{n \le x} \frac{{\tau_\kappa}(n)^2}n\right)^{1/2};\end{equation*}

here the hypotheses for Theorem [Reference Hall, Tenenbaum and Divisors10, Theorem 00] follow from Chebyshev’s bounds in conjunction with the fact that

(2.5)\begin{equation} {\tau_\kappa}(p^v) = \binom{\kappa+v-1}v \le \prod_{r \le 10\kappa} \left(1+\frac{\kappa-1}r\right) \cdot \prod_{10\kappa \lt r \le v} \left(1+\frac{\kappa-1}r\right) \le \kappa^{10\kappa} (1.1)^v \ll (1.1)^v. \end{equation}

As such, we obtain

\begin{align*}\sum_{n \le x} {\tau_\kappa}(n) {\mathbb 1}_{P(n) \le z} &\ll \left(\frac{x\Psi(x, z)}{\log x} \prod_{p \le x} \left(1+\sum_{v \ge 1} \frac{{\tau_\kappa}(p^v)^2}{p^v} \right)\right)^{1/2} \\ &\ll \left(\frac{x\Psi(x, z)}{\log x} \exp\left(\sum_{\substack{p \le x\\ \, v \ge 1}} \frac{{\tau_\kappa}(p^v)^2}{p^v} \right)\right)^{1/2}.\end{align*}

Noting that ${\tau_\kappa}(p)=\kappa$ and using (2.5) to bound the last sum above, we deduce that the total contribution of the z-smooth n to the left-hand side of (2.4) is $\ll (x \Psi(x, z) (\log x)^{\kappa^2-1})^{1/2}$, which is absorbed in the right side of (2.4).

Moreover by (2.5), the contribution to the sum $\sum_{n \le x} f(n)$ from all n divisible by the square of a prime exceeding y is no more than

\begin{equation*}\sum_{\substack{p \gt y\\v \ge 2}} \sum_{n \le x:\, p^v \parallel n} {\tau_\kappa}(n) \le \sum_{\substack{p \gt y\\v \ge 2}} {\tau_\kappa}(p^v) \sum_{m \le x/p^v} {\tau_\kappa}(m) \ll x(\log x)^{\kappa-1} \sum_{\substack{p \gt y\\v \ge 2}} \left(\frac{1.1}p\right)^v \ll \frac{x(\log x)^{\kappa}}{y \log y},\end{equation*}

which is also absorbed in the right-hand side of (2.4). Here we have used the crude bound

(2.6)\begin{equation} \begin{array}{rcl} \sum_{n \le X} \tau_{\kappa}(n) &=& \sum_{n \le X} \sum_{d \mid n} \tau_{\kappa-1}(d) = \sum_{d \le X} \tau_{\kappa-1}(d) \sum_{\substack{n \le X\\d \mid n}} 1\\ &\le& X \sum_{d \le X} \frac{\tau_{\kappa-1}(d)}d \le X \prod_{p \le X} \left(1+\frac{\kappa-1}{p} + O\left(\frac1{p^2}\right)\right) \ll X (\log X)^{\kappa-1}. \end{array} \end{equation}

To establish (2.4), it thus remains to bound the sum of f(n) over non z-smooth $n \le x$ having no repeated prime factor exceeding y. To do this, we follow the arguments leading to (2.3), recalling that $|\varrho| \le \kappa$ and $|f(p)| \le \kappa$ for any prime p. The corresponding error term is

\begin{equation*} \begin{array}{l} \ll \sum_{j \ge 2} \frac{\kappa^{j-1}}{(j-2)!} {\sum_{\substack{m \le x\\P^+(m) \le y}}} |f(m)| \sum_{z \lt P_1 \le \frac{x}{my^{j-1}}} j {\sum_{\substack{P_2, \dots, P_{j-1} \in (y, P_1)\\P_2, \dots, P_{j-1}\, \text{distinct}\\P_2 \cdots P_{j-1} \le x/myP_1}}} 1 \\ \qquad + \sum_{j \ge 2} \frac{\kappa^{j-1}}{(j-2)!} {\sum_{\substack{m \le x\\P^+(m) \le y}}} |f(m)| \sum_{z \lt P_1 \le \frac{x}{my^{j-1}}} \frac{Mx {\mathcal E}(y)}{mP_1} {\sum_{\substack{P_2, \dots, P_{j-1} \in (y, P_1)\\P_2, \dots, P_{j-1}\, \text{distinct}\\P_2 \cdots P_{j-1} \le x/myP_1}}} \frac1{P_2 \cdots P_{j-1}} \\ \ll \!\sum_{j \ge 2} \!\sum_{\substack{m, P_1, \dots, P_{j-1}\\ mP_1 \cdots P_{j-1} \le x/y\\P_1 \gt z,\ P^+(m) \le y \lt P_{j-1} \lt \dots \lt P_1}} \!\left( \!\frac{\log x}{\log y} \cdot {\tau_\kappa}(mP_1 \dots P_{j-1}) \!+\! Mx{\mathcal E}(y) \!\cdot\! \frac{{\tau_\kappa}(mP_1 \dots P_{j-1})}{mP_1 P_2 \cdots P_{j-1}} \right)\\ \ll \frac{\log x}{\log y} \cdot \sum_{n \le x/y} {\tau_\kappa}(n) + M x {\mathcal E}(y) \sum_{n \le x/y} \frac{{\tau_\kappa}(n)}n \ll {Mx(\log x)^\kappa} \left({\mathcal E}(y) + \frac1{y \log y}\right). \end{array} \end{equation*}

Here the last step uses (2.6) as well as the bound $\sum_{n \le X} {{\tau_\kappa}(n)}/n \ll (\log {X})^\kappa$ that can be established by the last part of the computation in (2.6). This shows that the analogue of (2.3) holds with $\log x$ in the error term replaced by $(\log x)^\kappa$. Now we simply carry out the rest of the arguments of Theorem 1.1: The only additional point is to note that

\begin{equation*}\sum_{m:\, P^+(m) \le y} \frac{|f(m)|}m \le \prod_{p \le y} \left(1+\sum_{v \ge 1} \frac{|f(p^v)|}{p^v}\right) \ll \exp\left(\sum_{p \le y} \frac{|f(p)|}p \right), \end{equation*}

once again with the last bound coming from the fact that $\sum_{p, v \ge 2} {\tau_\kappa}(p^v)/p^v \ll 1$ by (2.5). This completes the proof of the desired bound (2.4).

3. Equidistribution of the Alladi–Erdős function: Proof of Theorem 1.2

By the orthogonality of the additive characters mod q, we have

(3.1)\begin{equation} \sum_{\substack{n \le x\\A(n) \equiv a\!\!\!\!\! \pmod q}} 1 = \frac xq + \frac1q \sum_{0 \lt r \lt q} \text{e}\left(-\frac{ar}q\right) \sum_{n \le x} \text{e}\left(\frac{rA(n)}q\right). \end{equation}

Let $y := \exp((\log x)^{\epsilon/2})$ and $z := x^{1/\log_2 x}$. Then for each $r \in \{0, 1, \dots , q-1\}$, the multiplicative function $f(n) := e(rA(n)/q)$ satisfies the hypothesis (1.1) with $\varrho : = {\rho _r}: = {1 \over {\phi (q)}}\sum\nolimits_{\scriptstyle v\,\bmod \,q \atop \scriptstyle (v,q) = 1} {\,{\rm{e}}} \,\left( {{{rv} \over q}} \right)$. Indeed by the Siegel-Walfisz theorem (as stated in [Reference Montgomery and Vaughan15, Corollary 11.21]), we find that

(3.2)\begin{equation} \begin{array}{rcl} \sum_{y \lt p \le Y} \text{e}\left(\frac{rA(p)}q\right) &=& \sum_{y \lt p \le Y} \text{e}\left(\frac{rp}q\right) = \sum_{\substack{v \bmod q\\ (v, q)=1}} \text{e}\left(\frac{rv}q\right) \sum_{\substack{y \lt p \le Y\\p \equiv v\!\!\!\!\! \pmod q}} 1\\ &=& \sum_{\substack{v \bmod q\\ (v, q)=1}} \text{e}\left(\frac{rv}q\right) \left\{{\frac1{\phi(q)}} \sum_{\substack{y \lt p \le Y}} 1 + O\left(Y \exp(-C_0\sqrt{\log Y})\right)\right\}\\ &=& \rho_r(\pi(Y) - \pi(y)) + O(\phi(q) Y \exp(-C_0\sqrt{\log y})), \end{array} \end{equation}

uniformly for all $q \le (\log x)^K$ and $Y \ge y$. Here $C_0 \gt 0$ is an absolute constant and we have noted that $(\log x)^K \lt y/2$ for all sufficiently large x (recall that implied constants are allowed to depend on the fixed number K). This verifies hypothesis (1.1), with $\varrho := \rho_r$, $M := \phi(q)$ and ${\mathcal E}(y) := \exp(-C_0\sqrt{\log y})$. From Theorem 1.1, we obtain

(3.3)\begin{equation} \sum_{n \le x} \text{e}\left(\frac{rA(n)}q\right) \ll \frac{|\rho_r| x}{(\log x)^{1-|\rho_r|-2\epsilon/3}} + \frac x{(\log x)^{(1+o(1)) \log_3 x}}, \end{equation}

where we have noted that $\Psi(x, z) \ll x/(\log x)^{(1+o(1)) \log_3 x}$ by well-known results on smooth numbers (for instance [Reference Tenenbaum24, Theorem 5.13 and Corollary 5.19, Chapter III.5]).

The sum ρ_r is a (normalized) Ramanujan sum and is nonzero only if $q'_r := q/(q, r)$ is squarefree (see [Reference Hardy and Wright12] or [Reference Montgomery and Vaughan15] for some standard properties of Ramanujan sums). Moreover, unless q is even and $r=q/2$, we have $q'_r \ge 3$, so that $|\rho_r| \le \frac1{\phi(q'_r)} \le 1/2$. This shows that

(3.4)\begin{align} \sum_{\substack{0 \lt r \lt q\\r \ne q/2}} \left|\sum_{n \le x} \text{e}\left(\frac{rA(n)}q\right) \right| &\ll \Bigg(\sum_{\substack{0 \lt r \lt q\\q'_r\, \text{squarefree }}} \frac1{\phi(q'_r)}\Bigg) \frac x{(\log x)^{1/2-2\epsilon/3}} + \frac x{(\log x)^{\frac12\log_3 x}} \nonumber\\ & \ll \frac x{(\log x)^{1/2-\epsilon}}; \end{align}

here we have noted that for each squarefree divisor d of q, there are exactly $\phi(d)$ many residues r mod q for which $q'_r = q/(q, r) = d$, so that

\begin{equation*}\sum_{\substack{0 \lt r \lt q\\q'_r\, \text{squarefree }}} \frac1{\phi(q'_r)} \le \sum_{\substack{d\mid q \\d\, \text{squarefree}}} 1 = 2^{\omega(q)} \le (\log x)^{\epsilon/6}.\end{equation*}

It remains to deal with the case $r = q/2$, which arises only for even q. But for this value of r, a classical estimate of Hall and Tenenbaum for the mean values of multiplicative functions taking values in $[-1, 1]$ (see [Reference Tenenbaum24, Theorem 4.14]) yields

(3.5)\begin{equation} \sum_{n \le x} \text{e}\left(\frac{rA(n)}q\right) = \sum_{n \le x} (-1)^{A(n)} \ll \frac x{(\log x)^{3/5}}. \end{equation}

(In fact, Alladi and Erdős [Reference Alladi and Erdos1] show that the left-hand side of (3.5) is $O(x \exp(-c_0 \sqrt{\log x \log_2 x}))$ for some absolute constant $c_0 \gt 0$.) Inserting (3.4) and (3.5) into (3.1) completes the proof of the theorem.

4. Distribution of Euler’s totient to odd moduli: Proof of Theorems 1.3 and 1.4

In what follows, we assume q to be any odd positive integer less than or equal to $(\log x)^K$, until stated otherwise. We abbreviate $\alpha(q)$ to α; it will be useful to note that for all odd q, we have $\alpha \gg 1/\log_2 (3q)$. We first state a rough estimate on the count of $n \le x$ having $\phi(n)$ coprime to q, for odd numbers $q \le (\log x)^K$.

Proposition 4.1. Fix K > 0. We have

\begin{equation*} \#\{n\le x: (\phi(n),q)=1\} = \frac{x}{(\log{x})^{1-\alpha}} \exp(O((\log\log{(3q)})^{O(1)})), \end{equation*}

uniformly in odd $q \le (\log x)^K$.

The above result is a special case of Proposition 2.1 in [Reference Pollack and Singha Roy19] (cf. the work of Scourfield [Reference Scourfield20, Reference Scourfield21] who gives more precise estimates). In view of Proposition 4.1, it remains to show the first assertion of Theorem 1.3 in order to complete the proof of the theorem. To that end, we also state the following lemma, which is a special case of [Reference Pollack and Singha Roy19, Lemma 2.4].

Lemma 4.2. For each positive integer q and each real number $x\ge 3q$,

\begin{equation*} \sum_{p \le x} \frac{{\mathbb{1}}_{(p-1,q)=1}}{p} = \alpha \log_2{x} + O((\log\log{(3q)})^{O(1)}).\end{equation*}

Coming to the first assertion of Theorem 1.3, set $y := \exp((\log x)^{\epsilon/2})$ and $z := x^{1/\log_2 x}$ as in the proof of Theorem 1.2. We start by removing from the count of $n \le x$ satisfying $\phi(n) \equiv a \pmod q$ those that are either z-smooth or have a repeated prime factor exceeding y. As observed before, the total contribution of such n is $\ll \Psi(x, z) + x/y \ll x/(\log x)^{(1+o(1))\log_3 x}$, which is negligible in comparison to the error term in the statement of the theorem.

Among the surviving n, we also remove those that have $P_2(n) \le y$: any such n can be written in the form n = mP, where $P = P(n) \gt z$, m is y-smooth and $\phi(n) = \phi(m) \phi(P) = \phi(m) (P-1)$. As such, the condition $\phi(n) \equiv a \pmod q$ forces $\phi(m)$ to be coprime to q and, for each choice of m, constrains $P \in (z, x/m]$ to at most one coprime residue class modulo q. By the Brun–Titchmarsh theorem, there are $\ll x/\phi(q)m\log(z/q) \ll x\log_2 x/\phi(q)m\log x$ many possible choices of P for each choice of m. Consequently, the total contribution of the surviving $n \le x$ having $P_2(n) \le y$ is

\begin{equation*} \begin{array}{rcl} \ll \frac{x\log_2 x}{\phi(q)\log x}\sum_{\substack{m:\, P^+(m) \le y}} \frac{{\mathbb 1}_{(\phi(m), q)=1}}m &\ll & \frac{x\log_2 x}{\phi(q)\log x} \exp\left(\sum_{p \le y} \frac{{\mathbb 1}_{(p-1, q)=1}}p\right)\\ &\ll & \frac{x\log_2 x}{\phi(q)(\log x)^{1-\alpha\epsilon/2}} \exp((\log_2 (3q))^{O(1)}) \\ &\ll & \frac{x}{\phi(q)(\log x)^{1-2\alpha\epsilon/3}}, \end{array} \end{equation*}

where we invoked Lemma 4.2 in order to estimate the sum $\sum_{p \le y} {\mathbb 1}_{(p-1, q)=1}/p$ and recalled that $\alpha \gg 1/\log_3 x$ for all odd $q \le (\log x)^K$. Collecting estimates, we have so far shown that

\begin{equation*} \sum_{\substack{n \le x\\\varphi(n) \equiv a\!\!\!\!\! \pmod q}} 1 = \sum_{\substack{n \le x\\P(n) \gt z,\ P_2(n) \gt y\\p \gt y \implies p^2 \nmid n}} {\mathbb 1}_{\varphi(n) \equiv a\!\!\!\!\! \pmod q} + O\left(\frac{x}{\varphi(q)(\log x)^{1-2\alpha\epsilon/3}}\right). \end{equation*}

By the orthogonality of the Dirichlet characters mod q, we have ${\mathbb 1}_{\phi(n) \equiv a \pmod q} = \frac{{\mathbb 1}_{(\phi(n), q)=1}}{\phi(q)} + {\frac1{\phi(q)}}{\sum_{\chi \ne \chi_0 \bmod q}} {\overline\chi(a)} {\chi(\phi(n))}$, where χ ₀ denotes the principal character modulo q, and the last sum is over the nonprincipal Dirichlet characters χ mod q. This yields

(4.1)\begin{equation} \begin{array}{l} \sum_{\substack{n \le x\\\phi(n) \equiv a\!\!\!\!\! \pmod q}} 1 = {\frac1{\phi(q)}}\sum_{\substack{n \le x\\(\phi(n), q)=1}} 1\\ \qquad + {\frac1{\phi(q)}}{\sum_{\chi \ne \chi_0 \bmod q}} {\overline\chi(a)}\sum_{\substack{n \le x\\P(n) \gt z,\, P_2(n) \gt y\\p \gt y \implies p^2 \nmid n}} {\chi(\phi(n))} + O\left(\frac{x}{\phi(q)(\log x)^{1-2\alpha\epsilon/3}}\right). \end{array} \end{equation}

Here we have used the same arguments as before to see that there are $O({x}/{(\log x)^{1-2\alpha\epsilon/3}})$ many $n \le x$ satisfying $(\phi(n), q)=1$ but failing at least one of the following three conditions:

1. (i) $P(n) \gt z,$

2. (ii) $p \gt y \implies p^2 \nmid n,$

3. (iii) $P_2(n) \gt y$.

Indeed, any n satisfying conditions (i) and (ii) but failing condition (iii) is of the form mP with $P^+(m) \le y$, $P = P^+(n) \in (z, x/m]$ and $\phi(n) = \phi(m)(P-1)$. As such, $(\phi(m), q)=1$ and the number of P given m is $\ll x/m\log z \ll x\log_2 x/m\log x$, summing which over m yields the claimed bound.

We now apply the methods from the proof of Theorem 1.1 in order to estimate the inner sums of $\chi(\phi(n))$ occurring in (4.1). Any n having $P(n) \gt z$, $P_2(n) \gt y$ and no repeated prime factor exceeding y can be uniquely written in the form $mP_j \cdots P_1$ for some $j \ge 2$, where $P_1 = P(n) \gt z$ and $P(m) \le y \lt P_j \lt \dots \lt P_1$. This shows that

\begin{equation*}\sum_{\substack{n \le x\\P(n) \gt z,\ P_2(n) \gt y\\p \gt y \implies p^2 \nmid n}} {\chi(\varphi(n))} = \sum_{j \ge 2} \sum_{\substack{m \le x\\P(m) \le y}} \chi(\varphi(m)) \sum_{\substack{P_1, \dots, P_j\\P_j \cdots P_1 \le x/m\\P_1 \gt z,\ y \lt P_j \lt \dots \lt P_1}} \chi(P_1-1) \cdots \chi(P_j-1).\end{equation*}

We proceed as in the proof of Theorem 1 to successively remove $\chi(P_1-1), \ldots, \chi(P_j-1)$, with the input from (1.1) replaced by the estimate for $\sum_{y \lt p \le Y} \chi(p-1)$ analogous to (3.2) and coming from the Siegel–Walfisz Theorem. After the dust settles, we are left with

\begin{equation*} \begin{array}{rcl} \sum_{\substack{n \le x\\P(n) \gt z,\ P_2(n) \gt y\\p \gt y \implies p^2 \nmid n}} {\chi(\varphi(n))} &=& \sum_{j \ge 2} \frac{(\rho_\chi)^j}{(j-1)!} \sum_{\substack{m \le x\\P(m) \le y}} \chi(\varphi(m)) \sum_{\substack{P_1, \dots, P_j\\P_1 \gt z,\ P_j \cdots P_1 \le x/m\\P_2, \dots , P_j \in (y, P_1)\, \text{distinct }}} 1\\ &&+ O(x \exp(-K_0 \sqrt{\log y})), \end{array} \end{equation*}

where $\rho_\chi := {\frac1{\phi(q)}} \sum_{v \bmod q} \chi_0(v) \chi(v-1)$ and $K_0 \gt 0$ is an absolute constant. Hereafter, carrying out the rest of the proof of Theorem 1.1 yields

(4.2)\begin{align} \sum_{\substack{n \le x\\P(n) \gt z,\ P_2(n) \gt y\\p \gt y \implies p^2 \nmid n}} {\chi(\varphi(n))} &\ll |\rho_\chi|^2 \frac{x \log_2 x}{\log z} \cdot (\log x)^{|\rho_\chi|} \exp\left(\sum_{p \le y} \frac{{\mathbb 1}_{(p-1, q)=1}}p \right) \nonumber\\ &\quad+ x \exp(-K_0 \sqrt{\log y})\nonumber\\ &\ll |\rho_\chi|^2 \frac x{(\log x)^{1-|\rho_\chi|-2\alpha\epsilon/3}} + x \exp(-K_0 \sqrt{\log y}), \end{align}

where we have recalled Lemma 4.2 while passing to the second line above.

To use the last bound, we need to better understand $|\rho_\chi|$. Let ${\mathfrak f(\chi)}$ denote the conductor of $\chi \bmod q$, so that ${\mathfrak f(\chi)} \gt 1$ and ${\mathfrak f(\chi)} \mid q$. We can write χ uniquely in the form $\prod_{\ell^e \parallel q} \chi_\ell$, where each $\chi_\ell$ is a character mod $\ell^e$ and $\chi_\ell$ is nontrivial precisely when $\ell\mid {\mathfrak f(\chi)}$. Now $\phi(q)\rho_\chi = \prod_{\ell^e \parallel q} S_{\chi, \ell}$, where for each prime power $\ell^e \parallel q$,

(4.3)\begin{equation} S_{\chi, \ell} := \sum_{v \bmod \ell^e} \chi_{0, \ell}(v) \chi_\ell(v-1) = \sum_{\substack{v \bmod{\ell^e}\\(v, \ell)=1}} \chi_\ell(v-1) = \sum_{u \bmod{\ell^e}} \chi_\ell(u) - \sum_{\substack{u \bmod{\ell^e}\\u \equiv -1\!\!\!\!\! \pmod \ell}} \chi_\ell(u). \end{equation}

Here $\chi_{0, \ell}$ denotes the trivial character mod $\ell^e$, and we have noted that as v runs over the coprime residues mod $\ell^e$, the expression v − 1 runs over all the residues mod $\ell^e$ except for those congruent to −1 mod $\ell$. The first sum in the rightmost expression in (4.3) is ${\mathbb 1}_{\chi_\ell = \chi_{0, \ell}} \phi(\ell^e)$. We claim that the second sum is zero unless ${\mathfrak f}(\chi_\ell) \mid \ell$, in which case it is $\chi_\ell(-1) \ell^{e-1}$. Indeed, the second sum is equal to ${\chi _\ell }( - 1)\sum\nolimits_{\scriptstyle v\,\bmod \,{\ell ^e} \atop \scriptstyle u \equiv 1\;\;\;\,\left( {\bmod \ell } \right)} {{\chi _\ell }\left( u \right)} $, and this latter sum is invariant upon multiplication by an element lying in the subgroup of residues that are 1 mod $\ell$ and hence is non-vanishing precisely when $\chi_\ell$ restricts to the trivial character on this subgroup. This shows that if the second sum is nonzero, then ${\mathfrak f}(\chi_\ell) \mid \ell$. Conversely, if ${\mathfrak f}(\chi_\ell) \mid \ell$, then it is clear that the second sum is equal to ${\chi _\ell }( - 1)\sum\nolimits_{\scriptstyle u\,\bmod \,{\ell ^{e}} \atop \scriptstyle u \equiv - 1\;\;\;\,\left( {\bmod \ell } \right)}{1 = {\chi _\ell }( - 1){\ell ^{e - 1}}}$, establishing our claim.

Altogether, we obtain

\begin{equation*}S_{\chi, \ell} = {\mathbb 1}_{\chi_\ell = \chi_{0, \ell}} \phi(\ell^e) - {\mathbb 1}_{{\mathfrak f}(\chi_\ell)\mid \ell} \chi_\ell(-1) \ell^{e-1} = {\mathbb 1}_{{\mathfrak f}(\chi_\ell)\mid \ell} \ell^{e-1}\left({\mathbb 1}_{\ell \nmid {\mathfrak f(\chi)}} (\ell-1) - \chi_\ell(-1)\right)\end{equation*}

for each prime power $\ell^e \parallel q$. Multiplying this relation over all these prime powers, we obtain

(4.4)\begin{equation} \rho_\chi \!=\! \prod_{\ell^e \parallel q} \frac{S_{\chi, \ell}}{\phi(\ell^e)} \!=\! {\mathbb 1}_{{\mathfrak f(\chi)}\, \text{squarefree }} \!\prod_{\ell^e \parallel q}\! \left({\mathbb 1}_{\ell \nmid {\mathfrak f(\chi)}} - \frac{\chi_\ell(-1)}{\ell-1}\right) \!=\! {\mathbb 1}_{{\mathfrak f(\chi)}\, \text{squarefree }}\! \frac{(-1)^{\omega({\mathfrak f(\chi)})} \chi(-1) \alpha}{\prod_{\ell\mid {\mathfrak f(\chi)}} (\ell-2)}. \end{equation}

If $3\mid q$, let ψ denote the unique character mod q induced by the nontrivial character mod 3. Then for any nontrivial character $\chi \ne \psi$ mod q for which $\rho_\chi \ne 0$, its conductor ${\mathfrak f(\chi)}$ has a prime divisor at least 5, so that $|\rho_\chi| \le \alpha/3$ by (4.4). As such, (4.2) yields for all such χ,

(4.5)\begin{equation} \sum_{\substack{n \le x\\P(n) \gt z,\ P_2(n) \gt y\\p \gt y \implies p^2 \nmid n}} {\chi(\phi(n))} \ll |\rho_\chi|^2 \frac x{(\log x)^{1-(1/3+2\epsilon/3)\alpha}} + x \exp(-K_0 \sqrt{\log y}). \end{equation}

But from (4.4) and the fact that there are exactly $\prod_{\ell\mid d} (\ell-2)$ primitive characters modulo any squarefree integer d, we find that

\begin{align*} \sum_{\chi \bmod q} |\rho_\chi|^2 &\le \alpha^2\sum_{\substack{d\mid q\\d\,\text{squarefree}}} \frac1{\prod_{\ell\mid d} (\ell-2)^2} \sum_{\substack{\chi \bmod q\\{\mathfrak f(\chi)} = d}} 1 \le \alpha^2\sum_{\substack{d\mid q\\d\,\text{squarefree}}} \frac1{\prod_{\ell\mid d} (\ell-2)} \\ &\le \alpha^2 \prod_{\ell\mid q} \frac{\ell-1}{\ell-2} = \alpha. \end{align*}

Summing the bound (4.5) over all nontrivial characters $\chi \ne \psi$ mod q and substituting the resulting bound into (4.1), we thus obtain

(4.6)\begin{align} \sum_{\substack{n \le x\\\phi(n) \equiv a\!\!\!\!\! \pmod q}} 1 &= {\frac1{\phi(q)}}\sum_{\substack{n \le x\\(\phi(n), q)=1}} 1 + \frac{{\mathbb 1}_{3\mid q} \overline{\psi}(a)}{\phi(q)}\sum_{\substack{n \le x\\P(n) \gt z,\ P_2(n) \gt y\\p \gt y \implies p^2 \nmid n}} \psi(\phi(n)) \nonumber\\ &\quad+ O\left(\frac{x}{\phi(q)(\log x)^{1-\alpha(1/3+\epsilon)}}\right)\nonumber\\ &= {\frac1{\phi(q)}}\sum_{\substack{n \le x\\(\phi(n), q)=1}} 1 + \frac{{\mathbb 1}_{3\mid q} \overline{\psi}(a)}{\phi(q)}\sum_{n \le x} \psi(\phi(n)) \nonumber\\ &\quad+ O\left(\frac{x}{\phi(q)(\log x)^{1-\alpha(1/3+\epsilon)}}\right). \end{align}

In passing to the second line above, we have recalled our previous bound on the count of $n \le x$ having $\gcd(\phi(n), q)=1$ but failing one of conditions (i)–(iii) in the paragraph following (4.1).

The last equality in (4.6) already establishes the first assertion of Theorem 1.3 for moduli $q \le (\log x)^K$ coprime to 6, thus completing the proof of that theorem.

Coming to the proof of Theorem 1.4, we now consider $q \le (\log x)^K$ satisfying $\gcd(6, q)=3$, so that q is odd and divisible by 3. By definition of ψ, we have

\begin{equation*}\psi(\varphi(n)) = \begin{cases} \psi(a), & \text{if } \gcd(\varphi(n), q)=1 \text{ and } \varphi(n) \equiv a\!\!\!\!\! \pmod 3,\\ \psi(-a) = -\psi(a), & \text{if } \gcd(\varphi(n), q)=1 \text{ and } \varphi(n) \equiv -a\!\!\!\!\! \pmod 3,\\ 0, & \text{if } \gcd(\varphi(n), q) \ne 1. \end{cases}\end{equation*}

Inserting this into (4.6) and recalling that $\psi(a) \overline\psi(a) = 1$, we obtain the first estimate claimed in Theorem 1.4. To obtain the final asymptotic formula in the theorem, it suffices to show that

(4.7)\begin{equation} 3\sum_{\substack{n \le x:\, (\phi(n), q)=1\\ \phi(n) \equiv a\!\!\!\!\! \pmod 3}} 1 \ge \sum_{\substack{n \le x/4\\ (\phi(n),\, q)=1}} 1. \end{equation}

Indeed once we show this, an application of Proposition 4.1 will reveal that the right-hand side of the above inequality grows strictly faster than the O-term in (1.3), which will lead to (1.4).

Finally to prove (4.7), we split the right-hand side of the inequality as

\begin{equation*}\sum_{\substack{n \le x/4\\ (\phi(n), q)=1\\ \phi(n) \equiv a\!\!\!\!\! \pmod 3}} 1 ~ + \sum_{\substack{n \le x/4:\ 2 \nmid n\\ (\phi(n), q)=1\\ \phi(n) \equiv -a\!\!\!\!\! \pmod 3}} 1 ~ + \sum_{\substack{n \le x/4:\ 2\mid n\\ (\phi(n), q)=1\\ \phi(n) \equiv -a\!\!\!\!\! \pmod 3}} 1.\end{equation*}

We denote the sum on the left-hand side of (4.7) by S ₀; in other words, S ₀ is one-third the left-hand side of (4.7). We claim that each of the three sums in the above display is no more than S ₀. Indeed, any n counted in the first of the three sums is automatically counted in S ₀. For any n counted in the second sum above, $\phi(4n) = 2\phi(n)$ is coprime to q (since q is odd) and $\phi(4n) \equiv -\phi(n) \equiv a \pmod 3$, so that $4n \le x$ is counted in S ₀. Finally, for any n counted in the third sum above, we have $2n \le x/2$, and $\phi(2n) = 2 \phi(n) \equiv -\phi(n) \equiv a \pmod 3$ and $\gcd(\phi(2n), q) = \gcd(2 \phi(n), q)=1$, so that $2n \le x$ is counted in S ₀. This establishes the bound (4.7), completing the proof of Theorem 1.4.

Remark: It is worth pointing out that the count of $n \le x$ satisfying $\gcd(\phi(n), q)=1$ and $\phi(n) \equiv a \pmod 3$ (which appears in the main term on the right-hand side of (1.3)) is of the same order of magnitude as the count of $n \le x$ satisfying $\gcd(\phi(n), q)=1$. In other words, these two quantities are bounded by constant multiples of one another (said constants being independent of q). This follows by combining the lower bound (4.7) with Theorems A and B in [Reference Scourfield21].

Remark: To substantiate some of the remarks made after the statement of Theorem 1.1, note that if we were to directly invoke the Halász–Montogomery–Tenenbaum (HMT) Theorem (as in [Reference Tenenbaum24, Corollary III.4.12], say) in the proofs of Theorems 1.2 and 1.3 so as to estimate the sums $\sum_{n \le x} e(rA(n)/q)$ and $\sum_{n \le x} \chi(\phi(n))$, then we would get for any fixed $\delta \in (0, 1)$,

\begin{equation*}\sum_{n \le x} e\left(\frac{rA(n)}q\right) \ll \frac x{(\log x)^{1/2-\delta}}, ~~~ \sum_{n \le x} \chi(\phi(n)) \ll \frac x{(\log x)^{1-(\alpha/3+\delta)}}\end{equation*}

(The ‘pretentious distances’ can be bounded as in [Reference Pollack and Singha Roy18, Lemma 3.3].) The second expression above may become larger than the main term $\sum_{n \le x: \, (\phi(n), q)=1} 1$ if $\alpha=\alpha(q)$ is too small compared to δ. Contrast this with the bound (4.5) where the exponent of $\log x$ was $1-\alpha(1/3+2\epsilon/3)$; this latter difference arises due to the fact that a direct application of HMT requires control on the oscillatory behaviour of $\chi(p-1)$ at primes $p \le y$, whereas Theorem 1.1 does not. Now supplementing HMT with anatomical arguments that already constitute part of the arguments of Theorem 1.1 (see also [Reference Singha Roy22, Theorem 5.5]), we can replace ‘ $1-(\alpha/3+\delta)$’ with the desired ‘ $1-(\alpha/3)(1+\delta)$’. But even then, both the above bounds miss the factors of $|\rho_r|$ and $|\rho_\chi|^2$ in (3.3) and (4.5), respectively, which are crucial for ensuring that the total contribution of these character sums (over all nonzero r or all nontrivial χ) does not become too large. In fact, if we sum the above bounds over all r (respectively, over all χ), then we would get the weaker versions of Theorems 1.2–1.4 without $1/q$ or $1/\phi(q)$ in the error terms; this would lead to much more limited ranges of uniformity in q.