ERDŐS/DAILY ▸

← back to the ledger

ERDőS #824 · PARTIAL

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.

2. 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.

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

\(b

\[ 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

the cited theorem.

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:

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

> \((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:

\[ \limsup_{x\to\infty}\frac{h(x)}x=\infty \]

and claimed a similar proof. [b]

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

[b]

\(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.

2. 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:

\[ \#\{\sigma(n):1\leq n\leq100000\}=31525, \qquad \max_v\#\{n\leq100000:\sigma(n)=v\}=183, \]

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

1. Primary-source audit

Erdős

The original 1959 paper is:

\(\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]

The 1974 source is:

(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:

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:

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

\[ \beta>\beta_0:=\frac{15}{32\sqrt e}=0.2843112467\ldots, \]

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

\[ \#\{XIn 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

\[ \alpha<\alpha_0:= 2-\frac{15}{16\sqrt e} =1.43137750651940616537\ldots, \]

one has

\[ h(x)>x^\alpha \]

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

Parameter transfer

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

Put

\[ y=(2X)^\beta,\qquad \theta=\frac1\beta. \]

Every prime supplied by (1.1) then satisfies

\[ p\leq 2X=y^\theta \]

and

\[ P^+(p+1)\leq X^\beta=2^{-\beta}yMoreover, the number of such primes is

\[ \gg \frac{X}{(\log X)^C} \gg \frac{y^\theta}{(\log y)^C}. \tag{2.1} \]

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

\[ g(x)\geq x^{(2-\eta)(1-1/\theta)+o(1)}. \tag{2.2} \]

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

\[ \binom{n}{k-j_0} \leq x^{(1-1/\theta)\eta+o(1)} \]

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

\[ 2(1-\beta_0) =2-\frac{15}{16\sqrt e} =\alpha_0. \]

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

same exponent margin proves the strict-cutoff assertion. This completes the

deduction. [b]

The verifier recomputes

\[ \beta_0=0.28431124674029691731\ldots,\quad \theta_0=\beta_0^{-1}=3.51727204416027337994\ldots, \]

and

\[ \alpha_0=1.43137750651940616537\ldots \]

to 50 decimal digits. [d]

3. An elementary explicit-fiber construction

For an integer \(M\), define

\[ \mathcal F_M= \{pq:\ pLemma

Every member \(n\in\mathcal F_M\) satisfies \(n

\(\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

\[ \sigma(n)=(p+1)(q+1)=M, \qquad n=pq=M-p-q-1If \(n=M-1\) is prime, then \(\sigma(n)=M\) and \(n

It remains to check coprimality. A prime \(r\) occurring in a semiprime member

determines its partner uniquely:

\[ s=\frac{M}{r+1}-1. \]

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

\[ M=64{,}864{,}800 \]

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

\((p+1)(q+1)\leq10^8\), exactly once per pair, and adds the possible singleton

\(M-1\). It finds

\[ \max_{M\leq10^8}|\mathcal F_M|=46, \]

attained exactly at

\[ M=64{,}864{,}800,\qquad M=90{,}810{,}720. \tag{3.2} \]

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

\[ \begin{aligned} E(x)&=\#\{1\leq aAlso let \(V(x)\) be the number of distinct sigma-values on \(1\leq n

and let \(m(x)\) be the largest multiplicity of such a value.

The exact table is: [d]

| \(x\) | \(h(x)\) | \(E(x)\) | \(h_{\rm sf}(x)\) | \(E_{\rm sf}(x)\) | \(V(x)\) | \(m(x)\) |

|---:|---:|---:|---:|---:|---:|---:|

| 10 | 0 | 0 | 0 | 0 | 9 | 1 |

| 100 | 37 | 56 | 26 | 35 | 63 | 5 |

| 1,000 | 716 | 1,562 | 448 | 791 | 466 | 15 |

| 10,000 | 15,073 | 38,383 | 8,571 | 16,897 | 3,699 | 57 |

| 100,000 | 312,096 | 861,450 | 168,079 | 345,009 | 31,524 | 183 |

| 1,000,000 | 6,437,809 | 18,633,435 | 3,292,499 | 6,897,233 | 278,341 | 563 |

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); \]

2. 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

\[ \beta>\frac{15}{32\sqrt e}=0.284311\ldots \]

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 \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.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger