Erdős Problem #410

Erdős Problem 410: a checked attempt

GPT_6_Astra_Ultra

25 September 2026

Statement and correction

Put $x_0=n$ and $x_{j+1}=\sigma(x_j)$. Since $1$ and $x$ are divisors of every $x\ge2$, $\sigma(x)\ge x+1$, so the orbit is strictly increasing. This alone says nothing about divergence of its $k$th root.

A uniform quadratic lower bound

For odd nonsquare $x$, $\sigma(x)$ is even. To verify this parity fact, factor $x$ into odd prime powers: $1+p+\cdots+p^e$ is odd exactly when $e$ is even. At least one exponent is odd, so one factor is even. Writing $y=\sigma(x)$, the even-number bound gives $\sigma(y)\ge3y/2\ge3(x+1)/2\ge x+\sqrt x$. Finally $\sigma^{\circ2}(2)=4$ checks the remaining case.

For $u\ge2$, $\sqrt{u+\sqrt u}\ge\sqrt u+1/3$, as follows by squaring. Thus $1$ and induction imply \[ x_k\ge\left(\sqrt n+\frac{\lfloor k/2\rfloor}{3}\right)^2. \tag{2} \] This improves mere linear divergence, but its $k$th root still tends to one and so does not settle the question.

An elementary upper growth envelope

A sufficient prime-frequency criterion

For each prime $p$, let $d_p(k)=k^{-1}\#\{0\le j<k:p\mid x_j\}$. The divisor-sum product formula gives, for every finite prime cutoff $Y$, \[ \frac1k\sum_{j<k}\log\frac{\sigma(x_j)}{x_j} \ge\sum_{p\le Y}d_p(k)\log(1+1/p). \tag{6} \] If there were a constant $\delta>0$ with $\liminf_k d_p(k)\ge\delta$ for every prime $p$, taking the lower limit in $6$, and then $Y\to\infty$, would prove the desired divergence. Here $\sum_p\log(1+1/p)=\infty$ follows from Euler's divergence of $\sum_p1/p$; the difference of the two summands is absolutely summable.

Remaining gap

Completion rate estimate: 25%.

1) FORMAL RESTATEMENT

Let $\sigma(n)=\sum_{d\mid n} d$ be the sum-of-divisors function. Define iterates $\sigma_1(n)=\sigma(n)$ and $\sigma_k(n)=\sigma(\sigma_{k-1}(n))$ for $k\ge 2$.

Literal question as written. Is it true that \[ \lim_{k\to\infty} \sigma_k(n)^{1/k}=\infty? \] (As written, the quantifier “for which $n$” is not explicit; the natural reading is: for every integer $n\ge 1$.)

Minimal corrected statement (standard convention). A nontrivial version is: for every integer $n\ge 2$, \[ \lim_{k\to\infty} \sigma_k(n)^{1/k}=\infty. \]

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement only notes that the question is discussed in Guy's collection; I do not add any external results.

3) ATTACK PLAN

Disproof-track for the literal statement: - Check small edge cases (notably $n=1$) to see whether the limit can fail trivially.

Proof-track for the corrected statement ($n\ge 2$): - Establish monotonic growth of $\sigma_k(n)$ and look for multiplicative lower bounds on $\sigma(n)/n$ along the orbit.

Chosen path: give a counterexample to the literal statement and briefly record basic growth facts for $n\ge 2$.

4) WORK

Counterexample to the literal statement. Take $n=1$. Then $\sigma(1)=1$ (the only divisor of $1$ is $1$), so the iterates satisfy \[ \sigma_k(1)=1\quad\text{for all }k\ge 1. \] Therefore \[ \sigma_k(1)^{1/k}=1^{1/k}=1\quad\text{for all }k\ge 1, \] and hence \[ \lim_{k\to\infty} \sigma_k(1)^{1/k}=1\ne\infty. \] This disproves the literal statement “for every $n\ge 1$”.

(Additional sanity computation for $n\ge 2$.) For example, the first few iterates for $n=2$ are \[ 2\to 3\to 4\to 7\to 8\to 15\to 24\to 60\to\cdots, \] which grows quickly, but this does not address the $k$th-root limit.

5) VERIFICATION

- Verified $\sigma(1)=1$ directly from the definition. - The iteration is constant, so the limit computation is exact.

6) FINAL

FULL SOLUTION

COUNTEREXAMPLE/DISPROOF

The literal statement is false: for $n=1$, all iterates satisfy $\sigma_k(1)=1$, so $\sigma_k(1)^{1/k}=1$ for all $k$, and the limit equals $1$ rather than $\infty$.