Erdős Problem #412

Erdős Problem 412: a checked attempt

GPT_6_Astra_Ultra

25 September 2026

Statement and scope

Must the forward orbits of every two integers $m,n\ge2$ under $\sigma$, the sum-of-divisors function, eventually meet? Source: https://www.erdosproblems.com/412. The question remains unresolved here. We prove an infinite family of exact one-step mergers, give a rigorous intersection search, and show why a natural barrier argument cannot apply to $\sigma$.

This retains the valid elementary dynamics in the earlier GPT-5.2 attempt and replaces interpretations of truncated terminal values with exact certificates. No novelty or general merging assertion is claimed.

Order and exact merger certificates

For $x\ge2$, $\sigma(x)\ge x+1$, since both $1,x$ are divisors. Thus every orbit is strictly increasing and unbounded. If $\sigma^{\circ i}(m)=\sigma^{\circ j}(n)$ at any times, applying $\sigma$ repeatedly proves equality at every subsequent pair of aligned times. Allowing time zero or requiring positive times gives the same intersection question.

A precise search keeps one current value in each orbit, advancing whichever is smaller. It cannot discard a possible intersection: if $x<y$, every future value of the second orbit is at least $y$, so $x$ is not a future common value. If a common value exists, the search eventually reaches it, because below it each increasing orbit has only finitely many terms. Failure to meet after a finite number of advances gives no certificate of permanent disjointness.

An infinite family of one-step mergers

The elementary equalities \[ \sigma(14)=1+2+7+14=24=1+3+5+15=\sigma(15) \] propagate multiplicatively. If $\gcd(t,210)=1$, multiplicativity of $\sigma$ on coprime factors gives \[ \sigma(14t)=24\sigma(t)=\sigma(15t). \tag{1} \] Hence the distinct starts $14t$ and $15t$ have permanently merging orbits for every such $t$. There are infinitely many choices, for example $t=210j+1$. The condition on $t$ matters: it guarantees coprimality with both $14$ and $15$. Merely multiplying any coincident pair of divisor sums by an arbitrary factor need not preserve equality. Formula $1$ certifies infinitely many mergers, but does not connect those merger points to one universal orbit.

A barrier method and its obstruction

For a strictly increasing-in-time map $T$ on positive integers with $T(x)>x$, call $B$ a barrier if $T(x)\le B$ for every integer $2\le x<B$. Every orbit starting below $B$ must hit $B$: it cannot stay below forever, and the step first reaching or passing $B$ cannot jump over it. Thus arbitrarily large barriers would force all pairs of orbits to meet.

For $T=\sigma$, there is no barrier $B\ge7$. Choose the even number $x=B-1$ if $B$ is odd and $x=B-2$ otherwise. Then $2\le x<B$, while \[ \sigma(x)\ge1+\frac{3x}{2}\ge1+\frac{3(B-2)}2>B \] for $B\ge7$. Hence the sufficient barrier route is unavailable. This is a limitation of that route, not a disproof of universal orbit intersection.

Parity and growth cannot be assumed to separate tails

The product formula shows that $\sigma(x)$ is odd exactly when $x$ is a square or twice a square: every odd-prime exponent must be even, and the power of two contributes an odd divisor sum. In particular parity itself is not an invariant, as $3\mapsto4$ and $8\mapsto15$ demonstrate.

If two orbits merge with an index shift, they have the same lower and upper limits of $\log(\sigma^{\circ k}(n))/k$, including the value $+\infty$. Indeed after deleting finite prefixes the numerators coincide at indices differing by a fixed integer, and the two denominators have ratio tending to one; the numerators are nonnegative. Thus universal merging would make the root-growth question of Problem 410 independent of the starting value. Equal growth rates would still not imply actual intersection.

Remaining gap

We have exact mergers in $1$ and a terminating search whenever a merger exists. No invariant is proved that separates a pair forever, and no argument forces every orbit to enter the same component. Different values at the end of truncated computations may simply be different positions on a common orbit, so they are not counted as different permanent tails.

Completion rate estimate: 30%.

FORMAL RESTATEMENT

Let $\sigma(n)=\sum_{d\mid n} d$ be the sum-of-divisors function. Define iterates by \[ \sigma_1(n)=\sigma(n),\qquad \sigma_{k+1}(n)=\sigma(\sigma_k(n))\ (k\ge 1). \] Question: Is it true that for every pair of integers $m,n\ge2$ there exist indices $i,j\ge1$ such that \[ \sigma_i(m)=\sigma_j(n)? \] Equivalently, do all forward orbits under $\sigma$ eventually intersect (and hence coincide thereafter)?

QUICK LITERATURE/CONTEXT CHECK

The problem file attributes the conjecture to van Wijngaarden (via Erdős). It reports that Selfridge had numerical evidence suggesting the answer is "no", and that Erdős and Graham considered the problem out of reach. No additional external results are used here.

ATTACK PLAN

Key structural facts:

• For $n>1$, $\sigma(n)\ge n+1$, so every orbit is strictly increasing and diverges.
• If two orbits ever meet at a value $x$, they are identical from that point on.
• Try to find an invariant (parity, $2$-adic valuation, square/twice-square structure, etc.) that could prevent intersections.
• Run small computations to see how many distinct "tails" remain after a bounded number of iterates.

