Erdős problem #824 — wave 7n

Accessed: 2026-07-27 (UTC) Authoritative page: erdosproblems.com/824 Standalone verifier: runs/erdos824_wave7n_verify.py

Outcome

The problem remains open, but there are three verifiable partial outputs.

1. A post-2016 improvement to the published exponent. Combining Theorem

1.1 of Lichtman (arXiv:2211.09641) with the last two pages of Pollack--Pomerance gives \[ h(x)>x^\alpha \quad\text{for all sufficiently large }x \quad\text{for every}\quad \alpha< 2-\frac{15}{16\sqrt e} =1.431377506519406\ldots . \] This improves the \(x^{1.4}\) consequence printed by Pollack--Pomerance. It does not approach the requested exponent \(2\). This is [b] rigorous modulo the two precisely named theorems/arguments; Lichtman's source is currently cited here as an arXiv preprint, not as a proof independently reproduced in this run.

1. An explicit concentrated fiber. There are 46 explicitly listed,

pairwise-coprime integers below \(64{,}864{,}800\), all having \(\sigma(n)=64{,}864{,}800\). Thus this one fiber supplies \(\binom{46}{2}=1035\) certified pairs. The construction lemma is [a] elementary-rigorous; all primality and arithmetic in the displayed instance are [d] deterministically computer-verified.

1. Exact finite data. Direct enumeration under the page's strict

\(b<x\) convention gives \[ h(10^6)=6{,}437{,}809. \] A full table, including independent sigma-sieve checks and the squarefree subproblem, appears below. These claims are [d] computational-only.

No claim here proves \(h(x)>x^{2-o(1)}\).

Claim labels

• [a] elementary-rigorous: a complete argument is included.
• [b] rigorous-modulo-named-theorem: the deduction is complete assuming

the cited theorem.

• [c] plausible/structural-unverified: heuristic or conjectural only.
• [d] computational-only: a finite result established by the reproducible

computation.

0. Mandatory live-page audit

I fetched the Cloudflare-protected live page, its LaTeX view, and its discussion thread through the Bright Data browser path before doing mathematics.

The live state was:

• status: OPEN;
• 0 claimed proofs for this problem;
• Interested in collaborating: None;
• Currently working on this problem: None;
• “This problem looks difficult”: None;
• “This problem looks tractable”: None;
• “The results on this problem could be formalisable”: None;
• “I am working on formalising the results on this problem”: None;
• “Likes this problem”: Dogmachine;
• two comments;
• last edited: 28 September 2025.

Thus none of the mandatory stop conditions applied.

Verbatim live statement

The following is copied verbatim from the page's LaTeX view:

Let \(h(x)\) count the number of integers \(1\leq a<b<x\) such that \((a,b)=1\) and \(\sigma(a)=\sigma(b)\), where \(\sigma\) is the sum of divisors function.

Is it true that \(h(x)>x^{2-o(1)}\)?

Results and variants listed on the live page

The page says:

• Erdős proved

\[ \limsup_{x\to\infty}\frac{h(x)}x=\infty \] and claimed a similar proof. [b]

• Pollack and Pomerance gave a complete proof that

\[ \frac{h(x)}x\longrightarrow\infty. \] [b]

• It records a variant in which \(a,b\) are required to be squarefree.
• It records Weisenberg's variant: there should be no proper factors

\(u\mid a\), \(v\mid b\) with \(\sigma(u)=\sigma(v)\) and \((u,a/u)=(v,b/v)=1\).

The page's two comments, both explicitly marked by the site as unverified, are:

1. StijnC (24 November 2025) points to the first \(100{,}000\) values in the

OEIS A000203 b-file, reporting 31,525 distinct sigma-values and maximum multiplicity 183. The comment also clarifies that Erdős's “similar proof” concerns the full-limit version rather than another proof of the displayed limsup statement.

1. Terence Tao (11 August 2025) explains that Pollack--Pomerance reduce the

