Erdős Problem #955

Erdős Problem 955 --- collection record

PROVENANCE AND STATUS

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/955.tex.

REUSED SOURCE 1

Erdos Problem 955.

1) FORMAL RESTATEMENT. For $n\in\mathbb{N}$ define \[ s(n):=\sigma(n)-n=\sum_{\substack{d\mid n\\ d<n}} d, \] the sum of the proper divisors of $n$. For a set $A\subseteq\mathbb{N}$, write $A$ has (natural) density $0$ if \[ \lim_{x\to\infty} \frac{|A\cap [1,x]|}{x}=0. \] The conjecture asks:

If $A\subseteq\mathbb{N}$ has density $0$, must the preimage $s^{-1}(A):=\{n\in\mathbb{N}: s(n)\in A\}$ also have density $0$?

2) QUICK LITERATURE/CONTEXT CHECK. The problem file attributes this conjecture to Erdős, Granville, Pomerance and Spiro. It records several partial results (e.g. for very sparse $A$, and results depending on bounds for $s(n)$) and notes that there exist sets $A$ of positive density with $s^{-1}(A)=\varnothing$.

3) ATTACK PLAN. (A) Prove robust inequalities relating $s(n)$ to elementary parameters of $n$ (size, smallest prime factor, divisor count). (B) Use these inequalities to control $\{n\le x: s(n)\in A\}$ for special classes of sparse sets $A$. (C) Run a sieve for small $x$ to see how often $s(n)$ hits various zero-density targets (squares, primes, etc.).

4) WORK.

FAST REALITY CHECK (computations for small targets). Using a divisor-sum sieve up to $200000$, I computed the proportions \[\#\{n\le X: s(n)\text{ is a square}\}/X\quad\text{and}\quad \#\{n\le X: s(n)\text{ is prime}\}/X.\] The results were: \[ \begin{array}{c|c|c||c|c} X & \#\{s(n)\text{ square}\} & \text{ratio} & \#\{s(n)\text{ prime}\} & \text{ratio}\\\hline 10^2 & 36 & 0.36 & 15 & 0.15\\ 10^3 & 216 & 0.216 & 125 & 0.125\\ 10^4 & 1422 & 0.1422 & 1045 & 0.1045\\ 5\cdot 10^4 & 5593 & 0.11186 & 4655 & 0.0931\\ 10^5 & 10312 & 0.10312 & 8801 & 0.08801\\ 2\cdot 10^5 & 19070 & 0.09535 & 16734 & 0.08367 \end{array} \] These ratios decrease over this range, consistent with (but not proving) density $0$ for these particular choices of $A$.

Lemma 955.1 (A universal lower bound for composite $n$). If $n$ is composite, then \[ s(n)\ge 1+2\sqrt{n}. \]

Proof. Since $n$ is composite, choose a divisor $d$ with $1<d\le \sqrt{n}$. Then $d$ and $n/d$ are both proper divisors of $n$ (because $d>1$ and $n/d<n$). Therefore \[ s(n)\ge 1 + d + \frac{n}{d}. \] By AM--GM, $d + n/d \ge 2\sqrt{n}$, so $s(n)\ge 1+2\sqrt{n}$. $\square$

Lemma 955.2 (Lower bound using the smallest prime factor). Let $n\ge 2$ and let $p$ be the smallest prime divisor of $n$. Then \[ s(n)\ge \frac{n}{p}+1. \]

Proof. The integer $n/p$ is a proper divisor of $n$ because $p\ge 2$. Also $1$ is a proper divisor of $n$. Since $s(n)$ is the sum of all proper divisors, it is at least the sum of these two: $s(n)\ge 1+n/p$. $\square$

Lemma 955.3 (Crude universal upper bound in terms of the divisor function). Let $\tau(n):=\#\{d:d\mid n\}$ be the number of positive divisors of $n$. Then \[ s(n)\le (\tau(n)-1)\,n. \]

Proof. There are exactly $\tau(n)-1$ proper divisors of $n$. Each proper divisor $d$ satisfies $d\le n$. Summing the $\tau(n)-1$ terms gives $s(n)\le (\tau(n)-1)n$. $\square$

5) VERIFICATION. • Lemma 955.1: the choice of $d\le \sqrt{n}$ is standard and always possible for composite $n$. • Lemma 955.2: uses only two explicit proper divisors. • Lemma 955.3: very weak but unconditional. • Computations: the sieve method computed $s(n)$ exactly by adding each divisor $d$ to multiples $2d,3d,\dots$.

6) FINAL. UNRESOLVED. (i) Strongest proved partial result: For composite $n$, $s(n)\ge 1+2\sqrt{n}$ and $s(n)\ge 1+n/p$ where $p$ is the least prime factor of $n$; also $s(n)\le (\tau(n)-1)n$. (ii) First gap: turn these pointwise inequalities into a density statement for arbitrary zero-density sets $A$, i.e. show $\#\{n\le x: s(n)\in A\}=o(x)$ from the hypothesis $|A\cap[1,y]|=o(y)$. (iii) Top 3 next moves: $1$ Prove that for most $n\le x$, the value $s(n)$ lies in an interval $[c_1 n, c_2 n\log\log n]$ with a distribution that is sufficiently “mixing” to prevent concentration on a zero-density set. $2$ For a given sparse $A$, try to bound solutions of $s(n)=a$ with $a\in A$ by structural restrictions on $n$ (e.g. on its prime factorization), then sum over $a\le y$. $3$ Run targeted computations for adversarial-looking zero-density sets (e.g. squares, powers, very thin unions of intervals) to guess what the hardest $A$ might look like. (iv) Minimal counterexample structure: a zero-density $A$ and a positive-density set $B$ such that $s(B)\subseteq A$; equivalently, $s(n)$ would have to fall into a very sparse set for a positive proportion of integers $n$.

