Erdős Problem #824

Erdős Problem 824 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/824

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/824.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/824.tex.

FORMAL RESTATEMENT

Let $\sigma(n)=\sum_{d\mid n} d$ be the sum-of-divisors function. For $x>0$, define $h(x)$ to be the number of pairs of integers $(a,b)$ such that \[ 1\le a<b<x,\qquad \gcd(a,b)=1,\qquad \sigma(a)=\sigma(b). \] The question is:

Conjecture. Is it true that \[ h(x) > x^{2-o(1)}\qquad (x\to\infty)? \] Equivalently: is $\log h(x) / \log x \to 2$?

QUICK LITERATURE/CONTEXT CHECK

From the problem statement: Erdős proved $\limsup h(x)/x=\infty$ and claimed a similar proof for the stronger question; Pollack--Pomerance later gave a complete proof that $h(x)/x\to\infty$. The conjecture $h(x)>x^{2-o(1)}$ is substantially stronger.

I do not invoke any external results beyond those explicitly mentioned above.

ATTACK PLAN

• Proof track (ambitious): Try to build $\gg x^{2-o(1)}$ coprime pairs with equal $\sigma$ by constructing many collisions of the multiplicative function $\sigma$ among coprime arguments.
• Construction track (doable partially): Produce explicit infinite families of coprime pairs $(a,b)$ with $\sigma(a)=\sigma(b)$ (even if the count is far from $x^{2-o(1)}$), and compute small $x$ to sanity-check.

WORK

FAST REALITY CHECK (exact computation for small $x$).

I computed $h(x)$ exactly for $x\in\{20,50,100,200,300,500,1000\}$ by brute force. The results were: \[ h(20)=3,\; h(50)=13,\; h(100)=37,\; h(200)=82,\; h(300)=149,\; h(500)=285,\; h(1000)=716. \] Sample coprime pairs with equal $\sigma$ under $x=20$ are $(6,11)$ with $\sigma=12$, $(10,17)$ with $\sigma=18$, and $(14,15)$ with $\sigma=24$.

Lemma ($\sigma$ is multiplicative on coprime inputs). If $\gcd(m,n)=1$, then $\sigma(mn)=\sigma(m)\sigma(n)$.

Proof. Every divisor $d$ of $mn$ can be written uniquely as $d=ab$ with $a\mid m$ and $b\mid n$ because $\gcd(m,n)=1$ (uniqueness follows from unique factorization and disjoint prime supports). Therefore \[ \sigma(mn)=\sum_{d\mid mn} d = \sum_{a\mid m}\sum_{b\mid n} ab = \left(\sum_{a\mid m} a\right)\left(\sum_{b\mid n} b\right)=\sigma(m)\sigma(n). \] $\square$

Lemma (Squarefree formula). If $n$ is squarefree with prime factorization $n=\prod_{i=1}^r p_i$, then \[ \sigma(n)=\prod_{i=1}^r (p_i+1). \]

Proof. For a prime $p$, the divisors of $p$ are $1,p$, hence $\sigma(p)=1+p=p+1$. If $n$ is squarefree, the prime factors $p_i$ are distinct, hence pairwise coprime. By repeated application of the multiplicativity of $\sigma$ on coprime inputs, \[ \sigma\left(\prod_{i=1}^r p_i\right)=\prod_{i=1}^r \sigma(p_i)=\prod_{i=1}^r (p_i+1). \] $\square$

Lemma (A parametric collision producing coprime pairs). Let $p,q$ be primes and set $a:=pq$. If $r:=(p+1)(q+1)-1$ is also prime and $r\notin\{p,q\}$, then with $b:=r$ we have \[ \gcd(a,b)=1\quad\text{and}\quad \sigma(a)=\sigma(b)=(p+1)(q+1). \]

Proof. Since $p,q$ are primes and $a=pq$ is squarefree, the squarefree formula gives \[ \sigma(a)=(p+1)(q+1). \] Since $b=r$ is prime, $\sigma(b)=1+r=(p+1)(q+1)$ by definition of $r$.

For the gcd, because $b$ is prime it suffices to show $b\nmid a$. If $b=p$ then $p=(p+1)(q+1)-1$, which rearranges to $(p+1)(q+1)=p+1$, forcing $q=0$, impossible. Similarly $b\ne q$. Thus $b$ is a prime distinct from $p$ and $q$, so $\gcd(a,b)=1$. $\square$

Explicit instances of the parametric collision lemma.

• $p=2,q=3$: then $r=(3\cdot 4)-1=11$ is prime, and $(a,b)=(6,11)$ gives $\sigma(6)=\sigma(11)=12$.
• $p=2,q=5$: then $r=(3\cdot 6)-1=17$ is prime, and $(a,b)=(10,17)$ gives $\sigma(10)=\sigma(17)=18$.
• $p=3,q=5$: then $r=(4\cdot 6)-1=23$ is prime, and $(a,b)=(15,23)$ gives $\sigma(15)=\sigma(23)=24$.

