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

Erdős problem #976 — wave w027

Date: 2026-07-29 (UTC)

Claim labels

(a) elementary-rigorous: proved below from elementary facts.
(b) rigorous-modulo-named-theorem: the deduction is rigorous assuming the

accurately quoted theorem from the named primary source.

(c) plausible/structural-unverified: heuristic or an unverified claim; not

used as a theorem.

(d) computational-only: an exhaustive finite statement certified by the

standalone program accompanying this report.

No claim labelled (c) is used to infer an asymptotic result.

Step 0: mandatory live-page audit

I accessed the live problem page, its LaTeX-source view, and its discussion thread through the Bright Data browser path on 2026-07-29.

The live status was:

OPEN;
0 claimed proofs for this problem;
Currently working on this problem: None;
Interested in collaborating: None;
three discussion comments;
last problem-page edit: 01 February 2026.

Thus none of the mandatory stop conditions was present.

Verbatim live statement

Let $f\in \mathbb{Z}[x]$ be an irreducible polynomial of degree $d\geq 2$. Let $F_f(n)$ be maximal such that there exists $1\leq m\leq n$ with $f(m)$ is divisible by a prime $\geq F_f(n)$. Equivalently, $F_f(n)$ is the greatest prime divisor of\[\prod_{1\leq m\leq n}f(m).\]Estimate $F_f(n)$. In particular, is it true that $F_f(n)\gg n^{1+c}$ for some constant $c>0$? Or even $\gg n^d$?

Verbatim known-results text on the live page

Nagell \cite{Na22} and Ricci \cite{Ri34} proved that\[F_f(n) \gg n\log n,\]which Erd\H{o}s \cite{Er52c} improved to\[F_f(n) \gg n(\log n)^{\log\log\log n}.\]In \cite{Er65b} he claimed a proof of\[F_f(n) \gg n\exp((\log n)^c)\]for some constant $c>0$, but said he had never published the proof, which was 'fairly complicated'. This seems to have been flawed, since Erd\H{o}s and Schinzel \cite{ErSc90} later published a weaker bound. A proof of the stronger bound above was finally provided by Tenenbaum \cite{Te90}.

All live comments and markers read

The page warns that comments are user-supplied and unverified.

AronBhalla (16:39, 16 April 2026) says that a strong prime-values

hypothesis gives $F_f(n)\gg n^d$, and that the single-polynomial Bateman--Horn conjecture is an immediate corollary. The linked note is this Google Drive file. This is conditional, not a claimed unconditional solution.

Nat Sothanaphan (17:59, 16 April 2026) says a “standard check” found no

issues in that conditional note.

Przemek Chojecki (08:06, 03 February 2026) gives a literature summary:

general unconditional bounds remain $n^{1+o(1)}$; fixed powers are available for certain special cubics and quartics; and, for quadratics, it says the cited infinite-often results lack the dyadic positive-proportion statement that would force a uniform running-maximum bound. This last assertion is part of the unverified comment, not a conclusion used here. The comment links Erdős--Schinzel, Irving, Dartyge--Maynard, Deshouillers--Iwaniec, Merikoski, Arango-Piñeros--Keliher, and Lagarias--Odlyzko.

The remaining external-data markers were: “Likes: Aron”; “looks difficult: None”; “looks tractable: None”; “formalisable: None”; and “working on formalising: None.”

Normalisation

Write $P^+(N)$ for the greatest prime divisor of $|N|$. Since an irreducible polynomial of degree at least two has no integer zero,

F_f(n)=\max_{1\le m\le n}P^+(f(m)).

This is merely the fundamental theorem of arithmetic applied to the product. (a)

Also, for fixed $f$ of degree $d$,

F_f(n)\ll_f n^d,

because every relevant prime is at most $|f(m)|\ll_f n^d$. Thus $n^d$ is the largest possible scale up to an $f$-dependent constant. (a)

Primary-source literature audit

1. The exact strongest general theorem located

Erdős and Schinzel, On the greatest prime factor of $\prod_{k=1}^x f(k)$, Acta Arith. 55 (1990), 191--200, journal record, primary scan, prove that for irreducible $f$ of degree $>1$,

F_f(x)>x\exp\exp\!\left(c_1(\log\log x)^{1/3}\right)

for an absolute $c_1>0$ and all sufficiently large $x$. This is their Theorem 1. (b)

