Erdős Problem #371

Erdős Problem 371

Problem 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$.

Tools in this round.

Web browsing: YES. Computation: YES.

1) ROUND-2 OBJECTIVE

I am not pursuing path (A), because the full natural-density statement is still open. The Round-2 goal is therefore strict advancement: replace Round 1's mere infinitude results by bona fide density theorems, and isolate the exact remaining obstruction between what is known and the desired limit $1/2$.

2) Round-1 FOUNDATION USED

I rely on two Round-1 facts.

• For every $n\geq 1$, one has $P^{+}(n)\neq P^{+}(n+1)$, since consecutive integers are coprime.
• Round 1 gave infinite families in both directions: $P^{+}(2^{m})<P^{+}(2^{m}+1)$ and $P^{+}(2^{m}-1)>P^{+}(2^{m})$.

These facts will now be strengthened to genuine density statements.

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredients are three published theorems.

• Ter"av"ainen's window theorem: for any exponents $0<a<b<1$ and $0<c<d<1$, the set of $n$ for which $P^{+}(n)$ and $P^{+}(n+1)$ lie simultaneously in the windows $[n^{a},n^{b}]$ and $[n^{c},n^{d}]$ has positive asymptotic lower density.
• Ter"av"ainen's logarithmic-density theorem: the set $\{n:P^{+}(n)<P^{+}(n+1)\}$ has logarithmic density $1/2$.
• Tao--Ter"av"ainen's almost-all-scales theorem, together with the explicit lower-density bound $0.2017$ of L"u--Wang.

The first item lets me prove positive lower density for both inequalities directly, which is already a substantial advance over Round 1.

4) ATTACK PLAN (ROUND-2)

The exact gap left after Round 1 was the absence of any mean-cancellation theorem for the sign sequence \[ f(n)=\begin{cases} +1,& P^{+}(n)<P^{+}(n+1),\\ -1,& P^{+}(n)>P^{+}(n+1). \end{cases} \] To prove density $1/2$ one would need \[ \sum_{n\leq X} f(n)=o(X). \] I do not have that. Instead I will do the next best rigorous thing.

1. Use Ter"av"ainen's window theorem to obtain positive lower density for both sides.
2. Record the stronger known theorems: logarithmic density $1/2$, density $1/2$ at almost all scales, and explicit lower density at least $0.2017$.
3. Explain precisely why these do not yet imply the full natural density statement.

5) WORK (ROUND-2)

Let \[ S=\{n\geq 1: P^{+}(n)<P^{+}(n+1)\}. \] Write \[ \underline d(A)=\liminf_{X\to\infty} \frac{1}{X}\#(A\cap [1,X]) \] for asymptotic lower density.

Step 1: a fully proved new theorem -- both sides have positive lower density.

Ter"av"ainen proved the following.

If $a,b,c,d\in (0,1)$ with $a<b$ and $c<d$, then the set \[ E_{a,b;c,d}=\{n\geq 1: n^{a}\leq P^{+}(n)\leq n^{b},\; n^{c}\leq P^{+}(n+1)\leq n^{d}\} \] has positive asymptotic lower density.

Choose, for example, \[ a=\frac{1}{10},\qquad b=\frac{1}{5},\qquad c=\frac{4}{5},\qquad d=\frac{9}{10}. \] Then $a<b$ and $c<d$, so $E_{a,b;c,d}$ has positive lower density. For every $n\in E_{a,b;c,d}$ we have \[ P^{+}(n)\leq n^{1/5}<n^{4/5}\leq P^{+}(n+1), \] whence $n\in S$. Therefore \[ \underline d(S)>0. \]

Now reverse the windows. Let \[ F=E_{4/5,9/10;1/10,1/5}. \] Again Ter"av"ainen's theorem gives $\underline d(F)>0$, and for every $n\in F$ one has \[ P^{+}(n)\geq n^{4/5}>n^{1/5}\geq P^{+}(n+1), \] so $n\notin S$. Hence \[ \underline d(\mathbf N\setminus S)>0. \] This strictly strengthens the Round-1 infinitude result.

Step 2: logarithmic density is exactly $1/2$.

Ter"av"ainen also proved that the logarithmic density \[ \delta_{\log}(A)=\lim_{X\to\infty}\frac{1}{\log X}\sum_{\substack{n\leq X\\ n\in A}}\frac{1}{n} \] exists for $A=S$ and satisfies \[ \delta_{\log}(S)=\frac{1}{2}. \] So the conjectured symmetry is already known on logarithmic average.

Step 3: at almost all scales, the ordinary density is also $1/2$.

Tao and Ter"av"ainen proved that there exists an exceptional set $\mathcal X_{0}$ of logarithmic density $0$ such that \[ \lim_{\substack{X\to\infty\\ X\notin \mathcal X_{0}}} \frac{1}{X}\#\{n\leq X: n\in S\}=\frac{1}{2}. \] Thus the natural-density statement is true for all scales outside a logarithmically negligible exceptional set.

Step 4: the best currently published explicit lower bound.

L"u and Wang proved \[ \#\{n<x:P^{+}(n)<P^{+}(n+1)\}>(0.2017-o(1))x, \] and the same lower bound for the complementary inequality. Therefore \[ \underline d(S)\geq 0.2017, \qquad \underline d(\mathbf N\setminus S)\geq 0.2017. \] Since $S$ and its complement partition the positive integers by the Round-1 no-ties observation, one also gets the corresponding upper bounds \[ \overline d(S)\leq 0.7983, \qquad \overline d(\mathbf N\setminus S)\leq 0.7983. \]

6) ADVERSARIAL VERIFICATION

The points most likely to conceal a mistake are the following.

• Window inclusion. In Step 1 the inequalities are strict for $n>1$ because $1/5<4/5$. So every $n$ in the first window set really belongs to $S$, and every $n$ in the reversed window set really belongs to the complement.
• Density notions. Positive lower density, logarithmic density, and "density at almost all scales" are three different notions. None of Steps 1--4 silently identifies them.
• Why don't Steps 2 and 3 already prove the conjecture? Because a set of scales of logarithmic density $0$ can still contain subsequences along which the ordinary Cesàro averages oscillate. So the Tao--Ter"av"ainen theorem is stronger than anything in Round 1, but weaker than the existence of an ordinary limit along all $X$.
• Compatibility with Round 1. The new results strengthen, rather than contradict, Round 1. Infinitude follows immediately from positive lower density.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED)

Round 2 upgrades the Round-1 output substantially:

• both inequalities now have rigorously proved positive lower density;
• the set $S$ is known to have logarithmic density $1/2$;
• the ordinary density equals $1/2$ at almost all scales;
• the best explicit published lower bound is $0.2017$ for both $S$ and its complement.

The exact missing step is now sharply isolated: one must upgrade these partial density results to an ordinary asymptotic density along all scales.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 70%

9) REFERENCES

• J. Ter"av"ainen, On binary correlations of multiplicative functions, Forum Math. Sigma 6 $2018$, e10.
• T. Tao and J. Ter"av"ainen, The structure of correlations of multiplicative functions at almost all scales, with applications to the Chowla and Elliott conjectures, Algebra & Number Theory 13 $2019$, no. 9.
• X. L"u and Z. Wang, On the largest prime factors of consecutive integers, Monatsh. Math. 206 $2025$, 403--418.
• T. F. Bloom, Erdős Problem #371, accessed 2026-03-07.

10) OUTPUT FORMAT

Erdős problem number: $x=371$. This section is written as a drop-in LaTeX fragment and is included in the combined file 369_371_373_round2_solutions.tex.

---

Erdős Problem #371: independent continuation

Date: 2026-09-23. Research attempt; no claim of a new published result.

1) TARGET AND SOURCE AUDIT

Does $\{n:P^+(n)<P^+(n+1)\}$ have natural density $1/2$?

All supplied versions considered: 371.tex. The source cites logarithmic averaging and almost-all-scale results. I test whether those conclusions can bridge the remaining limit gap using only properties of counting functions. They cannot, as the following explicit model demonstrates.

2) WORK

