Erdős–Granville–Pomerance–Spiro conjecture

This entry is a partial result on an open problem. It does not claim a solution of the general conjecture.

If 𝒜\mathcal A is a set of positive integers of natural density zero, the conjecture asserts that the inputs n≥2n\ge2 whose proper-divisor sum s(n)=σ(n)−ns(n)=\sigma(n)-n belongs to 𝒜\mathcal A also have natural density zero. The full conjecture remains open. Original paper, Conjecture 4 · Erdős Problem 955

The written proofs establish the preimage conclusion for every density-zero target set on a fixed union of input families of natural density approximately 53.46%.

Inputs Density added to the union Proof
n=pqℓn=pq\ell with p>qℓp>q\ell and q>ℓq>\ell (log2)2(\log 2)^2 Two dominant primes
Largest prime p≤np\le\sqrt n, with the cofactor and second prime satisfying the logarithmic size inequalities About 3.91 percentage points Bilinear collision count and prime sieve
n=pqrwn=pqrw with p>q>rp>q>r prime, p>np>\sqrt n, r>w3r>w^3, and q≤rwq\le rw About 1.50 percentage points Rational cofactor ratios and quadratic norms

The proofs use second-moment estimates for divisor-sum collisions after discarding an arbitrarily small upper proportion of inputs. The reproducible checks exercise some of the algebraic and congruence steps on finite ranges.

python3 results/erdos-granville-pomerance-spiro/verify.py

Lean status: None.

Research discussion