Tenenbaum, Sur une question d'Erdős et Schinzel, II, Invent. Math. 99 (1990), 215--224, author-hosted primary PDF, proves the sharper statement:

\boxed{\quad F_f(x)>x\exp\!\left((\log x)^\alpha\right) \quad(0<\alpha<2-\log 4) \quad}

for every irreducible $f\in\mathbb Z[x]$ of degree $>1$, once $x>x_0(f,\alpha)$. This is Theorem 2 of the paper. Numerically,

2-\log 4=0.613705638880\ldots.

(b)

There is a small bibliographic ambiguity on the live page: its [Te90] entry is Tenenbaum's longer chapter Sur une question d'Erdős et Schinzel, pp. 405--443 in A Tribute to Paul Erdős. The “added in proofs” paragraph on p. 442 explicitly points to the Inventiones “II” paper and states the same consequence for every $\alpha<2-\log4$. I checked both texts.

Erdős's original 1952 paper also exists as a primary scan, with the bibliographic data stated on the live page. (b)

2. Later divisor-distribution work does not reach the endpoint

Ford and Qian, The distribution of divisors of polynomials, Mathematika 66 (2020), 395--415, arXiv:1910.02832, author PDF, determine the order of the divisor-in-an-interval count $H_f(x,y,z)$ in the range

y+\frac{y}{(\log y)^C}<z\le y^2,\qquad y\le x^{1-\delta}.

The condition $y\le x^{1-\delta}$ excludes the endpoint $y\asymp x$ that drives problem #976. Thus this paper sharpens the divisor statistics but does not improve Tenenbaum's general $F_f(x)$ exponent. (b)

3. A post-page-edit special-case advance

Ermoshin, The largest prime factor of an irreducible cubic polynomial, arXiv:2602.03642v3 (revised 12 June 2026), proves in its stated theorem that for every monic irreducible cubic $f\in\mathbb Z[x]$, there is a $c_f>0$ such that a positive proportion of $m\in[X,2X]$ have

P^+(f(m))>X^{1+c_f}.

Consequently, choosing $X=n/2$ gives

F_f(n)\gg_f n^{1+c_f}

for every sufficiently large $n$. (b), modulo this recent preprint

This is genuine progress on a large special class, but it is not a solution for arbitrary degree, nor does its stated theorem cover nonmonic cubics. The live problem page was last edited two days before v1 of this preprint and therefore does not mention it.

Ermoshin's introduction itself identifies Tenenbaum's $\alpha<2-\log4$ result as the best bound for arbitrary degree. My search found no later primary source claiming an improvement for all irreducible $f$. This is a search report, not a proof that no such paper exists.

4. A recent pointwise result that does not improve this product problem

Cuevas Barrientos and Pasten, On the greatest prime factor of polynomial values and subexponential Szpiro in families, arXiv:2504.15971v3, prove, among other things,

P^+(f(n))\gg_f \frac{(\log_2 n)^2}{\log_3 n}

for irreducible quadratics with complex roots and cubics of a specified form. This is a pointwise-in-$n$ theorem and is far below Tenenbaum's lower bound for the running product maximum $F_f(n)$. I include it to separate two easily confused “greatest prime factor of polynomial values” questions. (b)

A clean reduction and the exact analytic wall

For irreducible $f$ of degree $d$, define

H_f(x):=\#\{m\le x:\ f(m)\text{ has a divisor }q \text{ with }x/2<q\le x\}.

Erdős--Schinzel's quantitative form of Erdős's argument, quoted as equation (1.3) in Tenenbaum II, is

F_f(x)> x\exp\!\left(\frac{\log x}{d\,x}H_f(x)\right) \qquad(x>x_0(f)). \tag{ES}

(b)

Consequence 1: what would be enough for a fixed power

If one could prove, uniformly for all large $x$,

H_f(x)\ge\delta_f x \tag{PD}

with $\delta_f>0$, then (ES) would give

F_f(x)>x^{1+\delta_f/d}.

The substitution is elementary and loses no uniformity. (a), conditional on (ES) and (PD)

Tenenbaum's Theorem 1 gives only

H_f(x,y,2y)>x(\log x)^{-\eta} \quad\text{for }y\le x/2,\quad \eta>\log4-1.

At $y=x/2$, substitution in (ES) yields

