A sharp inverse theorem for the quadratic large sieve
Abstract
We prove that if A⊆[N], |A|≫√N, and |Ap|≤ p/2+O(1) for every prime p≪ log N, then A contains at least exp(c√(log N)/loglog N) elements in the image of a single integral quadratic m± x2. This significantly improves Hanson's logarithmic lower bound, while requiring the residue restriction only for primes p≪log N. Our proof uses a new weighted entropy argument inspired by our previous work \href{https://arxiv.org/abs/2606.17487}{arXiv:2606.17487} with Sheffer. A matching construction shows that this exponential scale is optimal even when the quadratic may be chosen arbitrarily in ℤ[x]. We also show extending the residue restrictions to primes up to (log N)3 yields the stronger bound exp(c√(log N/loglog N)) via a Selberg-sieve-type argument, and discuss an application to the inverse Goldbach problem.
Related
- Optimization of Quadratic Sieve Algorithm Implementation for Large Integer Factorization
- CUDA-MPQS: A GPU-Resident Self-Initializing Quadratic Sieve, and the Factorization of RSA-155
- The weighted large sieve through Parseval
- The large sieve through Parseval, Large sifted sets are regular
- Optimal large sieve for fixed order characters
BibTeX
@misc{croot2026sharp,
title = {{A sharp inverse theorem for the quadratic large sieve}},
author = {Ernie Croot and Junzhe Mao and Cosmin Pohoata and Chi Hoi Yip},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.15311},
eprint = {2607.15311},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.15311},
}
RIS
TY - UNPB
TI - A sharp inverse theorem for the quadratic large sieve
AU - Ernie Croot
AU - Junzhe Mao
AU - Cosmin Pohoata
AU - Chi Hoi Yip
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2607.15311
UR - https://arxiv.org/abs/2607.15311
AB - We prove that if A⊆[N], |A|≫√N, and |A_p|≤ p/2+O(1) for every prime p≪ log N, then A contains at least exp(c√(log N)/loglog N) elements in the image of a single integral quadratic m± x^2. This significantly improves Hanson's logarithmic lower bound, while requiring the residue restriction only for primes p≪log N. Our proof uses a new weighted entropy argument inspired by our previous work \href{https://arxiv.org/abs/2606.17487}{arXiv:2606.17487} with Sheffer. A matching construction shows that this exponential scale is optimal even when the quadratic may be chosen arbitrarily in ℤ[x]. We also show extending the residue restrictions to primes up to (log N)^3 yields the stronger bound exp(c√(log N/loglog N)) via a Selberg-sieve-type argument, and discuss an application to the inverse Goldbach problem.
ER -