Two dimensional covering systems and possible prime producing $a^m-b^n$

1. Problem Statement

The paper investigates the distribution of prime values generated by the expression $|a^m - b^n|$ for integers $a, b \ge 2$ and non-negative integers $m, n$.

The central question is: Under what conditions does $|a^m - b^n|$ take on infinitely many distinct prime values?

The authors identify a specific obstruction to this phenomenon: the existence of a non-zero integer $Q$ such that $\gcd(a^m - b^n, Q) > 1$ for all $m, n \ge 1$. If such a $Q$ exists, the expression is "covered" by the prime factors of $Q$, meaning it can only be prime (or a prime power) for finitely many pairs $(m, n)$. The paper aims to characterize these obstructions and conjecture that they are the only reasons why $|a^m - b^n|$ might fail to produce infinitely many primes.

2. Methodology

The authors employ a combination of number-theoretic tools, algebraic structures, and heuristic probabilistic modeling:

A. Two-Dimensional Covering Systems

The core mathematical tool is the two-dimensional covering system.

• Definition: A set of integer triples $\{(u_i, v_i, r_i)\}$ is a covering system if for every pair of integers $(m, n)$, there exists an index $i$ such that $m v_i \equiv n u_i \pmod{r_i}$.
• Connection to Primes: The authors establish a bijection between the condition "$\gcd(a^m - b^n, Q) > 1$ for all $m, n$" and the existence of a two-dimensional covering system derived from the multiplicative orders of $a$ and $b$ modulo the prime factors of $Q$.
• Construction:
  • For a prime $p \nmid ab$, let $r = \text{ord}_p(a)$ and $s = \text{ord}_p(b)$.
  • They define a reduced triple $(u, v, L)$ where $L = \text{lcm}(r, s)$, $u = L/s$, and $v$ is derived from the discrete logarithm relationship between $a$ and $b$ modulo $p$.
  • The set of pairs $(m, n)$ where $p \mid (a^m - b^n)$ corresponds exactly to the lattice $S(u, v, L)$.
  • If a finite set of primes $Q = p_1 \dots p_k$ covers all $(m, n)$, the corresponding reduced triples form a two-dimensional covering system.

B. S-Unit Theorem and Siegel's Theorem

The authors utilize Siegel's S-unit theorem to prove that if a covering obstruction exists (i.e., condition (1.1) holds), then $|a^m - b^n|$ can be a prime or prime power for only finitely many pairs $(m, n)$. This rigorously establishes that covering systems are a sufficient condition for the finiteness of prime values.

C. Heuristic Probabilistic Modeling (Cramér Model)

To predict the density of primes when no covering system exists, the authors adapt the Cramér heuristic:

1. Counting Pairs: They estimate the number of pairs $(m, n)$ such that $|a^m - b^n| \le x$, finding it grows as $\frac{(\log x)^2}{\log a \log b}$.
2. Prime Probability: They adjust the standard probability $1/\log x$ by local factors accounting for divisibility by small primes and the condition $\gcd(m, n) = 1$.
3. The Constant $\kappa_{a,b}$: They define a limiting constant $\kappa_{a,b}$ derived from the proportion of pairs $(m, n)$ coprime to a sequence of composite moduli $q_k$.
4. Conjectured Asymptotic: They propose that the number of primes is asymptotically:
   $$\#\{|a^m - b^n| \le x : |a^m - b^n| \text{ is prime}\} \sim c_{a,b} \log x$$
   where $c_{a,b} = \frac{2ab \kappa_{a,b}}{\phi(ab) \log a \log b}$.

3. Key Contributions

1. Formulation of Conjecture 1: The authors conjecture that for $a, b \ge 2$ (neither being a perfect power), $|a^m - b^n|$ produces infinitely many primes if and only if there is no integer $Q$ such that $\gcd(a^m - b^n, Q) > 1$ for all $m, n$.
2. Generalization to Perfect Powers (Conjecture 2): They extend the conjecture to cases where $a$ or $b$ are perfect powers ($a=A^k, b=B^\ell$), modifying the obstruction condition to require coprimality of exponents with the power indices.
3. Algorithmic Construction: They provide a method to construct all triples $(a, b, Q)$ satisfying the covering condition using two-dimensional covering systems. This allows for the systematic generation of "counter-examples" (pairs that produce few primes).
4. Classification of Obstructions: They prove that non-trivial covering systems imply that $a-1$ and $b-1$ must have odd prime factors, ruling out cases where $a$ or $b$ are powers of 2 or of the form $2^\ell + 1$.

4. Results and Computational Evidence

The authors conducted extensive computational experiments to validate their heuristics and conjectures:

• Verification of the Obstruction: They identified specific pairs $(a, b)$ with $b \le 100$ and $a+b \le 500$ that produced very few primes (e.g., $(9, 74)$, $(29, 34)$, $(13, 302)$). For these pairs, they successfully constructed the corresponding two-dimensional covering systems, confirming the obstruction hypothesis.
• Validation of the Asymptotic Formula:
  • They calculated the number of primes $\Pi_{a,b}(100)$ for various pairs.
  • They compared the observed counts against their predicted constant $G_2(a, b)$.
  • Table 3 and Table 6 show that the observed mean number of primes closely matches the predicted values (e.g., for $(26, 149)$, prediction was 100, observed was 115; for $(128, 253)$, prediction 100, observed 102).
• Convergence of Constants: They computed the sequence $\kappa_{a,b}(k)$ for increasing $k$ (Table 2), observing that these values appear to converge to a stable non-zero constant, supporting the existence of the asymptotic density.

5. Significance

• New Application of Covering Systems: The paper introduces a novel application of two-dimensional covering systems to the study of prime values in exponential Diophantine equations, moving beyond the traditional one-dimensional covering systems used in problems like the Erdős–Selfridge problem.
• Refining Prime Distribution Conjectures: It provides a precise conjecture for the density of primes in the sequence $|a^m - b^n|$, including a specific constant factor that accounts for local modular obstructions. This parallels the Bateman-Horn conjecture for polynomials but adapts it to the non-polynomial, exponential setting.
• Complete Characterization of "Bad" Cases: By linking the finiteness of prime values directly to the existence of covering systems, the paper offers a complete structural explanation for why certain pairs $(a, b)$ fail to generate primes, distinguishing them from the "generic" case where infinitely many primes are expected.
• Computational Benchmarking: The extensive numerical data serves as a strong empirical foundation for the conjectures, highlighting the accuracy of the proposed heuristic even for relatively small values of $x$.

In summary, Granville and Pappalardi provide a rigorous framework linking algebraic covering systems to the distribution of primes in exponential sequences, proposing that covering systems are the sole obstruction to infinitude of primes in $|a^m - b^n|$, and backing this with strong computational evidence.