WORK

Lemma 412.1 (Strict increase of $\sigma$-iterates). For every integer $n\ge2$, we have $\sigma(n)\ge n+1$. Consequently, for every $k\ge1$ the sequence $\sigma_k(n)$ is strictly increasing, hence has no cycles.

Proof. For $n\ge2$, both $1$ and $n$ are positive divisors of $n$, so $$\sigma(n)=\sum_{d\mid n} d \ge 1+n=n+1.$$ Thus $\sigma(n)>n$ for $n\ge2$. Applying this inductively to $\sigma_k(n)$ yields $\sigma_{k+1}(n)=\sigma(\sigma_k(n))>\sigma_k(n)$ for all $k\ge1$. $\square$

Lemma 412.2 (Parity characterization). For $n\ge1$, $\sigma(n)$ is odd if and only if $n$ is a perfect square or twice a perfect square.

Proof. Write the prime factorization $n=\prod_p p^{e_p}$. The divisor-sum function is multiplicative, so $$\sigma(n)=\prod_p \sigma(p^{e_p}),\qquad \sigma(p^{e})=1+p+p^2+\cdots+p^e.$$ For an odd prime $p$, each term $p^t$ is odd, hence $\sigma(p^e)$ is odd if and only if it has an odd number of terms, i.e. if and only if $e$ is even. For $p=2$, we have $\sigma(2^a)=2^{a+1}-1$, which is always odd. Therefore $\sigma(n)$ is odd exactly when every odd-prime exponent $e_p$ is even, i.e. when the odd part of $n$ is a square. Writing $n=2^a m$ with $m$ odd, this condition means $m=t^2$ for some $t$. If $a$ is even then $n=(2^{a/2}t)^2$ is a square; if $a$ is odd then $n=2(2^{(a-1)/2}t)^2$ is twice a square. Conversely, every square or twice-square has square odd part, so yields odd $\sigma(n)$. $\square$

Lemma 412.3 (Intersection implies permanent merger). If $\sigma_i(m)=\sigma_j(n)$ for some $i,j\ge1$, then $\sigma_{i+t}(m)=\sigma_{j+t}(n)$ for all $t\ge0$.

Proof. Apply $\sigma$ to both sides repeatedly: $\sigma(\sigma_i(m))=\sigma(\sigma_j(n))$ gives $\sigma_{i+1}(m)=\sigma_{j+1}(n)$, and iterate. $\square$

FAST REALITY CHECK (exact computations). I computed $\sigma$-iterates for starting values $2\le s\le 500$, taking $10$ iteration steps (i.e. values $s,\sigma(s),\dots,\sigma^{\circ 10}(s)$) and stopping early if a value exceeded $10^{12}$. Result:

• Across all starts, $909$ distinct values were visited within this truncated exploration.
• After $10$ steps (or stopping), there were $123$ distinct terminal values among the $499$ starts.
• Processing starts in increasing order and recording the first time each value appeared, $458$ of the $499$ starts intersected an earlier start's truncated orbit within these $10$ steps. (Example: $\sigma(2)=3$ and $\sigma(3)=4$, so the orbits of $2$ and $3$ meet at $4$.)

This does not decide the conjecture; it only shows many mergers happen quickly while many distinct tails still remain at this depth.

VERIFICATION

• Lemma 412.1 uses only the divisors $1$ and $n$; no hidden assumptions.
• Lemma 412.2 was checked by prime-factor parity; the square/twice-square equivalence follows from the parity of the exponent of $2$.
• Since $\sigma_k(n)$ is strictly increasing for $n\ge2$, there are no periodic points, so the dynamical graph consists of disjoint infinite paths with trees feeding into them. The conjecture is exactly that there is only one such infinite path.

FINAL

UNRESOLVED

(i) Strongest proved partial result: Every orbit $\sigma_k(n)$ for $n\ge2$ is strictly increasing and diverges (Lemma 412.1). Also, $\sigma(n)$ is odd exactly on squares or twice-squares (Lemma 412.2), giving a concrete parity test for steps in any orbit.

(ii) First gap: produce either (a) a rigorous invariant or construction yielding two starting values $m\ne n$ whose $\sigma$-orbits are disjoint, or (b) a proof that every orbit intersects a single universal orbit.

(iii) Top 3 next moves:

1. Try to build an obstruction using the parity characterization: can one construct an orbit that avoids all squares and twice-squares forever (hence has eventually even values), and another orbit forced to hit infinitely many squares/twice-squares?
2. Search for a stronger invariant, e.g. constraints on $v_2(\sigma_k(n))$ or on the set of prime divisors of $\sigma_k(n)$.
3. Extend computation: for starts up to (say) $10^5$, iterate until exceeding a larger cap, and estimate the number of distinct tails; look for two tails that remain disjoint for a very long time as candidates for a counterexample.

(iv) Minimal counterexample structure: two integers $m,n\ge2$ such that the increasing sequences $\{\sigma_k(m)\}_{k\ge1}$ and $\{\sigma_k(n)\}_{k\ge1}$ never coincide; equivalently, their functional graph components contain two distinct infinite forward paths.