# Questions tagged [sieve-theory]

The sieve-theory tag has no usage guidance.

75
questions

**0**

votes

**0**answers

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

**-4**

votes

**1**answer

203 views

### References of research papers which lead to starting of Sieve Theory

A Bit of background of mathematics which I have studied ->
I have studied number theory from David M Burton and apostol introduction to analytic number theory and modular functions and dirichlet ...

**1**

vote

**0**answers

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

**0**

votes

**0**answers

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

**2**

votes

**0**answers

246 views

### Primes with given Hamming weight

If I understand correctly, in the following MO-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 \...

**13**

votes

**1**answer

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

**3**

votes

**0**answers

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

**2**

votes

**1**answer

160 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) \ll \sum_{p \le n}1 \le \frac{n}{\log n}...

**5**

votes

**1**answer

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

**2**

votes

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**1**answer

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

**8**

votes

**1**answer

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

**3**

votes

**1**answer

440 views

### Use of weights in the GPY's and Tao-Maynard's work on the twin prime conjecture

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

105 views

### Sieving the values of an arithmetic sequence which is infinitely many times $1$

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

228 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

**1**answer

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

**1**

vote

**1**answer

253 views

### Some questions about some examples in “sieve methods” in the book “Opera de Cribro” by Friedlander and Iwaniec

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

**5**

votes

**0**answers

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

**7**

votes

**1**answer

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

**2**

votes

**0**answers

139 views

### Lattice Sieving in Number Field Sieve

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

285 views

### Squarefree values of polynomials at prime arguments

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

**1**

vote

**1**answer

196 views

### Lattice Sieving

What are some good references for Lattice Sieving in Number Field Sieve? Could someone suggest some research papers in this area?(Theoretical and Computational Perspective)

**5**

votes

**1**answer

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

**4**

votes

**1**answer

154 views

### Shifted primes avoiding a set of divisors

Let $B$ be a set of positive integers such that $\sum_{b \in B} 1 / \varphi(b) < +\infty$, where $\varphi(\cdot)$ is the Euler's totient function. For any $y > 0$ put
$$\delta_y := \limsup_{x \...

**2**

votes

**1**answer

260 views

### Higher dimensional large sieve inequality

One of the most important achievements in analytic number theory is the establishment of the so-called large sieve inequality, which is formulated as follows. Let $\{a_n\}$ denote a finite sequence of ...

**2**

votes

**1**answer

124 views

### A sieve by not (necessarily) coprime integers

Let $\mathcal{A}$ be a nonempty set of pairwise coprime positive integers, and for each $a \in \mathcal{A}$ let $\Omega_a \subsetneq \{0, \ldots, a - 1\}$ be a set of residues modulo $a$. Furthermore, ...

**1**

vote

**1**answer

106 views

### Bounding the number of polynomials whose Galois group is a subgroup of the alternating group

In the article of DAVID ZYWINA https://pdfs.semanticscholar.org/cd50/c2d3fb0ce0c6a66ee629419b69165b30d5bc.pdf. It says that using $n$- dimensional large sieve, we can get the bound
|$\{$$ \ \ f(x)=x^...

**3**

votes

**0**answers

178 views

### Sum of multiplicative arithmetic function over squarefree numbers

In the "Sieve methods" notes of Dimitris Koukoulopoulos (see http://www.dms.umontreal.ca/~koukoulo/documents/notes/sievemethods.pdf), the following useful result can be found:
Theorem 0.4.1. Let $g$ ...

**3**

votes

**0**answers

84 views

### A sieve result with two parameters

I proved the following sieve result and - since the proof is quite long and I need to use it in a work - I am looking for a reference to it (or at least something from which it could be proved quickly)...

**3**

votes

**1**answer

146 views

### A sieve with two parameters

I am in need of a (relatively) general sieve with two parameters $y, z$. I am quite sure that on the literature there must be some result of the kind that I have in mind, probably a corollary of the ...

**1**

vote

**1**answer

161 views

### Best bound on $p, p+2k$ with $k$ fixed

Given some integer $k>0$, there are $O(x/\log^2 x)$ primes $p \le x$ such that $p+2k$ is also prime. It has been conjectured at least since Hardy-Littlewood that
$$
\pi_{2k}(x) \sim c_{2k}\int_2^x\...

**2**

votes

**0**answers

186 views

### Quasiprimes in arithmetic progressions

Let
$$\Lambda_z(n) = \sum_{d|n, d>z} \mu(d) \log(d/z).$$
As S. Graham proved in 1978,
$$\sum_{n\leq x} |\Lambda_z(n)|^2 \sim x \log(x/z).$$
provided $x\geq z$.
We also know that, by the large ...

**4**

votes

**0**answers

165 views

### Counting number of primes $p$ less than $x$ with certain constraints on prime divisors of $p-1$ for Artin's Conjecture on primitive root

I was reading this paper. There is a Lemma 1 saying that for a fixed prime $q$ the cardinality of the set $\{p \leq x \mid (\frac{q}{p})=-1\}$ such that all odd prime divisors of $p-1$ are greater ...

**9**

votes

**1**answer

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

**2**

votes

**1**answer

168 views

### Bounds for relative totient function for small values

Define $\phi(n,x)= \sum_{m\leq x,\gcd(m,n)=1} 1$, the number of elements in the interval $[1,x]$ that is relatively prime to $n$. $\omega(n)$ is the number of distinct prime factors of $n$.
It's not ...

**4**

votes

**1**answer

535 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

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

**1**

vote

**0**answers

59 views

### Sieving for points not on a conic and quadratic residues

Let
$$\displaystyle F(x,y,z) = \sum_{\substack{0 \leq i_1, i_2, i_3 \leq 2 \\ i_1 + i_2 + i_3 = 2}} a_{i_1, i_2, i_3} x_1^{i_1} x_2^{i_2} x_3^{i_3}$$
be a ternary quadratic form with integer ...

**3**

votes

**1**answer

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

**25**

votes

**1**answer

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

**4**

votes

**0**answers

116 views

### Large Gaps Between Almost Primes

What is the best lower bound for the longest interval contained in $[1,x]$ free of primes and products of two primes? In other words I am asking for the best lower bounds in a variant of the ...

**5**

votes

**2**answers

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

**12**

votes

**1**answer

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

**3**

votes

**1**answer

198 views

### Well-spacing of the roots of a quadratic congruence

On pages 956-957 of this paper, it is established that for any two $v_1, v_2$ satisfying $v_1^2 + 1 \equiv 0\operatorname{(mod} d_1), v_2^2 + 1\equiv 0\operatorname{(mod} d_2)$, $$\left\lVert \frac{...

**9**

votes

**0**answers

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

**11**

votes

**2**answers

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

**2**

votes

**1**answer

200 views

### Does this modification of the General Number Field Sieve factor integers?

The General Number Field Sieve
factors composite $n$ basically this way.
Select homogeneous polynomials with integer coefficients $f(x,y),g(x,y)$
s.t. $f(x,1),g(x,1)$ have common root modulo $n$ but ...

**4**

votes

**1**answer

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

**11**

votes

**2**answers

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