issue to finding many primes one less than a smooth number and records the then-used parameter \(\theta\approx3.377\), leading to \(h(x)\gg x^{1.4}\). The rendered comment literally says “\(p+1\) \(y\)-rough”; that must be a typo for \(y\)-smooth, since \(p+1\) is even and the cited Pollack--Pomerance condition is \(P^+(p+1)\leq y\).

The standalone computation independently confirms the first comment with its proper finite scope:

with the maximum attained at \(v=120960\). [d]

1. Primary-source audit

Erdős

The original 1959 paper is:

• P. Erdős, *Remarks on number theory II. Some problems on the

\(\sigma\) function*, Acta Arith. 5 (1959), 171--177, DOI 10.4064/aa-5-2-171-177; author-archive PDF.

Page 172 asks whether the number \(g(x)\) of coprime solutions \(\sigma(a)=\sigma(b)\), \(a<b<x\), satisfies \(g(x)/x\to\infty\). [b]

The 1974 source is:

• P. Erdős, Remarks on some problems in number theory, Math. Balkanica 4

(1974), 197--202; author-archive PDF.

On pages 201--202 Erdős states the same problem, sketches a proof of the limsup result, says the full limit can be obtained “with a little more trouble,” and conjectures \(h(x)>x^{2-\varepsilon}\) for every \(\varepsilon>0\). The squarefree reduction used there is discussed again below. [b]

Pollack--Pomerance

The cited paper exists as:

• P. Pollack and C. Pomerance, *Some problems of Erdős on the

sum-of-divisors function*, Trans. Amer. Math. Soc. Ser. B 3 (2016), 1--26, DOI 10.1090/btran/10; AMS open-access PDF.

Pages 23--24 give the complete \(h(x)/x\to\infty\) proof and, using Baker--Harman's shifted-prime exponent, conclude \(g(x)>x^{1.4}\) for all sufficiently large \(x\). The relevant general exponent is displayed there, not inferred from an abstract. [b]

A newer smooth-shifted-prime theorem

The later primary source is:

• J. D. Lichtman, *Primes in arithmetic progressions to large moduli, and

shifted primes without large prime factors*, arXiv:2211.09641.

The arXiv identifier exists and its Theorem 1.1 states that, for every fixed nonzero \(a\in\mathbb Z\) and every

there is a constant \(C\geq1\) such that

In particular, it is quantitative and applies to the needed shift \(a=-1\); it is not merely an infinitude statement about \(p-1\). [b]

This improves Baker--Harman's \(0.2961\) threshold:

• R. C. Baker and G. Harman, Shifted primes without large prime factors,

Acta Arith. 83 (1998), 331--361, DOI 10.4064/aa-83-4-331-361.

Exact-title, exact-formula, shifted-prime, and forward-citation searches through the access date found no later primary source claiming #824 solved or falsified, and no later theorem improving Lichtman's small-factor threshold. This is a reported search miss, not a claim that no such source can exist.

2. Sharpening the unconditional exponent

Proposition

For every

one has

for every sufficiently large \(x\). [b]

Parameter transfer

Fix \(\beta>\beta_0\) and apply Lichtman's Theorem 1.1 with \(a=-1\). Put

Every prime supplied by (1.1) then satisfies

and

Moreover, the number of such primes is

Thus every \(\theta=1/\beta\) with \(\beta>\beta_0\) satisfies exactly the smooth-shifted-prime hypothesis used on page 23 of Pollack--Pomerance.

Their page-24 stripping argument says that, for each fixed arbitrarily small \(\eta>0\), the number \(g(x)\) of coprime equal-sigma pairs with \(b\leq x\) obeys

Here is the role of the exponent in their proof. Products of \(k\) distinct smooth-shifted primes first give \(x^{2-2/\theta+o(1)}\) equal-sigma pairs. After common prime factors are stripped, almost all surviving cores have more than \((1-\eta)k\) prime factors. A fixed core has at most

preimages. Division gives (2.2).

Since \(1/\theta=\beta\), letting \(\eta\downarrow0\) and then \(\beta\downarrow\beta_0\) makes the exponent in (2.2) approach

Given any \(\alpha<\alpha_0\), choose the parameters with a fixed positive margin and absorb the \(o(1)\). Finally, Pollack--Pomerance use \(b\leq x\) while the live page uses \(b<x\); replacing \(x\) by \(x-1\) and using the same exponent margin proves the strict-cutoff assertion. This completes the deduction. [b]

The verifier recomputes

and

to 50 decimal digits. [d]

3. An elementary explicit-fiber construction

For an integer \(M\), define

Lemma

Every member \(n\in\mathcal F_M\) satisfies \(n<M\) and \(\sigma(n)=M\), and distinct members of \(\mathcal F_M\) are coprime. Consequently, all \(\binom{|\mathcal F_M|}{2}\) unordered pairs of distinct members are counted by \(h(M)\). [a]

Proof. If \(n=pq\), then \(p\ne q\), so multiplicativity gives

If \(n=M-1\) is prime, then \(\sigma(n)=M\) and \(n<M\).

It remains to check coprimality. A prime \(r\) occurring in a semiprime member determines its partner uniquely:

Hence two representations sharing a prime are the same unordered representation. The singleton prime \(M-1\) cannot occur in a semiprime representation, since its shifted factor is already \(M\), leaving complementary factor \(1\). Thus distinct members have disjoint prime supports.

\(\square\)

A 46-element instance

For

the following 46 factorizations instantiate (3.1):

60231587 = 13*4633199       61621541 = 19*3243239
63390557 = 43*1474199       63783661 = 59*1081079
64053911 = 79*810809        64240997 = 103*623699
64401341 = 139*463319       64508219 = 181*356399
64537003 = 197*327599       64594291 = 239*270269
64607149 = 251*257399       64653893 = 307*210599
64679123 = 349*185327       64684261 = 359*180179
64698091 = 389*166319       64709941 = 419*154439
64716941 = 439*147419       64725733 = 467*138599
64755007 = 593*109199       64756093 = 599*108107
64771699 = 701*92399        64773991 = 719*90089
64779791 = 769*84239        64804309 = 1091*59399
64812061 = 1259*51479       64814341 = 1319*49139
64820389 = 1511*42899       64821661 = 1559*41579
64822267 = 1583*40949       64823141 = 1619*40039
64827853 = 1847*35099       64828279 = 1871*34649
64828591 = 1889*34319       64834163 = 2287*28349
64838077 = 2699*24023       64839991 = 2969*21839
64840661 = 3079*21059       64840891 = 3119*20789
64843861 = 3779*17159       64846261 = 4679*13859
64846399 = 4751*13649       64847389 = 5399*12011
64847863 = 5849*11087       64848541 = 7019*9239
64848677 = 7699*8423        64864799 = 64864799 (prime)

The verifier factors every displayed number by trial division, checks every factor is prime, checks \((p+1)(q+1)=M\), recomputes sigma from the prime factorization, and checks all \(1035\) gcds. [d]

This is a compact construction concentrated at one sigma-value. It is not a stronger numerical lower bound for \(h(M)\) than monotonicity plus the \(h(10^6)\) table below; its value is the explicit single-fiber certificate.

Exhaustive record inside this construction

The program exhausts all prime pairs \(p<q\) with \((p+1)(q+1)\leq10^8\), exactly once per pair, and adds the possible singleton \(M-1\). It finds

attained exactly at

It enumerated 15,492,742 prime pairs. [d]

Equation (3.2) is only an optimum for the special family (3.1). It is not a claim about the largest arbitrary equal-sigma coprime fiber below \(10^8\).

4. Exact computation of \(h(x)\)

For comparison, define

Also let \(V(x)\) be the number of distinct sigma-values on \(1\leq n<x\), and let \(m(x)\) be the largest multiplicity of such a value.

The exact table is: [d]

The distinction between \(V(100000)=31524\) and the comment's 31525 is the endpoint: the table uses \(n<100000\), as the problem requires, whereas the OEIS-prefix check includes \(n=100000\).