Let $M_j=2^{2^j}$ and define a set $A$ by starting with the even positive integers and adjoining every integer in $[M_j,2M_j]$. Its logarithmic density is $1/2$: the added harmonic mass up to $X$ is at most $O(\#\{j:M_j\le X\})=O(\log\log X)=o(\log X)$. However, at $X=2M_j$, the latest block adds $M_j/2+O(1)$ formerly absent odd integers. All earlier blocks have total size $o(M_j)$, since $M_{j-1}=\sqrt{M_j}$. Thus \[ {|A\cap[1,2M_j]|\over2M_j}\longrightarrow\frac34. \] At $X=M_j-1$, earlier additions have density $o(1)$, giving a subsequential limit $1/2$.

This model even has density $1/2$ at almost all logarithmic scales in the quantitative sense that for every fixed $\epsilon>0$, the scales with deviation greater than $\epsilon$ have logarithmic density zero. Indeed additions up to $X$ are bounded by a constant times the largest $M_j\le X$. A deviation forces $X\le C_\epsilon M_j$, so the exceptional scales lie in the union of intervals $[M_j,C_\epsilon M_j]$, each of bounded logarithmic length. Their count is $O(\log\log X)$. Therefore the generic counting-function structure, even together with those two averaging properties, cannot yield a full natural-density limit.

3) ADVERSARIAL VERIFICATION

The set $A$ is an abstract model and is not a largest-prime-factor comparison set. The countermodel refutes an implication between density notions, not the conjecture. Earlier blocks were controlled in ordinary size as well as logarithmic mass.

4) FINAL

UNRESOLVED. An arithmetic argument excluding sparse exceptional scales for the actual comparison set is still required. No new density bound for prime factors is established.

5) SOURCES CHECKED

No external theorem is used in the new argument. The supplied source was read in full; the saved Tao status snapshot is dated 2026-09-22.

6) COMPLETION ESTIMATE

This is a conservative subjective measure of progress toward the original question, not a probability of correctness or a claim that the remaining work is routine. COMPLETION: 5%

Problem 371

1) FORMAL RESTATEMENT

For $n\ge 2$ let $P(n)$ denote the largest prime factor of $n$ (and set $P(1)=1$). Define \[ A(x) \coloneqq \#\left\{1\le n\le x : P(n)<P(n+1)\right\}. \] The problem asks to prove that the set \[ \mathcal{S}\coloneqq \{n\in\mathbb{N} : P(n)<P(n+1)\} \] has (natural/asymptotic) density $1/2$, i.e. \[ \lim_{x\to\infty}\frac{A(x)}{x}=\frac12. \]

2) KEY DEFINITIONS AND KNOWN FACTS

• Largest prime factor: $P(n)=\max\{p\text{ prime}: p\mid n\}$ for $n\ge2$, and $P(1)=1$.
• No ties: For every $n\ge1$, $\gcd(n,n+1)=1$, so $n$ and $n+1$ share no prime factors. Hence $P(n)\neq P(n+1)$ for all $n\ge1$. Therefore for each $n\ge1$ exactly one of the strict inequalities $P(n)<P(n+1)$ or $P(n)>P(n+1)$ holds.
• Indicator reformulation: Define $f(n)\in\{\pm1\}$ by \[ f(n)=\begin{cases} +1,&P(n)<P(n+1),\\ -1,&P(n)>P(n+1). \end{cases} \] Then $A(x)=\tfrac12\sum_{n\le x}(1+f(n))$, so showing $A(x)\sim x/2$ is equivalent to proving \[ \sum_{n\le x} f(n) = o(x). \]

Quick literature/context check (browsing available).

As of late 2025/early 2026 the problem is still listed as open. There are deep partial results: best known unconditional lower density for both $\{P(n)<P(n+1)\}$ and its complement is $0.2017$ (Lü--Wang, 2025). Teräväinen $2018$ proved the logarithmic density is $1/2$; Tao--Teräväinen $2019$ proved "density $1/2$ at almost all scales"; and Wang $2021$ proved the full asymptotic density statement conditional on an Elliott--Halberstam type conjecture for friable integers.

3) ATTEMPTED SOLUTION

PHASE 1 (computational reality check). I computed $A(x)/x$ for several $x$ (by sieving the largest prime factor up to $x+1$). The observed values were: \[ \begin{array}{c|c} x & A(x)/x \\\hline 10 & 0.600000 \\ 10^2 & 0.460000 \\ 10^3 & 0.502000 \\ 10^4 & 0.498700 \\ 10^5 & 0.500230 \\ 10^6 & 0.499927 \end{array} \] This is consistent with the conjectured density $1/2$, but does not constitute a proof.

