Questions tagged [sieve-theory]
The sieve-theory tag has no summary.
134 questions
2 votes
1 answer
265 views
Is $S_k(x)$ non-empty for all $k$ for sufficiently large $x$?
Let $x$ be large and $$ A = \{1,3,5,\dots,\le x\} $$ be the odd integers $\le x$. For each odd prime $p \le x$ and for each integer $k$, remove from $A$ all integers $$ n \equiv \frac{p-9}{2} \pmod p \...
- 23
0 votes
0 answers
66 views
Maximal length of pairwise-coprime blocks in $\lfloor f(n) \rfloor$ for $C^2$ functions
Let $\mathcal{F}$ be the class of $C^2$ functions $f: [1, \infty) \to \mathbb{R}$ satisfying $$f''(x) \to 0 \quad \text{and} \quad \limsup_{x \to \infty} |f'(x)| = \infty$$ Let $H(n)$ be a non-...
4 votes
0 answers
146 views
Partitioning an infinite sumset into primes and composites
Let $A = \{a_1, a_2, \ldots\}$ and $B = \{b_1, b_2, \ldots\}$ be infinite, strictly increasing sequences of natural numbers. Define $S_{ij} = a_i + b_j$. Question: Do there exist sequences $A$ and $B$ ...
0 votes
0 answers
48 views
Minimal `s` for Non-emptiness of Sieved Sets with Two Forbidden Residues Modulo Primes
I am investigating a sieve theory problem concerning the non-emptiness of sets defined by forbidding two residues modulo each prime in a specific set. The setup is as follows: Let $s$ be a positive ...
0 votes
1 answer
298 views
Euler product with asymptotic
In Polymath8b project there is that equation, Which I do not understand the steps. I tried to fix a j and factorise, $$\displaystyle S_j=\sum_{d_j,e_j}\frac{\mu(d_j)\mu(e_j)}{[d_j,e_j]{d_j}^s{e_j}^t} ...
- 45
1 vote
0 answers
164 views
New local sieve for factorization and definition of primes within [x ^ 2, (x+1) ^ 2) [closed]
Good day! I ask for your help – in investigating the twin prime conjecture, I am investigating a simple sawtooth function for the integer factorization of any natural number n = x ^ 2 + k in the range ...
1 vote
1 answer
225 views
Continuous large sieve inequality
In Tao's blog we can find this exercise: Let $[M,M+N]$ be an interval for some $M \in {\bf R}$ and $N > 0$, and let $\xi_1,\dots,\xi_J \in {\bf R}$ be $\delta$-separated. For any complex numbers $...
- 13
5 votes
0 answers
207 views
Sieving in the Gaussian integers
I asked this question as below a couple weeks ago in stackexchange but got no comments/answers, so I'll ask it here. (My understanding was that this is ok? Let me know if not). Question: Can anyone ...
- 1,564
7 votes
0 answers
421 views
Average of $\left(\frac{p}{q}\right)$ over $p\leq q^\epsilon$ for *most* $q$? (unconditionally)
Let $(\cdot/\cdot)$ be the Jacobi symbol. Consider the problem of showing that $(p/q)$ averages to $0$ as $p$ ranges over the primes $\leq q^\epsilon$, or some smaller range. For fixed $q$ (prime or ...
- 21.7k
2 votes
1 answer
181 views
On the error term in a result of Fouvry and Iwaniec
I am currently following the paper On a theorem of Bombieri-Vinogradov type by E. Fouvry and H. Iwaniec. They showed that when $f_z(n)$ is the characteristic function for integers free of prime ...
- 1,417
0 votes
0 answers
89 views
Complete list of functions known to satisfy the Siegel-Walfisz assumption
When I was reading Yitang Zhang's paper "Bounded Gaps between Primes" Text, on Page 1145, it is stated that "It should be remarked, by the Siegel-Walfisz theorem, that for all the ...
6 votes
1 answer
381 views
Prime number theorem via large sieve type sums
We know that the prime number theorem is equivalent to the statement $$ M(x)=\sum_{n\le x}\mu(n)=o(x). $$ By using Ramanujan sums, we can write $M(x)$ as $$ M(x)=\sum_{q\le x}\sum_{\substack{0\lt a\le ...
- 178
2 votes
1 answer
342 views
Sieve Method works for variant question?
There are multiple results on the sieve method, and I wanted to ask about the following variant (to know if it is trivial by one of the current versions of the sieve method, or seems a challenging ...
- 59
7 votes
1 answer
367 views
From $\Lambda_k$ and $\Lambda$ to $\mu$ (or $\lambda$)
Let $\{a_n\}_{n=1}^\infty$, $a_n \in \mathbb{C}$, $|a_n|\leq 1$. Let $\Lambda_k = \mu \ast \log^k$; in particular, $\Lambda_1$ equals the von Mangoldt function $\Lambda$. Suppose that we have ...
- 21.7k
7 votes
4 answers
951 views
Must bounded sequences be well-distributed to most *composite* moduli?
Let $\{a_n\}_{n=1}^N$, $|a_n|\leq 1$. Let $Q=\sqrt{N}$. Then $a_n$ is well-distributed modulo most prime $p\leq Q$, in the following sense: $$\sum_{p\leq Q} \frac{1}{p} \left(\frac{1}{N/p} \sum_{\...
- 21.7k
5 votes
1 answer
826 views
Sum of reciprocals of rough numbers
Let $x$ and $y$ be given real numbers. We may suppose that $2\leqslant x \leqslant y$ and that $u:= \log(y)/\log(x)$ remains bounded in a compact set away from $1$ as $x,y\to\infty$. An integer $n$ is ...
- 731
5 votes
2 answers
760 views
The twin prime problem and the Jurkat-Richert Theorem
Where does the Jurkat-Richert Theorem for linear sieves fail when applied to the twin prime problem? I'm reading the last two chapters of Additive Number Theory The Classical Bases. The Jurkat-...
user124163
0 votes
1 answer
297 views
Trying to understand last part of the proof of normalized prime gap
We know that $$\liminf_{n\to\infty}{\frac{p_{n+1}-p_n}{\log p_n}}=0.$$ I'm trying to figure out the proof and I have read a lot of documents, I asked a question here. Still I can't see what's going on....
- 45
4 votes
2 answers
619 views
Understanding the proof of Goldston–Pintz–Yíldírím's theorem
I hope this question fits the mission of this site. In "Primes in Tuples I" theorem 2 says, $$\liminf_{n\to\infty}{\frac{p_{n+1}-p_n}{\log p_n}}=0.$$ After a sieving progress you get $$h>\...
- 45
1 vote
1 answer
216 views
Are there infinitely many primes $p$ such that $p +2$ has at most two distinct prime factors?
using lower bound sieve, one can show that there are infinitely many prime $p$ such that $p+2$ has at most four distinct prime factors [Theorem 10.2.1, 1]. Has there been any improvement of the above ...
user124163
2 votes
0 answers
212 views
A Brun-Titchmarsh type result for divisor sums; asymptotic/improved bound
In Shiu's work ('A Brun-Titchmarsh theorem for multiplicative functions') he proved that if $r\le x$ is a natural number, we have $$\sum_{r<n\le x}d(n)d(n-r)\ll x\log^2x\sum_{d|r}\frac{1}{d}.$$ I ...
user344548
6 votes
0 answers
224 views
Fundamental lemma of sieve theory in function fields
Is there any literature concerning the fundamental lemma of sieve theory in $\mathbb{F}_q[T]$? In integers there are various versions of the lemma (bases on different sieves); I would be happy with ...
- 15.5k
1 vote
0 answers
67 views
How much does one have to study connected fields to understand modern sieve methods? [closed]
For example, If I'd want to read through the "Primes in tuples" and other works on the GPY sieve, how much analysis/group theory/analytic number theory do I need to know?
- 101
5 votes
1 answer
370 views
Density of primes $p$ where $p-1$ has a prime factor exceeding $p^{2/3}$
Fouvry proved* that primes $p$ such that the greatest prime factor, $q$, of $p-1$ is greater than $p^{2/3}$ have positive density in the primes. (The sequence is A073024 in the OEIS.) Are there any ...
- 9,379
2 votes
1 answer
220 views
Selberg sieve for counting monic irreducible $P \in \mathbb{F}_q[t]$ such that $P + K$ is also irreducible
In a 1983 paper by William Webb (link below), the author gives a version of the Selberg sieve for function fields and uses it to prove that for a fixed $K \in \mathbb{F}_q[t]$, the number $\mathcal{N}(...
- 23
1 vote
1 answer
318 views
Large sieve type inequality
Let $S_x(t)=\sum_{n\le x} a_n e(nt)$, where $e(x)=e^{2\pi i x}$. Then, the large sieve inequality tells us that $$ \sum_{q\le Q} \sum_{\substack{0\lt a \lt q \\ (a,q)=1}}|S_x(a/q)|^2 \le (Q^2+4\pi x)\...
- 178
1 vote
0 answers
170 views
Counting prime factors of polynomial functions
Let $\Omega(n)$ denote the number of prime factors (counted with multiplicity) of a non-zero integer $n$. For $f \in \mathbb Z[X]$ non-zero, let $$m(f) = \liminf_{n \to \infty} \Omega(f(n))$$ (1) Is $...
- 12.3k
4 votes
2 answers
335 views
Sum of $\frac{1}{(\delta_1,\delta_2)}$ with congruence restrictions
In the course of my work, I encountered the following sum ($(x,y)$ stands for the GCD of $x$ and $y$): $$L(Q)=\sum_{\substack{\delta_1,\delta_2\leq Q\\\delta_1\equiv0\ (a)\\\delta_2\equiv0\ (b)}}\frac{...
- 41
8 votes
1 answer
403 views
Density of extended Mersenne numbers?
Consider the subset of odd positive integers defined and constructed as follows by these rules : A) $1$ is in the set. B) if $x$ is in the set , then $2x + 1$ is in the set. C) if $x$ and $y$ are in ...
- 799
1 vote
1 answer
202 views
Functor whose essential image is a cosieve?
Definitions An object $d \in Obj(\mathcal D)$ is in the essential image of $F$ if there exists some $c \in Obj(\mathcal C)$ such that $d \cong F c$. A sieve in $\mathcal D$ is a full subcategory of $\...
- 521
3 votes
0 answers
119 views
Divisor of given order in short intervals
Is the following Open question or Conjecture already known, or eventually settled ? Open question : For sufficiently large $x$ there is at least a positive integer in the interval $[x,x+\log^2(x)]$ ...
- 523
1 vote
0 answers
94 views
Upper bound for the number of coprimes to primes below $x$ in an arbitrary interval of length $x$?
Let $\mathcal{E}$ be a subset of the primes up to $x^{{1/2}-o(1)}$ and let $S(T,T+x;\mathcal{E})$ be the number of integers in the interval $(T,T+x]$ that are coprime to the primes in $\mathcal{E}$. ...
- 965
3 votes
1 answer
370 views
Best available bounds for $\pi(Y)-\pi(Y-X)$?
I don't know much (anything) about sieves, but as I read the section on the Selberg upper bound sieve from Greaves's Sieves in Number Theory, there is a theorem 4 which says that If $Y\ge X \ge 2$, ...
- 107
0 votes
0 answers
513 views
Relation between sieve wheel and Sundaram sieve
I made this sieve for prime numbers, which I briefly describe: We consider $\quad p=r+modulus \cdot k \quad$ with $\quad modulus=p_1*p_2* \cdots *p_m$ and then we choose an appropriate reduced ...
- 199
1 vote
0 answers
121 views
Large sieve inequality-like sum without the square
Let $S(\alpha) = \sum_{n\leq N} w(n) e^{2\pi i \alpha n}$ for some function $w$ defined on $\mathbb{R}$. Suppose $\alpha_1, \ldots, \alpha_R$ are real numbers that are $\delta$-spaced modulo $1$, for ...
- 579
0 votes
0 answers
73 views
On the upper bound estimation of $D(N)$ in Chen Jingrun's theorem
What are the current research results on the estimation of the upper bound of $D(N)$ in Chen Jingrun's theorem? Including but not limited to Chen Jingrun's improvement 7.8342 and Wu Jie's improvement ...
- 1
3 votes
1 answer
309 views
What fraction of the values of a quadratic polynomial can be prime?
I have an explicit, monic quadratic polynomial $P(x)$ and an integer $m$. Can I bound the number of prime values in $P(0), P(1), \ldots, P(m)$? A reference would be appreciated, if available. An ...
- 9,379
10 votes
1 answer
1k views
Status of current research in Sieve Theory
I have done a course in Sieve Theory from the notes of Prof. Rudnick. Before this, I did 2 courses in Number Theory from the 2 volumes of Apostol. I don't have any guidance by professor as I am living ...
- 821
5 votes
2 answers
768 views
Specific application of Cauchy-Schwarz and Large Sieve
Im reading a paper by Matomaki here, and the following is stated (I'm paraphrasing): "By the Cauchy-Schwarz inequality and the large sieve, we have $$\sum_{q \leq Q}\frac{q}{\phi(q)}\sum_{\...
- 153
2 votes
1 answer
315 views
Sieve theory through variational principles
Disclaimer: I'm just starting to read Sieve Methods by Halberstam and Richert, so my present knowledge of the subject is close to zero, but it made me wonder if some connection to physics could exist, ...
- 7,000
2 votes
0 answers
313 views
Conjecture on a sieve of Flavius Josephus
Flavius Josephus's sieve: Start with the natural numbers; at the $k$-th sieving step, remove every $(k+1)$-st term of the sequence remaining after the $(k-1)$-st sieving step; iterate. Some examples: ...
user231922
14 votes
1 answer
477 views
Unpublished result of Rosser in Sieve Methods book
Erdős and Selfridge (1971) state that the following is "implied by an unpublished result of Rosser" which they claim appears in a forthcoming book on sieve methods by Halberstam and Richert. ...
- 25.2k
5 votes
1 answer
256 views
Remainder terms of congruence sums in sets of positive density
Let $\mathcal{A} \subset \mathbb{N}$ be an infinite sequence with positive density, in the sense that $$ \tag{1} \lim_{x\to\infty} \frac{|\mathcal{A} \cap x|}{x} = c > 0, $$ and define the ...
- 2,142
12 votes
2 answers
1k views
Are there are any attempts utilising sieve theory to attack the general $a p \pm 1$ problem?
It is currently an open question if there are infinitely many primes $p$ such that $2p + 1$ is prime (Sophie Germain primes) or that at least one of $24p \pm 1$ is prime. Could Zhang's method, or the ...
- 541
3 votes
2 answers
604 views
Least number coprime to a given integer
For a positive integer $n$ let $$f(n):=\min\{m\in \mathbb N: m>1, \gcd(m,n)=1\} .$$ Equivalently, $f(n) $ is the smallest prime not dividing $n$. Is there any upper bound literature for this? It is ...
- 3,082
3 votes
0 answers
255 views
Numbers made up of primes from a given set
Take a set $\mathcal P$ of primes and denote by $\langle \mathcal P\rangle $ the set of all natural numbers composed of primes from $\mathcal P$. If \[ \sum _{p\in \mathcal P}\frac {1}{p}\] converges ...
- 1,564
5 votes
0 answers
365 views
Counting primes, twin primes, cousin primes: unusual approach, connection to some conjectures
I am investigating the following sieve-like algorithm. Let $S_N=\{1,\dots,N\}$. For all primes $p$ with $p_0\leq p \leq M$, we remove from $S_N$ the following elements: all numbers $n\in S_N$ such ...
- 3,158
13 votes
1 answer
845 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 < \...
- 253
2 votes
0 answers
93 views
Order of magnitude on lower bounds for primes in intervals
I have been looking at the literature on sieve theory which proves theorems similar to the following: For all $x > x_0$ the interval $[x - x^{\theta}, x]$ contains prime numbers. For example, I ...
- 121
3 votes
0 answers
275 views
Counting twin primes with a sieve-like algorithm
The sequence A002822, denoted as $S$, represents all the twin primes except $\{3, 5\}$. Other than that exception, $k$ and $k+2$ are twin primes iff $(k+1)/6\in S$. Let $S(N)$ be the subset of $S$ ...
- 3,158