Erdős problem #1060 — wave w030

Accessed 2026-07-29. This is a partial result, not a solution of the uniform asymptotic question.

Claim labels

• (a) elementary-rigorous: proved below from elementary facts.
• (b) rigorous-modulo-named-theorem: the deduction is rigorous modulo the

named, correctly identified theorem.

• (c) plausible/structural-unverified: a heuristic or explicitly

unproved route; never used as a theorem.

• (d) computational-only: proved by the exhaustive standalone program

supplied with this report, or reported as computation by another source.

0. Mandatory live-page check

I loaded both the live problem page and its discussion thread through the Bright Data browser path. I did not rely on datacenter curl or on the stale tracker YAML.

The rendered live status was OPEN.

Verbatim current statement

Let \(f(n)\) count the number of solutions to \(k\sigma(k)=n\), where \(\sigma(k)\) is the sum of divisors of \(k\). Is it true that \(f(n)\leq n^{o(\frac{1}{\log\log n})}\)? Perhaps even \(\leq(\log n)^{O(1)}\)?

The page's only remarks text is:

This is discussed in problem B11 of Guy's collection [Gu04].

The current metadata shown on the page was:

| field | live value | |---|---| | status | OPEN | | last edited | 28 September 2025 | | comments | 2 comments on this problem | | claimed proofs | 0 claimed proofs for this problem | | Likes this problem | skominers | | Interested in collaborating | skominers | | Currently working on this problem | None | | difficult / tractable / formalisable / formalising markers | all None | | formalised statement | Yes | | related OEIS sequence | A327153 |

Thus the mandatory stop condition did not apply: the formal current-worker marker is None, and the page shows neither a claimed proof nor a solved/falsified status.

All current comments

The newest comment, by skominers at 11:45 on 20 July 2026, reports:

1. injectivity of \(k\mapsto k\sigma(k)\) on squarefree integers;
2. the resulting majorant

\[ f(n)\leq\prod_{p\mid n}v_p(n) \] and its maximal-order consequence \[ f(n)\leq \exp\!\left(\left(\frac{\log 3}{3}+o(1)\right) \frac{\log n}{\log\log n}\right); \]

1. a computer-assisted claim that

\[ a(7)=106345074572730040320, \] that \(f(n)\leq5\) for \(1<n<a(7)\), and that multiplicity \(6\) does not occur up through that value; and

1. together with a displayed sixfold value, the claimed inequality

\(a(7)<a(6)\).

The comment links Scott Duke Kominers's 20 July 2026 working paper “On the Number of Solutions of \(k\sigma(k)=n\)”. The paper says its census source archive is “currently being packaged for posting.” I therefore treat its large census as (d, externally reported), not as a theorem or as independently reproduced here. The elementary majorant is reproved below.

The older comment, by StijnC at 07:36 on 6 October 2025, links OEIS and observes that

The rendered plain text visually collapses the superscript to “216”; I checked the live MathJax DOM, whose exact data-latex value is n \le 2^{16}.

The forum itself warns that comments are the users' responsibility and are not verified. No proof claim is attached to either comment.

1. Primary-source literature audit

1.1 Guy's source

Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer (2004), Problem B11, pp. 101–102, DOI 10.1007/978-0-387-26677-0, is the source cited by the live page. B11 records:

• the collision \(12\sigma(12)=14\sigma(14)=336\);
• Erdős's squarefree-injectivity observation;
• Mąkowski's construction of large finite fibers from any finite

collection of distinct Mersenne primes; and

• Erdős's belief that for every fixed \(\epsilon>0\),

\(f(n)<n^{\epsilon/\log\log n}\), perhaps even \(f(n)<(\log n)^c\).

That last formulation is the source of the live quantitative question. (b, source identification)

1.2 Erdős (1959)

Paul Erdős, “Remarks on number theory II: Some problems on the \(\sigma\) function,” Acta Arithmetica 5 (1959), 171–177, DOI 10.4064/aa-5-2-171-177, proves related results about fixed abundancy \(\sigma(n)/n\), including squarefree uniqueness for abundancies and a linear asymptotic for the number of abundancy collisions. Those results do not give the desired uniform fiber bound here: if \(k\sigma(k)=n\), then \(\sigma(k)/k=n/k^2\), which changes with \(k\). (b)

1.3 Noppakaew–Pongsriiam (2023)

