Erdoes #975 - working report - Erdős Problem a Day

Erdős problem #975 — live-page audit, cubic reduction, and exact computation

Access date: 2026-07-29 UTC.

Claim labels used throughout:

(a) elementary-rigorous: proved below using only exact identities or elementary arguments.
(b) rigorous-modulo-named-theorem: the named standard theorem is stated.
(c) plausible/structural-unverified: heuristic only; never used as a theorem.
(d) computational-only: an exact finite computation or a source observation, not an asymptotic theorem.

0. Mandatory live-page gate

(d, live retrieval) I fetched both the live problem page, its “View the LaTeX source” view, and the discussion thread through the Bright Data browser path. The live page said:

status OPEN;
0 claimed proofs for this problem;
Currently working on this problem None;
Interested in collaborating None;
last edited 27 December 2025.

Thus the mandatory stop condition did not apply.

Verbatim live statement

The following is copied verbatim from the page's LaTeX-source view (only placed in a code block):

Let $f\in \mathbb{Z}[x]$ be an irreducible non-constant polynomial such that $f(n)\geq 1$ for all large $n\in\mathbb{N}$. Does there exist a constant $c=c(f)>0$ such that\[\sum_{n\leq X} \tau(f(n))\sim cX\log X,\]where $\tau$ is the divisor function?

Everything else listed on the live page

(d, live retrieval) The page lists the following known results:

van der Corput [Va39] proved

\[ \sum_{n\le X}\tau(f(n))\gg_f X\log X; \]

Erdős [Er52b] proved by elementary methods

\[ \sum_{n\le X}\tau(f(n))\ll_f X\log X; \]

Hooley [Ho63] proved the requested asymptotic for every irreducible quadratic;
McKee [Mc95], [Mc97], and [Mc99] gave expressions for the quadratic constants;
the page gives

\[ \sum_{n\le x}\tau(n^2+1)=\frac3\pi x\log x+O(x) \] as an example, and links Tao's blog post.

(d, live retrieval) The four displayed comments, which the site itself warns are not verified, are:

Alfaiz, 16 June 2026: points to K. Lapkova [La18] on

\(\sum_{n\le N}\tau(n^2+2bn+c)\) and says that paper contains several partial results.

Yael Dillies, 23 December 2025: notes that the constant-polynomial case gives the boring counterexample \(f=1\); the live statement was subsequently changed to “non-constant.”
Terence Tao, 12 September 2025: corrects a formerly displayed constant \(2\), points out the \(3/\pi\) constant for \(n^2+1\), and notes that irreducibility is needed because reducible quadratics instead have \(X\log^2X\)-type growth; the live page was subsequently updated.
Terence Tao, 1 September 2025: links his blog post; the live page was subsequently updated.

1. Primary-source literature audit

(d, source audit) I verified that the principal references actually exist and say what is attributed to them:

P. Erdős, “On the Sum \(\sum_{k=1}^x d(f(k))\),” J. London Math. Soc. 27 (1952), 7–15, DOI 10.1112/jlms/s1-27.1.7, with an author-archive PDF.
C. Hooley, “On the number of divisors of quadratic polynomials,” Acta Math. 110 (1963), 97–114, DOI 10.1007/BF02391856.
J. McKee's 1995 paper explicitly treats irreducible quadratics and identifies the leading constant using class numbers; his 1999 paper extends the description to general irreducible quadratics. The primary PDFs are 1995 and 1999.
K. Lapkova's paper mentioned in the newest comment is arXiv:1704.02498, later Monatsh. Math. 186 (2018), 663–673; it concerns irreducible quadratics, not a higher-degree univariate case.

(d, source audit) I also checked work not listed on the page:

L. Chiriac, DOI 10.1556/314.2022.00019, says in its introduction (in 2022) that no such asymptotic had been shown for higher-degree polynomials.
K. Ford and G. Qian, arXiv:1910.02832, current manuscript date 22 March 2026, determine the order of magnitude for the number of \(n\le x\) for which \(F(n)\) has a divisor in \((y,z]\), but their theorem assumes \(y\le x^{1-\delta}\). The long divisors isolated below begin at \(y>x\), so that theorem does not supply the needed estimate.
L. Grimmelt and J. Merikoski, arXiv:2508.17979, prove an asymptotic for the binary, nonhomogeneous cubic \(XY^2+1\). It averages over two variables and does not give an asymptotic for one sequence \(f(n)\).
Tao's 2011 exposition explicitly identifies the failed hyperbola-method level: degree \(3\) leaves moduli of size about \(X^{3/2}\), whose accumulated endpoint errors exceed the main term.

(d, honest search miss) I found no primary source proving the desired asymptotic for any fixed irreducible univariate cubic, in particular \(n^3+2\). This is a report of the search, not a proof that no such paper exists; the live page's current status remains the authoritative status used here.

