ID: 1311.6176

Inverse questions for the large sieve

November 24, 2013

View on ArXiv
Ben J. Green, Adam J. Harper
Mathematics
Number Theory

Suppose that an infinite set $A$ occupies at most $\frac{1}{2}(p+1)$ residue classes modulo $p$, for every sufficiently large prime $p$. The squares, or more generally the integer values of any quadratic, are an example of such a set. By the large sieve inequality the number of elements of $A$ that are at most $X$ is $O(X^{1/2})$, and the quadratic examples show that this is sharp. The simplest form of the inverse large sieve problem asks whether they are the only examples. We prove a variety of results and formulate various conjectures in connection with this problem, including several improvements of the large sieve bound when the residue classes occupied by $A$ have some additive structure. Unfortunately we cannot solve the problem itself.

Similar papers 1

Additive Correlation and the Inverse Problem for the Large Sieve

June 21, 2017

91% Match
Brandon Hanson
Number Theory

Let $A\subset [1,N]$ be a set of positive integers with $|A|\gg \sqrt N$. We show that if avoids about $p/2$ residue classes modulo $p$ for each prime $p$, the $A$ must correlate additively with the squares $S=\{n^2:1\leq n\leq \sqrt N\}$, in the sense that we have the additive energy estimate $E(A,S)\gg N\log N$. This is, in a sense, optimal.

Find SimilarView on arXiv

On a variant of the large sieve

July 31, 2008

90% Match
Ben Green
Number Theory

We introduce a variant of the large sieve and give an example of its use in a sieving problem. Take the interval [N] = {1,...,N} and, for each odd prime p <= N^{1/2}, remove or ``sieve out'' by all n whose reduction mod p lies in some interval I_p of Z/pZ of length (p-1)/2. Let A be the set that remains: then |A| << N^{1/3 + o(1)}, a bound which improves slightly on the bound of |A| << N^{1/2} which results from applying the large sieve in its usual form. This is a very, very...

Find SimilarView on arXiv

Polynomial values modulo primes on average and sharpness of the larger sieve

September 25, 2014

90% Match
Xuancheng Shao
Number Theory

This paper is motivated by the following question in sieve theory. Given a subset $X\subset [N]$ and $\alpha\in (0,1/2)$. Suppose that $|X\pmod p|\leq (\alpha+o(1))p$ for every prime $p$. How large can $X$ be? On the one hand, we have the bound $|X|\ll_{\alpha}N^{\alpha}$ from Gallagher's larger sieve. On the other hand, we prove, assuming the truth of an inverse sieve conjecture, that the bound above can be improved (for example, to $|X|\ll_{\alpha}N^{O(\alpha^{2014})}$ for ...

Find SimilarView on arXiv

On the large sieve with sparse sets of moduli

December 12, 2005

89% Match
Stephan Baier
Number Theory

Extending a method of D. Wolke, we establish a general result on the large sieve with sparse sets S of moduli which are in a sense well-distributed in arithmetic progressions. We then use this result together with Fourier techniques to obtain large sieve bounds for the case when S consists of squares. These bounds improve a recent result by L. Zhao.

Find SimilarView on arXiv

A Lower Bound for the Large Sieve with Square Moduli

December 14, 2018

88% Match
Stephan Baier, Sean B. Lynch, Liangyi Zhao
Number Theory

We prove a lower bound for the large sieve with square moduli.

Find SimilarView on arXiv

Distribution of squares modulo a composite number

February 17, 2015

88% Match
Farzad Aryan
Number Theory

In this paper we study the distribution of squares modulo a square-free number $q$. We also look at inverse questions for the large sieve in the distribution aspect and we make improvements on existing results on the distribution of $s$-tuples of reduced residues.

Find SimilarView on arXiv

Large Sieve Inequalities for Characters to Square Moduli

August 7, 2005

88% Match
Liangyi Zhao
Number Theory

In this paper, we develop a large sieve type inequality with characters to square moduli. One expects that the result should be weaker than the classical inequality, but, conjecturally at least, not by much. The method is generalizable to higher power moduli.

Find SimilarView on arXiv

The large sieve with sparse sets of moduli

August 22, 2005

88% Match
Stephan Baier
Number Theory

Extending a method of D. Wolke, we establish a general result on the large sieve with sparse sets S of moduli which are in a sense well-distributed in arithmetic progressions. We then apply our result to the case when S consists of sqares. In this case we obtain an estimate which improves a recent result by L. Zhao.

Find SimilarView on arXiv

On the large sieve with square moduli

August 22, 2005

88% Match
Stephan Baier
Number Theory

We prove an estimate for the large sieve with square moduli which improves a recent result of L. Zhao. Our method uses an idea of D. Wolke and some results from Fourier analysis.

Find SimilarView on arXiv

When the sieve works II

September 8, 2015

88% Match
Kaisa Matomäki, Xuancheng Shao
Number Theory
Combinatorics

For a set of primes $\mathcal{P}$, let $\Psi(x, \mathcal{P})$ be the number of positive integers $n \leq x$ all of whose prime factors lie in $\mathcal{P}$. In this paper we classify the sets of primes $\mathcal{P}$ such that $\Psi(x, \mathcal{P})$ is within a constant factor of its expected value. This task was recently initiated by Granville, Koukoulopoulos and Matom\"aki and their main conjecture is proved in this paper. In particular our main theorem implies that, if not ...

Find SimilarView on arXiv