Passawan Noppakaew and Prapanpong Pongsriiam, “Product of Some Polynomials and Arithmetic Functions,” Journal of Integer Sequences 26 (2023), Article 23.9.1, prove in Theorem 12 that \(n^a\sigma(n)^b\) is injective on squarefree integers for all positive integers \(a,b\). Their \(a=b=1\) case is exactly the squarefree input needed here. Questions 27–28 explicitly ask about the number of solutions to \(x\sigma(x)=m\). (b)

1.4 July 2026 working paper

The Kominers paper linked by the current comment gives a self-contained proof of the squarefree result, the \(\prod v_p(n)\) bound, its sharp majorant constant, and the large census described above. It is a current working paper rather than a peer-reviewed source. Its proof of the elementary bound checks out and is independently reconstructed in Sections 2.1–2.3. Its large minimality/no-six census is not independently adopted because the source code is not yet linked. (a) for the reconstructed proof; (d) for the reported census

1.5 Search misses and false leads

Targeted searches used the exact equations “\(k\sigma(k)=n\),” “\(m\sigma(m)=n\sigma(n)\),” the OEIS identifiers A327153/A212490, Guy B11, and citations to the 2023 paper.

• Gabdullin–Iudelevich–Luca,

“Numbers of the form \(kf(k)\)”, International Journal of Number Theory 19 (2023), 1191–1204, treats \(f=\tau,\omega,\varphi\), not \(f=\sigma\).

• Akande,

“The number of preimages of iterates of \(\phi\) and \(\sigma\)”, Journal of Number Theory 259 (2024), 82–92, bounds fibers of a fixed value of \(\sigma\) and its iterates. Here the required value is \(\sigma(k)=n/k\), varying with the candidate \(k\), so that theorem does not imply the requested estimate.

• OEIS A212490 records the least known values of

each exact multiplicity, but OEIS data are not a proof of uniform minimality.

I found no other primary source giving a uniform bound for this exact function stronger than the July 2026 elementary majorant. This is an honest search miss, not a claim that no such paper exists.

2. Exact powerful-core reduction

Write

The following reformulation makes precise what the squarefree argument does and what a stronger argument would still have to control.

2.1 Squarefree injectivity

Lemma 2.1. If \(a,b\) are squarefree and \(h(a)=h(b)\), then \(a=b\). (a)

Proof. Put \(d=(a,b)\), \(a=da'\), and \(b=db'\). Squarefreeness makes \(d,a',b'\) pairwise coprime, so multiplicativity gives \(h(a')=h(b')\). Thus it suffices to treat coprime squarefree \(a',b'\).

If both are nontrivial, let \(p\) be the largest prime dividing \(a'b'\); say \(p\mid a'\). Then \(p\mid h(a')=h(b')\), but \(p\nmid b'\), so

For some prime \(q<p\), therefore, \(p\mid q+1\). Since \(q+1\leq p\), we have \(q+1=p\). The only consecutive primes are \(2,3\), so this is impossible when \(p\geq5\). If \(p\leq3\), the only nontrivial coprime possibility is \(\{a',b'\}=\{2,3\}\), but \(h(2)=6\neq12=h(3)\). If one of \(a',b'\) is \(1\), the other must be \(1\) because \(h(m)>1\) for \(m>1\). Hence \(a'=b'=1\) and \(a=b\). \(\square\)

2.2 A constructive inverse on squarefree inputs

For squarefree \(s\),

If the largest prime \(q\mid s\) satisfies \(q\geq5\), then \(q\) is the largest prime factor of \(h(s)\): every prime factor of \(p+1\), for odd \(p\leq q\), is at most \((p+1)/2<p\), and \(2+1\) contributes only \(3\). Thus one can peel off \(q(q+1)\) and recurse. The terminal supports contained in \(\{2,3\}\) are

This gives an exact algorithm \(I(M)\): it returns the unique squarefree \(s\) with \(h(s)=M\), or reports that none exists. Its correctness is another constructive proof of Lemma 2.1. (a)

2.3 Bijection with admissible powerful divisors

Call \(P\) powerful if every prime occurring in \(P\) has exponent at least two; allow \(P=1\). For any \(k\), split it uniquely as

Then \(P(k)\) is powerful, \(S(k)\) is squarefree, \((P(k),S(k))=1\), and

For \(n=\prod p^{a_p}\), define

Also define the admissible set

Proposition 2.2.

(a)