2. A concrete irreducible cubic and its local residue

Set

f(n)=n^3+2,\qquad \rho(q)=\#\{a\bmod q:a^3+2\equiv0\pmod q\}.

(a) The polynomial is irreducible over \(\mathbb Z\) by Eisenstein at \(2\), and \(f(n)>n^2\) for every \(n\ge1\).

(a) Chinese remaindering makes \(\rho\) multiplicative. Its prime-power values are

\rho(2)=\rho(3)=1,\qquad \rho(2^k)=\rho(3^k)=0\quad(k\ge2),

and, for \(p\ge5\),

\rho(p^k)=\rho(p)= \begin{cases} 1,&p\equiv2\pmod3,\\ 3,&p\equiv1\pmod3\ \text{and}\ (-2)^{(p-1)/3}\equiv1\pmod p,\\ 0,&p\equiv1\pmod3\ \text{otherwise}. \end{cases}

For \(p\ge5\) this is the cyclic structure of \(\mathbb F_p^\times\) plus Hensel lifting. At \(2\), a root must be even and then \(x^3+2\equiv2\pmod4\); at \(3\), a root is \(x\equiv1\pmod3\) and then \(x^3+2\equiv3\pmod9\).

Let

D(s)=\sum_{q\ge1}\frac{\rho(q)}{q^s}.

Put \(K=\mathbb Q(\sqrt[3]2)\), \(\beta=\sqrt[3]2\), and \(t=p^{-s}\).

(b, pure-cubic integral-basis criterion and Dedekind factorisation) We have \(\mathcal O_K=\mathbb Z[\beta]\), \(\operatorname{disc}K=-108\), and \(2,3\) are totally ramified. For \(p\ge5\), the three possible splitting types and the corresponding local quotient \(H_p(s)=D_p(s)/\zeta_{K,p}(s)\) are

\begin{array}{c|c|c} \rho(p)&\text{splitting type}&H_p(s)\\ \hline 3&(1,1,1)&1-3t^2+2t^3\\ 1&(1,2)&1-t^2\\ 0&(3)&1-t^3. \end{array}

At \(p=2,3\), \(H_p(s)=1-t^2\). Hence

D(s)=\zeta_K(s)H(s),

where the Euler product for \(H\) is absolutely convergent for \(\Re s>1/2\).

(a, given the integral basis) The class number and regulator can be obtained without trusting a database. Minkowski's bound is

\frac4\pi\frac{3!}{3^3}\sqrt{108} =\frac{16\sqrt3}{3\pi}<3.

Thus every ideal class has a representative of norm \(1\) or \(2\). The unique prime over \(2\) is \((\beta)\), of norm \(2\), so it is principal and \(h_K=1\). The unit

\varepsilon=1+\beta+\beta^2=(\beta-1)^{-1}

is fundamental. A short check is as follows: if a positive unit \(u=a+b\beta+c\beta^2\) satisfied \(1<u<\varepsilon\), then its complex conjugates have modulus \(u^{-1/2}\). From

\operatorname{Tr}(u)=3a,\qquad \operatorname{Tr}(u^2)=3(a^2+4bc)

one gets \(a\in\{0,1\}\), then \(a=1\), and \(bc\in\{0,1\}\). The norm equation

N(a+b\beta+c\beta^2)=a^3+2b^3+4c^3-6abc=1

then leaves only \(u=1\) or \(u=\varepsilon\), contradicting strict inequality.

(b, analytic class-number formula) Therefore

\kappa_K:=\operatorname*{Res}_{s=1}\zeta_K(s) =\frac{\pi\log(1+\sqrt[3]2+\sqrt[3]4)}{3\sqrt3}.

Define the positive, completely explicit residue

\boxed{ R=\operatorname*{Res}_{s=1}D(s) =\kappa_K(1-2^{-2})(1-3^{-2}) \prod_{p\ge5} \begin{cases} 1-3p^{-2}+2p^{-3},&\rho(p)=3,\\ 1-p^{-2},&\rho(p)=1,\\ 1-p^{-3},&\rho(p)=0. \end{cases}} \tag{1}

(b, Wiener–Ikehara) Since \(D\) has nonnegative coefficients, a single simple pole at \(1\), and \(H\) is regular there,

\sum_{q\le y}\rho(q)\sim Ry,\qquad \sum_{q\le y}\frac{\rho(q)}q=R\log y+o(\log y). \tag{2}

(b+d) Truncating (1) at \(P=2{,}000{,}000\) gives

0.507395143397\le R\le0.507395904490 \tag{3}

under ordinary double-precision evaluation of the displayed finite product. The truncation error itself is analytically enclosed: every omitted factor is \(1-a_p\) with \(0\le a_p\le3/p^2\), so

