Count coprime pairs with equal sum-of-divisors: is $h(x)>x^{2-o(1)}$? (Erdős #824)
Statement
For $x\geq 1$ let $h(x)$ count the pairs of integers $1\leq a<b<x$ with $(a,b)=1$ and $\sigma(a)=\sigma(b)$, where $\sigma$ is the sum-of-divisors function and $(a,b)$ denotes the greatest common divisor. Is it true that $$h(x)>x^{2-o(1)}?$$ Equivalently, does $\log h(x)/\log x\to 2$ as $x\to\infty$? Since trivially $h(x)\leq\binom{x}{2}<x^2$, this asks for a near-maximal count of coprime pairs sharing the same divisor sum.
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean/Coq preferred, otherwise a full rigorous written proof) that $h(x)>x^{2-o(1)}$ — i.e. for every $\epsilon>0$ there is $x_0$ with $h(x)>x^{2-\epsilon}$ for all $x\geq x_0$ — OR a disproof establishing $h(x)\leq x^{2-\delta}$ for some fixed $\delta>0$ and all large $x$. ADVANCES: a proven power-saving lower bound $h(x)\gg x^{1+c}$ for an explicit constant $c>0$ (strictly beyond the currently proved $h(x)/x\to\infty$ frontier stated in the background), with full proof; or the analogous improvement for the squarefree or Weisenberg variants; or a rigorous non-trivial upper bound $h(x)\leq x^{2-\delta}$ with explicit $\delta>0$. Deliver the proof (formal or written) or the explicit bound together with its derivation.
Background
Posed by Erdős [Er59c, p.172] and again in [Er74b, p.202]; listed as open on erdosproblems.com/824 (fetched 2026-07-21, status 'open'). Erdős [Er74b] proved that $\limsup_{x\to\infty} h(x)/x=\infty$ and asserted a similar argument yields $h(x)/x\to\infty$; a complete proof that $h(x)/x\to\infty$ was later supplied by Pollack and Pomerance [PoPo16]. The conjectured $x^{2-o(1)}$ is vastly stronger than $h(x)/x\to\infty$: it demands essentially the maximal possible number of $\sigma$-collisions among coprime pairs. Two variants are recorded on the page: the same count with $(a,b)=1$ replaced by the condition that $a$ and $b$ are squarefree; and Weisenberg's variant, which instead forbids proper coprime factors $u\mid a$, $v\mid b$ with $\sigma(u)=\sigma(v)$ and $(u,a/u)=(v,b/v)=1$ (the weakest restriction still eliminating trivially duplicated pairs). Attacker's tool: Erdős-style multiplicative/sieve arguments that force many $\sigma$-collisions among coprime integers, supported by large-scale tabulation of $\sigma$ to compute $h(x)$ and empirically bracket its growth exponent.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #824 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.