Existence and value of the limit of $(\log_2 n_k)/k^2$ for Erdős–Evans prime sets satisfying the divisibility condition (*)

For a set $P$ of primes and a subset $X \subseteq P$, write $\Pi X$ for the product of the primes in $X$. Say that $P$ satisfies condition $(*)$ if $\gcd(\Pi A - \Pi B, \Pi P) = 1$ for every pair of disjoint non-empty subsets $A, B \subseteq P$. Erdős and Evans (1996) proved that such $k$-element sets exist for every $k$, and for $n_k = \min\{\Pi P : |P| = k,\ P \text{ satisfies condition } (*)\}$ they established $1 - 2/k < (\log_2 n_k)/k^2 < \log_2(3 + \varepsilon)$ for every $\varepsilon > 0$ and all sufficiently large $k$ (the lower bound holds for all $k \ge 2$). The question is whether $\lim_{k \to \infty} (\log_2 n_k)/k^2$ exists, and if so which value $L \in [1, \log_2 3]$ it takes — equivalently, whether $n_k = \alpha^{(1+o(1))k^2}$ for a constant $\alpha \in [2, 3]$, and what $\alpha$ is. If the limit does not exist, the problem is to determine the set of limit points of $(\log_2 n_k)/k^2$ within $[1, \log_2 3]$. No resolution of this question is known in the literature to date.

Background

This problem originates in the theory of representations of graphs modulo $n$. A finite graph $G$ is representable modulo $n$ if there exist distinct integers $a_1, \ldots, a_r \in \{0, \ldots, n-1\}$ (one per vertex) such that two vertices are adjacent exactly when $\gcd(a_i - a_j, n) = 1$; the representation number $\mathrm{rep}(G)$ is the smallest such $n$. The notion grew out of the theory of orthogonal Latin square graphs — graphs whose vertices are Latin squares of a common order, two vertices being adjacent exactly when their squares are orthogonal, meaning that superimposed the two squares display every ordered pair of symbols exactly once: Lindner, E. Mendelsohn, N. S. Mendelsohn and Wolk (1979) proved that every finite graph can be represented as an orthogonal Latin square graph, and Erdős and Evans (1989) gave a new, simpler proof of this fact in arithmetic form by proving that every finite graph is representable modulo some $n$. The engine of their proof is a prime-set lemma: for every $m$ there exist $m$ distinct primes $p_1, \ldots, p_m$ such that $\gcd(\Pi A - \Pi B, p_1 p_2 \cdots p_m) = 1$ for all disjoint non-empty $A, B \subseteq \{p_1, \ldots, p_m\}$, where $\Pi X$ denotes the product of the primes in $X$. The construction chooses primes larger than $3^m$ that avoid a bounded set of forbidden residue classes $a/b \bmod p_i$ — here Dirichlet's theorem on primes in arithmetic progressions, which guarantees infinitely many primes in every residue class coprime to its modulus, supplies the primes — and the graph representation is then built by assigning to each vertex the product of the primes corresponding to non-incident edges. Erdős and Evans (1996) isolated this combinatorial condition on primes — call it condition $(*)$ — and initiated its quantitative study. Writing $n_k$ for the smallest $\Pi P$ over all $k$-element prime sets $P$ satisfying $(*)$, they proved: (Theorem 1) if $P$ is a $k$-element set satisfying $(*)$ with smallest prime $p$, then $k \le \log_2(p-1) + 2$, and if $P$ cannot be extended to a $(k+1)$-element set satisfying $(*)$, then $k \ge \min\{r : 3^{r-1} - 2^{r-1} \ge p-1\}$; and (Theorem 2) the bounds $1 - 2/k < (\log_2 n_k)/k^2$ for $k \ge 2$ and $(\log_2 n_k)/k^2 < \log_2(3 + \varepsilon)$ for every $\varepsilon > 0$ and all sufficiently large $k$. (The terms appearing here are elementary: $\Pi P$ is just the product of all primes in $P$, and condition $(*)$ says that no difference of two sub-products shares a prime factor with the total product.) Thus $2^{k^2-2k} < n_k < (3 + \varepsilon)^{k^2}$ for all sufficiently large $k$, so every limit point of $(\log_2 n_k)/k^2$ lies in $[1, \log_2 3]$, and if the limit $L$ exists then $n_k = \alpha^{(1+o(1))k^2}$ with the exponential base $\alpha = 2^L$ pinned only to the interval $[2, 3]$. Condition $(*)$ is equivalently the statement that the squarefree integer $n = \Pi P$ (a positive integer with no repeated prime factor) satisfies $\gcd(n, d_2 - d_1) = 1$ for every pair of coprime divisors $1 < d_1 < d_2 < n$, which is the form under which the sequence $n_k$ is recorded in the On-Line Encyclopedia of Integer Sequences (OEIS) as A287935: $2, 6, 105, 23023, 16028909, 40502880317$, with $a(7) \le 1378987557700217$ (a 2017 upper bound by Giovanni Resta, still not known to be tight). A related but distinct research line — Evans–Isaak–Narayan (2000), Evans–Narayan–Urick (2009) and subsequent work — studies the representation number $\mathrm{rep}(G)$ of specific graph classes; that line uses the existence of prime sets satisfying $(*)$, not the asymptotics of $n_k$.

