Factor-difference sets: do $k$ integers always share $\geq k$ common factor differences? (Erdős #885)
Statement
For an integer $n\geq 1$ define its factor difference set $$D(n)=\{\lvert a-b\rvert : n=ab,\ a,b\in\mathbb{Z}_{\geq 1}\},$$ the set of gaps between complementary factor pairs of $n$ (for example $D(12)=\{11,4,1\}$ from the factorizations $12=1\cdot 12=2\cdot 6=3\cdot 4$). Is it true that for every $k\geq 1$ there exist integers $N_1<N_2<\cdots<N_k$ such that $$\Bigl\lvert\bigcap_{i=1}^{k} D(N_i)\Bigr\rvert\geq k,$$ i.e. $k$ integers whose factor difference sets share at least $k$ common values?
Acceptance. FULLY RESOLVES: prove the statement for all $k$ (a complete proof, Lean/Coq preferred, else a full written proof), OR disprove it by exhibiting a specific $k$ and proving that no tuple $N_1<\cdots<N_k$ achieves $\lvert\bigcap_i D(N_i)\rvert\geq k$. ADVANCES: settle a new individual case $k\geq 5$ — for $k=5$, exhibit explicit integers $N_1<\cdots<N_5$ and five values $g_1,\ldots,g_5$ such that each $g_j\in D(N_i)$ for all $i$, giving for every relevant pair the factorization $N_i=a\cdot b$ with $\lvert a-b\rvert=g_j$ — a fully machine-checkable witness; larger $k$ likewise. A proof that suitable tuples exist for all $k$ up to a new explicit bound (beyond the current $k=4$) also qualifies. Deliver the explicit tuple(s) with certified common differences and factorizations, or the proof file.
Background
A question of Erdős and Rosenfeld [ErRo97]; listed as open on erdosproblems.com/885 (fetched 2026-07-21, status 'open', tagged 'number theory | divisors'). Erdős and Rosenfeld [ErRo97] proved the case $k=2$; Jiménez-Urroz [Ji99] proved $k=3$; and Bremner [Br19] proved $k=4$, the last via explicit computations on elliptic curves. The statement is open for every $k\geq 5$. Crucially, for each fixed $k$ the claim is an existence statement certified by a finite object — a tuple $N_1<\cdots<N_k$ together with $\geq k$ values lying in every $D(N_i)$, each accompanied by the factorization $N_i=a\cdot b$ realizing it — so a single new value of $k$ is a fully checkable target rather than an asymptotic. A formalized statement exists in the DeepMind formal-conjectures repository (FormalConjectures/ErdosProblems/885.lean). No cash prize is attached. The attacker's tools: Diophantine and elliptic-curve search extending Bremner's $k=4$ construction — hunting for an explicit quintuple $N_1<\cdots<N_5$ whose factor difference sets share five common differences — guided by parametric families of integers with prescribed factor gaps.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #885 (T. F. Bloom) | website |
| REF-02 | Formalized statement of Erdős #885 (DeepMind formal-conjectures, Lean) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.