F_f(x)> x\exp\!\left(\frac1d(\log x)^{1-\eta}\right).

Choosing $\log4-1<\eta<1-\alpha$ recovers every $\alpha<2-\log4$. (b)

This displays the barrier exactly: the available $H_f(x)/x$ tends to zero. Moreover, Tenenbaum's and Ford--Qian's divisor-distribution results away from the endpoint have order

H_f(x,y,2y)=x(\log y)^{-\delta+o(1)},\qquad \delta=1-\frac{1+\log\log2}{\log2}=0.086071\ldots,

so positive density is not even the expected outcome of this divisor localisation statistic. (b) for their stated ranges; (c) if extrapolated to the endpoint

Thus the standard Erdős--Schinzel/Tenenbaum route cannot reach a fixed power merely by polishing constants. It would need either a qualitatively false-looking positive-density upgrade of $H_f$, or a stronger inequality than (ES) that extracts much more from a zero-density set.

Consequence 2: why this route cannot reach $x^d$

Even the formal maximum $H_f(x)=x$ makes the right side of (ES) only

x^{1+1/d},

strictly smaller than $x^d$ for every $d\ge2$. This is a ceiling on what this inequality can certify, not an upper bound on $F_f$. (a)

For a fixed power, an alternative sufficient target is the dyadic large-prime lemma

\exists\,c_f>0\ \forall X\gg_f1\ \exists m\in(X,2X]: P^+(f(m))>X^{1+c_f}. \tag{DLP}

Taking $X=n/2$ proves $F_f(n)\gg_f n^{1+c_f}$. (a)

Ermoshin proves the stronger positive-proportion version of (DLP) for monic cubics. Analogous Type I/II or exponential-sum estimates are known only for selected algebraic families. The exact missing general input is a uniform dyadic estimate ruling out $X^{1+c}$-smooth values of an arbitrary irreducible polynomial strongly enough to establish (DLP). No finite computation can supply this uniform analytic statement.

For the conjectural $x^d$ scale, the corresponding sufficient input is a prime or almost-prime value of size $\asymp X^d$ in every dyadic interval; this is where the live comment's prime-values/Bateman--Horn hypothesis enters. It is not presently unconditional.

Exact finite computation for $f(x)=x^2+1$

The polynomial $x^2+1$ is irreducible over $\mathbb Z$. (a)

The standalone checker erdos976_wavew027_reverify.py exactly factors every $m^2+1$ for $1\le m\le10^6$, computes every running maximum, and proves the following finite statements.

Exact endpoint table

All entries in the last column are themselves prime.

| $n$ | exact $F_{x^2+1}(n)$ | witness $m$ | factorisation of $m^2+1$ | |---:|---:|---:|---:| | 10 | 101 | 10 | 101 | | 100 | 8,837 | 94 | 8,837 | | 1,000 | 972,197 | 986 | 972,197 | | 10,000 | 99,800,101 | 9,990 | 99,800,101 | | 100,000 | 9,999,200,017 | 99,996 | 9,999,200,017 | | 1,000,000 | 999,920,001,601 | 999,960 | 999,920,001,601 |

(d)

Sharp finite $C n^2$ bounds

Each interval below is inclusive. The displayed rational number is the exact minimum of $F_{x^2+1}(n)/n^2$ over every integer in that interval, not a rounded fit.

| interval | sharp $C=\min F(n)/n^2$ | attaining $n$ | record witness $m$ | decimal | |---:|---:|---:|---:|---:| | $[2,9]$ | $41/81$ | 9 | 9 | 0.506172839506173 | | $[10,100]$ | $677/1225$ | 35 | 26 | 0.552653061224490 | | $[100,1000]$ | $8837/11881$ | 109 | 94 | 0.743792610049659 | | $[1000,10000]$ | $1464101/1545049$ | 1,243 | 1,210 | 0.947608134110957 | | $[10000,100000]$ | $108784901/110019121$ | 10,489 | 10,430 | 0.988781768216454 | | $[100000,1000000]$ | $11878820101/11901282649$ | 109,093 | 108,990 | 0.998112594359576 |

In particular, for every integer $100000\le n\le1000000$,

\boxed{\quad F_{x^2+1}(n)\ge \frac{11878820101}{11901282649}\,n^2 =0.998112594359576\ldots\,n^2, \quad}

