ERDŐS/DAILY ▸

← back to the ledger

ERDőS #726 · PARTIAL

Erdős problem #726 — reciprocal mass of upper-half residues

Outcome

PARTIAL, not a solution. The live page passed the mandatory collision gate. The principal mathematical result of this run is a complete deduction, from a published equidistribution theorem, of

\[ \boxed{\frac16\leq \liminf_{n\to\infty}\frac{S(n)}{\log\log n} \leq \limsup_{n\to\infty}\frac{S(n)}{\log\log n} \leq\frac56}, \qquad S(n):=\sum_{\substack{p\leq n\\2(n\bmod p)>p}}\frac1p. \]

This is rigorous modulo Proposition 1.13 of Matomäki–Radziwiłł–Shao–Tao–Teräväinen (Proposition 1.12 in the arXiv version), not a new unconditional proof of the conjecture. It turns the back-of-the-envelope \(1/6,5/6\) observation in a page comment into a detailed smoothing and partial-summation argument.

The second output is an exhaustive, rationally enclosed computation for every \(100\leq n\leq10^7\), with a standalone from-scratch checker: erdos726_wavew012_reverify.py.

Claim labels used below

program results).

1. Mandatory live-page audit

[d] I accessed the live page through the Bright Data browser path on 2026-07-28. It displayed:

Therefore the mandatory skip condition did not fire.

[d] Verbatim current statement (from “View the LaTeX source”):

As $n\to \infty$ ranges over integers\[\sum_{p\leq n}1_{n\in (p/2,p)\pmod{p}}\frac{1}{p}\sim \frac{\log\log n}{2}.\]

[d] Verbatim supporting text and cited comparison:

A conjecture of Erd\H{o}s, Graham, Ruzsa, and Straus \cite{EGRS75}. For comparison the classical estimate of Mertens states that\[\sum_{p\leq n}\frac{1}{p}\sim \log\log n.\]By $n\in (p/2,p)\pmod{p}$ we mean $n\equiv r\pmod{p}$ for some integer $r$ with $p/2<r<p$.

[d] The page also displayed “Formalised statement? Yes,” “Likes this problem: ebarschkis,” “This problem looks difficult: ebarschkis, Dogmachine,” and None for the tractable, formalisable-result, and working-on-formalisation markers.

All six live comments

The page itself warns that comments are not verified. Accordingly, the items in this subsection are labelled [c] unless independently established later.

  1. [c] msawhney, 2025-08-31 18:31. Suggested Fourier expansion and the

reciprocal-phase prime sum \(\sum e(n/p)/p\). Bilinear decomposition leads to sums \(\sum e(n/(ab))\) at subpolynomial scales that appear beyond standard methods; restricting to sufficiently large primes might still yield positive-fraction lower and upper bounds.

  1. [c] TerenceTao, 2025-08-31 19:14. Linked Proposition 1.12 of

arXiv:2106.03335 and suggested it should handle \(p\geq\exp((\log n)^{2/3+\varepsilon})\), giving constants \(1/6\) and \(5/6\). Section 4 below verifies this deduction.

  1. [c] msawhney, 2025-09-04 00:02. Observed that the remaining

exponential-sum issue appears related to the zeta zero-free region, while an average-in-\(n\) result is substantially easier.

  1. [c] jleng01, 2025-09-08 17:40. Noted the floor-function rewriting of

the residue indicator. Section 2 proves the identity, including its exceptional \(p=2\) case.

  1. [c] TerenceTao, 2025-10-23 19:40. Suggested the motivation from

binomial coefficients and Kummer's theorem: the displayed indicator is the first prime-power carry contributing to \(v_p\binom{2n}{n}\).

  1. [c] Steve Fan, 2026-07-18 19:33. Claimed the mean-square estimate

\[ \frac1x\sum_{1<n\leq x} \left(S(n)-\frac12\log\log n\right)^2=O(1), \]

hence the conjectured asymptotic for almost all \(n\). This comment did not provide a proof or literature citation, so this report does not use it as a theorem.

2. Elementary exact formulations

Put

\[ g(x):=1_{\{\{x\}\in(1/2,1)\}}. \]

[a] For every odd prime \(p\),

\[ g(n/p) = \left\lfloor\frac{2n}{p}\right\rfloor -2\left\lfloor\frac np\right\rfloor. \tag{2.1} \]

