Residue classes modulo primes slightly above the square root
Let $N$ be a large integer, and for each prime $p$ with $N^{0.51} \le p < 2N^{0.51}$ pick a residue class $a(p) \in \mathbb{Z}/p\mathbb{Z}$. Green thinks of this as a Kakeya problem in dimension $2 + \varepsilon$. With $0.51$ replaced by an exponent below $\tfrac12$ the analogous question is straightforward, by inclusion–exclusion or Cauchy–Schwarz.
Problem. Is it true that $$\#\{n \in [N] : n \equiv a(p) \pmod p \text{ for some } p\} \gg N^{1 - o(1)},$$ whatever the choice of the classes $a(p)$?
Source: B. Green, A note on multiplicative functions on progressions to large moduli, Proc. Roy. Soc. Edinburgh Sect. A 148 (2018), Section 4. Listed as Problem 43 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
- Kakeya problem, large sieve, residue classes, sieve theory
- Literature checked
- Oct. 26, 2026 by clemens-admin
References
@article{green2018multiplicative,
author = {Green, Ben},
title = {A note on multiplicative functions on progressions to large moduli},
journal = {Proceedings of the Royal Society of Edinburgh Section A: Mathematics},
volume = {148},
number = {1},
pages = {63--77},
year = {2018},
doi = {10.1017/S0308210517000191},
eprint = {1604.04481},
archivePrefix = {arXiv}
}
@article{alon1992peres,
author = {Alon, Noga and Peres, Yuval},
title = {Uniform dilations},
journal = {Geometric and Functional Analysis},
volume = {2},
number = {1},
pages = {1--28},
year = {1992},
doi = {10.1007/BF01895704}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 43; 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-00941, "Residue classes modulo primes slightly above the square root", clopen.solutions.