Direct counting algorithm

The program processes \(b=1,2,\ldots,x-1\). For each \(b\), it looks only at earlier members of the exact fiber \(\sigma^{-1}(\sigma(b))\):

fiber = buckets.setdefault(sigma[b], [])
equal_pairs += len(fiber)
h += sum(math.gcd(a, b) == 1 for a in fiber)
fiber.append(b)

After processing \(b\), the accumulated value is \(h(b+1)\), which enforces the strict endpoint without an adjustment after the fact.

The sigma values are generated twice by independent recurrences:

1. an Euler linear sieve using

\[ \sigma(p^{a+1}r)=\sigma(p^ar)+p^{a+1}\sigma(r) \quad((p,r)=1); \]

1. an Eratosthenes smallest-prime-factor sieve, followed by direct geometric

sums for each prime power.

The two arrays agree entry-for-entry through \(999999\). A third definition-level divisor-pair routine recomputes every \(\sigma(n)\) through \(n=10000\), and a separate trial-division routine checks squarefreeness there.

The entire seven-column table is then independently aggregated a second way: all inputs are sorted into complete sigma-fibers, the non-coprime columns are recomputed from cutoff-truncated binomial coefficients, and each gcd-one pair is activated at the first requested cutoff larger than its second member. The two full \(x\leq10^6\) tables agree exactly.

5. Reproduction

Run the complete standard-library verifier from the repository root:

python runs/erdos824_wave7n_verify.py

A faster mode retains the \(h(10^6)\) table and explicit 46-element certificate but searches the special construction only through \(10^7\):

python runs/erdos824_wave7n_verify.py --quick

The complete executable source is runs/erdos824_wave7n_verify.py (665 lines), SHA-256

c47d2ef412d891415885ca4341284ca4345d4a09b71ad84c3c12a2fde8233c71

The default run exited successfully with:

sigma-table sha256=2e7a850c0997767fa790914c6e35ebb501ec2702cac5c4983deccf07e2956edb
record=46 maximizers=(64864800, 90810720)
summary sha256=c22c39c4b7e453d587474bc3ae435cdd77e1a202cd4ae64f178a413323453bd0
ALL CHECKS PASSED in 50.26s

Measured resources were 49.91 user CPU seconds, 50.33 wall seconds, and 263,608 KiB peak resident memory. No external package or downloaded data is used by the verifier.

6. Exact wall for the standard machinery

Lichtman's theorem currently reaches

in the quantitative smooth-shifted-prime statement. Pollack--Pomerance turn a given \(\beta\) into a coprime-pair exponent approaching \(2(1-\beta)\). Therefore this route stops at \(1.431377\ldots\), exactly as calculated above.

A sufficient missing lemma is:

For every fixed \(\beta>0\), there is \(C_\beta\) such that, for all sufficiently large \(X\), \[ > \#\{X<p\leq2X:P^+(p+1)\leq X^\beta\} > \gg_\beta \frac{X}{(\log X)^{C_\beta}}. \tag{6.1} > \]

If (6.1) were known for arbitrarily small fixed \(\beta\), the same parameter transfer would give \(h(x)>x^\alpha\) for every \(\alpha<2\), exactly the live question. [b] conditional implication; [c] unproved hypothesis

The obstruction is thus not a finite sigma-table computation or the common-factor stripping step. It is the lack of a quantitative theorem giving primes \(p\) for which \(p+1\) is \(p^\beta\)-smooth for arbitrarily small \(\beta\). Larger finite searches can test examples but cannot supply the uniform all-large-\(X\) estimate (6.1).

PARTIAL: Verified \(h(10^6)=6{,}437{,}809\), an explicit 46-member coprime sigma-fiber, and the sharper named-theorem bound \(h(x)>x^\alpha\) for every \(\alpha<1.4313775065\ldots\); exponent \(2\) still requires smooth shifted primes at arbitrarily small fixed smoothness exponent.