Indeed, writing \(n=qp+r\) with \(0\leq r<p\), the right side is \(\lfloor2r/p\rfloor\), which is one exactly when \(2r>p\). For \(p=2\), the strict interval \((p/2,p)\) contains no integer residue, whereas the floor expression is \(n\bmod2\); thus \(p=2\) is the sole exception.

[a] If \(q=\lfloor n/p\rfloor\geq1\), the same condition is

\[ \frac{n}{q+1}<p<\frac{2n}{2q+1}. \tag{2.2} \]

This follows without real-number rounding: the two inequalities are \(p(q+1)>n\) and \(p(2q+1)<2n\), and the second is exactly \(p<2r\). Consequently the selected primes are partitioned by disjoint quotient intervals. Both (2.1) and (2.2) are exhaustively checked for all applicable \((n,p)\) with \(n\leq2000\) by the verifier.

Define also

\[ H(n):=\sum_{p\leq n}\frac1p,\qquad R(n):=\frac{2S(n)}{H(n)}. \]

[b] Mertens' estimate, as cited on the problem page, makes the original conjecture equivalent to \(R(n)\to1\). This normalization is preferable for finite exact computation because both numerator and denominator are rational prime-reciprocal sums.

3. Primary-source literature check

[d] Exact-title, exact-formula, and citation searches located the following primary sources. I opened the papers themselves and checked the statements quoted here.

  1. [d] P. Erdős, R. L. Graham, I. Z. Ruzsa, and E. G. Straus,

“On the Prime Factors of \(\binom{2n}{n}\)”, Math. Comp. 29 (1975), 83–92, DOI 10.1090/S0025-5718-1975-0369288-3. On page 90 they state exactly the conjecture now recorded as #726.

  1. [b] J. W. Sander,

“On a Sum over Primes”, Hardy–Ramanujan Journal 17 (1994), 32–39, DOI 10.46298/HRJ.1994.129, proved, for every \(\delta>0\),

\[ \sum_{p\leq n}^{*}\frac{\log p}{p} =\frac12\log n+ O_\delta\!\left((\log n)^{5/6+\delta}\right), \tag{3.1} \]

where the star is precisely the upper-half residue restriction. This is a log-weighted analogue, not #726. Sander's final remarks explicitly explain why the method does not control the unweighted contribution of primes below \(\exp((\log n)^{2/3})\).

  1. [b] K. Matomäki, M. Radziwiłł, X. Shao, T. Tao, and J. Teräväinen,

“Singmaster's Conjecture in the Interior of Pascal's Triangle”, Quart. J. Math. 73 (2022), 1137–1177, arXiv:2106.03335. Proposition 1.13 in the published paper (1.12 in arXiv v1) gives, for \(I\subset[P,2P]\),

\[ \sum_{p\in I}e\!\left(\frac Np+\frac{M}{p^j}\right) = \int_I e\!\left(\frac Nt+\frac{M}{t^j}\right)\frac{dt}{\log t} +O_{\varepsilon,A}(P\log^{-A}P) \tag{3.2} \]

when \(M,N=O(\exp((\log P)^{3/2-\varepsilon}))\), together with its smooth periodic-function version. The authors explicitly state that they do not know how to relax this size restriction even under the Riemann hypothesis.

[d] The searches found no primary source claiming the full unweighted asymptotic. This is a report of the searches performed, not a proof that no such paper exists.

4. A rigorous \(1/6\)–\(5/6\) partial theorem

The large-prime asymptotic

[b] Proposition. Fix \(2/3<\alpha<1\), let \(L=\log n\), and put

\[ Y=\exp(L^\alpha). \]

Then

\[ \sum_{Y<p\leq n}\frac{g(n/p)}p = \left(\frac{1-\alpha}{2}+o(1)\right)\log\log n. \tag{4.1} \]

Here and throughout this section, [b] means rigorous modulo the published equidistribution estimate (3.2).

Proof

[a] Choose \(\varepsilon_0>0\) so small that

\[ \alpha(3/2-\varepsilon_0)>1. \tag{4.2} \]

For every \(P\geq Y\),

\[ \exp((\log P)^{3/2-\varepsilon_0}) \geq \exp(L^{\alpha(3/2-\varepsilon_0)}) \gg n. \]

Thus the hypothesis of Proposition 1.13 applies with \(N=n\), \(M=0\) on every dyadic prime block above \(Y\).

[a] For \(\eta=L^{-1}\), choose smooth one-periodic functions \(W^-_\eta\leq g\leq W^+_\eta\) with

\[ \int_0^1W^\pm_\eta(u)\,du=\frac12+O(\eta), \qquad \|W^\pm_\eta\|_{C^3}\ll\eta^{-3}. \tag{4.3} \]

They are obtained by smoothing the two jump points over intervals of total length \(O(\eta)\). The strict midpoint causes no issue for odd \(p\).

[b] Apply the smooth version of Proposition 1.13 to every prefix of a dyadic block and then Abel-sum the weight \(1/p\). On one block \(I\subset[P,2P]\), this gives

\[ \sum_{p\in I}\frac{W^\pm_\eta(n/p)}p = \int_I W^\pm_\eta(n/t)\frac{dt}{t\log t} +O_{\varepsilon_0,A}\! \left(\eta^{-3}(\log P)^{-A}\right). \tag{4.4} \]

There are \(O(L)\) dyadic blocks. Since \(\log P\geq L^\alpha\), their total error is

\[ O(L\cdot L^3\cdot L^{-\alpha A})=o(1) \tag{4.5} \]

after choosing \(A>4/\alpha\).

[a] It remains to evaluate the continuous integral. For any one-periodic \(W\) of mean \(\mu\), the substitution \(u=n/t\) gives

\[ \int_Y^n W(n/t)\frac{dt}{t\log t} = \int_1^{n/Y}\frac{W(u)}{u(L-\log u)}\,du. \tag{4.6} \]

The primitive of \(W-\mu\) is bounded. The weight \(1/(u(L-\log u))\) is decreasing while \(t=n/u\geq Y>e\), so integration by parts bounds the centered contribution by \(O(1/L)\). Therefore

\[ \int_Y^n W(n/t)\frac{dt}{t\log t} = \mu\int_Y^n\frac{dt}{t\log t}+O(1/L) = \mu(1-\alpha)\log L+O(1/L). \tag{4.7} \]

Using (4.3)–(4.7) for the upper and lower smooth brackets proves (4.1).

Consequence

[b] Mertens' theorem gives

\[ \sum_{p\leq Y}\frac1p =\log\log Y+O(1) =\alpha\log\log n+O(1). \tag{4.8} \]

The small-prime part of \(S(n)\) lies between zero and (4.8), while (4.1) determines the large-prime part. Hence

\[ \left(\frac{1-\alpha}{2}+o(1)\right)\log\log n \leq S(n)\leq \left(\frac{1+\alpha}{2}+o(1)\right)\log\log n. \tag{4.9} \]

Letting \(\alpha\downarrow2/3\) proves the boxed \(1/6\)–\(5/6\) theorem.

[b] This does not prove the conjecture: it identifies exactly \(p\leq\exp((\log n)^{2/3+o(1)})\) as the range still capable of carrying two-thirds of the total reciprocal-prime mass.

5. Exhaustive rational-enclosure computation through \(10^7\)

Certification method

[a] Fix \(Q=10^{15}\). For each \(n\), the verifier computes integers

