Let epsilon,eta>0. Does there exist k=k_0(epsilon,eta) such that, whenever p_1<…<p_k<n^1-epsilon are primes and A_i consists of (p_i-1)/2 residue classes modulo p_i, fewer than epsilon n integers m≤ n avoid every A_i modulo p_i?

Erdős Problem #1202 — Avoiding half-residue classes modulo small primes

Erdős posed the problem in 1980: does forbidding half the residue classes modulo sufficiently many primes below $n^{1-\epsilon}$ leave fewer than $\epsilon n$ integers up to $n$ ?

Known results

The large sieve settles the restricted range $p_k<n^{1/2}$ .
Erdős described the full problem as seemingly “intractable at present” in 1980.

Reported counterexample (undated)

Liam Price and GPT-5.4 Pro are credited with a construction using primes of size roughly $\sqrt{n}\log n$ and interval-like forbidden sets, leaving at least $(1/2-c)n$ survivors for every $c>0$ . If correct, this disproves the conjecture beyond the large-sieve range; the claim remains unverified and no published proof is cited.

Current status (as of September 2026): The range $p_k<n^{1/2}$ is settled, while the reported counterexample beyond that range remains unverified.

Erdős Problem #1202 — Avoiding half-residue classes modulo small primes

Primary source

Additional references

Progress summary

Solutions 0