Large Sieve and Quadratic Sets

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For $A\subset\mathbb N$ and a prime $p$, write $A\bmod p=\{a+p\mathbb Z:a\in A\}\subset\mathbb Z/p\mathbb Z$. A rational quadratic map is $\phi(t)=at^2+bt+c$ with $a,b,c\in\mathbb Q$ and $a\ne0$; its integer-argument image is $\phi(\mathbb Z)=\{\phi(n):n\in\mathbb Z\}$. Throughout this statement $\log$ is the natural logarithm. The notation $u(X)\ll v(X)$ means that $u(X)\le C v(X)$ for all sufficiently large $X$, for a constant $C$ independent of $X$.

Statement recorded in the supplied source.

Suppose that $A\subset\mathbb N$ satisfies \[ |A\bmod p|\le\frac{p+1}{2}\quad\text{for every sufficiently large prime }p. \] Must at least one of the following alternatives hold?

• There exists $C>0$ such that $|A\cap\{1,\ldots,\lfloor X\rfloor\}|\le C X^{1/2}/(\log X)^{100}$ for all sufficiently large $X$.
• There is a rational quadratic map $\phi$ such that $A\subset\phi(\mathbb Z)$.

The second alternative requires containment of the whole set in a single quadratic image, as stated in Problem 47. The relevant quadratic cardinality scale is $X^{1/2}$ for integers up to $X$. [S1][S2]

Short English statement

If a set of positive integers occupies at most half the residue classes modulo every sufficiently large prime, must it either be substantially smaller than square-root size or lie entirely among the values of one rational quadratic polynomial at integers?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 109 (GREEN-021). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Ben Green, 100 Open Problems, author manuscript with December 2025 updates, Problem 47 and its comments, p. 23. https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.