Skip to content

Erdős Problem #428

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, primes.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Can one choose an infinite set of positive integers \(A\) that is quite large on the scale of the primes, yet has infinitely many translations that turn every selected smaller element into a prime? Erdős Problem 428 asks for an \(A\subseteq\mathbb N\) such that, for infinitely many positive integers \(n\),

\[ n-a\ \text{is prime for every }a\in A\text{ with }0<a<n, \]

and at the same time

\[ \liminf_{x\to\infty} \frac{|A\cap[1,x]|}{\pi(x)}>0, \]

where \(\pi(x)\) is the number of primes not exceeding \(x\).

The two conditions are jointly demanding. Each chosen \(n\) must work simultaneously for all the previously selected elements, not only for finitely many convenient ones. And the set \(A\) cannot be arbitrarily sparse: it must contain at least a fixed positive multiple of \(\pi(x)\) elements up to every sufficiently large \(x\). This is density relative to the prime-counting function, not ordinary natural density relative to \(x\).

The use of a lower limit is also essential. A positive \(\limsup\) permits the ratio to be large on occasional subsequences and tiny in between. A positive \(\liminf\) prohibits those persistent troughs.

A small example

Let \(A=\{1,3,5\}\) and take \(n=8\). Then

\[ 8-A=\{7,5,3\}, \]

and every displayed integer is prime. This is a genuine finite witness of the simultaneous-primality condition at one starting point. It can be checked exactly by trial division: \(3,5,7\) have no divisors other than \(1\) and themselves.

However, \(A\) is finite, and therefore

\[ \lim_{x\to\infty}\frac{|A\cap[1,x]|}{\pi(x)} =\lim_{x\to\infty}\frac3{\pi(x)}=0. \]

So this example cannot solve the problem. The same issue affects any finite collection of impressive primality witnesses: a finite set can never satisfy the required positive relative lower density.

For a finite candidate set, one can enumerate integer translates \(n\) and test every required \(n-a\) for primality, but the problem asks for one fixed infinite \(A\) and infinitely many suitable \(n\). An experiment confined to \(n\leq N\) cannot establish either infinite quantifier. The exact placement of \(a<n\) matters too: when \(a\geq n\), the corresponding difference is not required to be prime, and including it would change the problem.

What is known

The question comes from Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), the original source denoted [ErGr80] by the maintained catalogue. It links the theory of prime constellations with an additional, difficult requirement of consistent positive relative density across all large scales.

The maintained Erdős Problems #428 page reports the exact problem as OPEN. It credits Erdős and Graham with a conditional partial result: assuming the prime-tuple conjecture of order \(k\), they could obtain such a construction if the density requirement were weakened by replacing \(\liminf\) with \(\limsup\). This is an important distinction in two directions. The prime-tuple conjecture of order \(k\) is not an established general theorem, and the weaker positive-upper-limit assertion does not imply the desired positive-lower-limit condition.

To see why the limit distinction is logical rather than cosmetic, imagine a nonnegative sequence of ratios that repeatedly takes values near \(1\) and \(0\). Such a sequence has positive limsup but zero liminf. Establishing good density at selected scales leaves open whether the set becomes too sparse in the gaps between those scales. The Erdős problem demands that these gaps remain controlled while infinitely many prime-compatible translates are preserved.

Other research on admissible prime tuples or prime-rich patterns can offer possible methods, but no named external theorem was verified here as settling the full combination of requirements. A finite admissible pattern, even when it has arbitrarily many prime translations conditionally or unconditionally, is not yet a globally dense infinite set with the required synchronization.

GCL's current state

The original GCL issue #1698 freezes the teorth catalogue at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, file data/problems.yaml, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The frozen issue records an open status, consistent with the maintained mathematical page.

The pinned FormalConjectures 428.lean has Git blob d4ea9492ffc89822f2674fd3e6584c20a77d7bf6. It defines a relative-prime-density ratio using the cardinality of the selected positive integers up to \(n\), divided by the prime-counting function. The research statement quantifies over infinitely many suitable \(n\) and requires the liminf to be positive. Its theorem body remains by sorry, so the file is a formal statement interface rather than a completed proof.

The authenticated original issue source audit is RESULT/1 comment #6157388132. The comment anchors the mathematical and bibliographic claims; it does not certify an original solution or confer accepted article status in the V2 ledger.

What remains

An appropriate bounded next task is an exact finite prime-translate experiment, with its interpretation deliberately limited. Enumerate candidate finite sets \(A\subseteq[1,12]\) and translations \(1\leq n\leq100\). For each pair, test whether every required difference \(n-a\) is prime, using a certified or independently cross-checked primality routine. Record successful witnesses, the exact selected elements below each \(n\), and any modular obstruction.

The conceptual task is to write a short theorem-concordance note distinguishing the full original positive-liminf requirement from Erdős and Graham's conditional positive-limsup substitute. State precisely what additional uniform lower bound on \(|A\cap[1,x]|\) would be needed to upgrade the density conclusion. The bounded work succeeds if its finite data replay, the two infinite quantifiers remain explicit, and no conditional result is promoted into an unconditional proof. Falsification includes a composite difference, a missing selected element, or substituting a sparse finite set for the required infinite one. Stop after these finite and source checks rather than claiming resolution of the open problem.

Sources and claim boundaries

Primary historical source: Erdős–Graham (1980), original monograph. Maintained statement and partial-result attribution: Erdős Problem #428. Original GCL assignment: issue #1698, frozen catalogue, pinned formal source, and authenticated source report.

The displayed finite primality witness is independently verifiable but cannot certify either infinite assertion. The historical weaker claim is expressly conditional on the prime-tuple conjecture of order \(k\). No theorem resolving the positive-liminf question, no Lean proof replay and no protected editorial admission are claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1698 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction