$(a,a)$-Carmichael numbers and greatest common divisors of $p-a$

Technical Summary: (A, A)-Carmichael Numbers and Greatest Common Divisors of $P - A$

Problem Statement
The paper addresses the distribution and construction of $(a, a)$-Carmichael numbers. A composite, squarefree integer $n$ is defined as an $(a, a)$-Carmichael number if for every prime factor $p$ of $n$, the condition $p - a \mid n - a$ holds. This generalizes the classical definition of Carmichael numbers (where $a=1$), which satisfy $p-1 \mid n-1$.

The central problem investigated is whether there exist infinitely many such numbers with a bounded greatest common divisor (GCD) of the terms $p-a$. Specifically, for a given $(a, a)$-Carmichael number $n$ with prime factors $p_1, \dots, p_m$, let $K = \gcd(p_1 - a, \dots, p_m - a)$. The paper seeks to determine the lower bound for $C_\nu(X, a)$, the count of $(a, a)$-Carmichael numbers up to $X$ where $K = \nu$.

This inquiry is framed as an intermediate step toward a broader open question: whether there are infinitely many $(a, a)$-Carmichael numbers divisible by a fixed prime $Q$. Previous constructions of Carmichael numbers (e.g., Alford, Granville, and Pomerance [1]) generally required the GCD $K$ to grow as $n$ increases, preventing the construction of infinitely many numbers divisible by a fixed prime. The author aims to show that $K$ can be held constant (specifically $K=\nu$) while still generating a large set of such numbers.

Methodology
The proof relies on a conditional construction framework that modifies the standard combinatorial approach used in [1], [17], and [18]. The methodology involves the following key components:

1. Conditional Assumption: The results are conditional on Conjecture 2, a weakened version of a conjecture by Heath-Brown regarding the first prime in an arithmetic progression. The conjecture posits that for any $A \ge 2$, if $l$ is sufficiently large and $(b, l) = 1$, there exists a prime $p \equiv b \pmod l$ such that $p < l(\log l)^A$. This ensures the existence of small multipliers in arithmetic progressions.

2. Dual Construction of Prime Sets:

   • The author constructs two disjoint sets of primes, $Q_1$ and $Q_2$, derived from products of primes $r$ in the range $[z/2, z]$.
   • These sets are used to form large integers $L_1$ and $L_2$. Crucially, the construction ensures that the Carmichael lambda function $\lambda(L_1 L_2)$ is extremely small relative to $L_1 L_2$ (specifically $\lambda(L_1 L_2) \le e^{4/5 z}$).
   • Two sets of primes, $P_{k_1}$ and $P_{k_2}$, are defined based on arithmetic progressions modulo $L_1$ and $L_2$ respectively. The parameters $k_1$ and $k_2$ are chosen to be small integers such that primes in $P_{k_1}$ are of the form $d_1 k_1 \nu + a$ and primes in $P_{k_2}$ are of the form $d_2 k_2 \nu + a$.

3. Combinatorial Selection:

   • Using a theorem by van Emde Boas, Kruyswijk, and Meshulam regarding zero-sum subsequences in $(\mathbb{Z}/M\mathbb{Z})^\times$, the author demonstrates that there exist subsets of primes within $P_{k_1}$ and $P_{k_2}$ whose products, $n_1$ and $n_2$, satisfy specific congruence conditions.
   • Specifically, $n_1 \equiv 1 \pmod{L_1 L_2 k_1 k_2 k_3 \nu}$ and $n_2 \equiv 1 \pmod{L_1 L_2 k_1 k_2 k_3 \nu}$, where $P = L_1 L_2 k_1 k_2 k_3 \nu + a$ is a specific prime found via the conjecture.

4. Final Construction:

   • The final $(a, a)$-Carmichael number is constructed as $n = P n_1 n_2$.
   • The structure ensures that for any prime factor $p$ of $n$, $p - a$ divides $n - a$.
   • A critical lemma proves that for this construction, $\gcd(p_1 - a, p_2 - a) = \nu$ for primes from the different sets, ensuring the global GCD $K$ is exactly $\nu$.

Key Contributions and Results
The primary result is Theorem 1, which establishes a lower bound for the number of $(a, a)$-Carmichael numbers with a fixed GCD $\nu$.

• Theorem: Assuming Conjecture 2 holds, for any integer $a$ and any natural number $\nu$ such that $(a, \nu) = 1$ and $a, \nu$ have opposite parity:
  $$C_\nu(X, a) \ge X^{1 - (2+o(1)) \frac{\log \log \log \log X}{\log \log \log X}}$$
• Significance of the Bound: This lower bound is identical to the one previously established by the author in [17] for the total count of classical Carmichael numbers ($C(X, 1)$).
• Departure from Tradition: Unlike traditional constructions where the GCD $K$ must grow with $n$ to ensure the existence of sufficient primes, this result demonstrates that one can fix $K = \nu$ and still achieve a lower bound that is "close to best possible."

Significance and Claims
The paper claims that this result is a significant departure from previous methods in the study of Carmichael numbers.

• Bounded GCD: It resolves a specific intermediate question (Question 5 in the introduction) by showing that the number of $(a, a)$-Carmichael numbers with a bounded GCD $\nu$ is not negligible; rather, it is of the same asymptotic order as the total set of Carmichael numbers.
• Implications for Open Questions: While the paper acknowledges that the full question of whether there are infinitely many $(a, a)$-Carmichael numbers divisible by a fixed prime $Q$ remains out of reach, this result suggests that the constraint of a bounded GCD does not significantly reduce the density of such numbers.
• Optimality: The author notes that the derived lower bound is close to the conjectured upper bound for the total number of Carmichael numbers (proposed by Pomerance), suggesting that the set of $(a, a)$-Carmichael numbers with bounded $K$ constitutes a substantial portion of the total set.

The paper does not claim to prove the infinitude of such numbers unconditionally, nor does it resolve the question for fixed prime divisors $Q$ directly. Instead, it provides a conditional proof that the "bounded GCD" constraint is compatible with the high density of Carmichael numbers.