\exp\!\left( -\frac{3/P}{1-3/(P+1)^2} \right) \le\prod_{p>P}(1-a_p)\le1.

The conservative decimal consequence is \(0.5073951<R<0.5073960\).

(c) If long residue classes are unbiased, the natural leading constant is

c_{\mathrm{nat}}=3R\in [1.522185430190,1.522187713469] \tag{4}

at the raw precision of (3). Formula (4) is a prediction, not a proved asymptotic.

3. Exact reduction to the missing long-modulus discrepancy

For \(X\ge1\), define

\begin{aligned} S(X)&=\sum_{n\le X}\#\{d\mid f(n):d\le n\},\\ E(X)&=\sum_{n\le X}\#\{d\mid f(n):n<d\le X,\ d\le\sqrt{f(n)}\},\\ L(X)&=\sum_{n\le X}\#\{d\mid f(n):X<d\le\sqrt{f(n)}\},\\ Q(X)&=\#\{n\le X:f(n)\text{ is a square}\},\\ T(X)&=\sum_{n\le X}\tau(f(n)). \end{aligned}

(a) Since \(f(n)>n^2\), divisor pairing gives the exact identity

T(X)=2S(X)+2E(X)+2L(X)-Q(X). \tag{5}

(a+b, using (2)) Swapping the \(d\le n\) summation gives

\begin{aligned} S(X) &=\sum_{d\le X} \left(\rho(d)\frac{X-d+1}{d}+O(\rho(d))\right)\\ &\sim R X\log X. \end{aligned} \tag{6}

Also

0\le E(X)\le\sum_{d\le X}\rho(d)=O(X),\qquad 0\le Q(X)\le X. \tag{7}

Consequently,

\boxed{T(X)=2R X\log X+2L(X)+o(X\log X).} \tag{8}

Thus, for this first irreducible cubic, the entire unknown leading term is carried by divisors in the precise range

X<d\le\sqrt{n^3+2}\le X^{3/2}+o(1).

To expose the endpoint error, for \(X<d\le\sqrt{X^3+2}\) set

\begin{aligned} \ell_d(X)&=\#\{1\le n\le X:d^2\le n^3+2\},\\ A_d(X)&=\#\{1\le n\le X:d^2\le n^3+2,\ n^3+2\equiv0\pmod d\},\\ \Delta(X)&=\sum_{X<d\le\sqrt{X^3+2}} \left(A_d(X)-\rho(d)\frac{\ell_d(X)}d\right). \end{aligned} \tag{9}

(a) The first two lines of (9) make

L(X)=\sum_{X<d\le\sqrt{X^3+2}}A_d(X) \tag{10}

an exact identity.

