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.

Filter by
Sorted by
Tagged with
-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 ...
user avatar
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....
user avatar
  • 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 ...
user avatar
  • 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/...
user avatar
  • 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 ...
user avatar
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/...
user avatar
  • 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 ...
user avatar
  • 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/~...
user avatar
  • 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/~...
user avatar
  • 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....
user avatar
  • 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/...
user avatar
  • 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 ...
user avatar
  • 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))}{...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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(...
user avatar
  • 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 $[...
user avatar
  • 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\...
user avatar
  • 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 ...
user avatar
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/...
user avatar
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-\...
user avatar
  • 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 ...
user avatar
  • 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/~...
user avatar
  • 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 ...
user avatar
  • 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_{\...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 < \...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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}$...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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....
user avatar
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$,...
user avatar
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) - ...
user avatar
  • 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,...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar

1
2 3 4 5 6