Questions tagged [sieve-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
2answers
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}}$$ ...