OP-01135 Needs verification

Sieving by half the residue classes modulo 1000 large primes

Needs verification: Answered no after Green's list by Price with GPT-5.4 Pro (Erdős problem #1202), with no paper; held, as no record of it can be listed here.

Submit a result

Let $N$ be large and let $p_1 < p_2 < \dots < p_{1000} < N^{9/10}$ be primes. For each $i$, delete from $\{1, \dots, N\}$ all integers lying in a chosen set of $\lfloor p_i / 2 \rfloor$ residue classes modulo $p_i$. When all the primes are below $N^{1/2}$, the large sieve shows, as Erdős noted, that at most $\frac{1}{10} N$ integers remain.

Problem. Must at most $\frac{1}{10} N$ integers remain, for every such choice of primes and residue classes?

Source: P. Erdős, A survey of problems in combinatorial number theory, Ann. Discrete Math. 6 (1980), Section 6, Problem 3; Erdős problem #1202. Listed in this form as Problem 44 in B. Green, 100 open problems (version of January 2026).

Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.

Classification

Primary: NT — Number Theory
Secondary: CO
Keywords: Erdős problems, large sieve, residue classes, sieve theory
Literature checked: Nov. 3, 2026 by clemens-admin

References

@incollection{erdos1980survey,
  author = {Erd{\H o}s, Paul},
  title = {A survey of problems in combinatorial number theory},
  booktitle = {Combinatorial mathematics, optimal designs and their applications},
  series = {Annals of Discrete Mathematics},
  volume = {6},
  pages = {89--115},
  publisher = {North-Holland},
  year = {1980}
}

@misc{erdosproblems1202,
  author = {Bloom, Thomas F.},
  title = {Erd{\H o}s {P}roblem \#1202},
  howpublished = {\url{https://www.erdosproblems.com/1202}},
  note = {Records the negative answer of Price and GPT-5.4 Pro; accessed 2026-11-03},
  year = {2026}
}

@misc{green100open,
  author = {Green, Ben},
  title = {100 open problems},
  howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
  note = {Problem 44; version of January 2026, most recent update December 2025},
  year = {2026}
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-01135, "Sieving by half the residue classes modulo 1000 large primes", clopen.solutions.