Questions tagged [sieve-theory]
Sieve theory deals with number theoretic sieves, and sifted sets. E.g. the Sieve of Eratosthenes, Brun sieve, and other modern sieves.
260
questions
-1
votes
0
answers
46
views
Is there a non-integer sieve? [closed]
Approaching a sieve as a discrete process rather than a filter for integers, is it called a sieve if sets of real numbers are filtered, or is this called something else?
Specifically, I'm looking at a ...
0
votes
1
answer
16
views
Help needed in deducing an inequality in a lemma in the proof of linnik's theorem.
I have been reading Sieve theory from notes of Zeev Rudnick here:http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html and I have a question on page 5 of lecture 14 here: http://www.math.tau.ac....
- 27
0
votes
0
answers
24
views
2 questions in the proof of Brun Titchmarch Inequality
This question is from lecture 13 of the notes of Sieve Theory here:http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html
I have 2 questions in the proof of lemma 2.2 on page 3:
Question 1 : I am ...
- 1,420
-2
votes
1
answer
48
views
Questions in theorem related to primes with fixed modulus
This question is from notes on sieve theory here:http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html.
I have questions in page 4 of lecture 12(http://www.math.tau.ac.il/~rudnick/courses/...
- 1,420
0
votes
0
answers
31
views
Reference request for books on Sieve Theory
For various reasons, I am hoping to study sieving methods some during this summer. My general goal would be to read a book on the topic, complete relatively large amounts of questions in my own, and ...
user1059480
1
vote
1
answer
49
views
2 questions in the theory of Counting Perfect Squares
I have been reading sieve theory from notes of zeev rudnick here :http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html and in page 2 of lecture 16(http://www.math.tau.ac.il/~rudnick/courses/...
- 1,420
2
votes
0
answers
20
views
van der Waerden's proof that a monic $p(x) \in \mathbb{Z}[x]$ has Galois group $S_n$ with probability 1
This paper mentions that van der Waerden proved some results on the density of monic integer polynomials with Galois group the symmetric group $S_n$ in 1936. I have found van der Waerden's original ...
- 3,516
0
votes
1
answer
42
views
Some questions in the proof of Analytic Large Sieve
I am learning about the analytic large sieve from the lecture notes here:http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html . I have some question in lecture 15:http://www.math.tau.ac.il/~...
- 1,420
0
votes
1
answer
31
views
Questions in proof of Arithmetic Large Sieve
I am studying Arithmetic Large Sieve from following notes of Zeev Rudnick:http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html
I have questions in lecture 14 here: http://www.math.tau.ac.il/~...
- 1,420
0
votes
1
answer
29
views
A question in proof of analytic large sieve
I have been reading Sieve theory from notes of Zeev Rudnick here:http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html and I have a question on page 5 of lecture 14 here: http://www.math.tau.ac....
- 1,420
0
votes
1
answer
50
views
A question in proof of Linnik's Theorem in Arithmetic Large Sieve
This question is from course notes in sieve theory and I am struck on this assertion in the proof of Linnik's theorem.
Consider Page 4 of lecture 14 here: http://www.math.tau.ac.il/~rudnick/courses/...
- 1,420
0
votes
0
answers
49
views
How to estimate S(z) in Arithmetic Large Sieve
This question is part of a proof in course in Sieve Theory( http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html, precisely lecture 11 and 14)and I am not able to prove this particular ...
- 1,420
0
votes
0
answers
19
views
Brun-Titchmarsh for semiprimes (or semi-primes)
We know, by Brun-Titchmarsh theorem and sieve methods that
$\pi(X+Y)-\pi(Y)\leq \frac{2X}{\log(X)}(1+o_X(1))$.
Do we know something for semiprimes? Like
$\pi_2(X+Y)-\pi_2(Y)\leq \frac{2X\log(\log(X))}{...
- 39
3
votes
1
answer
166
views
Estimating reducible monic polynomials of degree n with integer coefficients of height of atmost N
This question is from my assignment in Sieve Theory and I am struck on it. I am following following notes on Sieve Theory: http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html
Question: For a ...
- 1,420
3
votes
1
answer
53
views
Show that number of primes $p\leq x$ so that $2p+1$ is also a prime...
This question is from assignment 4 of the following sieve theory course: http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html
Question : Show that the number of primes $p\leq x$ so that $2p+1$ ...
- 1,420
0
votes
0
answers
29
views
Atkin sieve algorithm asymptotic analysis
In section 5 in Atkin sieve paper. I don't really understand his analysis of algorithm complexity.
He started with defining $\displaystyle W=12\left(\prod_{3<p\le \sqrt{\log N}}p\right)$ which is ...
0
votes
1
answer
48
views
What is meant by supported on prime numbers in this context?
I am reading Sieve - Theory from following lecture notes of Prof. Zeev Rudnick: http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html .
I am studying lecture 11 page 6.
But I think you will be ...
- 1,420
0
votes
1
answer
66
views
Why do sieves have the parity problem?
Sieve methods have the "parity problem".
Terry Tao gives a "rough" statement of the problem: If A is a set whose elements are all products of an odd number of primes (or are all ...
0
votes
0
answers
22
views
Lectures on Sieves by Motohashi - cannot see what equation is
I found these lecture notes on sieve theory by Motohashi: http://www.math.tifr.res.in/~publ/ln/tifr72.pdf
Equation 1.1.2 (page 16 of pdf) gives a congruence relation but it looks like some text is ...
6
votes
1
answer
155
views
On an approximation to Goldbach's conjecture
I've been recently reading Yuan Wang's paper on an approximation to Goldbach's problem, in which he showed that
Proposition 1: For all large even integer $x$, there exists $1<n<x-1$ such that $n(...
- 3,620
1
vote
2
answers
95
views
Landau's problem in sieve theory
In Tao's blog, one of Landau's problems is interpreted in the setting of sieve theory. More precisely, the twin prime conjecture leads to considering the following:
$A$ the set of prime numbers on $[...
- 491
1
vote
0
answers
39
views
On the derivation of the fundamental lemma of the combinatorial sieve
Let $b(d)$ be multiplicative function defined on squarefree numbers such that
$$
r_\mathcal A(d)=|\mathcal A_d|-{b(d)\over d}X
$$
relatively small, and $P(z)$ is the product of primes in $\mathcal P\...
- 3,620
0
votes
0
answers
105
views
Is there a "simple" way to factor particular integers using elementary curves?
Let l and m be consecutive integers, where l represents the floor of the square root of a whole number N that is not a perfect square. Are there any elementary curve structures that might allow l or m ...
- 23
1
vote
0
answers
81
views
Suggestions regarding these proofs
Severe humiliation by my university's staff notwithstanding, I have taken it upon me to investigate several problems in number theory, and I wrote down the results, see
https://www.researchgate.net/...
- 2,535
0
votes
1
answer
51
views
Prove that $\sum_{n \leq z} \frac{\mu(n)^2} { (\mu \star f)(n)} \geq \zeta(2) +O(1/z)$
This question is from Assignment 3 of following notes of Zeev Rudnick:http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html
Let $f(n)=n^2$. (a) Show that $(f\star \mu)(n)=n^2 \prod_{p|n} (1-\...
- 1,420
1
vote
1
answer
123
views
Square free values of polynomials on $\mathbb{Z}[x]$
Let $f(x) \in \mathbb{Z}[x]$ be a separable polynomial (i.e. with no repeated roots) of positive degree. Set $B := \gcd\{ f(n) : n \in \mathbb{Z}\}$ and let $B'$ be
the smallest divisor of $B$ so that ...
- 1,420
0
votes
1
answer
92
views
Density of Squarefree 1 degree polynomial
Let a > 0, b be coprime integers. Find the density of integers
n for which $an + b$ is squarefree.
This question is from assignment 2 of Zeev Rudnick's Lecture notes: http://www.math.tau.ac.il/~...
- 1,420
0
votes
3
answers
113
views
Prove that $\omega(n) \ll \frac{ \log n} {\log \log n}$
Let $\omega(n)$ the number of distinct prime divisors of an integer
n, so for instance $\omega(12) = 2$. Show that $\omega(n) \ll \frac{ \log n} {\log \log n}$.
This question is from assignment 2 of ...
- 1,420
0
votes
0
answers
30
views
Large sieve inequality for Farey fractions with only squarefree denominators.
When trying to deduce the arithmetic large sieve, I encountered the following step:
$$
\sum_{q\le Q}\mu^2(q)\sum_{\substack{a\le q\\(a,q)=1}}\left|S\left(\frac aq\right)\right|\le\sum_{q\le Q}\sum_{\...
- 3,620
1
vote
1
answer
116
views
Simple proof for a general Brun's upper bound sieve
Let $b(d)$ be the number of residue classes in $\mathcal A_d$ for squarefree integers $d$, and there's a positive number $X$ such that
$$
\left|\mathcal A_d-{b(d)\over d}X\right|\le b(d)
$$
Let $N_z$ ...
- 3,620
1
vote
2
answers
71
views
Eratosthenes-like sieves will always leave an infinite set of unsieved numbers
In this question I visualized the sieve of Eratosthenes as a series of combs whose teeth cover (i.e. eliminate) composite numbers. The $i$th comb has teeth spaced by $p_i$ and is positioned so that ...
- 6,181
1
vote
1
answer
76
views
A soft question about sieving
Please consider this a SOFT and very general question.
Ever since first being introduced to the Sieve of Eratosthenes (many decades ago) I have always visualized it as applying combs to the number ...
- 6,181
2
votes
0
answers
101
views
For calculating Collatz class records, how is the sieve constructed and used?
I'm looking at the class record algorithm here. I understand how some of the numbers (e.g. 8*k+5) can be skipped because they join with a lower number. But I don't understand exactly how the sieve of ...
- 329
1
vote
0
answers
37
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 < \...
- 1,923
1
vote
1
answer
136
views
Quadratic Sieve: Gaussian Elimination
I am reading the Quadratic Sieve algorithm from Silverman's mathematical Cryptography book.
I have understood almost everything in the algorithm except the part where he uses Gaussian Elimination to ...
- 331
1
vote
1
answer
36
views
A question related to inequality in Selberg Sieve
Consider these images related to Theory of selberg Sieve , taken from notes on Sieve theory Of Prof. Rudnick. http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html
Note: Earlier it was asked on ...
- 1,420
0
votes
0
answers
14
views
A question related to minimizing the variable in selberg sieve
I am studying about Selberg Sieve and I have a question regarding deriving an equation .
Consider S(x, z) = $\sum_{n \leq x} \delta ((gcd (n, P(z)) )$.
$P(z) = \prod_{p\leq z} p$, $\delta(m)$ = {1 if ...
- 1,420
0
votes
0
answers
81
views
A question related to a deducing a result related to degree of a polynomial
Consider the following expression.
$P* = \prod_{\deg P \leq \zeta} P$
So, $\deg P* = \sum\limits_{\deg P \leq \zeta} \deg P = \sum\limits_{j \leq \zeta } j π(j) $ .
I understand how $\deg P* = \sum\...
- 1,420
0
votes
1
answer
81
views
A question related to study of functions in Prime polynomial theorem
I am studying prime polynomial theorem from notes of a friend and I am unable to prove a lemma.
Let $F_{q}[t]$ be the ring of polynomials with coefficients in $F_q$ . Also, let $\pi_{q}(n) $ be the ...
- 1,420
2
votes
0
answers
39
views
sieve of Eratosthenes generalization to Dedekind domains or even PID's
I'm Interested in finding irreducibles in Dedekind domains, (and especially integer rings) in an efficient manner.
I've tried to look around a bit but found no papers on this (admittedly my paper ...
2
votes
1
answer
88
views
The sieving stage in quadratic sieve algorithm
I've been trying to figure out how sieving works in the quadratic sieve factorization algorithm.
Example: to factorize 90283. The ceil of the square root of 90283 is 301. We generate a sequence $x^{2}$...
- 63
3
votes
1
answer
195
views
Is it possible to come up with a formula for upper bound for this?
Consider a sieve, where the only numbers left are $n \equiv 5 mod (6)$
So the sieve has 5, 11, 17, 23...
Where the gap is uniform and is 6, initially.
Now we'll continue to sieve out the multiples of ...
user933694
0
votes
0
answers
54
views
A question on the derivation of Selberg's sieve
I am currently reading An Introduction to Sieve Methods and Their Applications by Cojocaru and Murty. In section 7.1, I became stuck on the following derivation:
Let $\lambda_d$ be a real sequence ...
- 3,620
1
vote
0
answers
64
views
Alternating sum of the reciprocals of the twin primes $\sum(\frac1p-\frac1{p+2})$
I ask if the limit of the alternating sum of the reciprocals of the twin primes
$$\sum_{p,\,p+2\,\in\,P}\Big(\frac1p-\frac1{p+2}\Big)=\frac13-\frac15+\frac15-\frac17+\frac1{11}-\frac1{13}\;+\;...=0....
- 1,806
3
votes
0
answers
60
views
Consecutive numbers removed by a sieve
This is a question about a particular sieve, which interests me because it has implications for twin primes. Consider primes of the form $p_i=6k_i \pm 1$. In a sequential manner, starting with $p_1=5$,...
- 6,181
3
votes
0
answers
55
views
How do the error terms in the Legendre Sieve become large?
I know I have made a mistake! But I can't figure out where, and I'm just hoping someone can explain where/why.
The Legendre Sieve, if we use the floor function, gives the formula
$$\pi_L(x) = \pi(x) - ...
- 1,356
1
vote
0
answers
22
views
On an inequality related to Selberg's sieve
I am reading section 9.3 of GTM206, which is about the derivation and application of Selberg's sieve, and I was stuck at proving
$$
\sum_{n\le x}\left(\sum_{d|(n,P_z)}\lambda_d\right)^2\le\sum_{d_1,...
- 3,620
1
vote
2
answers
135
views
Sieve of Eratosthenes - why can we begin marking off from the square of a number?
In the Sieve of Eratosthenes algorithm, whenever we identify a number $i$ as prime, we can mark off all numbers from $i^2$ to our limit $n$ as not prime, as opposed to starting from $2i$. How do we ...
0
votes
1
answer
38
views
is this prime probability function that generated from Eratosthenes Sieve can predict numbers of prime in closed interval?
I have two question regarding this prime probability $P(p)$ for $p$ that exists for $[p_{k-1}^2 , x]$
$P(p)=\prod^k_{i=1}\big{(} 1 -\frac{1}{p_i}\big{)}$
Where $x<p_k^2$ and $k$ was index such that ...
0
votes
2
answers
144
views
A slight generalization of the Sieve of Sundaram that might shed light on the $6n \pm 1$ phenomenon of sequence A002822.
There's the $n$ such that $6n \pm 1$ is a twin prime pair sequence: https://oeis.org/A002822
It contains all twin prime averages (divided by $6$) other than $4$.
Notice this sequence: Positive ...
- 19.2k