# Questions tagged [sieve-theory]

The sieve-theory tag has no usage guidance.

**3**

votes

**0**answers

89 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

113 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

109 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

90 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

146 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

122 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

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

**2**

votes

**1**answer

387 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

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

**7**

votes

**0**answers

209 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

234 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

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

**4**

votes

**0**answers

117 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

284 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

129 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

234 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

167 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

192 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

136 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

206 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

110 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

105 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

149 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

80 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

133 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

143 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

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

**1**

vote

**0**answers

97 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

281 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

161 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

427 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

368 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

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

**24**

votes

**1**answer

743 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

110 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

210 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

679 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

194 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

352 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

451 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

182 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

501 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

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

**14**

votes

**1**answer

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

**7**

votes

**2**answers

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

**3**

votes

**0**answers

547 views

### Ramanujan conjecture and covariance of Kloosterman sums

There has been interest in moments and covariances/correlations of Kloosterman sums $S(m,n,c)=\sum_{ad=1\ (\text{mod}\ c)} e(\frac{ma+nd}{c})$ like
$\sum_{m\in\mathbb F_c} S(m,n,c)^k$, $\sum\sum_{m_1,...

**4**

votes

**1**answer

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

**6**

votes

**0**answers

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

**1**

vote

**0**answers

114 views

### Sieving question

How many integers $n\leq X$ are there with the property that $\prod_{p\in S} p \geq n^{1/2-\epsilon}$? Here (to keep notation readable) I've written $p\in S$ if and only if $p||n$ (that is, $p|n$ and $...