Composite values of shifted exponentials

It is a notorious open question to determine whether a shifted exponential sequence $a^{n}-b$ for given $a>1$ and $b\in\mathbb{Z}\setminus\{0\}$ produces infinitely many primes as $n$ ranges over the positive integers $\mathbb{N}$. One expects that this should be the case whenever there is no obvious reason for $a^{n}-b$ to be composite for all large $n$, the obvious reasons being that $a^{n}-b$ either has a fixed prime divisor or that it factors as the result of a polynomial identity. This leads to the following question.

Here case (ii) corresponds to the well-known fact that the binomial $x^{n}-d\in\mathbb{Q}[x]$ is reducible if and only if $d$ is an $m$th power of a rational number for some $m\geq 2$, $m\mid n$, or $4\mid n$ and $d=-4c^{4}$ for some rational $c$. The exclusion of $b=-1$ stems from the fact that for $b=-1$ one easily sees that the only possible primes in the sequence are of the form $a^{2^{m}}+1$, and as is discussed below, probabilistic heuristics suggest that there are only finitely many such primes (even though (i) and (ii) hold for $(a,b)=(2,-1)$, say). See Section 11 for further discussion on the necessity of the conditions.

Question 1.1 is closely connected with two conjectures that are among the oldest in number theory: the existence of Mersenne primes and Fermat primes. Mersenne primes are primes of the form $2^{p}-1$ with $p$ a prime; one easily sees that any prime of the form $2^{n}-1$ must be of this form. Many of the largest known primes are Mersenne primes. Fermat primes are primes in the sequence $2^{2^{m}}+1$; again, all the primes of the form $2^{n}+1$ are easily seen to have this shape. The first five Fermat numbers ($m=0,1,2,3,4$) are all prime, but extensive numerical searches have produced no further Fermat primes. A widely-believed conjecture (supported by probabilistic arguments; see [11, Problem A3]) is that there are infinitely many Mersenne primes but only finitely many Fermat primes. These two assertions seem to be well beyond reach of all known methods.

Although little is known about the primality of $2^{n}\pm 1$, it is noteworthy that $2^{n}\pm 1$ can be prime only for a set of integers $n$ of natural density $0$; this follows immediately from the form that the exponents of the Mersenne and Fermat primes take. In light of this, one conjectures more generally that $a^{n}-b$ is prime for a natural density $0$ of natural numbers $n$. Even this is still an open problem. The problem, in the concrete special case of the sequence $2^{n}+5$, was suggested by Gil Kalai in [16] as a possible Polymath project (with the comment that it “might be too hard”). The problem was originally studied by Christopher Hooley in his book [13], and was popularized by Peter Sarnak¹¹1Sarnak remarks in [30] that “Even a problem like $2^{n}+5$ being composite for almost all $n$ is very problematic (Hooley).” [30].

In the discussion in [16], it was suggested that in order to make any progress on the compositeness of $2^{n}+5$ one should assume GRH. Our first main result confirms that $2^{n}+5$ is indeed composite for almost all $n$, as well as the analogous result for general shifted exponential sequences $a^{n}-b$, assuming GRH and an additional Brun-Titchmarsh type inequality for primes satisfying conditions of form “$p\equiv 1\pmod{m}$, $c$ is a perfect $m^{\prime}$th power modulo $p$”. We postpone detailed discussion of the hypotheses to Subsection 1.1.

We then state our main results.

In addition to showing compositeness of $a^{n}-b$ for almost all $n$, we are more generally able to show that $a^{n}-b$ is not a $k$-almost prime (a number with at most $k$ prime factors) for a density $1$ set of natural numbers $n$. We prove this in the following strong sense.

Here, as usual, $\omega(n)$ denotes the number of distinct prime factors of $n$.

We will in fact prove that the number of prime divisors of $a^{n}-b$ which are less than $\sqrt{n}$ is almost always $\gg\log\log n$. On the other hand, $a^{n}-b$ should of course have a lot of prime factors $p>\sqrt{n}$ as well, but our method does not apply to detecting these large factors.

One naturally wonders whether one can say something about the compositeness of $a^{n}-b$ even when $n$ is restricted to an interesting subset of natural numbers, particularly the primes. In the case of Mersenne primes, which are of the form $2^{p}-1$ with $p$ prime, it appears unknown that there are even infinitely many composite numbers in this sequence. Nevertheless, we are able to apply our methods also to the sequence $a^{p}-b$ with prime exponents, as long as we are not in the case $a=2$, $b=1$ that corresponds to Mersenne primes.

Without further mention, we assume GRH in the lemmas and theorems that follow. We will assume Hypothesis 1.2 only in the proof of Lemma 7.1 below.

