Questions tagged [sieve-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
47 views

How much does one have to study connected fields to understand modern sieve methods? [closed]

For example, If I'd want to read through the "Primes in tuples" and other works on the GPY sieve, how much analysis/group theory/analytic number theory do I need to know?
zielik's user avatar
  • 101
4 votes
1 answer
250 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,984
2 votes
1 answer
155 views

Selberg sieve for counting monic irreducible $P \in \mathbb{F}_q[t]$ such that $P + K$ is also irreducible

In a 1983 paper by William Webb (link below), the author gives a version of the Selberg sieve for function fields and uses it to prove that for a fixed $K \in \mathbb{F}_q[t]$, the number $\mathcal{N}(...
Owen Sharpe's user avatar
1 vote
1 answer
196 views

Large sieve type inequality

Let $S_x(t)=\sum_{n\le x} a_n e(nt)$, where $e(x)=e^{2\pi i x}$. Then, the large sieve inequality tells us that $$ \sum_{q\le Q} \sum_{\substack{0\lt a \lt q \\ (a,q)=1}}|S_x(a/q)|^2 \le (Q^2+4\pi x)\...
Itachi's user avatar
  • 167
1 vote
0 answers
144 views

Counting prime factors of polynomial functions

Let $\Omega(n)$ denote the number of prime factors (counted with multiplicity) of a non-zero integer $n$. For $f \in \mathbb Z[X]$ non-zero, let $$m(f) = \liminf_{n \to \infty} \Omega(f(n))$$ (1) Is $...
Jens Reinhold's user avatar
4 votes
2 answers
251 views

Sum of $\frac{1}{(\delta_1,\delta_2)}$ with congruence restrictions

In the course of my work, I encountered the following sum ($(x,y)$ stands for the GCD of $x$ and $y$): $$L(Q)=\sum_{\substack{\delta_1,\delta_2\leq Q\\\delta_1\equiv0\ (a)\\\delta_2\equiv0\ (b)}}\frac{...
Tom Glover's user avatar
7 votes
1 answer
216 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
  • 733
1 vote
1 answer
147 views

Functor whose essential image is a cosieve?

Definitions An object $d \in Obj(\mathcal D)$ is in the essential image of $F$ if there exists some $c \in Obj(\mathcal C)$ such that $d \cong F c$. A sieve in $\mathcal D$ is a full subcategory of $\...
anuyts's user avatar
  • 469
3 votes
0 answers
67 views

Divisor of given order in short intervals

Is the following Open question or Conjecture already known, or eventually settled ? Open question : For sufficiently large $x$ there is at least a positive integer in the interval $[x,x+\log^2(x)]$ ...
G. Melfi's user avatar
  • 388
1 vote
0 answers
67 views

Upper bound for the number of coprimes to primes below $x$ in an arbitrary interval of length $x$?

Let $\mathcal{E}$ be a subset of the primes up to $x^{{1/2}-o(1)}$ and let $S(T,T+x;\mathcal{E})$ be the number of integers in the interval $(T,T+x]$ that are coprime to the primes in $\mathcal{E}$. ...
user45947's user avatar
  • 955
3 votes
1 answer
278 views

Best available bounds for $\pi(Y)-\pi(Y-X)$?

I don't know much (anything) about sieves, but as I read the section on the Selberg upper bound sieve from Greaves's Sieves in Number Theory, there is a theorem 4 which says that If $Y\ge X \ge 2$, ...
user859588's user avatar
0 votes
0 answers
432 views

Relation between sieve wheel and Sundaram sieve

I made this sieve for prime numbers, which I briefly describe: We consider $\quad p=r+modulus \cdot k \quad$ with $\quad modulus=p_1*p_2* \cdots *p_m$ and then we choose an appropriate reduced ...
user140242's user avatar
1 vote
0 answers
91 views

Large sieve inequality-like sum without the square

Let $S(\alpha) = \sum_{n\leq N} w(n) e^{2\pi i \alpha n}$ for some function $w$ defined on $\mathbb{R}$. Suppose $\alpha_1, \ldots, \alpha_R$ are real numbers that are $\delta$-spaced modulo $1$, for ...
SJY's user avatar
  • 579
0 votes
0 answers
52 views

On the upper bound estimation of $D(N)$ in Chen Jingrun's theorem

What are the current research results on the estimation of the upper bound of $D(N)$ in Chen Jingrun's theorem? Including but not limited to Chen Jingrun's improvement 7.8342 and Wu Jie's improvement ...
RL433's user avatar
  • 1
2 votes
1 answer
190 views

What fraction of the values of a quadratic polynomial can be prime?

I have an explicit, monic quadratic polynomial $P(x)$ and an integer $m$. Can I bound the number of prime values in $P(0), P(1), \ldots, P(m)$? A reference would be appreciated, if available. An ...
Charles's user avatar
  • 8,984
9 votes
1 answer
667 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
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
2 votes
1 answer
254 views

Sieve theory through variational principles

Disclaimer: I'm just starting to read Sieve Methods by Halberstam and Richert, so my present knowledge of the subject is close to zero, but it made me wonder if some connection to physics could exist, ...
Sylvain JULIEN's user avatar
2 votes
0 answers
231 views

Conjecture on a sieve of Flavius Josephus

Flavius Josephus's sieve: Start with the natural numbers; at the $k$-th sieving step, remove every $(k+1)$-st term of the sequence remaining after the $(k-1)$-st sieving step; iterate. Some examples: ...
Notamathematician's user avatar
14 votes
1 answer
402 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
4 votes
1 answer
202 views

Remainder terms of congruence sums in sets of positive density

Let $\mathcal{A} \subset \mathbb{N}$ be an infinite sequence with positive density, in the sense that $$ \tag{1} \lim_{x\to\infty} \frac{|\mathcal{A} \cap x|}{x} = c > 0, $$ and define the ...
Joshua Stucky's 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
1 vote
1 answer
278 views

Least number coprime to a given integer

For a positive integer $n$ let $$f(n):=\min\{m\in \mathbb N: m>1, \gcd(m,n)=1\} .$$ Equivalently, $f(n) $ is the smallest prime not dividing $n$. Is there any upper bound literature for this? It is ...
Dr. Pi's user avatar
  • 2,949
3 votes
0 answers
228 views

Numbers made up of primes from a given set

Take a set $\mathcal P$ of primes and denote by $\langle \mathcal P\rangle $ the set of all natural numbers composed of primes from $\mathcal P$. If \[ \sum _{p\in \mathcal P}\frac {1}{p}\] converges ...
tomos's user avatar
  • 1,166
5 votes
0 answers
314 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
13 votes
1 answer
734 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
2 votes
0 answers
65 views

Order of magnitude on lower bounds for primes in intervals

I have been looking at the literature on sieve theory which proves theorems similar to the following: For all $x > x_0$ the interval $[x - x^{\theta}, x]$ contains prime numbers. For example, I ...
Bolton Bailey's user avatar
3 votes
0 answers
238 views

Counting twin primes with a sieve-like algorithm

The sequence A002822, denoted as $S$, represents all the twin primes except $\{3, 5\}$. Other than that exception, $k$ and $k+2$ are twin primes iff $(k+1)/6\in S$. Let $S(N)$ be the subset of $S$ ...
Vincent Granville's user avatar
5 votes
0 answers
124 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
6 votes
1 answer
597 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
11 votes
2 answers
709 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
8 votes
1 answer
220 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
-1 votes
1 answer
237 views

A number theoretical identity of exponential sum

I try to understand a number theoretical identity used by Jan-Christoph Schlage-Puchta in this answer. He defined the function $$S(\alpha)=\sum_{n\leq N}\Lambda(n) e(n\alpha)$$ where $\Lambda(n)$ is ...
user267839's user avatar
  • 6,000
3 votes
0 answers
167 views

Kubilius model in higher sieve dimension?

The Kubilius model, based on the fundamental lemma of sieve theory, let us approximate the probability of events depending on the variables $X_p$, $p\leq y$, where $X_p=1$ if $p|n$ ($n$ a random ...
H A Helfgott's user avatar
  • 19.3k
1 vote
1 answer
242 views

"Halfway" approach to Landau's 4th problem (special case of Bateman-Horn)

Landau's 4th problem asks if $n^2 + 1$ is prime for infinitely many $n \in \Bbb{Z}$. It is known that $n^2 + 1$ can only be divisible by Pythagorean primes, and that for any $p$ congruent to $1 \pmod ...
Rivers McForge's user avatar
3 votes
1 answer
176 views

Sieving by composite moduli

A traditional sieve gives a bound on the number of integers $n$ in an interval (say $I=[0,N]$) such that $$n\not\in S_p \mod p$$ for every prime $p$ in a set $\mathcal{P}$, where $S_p\subset \mathbb{Z}...
H A Helfgott's user avatar
  • 19.3k
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
0 votes
0 answers
187 views

Prime factors of $p-1$

It is one of the consequences of Sieve theory is that number of primes $p\leq x$ such that all prime divisors of $p-1$ are greater than $p^{\varepsilon},$ is $\gg \frac{x}{\log^2x}.$ In particular, ...
dragoboy's user avatar
  • 521
-3 votes
1 answer
371 views

References of research papers which lead to starting of Sieve Theory

Question - I am thinking to present one or two papers on Sieve Theory in my masters thesis. I will also present 3 other papers on Riemann Zeta Function which I have studied earlier . But I have no ...
Arnold's user avatar
  • 668
1 vote
0 answers
99 views

Sieve Theory uniform bound in Richert's Lectures on Sieves

I'm not sure how suitable this question is, but I have had no response on Mathematics Stack Exchange. My original question is here: https://math.stackexchange.com/questions/3402938/uniformity-...
VBACODER's user avatar
  • 111
0 votes
0 answers
175 views

Prime counting function estimate sieve of Eratosthenes-Legendre

I'm trying to arrive at estimate 1.17 (page 21) of Koukoulopoulos lecture notes [https://dms.umontreal.ca/~koukoulo/documents/notes/sievemethods.pdf] $$\#\{n \leq x : p|n \Rightarrow p > \sqrt{x}\}...
numbertheorylearner's user avatar
3 votes
1 answer
404 views

Primes with given Hamming weight

If I understand correctly, in the following thread Are There Primes of Every Hamming Weight? two users of the site claim that it has been already proven that, for every sufficiently large $n \in \...
Jamai-Con's user avatar
15 votes
1 answer
970 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
3 votes
0 answers
104 views

Friedlander-Iwaniec Flipping moduli

I am reading section 12 (Flipping Moduli) of the paper "The polynomial $X^2+Y^4$ captures its primes" by Friedlander and Iwaniec. At page 997, just below equation (12.7) we start estimating the ...
user133643's user avatar
3 votes
2 answers
353 views

Sieve bound for the sum of two squares

Let $$S(n) = \sum_{p \le n} b(n-p),$$ where $b(a)=1$ is $a$ is a sum of two squares of positive integers and $b(a)=0$ otherwise. Trivially by PNT we have $$S(n) \le \sum_{p \le n}1 \ll \frac{n}{\log n}...
toshi's user avatar
  • 130
5 votes
1 answer
183 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
2 votes
0 answers
118 views

Almost-prime values attained by polynomials, with extra conditions

Given integers $a_1,\ldots,a_k>0$ and $b_1,\ldots,b_k$, consider the polynomial $f(x) = \prod_{i=1}^{k} (a_i x +b_i) \in \mathbb{Z}[x]$. Suppose that $\{ a_i x+b_i\}_{i=1}^{k}$ are pairwise ...
Ofir Gorodetsky's user avatar
1 vote
0 answers
181 views

Sieving beyond threshold

This is a follow-up to the question here: Sum of divisors below threshold. User "Lucia" gave an excellent answer there, and probably the question below is very closely related. Still, since I am not ...
Kurisuto Asutora's user avatar
2 votes
1 answer
220 views

Sieving modulo non-prime residue classes

Let $n$ be a positive integer, and consider the set $\{1, \dots, n\}$. If we remove from this set all the numbers $a$ which satisfy $$ a \equiv 0 \mod d $$ for at least one divisor $d$ of $n$ (...
Kurisuto Asutora's user avatar
8 votes
1 answer
941 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