← All papers
First page of An Average-Order Theorem for a Shifted Pairwise-Coprime Extremal Problem

An Average-Order Theorem for a Shifted Pairwise-Coprime Extremal Problem

Eric Li

math.NT Jun 16, 2026 · v2 math.CO
All forty named theorems, lemmas, propositions and corollaries are formalized in Lean 4 with Mathlib, developed with OpenAI Codex, with a public GitHub repository.
For $n\ge 2$, let $M(n)$ be the supremum of $\sum_{a\in A}1/(n-a)$ over pairwise coprime sets $A\subset[1,n)$. Erdős asked whether $M(n)\le \sum_{p<n}1/p+O(1)$ uniformly in $n$. We prove the quantitative average-order formula $\sum_{n\le N}M(n)=e^{-γ}N\log\log N+O(N)$. The proof combines the self-rough lower construction $\{n-d:P^{-}(n-d)>d\}$ with a bounded-cost dual certificate and Buchstab–de Bruijn estimates. We also show $M(n)=(e^{-γ}+o(1))\log\log n$ for almost all $n$, with a quantitative exceptional-set bound, so Erdős's inequality holds for almost all $n$. The argument combines a long-interval two-dimensional beta sieve for two moving forbidden residue classes with an exact finite singular-series cancellation. The remaining obstacles to a full variance estimate are a shifted-prime second moment for $d>\sqrt{2N}$ and finite-$u$ rough correlations in the intermediate tail, yielding a precise conditional criterion. For every $\varepsilon>0$ we also prove the uniform pointwise bound $M(n)\le(2+\varepsilon)\log\log n+O_{\varepsilon}(1)$ and explain the linear-sieve barrier at the constant $2$. The results of this paper have been formally verified in Lean.

Erdős asked whether every pairwise coprime set A in [1,n) satisfies the bound sum 1/(n-a) ≤ sum_{p<n} 1/p + O(1). The paper studies the extremal quantity M(n), defined as the supremum of this sum.

A lower bound comes from a self-rough construction {n-d : P^-(n-d) > d}, and an upper bound from a bounded-cost dual certificate. The two bounds are controlled in mean using Buchstab–de Bruijn rough-number estimates. A two-dimensional beta sieve with singular-series cancellation handles the almost-all result, and a linear sieve gives the pointwise bound. All named results are formalized in Lean 4 with Mathlib, with no admitted proofs or project-defined axioms.

The average-order formula sum_{n≤N} M(n) = e^{-γ} N log log N + O(N) is proved. M(n) = (e^{-γ}+o(1)) log log n holds for almost all n, and M(n) ≤ (2+ε) log log n + O_ε(1) holds for every n. A conditional criterion is given for the full pointwise inequality.