Problem Statement

Let $n_k$ be the smallest product $\Pi P$ of a set $P$ of $k$ primes satisfying the Erdős–Evans divisibility condition $(*)$: $\gcd(\Pi A - \Pi B, \Pi P) = 1$ for all disjoint non-empty subsets $A, B \subseteq P$, where $\Pi X$ denotes the product of the primes in $X$. Erdős and Evans proved $1 - 2/k < (\log_2 n_k)/k^2$ for $k \ge 2$ and $(\log_2 n_k)/k^2 < \log_2(3 + \varepsilon)$ for every $\varepsilon > 0$ and all sufficiently large $k$. Determine whether $\lim_{k \to \infty} (\log_2 n_k)/k^2$ exists. If it exists, determine its value $L \in [1, \log_2 3]$ — equivalently, determine the constant $\alpha = 2^L \in [2, 3]$ in the asymptotic $n_k = \alpha^{(1 + o(1))k^2}$. If it does not exist, determine the set of limit points of $(\log_2 n_k)/k^2$ within $[1, \log_2 3]$. Partial progress of independent interest: (a) shrink the interval $[1, \log_2 3]$ containing the limit superior and limit inferior; (b) determine $n_7$ exactly (currently only the upper bound $n_7 \le 1378987557700217$ is known).

References

1. Paul Erdős & Anthony B. Evans, 'Sets of prime numbers satisfying a divisibility condition', Journal of Number Theory 61(1):39–43, 1996. DOI: 10.1006/jnth.1996.0135, https://doi.org/10.1006/jnth.1996.0135
2. Paul Erdős & Anthony B. Evans, 'Representations of graphs and orthogonal latin square graphs', Journal of Graph Theory 13(5):593–595, 1989. DOI: 10.1002/jgt.3190130509, https://doi.org/10.1002/jgt.3190130509
3. C. C. Lindner, E. Mendelsohn, N. S. Mendelsohn & B. Wolk, 'Orthogonal latin square graphs', Journal of Graph Theory 3(4):325–338, 1979. DOI: 10.1002/jgt.3190030403, https://doi.org/10.1002/jgt.3190030403
4. Anthony B. Evans, 'Orthomorphism Graphs of Groups', in: Orthogonal Latin Squares Based on Groups (Developments in Mathematics 57), Springer, 2018, pp. 203–255. DOI: 10.1007/978-3-319-94430-2_8, https://doi.org/10.1007/978-3-319-94430-2_8
5. OEIS Foundation, 'A287935: a(n) is the smallest squarefree number k with n prime factors such that gcd(k, d2-d1) = 1 for all coprime pairs of divisors of k, 1 < d1 < d2 < k', https://oeis.org/A287935
6. Anthony B. Evans, Darren A. Narayan & James Urick, 'Representations of graphs modulo n: some problems', Bulletin of the Institute of Combinatorics and its Applications 56:85–97, 2009. zbMATH identifier 1175.05098
7. Anthony B. Evans, Garth Isaak & Darren A. Narayan, 'Representations of graphs modulo n', Discrete Mathematics 223(1–3):109–123, 2000. DOI: 10.1016/S0012-365X(00)00062-5, https://doi.org/10.1016/S0012-365X(00)00062-5