ERDŐS/DAILY ▸

← back to the ledger

ERDőS #950 · PARTIAL

Erdős problem 950 — wave 6s

Access date: 2026-07-27 (UTC)

Claim labels used throughout:

0. Mandatory live-page gate

I fetched both the problem page and its discussion thread through the Bright Data browser, rather than through datacenter curl.

The live page at <https://www.erdosproblems.com/950> said:

Thus the requested collision/claimed-proof stop condition was not triggered.

Verbatim current statement

The following is copied verbatim from the live page's “View the LaTeX source” view:

Let\[f(n) = \sum_{p<n}\frac{1}{n-p}.\]Is it true that\[\liminf f(n)=1\]and\[\limsup f(n)=\infty?\]Is it true that $f(n)=o(\log\log n)$ for all $n$?

Results and comments listed on the live page

The page lists the following as known background.

\[ \sum_{n<x}f(n)\sim\sum_{n<x}f(n)^2\sim x. \] The page links Ofir Gorodetsky's 24 February 2026 MathOverflow answer for a proof of the second assertion. The answer explicitly expands the square, reduces the off-diagonal term by partial fractions, and isolates three prime-sum estimates. It says some partial-summation details in its third lemma are omitted.

\[ \#\bigl(\mathbb P\cap[n,n+n^c]\bigr)\gg n^c/\log n \] for some \(c>0\) implies \(\liminf f(n)>0\).

and all sufficiently large \(x\), some \(y<x\) satisfies \[ \pi(x)<\pi(y)+\epsilon\pi(x-y). \]

\[ \pi(x)<\pi(y)+O\!\left(\frac{x-y}{\log x}\right) \quad \left(y<x-(\log x)^C\right) \] would imply \(f(n)\ll\log\log\log n\).

could not prove \[ \sum_{p<x}f(p)^2\sim\pi(x). \]

The three live comments were also checked.

  1. Terence Tao (25 August 2025) wrote that an upper-bound sieve gives

\(\sum_{n<x}f(n)^2\ll x\), but that he initially saw the asymptotic as requiring prime-number-theorem information in almost all short intervals. He also suggested that a Hardy–Littlewood prime-tuples assumption should give infinite limsup via dense prime clusters. [c] This is a conditional route suggestion, not a claimed proof.

  1. Aron Bhalla (14 April 2026) linked the MathOverflow answer above.
  2. Stijn Cambie (24 August 2025) noted the strict decrease between successive

prime-triggered jumps and suggested \(\sum_{p\le x}f(p+1)^2\sim4\pi(x)\). The comment itself warns that this would not imply infinite limsup. The moment suggestion is [c] and is not used below. The monotonicity is proved from scratch below.

1. Primary-source literature audit

The original source is P. Erdős, Problems and results on combinatorial number theory III, Number Theory Day, Lecture Notes in Mathematics 626 (1977), 43–72, DOI 10.1007/BFb0063064. I checked the primary scan, especially printed pages 62–63. It contains this exact \(f(n)\), the two moments, the positive liminf consequence of Hoheisel's theorem, and all three questions on the live page.

An exact-formula/title search also located a later primary source which the live page does not mention: P. Erdős, Many old and on some new problems of mine in number theory, Congressus Numerantium 30 (1981), 3–27 (primary scan, printed pp. 25–26). Erdős writes that he and Pomerance had “observed” that \(1+1/k\), \(k=1,2,\ldots\), must be limit points of \(f(n)\). No proof is given there and I did not find a proof in the direct searches, so this is recorded only as [c] historical-unverified and is not used as a theorem. The scan is unambiguous: it says \(1+1/k\), not \(1+k\).

For current short-interval input I checked L. Guth and J. Maynard, New large value estimates for Dirichlet polynomials, arXiv:2405.20552v2, revised 7 April

  1. Its Corollary 1.3 says, uniformly for

\(y\in[x^{17/30+\epsilon},x^{0.99}]\),

\[ \pi(x+y)-\pi(x) =\frac{y}{\log x} O_\epsilon\!\left(y\exp\left(-(\log x)^{1/4}\right)\right). \tag{GM} \]

The arXiv ID, authors, revision, exponent, main term, and error term were all checked in the primary HTML/PDF, not inferred from a secondary summary.

For the uniform upper bound below I use the \(q=1\) Brun–Titchmarsh theorem from H. L. Montgomery and R. C. Vaughan, The large sieve, Mathematika 20 (1973), 119–134, DOI 10.1112/S0025579300004708.

Exact searches for the displayed definition, the two limit questions, “\(1+1/k\) limit points”, and the original article title found the sources above but no later paper claiming any of the three questions solved. This is an honest search report, not a claim that no unindexed literature exists.

2. Results obtained

Here is the useful output in compact form.

  1. [a] Exact one-sequence reduction. All three open assertions reduce to

the values \(f(p)\) with \(p\) prime: \[ \liminf_n f(n)=\liminf_{p\to\infty}f(p), \] \[ \limsup_n f(n)=\infty \iff \limsup_{p\to\infty}f(p)=\infty, \] and \[ f(n)=o(\log\log n)\ \text{for all }n \iff f(p)=o(\log\log p)\ \text{through the primes}. \]

  1. [b] Quantitative unconditional lower bound modulo Guth–Maynard (GM):

\[ \boxed{\displaystyle \liminf_{n\to\infty}f(n)\ge\frac{13}{30}.} \] The page only records the qualitative lower bound \(>0\).

  1. [b] Combining that bound with an elementary parity estimate gives

\[ \liminf_{p\to\infty}f(p+1) \ge \frac{13}{30}+\log 2, \] and hence \[ \boxed{\displaystyle \limsup_{n\to\infty}f(n) \ge\frac{13}{30}+\log2 =1.126480\ldots .} \] This of course does not prove that the limsup is infinite.

  1. [b] Rigorous baseline modulo Brun–Titchmarsh:

\[ f(n)\le 2\log\log n+O(1) \] uniformly. The exact missing improvement is a logarithmic-scale average local-density lemma stated in Section 5.

  1. [d] Exact finite theorem. For every integer

\(3\le n\le2{,}000{,}000\), the unique minimum is at \(n=223\), and the unique maximum is at \(n=1{,}954{,}370\). This was certified by an exact integer convolution, not a floating-point FFT.

The known two moments give

\[ \frac1x\sum_{n<x}(f(n)-1)^2\longrightarrow0. \]

Therefore [b] \(\liminf f(n)\le1\). Combining this with item 2 narrows the first question to

\[ \boxed{\displaystyle \frac{13}{30}\le\liminf f(n)\le1.} \]

3. Elementary sawtooth structure and exact reduction

For every \(n\ge3\), direct subtraction gives

\[ \begin{aligned} f(n+1)-f(n) &=\mathbf 1_{\mathbb P}(n) +\sum_{p<n}\left(\frac1{n+1-p}-\frac1{n-p}\right)\\ &=\mathbf 1_{\mathbb P}(n) -\sum_{p<n}\frac1{(n-p)(n+1-p)}. \tag{1} \end{aligned} \]

This is [a].

If \(n\) is composite, (1) is strictly negative. If \(n\) is prime, then

\[ \sum_{p<n}\frac1{(n-p)(n+1-p)} < \sum_{d\ge1}\frac1{d(d+1)} =1, \]

so (1) is strictly positive. Thus, if \(p_j<p_{j+1}\) are consecutive primes,

\[ f(p_j+1)>f(p_j+2)>\cdots>f(p_{j+1}). \tag{2} \]

Write

\[ \delta_p=f(p+1)-f(p) =1-\sum_{q<p}\frac1{(p-q)(p+1-q)} \qquad(p\ \text{prime}). \]

The preceding argument gives \(0<\delta_p<1\). For an odd prime \(p\), all differences \(p-q\) with odd \(q\) are even, while \(q=2\) contributes separately. Hence [a]

\[ \begin{aligned} \sum_{q<p}\frac1{(p-q)(p+1-q)} &\le \frac1{(p-2)(p-1)} +\sum_{k\ge1}\frac1{2k(2k+1)}\\ &=\frac1{(p-2)(p-1)}+1-\log2, \end{aligned} \]

and therefore

\[ \boxed{\displaystyle \log2-\frac1{(p-2)(p-1)} \le\delta_p<1.} \tag{3} \]

Now take any \(n\) with

\[ p_j<n\le p_{j+1}. \]

Equation (2) and \(0<\delta_{p_j}<1\) give

\[ f(p_{j+1})\le f(n)\le f(p_j+1)<f(p_j)+1. \tag{4} \]

The lower half of (4), together with the prime subsequence itself, proves

\[ \liminf_n f(n)=\liminf_p f(p). \]

The upper half proves that \(f(n)\) is unbounded exactly when \(f(p)\) is unbounded. Finally, if \(f(p)=o(\log\log p)\), (4) gives the same estimate for all \(n\). Bertrand's theorem gives \(p_j>n/2\), so \(\log\log p_j\sim\log\log n\). The converse follows by restriction to the prime subsequence. This proves all three reductions in Section 2, item 1.

One useful consequence of (3) is

\[ \liminf_p f(p+1) \ge \liminf_p f(p)+\log2. \tag{5} \]

4. The \(13/30\) lower bound

Define the backward short-interval count

\[ A_n(t)=\#\{p<n:n-p\le t\}. \]

Stieltjes partial summation over the distances \(d=n-p\) gives the exact identity [a]

\[ f(n)=\frac{A_n(n-2)}{n-2} +\int_1^{n-2}\frac{A_n(t)}{t^2}\,dt. \tag{6} \]

Fix a small \(\epsilon>0\), and put

\[ \alpha=\frac{17}{30}+2\epsilon. \]

I now derive from (GM) the uniform estimate

\[ A_n(t)=(1+o(1))\frac{t}{\log n} \quad \left(n^\alpha\le t\le\frac n2\right). \tag{7} \]

This step is [b], rigorous modulo Guth–Maynard Corollary 1.3.

For \(t\le n^{0.98}\), apply (GM) directly with \(x=n-t\) and \(y=t\). Here \(x\asymp n\), the lower exponent has \(\epsilon\) of slack, and \(t\le x^{0.99}\) for large \(n\). Including or excluding a possible prime at the right endpoint changes the count by at most one, which is \(o(t/\log n)\).

For \(n^{0.98}<t\le n/2\), subdivide \((n-t,n]\) into intervals of length

\[ \ell=\frac{n^{0.98}}{(\log n)^2}. \]

Every full block lies in \([n/2,n]\), and (GM) applies to it uniformly. Summing the block estimates gives the expected count; the remaining block has length \(<\ell=o(t/\log n)\). This proves (7).

All terms in (6) are nonnegative, so (7) gives

\[ \begin{aligned} f(n) &\ge \int_{n^\alpha}^{n/2}\frac{A_n(t)}{t^2}\,dt\\ &=(1+o(1))\frac1{\log n} \int_{n^\alpha}^{n/2}\frac{dt}{t}\\ &=1-\alpha+o(1). \end{aligned} \]

Thus

\[ \liminf f(n)\ge1-\frac{17}{30}-2\epsilon. \]

Letting \(\epsilon\downarrow0\) proves [b]

\[ \liminf f(n)\ge\frac{13}{30}. \]

The verifier independently checks the exact arithmetic \(1-17/30=13/30\).

Equation (5) then proves [b]

\[ \liminf_p f(p+1)\ge\frac{13}{30}+\log2, \]

which yields the stated lower bound for the global limsup.

5. Exact analytic wall for the little-\(o\) question

Brun–Titchmarsh gives, uniformly in the interval's position,

\[ A_n(t)\le \frac{2t}{\log t}+O(1) \qquad(t\ge2). \tag{8} \]

Inserting (8) into (6) proves [b]

\[ f(n)\le 2\int_2^n\frac{dt}{t\log t}+O(1) =2\log\log n+O(1). \tag{9} \]

Define the dimensionless local-density ratio

\[ R_n(t)=\frac{A_n(t)\log t}{t}. \]

Then the integral in (6) is exactly

\[ \int_2^{n-2}\frac{A_n(t)}{t^2}\,dt = \int_2^{n-2}R_n(t)\,d(\log\log t). \tag{10} \]

The boundary term \(A_n(n-2)/(n-2)\) is at most \(1\). Consequently, [a] the third question is equivalent to the assertion that the \(d(\log\log t)\)-average of \(R_n(t)\) is \(o(1)\), uniformly as the endpoint \(n\) varies:

\[ \boxed{\displaystyle \int_2^{n-2}\frac{A_n(t)}{t^2}\,dt =o(\log\log n).} \tag{11} \]

For every fixed \(\eta>0\), Brun–Titchmarsh already gives

\[ \int_{n^\eta}^{n-2}\frac{A_n(t)}{t^2}\,dt=O_\eta(1). \]

Thus the whole possible \(\log\log n\) loss is concentrated in the nested short intervals

\[ 2\le t\le n^\eta \]

for arbitrarily small fixed \(\eta\). Existing uniform sieve theory only bounds \(R_n(t)\) by approximately \(2\) there; it does not show that its logarithmic-scale average tends to zero. This is the precise missing lemma, not merely “better prime distribution”.

The same calculation explains the first-question wall. A prime number theorem in every interval of length \(n^\eta\), for every fixed \(\eta>0\), would let the proof in Section 4 send \(\alpha\downarrow0\), yielding \(\liminf f(n)\ge1\); the known moments would then force equality. The current uniform exponent \(17/30\) stops this route at \(13/30\).

For infinite limsup, Section 3 shows that the exact missing assertion is

\[ \sup_{p\in\mathbb P}f(p)=\infty. \]

The all-integer moments do not control this zero-density subsequence, and the live page notes that even the prime-restricted second moment remains unknown. This identifies the required new input as weighted prime-pair (and likely higher prime-tuple) control with a prime endpoint. [c] Merely finding more finite records cannot provide the needed uniformity.

6. Exact computation through two million

The complete standalone checker is runs/erdos950_wave6s_verify.py (465 lines, SHA-256 4c8550bdb306d85dee4f721b9c7f2c20d8c11a0eb4341a34fa90e526a07d80f2). It uses only Python's standard library plus the system C++17 compiler.

For \(Q=10^{12}\), define

\[ L(n)=\sum_{p<n}\left\lfloor\frac{Q}{n-p}\right\rfloor. \]

Then, with \(k_n=\pi(n-1)\),

\[ \frac{L(n)}Q\le f(n)<\frac{L(n)+k_n}Q. \tag{12} \]

Both endpoints of (12) are integers divided by \(Q\).

The checker computes all \(L(n)\) simultaneously as the exact convolution of

\[ a_p=\mathbf1_{\mathbb P}(p), \qquad b_d=\left\lfloor\frac Qd\right\rfloor. \]

It performs the convolution modulo

\[ M=20000010141697, \qquad M-1=2^{23}\cdot3\cdot13\cdot113\cdot541, \]

with primitive root \(7\). There is no modular wrap because every convolution coefficient is less than

\[ QH_{2,000,000}<Q(1+\log 2,000,000)<M. \]

For each cutoff, the program proves uniqueness by the integer inequalities

\[ L(n_{\min})+k_{n_{\min}} \le\min_{m\ne n_{\min}}L(m) \]

and

\[ L(n_{\max}) \ge\max_{m\ne n_{\max}}\bigl(L(m)+k_m\bigr). \]

Because the upper endpoint in (12) is strict, these certify strict extrema.

The implementation independently:

\(\pi(2,000,000)=148,933\);

Certified table

Every row below is [d] computational-only, but the computation and comparisons are exact. Intervals are of the form \([L/Q,(L+k)/Q)\).

Range \(3\le n\le X\)unique minimizercertified \(f(n)\) intervalunique maximizercertified \(f(n)\) interval
\(10\)\(10\)\([0.801190476190,0.801190476194)\)\(8\)\([1.699999999999,1.700000000003)\)
\(100\)\(29\)\([0.630675343172,0.630675343181)\)\(74\)\([1.984493964605,1.984493964626)\)
\(1,000\)\(223\)\([0.601780537782,0.601780537829)\)\(830\)\([2.192177475186,2.192177475331)\)
\(10,000\)\(223\)\([0.601780537782,0.601780537829)\)\(9,440\)\([2.373996178856,2.373996180026)\)
\(100,000\)\(223\)\([0.601780537782,0.601780537829)\)\(88,820\)\([2.467051824599,2.467051833204)\)
\(1,000,000\)\(223\)\([0.601780537782,0.601780537829)\)\(855,740\)\([2.559292259642,2.559292327674)\)
\(2,000,000\)\(223\)\([0.601780537782,0.601780537829)\)\(1,954,370\)\([2.568366752345,2.568366898154)\)

The exact minimum value is [d]

\[ f(223)= \frac{8023008785848155555574799200811} {13332117411344755653574470926400} =0.601780537802727\ldots. \]

The maximizer has the predicted form \(1,954,370=1,954,369+1\), where \(1,954,369\) is prime.

Run:

python runs/erdos950_wave6s_verify.py

On this VM the full clean run took about 10 seconds. It ended with:

PASS exact_integer_ntt N=2000000 piN=148933 Q=1000000000000 MOD=20000010141697 length=4194304
PASS exact_sawtooth_identities n<=500
PASS exponent_arithmetic 1-17/30=13/30
PASS wrapper_expected_rows

Why not spend the budget on a much larger scan?

[c] Cost estimate. Extending the same exact method to \(10^8\) would require transform length \(2^{28}\), a different high-2-adicity modulus, roughly 5 GB of working memory, and roughly \(1.1\times10^{10}\) modular butterflies (on the order of 1–5 core-hours in a careful C++ implementation). It would produce a larger record table but would not address any of the three uniform asymptotic gaps isolated in Section 5, so I did not run it.

PARTIAL: modulo Guth–Maynard, \(13/30\le\liminf f\le1\) and \(\limsup f\ge13/30+\log2\); all three questions reduce exactly to \(f(p)\), and exact integer computation certifies the unique extrema through \(2{,}000{,}000\), but the original assertions remain open.

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