and the constant is sharp on that finite interval. (d)

There are 54,111 strict record setters through $10^6$. The longest constant-record plateau is $840904\le n\le841115$, of length 212. The SHA-256 digest of all binary pairs $(m,P^+(m^2+1))$, $1\le m\le10^6$, is

b74ba5b709161c3df88369a2e035561223e281b71ed7e0e8fd5b2acf6a194343

(d)

Why the computation is exact

The checker constructs all primes $p\le10^6$ by its own Eratosthenes

sieve.

For $p\equiv1\pmod4$, it constructs and verifies the two roots of

$u^2\equiv-1\pmod p$. For $p\equiv3\pmod4$, there are no roots; $p=2$ is handled separately.

Along each root progression it divides out every power of $p$ from

every $m^2+1$.

It reconstructs each original integer from the removed prime powers and

its residual. If a residual $r>1$ were composite, it would have a prime divisor at most $\lfloor\sqrt{m^2+1}\rfloor\le10^6$, already removed. Hence the residual is prime. (a)

A locally implemented deterministic 64-bit Miller--Rabin test provides

an additional residual check.

A second implementation builds its own small prime list by incremental

trial division, then independently factors every value for $1\le m\le10000$.

All minima are checked using integer cross-multiplication, not

floating-point comparison.

The expected endpoints, exact ratios, record count, plateau, and digest

are assertions evaluated only after recomputing the full factorisation.

The command

python3 runs/erdos976_wavew027_reverify.py

completed on this VM with:

LIMIT=1000000
PAIR_SHA256=b74ba5b709161c3df88369a2e035561223e281b71ed7e0e8fd5b2acf6a194343
RECORD_COUNT=54111
LONGEST_RECORD_PLATEAU=[840904,841115] length=212
ENDPOINTS: n F(n) witness factorization(witness^2+1)
  10 101 10 101
  100 8837 94 8837
  1000 972197 986 972197
  10000 99800101 9990 99800101
  100000 9999200017 99996 9999200017
  1000000 999920001601 999960 999920001601
SHARP_RATIOS: [lo,hi] min(F(n)/n^2) n witness decimal
  [2,9] 41/81 n=9 witness=9 0.506172839506173
  [10,100] 677/1225 n=35 witness=26 0.552653061224490
  [100,1000] 8837/11881 n=109 witness=94 0.743792610049659
  [1000,10000] 1464101/1545049 n=1243 witness=1210 0.947608134110957
  [10000,100000] 108784901/110019121 n=10489 witness=10430 0.988781768216454
  [100000,1000000] 11878820101/11901282649 n=109093 witness=108990 0.998112594359576
PREFIX_CROSSCHECK=1..10000: PASS
PASS

The full run used about 50 CPU-seconds and roughly 30 MB for the three 64-bit arrays plus sieve overhead. A direct scale-up of this Python implementation to $10^8$ would require roughly 2.4 GB just for those arrays and, by the observed near-linear scaling, about 1.3--1.5 single-core hours. Such a run would still concern only one quadratic and could not prove an asymptotic statement, so it was not attempted.

What has and has not been established

The exact best general theorem found in the primary literature is

Tenenbaum's $F_f(x)>x\exp((\log x)^\alpha)$ for every $\alpha<2-\log4$. (b)

The fixed-power question has a June 2026 positive answer for monic

irreducible cubics, modulo Ermoshin's recent preprint, but not for arbitrary irreducible $f$. (b)

The finite $x^2+1$ table and all six sharp interval bounds through

$10^6$ are exactly reproducible. (d)

The finite data do not prove $F_{x^2+1}(n)\gg n^2$, and say still

less about arbitrary $f$. No asymptotic closure is claimed.

The precise general obstruction is the missing dyadic large-prime

estimate (DLP), or comparable Type I/II distribution input, for arbitrary irreducible polynomials. The classical divisor-localisation statistic has zero density and equation (ES) cannot turn it into a fixed power.

PARTIAL: verified Tenenbaum's exact best general exponent, isolated the zero-density/Type-I–II barrier, recorded the June-2026 monic-cubic advance, and exactly certified $F_{x^2+1}(n)\ge0.998112594359576\,n^2$ for every $10^5\le n\le10^6$; the arbitrary-degree fixed-power question remains open.

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