MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm new to sieve theory, and I'm trying desperately to understand Selberg's sieve. I would like to apply the sieve to give me a nice upper bound on primes of the set $$A^D(N)= \{ Dq-2 : q\in P, N/2 < q \leq N \} $$ But basically, for a fixed N, I would like $A^D(N)$ to be the set of elements of the form $Dq-2$ for a fixed positive integer $D$ and letting $p$ run through all primes between $N/2$ and $N$. Now, as I said, I'm trying to apply Selberg's sieve, but as I don't really know what I'm doing, I'm a bit confused. Now, if I understand it correctly could I then say that $$S(A^D(N),N/2,N/2) \leq \frac{\pi(N)-\pi(N/2)}{L_p(z)}+O \Big( \frac{z^2}{L_p(x)^2} \Big)$$ Where $S(A^D(N),N/2,N/2)$ is the number of elements of $A^D(N)$ which are prime and $$L_p(z)=\sum_{n\leq z}^{n\vert P} \frac{\mu(n)^2}{\phi(n)}.$$ where $$\frac{1}{\phi(n)}=\frac{1}{n}\prod_{p\vert n} \frac{1}{1-1/p}.$$ I got this from a pater called "Sketch of the Selberg Sieve method" By Sean Prendville (January, 2008) where he describes the Selberg Sieve not on $A^D(N)$ but on the set of all integers between some positive integer $x$, and $x+y$. I'm sure some of it is wrong, or that I totally misinterpreted, but I would like to know if this is right, and if it is, where do I go from here? (especially with dealing with $L_p$). I appreciate any help, but please keep in mind that I'm sixteen years old and live in the Bronx. As dumbed down as possible would be greatly appreciated..this is all new to me. Much appreciated, Alexis D. Botros

share|cite|improve this question
I can't help because (regarding sieve theory and other topics) I am pretty dumb too. My county library participates in a inter-library loan program; with that I could borrow Murty and Cojocaru's book on sieve methods. I think you might find it just barely accessible. If you can't find it online or available, write a response comment and I will see if there is something else that might help. Gerhard "Dumbing Down Is Our Pastime" Paseman, 2011.03.12 – Gerhard Paseman Mar 13 '11 at 5:05
Thanks. I appreciate it...I found it online. Will see what comes of it – Alex Botros Mar 13 '11 at 5:10
I suppose the real problem comes from the fact that $\phi(n)$ is used in the asymptotic approximation of the number integers in $(x, x+y]$ that are relatively prime to a certain integer. Therefore, if we switch from talking about consecutive integers, to integers in $A^D(n)$, then we must find a new asymptotic approximation to those elements of $A^D(n)$ relatively prime to a given integer. How in the heck is that going to work? How can we possibly estimate the number of integers in $A^D(n)$ that are relatively prime to a certain other integer? – Alex Botros Mar 13 '11 at 5:17
What does living in the Bronx have to do with anything? – Gerry Myerson Mar 13 '11 at 5:37
Alex: What Gerry's comment means is that your age (which you gave) helps people on this website know a suitable level at which to pitch an answer to you even though your age has nothing to do with math, but your location (which you also gave) doesn't really assist anyone in the same way. As an option other than Math Overflow, since you are in New York you could try to speak with someone in person at one of the math departments in New York, such as Columbia or the CUNY Graduate Center. – KConrad Mar 13 '11 at 7:41
up vote 0 down vote accepted

Getting an upper bound here is, at the level of research, a simple exercise. To do it the quickest way with least background, I'd suggest using the large sieve. Here you are essentially looking at estimating the number of integers between $N/2$ and $N$ which, modulo primes $r\leq \sqrt{N}$, are neither $0$ nor $2\bar{D}$, where $\bar{D}$ is the inverse of $D$ modulo $r$ (and the second condition drops if $r$ divides $D$). The large sieve inequality tells you that this number is bounded by $N/J$ where $J=\sum_{n\leq \sqrt{N}}\mu(n)^2\prod_{r\mid n}{2/(r-2)}$, with $2/(r-2)$ replaced by $1/(r-1)$ when there is a single condition modulo $r$ ($r$ is again restricted to primes). Getting a lower bound for $J$ is again standard number theory, but not obvious of course at first sight. One gets $J\gg (\log N)^2$ (the key reason behind the exponent $2$ is that there are two excluded classes modulo each prime $r$), and therefore the number you want to estimate is $\ll N/(\log N)^2$. It is also fairly easy to obtain a result uniform in terms of $D$ along these lines.

For references, I suggest an old survey of H. Montgomery, "The analytic principle of the large sieve", which is available online (Bulletin of the AMS, 1984), and I think googling reveals also a very good short write-up by B. Green.

share|cite|improve this answer
Thanks Denis, this is extremely helpful. – Alex Botros Mar 17 '11 at 2:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.