Computational and Analytic Approaches to the Erdős–Pomerance Divisible Injection Problem

We report on an extensive computational and analytic investigation of Erdős Problem #710: determine f(n), the minimum length L such that there exists an injection φ: {1, …, n} → (n, n + L] ∩ ℤ with k | φ(k) for all k. The conjectured answer is f(n) = (2/√e + o(1)) · n · √(ln n/ ln ln n), where the lower bound is due to Erdős and Pomerance. We verify computationally that the matching upper bound holds for all n ≤ 10⁶ via exhaustive Hopcroft–Karp matching with zero failures. For the analytic regime n → ∞, we document 43 distinct approaches—including Cauchy–Schwarz variants, fractional matching, the Lovász Local Lemma, spectral methods, sieve bounds, semi-random nibble, and graph-theoretic techniques—each of which fails to close the gap between per-interval Hall verification and global Hall's condition. We identify the precise structural obstruction: the worst-case subset T* spans approximately 48–53% of vertices, drawn from all dyadic intervals at roughly 60% density per interval, with expansion ratio barely exceeding 1. We catalog every approach, its failure mechanism, and the computational evidence, with the aim of guiding future work on this long-standing open problem. This paper was drafted with substantial assistance from large language models (Claude, Anthropic, Opus 4.6). Readers are encouraged to reproduce the computational experiments using the scripts provided in the accompanying repository.