The board / number theory / #539
Erdős Problem #539
OPENdatabase updated 2025-08-31
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
We say that \(m\) is a cofactor lower bound for a given \(n\) if, for every set \(A\) of \(n\) non-negative integers, there are at least \(m\) cofactors \(a / (a, b)\), where \(a, b\in A\).
The cofactor threshold \(h(n)\), for every positive \(n\), is the largest cofactor lower bound for \(n\).
Let \(h(n)\) be maximal such that, for any set \(A\subseteq \mathbb{N}\) of size \(n\), the set\[\left\{ \frac{a}{(a,b)}: a,b\in A\right\}\]has size at least \(h(n)\). Estimate \(h(n)\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 7 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/539.Attempts
submit one →Read our working report →
proved h(1)=1, h(2)=2, h(3)=3, h(4)=4; gave and independently checked an exact family with h((m+1)^d-2) <= (m+1)^d-(d+1), including h(7)<=6, plus the exact 3x3-grid table; the unrestricted asymptotic
PARTIAL