We may assume in the proofs of Theorems 1.3 and 1.6 that $a$ is not a perfect power, as the case of $a$ being a perfect power immediately reduces to the generic case. If $|b|\leq 1$, the conclusion of Theorems 1.3 and 1.7 is trivial, since $a^{m}-1\mid a^{n}-1$ for $m\mid n$ and $a^{m}+1\mid a^{n}+1$ for $m\mid n$ and $m$ odd. Thus we may assume $|b|>1$ when proving these theorems. We may also assume that $(a,b)=1$, since otherwise $a^{n}-b$ is composite.

If $p$ is a prime not dividing $a$, we denote by $\textup{ord}_{p}(a)$ the least positive integer $e$ such that $a^{e}\equiv 1\pmod{p}$.

We denote by $\zeta_{k}$ any primitive $k$th root of unity.

We let $\tau(n),\phi(n)$ denote the divisor and Euler phi functions, respectively. We let $(a,b)$ stand for the greatest common divisor of $a$ and $b$ and $\textnormal{lcm}(a,b)$ for their least common multiple. By $\textnormal{rad}(n)$ we denote the product of the prime factors of $n$.

The natural density of a set $S\subset\mathbb{N}$ is defined as the limit

provided that the limit exists. We similarly define the relative density of a set $A\subset\mathbb{N}$ in the set $B\subset\mathbb{N}$ as

assuming that $A\subset B$ and that the limit exists. The density $d_{\mathbb{P}}(\mathcal{P})$ of a subset $\mathcal{P}$ of the primes $\mathbb{P}$ is to be considered as its relative density in the set of primes.

For any subset $S$ of the primes, we define $\pi_{S}(x):=|\{p\leq x:\,\,p\in S\}|$.

Given an extension $L/K$ of number fields, a prime $\mathfrak{p}$ of $\mathcal{O}_{K}$, and a prime $\mathfrak{P}$ of $\mathcal{O}_{L}$ lying above $\mathfrak{p}$, we define the Artin symbol $\left(\frac{L/K}{\mathfrak{P}}\right)$ as the unique element $\sigma\in\textnormal{Gal}(L/K)$ satisfying

for all $\alpha\in L$. Further, if $K=\mathbb{Q}$ and $p$ is a rational prime unramified in $L$, we define $\left(\frac{L/\mathbb{Q}}{p}\right)$ as the conjugacy class of possible values of $\left(\frac{L/\mathbb{Q}}{\mathfrak{P}}\right)$ with $\mathfrak{P}$ lying above $p$; it can be checked that such values do indeed form a conjugacy class. (This definition could be extended to $K\neq\mathbb{Q}$ as well, but we will only need the case $K=\mathbb{Q}$.)

The prime $p$ is said to split completely in $L$ if $\left(\frac{L/\mathbb{Q}}{p}\right)$ is the conjugacy class consisting of the identity of $\textup{Gal}(L/\mathbb{Q})$.

We use the following version of the Chebotarev density theorem, due to Serre [31] and conditional on GRH (this improves on work of Lagarias and Odlyzko [17]).

In this section, we give a sketch of the proof method of Theorem 1.3; the actual details in subsequent sections are slightly different and more complicated, but the purpose of this section is just to illustrate the approach.

As already mentioned, we may assume that $a$ is not a perfect power. Let

since $P_{a}$ contains those primes $p$ for which $a$ is a primitive root, under GRH the set $P_{a}$ contains a positive proportion of the primes. For each $p\in P_{a}$, there exists a unique integer $\ell(p)\in[1,\textup{ord}_{p}(a)]$ such that $a^{\ell(p)}\equiv b\pmod{p}$. Now, for any integer $n\equiv\ell(p)\pmod{\textup{ord}_{p}(a)}$, we have $a^{n}\equiv b\pmod{p}$, implying that $a^{n}-b$ is not prime (except possibly for $n=\ell(p)$). The goal is to prove that the density of integers covered by such arithmetic progressions $\ell(p)\pmod{\textup{ord}_{p}(a)}$ is $1$. Thus the statement is that the residue classes $\ell(p)\pmod{\textup{ord}_{p}(a)}$ for $p\leq P\to\infty$ are nearly (up to a vanishing proportion of numbers) a covering system of the integers. This is generally speaking a rather delicate condition; see [8] and [1] for work on finite sets of congruences covering all but an $\varepsilon$-proportion of the integers⁴⁴4Note that whether or not residue classes $a_{p}\pmod{p-1}$ cover almost all numbers depends heavily on the values of the $a_{p}$; for example, it is known that the proportion of integers covered by $0\pmod{p-1}$ for $p>P$ approaches $0$ as $P\to\infty$. Also if $\mathcal{P}$ is any subset of the primes with sum of reciprocals less than $\frac{1}{2}$, say, then $a_{p}\pmod{p-1}$ for $p\in\mathcal{P}$ leaves uncovered a positive proportion of all numbers..

If the conditions $x\equiv\ell(p)\pmod{\textup{ord}_{p}(a)}$ were independent of each other (which would be the case by the Chinese reminder theorem if the moduli $\textup{ord}_{p}(a)$ and $\textup{ord}_{q}(a)$ were coprime for all $p\neq q$), the density of integers not covered by such congruence conditions would be

Under GRH the relative density of $P_{a}$ inside the primes is positive, so by Mertens’ theorem the above product evaluates to $0$.

However, since $\textup{ord}_{p}(a)$ and $\textup{ord}_{q}(a)$ are typically not coprime⁵⁵5Note that it does not help to restrict to a subset of primes for which $\textup{ord}_{p}(a)/2$ are pairwise coprime, since such a set always has finite sum of reciprocals. If for example we restrict to primes $p$ such that $(p-1)/2$ is also prime, then it is known that such primes have bounded sum of reciprocals (even though their infinitude is not known)., we have to take into account the dependencies between the conditions imposed by different primes. For this we utilize the second moment method.

In our case, the events $A_{p}$ correspond to a “random” integer being congruent to $\ell(p)\pmod{\textup{ord}_{p}(a)}$, where $p$ ranges over $P_{a}\cap[1,x]$, from which we get $\Pr(A_{p})=1/\textup{ord}_{p}(a)$. (See Section 5 for a precise formulation of this idea.) Then the expected value $\mu$ appearing in (3.2) is, more or less, equal to

For reasons explained below, we will in fact restrict to a subset of $P_{a}$ where $\textup{ord}_{p}(a)\gg p-1$, which moreover has a positive relative density inside the primes. This then allows for an asymptotic evaluation of (3.4). We now turn to the sum of the pairwise intersections in (3.3), which are much more difficult to analyze.

Let $p$ and $q$ be primes, and write $(\textup{ord}_{p}(a),\textup{ord}_{q}(a))=m$. The system $y\equiv\ell(p)\pmod{\textup{ord}_{p}(a)},y\equiv\ell(q)\pmod{\textup{ord}_{q}(a)}$ has a solution if and only if $m\mid\ell(p)-\ell(q)$. If a solution exists, then $\Pr(A_{p}\cap A_{q})=\frac{m}{\textup{ord}_{p}(a)\textup{ord}_{q}(a)}$, and otherwise $\Pr(A_{p}\cap A_{q})=0$. Thus

If the pairs $(\ell(p),\ell(q))$ were equidistributed modulo all $m\leq x$, even when conditioned on the event $(\textup{ord}_{p}(a),\textup{ord}_{q}(a))=m$, we would see that $A_{p}$ and $A_{q}$ are independent “on average”, resulting in the same asymptotics for (3.5) as for (3.4).

Unfortunately, the set $P_{a}$ does not have the required equidistribution property for all moduli.⁶⁶6For example, if $p\equiv\pm 3\pmod{8}$ and $2^{x}\equiv 9\pmod{p}$, then $x$ must be even. More generally, congruence conditions for $p$ give information on quadratic residues modulo $p$, leading to bias even in power-free cases. For example, if $2^{x}\equiv-3\pmod{p}$ and $p\equiv 1\pmod{3}$, $p\equiv\pm 3\pmod{8}$, then $-3$ is a quadratic residue $\pmod{p}$ and $2$ is not, so $x$ must be even. In Section 4, we construct a positive density set $S$ of primes $p$ (depending on $a,b$) for which $a^{x}\equiv b\pmod{p}$ is solvable and for which the smallest solution $\ell(p)$ of the congruence does enjoy the required equidistribution property for all fixed $m$ by adapting the method of Lenstra [18]. We then apply Lemma 3.1 to this subset $S$ of primes in place of $P_{a}$ (in which case showing the existence and positivity of $d_{\mathbb{P}}(S)$ requires some work).

The main difficulty then is that we need to estimate (3.5) in all ranges of $m$, not only for $m$ fixed (even though the case of bounded $m$ should give the main term in (3.5) and larger $m$ should only contribute an error term). This will be achieved in four steps, carried out in different sections.

• (i)

  We handle the case of fixed $m$ (say $m\leq N$) in Section 6, making use of the equidistribution of the set $S$ in residue classes, which in turn is proved in Section 4.

• (ii)

  The contribution of medium-large $m$ (say $N\leq m\leq\max\{p,q\}^{c}$ for some small constant $c>0$) is handled in Subsection 7.2 using the effective version of the Chebotarev density theorem stated in Lemma 2.1.

• (iii)

  The case of very large $m$ (say $\max\{p,q\}/\exp(\log\max\{p,q\})^{1/2})\leq m\leq\max\{p,q\}$) is handled (unconditionally) by applying Selberg’s sieve in Subsection 7.1. The range here is optimal in the sense that this argument (which starts by dropping the condition $m\mid\ell(p)-\ell(q)$) would not work in any larger regime.