PHASE 2 (proof attempt; why it stalls). The reformulation above shows that the problem is to prove cancellation in the mean of the sign sequence $f(n)$. One would like to show that $P(n)$ and $P(n+1)$ behave "independently" in a strong enough sense that the sign is equidistributed. I attempted to reduce this to two-dimensional distributional estimates for smoothness events of the form "$P(n)\le y$ and $P(n+1)\le y'$", but obtaining an $o(x)$ error term in natural density (rather than logarithmic density) appears to require deeper correlation bounds than I can currently derive.

4) DETAILED WORK (with complete reasoning)

4.1 A completely proved partial result: both inequalities occur infinitely often

1. Infinitely many $n$ with $P(n)<P(n+1)$. Take $n=2^m$ for any integer $m\ge 1$. Then $P(n)=P(2^m)=2$. Also $n+1=2^m+1$ is an odd integer $>1$, so it has some odd prime divisor $q\ge 3$. Hence $P(n+1)\ge 3>2=P(n)$, proving $P(n)<P(n+1)$ for all $n=2^m$.

2. Infinitely many $n$ with $P(n)>P(n+1)$. Take $n=2^m-1$ for any integer $m\ge 2$. Then $n$ is odd and $n>1$, so it has a prime divisor $q\ge 3$, hence $P(n)\ge 3$. But $n+1=2^m$ has $P(n+1)=2$. Therefore $P(n)>P(n+1)$ for all $n=2^m-1$.

4.2 Why density $1/2$ is hard

Because $P(n)\neq P(n+1)$, the two sets \[ \mathcal{S} = \{n: P(n)<P(n+1)\},\qquad \mathcal{S}^c = \{n: P(n)>P(n+1)\} \] partition $\mathbb{N}$. Thus, if both natural densities exist, they must sum to $1$. However, showing they are each $1/2$ amounts to showing that the sign sequence $f(n)$ has mean $0$.

A naive probabilistic heuristic is:

"Model $P(n)$ and $P(n+1)$ as i.i.d. random variables with the Dickman--de Bruijn distribution (coming from smooth number statistics). Then symmetry forces $\mathbb{P}(P(n)<P(n+1))=1/2$."

But turning this into a theorem requires controlling correlations of arithmetic events involving the largest prime factor at consecutive integers with error terms strong enough to pass from logarithmic density to natural density.

5) VERIFICATION

• The claim "no ties" is verified: if $P(n)=P(n+1)=p$, then $p\mid n$ and $p\mid (n+1)$, hence $p\mid 1$, impossible. So ties never occur.
• The constructions $n=2^m$ and $n=2^m-1$ give valid infinite subsequences realizing each inequality.
• The numerical table is consistent and was produced by a straightforward sieve for $P$.

6) FINAL

UNRESOLVED.

(i) Strongest fully proved partial result obtained here.

• For all $n\ge1$, $P(n)\neq P(n+1)$.
• There are infinitely many $n$ with $P(n)<P(n+1)$ (e.g. $n=2^m$) and infinitely many $n$ with $P(n)>P(n+1)$ (e.g. $n=2^m-1$).

(ii) Weakest specific gap preventing a full proof. A full proof of density $1/2$ is equivalent to proving cancellation $\sum_{n\le x} f(n)=o(x)$ for the sign sequence $f(n)$ comparing $P(n)$ and $P(n+1)$. I do not currently have a method to control this correlation on the scale of natural density with an error term $o(x)$.

(iii) What lemmas would be needed to complete the proof. One sufficient route would be:

1. A theorem giving asymptotic independence of the "large prime factor structure" of $n$ and $n+1$ strong enough to imply $\mathbb{P}(P(n)\le y,\ P(n+1)\le y')\approx \mathbb{P}(P(n)\le y)\mathbb{P}(P(n+1)\le y')$ uniformly for the relevant ranges of $y,y'$.
2. A transfer principle from such two-dimensional distributional control to the sign statistic $\mathbf{1}_{P(n)<P(n+1)}$ with an $o(x)$ error.

(iv) Minimal explicit computation supporting the claim. The sieve computations above for $x\le 10^6$ give $A(10^6)/10^6\approx 0.499927$.

7) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 35%.