Let A⊆N be admissible if there is no prime p such that A contains at least one element in every residue class modulo p. Erdős and Graham's conjecture. There is a non-decreasing, unbounded function f:N→Z_≥ 0 such that, whenever A⊆N is admissible and |A cap1,…,N|≤ f(N) for all N, there exists n∈Z such that A+n is contained in the positive primes. Erdős and Graham asked whether sufficiently sparse infinite admissible sets must have a translate contained in the primes. The conjecture is false: the paper constructs arbitrarily sparse infinite admissible sets with no such translate.

Erdős and Graham's sparse admissible-set conjecture

About 2 years old · traced to 2024

Let $A\subseteq\mathbb{N}$ be admissible if there is no prime $p$ such that $A$ contains at least one element in every residue class modulo $p$ . Erdős and Graham's conjecture. There is a non-decreasing, unbounded function $f:\mathbb{N}\to\mathbb{Z}_{\geq 0}$ such that, whenever $A\subseteq\mathbb{N}$ is admissible and

|A\cap\{1,\dots,N\}|\leq f(N)

for all $N$ , there exists $n\in\mathbb{Z}$ such that $A+n$ is contained in the positive primes. Erdős and Graham asked whether sufficiently sparse infinite admissible sets must have a translate contained in the primes. The conjecture is false: the paper constructs arbitrarily sparse infinite admissible sets with no such translate.

References

Primary source

Desmond Weisenberg, “Sparse Admissible Sets and a Problem of Erdős and Graham”, arXiv:2405.12310 (2024).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A 2024 preprint claims the conjecture is false by constructing arbitrarily sparse admissible sets that have no translate consisting entirely of primes.

Erdős and Graham asked whether every sufficiently sparse infinite admissible set has a translate contained in the primes. The question appears in their book and is listed as Problem 429 on erdosproblems.com.

May 2024 counterexample claim

The preprint claims that for every non-decreasing unbounded function $f$ , there is an admissible set $A$ with $|A\cap\{1,\dots,N\}|\leq f(N)$ for every $N$ , yet no translate $A+n$ lies in the positive primes. It gives several constructions, including an elementary Chinese-remainder-theorem construction; the catalogue records the conjecture as refuted.

Current status (as of September 2026): A preprint claims to disprove the conjecture, but the retrieved record contains no independent verification, error report, withdrawal, or retraction.

Sources

No solutions have been posted yet.