The tag has no usage guidance.

learn more… | top users | synonyms

3
votes
1answer
302 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 ...
22
votes
1answer
459 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
81 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 ...
4
votes
2answers
151 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 ...
10
votes
1answer
470 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 ...
4
votes
1answer
180 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 ...
9
votes
0answers
291 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 ...
11
votes
2answers
424 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$. ...
1
vote
1answer
126 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
311 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 ...
10
votes
2answers
485 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}}$$ ...
13
votes
1answer
639 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
2answers
656 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 ...
3
votes
0answers
210 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$, ...
5
votes
0answers
116 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
0answers
87 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 ...
6
votes
0answers
310 views

$x^2+1$ attaining almost prime values

Iwaniec, using the linear sieve, proved that $n^2+1$ can be a product of at most two primes infinitely often and furthermore a lower bound of the correct order of magnitude for the number of such ...
7
votes
1answer
576 views

Is this weak asymptotic Goldbach's conjecture open?

Let $\tau(x)$ be the number of even numbers $2<2n<x$ which can't be written as a sum of two primes. Goldbach's conjecture: $\tau(x) = 0$ Asymptotic Goldbach's conjecture: $\tau(x) = O(1) $ ...
2
votes
1answer
430 views

Proof of the Friedlander–Iwaniec theorem

Does anybody know where I could find the proof of the Friedlander–Iwaniec theorem. The link that I find when I search for it is http://www.pnas.org/content/94/4/1054.full.pdf+html, but this seems more ...
0
votes
0answers
213 views

Relationship between this conjecture and Lehmer's Theorem?

Let A be: n such that $\ \frac{n-1}{ord_n 2}=2^x\ $ and $n$ with the conditions of the conjecture in OEIS A226014,$\ n \in \mathbb{Z^+} ,\ x \in \mathbb{Z}_{\geq 0},\ $then $n$ is prime ...
14
votes
2answers
220 views

S integral points of an elliptic curve, with S of positive density

Let E be an elliptic curve over Q of non-zero rank. Let S be the union of the primes of bad reduction of E with a Chebotarev set [1]. Suppose additionally that S has density strictly less than one. ...
3
votes
1answer
341 views

An introduction to sieve method and their application, Cojocaru & Murty

On page 188. Lemma 10.2.3 is $\sum_{\substack{\delta \leq x \\ 2 \nmid \delta}}\frac{\mu^{2}(\delta)}{\phi_{1}(\delta)} = A_{1}log(x) +A_{2} + O(\frac{1}{x^{1/4}})$ for positive $A_{1}$, $A_{2}$. ...
10
votes
1answer
466 views

Does the Maynard-Tao Theorem apply to general tuples of linear forms?

In the paper http://arxiv.org/pdf/1311.5319v1.pdf the author states the following theorem, which he attributes to Maynard and Tao. For any integer $m > 2$, there exists an integer $k = k(m)$ such ...
15
votes
3answers
959 views

What is a sieve and why are sieves useful?

I have been trying to understand what is exactly a sieve and why sieves are useful. I have read Wikipedia articles about sieve theory but they don't provide a definition of what is a sieve or why they ...
7
votes
1answer
353 views

Are primes of density 0 in $a\cdot b^n+c$?

Hooley proves in Applications of Sieves to the Theory of Numbers that there are only $o(x)$ numbers $n\le x$ such that $n\cdot2^n+1$ is a (Cullen) prime. The proof generalizes to forms ...
4
votes
0answers
111 views

On a weighted sum in a lemma for sieve methods

I'm reading James Maynard's paper "Small gaps between primes". Lemma 6.1 (p.14) in this paper confused me. This lemma was taken from Goldston-Graham-Pintz-Yildirim's paper "Small gaps between ...
9
votes
0answers
419 views

Sieve bound for prime $k$-tuples

Let $d_1<d_2<\dots<d_k$ be integers. Then the number of integers $n\leq x$, such that $n+d_1, n+d_2, \ldots, n+d_k$ are simultaneously prime, is bounded above by $$ \mathfrak{S}(d_1, \ldots, ...
2
votes
0answers
150 views

Best known Upper bound on Twin Primes [duplicate]

I know that there is a result from J Wu that the number of twin primes less than a given magnitude $N$ does not exceed $$\frac{2aCN}{\log^2{N}}$$ Where $C=\prod \frac{p(p-2)}{(p-1)^2}$ and $a$ is ...
7
votes
1answer
1k views

A reformulation of the Riemann Hypothesis

I am studying Sieve theory from Iwaniec's notes. I have come across a theorem which estimates $\varphi(x,N)=\#\{1\leq n \leq x:(n,N)=1\}$, where $N$ is product of distinct primes. Let's define ...
26
votes
1answer
1k views

Does a proof of Selberg's 3.2 inequality exist?

A well-known inequality of Montgomery and Vaughan (generalizing a result of Hilbert) states that $$ \left |\sum_{r \neq s} \frac{w_{r} \overline{w_{s}} }{\lambda_r - \lambda_s} \right| \leq \pi ...
12
votes
1answer
771 views

Least prime in an arithmetic progression and the Selberg sieve

My question concerns a technical step in the proof of Linnik's theorem on the least prime in an arithmetic progression, as presented in Chapter 18 of Iwaniec-Kowalski: Analytic number theory. The ...
5
votes
1answer
273 views

Large gaps between P2s

Gaps between consecutive primes are $O(n^{\theta+\varepsilon})$ for $\theta=0.525$ and any $\varepsilon>0.$ I was wondering if a better result is known for gaps between numbers with at most two ...
23
votes
3answers
959 views

Are sets with similar asymptotic behavior as the primes necessarily finite additive bases?

The set of primes $\mathbb{P}$ has many interesting properties in additive number theory and some of the most famous open problems about $\mathbb{P}$ are the well-known Goldbach's strong and weak ...
2
votes
1answer
256 views

10 factors for x^2 coefficient in quadratic sieve?

I wrote a quadratic sieve and I tried plugging in all the same parameters as the wikipedia article says msieve uses: http://en.wikipedia.org/wiki/Quadratic_sieve#Parameters_from_realistic_example It ...
7
votes
1answer
735 views

Best possible sieves for the jacobsthal problem, linear programming, and the prime 2

Background/Motivation Gerhard Paseman asked a question about bounds on the Jacobsthal function a while ago, which made me curious about whether the known bounds are best possible. Briefly, the ...
16
votes
6answers
3k views

Erik Westzynthius's cool upper bound argument: update?

Version 2 of this writeup is available, and includes a newer and simple upper bound thanks to MathOverflow 88777 as well as indirect references to future writeups. Details of further work ...