COMPLETION ESTIMATE

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

Erdos Problem 955.

1) FORMAL RESTATEMENT. For $n\in\mathbb{N}$ define \[ s(n):=\sigma(n)-n=\sum_{\substack{d\mid n\\ d<n}} d, \] the sum of the proper divisors of $n$. For a set $A\subseteq\mathbb{N}$, write $A$ has (natural) density $0$ if \[ \lim_{x\to\infty} \frac{|A\cap [1,x]|}{x}=0. \] The conjecture asks:

If $A\subseteq\mathbb{N}$ has density $0$, must the preimage $s^{-1}(A):=\{n\in\mathbb{N}: s(n)\in A\}$ also have density $0$?

2) QUICK LITERATURE/CONTEXT CHECK. The problem file attributes this conjecture to Erdős, Granville, Pomerance and Spiro. It records several partial results (e.g. for very sparse $A$, and results depending on bounds for $s(n)$) and notes that there exist sets $A$ of positive density with $s^{-1}(A)=\varnothing$.

3) ATTACK PLAN. (A) Prove robust inequalities relating $s(n)$ to elementary parameters of $n$ (size, smallest prime factor, divisor count). (B) Use these inequalities to control $\{n\le x: s(n)\in A\}$ for special classes of sparse sets $A$. (C) Run a sieve for small $x$ to see how often $s(n)$ hits various zero-density targets (squares, primes, etc.).

4) WORK.

FAST REALITY CHECK (computations for small targets). Using a divisor-sum sieve up to $200000$, I computed the proportions \[\#\{n\le X: s(n)\text{ is a square}\}/X\quad\text{and}\quad \#\{n\le X: s(n)\text{ is prime}\}/X.\] The results were: \[ \begin{array}{c|c|c||c|c} X & \#\{s(n)\text{ square}\} & \text{ratio} & \#\{s(n)\text{ prime}\} & \text{ratio}\\\hline 10^2 & 36 & 0.36 & 15 & 0.15\\ 10^3 & 216 & 0.216 & 125 & 0.125\\ 10^4 & 1422 & 0.1422 & 1045 & 0.1045\\ 5\cdot 10^4 & 5593 & 0.11186 & 4655 & 0.0931\\ 10^5 & 10312 & 0.10312 & 8801 & 0.08801\\ 2\cdot 10^5 & 19070 & 0.09535 & 16734 & 0.08367 \end{array} \] These ratios decrease over this range, consistent with (but not proving) density $0$ for these particular choices of $A$.

Lemma 955.1 (A universal lower bound for composite $n$). If $n$ is composite, then \[ s(n)\ge 1+2\sqrt{n}. \]

Proof. Since $n$ is composite, choose a divisor $d$ with $1<d\le \sqrt{n}$. Then $d$ and $n/d$ are both proper divisors of $n$ (because $d>1$ and $n/d<n$). Therefore \[ s(n)\ge 1 + d + \frac{n}{d}. \] By AM--GM, $d + n/d \ge 2\sqrt{n}$, so $s(n)\ge 1+2\sqrt{n}$. $\square$

Lemma 955.2 (Lower bound using the smallest prime factor). Let $n\ge 2$ and let $p$ be the smallest prime divisor of $n$. Then \[ s(n)\ge \frac{n}{p}+1. \]

Proof. The integer $n/p$ is a proper divisor of $n$ because $p\ge 2$. Also $1$ is a proper divisor of $n$. Since $s(n)$ is the sum of all proper divisors, it is at least the sum of these two: $s(n)\ge 1+n/p$. $\square$

Lemma 955.3 (Crude universal upper bound in terms of the divisor function). Let $\tau(n):=\#\{d:d\mid n\}$ be the number of positive divisors of $n$. Then \[ s(n)\le (\tau(n)-1)\,n. \]

Proof. There are exactly $\tau(n)-1$ proper divisors of $n$. Each proper divisor $d$ satisfies $d\le n$. Summing the $\tau(n)-1$ terms gives $s(n)\le (\tau(n)-1)n$. $\square$

5) VERIFICATION. • Lemma 955.1: the choice of $d\le \sqrt{n}$ is standard and always possible for composite $n$. • Lemma 955.2: uses only two explicit proper divisors. • Lemma 955.3: very weak but unconditional. • Computations: the sieve method computed $s(n)$ exactly by adding each divisor $d$ to multiples $2d,3d,\dots$.

6) FINAL. UNRESOLVED. (i) Strongest proved partial result: For composite $n$, $s(n)\ge 1+2\sqrt{n}$ and $s(n)\ge 1+n/p$ where $p$ is the least prime factor of $n$; also $s(n)\le (\tau(n)-1)n$. (ii) First gap: turn these pointwise inequalities into a density statement for arbitrary zero-density sets $A$, i.e. show $\#\{n\le x: s(n)\in A\}=o(x)$ from the hypothesis $|A\cap[1,y]|=o(y)$. (iii) Top 3 next moves: $1$ Prove that for most $n\le x$, the value $s(n)$ lies in an interval $[c_1 n, c_2 n\log\log n]$ with a distribution that is sufficiently “mixing” to prevent concentration on a zero-density set. $2$ For a given sparse $A$, try to bound solutions of $s(n)=a$ with $a\in A$ by structural restrictions on $n$ (e.g. on its prime factorization), then sum over $a\le y$. $3$ Run targeted computations for adversarial-looking zero-density sets (e.g. squares, powers, very thin unions of intervals) to guess what the hardest $A$ might look like. (iv) Minimal counterexample structure: a zero-density $A$ and a positive-density set $B$ such that $s(B)\subseteq A$; equivalently, $s(n)$ would have to fall into a very sparse set for a positive proportion of integers $n$.