These examples also appear among the small-$x$ computation above.

VERIFICATION

• Lemma ($\sigma$ is multiplicative on coprime inputs): the bijection between divisors of $mn$ and pairs of divisors of $m$ and $n$ uses $\gcd(m,n)=1$ essentially; without it, multiplicativity fails.
• Lemma (A parametric collision producing coprime pairs): the condition $r\notin\{p,q\}$ was used to guarantee $\gcd(pq,r)=1$. The proof shows this condition is automatic once $r$ is defined as $(p+1)(q+1)-1$ and $q\ge 2$; I kept it explicit to avoid missing edge cases.
• Computation: brute force verified the stated $h(x)$ values for the listed $x$.

FINAL

UNRESOLVED.

1. (i) Strongest proved partial result. I exhibited an explicit infinite family of conditional collisions (the parametric collision lemma): whenever primes $p,q$ make $r=(p+1)(q+1)-1$ prime, we get a coprime pair $(pq,r)$ with equal $\sigma$. Unconditionally, the small-$x$ computations confirm many such pairs exist at least for modest ranges.
2. (ii) First gap. Produce an unconditional lower bound of the form $h(x)\ge x^{1+\delta}$ for some fixed $\delta>0$ using only elementary constructions, let alone the conjectured $x^{2-o(1)}$.
3. (iii) Top 3 next moves.
   1. Develop systematic collision constructions using squarefree numbers: find many disjoint prime sets $A,B$ with $\prod_{p\in A}(p+1)=\prod_{q\in B}(q+1)$ and control the sizes of $\prod_{p\in A}p$ and $\prod_{q\in B}q$ to be $<x$.
   2. Compute $h(x)$ for larger $x$ (e.g. $10^5$) and classify the dominant collision mechanisms (prime vs semiprime vs higher squarefree) to guess the right asymptotic.
   3. Try to adapt additive-combinatorial ideas to the multiset $\{\log(p+1): p\le x\text{ prime}\}$ to force many multiplicative coincidences among products $\prod(p+1)$.
4. (iv) Minimal counterexample structure (if $h(x)\not> x^{2-o(1)}$). One would need an infinite sequence $x_j\to\infty$ such that for some fixed $\eta>0$, $h(x_j)\le x_j^{2-\eta}$. Such a failure would require that $\sigma$ is "almost injective" on coprime pairs below $x_j$; in particular, it would force strong restrictions on how often products $\prod(p+1)$ can coincide across disjoint prime sets.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT

Let $\sigma(n)=\sum_{d\mid n} d$ be the sum-of-divisors function. For $x>0$, define $h(x)$ to be the number of pairs of integers $(a,b)$ such that \[ 1\le a<b<x,\qquad \gcd(a,b)=1,\qquad \sigma(a)=\sigma(b). \] The question is:

Conjecture. Is it true that \[ h(x) > x^{2-o(1)}\qquad (x\to\infty)? \] Equivalently: is $\log h(x) / \log x \to 2$?

QUICK LITERATURE/CONTEXT CHECK

From the problem statement: Erdős proved $\limsup h(x)/x=\infty$ and claimed a similar proof for the stronger question; Pollack--Pomerance later gave a complete proof that $h(x)/x\to\infty$. The conjecture $h(x)>x^{2-o(1)}$ is substantially stronger.

I do not invoke any external results beyond those explicitly mentioned above.

ATTACK PLAN

• Proof track (ambitious): Try to build $\gg x^{2-o(1)}$ coprime pairs with equal $\sigma$ by constructing many collisions of the multiplicative function $\sigma$ among coprime arguments.
• Construction track (doable partially): Produce explicit infinite families of coprime pairs $(a,b)$ with $\sigma(a)=\sigma(b)$ (even if the count is far from $x^{2-o(1)}$), and compute small $x$ to sanity-check.

WORK

FAST REALITY CHECK (exact computation for small $x$).

I computed $h(x)$ exactly for $x\in\{20,50,100,200,300,500,1000\}$ by brute force. The results were: \[ h(20)=3,\; h(50)=13,\; h(100)=37,\; h(200)=82,\; h(300)=149,\; h(500)=285,\; h(1000)=716. \] Sample coprime pairs with equal $\sigma$ under $x=20$ are $(6,11)$ with $\sigma=12$, $(10,17)$ with $\sigma=18$, and $(14,15)$ with $\sigma=24$.

Lemma ($\sigma$ is multiplicative on coprime inputs). If $\gcd(m,n)=1$, then $\sigma(mn)=\sigma(m)\sigma(n)$.

Proof. Every divisor $d$ of $mn$ can be written uniquely as $d=ab$ with $a\mid m$ and $b\mid n$ because $\gcd(m,n)=1$ (uniqueness follows from unique factorization and disjoint prime supports). Therefore \[ \sigma(mn)=\sum_{d\mid mn} d = \sum_{a\mid m}\sum_{b\mid n} ab = \left(\sum_{a\mid m} a\right)\left(\sum_{b\mid n} b\right)=\sigma(m)\sigma(n). \] $\square$

