OP-00939 Open

Covering a cyclic group by few translates of a random set

Let $p$ be a prime and let $A \subset \mathbb{Z}/p\mathbb{Z}$ be a random set with $|A| = \sqrt{p}$. At least $\sqrt{p}$ translates of $A$ are needed to cover $\mathbb{Z}/p\mathbb{Z}$, and Green does not know whether even $1.01\sqrt{p}$ translates suffice.

Problem. Can $\mathbb{Z}/p\mathbb{Z}$ almost surely be covered by $100\sqrt{p}$ translates of $A$?

Source: B. Green, posed in Barbados in 2010; 100 open problems (version of January 2026), Problem 39.

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

Classification

Primary: CO — Combinatorics
Secondary: NT, PR
Keywords: covering, cyclic groups of prime order, random sets, translates
Literature checked: Oct. 26, 2026 by clemens-admin

References

@article{bollobas2011covering,
  author = {Bollob{\'a}s, B{\'e}la and Janson, Svante and Riordan, Oliver},
  title = {On covering by translates of a set},
  journal = {Random Structures \& Algorithms},
  volume = {38},
  number = {1-2},
  pages = {33--67},
  year = {2011},
  doi = {10.1002/rsa.20346},
  eprint = {0910.3815},
  archivePrefix = {arXiv}
}

@misc{green100open,
  author = {Green, Ben},
  title = {100 open problems},
  howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
  note = {Problem 39; 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-00939, "Covering a cyclic group by few translates of a random set", clopen.solutions.