2.1 The proof of Theorem 1.1

We apply the $ABC$ conjecture to the equation

$$ \begin{align*}a^n-1=st,\quad s:=s_{Kn}(u_n),\quad t=(a^n-1)/s \end{align*} $$

for $n\in {\mathcal A}_{K,c,{\textbf {u}}}$ with the obvious choices. Note that

$$ \begin{align*}{{\textrm{rad}}}(s)=\prod_{\substack{p\le Kn\\ p\mid a^n-1}} p\quad {{\textrm{and}}}\quad t<(a/c)^n. \end{align*} $$

We then have

$$ \begin{align*}a^n\ll_{\varepsilon} (a\cdot {{\textrm{rad}}}(s) t))^{1+\varepsilon}\ll \left(\prod_{\substack{p\le Kn\\ p\mid a^n-1}} p\right)^{1+\varepsilon} (a/c)^{n(1+\varepsilon)}. \end{align*} $$

We may of course assume that $1<c<a$ . Then

$$ \begin{align*}\sum_{\substack{p\le Kn\\ p\mid a^n-1}} \log p\ge \frac{n}{1+\varepsilon}(\log a-(1+\varepsilon)\log(a/c))+O_{\varepsilon}(1). \end{align*} $$

We choose $\varepsilon>0$ small enough so that $\log a-(1+\varepsilon )\log (a/c)>0$ . Then, we get

(2.1) $$ \begin{align} S_{a,K}(n):=\sum_{\substack{p\le Kn\\ p\mid a^n-1}} \log p\gg_{\varepsilon} n. \end{align} $$

The next lemma shows that the left–hand side above is $\le n^{2/3+o(1)}$ as $n\to \infty $ . This is unconditional and finishes the proof of Theorem 1.1.

Lemma 2.1 We have

$$ \begin{align*}S_{K,a}(n)\le K^{1/2} n^{1/2+o(1)} \end{align*} $$

as $n\to \infty $ .

Proof Let $\ell _p$ be the order of a modulo p; that is the smallest positive integer k such that $a^k\equiv 1\pmod p$ . Since primes p participating in $S_{K,a}(n)$ have $p\mid a^n-1$ , it follows that $\ell _p\mid n$ . Since also such primes are $O(n)$ , it follows that

$$ \begin{align*}S_{K,a}\ll \#P_{K,n}\log n, \end{align*} $$

where $P_{K,a}(n):=\{p\le Kn: \ell _p\mid n\}$ . To estimate $P_{K,a}(n)$ we fix a divisor d of n and look at primes $p\le Kn$ such that $\ell _p=d$ . Such primes p have the property that $p\equiv 1\pmod d$ by Fermat’s Little Theorem. In particular, the number of such (without using results on primes in progressions) is at most

$$ \begin{align*}\left\lfloor \frac{Kn}{d}\right\rfloor\le \frac{Kn}{d}. \end{align*} $$

However, since these primes divide $a^d-1$ , the number of them is $O(d)$ . Thus, for a fixed d the number of such primes is

$$ \begin{align*}\ll \min\left\{\frac{Kn}{d},d\right\}\ll (Kn)^{1/2}. \end{align*} $$

Summing this up over all divisors d of n we get that

$$ \begin{align*}\#P_{K,a}(n)\ll d(n) (Kn)^{1/2}\le K^{1/2} n^{1/2+o(1)} \end{align*} $$

as $n\to \infty $ , where we used $d(n)$ for the number of divisors of n and the well-known estimate $d(n)=n^{o(1)}$ as $n\to \infty $ (see Theorem 315 in [Reference Hardy, Wright, Heath-Brown and Silverman2]). Hence,

$$ \begin{align*}S_{K,a}(n)\ll \#P_{K,a}(n)\log n\le K^{1/2} n^{1/2+o(1)} \end{align*} $$

as $n\to \infty $ , which is what we wanted.□

2.2 The proof of Theorem 1.2

It is enough to prove an upper bound comparable to the upper bound from the right–hand side of (1.1) for $\#({\mathcal A}_{K,c,{\textbf {u}}}\cap (N/2,N])$ as then we can replace N by $N/2$ , then $N/4$ , etc. and sum up the resulting inequalities. So, assume that $n\in (N/2,N]$ . We estimate

$$ \begin{align*}Q_N:=\prod_{n\in (N/2,N]} s_{KN}(u_n). \end{align*} $$

