ERDŐS/DAILY ▸

← back to the ledger

ERDőS #371 · PARTIAL

Erdős problem 371 — wave8y

Access/research date: 2026-07-28 UTC.

Claim labels

No claim below closes the asymptotic problem.

Step 0: authoritative live page and go/no-go decision

The live page was fetched through the Bright Data browser, including the separate discussion thread:

Verbatim live statement

> Let \(P(n)\) denote the largest prime factor of \(n\). Show that the set of \(n\) with \(P(n) < P(n+1)\) has density \(1/2\).

The page labels the problem OPEN, reports 0 claimed proofs for this problem, and has Currently working on this problem: None. It also has Interested in collaborating: None. Thus the mandatory stop conditions do not apply. (page-observed)

The other displayed markers are: Likes this problem — Dogmachine; This problem looks difficult — Dogmachine; 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. The page says it was last edited 23 January 2026. (page-observed)

The citation string attached to the statement is [ErPo78,p.320][Er79e][ErGr80,p.70][Er85c,p.82][Va99,1.10]. (page-observed)

Known results listed on the main page

\[ \#\{n(0.2017-o(1))x, \]

with the same lower bound for the complement. (b; page-observed)

\[ P(n+1)>P(n)n^\alpha \]

exists. (b; page-observed)

\[ \int_{[0,1]^2}\mathbf 1_{y\geq x+\alpha}u(x)u(y)\,dx\,dy, \qquad u(x)=x^{-1}\rho(x^{-1}-1), \]

where \(\rho\) is the Dickman function. (b; page-observed and primary-source verified)

All five live comments

The page warns that comments are user-supplied and unverified. (page-observed)

1. Alfaiz, 03:10 on 20 July 2026: Z. Yang [Ya26] proved a lower bound larger than \(0.280\), improving Lü–Wang. (page-observed; independently source-verified below)

2. TerenceTao, 20:07 on 5 December 2025: a correction that [TaTe19] gives natural density \(1/2\), rather than \(0\), at almost all scales; the site says it was updated. (page-observed; independently source-verified below)

3. Alfaiz, 03:12 on 23 October 2025: pointed to Lü–Wang and its \(0.2017\) lower bound; the site says it was updated. (page-observed; independently source-verified below)

4. Alfaiz, 13:11 on 15 October 2025: pointed to Wang's 2021 conditional result under Elliott–Halberstam for friable integers; the site says it was updated. (page-observed; independently source-verified below)

5. DesmondWeisenberg, 20:06 on 24 August 2025: pointed to Teräväinen's logarithmic-density result and its relation to problem 928; the site says it was updated. (page-observed; independently source-verified below)

The July 2026 comment is newer than the January 2026 edit date of the main prose, so the main page's phrase “best unconditional lower bound” is stale. (a, from the displayed dates; page-observed)

Primary-source literature audit

I searched exact titles, the expressions \(P^+(n)

1. Erdős–Pomerance, On the largest prime factors of \(n\) and \(n+1\), Aequationes Mathematicae 17 (1978), 311–321. Their theorem includes the near-diagonal estimate: for every \(\varepsilon>0\), some \(\delta>0\) makes

\[ \#\{n

for all sufficiently large \(x\). It yields positive lower density for each ordering. (b)

2. Teräväinen, On binary correlations of multiplicative functions, arXiv:1710.01195v2, published as Forum of Mathematics, Sigma 6 (2018), e10, DOI 10.1017/fms.2018.10. Theorem 1.16 states logarithmic density \(1/2\); Theorem 1.17 gives the displayed \(\alpha\)-formula. (b)

3. Tao–Teräväinen, The structure of correlations of multiplicative functions at almost all scales, arXiv:1809.02518, published in Algebra & Number Theory 13 (2019), 2103–2150, DOI 10.2140/ant.2019.13.2103. Corollary 1.16 gives an exceptional set \(X_0\) of logarithmic density zero such that

\[ \lim_{\substack{X\to\infty\\X\notin X_0}} \frac1X\#\{n\leq X:P(n)

The paper explicitly says that upgrading “almost all scales” to “all scales” is not known. (b)

4. Wang, Three conjectures on \(P^+(n)\) and \(P^+(n+1)\) hold under the Elliott-Halberstam conjecture for friable integers, Journal of Number Theory 223 (2021), 1–11. Its abstract states the conditional density \(1/2\) and the stronger conditional joint friability law. (b)

5. Lü–Wang, On the largest prime factors of consecutive integers, Monatshefte für Mathematik 206 (2025), 403–418. Its abstract states the \(0.2017\) lower bound. (b)

6. Yang, An improvement on the largest prime factors of consecutive integers, arXiv:2607.16032v1, submitted 17 July 2026. Theorem 1.4 states, in its asymptotic notation,

\[ \#\{n0.280x, \]

and the same for the reversed ordering. This is a 31-page preprint, not a claimed solution of density \(1/2\). (b)

Yang's theorem implies that every sufficiently large prefix proportion is between \(0.280\) and \(0.720\), because the two strict orderings partition the integers. It supplies neither convergence nor equality of the two proportions. (a) from Yang's named theorem, hence overall (b)

The current searches found no unconditional all-scales proof later than Yang v1. This is only an honest search result, not a proof that no such paper exists. (c)

An exact parity/triple reduction

Adopt the standard convention \(P(1)=1\). Define

\[ A(X)=\#\{1\leq n\leq X:P(n)Adjacent values never tie: if \(P(n)=P(n+1)=p>1\), then the prime \(p\) divides both consecutive integers. The case \(n=1\) is also not a tie. Therefore

\[ D(X)=\sum_{n\leq X} \begin{cases} +1,&P(n)P(n+1). \end{cases} \tag{1} \]

(a)

For \(M\geq1\), let

\[ \begin{aligned} U(M)&=\#\{2\leq m\leq M:P(2m-1)P(m)>P(2m+1)\}. \end{aligned} \]

Then the exact identity is

\[ \boxed{D(2M)=2+2\bigl(U(M)-V(M)\bigr).} \tag{2} \]

(a)

Proof: the base pair \(n=1,2\) contributes \(+2\). For \(m\geq2\), \(P(2m)=P(m)\). Also \(m,2m-1,2m+1\) are pairwise coprime, so their three largest prime factors are distinct. Pairing the summands in (1) at \(2m-1,2m\) gives

\[ \operatorname{sgn}\!\bigl(P(m)-P(2m-1)\bigr) +\operatorname{sgn}\!\bigl(P(2m+1)-P(m)\bigr). \]

This is \(+2\) for the increasing triple counted by \(U\), \(-2\) for the decreasing triple counted by \(V\), and \(0\) for the other four order types. Summing proves (2). (a)

Since \(D(2M-1)\) and \(D(2M)\) differ by exactly \(1\), the original problem is equivalent to the single signed estimate

\[ \boxed{U(M)-V(M)=o(M).} \tag{3} \]

Thus (3), rather than six-way independence of all triple orderings, is exactly what remains in this reduction. (a)

I did not find identity (2) in the sources searched, but I make no novelty claim for it. (c)

Exact census through \(10^8\)

The standalone verifier is runs/erdos371_wave8y_reverify.py. It exhausts every \(n\leq10^8\); this is not sampling. (d)

| \(X\) | \(A(X)\) | \(A(X)/X\) | \(D(X)\) | \(U(X/2)\) | \(V(X/2)\) | \(U-V\) |

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

| 10 | 7 | 0.70000000 | 4 | 1 | 0 | 1 |

| 100 | 53 | 0.53000000 | 6 | 8 | 6 | 2 |

| 1,000 | 511 | 0.51100000 | 22 | 84 | 74 | 10 |

| 10,000 | 5,009 | 0.50090000 | 18 | 830 | 822 | 8 |

| 100,000 | 50,080 | 0.50080000 | 160 | 8,377 | 8,298 | 79 |

| 1,000,000 | 500,149 | 0.50014900 | 298 | 83,959 | 83,811 | 148 |

| 10,000,000 | 4,999,951 | 0.49999510 | -98 | 843,545 | 843,595 | -50 |

| 100,000,000 | 49,997,566 | 0.49997566 | -4,868 | 8,449,824 | 8,452,259 | -2,435 |

Every table entry is (d). Equation (2) independently checks each displayed discrepancy; for example,

\[ -4868=2+2(8{,}449{,}824-8{,}452{,}259). \]

(a) applied to (d) data

The exhaustive extrema on the whole range \(1\leq X\leq10^8\) are

\[ \max D(X)=1332\quad\text{at }X=9{,}340{,}534, \] \[ \min D(X)=-6870\quad\text{at }X=91{,}593{,}584. \]

Consequently,

\[ \left|A(X)-\frac X2\right|\leq3435 \quad(1\leq X\leq10^8), \]

with equality at \(X=91{,}593{,}584\). (d)

The verifier also computes the exact maximum relative error over entire tail ranges:

| Tail checked | Attaining \(X\) | \(D(X)\) | exact \(\max |A(X)/X-1/2|\) |

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

| \(10^3\leq X\leq10^8\) | 1,041 | 27 | \(9/694\) |

| \(10^4\leq X\leq10^8\) | 17,788 | 106 | \(53/17{,}788\) |

| \(10^5\leq X\leq10^8\) | 107,968 | 246 | \(123/107{,}968\) |

| \(10^6\leq X\leq10^8\) | 1,359,738 | 1,020 | \(85/226{,}623\) |

| \(10^7\leq X\leq10^8\) | 91,437,478 | -6,868 | \(1717/45{,}718{,}739\approx3.75557164864062\cdot10^{-5}\) |

These are sharp only on the stated finite ranges. (d)

There were zero adjacent LPF ties in the computation, consistent with the elementary proof that ties are impossible. (a) and (d)

How the computation is verified

The largest-prime-factor sieve starts with zeros and visits potential primes in increasing order. A composite index was already written by a smaller prime divisor, while an unwritten index is prime. Each prime overwrites all its multiples, so after the last overwrite every integer stores its largest prime divisor. This proves the sieve invariant. (a)

The script adds four independent safeguards:

1. A separate trial-division implementation recomputes \(P(n)\) for every \(n\leq20{,}000\). (d)

2. It checks (2) at every even prefix, not only at table endpoints. (a) applied computationally, hence (d) for the finite audit)

3. It asserts the full prefix table, discrepancy extrema, and all decade-relative-error extremizers against fixed expected constants. (d)

4. It selects relative-error extrema by integer cross multiplication; floating point is used only to print decimals. (a)

The completed full run printed FULL ASSERTIONS PASSED. On this VM it used 15.526 seconds for the sieve and 79.024 seconds for the independent checks and scan, 94.549 seconds total. The main LPF array is about 400 MB, and the largest temporary slice is about 200 MB. (d)

Reproduce from the repository root with:

python runs/erdos371_wave8y_reverify.py

A smaller structural audit can be run with, for example:

python runs/erdos371_wave8y_reverify.py --limit 1000000

The pure-Python design scales linearly up to logarithmic factors. The allocation formula predicts roughly 6 GB peak memory at \(10^9\), while a simple extrapolation from the measured run suggests about 16 single-core minutes, so that heavier run was not attempted. Such a finite extension would still not resolve an asymptotic uniformity question. (a) for the allocation; (c) for the runtime extrapolation; (a) for the logical limitation

The exact analytic wall

Equation (3) is an elementary equivalent form of the problem. A sufficient lemma closer to the existing analytic machinery can also be stated precisely.

For a fixed finite partition \((I_i)\) of the exponent interval, put

\[ B_X(I_i,I_j)=\#\left\{n\leq X: \frac{\log P(n)}{\log X}\in I_i,\quad \frac{\log P(n+1)}{\log X}\in I_j \right\}. \]

An all-scales box-swap estimate

\[ B_X(I_i,I_j)-B_X(I_j,I_i)=o(X) \qquad(i\ne j) \tag{4} \]

for every fixed partition would imply the answer. (b, using the Erdős–Pomerance near-diagonal theorem)

The exceptional endpoint \(n=X\), if \(P(X+1)>X\), contributes only \(O(1)\) and is harmless. Indeed, off-diagonal ascending and descending boxes cancel by (4). Choose the mesh at most \(\delta/2\). Points whose two exponents occupy the same bin then have

\[ X^{-\delta}for \(X>1\). Erdős–Pomerance make this diagonal contribution \(<\varepsilon X\), with \(\delta\) chosen after \(\varepsilon\). A fixed partition has finitely many off-diagonal pairs, so their \(o(X)\) errors sum to \(o(X)\); then \(\varepsilon\to0\). (a) modulo the named near-diagonal theorem, hence (b)

Full asymptotic independence of the two friability variables would imply (4), but (4) is weaker: only swap symmetry is needed. (a)

The precise missing ingredient is therefore an unweighted, fixed-shift, all-scales decorrelation/exchangeability estimate strong enough to give (4), or directly the scalar cancellation (3). (c as a diagnosis; (3) itself is (a))

  • Teräväinen supplies logarithmically weighted decorrelation, which cannot by itself rule out exceptional unweighted scales. (b)
  • Tao–Teräväinen supply the desired unweighted conclusion outside a set \(X_0\) of logarithmic density zero; eliminating \(X_0\) is exactly the remaining quantifier needed by the original problem. (b)
  • Wang eliminates it only after assuming Elliott–Halberstam for friable integers. (b)
  • Yang's unconditional sieve lower bounds control how often each ordering occurs, but do not force their difference to be \(o(X)\). (a) from the named theorem, hence overall (b)

The \(10^8\) census gives strong finite agreement with \(1/2\), but no finite census controls all later scales, so it is not evidence of the uniformity step in the sense required for a proof. (d for the data; (a) for the logical limitation)

Outcome

There is no construction or counterexample and no claim that the open problem is solved. The verifiable progress is: (i) the exact equivalent monotone-triple cancellation (2)–(3); (ii) a fully reproducible census and sharp discrepancy bounds through \(10^8\); and (iii) an explicit box-swap/all-scales lemma identifying why logarithmic density and almost-all-scales results stop short. (a), (d), and (b)/(c), respectively

PARTIAL: Proved an exact monotone-triple reduction, exhaustively verified all \(n\leq10^8\) with sharp tail discrepancy bounds, and isolated all-scales fixed-shift exchangeability as the missing lemma; the density-\(1/2\) problem remains open.

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