# Number of primes of the form $a^m \pm b^n$ with $a,b$ both prime and $\leq 89$

In an answer to my own question, I showed that if $p$ is an odd prime and $p=a^m \pm b^n$ with positive integers $a,b$ relatively prime to $p$, then $p$ does not simultaneously divide the Fermat quotients $\frac{a^{p-1}-1}{p}$ and $\frac{b^{p-1}-1}{p}$.

Once upon a time, this result would have been of some interest because it implies the first case of Fermat's Last Theorem (FLT) for certain prime exponents $p$. More precisely, Wieferich, Mirimanoff, and others showed that if the first case of FLT fails for the prime $p$, then $\frac{a^{p-1}-1}{p}$ will be divisible by $p$ for every prime number less than or equal to 89.

In particular, the above two paragraphs show that the first case of FLT holds if $p = a^m \pm b^n$ for some primes $a, b \leq 89$.

Although FLT was proved by independent methods, results like the one in my other question still have some interest. For instance, as far as I know, it is still unknown whether there are nontrivial solutions $x,y,z$ in the cyclotomic field $\mathbb{Q} (\zeta_p)$ (whether they are all relatively prime to $p$ or not) that satsify

$$x^p + y^p = z^p$$

In On the first case of the fermat theorem for cyclotomic fields", Kolyvagin proves that there are no such solutions relatively prime to $p$ if each of the numbers $\frac{a^{p-1}-1}{p}$ with $a$ prime and $\leq 89$ is relatively prime to $p$. In particular, this is true when $p$ has the form $p=a^m \pm b^n$ with $a, b$ primes $\leq 89$.

I would presume that the set of such primes is quite scarce (although the possibility $p = a^m-b^n$ throws me a bit), so my question is:

Are there known heuristics or results for the set of primes $p=a^m \pm b^n$ with $a,b$ primes less than $89$ (one of them, of course, being 2)?

-

Non-expert disclaimer here.

Applying some heuristics, you get that there are $O(\log N)$ primes of the form $a^m-b^n$ for fixed $a$ and $b$.

To see this, let's count the values taken by $a^m-b^n$ in the range $[0,N]$. I claim there are $O(\log^2N)$ such terms. If $m$ and $n$ are in the range $[0,2\log N]$, this accounts for $O(\log^2N)$ pairs, a good fraction of which are in the given range.

If $m > 2\log N$, then there is at most one $n$ such that $a^m-b^n$ is in the range. To complete the bound, we need to give an upper bound on the $m$'s for which there can exist $n$'s such that $a^m-b^n$ is in the range.

Consider $m > 2\log N$ and assume that $|a^m-b^n| < N$ so that $n \gtrsim \log N$ also. Notice that $|a^m-b^n|=a^m|1-b^n/a^m|\approx a^m\log(b^n/a^m)=a^m(n\log b-m\log a)$. By Baker et al's results on logarithmic forms, $|n\log b-m\log a|>m^{-k}$ for a constant $k$ that depends on $a$ and $b$, so that $|a^m-b^n|\gtrsim a^m/m^k$. In particular, if $a^m > N(\log N)^k$, you can't be in range. This shows that there are at most $\log^2N$ terms of the form $a^m-b^n$ in range. Of those, how many are prime?

The heuristic would be that the "density" of difference powers is $\log N/N$ (the derivative of $\log^2N$). The density of primes is $1/\log N$ by the PNT. So since they are `obviously' independent, the density of primes of this form is $1/N$. So... there should be infinitely many according to this heuristic, but there should be $O(\log N)$ such primes up to $N$.

-
You might be able to simplify this analysis by noting that one of a or b must be 2. Gerhard "Ask Me About Even Primes" Paseman, 2012.06.07 –  Gerhard Paseman Jun 8 '12 at 0:46
I'm guessing it wouldn't change much... –  Anthony Quas Jun 8 '12 at 0:59

Hi there, If you're only interested in heuristics, then if you replace $89$ by $x$, fix $m$ and $n$, fix $\pm$ to be $+$ or $-$, fix one of $a,b$ to be $2$, and let the other variable range over primes less than $x$, then it is in the right form for the Bateman-Horn conjecture to be applied to. See for example,

P. T. Bateman, R. A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Mathematics of Computation 16 (1962), 363--367.

(Say $a=2$, $b$ ranges over primes less than $x$, $m$ and $n$ are fixed, and $\pm$ is $+$. Then one can use the case of Bateman-Horn for two polynomials simultaneously, one polynomial being $z$, the other one being $z^n+2^m$.) Then depending on which other variables you want to vary, you can apply Bateman-Horn to each case like this.

Don't know how accurate it would be for $x=89$ ! But it should be more accurate for $x \rightarrow \infty$. The usual caveat about this still being a conjecture applies.

-