Erdős Problem #825

Erdős Problem 825: sufficiently abundant numbers are semiperfect

1. Statement and current resolution

Write $\sigma(n)=\sum_{d\mid n}d$ and $\ell(n)=\sigma(n)/n$. A positive integer is semiperfect if it is a sum of distinct proper divisors. The question asks whether some absolute $C$ makes $\ell(n)>C$ sufficient for semiperfectness. Larsen has answered yes. This attempt gives the full deduction from his stronger rough-number theorem, with the deep input explicitly delimited, and proves an independent elementary divisor-packing criterion.

2. External rough-number input

We use Larsen's Theorem 1: for every $\varepsilon>0$ there exists $L$ such that an integer $v$ with no prime factor less than $L$ and $\ell(v)>2+\varepsilon$ is semiperfect. The multi-scale selection and circle-method proof of this theorem is external here. This is stronger than the requested conclusion on a restricted class of integers; the removal of that restriction is the following complete argument. First, semiperfectness passes to every multiple. If $v=\sum_{d\in D}d$, where $D$ consists of distinct proper divisors of $v$, then \[ av=\sum_{d\in D}ad \] uses distinct proper divisors of $av$. Choose $L$ for $\varepsilon=1$, and put \[ M=\prod_{p<L}\left(1-\frac1p\right)^{-1},\qquad C=3M. \] This is a finite absolute constant. Factor any $n$ as $uv$, where $u$ contains exactly its prime-power factors with primes below $L$. Then $\gcd(u,v)=1$ and divisor factorization gives \[ \ell(n)=\ell(u)\ell(v),\qquad \ell(u)=\prod_{p^a\Vert u}\left(1+\frac1p+\cdots+\frac1{p^a}\right)\le M. \] Hence $\ell(n)>C$ implies $\ell(v)>3$. Larsen's theorem makes $v$ semiperfect, and scaling makes $n$ semiperfect. This proves the original existence assertion. Neither an explicit numerical value of $L$ nor the proposed sharp value $C=3$ follows from this deduction.

3. A proved elementary packing criterion

The following explains a substantial family in which the representation can be constructed without the external theorem. Suppose \[ n=\prod_{i=1}^t p_i^{a_i},\quad p_1<\cdots<p_t, \qquad p_i\le1+\sigma\left(\prod_{j<i}p_j^{a_j}\right)\quad(1\le i\le t). \tag{1} \] Then every integer between $0$ and $\sigma(n)$ is a sum of distinct divisors of $n$. To prove this, start with $n=1$, whose divisors represent $0,1$. Suppose the divisors of $m$ represent every integer in $[0,S]$, where $S=\sigma(m)$, and add a new prime power $p^a$ with $p\le S+1$. Divisors split into disjoint blocks $p^j\operatorname{Div}(m)$, $0\le j\le a$. Suppose the first $j$ blocks represent $[0,S(1+p+\cdots+p^{j-1})]$. By selecting independently in block $j$, they then represent every interval \[ [p^jb,\ p^jb+S(1+p+\cdots+p^{j-1})],\quad b=0,1,\ldots,S. \] Successive intervals touch or overlap because \[ S(1+p+\cdots+p^{j-1})\ge(p-1)(1+p+\cdots+p^{j-1})=p^j-1. \] Their union is the full required interval through $S(1+p+\cdots+p^j)$. This proves the induction and $1$. For completeness, if a sorted positive list $d_1<\cdots<d_s$ has all subset sums from $0$ to its total, then $d_1=1$ and \[ d_i\le1+\sum_{j<i}d_j. \tag{2} \] Otherwise the integer $1+\sum_{j<i}d_j$ is a gap. Conversely, $2$ implies interval coverage by the same overlap induction. Applied to the divisors of a number satisfying $1$, removing the largest divisor $n$ leaves a list still satisfying $2$. Therefore its proper divisors represent every integer through $\sigma(n)-n$. Whenever $\sigma(n)\ge2n$, they represent $n$ in particular. This supplies an exact constructive special case of the problem.

4. Why mere abundance is insufficient

For $n=70$, the proper divisors sum to $74$. If a subset summed to $70$, its complementary subset would sum to $4$. No subset of $\{1,2,5,7,10,14,35\}$ sums to $4$: the only entries at most $4$ are $1,2$, whose total is $3$. Thus $70$ is not semiperfect despite $\ell(70)=144/70>2$. In particular the existence proof cannot simply replace the rough-number input by the condition $\ell(n)>2$.

