Questions tagged [sieve-theory]
The sieve-theory tag has no usage guidance.
112
questions
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 ...
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 \...
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 ...
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 ...
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
...
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 ...
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 ...
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.
...
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 ...
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.
...
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 < \...
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 ...
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 ...
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, ...
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 ...
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$. ...
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$.
...
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}}$$ ...
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 ...
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 ...
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 ...
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}|...
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) $
...
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 ...
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,...
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 $\...
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$ ...
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}$ ...
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}+...
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....
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 ...
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 ...
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 ...
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 ...
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 ...
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) ...
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 ...
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 ...
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_{\...
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 ...
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 ...
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 ...
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 ...
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 ...
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&...
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)...
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 ...
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 ...
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 ...
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 ...