Questions tagged [sieve-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
29 votes
1 answer
1k views

Why is there a Parity Problem in Sieve Theory and not a Mod p problem for any other p?

The "parity problem" in sieve theory, so far as I understand it, is the fact that sieves can't distinguish between primes and $2$-almost primes, numbers with exactly two prime factors, and will always ...
Xiaoyu He's user avatar
  • 1,151
27 votes
1 answer
2k views

Does a proof of Selberg's 3.2 inequality exist?

A well-known inequality of Montgomery and Vaughan (generalizing a result of Hilbert) states that $$ \left |\sum_{r \neq s} \frac{w_{r} \overline{w_{s}} }{\lambda_r - \lambda_s} \right| \leq \pi \...
Mark Lewko's user avatar
  • 11.7k
24 votes
3 answers
1k views

Are sets with similar asymptotic behavior as the primes necessarily finite additive bases?

The set of primes $\mathbb{P}$ has many interesting properties in additive number theory and some of the most famous open problems about $\mathbb{P}$ are the well-known Goldbach's strong and weak ...
Joni Teräväinen's user avatar
21 votes
3 answers
3k views

What is a sieve and why are sieves useful?

I have been trying to understand what is exactly a sieve and why sieves are useful. I have read Wikipedia articles about sieve theory but they don't provide a definition of what is a sieve or why they ...
Kaveh's user avatar
  • 5,362
20 votes
6 answers
4k views

Erik Westzynthius's cool upper bound argument: update?

Version 2 of this writeup is available, and includes a newer and simple upper bound thanks to MathOverflow 88777 as well as indirect references to future writeups. Details of further work ...
Gerhard Paseman's user avatar
16 votes
1 answer
1k views

Elementary Proof of Infinitely many primes $\mathfrak{p} \in \mathbb{Z}[i]$ in the sector $\theta < \arg \mathfrak{p} <\phi $

A quick look at the primes in $\mathbb{Z}[i]$ suggests they might be evenly distributed by angle if we zoom out on a coarse enough scale. I would like ask about the much weaker statement forgetting ...
john mangual's user avatar
  • 22.6k
16 votes
1 answer
1k views

Least prime in an arithmetic progression and the Selberg sieve

My question concerns a technical step in the proof of Linnik's theorem on the least prime in an arithmetic progression, as presented in Chapter 18 of Iwaniec-Kowalski: Analytic number theory. The ...
GH from MO's user avatar
  • 98.2k
15 votes
2 answers
304 views

S integral points of an elliptic curve, with S of positive density

Let E be an elliptic curve over Q of non-zero rank. Let S be the union of the primes of bad reduction of E with a Chebotarev set [1]. Suppose additionally that S has density strictly less than one. ...
David Zureick-Brown's user avatar
15 votes
1 answer
966 views

Why do Maynard-Tao weights succeed?

I'm attempting to understand why the Maynard-Tao weights are successful in proving bounded gaps between primes, but the GPY weights are not. These two posts do an excellent job in giving an overview ...
numbertheorylearner's user avatar
14 votes
1 answer
401 views

Unpublished result of Rosser in Sieve Methods book

Erdős and Selfridge (1971) state that the following is "implied by an unpublished result of Rosser" which they claim appears in a forthcoming book on sieve methods by Halberstam and Richert. ...
Bjørn Kjos-Hanssen's user avatar
13 votes
1 answer
731 views

Large sieve inequality for sparse trigonometric polynomials

Let $S(\alpha) = \sum_{n\leq N}f(n) e^{2\pi i \alpha n}$ for some arithmetic function $f$. Suppose $\alpha_1, \ldots, \alpha_R$ are real numbers that are $\delta$-spaced modulo $1$, for some $0 < \...
user152169's user avatar
12 votes
1 answer
1k views

Why do the Maynard-Tao weights work so well?

I am looking for an intuitive reason for why the Maynard-Tao weights work well to capture many primes of the form $n+h_1, \ldots , n+h_k$, where $(h_1, \ldots , h_k)$ is any admissible $k$-tuple. For ...
George Shakan's user avatar
12 votes
1 answer
1k views

Does the Maynard-Tao Theorem apply to general tuples of linear forms?

In the paper http://arxiv.org/pdf/1311.5319v1.pdf the author states the following theorem, which he attributes to Maynard and Tao. For any integer $m > 2$, there exists an integer $k = k(m)$ such ...
anon's user avatar
  • 303
12 votes
0 answers
616 views

Sieve bound for prime $k$-tuples

Let $d_1<d_2<\dots<d_k$ be integers. Then the number of integers $n\leq x$, such that $n+d_1, n+d_2, \ldots, n+d_k$ are simultaneously prime, is bounded above by $$ \mathfrak{S}(d_1, \ldots, ...
Jan-Christoph Schlage-Puchta's user avatar
11 votes
2 answers
1k views

What is the significance of Friedlander-Iwaniec and related theorems?

On p.177 of Number Theory Revealed: A Masterclass by Andrew Granville, the author states that "One can ask for prime values of polynomials in two or more variables." (though he later ...
Favst's user avatar
  • 1,985
11 votes
2 answers
707 views

Improving the error term in a classic sieving problem

I'm new to asking questions on MathOverflow, so forgive me if this question is not the kind of thing to be asked here. Let $q$ be a positive integer and let $N$ be an integer with $1 \leq N \leq q$. ...
Joshua Stucky's user avatar
11 votes
2 answers
485 views

How many random sieve operations to decimate the set {2,...,n}?

Let $S$ be the set of integers $\{2,3,4,\ldots,n\}$. Consider the following process: Select a random element $k \in S$. Remove from $S$ every number divisible by $k$. Repeat with this reduced $S$. ...
Joseph O'Rourke's user avatar
11 votes
2 answers
1k views

Why going to number fields in number field sieve help beat quadratic sieve?

To factor an $n$ bit integer number field sieve roughly takes $$e^{c{(\ln\ln n)^{\frac23}}({\ln n})^{\frac13}}$$ time while quadratic sieve takes $$e^{c{(\ln\ln n)^{\frac12}}({\ln n})^{\frac12}}$$ ...
user avatar
10 votes
0 answers
322 views

Are there are any attempts utilising sieve theory to attack the general $a p \pm 1$ problem?

It is currently an open question if there are infinitely many primes $p$ such that $2p + 1$ is prime (Sophie Germain primes) or that at least one of $24p \pm 1$ is prime. Could Zhang's method, or the ...
KStarGamer's user avatar
9 votes
1 answer
385 views

Is the set of prime pairs such that $gcd(p−1,q−1)=2$ of positive density?

Is the set of prime pairs such that $gcd(p−1,q−1)=2$ of positive density? For example, for $p,q≤10^4$ the answer is approximately $1/2$. I was wondering if it were possible to use sieve methods and ...
Gal Porat's user avatar
  • 225
9 votes
1 answer
659 views

Status of current research in Sieve Theory

I have done a course in Sieve Theory from the notes of Prof. Rudnick. Before this, I did 2 courses in Number Theory from the 2 volumes of Apostol. I don't have any guidance by professor as I am living ...
Arnold's user avatar
  • 668
9 votes
0 answers
422 views

A characterization of quadratics similar to an inverse sieve problem

Suppose $\mathscr{A} \subset \mathbb{N}$ enjoys for all large enough cutoffs $X$ the following properties: $|\mathscr{A} \cap [1,X]| > \sqrt{X}/10$; and the discriminant $\prod_{\alpha \neq \beta}|...
Vesselin Dimitrov's user avatar
8 votes
1 answer
894 views

Is this weak asymptotic Goldbach's conjecture open?

Let $\tau(x)$ be the number of even numbers $2<2n<x$ which can't be written as a sum of two primes. Goldbach's conjecture: $\tau(x) = 0$ Asymptotic Goldbach's conjecture: $\tau(x) = O(1) $ ...
Sebastien Palcoux's user avatar
8 votes
1 answer
936 views

Sum of divisors below threshold

Let $\sigma(n)$ denote the sum of divisors of $n$, that is, $$ \sigma(n) = \sum_{d | n} d. $$ It is known that $\sigma$ can have values as large as order $n \log \log n$. However, obviously the sum is ...
Kurisuto Asutora's user avatar
8 votes
1 answer
1k views

A reformulation of the Riemann Hypothesis

I am studying Sieve theory from Iwaniec's notes. I have come across a theorem which estimates $\varphi(x,N)=\#\{1\leq n \leq x:(n,N)=1\}$, where $N$ is product of distinct primes. Let's define $R(x,...
Subhajit Jana's user avatar
8 votes
1 answer
219 views

How does the bound in the large sieve depend on the norm on the lattice?

I've been reading about the large sieve inequality in Serre's "Lectures on the Mordell-Weil theorem", which states it in the following setting, which I've simplified a bit here: Suppose $\...
Alison Miller's user avatar
8 votes
0 answers
242 views

Which continuous function is optimal for sieving?

In 1968, Barban and Vehov considered [1] the problem of determining for which continuous functions $\rho:\mathbb{R}^+\to [0,1]$ satisfying certain properties ($\rho(t)=1$ for $t\leq U_0$, $\rho(t)=0$ ...
H A Helfgott's user avatar
  • 19.3k
7 votes
2 answers
962 views

Upper density of the set of $n$'s such that $p(n)$ is prime, where $p$ is polynomial

The starting point for this question is the following (false) statement $\forall n\in \mathbb{N} (n^2 + n + 41 \text{ is prime}).$ Given a polynomial function $p:\mathbb{N} \to \mathbb{N}$ ...
Dominic van der Zypen's user avatar
7 votes
1 answer
418 views

Are primes of density 0 in $a\cdot b^n+c$?

Hooley proves in Applications of Sieves to the Theory of Numbers that there are only $o(x)$ numbers $n\le x$ such that $n\cdot2^n+1$ is a (Cullen) prime. The proof generalizes to forms $n\cdot2^{n+a}+...
Charles's user avatar
  • 8,974
7 votes
1 answer
323 views

Proportion of numbers with prime divisors from restricted set

Let $X$ be large, and let $\mathcal{P} \subset \{1, \dots, X\}$ be a set of primes. What is a good upper bound for $$ \sum_{\substack{1 \leq n \leq X,\\ p \nmid n \text{ for all }p \in \mathcal{P}}} 1....
Kurisuto Asutora's user avatar
7 votes
1 answer
469 views

Examples of the large sieve inequality where a constant larger than 1 is needed

Let $S(x) = \sum_{n=0}^{N-1} a_n e^{2 \pi i n x}$ be a trigonometric polynomial of length $N$. The analytic/harmonic large sieve inequality in its sharpest form states that $$ \sum_{r=1}^R |S(x_r)|^2 ...
Mark Lewko's user avatar
  • 11.7k
7 votes
1 answer
214 views

Density of extended Mersenne numbers?

Consider the subset of odd positive integers defined and constructed as follows by these rules : A) $1$ is in the set. B) if $x$ is in the set , then $2x + 1$ is in the set. C) if $x$ and $y$ are in ...
mick's user avatar
  • 703
7 votes
1 answer
910 views

Best possible sieves for the jacobsthal problem, linear programming, and the prime 2

Background/Motivation Gerhard Paseman asked a question about bounds on the Jacobsthal function a while ago, which made me curious about whether the known bounds are best possible. Briefly, the ...
zeb's user avatar
  • 8,533
6 votes
1 answer
596 views

The history and original paper of the Rosser–Iwaniec sieve

I'm trying to find Rosser's original paper where he introduces his eponymous sieve. I've already found https://arxiv.org/pdf/math/0505521 (where the reference isn't given, but where it is indicated ...
Cloudscape's user avatar
6 votes
2 answers
301 views

Evolution of partial sum of a sequence of induced Dirichlet characters

Let's consider the Dirichlet Character $\chi_3(n)$ modulo 3 given by $\chi_3(1)=1$, $\chi_3(2)=-1$ and $\chi_3(3)=\chi_3(0)=0$. Lets consider the sequence of induced characters $\chi^{P_N} $ obtained ...
Bertrand's user avatar
  • 1,121
6 votes
0 answers
217 views

admissible tuples vs. prime tuples

Let $\rho^\ast(x)$ denote the maximal length of an admissible sequence in $[1,x]$, i.e. of a sequence which does not cover all the residue classes modulo any $n\geq 2$. Hensley and Richards (1974) ...
GH from MO's user avatar
  • 98.2k
6 votes
0 answers
294 views

Constants for Rosser's Sieve

I am trying to apply Iwaniec's formulation of Rosser's sieve (here) to obtain nontrivial lower bounds for almost-primes in various sequences. These sequences have sieve dimension 1 (if $g(p)$ is the ...
Xiaoyu He's user avatar
  • 1,151
6 votes
0 answers
501 views

$x^2+1$ attaining almost prime values

Iwaniec, using the linear sieve, proved that $n^2+1$ can be a product of at most two primes infinitely often and furthermore a lower bound of the correct order of magnitude for the number of such ...
Dr. Pi's user avatar
  • 2,939
5 votes
2 answers
676 views

Specific application of Cauchy-Schwarz and Large Sieve

Im reading a paper by Matomaki here, and the following is stated (I'm paraphrasing): "By the Cauchy-Schwarz inequality and the large sieve, we have $$\sum_{q \leq Q}\frac{q}{\phi(q)}\sum_{\...
CBagshaw's user avatar
  • 153
5 votes
1 answer
439 views

Large gaps between P2s

Gaps between consecutive primes are $O(n^{\theta+\varepsilon})$ for $\theta=0.525$ and any $\varepsilon>0.$ I was wondering if a better result is known for gaps between numbers with at most two ...
Charles's user avatar
  • 8,974
5 votes
1 answer
223 views

Locating a certain result on primes represented by a certain polynomial

In Theorem 2 of the paper "A polynomial divisor problem" by Friedlander and Iwaniec, Theorem 2 states that $$\sum_{a^6 + b^2\le x} \Lambda(a^6 + b^2)\sim cx^{2/3}$$ for some constant $c > 0$ (in ...
Mayank Pandey's user avatar
5 votes
1 answer
182 views

Almost-prime values attained by a product of quadratic polynomials

Let $F(x) = \prod_{i=1}^{k} (a_i x +b_i)$ be a product of $k$ linear polynomials, where $a_i,b_i$ are integers. Under very reasonable conditions, it is known that a constant $C_k$ exists with the ...
Ofir Gorodetsky's user avatar
5 votes
1 answer
973 views

Reference to "bounds of Weil and Deligne"

In the this paper by Friedlander and Iwaniec, it is said that they are "able to avoid much of the high-powered technology frequently used in modern analytic number theory such as the bounds of Weil ...
Mayank Pandey's user avatar
5 votes
0 answers
313 views

Counting primes, twin primes, cousin primes: unusual approach, connection to some conjectures

I am investigating the following sieve-like algorithm. Let $S_N=\{1,\dots,N\}$. For all primes $p$ with $p_0\leq p \leq M$, we remove from $S_N$ the following elements: all numbers $n\in S_N$ such ...
Vincent Granville's user avatar
5 votes
0 answers
123 views

On Ford's "The distribution of integers with a divisor in a given interval"

Let $H(x,y,z)$ denote the number of positive integers of size at most $x$ which have a divisor in the range $(y,z]$. In his famous "The distribution of integers with a divisor in a given interval&...
Kurisuto Asutora's user avatar
5 votes
0 answers
406 views

Paging Henryk Iwaniec: Problems In Lemma 1?

I gritted my teeth and dove into some sieve theory. In his 1978 article On the Problem of Jacobsthal in Demonstratio Mathematica, Iwaniec presents two Lemmas to prove his main result (leading to $j(n)...
Gerhard Paseman's user avatar
4 votes
2 answers
805 views

Upper bound for the first Hardy-Littlewood conjecture

About the Hardy-Littlewood conjecture by Terence Tao: Conjecture 2 (Prime tuples conjecture, quantitative form) Let ${k_0 \geq 1}$ be a fixed natural number, and let ${{\mathcal H}}$ be a fixed ...
Alexey Milovanov's user avatar
4 votes
1 answer
245 views

Density of primes $p$ where $p-1$ has a prime factor exceeding $p^{2/3}$

Fouvry proved* that primes $p$ such that the greatest prime factor, $q$, of $p-1$ is greater than $p^{2/3}$ have positive density in the primes. (The sequence is A073024 in the OEIS.) Are there any ...
Charles's user avatar
  • 8,974
4 votes
1 answer
937 views

Number of twin primes

Consider number of twin primes less than $x$. We know that this number less than $\frac{Cx}{\log^2 x}$ for some constant $C$. Denote by $p_n$ the $n$-th prime number. Do we have the same result ...
Alexey Milovanov's user avatar
4 votes
1 answer
679 views

Relation between the binary Goldbach problem and binary version of Mobius sum

What I want to ask is about the structure of the Goldbach function that defined by $$ R(x)=\#\{ p \mid x-p \in \mathbb{P} , \ p\leq x/2\}$$ for $x\in 2\mathbb{N}$, where $\mathbb{P}$ is the set of ...
B . O's user avatar
  • 139