Proof. If \(h(k)=n\), then \(k\mid n\), so \(P(k)\in\mathcal P(n)\). The displayed factorisation gives

The squarefree inverse therefore recovers \(S(k)\) uniquely, so \(P(k)\in\mathcal A(n)\). Conversely, every \(P\in\mathcal A(n)\), with \(S=I(n/h(P))\), gives

The two maps are inverse. \(\square\)

There are exactly \(a_p\) choices \(0,2,\ldots,a_p\) for the exponent of each \(p\) in \(P\). Consequently,

This recovers the July 2026 majorant without importing its proof. (a)

For completeness, the standard maximal-order calculation gives

Indeed, \((\log a)/a\) is maximised over positive integers at \(a=3\). Splitting primes at

makes the small-prime contribution \(o(\log n/\log\log n)\), while for \(p>z\) one uses \(\sum v_p(n)\leq\log n/\log z\). The reverse inequality for this majorant is realised by \(\prod_{p\leq y}p^3\), using the prime number theorem. Thus (2.3) is (b), modulo the prime number theorem.

The sharpness is only for the majorant, not for \(f\). It explains exactly why merely counting powerful cores cannot establish the requested little-\(o\) exponent.

3. Improved bound for every odd target

This is the main new rigorous analytic progress in this run.

Lemma 3.1. If \(n\) is odd and \(h(k)=n\), then \(k\) is a square. (a)

Proof. Since \(k\mid n\), \(k\) is odd, and \(\sigma(k)=n/k\) is odd. For an odd prime power \(p^e\),

is odd exactly when \(e\) is even. Hence every exponent in the odd integer \(k\) is even. \(\square\)

It follows immediately that, for odd \(n=\prod p^{a_p}\),

the number of square divisors of \(n\). (a)

For every integer \(a\geq1\),

with equality at \(a=2\). For even \(a=2m\), this follows from \(m+1\leq2^m\); the odd case is weaker and follows from the same inequality.

Applying the same small/large-prime split as in (2.3) yields:

Proposition 3.2. Uniformly as odd \(n\to\infty\),

(a) for the reduction and upper-bound argument

Here are the details of the asymptotic step. Let \(L=\log n\), \(L_2=\log\log n\), and \(z=L/L_2^3\). The primes \(p\leq z\) contribute at most

For \(p>z\), (3.2) and

give (3.3).

Moreover,

because the reverse inequality for \(Q\) is obtained along \(\prod_{3\leq p\leq y}p^2\). This sharpness statement is (b), modulo the prime number theorem, and again concerns \(Q\), not the actual fiber size.

Numerically,

Thus (3.3) strictly improves the located general bound on the entire infinite regime of odd targets. It still has a positive constant and hence does not reach the little-\(o\) requested by Erdős.

4. Independent exact computations

The complete source is runs/erdos1060_wavew030_reverify.py. It uses only the Python standard library.

4.1 Complete census through \(10^{14}\)

For \(k>1\),

Therefore \(h(k)\leq X\) implies

For \(X=10^{14}\), this is the finite range \(2\leq k\leq9,999,999\). (a, completeness reduction)

The program computes every \(\sigma(k)\) in that range with a fresh linear sieve, retains every \(k\sigma(k)\leq X\), sorts the exact integer values, and run-length counts them. It enumerated \(8,103,366\) preimages giving \(7,859,315\) distinct represented values. The exact histogram on \(1<n\leq10^{14}\) is: (d)

| \(f(n)\) | number of \(n\) | |---:|---:| | 0 | 99,999,992,140,684 | | 1 | 7,621,870 | | 2 | 230,905 | | 3 | 6,475 | | 4 | 64 | | 5 | 1 |

In particular,

The least values of each attained positive multiplicity, along with a second verification by complete divisor enumeration, are: (d)

| \(r\) | least \(n>1\) with \(f(n)=r\) | complete fiber | |---:|---:|---| | 1 | 6 | \(2\) | | 2 | 336 | \(12,14\) | | 3 | 333,312 | \(336,372,434\) | | 4 | 5,418,319,872 | \(41,664,42,672,47,244,55,118\) | | 5 | 1,584,858,562,560 | \(624,960,640,080,696,384,708,660,713,232\) |

The sorted run-length table has SHA-256

c66731365f03614581b331c8d10a05855500e04fb325d0ef6f1ad24a7bae1684

This range is much smaller than the externally reported July 2026 census, but it is independently reproducible now and gives the entire histogram, not just the maximum.

