Erdős Problem #1140

Erdős Problem 1140: finiteness of universally prime quadratic differences

Statement and scope.

There are only finitely many positive integers $n$ for which $n-2x^2$ is prime whenever $x$ is a positive integer with $2x^2<n$. The following proof establishes finiteness, without claiming an explicit final list or resolving a possible exceptional integer in stronger classification results. See https://www.erdosproblems.com/1140. It is a reconstruction via the prime-character input used in the modern general resolution of the related problem 1141.

External prime-character theorem.

Pollack's Theorem 1.3 in Bounds for the first several prime character nonresidues, https://arxiv.org/abs/1508.05035, states that for every $\varepsilon,A>0$ and all sufficiently large moduli $M$, a quadratic Dirichlet character modulo $M$ has at least $(\log M)^A$ primes $p\leq M^{1/4+\varepsilon}$ with character value $1$. We use its nonprincipal case, with $\varepsilon=1/16$.

If $2n$ is not a square, the Kronecker character $\chi(t)=(8n/t)$ is a nonprincipal quadratic Dirichlet character modulo $M=8n$. The theorem produces an odd prime $p\nmid2n$, with \[ p\leq(8n)^{5/16},\qquad (2n/p)=1. \] Since multiplication by $2^2$ does not change a nonzero quadratic-residue class, this implies that $2x^2\equiv n\pmod p$ has a solution $1\leq r<p$. For sufficiently large $n$, \[ 2r^2\leq2p^2=O(n^{5/8})=o(n), \qquad n-2r^2>p. \] The positive integer $n-2r^2$ is divisible by $p$ and is greater than $p$, so it is composite.

The principal-character case.

If $2n$ is a square, choose any odd prime $p\nmid2n$. It can be chosen with $p=n^{o(1)}$: among the first $\omega(2n)+1$ odd primes at least one does not divide $2n$, and repeated Bertrand postulates bound that prime by $2^{O(\omega(2n))}$. Here $\omega(n)=o(\log n)$, since the product of $r$ distinct primes is at least $(r+1)!$. Now $(2n/p)=1$, and the identical root construction gives $1\leq r<p$, $2r^2=o(n)$, and a composite $n-2r^2>p$.

Thus every sufficiently large $n$ fails the property. Allowing $x=0$ as well only makes the original property stronger and does not affect this disproof.

Attribution.

Epure--Gica and Mollin--Williams give the more precise classification discussed on the problem page. The general Pollack-based approach is attributed in problem 1141 to the internal OpenAI model described in https://arxiv.org/abs/2604.06609; no new resolution or independent proof of Pollack's theorem is claimed.

Completion estimate.

The infinitude question is fully answered negatively, conditional only on the stated established prime-character theorem and standard quadratic reciprocity and Bertrand's postulate. COMPLETION: 100%