• (iv)

  The remaining case of large $m$ ($\max\{p,q\}^{c}\leq m\leq\max\{p,q\}/\exp(\log\max\{p,q\})^{1/2})$) is where we utilize Hypothesis 1.2. This case is dealt with in Subsection 7.3.

Combining the estimates for these four different regimes will yield Theorem 1.3.

We comment on some difficulties arising with controlling the contribution of large values of $m$. To bound the sum in (3.5) one has to bound the number of primes $x/2\leq p\leq x$ (or more generally $x_{1}\leq p\leq x_{2}$) satisfying $\ell(p)\equiv r\pmod{m}$ summed over all $r\pmod{m}$. (The contribution of large $m$ would be too large if the values $\ell(p)\pmod{m}$ attained only a few values, so we cannot just drop the condition on $\ell(p)$ and work only with the congruence conditions $p\equiv 1\pmod{m}$.) This condition can be naturally interpreted as $p$ splitting completely in a certain field extension, at least for $p\in S$, where $S$ is the set constructed in Section 4.

If $m$ is small (say $m\leq x^{1/4-\epsilon}$), one can apply the GRH-conditional Chebotarev density theorem for all $r$ separately (see case (ii) above). If $m$ is of magnitude $\sqrt{x}$, one can barely apply the Chebotarev density theorem for a single value of $r$ directly, and to control all $m$ values of $r$ one would need a uniform error term. If $m$ is much larger than $\sqrt{x}$, say $x^{3/4}$, the GRH-conditional square root error term is inapplicable. It is here that we use Hypothesis 1.2.

Note that while for fixed $m$ (see case (i)) we need exact (asymptotic) equidistribution, for large values of $m$ we only need that the residues $\ell(p)\pmod{m^{\prime}}$ do not obtain a small set of values very often. Heuristically each value $\pmod{m^{\prime}}$ occurs roughly $1/m^{\prime}$ of the time (even with $m^{\prime}$ quite large), but we only need that each value occurs at most $\max\{(1/m^{\prime})^{\epsilon},1/(\log y)^{2}\}$ of the time. This is indeed what Hypothesis 1.2 tells us.

Let $h$ be the largest integer such that $|b|$ is a perfect power of order $h$. Recall from Section 2 that we can assume $a$ is not a perfect power. Let $S\subset\mathbb{P}$ (which depends on $a$ and $b$) be a set of primes defined as

Note that for any $p\in S$ we have $\textup{ord}_{p}(b)\mid\frac{p-1}{2h}=\textup{ord}_{p}(a)$, so the congruence $a^{x}\equiv b\pmod{p}$ has a solution.

Let $\ell(p)$ be the smallest nonnegative solution to $a^{x}\equiv b\pmod{p}$ for $p\in S$. For each $m,d,r\in\mathbb{N}$, let

Note then that for $p\in S_{m,d,r}$ any solution to $a^{x}\equiv b\pmod{p}$ satisfies $x\equiv r\pmod{m}$. Note also that

Indeed, for the forward implication note that if $p\in S$ and $\ell(p)=r+jm$, then $a^{\ell(p)}\equiv b\pmod{p}$ is equivalent to $ba^{-r}\equiv a^{jm}\pmod{p}$, and here $a$ is a $2h$th power $\pmod{p}$. Conversely, suppose that $p\in S$, $md\mid\textup{ord}_{p}(a)$ and $ba^{-r}\equiv x^{2hm}\pmod{p}$. Then by the assumption on $\textup{ord}_{p}(a)$ we have $x^{2h}\equiv a^{j}$ for some $j$, so $ba^{-r}\equiv a^{jm}\pmod{p}$ for some $j$, and this implies $r+jm\equiv\ell(p)\pmod{m}$.

Our goal in this section is to prove the following two lemmas.

Before proving these lemmas, we make some preliminary considerations.

We build on the arguments of Lenstra in [18]. Let

Clearly if $m\equiv 0\pmod{|2ab|}$, then $\zeta_{|4abh|}\in\mathbb{Q}(\zeta_{2hmd})$. Since $|b|$ is a perfect $h$th power, $|b|^{1/2h}\in\mathbb{Q}(\zeta_{|4b|})$ (indeed, if $c=|b|^{1/h}$, then $\sqrt{c}\in\mathbb{Q}(\zeta_{|4c|})\subset\mathbb{Q}(\zeta_{|4b|})$). Furthermore, $b^{1/2h}$ is either $|b|^{1/2h}$ or $\zeta_{4h}^{j}|b|^{1/2h}$ for some $j$. In either case,

For a prime $\ell$, define

to be the smallest power of $\ell$ which does not divide $2h$, and let

We can now characterize the set $S_{m,d,r}$ as follows.