5. Sources and assessment

Sources: https://www.erdosproblems.com/825; D. Larsen, Sufficiently abundant numbers are pseudoperfect, Theorem 1, https://github.com/Larsen-Daniel/Erdos-825/blob/main/825.pdf. The older local GPT-5.2 attempt was also read; its elementary odd-weird-divisor observation does not supply the now-known unconditional theorem. SOLVED relative to Larsen's explicitly imported rough-number theorem. The reduction to arbitrary integers, the divisor-packing criterion and the obstruction at $70$ are fully proved. The completion estimate concerns this proof with its stated external dependency, not an independent reproduction of Larsen's analytic argument, a sharp constant, or a new discovery. Completion rate estimate: 100%.

FORMAL RESTATEMENT

Write $\sigma(n)=\sum_{d\mid n} d$ and call an integer $n$ semiperfect if $n$ is a sum of distinct proper divisors of $n$ (i.e. a sum of a subset of $\{d: d\mid n,\ d<n\}$). Call $n$ weird if $\sigma(n)>2n$ (abundant) but $n$ is not semiperfect.

The question is:

Problem. Does there exist an absolute constant $C>0$ such that every integer $n$ with $\sigma(n)>Cn$ is semiperfect?

Equivalently: is there an absolute upper bound on the abundancy index \[ \ell(n):=\frac{\sigma(n)}{n} \] among all weird numbers?

QUICK LITERATURE/CONTEXT CHECK

From the problem statement: it is suggested the statement might hold with $C=3$; necessarily $C>2$ since $\sigma(70)=144$ but $70$ is not semiperfect. The statement also records an observation attributed to Weisenberg: if a weird number has abundancy index $\ge 4$, then it is divisible by an odd weird number; thus if there are no odd weird numbers then every weird number has abundancy index $<4$.

I only use the definitions and the elementary multiplicativity facts that I prove below.

ATTACK PLAN

• Proof track: Try to show that very abundant numbers must be semiperfect by a subset-sum covering argument using many small divisors (a knapsack/greedy density idea). This seems hard without deep structure theorems.
• Disproof track: Try to build weird numbers with arbitrarily large abundancy index, e.g. by multiplicative constructions that keep non-semiperfectness while increasing $\sigma(n)/n$. This also seems hard; known weird numbers in computations have abundancy only slightly above $2$.
• What I will do here: Prove two problem-specific lemmas (multiplicativity of abundancy and the "odd weird divisor" implication), and run an exact small search for weird numbers up to $10^5$ to sanity-check abundancy sizes.

WORK

FAST REALITY CHECK (exact search for small weird numbers).

I searched exactly for weird numbers $n\le 100{,}000$ by checking abundance ($\sigma(n)>2n$) and semiperfectness (subset-sum over proper divisors via a bitset DP).

• There are $204$ weird numbers $\le 100{,}000$.
• The first few are $70, 836, 4030, 5830, 7192, 7912, \dots$.
• The maximum abundancy index among weird $n\le 100{,}000$ is attained at $n=10430$ and equals \[\ell(10430)=\frac{\sigma(10430)}{10430}=\frac{2160}{1043}\approx 2.070949\dots\,. \]

In particular, in this range there are no weird numbers with abundancy index anywhere near $3$ or $4$.

Lemma (Abundancy index is multiplicative on coprime inputs). If $\gcd(a,b)=1$, then \[ \ell(ab)=\ell(a)\ell(b). \]

Proof. By the lemma from Problem #824 that $\sigma$ is multiplicative on coprime inputs, $\sigma(ab)=\sigma(a)\sigma(b)$ when $\gcd(a,b)=1$. Divide both sides by $ab$: \[ \ell(ab)=\frac{\sigma(ab)}{ab}=\frac{\sigma(a)}{a}\cdot \frac{\sigma(b)}{b}=\ell(a)\ell(b). \] $\square$

Lemma (Explicit abundancy for powers of $2$). For every integer $k\ge 0$, \[ \ell(2^k)=\frac{\sigma(2^k)}{2^k}=2-2^{-k} < 2. \]

Proof. The divisors of $2^k$ are $1,2,2^2,\dots,2^k$, so \[ \sigma(2^k)=1+2+2^2+\cdots+2^k = 2^{k+1}-1. \] Therefore \[ \ell(2^k)=\frac{2^{k+1}-1}{2^k}=2-2^{-k}, \] which is strictly less than $2$. $\square$