\[ \begin{aligned} A(n)&=\sum_{\substack{p\leq n\\g(n/p)=1}}\left\lfloor\frac Qp\right\rfloor, &C(n)&=\#\{p\leq n:g(n/p)=1,\ p\nmid Q\},\\ B(n)&=\sum_{p\leq n}\left\lfloor\frac Qp\right\rfloor, &K(n)&=\#\{p\leq n:p\nmid Q\}. \end{aligned} \]

Termwise floor/ceiling bounds give the exact rational enclosure

\[ \frac{2A(n)}{B(n)+K(n)} \leq R(n)\leq \frac{2(A(n)+C(n))}{B(n)}. \tag{5.1} \]

There is no floating-point assumption in (5.1).

[a] For an odd prime \(p\), selected \(n\)'s occur in the intervals

\[ kp+\frac{p+1}{2} \leq n\leq (k+1)p-1,\qquad k\geq1. \tag{5.2} \]

Integer difference arrays add \(\lfloor Q/p\rfloor\) and the remainder flag over every interval (5.2). A cumulative pass obtains \(A,C\) for every \(n\). The core is:

weight, rem = divmod(scale, p)
length = (p - 1) // 2
start = p + (p + 1) // 2
while start <= limit:
    stop = min(limit, start + length - 1)
    diff_floor[start] += weight
    diff_floor[stop + 1] -= weight
    if rem:
        diff_count[start] += 1
        diff_count[stop + 1] -= 1
    start += p

lower = (2 * selected_floor, harmonic_floor + harmonic_count)
upper = (2 * (selected_floor + selected_count), harmonic_floor)

The full standard-library implementation is in the standalone checker.

Certified table

[d] Each displayed decimal lower endpoint was rounded downward and each upper endpoint upward. The exact integer numerators and denominators are emitted with --json.

| range | enclosure of \(\min R(n)\) | witness | enclosure of \(\max R(n)\) | witness | |---|---:|---:|---:|---:| | \(10^2\leq n<10^3\) | \([0.186983692768728,\ 0.186983692768742]\) | 121 | \([1.224558456653043,\ 1.224558456653108]\) | 284 | | \(10^3\leq n<10^4\) | \([0.230299851702372,\ 0.230299851702467]\) | 1,431 | \([1.242730419901418,\ 1.242730419902017]\) | 5,354 | | \(10^4\leq n<10^5\) | \([0.309184441870330,\ 0.309184441871014]\) | 13,212 | \([1.271462264512780,\ 1.271462264514357]\) | 16,673 | | \(10^5\leq n<10^6\) | \([0.335856630097045,\ 0.335856630104675]\) | 208,981 | \([1.259567541482165,\ 1.259567541501465]\) | 304,259 | | \(10^6\leq n\leq10^7\) | \([0.361788955035394,\ 0.361788955071469]\) | 1,170,730 | \([1.279093886145721,\ 1.279093886287755]\) | 2,799,299 |

[d] The last row combines the checker records \([10^6,9{,}999{,}999]\) and the separately checked endpoint \(10^7\); the endpoint enclosure \([0.676052951740170,0.676052952059766]\) changes neither extremum.

[d] In particular, over the complete aggregate range \(100\leq n\leq10^7\),

\[ 0.186983692768728 \leq R(n)\leq 1.279093886287755. \tag{5.3} \]

The extremal enclosures in (5.3) have witnesses \(121\) and \(2{,}799{,}299\), respectively.

[d] The finalized run reported:

469210e1e0f491e120ee2f79bcf19fe5806d5c8b4fefc70efafa1d3a37efe3d9 (SHA-256 of little-endian unsigned 32-bit primes);

[d] The checker independently:

  1. builds its own Eratosthenes sieve;
  2. compares the range-add result against literal modular summation for every

\(n\leq2000\);

  1. checks both exact identities (2.1) and (2.2) on that range;
  2. recomputes every table witness directly from \(2(n\bmod p)>p\);
  3. evaluates the direct sums again with 70-digit decimal arithmetic and

verifies containment in the rational bounds (5.1).

Reproduction command:

python3 runs/erdos726_wavew012_reverify.py \
  --limit 10000000 --self-test-limit 2000 --json

6. Exact remaining wall

[a] Clean sufficient reduction. It would suffice to extend (4.4) to every fixed \(\alpha>0\), uniformly for

\[ P\geq \exp((\log n)^\alpha), \tag{6.1} \]

with an error summable over dyadic \(P\) after the \(1/p\) weight and smooth Fourier truncation. Repeating Section 4 would then give

\[ \frac{1-\alpha}{2}+o(1) \leq\frac{S(n)}{\log\log n} \leq\frac{1+\alpha}{2}+o(1). \]

Letting \(\alpha\downarrow0\) would prove #726.

[b] The available Matomäki–Radziwiłł–Shao–Tao–Teräväinen theorem only reaches \(\alpha>2/3\), because it requires \(n\ll\exp((\log P)^{3/2-\varepsilon})\). The paper explicitly says that even RH does not currently relax this restriction. Thus the exact missing input is a reciprocal-phase prime equidistribution theorem at arbitrarily small subexponential scales, not a final Tauberian or bookkeeping step.

[c] Brute force cannot bridge this uniform asymptotic gap. Extrapolating the measured \(O(N\log\log N)\) interval scan, the same Python implementation at \(N=10^9\) would cost roughly 1.3–1.7 core-hours and 15–20 GB of RAM; it was not run. Even that computation would establish only another finite range, not the missing uniform exponential-sum estimate.

PARTIAL: Rigorous modulo MRSTT Proposition 1.13, \(1/6\leq\liminf S(n)/\log\log n\leq\limsup S(n)/\log\log n\leq5/6\); exhaustive rational enclosures verified every \(100\leq n\leq10^7\), but the uniform reciprocal-phase estimate below \(\exp((\log n)^{2/3+o(1)})\) remains open.

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