4.2 Exact checks of the displayed sixfold and sevenfold values

If \(h(k)=N\), then \(k\mid N\). Thus enumerating every divisor of a factored \(N\) is an exact finite check of its full fiber, with no search cutoff. (a, completeness; d, enumeration)

The program independently confirms

has exactly the seven preimages

and

has exactly the six preimages

This proves \(f(N_7)=7\) and \(f(N_6)=6\). It does not prove that \(N_7=a(7)\), that \(N_6=a(6)\), or that \(a(7)<a(6)\); those assertions need the huge uniform exclusion census not reproduced here.

For \(N_7\), the successive candidate counts in (2.2) are

For \(N_6\), they are

These exact numbers show concretely where the current majorant loses information. (d)

4.3 A sharp finite odd-target bound through \(10^{24}\)

If odd \(n\leq10^{24}\) has a preimage, Lemma 3.1 writes that preimage as \(k=m^2\) with \(m\) odd. Since

we must have \(m<10^6\). The verifier factors and evaluates \(h(m^2)\) for all \(500,000\) odd integers \(1\leq m<10^6\), and finds all values distinct. Hence

This is sharp: \(h(9)=117\), and complete divisor enumeration gives \(f(117)=1\). (d), with the elementary completeness reduction above

5. Reproduction and cross-check design

Run:

python runs/erdos1060_wavew030_reverify.py

The verifier deliberately uses independent paths:

1. a linear \(\sigma\)-sieve followed by global sort/run-length counting;
2. complete per-target divisor enumeration using geometric sums;
3. the powerful-core reduction with the recursive squarefree inverse;
4. a separate least-prime sieve for the odd-square census; and
5. trial-division factorisation of every displayed large target.

It also compares the direct-divisor and powerful-core fibers for every \(1\leq n\leq20,000\), checks the squarefree inverse on every squarefree input in that range, verifies the parity criterion through \(20,000\), and audits both exponent-ratio constants through exponent \(100,000\).

A clean run on this VM ended:

[census] histogram: {1: 7621870, 2: 230905, 3: 6475, 4: 64, 5: 1}
[census] least values: {1: 6, 2: 336, 3: 333312,
                        4: 5418319872, 5: 1584858562560}
[reduction] direct and powerful-core fibers agree for all 1 <= n <= 20,000
[odd] all 500,000 odd squares m^2 with 1 <= m < 10^6 have distinct h-values
[odd] therefore f(n) <= 1 for every odd n <= 1000000000000000000000000
ALL CHECKS PASSED in 20.881s

The measured peak resident memory was about 408 MiB.

6. Exact wall

By (2.1), the original problem is equivalent to proving

and the proposed polylogarithmic strengthening is equivalent to \(|\mathcal A(n)|\leq(\log n)^{O(1)}\).

A clean sufficient missing lemma would be

No source located here proves (6.2). Squarefree injectivity supplies at most one tail for each powerful core, but says nothing strong enough about how many powerful cores satisfy \(h(P)\mid n\). Discarding that divisibility condition gives \(\prod v_p(n)\), whose positive constant \(\log3/3\) is genuinely sharp for that discarded-condition majorant. The odd-target parity restriction lowers the constant to \(\log2/2\), but does not make it vanish.

This also pinpoints why standard inverse-\(\sigma\) estimates do not plug in: the target \(\sigma(k)=n/k\) varies with \(k\), while (6.2) requires a simultaneous anti-concentration statement for the prime factors of many geometric sums \(\sigma(p^e)\) constrained to the fixed factorisation of \(n\).

Finite computation cannot supply the missing uniformity. Reproducing the July 2026 cutoff would require enumerating about \(10.31\) billion inputs, roughly \(10^3\) times this run. A naive scaling of this implementation would need over 400 GiB; even an optimized segmented C++/external-sort version would write at least about 65 GiB of raw 64-bit values and plausibly 0.1–0.3 TB of scratch data. A realistic engineering estimate is 5–20 core-hours plus fast local SSD, so it was not run under the few-CPU-minute constraint. More importantly, even that census would not prove (6.1).

PARTIAL: Proved the exact powerful-core bijection, improved the general located exponent constant from log(3)/3 to log(2)/2 for every odd target, certified f(n)<=5 through 10^14 and f(n)<=1 for odd n through 10^24, and isolated the missing uniform bound on admissible powerful divisors.