---

Source. The paper's single Theorem, p. 7, of 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, as identified on the source card.

Statement

Setting (p. 7). $d(n)$ is the number of divisors of the positive integer $n$, and $f$ is an irreducible polynomial of degree $l$ with integer coefficients. The paper assumes, "for simplicity", that $f(k)>0$ for $k=1,2,\ldots$. The constants $c_1,c_2,\ldots$ are positive, independent of $x$, and may depend on $f$.

Theorem (p. 7, quoted). "There exist positive constants $c_1$ and $c_2$ such that

$$c_1x\log x<\sum_{k=1}^{x}d\bigl(f(k)\bigr)<c_2x\log x \qquad (1)$$

for $x\geqslant 2$."

The paper does not state $l\ge1$, but it is tacit: for a constant prime $f=p$ the sum is $2x$, and the proof works with a root of $f$ (Lemmas 7 and 10).

Context stated on p. 7, not proved in the paper.

• Writing $d_x(n)$ for the number of divisors of $n$ that do not exceed $x$, the paper says it would not be hard to show $\sum_{k\le x}d_x(f(k))=c_3x\log x+o(x\log x)$, its (2). It proves only that this sum exceeds $c_1x\log x$ (Sections 4 and 5), which gives the lower bound in (1). It says the lower bound in (1) is not difficult and is known, citing Bellman, Duke Math. J. 17 (1950), 159--168.
• For $l=2$ it reports that Bellman and Shapiro proved, in a result it calls unpublished, $\sum_{k\le x}d(f(k))=c_4x\log x+o(x\log x)$, its (3). It adds that (3) very likely holds also for $l>2$, but that it cannot prove this.
• It states that the method for the upper bound in (1), combined with Brun's method, would give $\sum_{p\le x}d(f(p))=O(x)$ over primes $p$, answering a question in Bellman's paper. No proof of this is given.

Proof pointer

Lower bound (Sections 4--5, pp. 14--15). Since $d(f(k))\ge d_x(f(k))$, it suffices to bound $\sum_{k\le x}d_x(f(k))$, which counts the solutions of $f(k)\equiv0\pmod y$ with $1\le k\le x$, $1\le y\le x$. Lemma 4 (p. 8) counts the $k\le x$ with $u\mid f(k)$ as between $\frac{x}{2u}\rho(u)$ and $\frac{2x}{u}\rho(u)$ for $1\le u\le x$, where $\rho(a)$ is the number of solutions of $f(k)\equiv0\pmod a$ with $0\le k<a$. Lemma 10 (p. 14), $\sum_{k\le y}\rho(k)>c_{13}y$ for large $y$, is proved from the Dedekind zeta function of the field generated by a root of $f$; partial summation then gives the bound.

Upper bound (Section 3, pp. 10--14). Lemma 1 (p. 8), van der Corput's $\sum_{k\le x}d(f(k))^2<x(\log x)^{c_5}$, and Lemma 2, its Cauchy--Schwarz consequence for sets of fewer than $x(\log x)^{-c_5}$ values of $k$, let Lemmas 5 and 6 (p. 9) discard at cost $O(x)$ the $k$ for which $f(k)$ has a large prime-power factor $p^\alpha$ with $\alpha>1$ or too much of its size in small primes. The remaining $f(k)$ are split at the point where the product of their smallest prime powers passes $x$. When the next prime is large, $d(f(k))$ is bounded by a constant times $d_x(f(k))$, and Lemma 4 with the Euler-product bound of Lemma 9 (p. 10) gives $O(x\log x)$. When it is smaller, the sum is cut by the size of that prime and each piece is bounded through Lemma 4 and the prime-sum estimates of Lemmas 7 and 8 (pp. 9--10); the pieces sum to $O(x\log x)$ (p. 14, (30)).

Read depth

Claims checked: the setting, the Theorem and the statements (2), (3) and the remark on primes were read clause by clause on p. 7 of the print, with Lemmas 1 to 4 (p. 8) and 10 (p. 14). The proofs were read for structure only. Nothing here is independently reviewed.

Dependencies

None in the corpus. External inputs the paper cites: van der Corput's second-moment bound (Lemma 1), Nagell's results on $\rho(p^\alpha)$ (Lemma 3), the prime ideal theorem (Lemma 7) and Dedekind's factorization theorem (Lemma 10).

Bears on

• Problem 975: the Theorem gives $\sum_{k\le x}d(f(k))\asymp x\log x$ for every $f$ in its setting, the order of magnitude of the sum whose asymptotic the problem asks for. It proves no asymptotic for any $f$; the paper reports the degree-two asymptotic (3) as an unpublished result of Bellman and Shapiro and says it cannot prove (3) for $l>2$.