Lemma (Squarefree formula). If $n$ is squarefree with prime factorization $n=\prod_{i=1}^r p_i$, then \[ \sigma(n)=\prod_{i=1}^r (p_i+1). \]

Proof. For a prime $p$, the divisors of $p$ are $1,p$, hence $\sigma(p)=1+p=p+1$. If $n$ is squarefree, the prime factors $p_i$ are distinct, hence pairwise coprime. By repeated application of the multiplicativity of $\sigma$ on coprime inputs, \[ \sigma\left(\prod_{i=1}^r p_i\right)=\prod_{i=1}^r \sigma(p_i)=\prod_{i=1}^r (p_i+1). \] $\square$

Lemma (A parametric collision producing coprime pairs). Let $p,q$ be primes and set $a:=pq$. If $r:=(p+1)(q+1)-1$ is also prime and $r\notin\{p,q\}$, then with $b:=r$ we have \[ \gcd(a,b)=1\quad\text{and}\quad \sigma(a)=\sigma(b)=(p+1)(q+1). \]

Proof. Since $p,q$ are primes and $a=pq$ is squarefree, the squarefree formula gives \[ \sigma(a)=(p+1)(q+1). \] Since $b=r$ is prime, $\sigma(b)=1+r=(p+1)(q+1)$ by definition of $r$.

For the gcd, because $b$ is prime it suffices to show $b\nmid a$. If $b=p$ then $p=(p+1)(q+1)-1$, which rearranges to $(p+1)(q+1)=p+1$, forcing $q=0$, impossible. Similarly $b\ne q$. Thus $b$ is a prime distinct from $p$ and $q$, so $\gcd(a,b)=1$. $\square$

Explicit instances of the parametric collision lemma.

• $p=2,q=3$: then $r=(3\cdot 4)-1=11$ is prime, and $(a,b)=(6,11)$ gives $\sigma(6)=\sigma(11)=12$.
• $p=2,q=5$: then $r=(3\cdot 6)-1=17$ is prime, and $(a,b)=(10,17)$ gives $\sigma(10)=\sigma(17)=18$.
• $p=3,q=5$: then $r=(4\cdot 6)-1=23$ is prime, and $(a,b)=(15,23)$ gives $\sigma(15)=\sigma(23)=24$.

These examples also appear among the small-$x$ computation above.

VERIFICATION

• Lemma ($\sigma$ is multiplicative on coprime inputs): the bijection between divisors of $mn$ and pairs of divisors of $m$ and $n$ uses $\gcd(m,n)=1$ essentially; without it, multiplicativity fails.
• Lemma (A parametric collision producing coprime pairs): the condition $r\notin\{p,q\}$ was used to guarantee $\gcd(pq,r)=1$. The proof shows this condition is automatic once $r$ is defined as $(p+1)(q+1)-1$ and $q\ge 2$; I kept it explicit to avoid missing edge cases.
• Computation: brute force verified the stated $h(x)$ values for the listed $x$.

FINAL

UNRESOLVED.

1. (i) Strongest proved partial result. I exhibited an explicit infinite family of conditional collisions (the parametric collision lemma): whenever primes $p,q$ make $r=(p+1)(q+1)-1$ prime, we get a coprime pair $(pq,r)$ with equal $\sigma$. Unconditionally, the small-$x$ computations confirm many such pairs exist at least for modest ranges.
2. (ii) First gap. Produce an unconditional lower bound of the form $h(x)\ge x^{1+\delta}$ for some fixed $\delta>0$ using only elementary constructions, let alone the conjectured $x^{2-o(1)}$.
3. (iii) Top 3 next moves.
   1. Develop systematic collision constructions using squarefree numbers: find many disjoint prime sets $A,B$ with $\prod_{p\in A}(p+1)=\prod_{q\in B}(q+1)$ and control the sizes of $\prod_{p\in A}p$ and $\prod_{q\in B}q$ to be $<x$.
   2. Compute $h(x)$ for larger $x$ (e.g. $10^5$) and classify the dominant collision mechanisms (prime vs semiprime vs higher squarefree) to guess the right asymptotic.
   3. Try to adapt additive-combinatorial ideas to the multiset $\{\log(p+1): p\le x\text{ prime}\}$ to force many multiplicative coincidences among products $\prod(p+1)$.
4. (iv) Minimal counterexample structure (if $h(x)\not> x^{2-o(1)}$). One would need an infinite sequence $x_j\to\infty$ such that for some fixed $\eta>0$, $h(x_j)\le x_j^{2-\eta}$. Such a failure would require that $\sigma$ is "almost injective" on coprime pairs below $x_j$; in particular, it would force strong restrictions on how often products $\prod(p+1)$ can coincide across disjoint prime sets.