On the one hand, since $s_{KN}(u_n)\ge s_{Kn}(u_n)\ge c^{n}\ge c^{N/2}$ for all $n\in {\mathcal A}_{K,c,{\textbf {u}}}$ , we get that

$$ \begin{align*}\log Q_N\gg N(\#{\mathcal A}_{K,c,{\textbf{u}}}\cap (N/2,N]). \end{align*} $$

Next, writing $\nu _p(m)$ for the exponent of p in the factorisation of m, we have

(2.2) $$ \begin{align} \log Q_N=\sum_{n\in (N/2,N]} \sum_{p\le KN} \nu_p(u_n)\log p\le \sum_{p\le KN}\log p \sum_{n\in (N/2,N]} \nu_p(u_n). \end{align} $$

Let $o_p:=\nu _p(u_{\ell _p})$ . It is well-known that if p is odd then

$$ \begin{align*}\nu_p(u_n)=\left\{\begin{matrix} o_p+\nu_p(n), & {{\textrm{if}}} & \ell_p\mid n;\\ 0, & {{\textrm{otherwise}}} & ~ \\ \end{matrix}\right. \end{align*} $$

(see, for example, (66) in [Reference Shparlinski7]). In particular, if $p\mid u_n$ , then $p^{o_p}\mid u_n$ . Furthermore, for each $k\ge 0$ , the exact power of p in $u_n$ is $o_p+k$ if and only if $\ell _p p^k$ divides n and $\ell _p p^{k+1}$ does not divide n. When $p=2$ , we may assume that a is odd (otherwise $\nu _2(u_n)=0$ for all $n\ge 1$ ), and the right–hand side of the above formula needs to be ammended to

$$ \begin{align*}\nu_2(u_n) =\left\{\begin{matrix} o_2, & {{\textrm{if}}} & 2\nmid n;\\ o_p+\nu_2(a+1)+\nu_2(n/2), & {{\textrm{if}}} & 2\mid n.\\ \end{matrix}\right. \end{align*} $$

Thus, for odd p,

(2.3) $$ \begin{align} \sum_{n\in (N/2,N]}\nu_p(u_n)=o(p)\#\{N/2<n\le N: \ell_p\mid n\}+\sum_{k\ge 1} \#\{N/2<n\le N: \ell_p p^k\mid n\}. \end{align} $$

A similar formula holds for $p=2$ . In particular, for $p=2$ , we have

$$ \begin{align*}\sum_{n\in (N/2,N]} \nu_2(u_n)=O(N). \end{align*} $$

Thus, the prime $p=2$ contributes a summand of size $O(N)$ to the right-hand side of (2.2). From now on, we assume that p is odd. The first cardinality in the right-hand side of formula (2.3) above is

$$ \begin{align*}\#\{N/2<n\le N: \ell_p\mid n\} \le \left\lfloor \frac{N}{2\ell_p}\right\rfloor+1\ll \frac{N}{\ell_p}. \end{align*} $$

The remaining cardinalities on the right-above can be bounded as

$$ \begin{align*}\#\{N/2<n\le N: \ell_p p^k\mid n\}\le \left \lfloor \frac{N}{2\ell_p p^k}\right\rfloor+1\ll \frac{N}{\ell_p p^k}. \end{align*} $$

Thus,

$$ \begin{align*}\sum_{n\in (N/2,N]}\nu_p(u_n)\ll \frac{N o_p}{\ell_p}+\sum_{k\ge 1} \frac{N}{\ell_p p^k}\ll \frac{N o_p}{\ell_p}+\frac{N}{\ell_p p}. \end{align*} $$

We thus get

$$ \begin{align*}\log Q_N\ll N\sum_{p\le Kn} \frac{o_p \log p}{\ell_p}+N\sum_{p\le Kn} \frac{\log p}{\ell_p p} \ll N\sum_{p\le Kn} \frac{o_p \log p}{\ell_p} :=S. \end{align*} $$

It remains to bound S. Since $p^{o_p}\mid a^{\ell _p}-1$ , we get that $p^{o_p}<a^{\ell _p}$ so $o_p\log p\ll \ell _p$ . Hence,

$$ \begin{align*}S=N\sum_{p\le KN} \frac{o_p\log p}{\ell_p}\ll N\pi(KN)\ll_K \frac{N^2}{\log N}. \end{align*} $$

We get the first nontrivial upper bound on $\#({\mathcal A}_{K,c,{\textbf {u}}}\cap (N/2,N]$ , namely

$$ \begin{align*}N\#({\mathcal A}_{K,c,{\textbf{u}}}\cap (N/2,N])\ll \log Q_N\ll S \ll \frac{N^2}{\log N}+N\log\log N\ll_K \frac{N^2}{\log N}, \end{align*} $$

so

$$ \begin{align*}\#({\mathcal A}_{K,c,{\textbf{u}}}\cap (N/2,N])\ll_K \frac{N}{\log N}. \end{align*} $$

To do better, we need to look more closely at $o_p\log p/\ell _p$ for primes $p\le KN$ . We split the sum S over primes $p\le KN$ in two subsums. The first is over the primes in the set $Q_1$ consisting of p such that $o_p\log p/\ell _p<1/y_N$ , where $y_N$ is some function of N which we will determine later. We let $Q_2$ be the complement of $Q_1$ in the set of primes $p\le Kn$ . The sum over primes $p\in Q_1$ is

$$ \begin{align*}S_1=N\sum_{p\in Q_1}\frac{o_p\log p}{\ell_p}\le \frac{N}{y_N}\pi(KN)\ll_K \frac{N^2}{y_N\log N}. \end{align*} $$

For $Q_2$ , we use the trivial estimate

$$ \begin{align*}S_2=N\sum_{p\in Q_2}\frac{o_p\log p}{\ell_p}\ll N\#Q_2, \end{align*} $$

and it remains to estimate the cardinality of $Q_2$ . Note that $Q_2$ consists of primes p such that $o_p>\ell _p/(y_N\log p)\gg \ell _p/(y_N\log N)$ . We put $\ell _p$ in dyadic intervals. That is $\ell _p\in (2^i,2^{i+1}]$ for some $i\ge 0$ . Then primes $p\le KN$ in $Q_2$ with such $\ell _p$ have the property that $o_p\gg 2^i/(y_N\log N)$ . Hence,

$$ \begin{align*} \frac{2^i\#(Q_2\cap (2^i,2^{i+1}])}{y_N \log N} & \ll \sum_{p\in Q_2\cap (2^i,2^{i+1}]} \nu_p(a^{\ell_p}-1)\log p\le \sum_{\ell \in (2^i,2^{i+1}]} \log(a^{\ell}-1)\\ & \ll \sum_{\ell\in (2^i,2^{i+1}]}\ell \ll 2^{2i}, \end{align*} $$

which gives

$$ \begin{align*}\#(Q_2\cap (2^i,2^{i+1}])\ll 2^i y_N\log N. \end{align*} $$

Summing up over all the i, we get

$$ \begin{align*}\#Q_2\le 2^I y_N\log N, \end{align*} $$

where I is maximal such that $(2^I,2^{I+1}]$ contains an element p of $Q_2$ . By a result of Stewart (see Lemma 4.3 in [Reference Shparlinski7]),

$$ \begin{align*} 2^I & < \ell_p<o_p y_N\log N<p\exp\left(-\frac{\log p}{51.9\log\log p}\right)y_N \log N \log \ell_p\\ & \ll KN\exp\left(-\frac{\log(Kn)}{51.9\log\log(KN)}\right)y_N\log(KN)^2\\ & \ll_K N\exp\left(-\frac{\log N}{51.95\log\log N}\right) y_N(\log N)^2. \end{align*} $$

Thus,

$$ \begin{align*} \#Q_2 & \ll 2^I y_N\log N\ll_K N\exp\left(-\frac{\log N}{51.95\log\log N}\right) y_N^2(\log N)^3\\ & \ll N\exp\left(-\frac{\log N}{52\log\log N}\right) y_N^2. \end{align*} $$

Choosing $y_N:={\displaystyle {\exp \left (c\frac {\log N}{\log \log N}\right )}}$ with a positive constant c to be determined later, we get

$$ \begin{align*} N\#({\mathcal A}_{K,c,{\textbf{u}}}\cap (N/2,N]) & \ll N\#Q_2+\frac{N}{y_N\log N}\\ & \ll _K N\left(\exp\left(\left(2c-\frac{1}{52}\right)\frac{\log N}{\log\log N}\right)+\exp\left(-\frac{c\log N}{\log\log N}\right)\right). \end{align*} $$

Choosing $c:=1/156$ , we get

$$ \begin{align*}\#({\mathcal A}_{K,c,{\textbf{u}}}\cap(N/2,N])\ll N\log N \exp\left(-\frac{\log N}{156\log\log N}\right), \end{align*} $$

which is what we wanted.