Lemma (Odd weird divisor if $\ell(n)\ge 4$). Let $n$ be weird and write $n=2^k m$ with $m$ odd. If $\ell(n)\ge 4$, then $m$ is an odd weird number. In particular, if no odd weird numbers exist, then every weird number satisfies $\ell(n)<4$.

Proof. Assume $n$ is weird and $n=2^k m$ with $m$ odd.

First, $\gcd(2^k,m)=1$, so the multiplicativity of $\ell$ on coprime inputs gives \[ \ell(n)=\ell(2^k)\ell(m). \] By the explicit formula for $\ell(2^k)$, $\ell(2^k)<2$. If $\ell(n)\ge 4$, then \[ \ell(m)=\frac{\ell(n)}{\ell(2^k)} > \frac{4}{2}=2, \] so $\sigma(m)>2m$ and $m$ is abundant.

It remains to show that $m$ is not semiperfect. Suppose, for contradiction, that $m$ is semiperfect. Then there exist distinct proper divisors $d_1,\dots,d_t$ of $m$ such that \[ m=d_1+\cdots+d_t. \] Multiplying by $2^k$ gives \[ 2^k m = 2^k d_1+\cdots+2^k d_t. \] Each $2^k d_i$ is a divisor of $n=2^k m$, and it is proper because $d_i<m$ implies $2^k d_i < 2^k m=n$. The terms are distinct because the $d_i$ are distinct. Hence this expresses $n$ as a sum of distinct proper divisors of $n$, i.e. shows $n$ is semiperfect.

This contradicts that $n$ is weird. Therefore $m$ is not semiperfect. Since we already proved $m$ is abundant, $m$ is weird. Finally, $m$ is odd by construction.

The last sentence follows immediately: if no odd weird numbers exist, then the conclusion "if $\ell(n)\ge 4$ then $m$ is an odd weird number" forces that no weird $n$ can have $\ell(n)\ge 4$. $\square$

VERIFICATION

• Lemma (Odd weird divisor if $\ell(n)\ge 4$) uses only (a) multiplicativity of $\ell$ on coprime parts, (b) the exact inequality $\ell(2^k)<2$, and (c) the fact that semiperfectness of the odd part would imply semiperfectness of $2^k$ times the odd part by scaling the subset-sum.
• The semiperfect scaling step: if $m=\sum d_i$ with $d_i\mid m$ and $d_i<m$, then $2^k d_i \mid 2^k m$ and $2^k d_i <2^k m$; no hidden assumption is used.
• Computation: the DP bitset check is exact (no floating tolerance). The reported maximum $\ell(10430)=2160/1043$ was obtained by exact integer arithmetic ($\sigma(10430)=21600$).

FINAL

UNRESOLVED.

1. (i) Strongest proved partial result. If a weird number $n$ satisfies $\ell(n)\ge 4$, then its odd part is an odd weird number (by the odd-weird-divisor lemma). Hence, assuming there are no odd weird numbers, every weird number has $\ell(n)<4$.
2. (ii) First gap. Either construct a sequence of weird numbers with $\ell(n)\to\infty$ (to disprove existence of a universal $C$), or prove an absolute upper bound on $\ell(n)$ for weird numbers (which would imply a positive answer).
3. (iii) Top 3 next moves.
   1. Attempt to prove that for sufficiently large abundancy index, the set of proper divisors below (say) $\varepsilon n$ has total sum $>n$ and has enough granularity to realize $n$ via a subset-sum (a quantitative semiperfectness criterion).
   2. Search computationally for weird numbers with unusually large abundancy index, focusing on numbers with many small prime factors but constrained subset-sum structure, and record the current computational maximum of $\ell(n)$.
   3. Prove structural closure properties: e.g. characterize when multiplying a weird number by a prime power preserves weirdness and increases $\ell$; any such closure could generate large-index examples.
4. (iv) Minimal counterexample structure (if the statement were false). One would need a sequence of weird numbers $n_j$ with $\ell(n_j)\to\infty$. By the odd-weird-divisor lemma, unless odd weird numbers exist, such a sequence would be impossible once $\ell(n_j)\ge 4$; therefore any counterexample to a universal $C$ likely forces existence of odd weird numbers and then an infinite mechanism to boost $\ell$.