# Questions tagged [sieve-theory]

The sieve-theory tag has no usage guidance.

The sieve-theory tag has no usage guidance.

103
questions

1
vote

0
answers

41
views

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}$. ...

3
votes

1
answer

233
views

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$, ...

0
votes

0
answers

181
views

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 ...

1
vote

0
answers

66
views

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 ...

0
votes

0
answers

48
views

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 ...

2
votes

1
answer

143
views

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 ...

9
votes

1
answer

454
views

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 ...

5
votes

2
answers

626
views

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_{\...

2
votes

1
answer

210
views

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, ...

0
votes

0
answers

121
views

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:
...

14
votes

1
answer

313
views

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.
...

4
votes

1
answer

189
views

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 ...

10
votes

0
answers

266
views

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 ...

1
vote

1
answer

205
views

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 ...

3
votes

0
answers

219
views

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 ...

5
votes

0
answers

268
views

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 ...

13
votes

1
answer

669
views

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 < \...

2
votes

0
answers

59
views

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 ...

3
votes

0
answers

218
views

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$ ...

5
votes

0
answers

118
views

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&...

6
votes

1
answer

500
views

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 ...

11
votes

2
answers

640
views

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$. ...

8
votes

1
answer

206
views

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 $\...

-1
votes

1
answer

219
views

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 ...

3
votes

0
answers

156
views

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 ...

0
votes

1
answer

199
views

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 ...

3
votes

1
answer

160
views

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}...

11
votes

2
answers

953
views

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 ...

0
votes

0
answers

130
views

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, ...

-3
votes

1
answer

348
views

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 ...

1
vote

0
answers

92
views

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-...

0
votes

0
answers

150
views

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}\}...

3
votes

1
answer

389
views

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 \...

14
votes

1
answer

841
views

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 ...

3
votes

0
answers

101
views

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 ...

3
votes

2
answers

286
views

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}...

5
votes

1
answer

166
views

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 ...

2
votes

0
answers

116
views

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 ...

1
vote

0
answers

176
views

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 ...

2
votes

1
answer

183
views

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$ (...

8
votes

1
answer

752
views

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 ...

3
votes

1
answer

534
views

I am going through James Maynard's paper, Small Gaps between Primes, and have a number of questions regarding his approach. First, I am wondering why uses weights in his approach. While I generally ...

2
votes

0
answers

111
views

I have a sequence of positive integers $a_n$ which assumes infinitely many times the value $1$. I want to estimate the cardinality of the following set:
$$\#\{n\leq x : a_n>1 \text{ and } (a_n, \...

8
votes

0
answers

235
views

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

1
answer

293
views

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....

1
vote

1
answer

303
views

I am reading the book "Opera de Cribro - John B. Friedlander, Henryk Iwaniec" and in pages 5,6 I do not understand why and how they chose $X$, $A(x)$, $A_d(x)$, $g(p)$ and $r_d(x)$.
any hints will be ...

6
votes

0
answers

184
views

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) ...

7
votes

1
answer

431
views

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 ...

2
votes

0
answers

154
views

I am currently going through Pollard's article on Lattice Sieving and have a few confusions. Firstly, how to figure that $C$ and $D$ in the two-dimensional array so that every $(c,d)$ pair corresponds ...

3
votes

1
answer

325
views

This is a reference request.
Assume that $f_1,\ldots,f_r \in \mathbb{Z}[t]$ are non-zero linear polynomial.
Letting $\mu$ be the M\"{o}bius function, is there any work on
$$ \sum_{p\leq x} \prod_{i=...