(b, using (2) and Stirling's formula) The local-density model in (9) satisfies

\begin{aligned} \sum_{X<d\le\sqrt{X^3+2}}\rho(d)\frac{\ell_d(X)}d &=\sum_{n\le X}\sum_{X<d\le\sqrt{n^3+2}}\frac{\rho(d)}d\\ &=\frac R2 X\log X+o(X\log X). \end{aligned} \tag{11}

Indeed, only \(n\gtrsim X^{2/3}\) contribute, and the main logarithm is

R\sum_{X^{2/3}<n\le X} \left(\frac32\log n-\log X\right) =\frac R2X\log X+O(X).

Combining (8)–(11) gives the clean reduction

\boxed{ T(X)=3R X\log X+2\Delta(X)+o(X\log X). } \tag{12}

(b) Therefore the requested asymptotic for \(f(n)=n^3+2\) exists if and only if \(\Delta(X)/(X\log X)\) has a limit. If that limit is \(\lambda\), then \(c=3R+2\lambda\). In particular, the natural constant \(c=3R\) is equivalent to the single estimate

\boxed{\Delta(X)=o(X\log X).} \tag{13}

(a+b) A single interval has endpoint error at most \(\rho(d)\), so the available termwise estimate only gives

|\Delta(X)| \le\sum_{d\le\sqrt{X^3+2}}\rho(d) =O(X^{3/2}), \tag{14}

which is too large by a factor of order \(X^{1/2}/\log X\). The exact missing lemma is therefore cancellation of the signed residue-class endpoint errors in (9) over \(X<d\le X^{3/2}\), strong enough to improve (14) to \(o(X\log X)\).

4. Exact finite computation for \(n^3+2\)

(d) The standalone verifier computed and certified every value through \(X=200{,}000\). “Middle” is all \(n<d\le\sqrt{f(n)}\); “long” is the hard subrange \(X<d\le\sqrt{f(n)}\). The four integer columns obey \(T=2S+2\,\mathrm{Middle}-Q\) exactly.

| \(X\) | \(T(X)\) | \(2S(X)\) | \(2\,\mathrm{Middle}\) | \(2L(X)\) | \(Q(X)\) | \(T/(X\log X)\) | \(2S/(X\log X)\) | \(2L/(X\log X)\) | |---:|---:|---:|---:|---:|---:|---:|---:|---:| | 100 | 762 | 582 | 180 | 108 | 0 | 1.654661976 | 1.263796942 | 0.234519020 | | 300 | 2,682 | 2,042 | 640 | 390 | 0 | 1.567380951 | 1.193360142 | 0.227918930 | | 1,000 | 11,056 | 8,046 | 3,010 | 2,132 | 0 | 1.600519931 | 1.164777800 | 0.308638612 | | 3,000 | 38,160 | 27,460 | 10,700 | 7,916 | 0 | 1.588735452 | 1.143256696 | 0.329571013 | | 10,000 | 145,188 | 103,958 | 41,230 | 31,680 | 0 | 1.576358681 | 1.128709644 | 0.343961230 | | 30,000 | 486,308 | 345,672 | 140,636 | 111,560 | 0 | 1.572445543 | 1.117708111 | 0.360722063 | | 100,000 | 1,806,176 | 1,274,868 | 531,308 | 433,166 | 0 | 1.568824540 | 1.107336275 | 0.376243207 | | 200,000 | 3,825,024 | 2,689,888 | 1,135,136 | 937,352 | 0 | 1.566852874 | 1.101864653 | 0.383969532 |

(d) Independently, the root-count computation gave

\sum_{q\le200000}\rho(q)=101469,\qquad \sum_{q\le200000}\frac{\rho(q)}q=7.234583123,

so the finite ratio \(\sum_{q\le200000}\rho(q)/200000=0.507345\). This is consistent with (3), but finite agreement is not a proof of a limit.

5. Reproduction and independent checks

The complete standard-library verifier is runs/erdos975_wavew027_reverify.py. Run from the repository root:

python3 runs/erdos975_wavew027_reverify.py --progress

(d) The final clean default run took 71.29 seconds on this VM and printed

SHA-256 certificate: 6c99145e265db3474b2e6bf842a649fb0628a9ec4eb1cc4a658e22f17a9f0e71
DEFAULT CERTIFICATE CHECK: PASS

(d) Its checks are deliberately redundant:

Every \(n^3+2\) is factored by deterministic 64-bit Miller–Rabin and a

deterministic sequence of Pollard–Brent attempts.

Every returned factor is re-certified prime and the product is checked

against \(n^3+2\).

For \(n\le2{,}000\), an independent exhaustive trial-division

factorisation must agree.

For \(n\le500\), direct iteration through every

\(1\le d\le\sqrt{n^3+2}\) independently checks \(\tau\), the small/middle split, and the square correction.

The multiplicative \(\rho(q)\) table is independently checked by trying

every residue class for every \(q\le2{,}000\).

The expected checkpoint rows and full SHA-256 certificate are hard-coded,

so later changes fail loudly.

(d) As an additional implementation-independent check, PARI/GP returned

\sum_{n\le1000}\tau(n^3+2)=11056,\qquad \sum_{n\le10000}\tau(n^3+2)=145188,

and at \(X=10000\) returned the split \([2S,2\,\mathrm{Middle},2L,Q]=[103958,41230,31680,0]\). PARI also independently returned discriminant \(-108\), class number \(1\), regulator \(1.3473773483293841\ldots\), and total ramification at \(2,3\).

6. What is and is not achieved

(a+b) Equations (8) and (12) are a rigorous reduction for the concrete irreducible cubic \(n^3+2\): all divisors with modulus at most \(X\) are settled to leading order, and the question is exactly the convergence of the long-modulus discrepancy (9).

(c) The natural answer for this cubic is \(c=3R\approx1.522186\), but neither the exact computation nor the local model proves the cancellation (13).

(d, cost diagnosis) Extending the present factorisation table cannot resolve a uniform \(X\to\infty\) statement. The current program processes about \(2.9\times10^3\) values/second in this range; a run to its 64-bit cap near \(2\times10^6\) would realistically cost roughly 15–25 one-core minutes and still prove only a finite table. Directly indexing the discrepancy by moduli already requires touching about \(X^{3/2}\) moduli. The needed advance is the analytic cancellation lemma (13), not a moderately larger finite search.

PARTIAL: For the irreducible cubic \(f(n)=n^3+2\), the \(d\le X\) contribution is rigorously \(2R X\log X\), the problem is reduced exactly to signed endpoint cancellation for \(X<d\le X^{3/2}\), \(R\) has an explicit Euler product with \(0.5073951<R<0.5073960\), and all divisor sums/splits through \(X=200000\) were exactly certified; the required \(o(X\log X)\) long-modulus discrepancy remains open.

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