# Some questions about some examples in “sieve methods” in the book “Opera de Cribro” by Friedlander and Iwaniec

I am reading the book "Opera de Cribro - John B. Friedlander, Henryk Iwaniec" and in pages 5,6 I do not understand why and how they chose $X$, $A(x)$, $A_d(x)$, $g(p)$ and $r_d(x)$.

any hints will be appreciated.  • We need more context to be able to answer your question. What do you know about the symbols $X,A(x),A_d(x),g(p),r_d(x)$ in general? Do you know the relationship between them? Do you know what Friedlander and Iwaniec have said about their purposes? – Greg Martin Jan 13 '18 at 19:24
• @GregMartin, I uploaded a few pages, you may see it here: docdro.id/H2A9YOC – asad Jan 14 '18 at 4:48
• I'm not referring to context in the book. I'm referring to context in terms of how much you understand already and what's the first thing you don't understand. It's not reasonable to expect us to explain entire pages of a research monograph; you should boil your question down to "here's what I do understand, and here's the first thing I don't understand". – Greg Martin Jan 14 '18 at 7:00
• @GregMartin, For instance with $A_d(x)$, I confuse with other literature such as Halberstam, Greaves, Cojocaru: I see that they define $\mathcal{A}_d=\{a: a\in\mathcal{A},\ a\equiv0(\mod d)\}$, but in "Opera de Cribro" it is defined as $\mathcal{A}_d=\{a_n: a_n\in\mathcal{A},\ n\equiv0(\mod d)\}$. Although the $\bigcup_{i=0}^{d-1}\mathcal{A}_d$ are the same in both definitions but individually are not! – asad Jan 14 '18 at 15:21
• continue from the previous comment: ... individually are not the same in general. – asad Jan 14 '18 at 15:29

Your questions are answered by (1.2) and the preceding display in the book along with the surrounding text. In the specific examples that you ask about, $A(x)$ is the number of elements of $\mathcal{A}$ up to $x$, while $A_d(x)$ is the number of elements of $\mathcal{A}$ up to $x$ that are divisible by $d$. Once you know $A_d(x)$, you need to approximate it reasonably with an expression of the form $g(d)X$, where $g(d)$ is a multiplicative function independent of $x$. In particular, $X\approx A(x)$, since $g(1)=1$. Finally, $r_d(x)$ is the error of your approximation, so that $A(x)=g(d)X+r_d(x)$ as (1.2) states. Apriori, you can choose $g(d)$ and $X$ arbitrarily, but you need some bounds on $r_d(x)$ in order to sieve $\mathcal{A}$ efficiently.
• thanks, but I did not get it yet, for instance why they chose $g(2)=1/2$ and $g(p)=2/p$, and $X=\sqrt{x}$ – asad Jan 14 '18 at 4:52
• @asad: $A(x)$ equals the integral part of $\sqrt{x-1}$, which explain their choice $X=\sqrt{x}$. The number of solutions of the congruence $m^2+1\equiv 0\pmod{p}$ equals $1$ when $p=2$, equals $2$ when $p\equiv 1\pmod{4}$, and equals $0$ when $p\equiv 3\pmod{4}$. Therefore $A_p(x)/\sqrt{x}$ tends to $1/2$ when $p=2$, tends to $2/p$ when $p\equiv 1\pmod{4}$, and tends to $0$ when $p\equiv 3\pmod{4}$. This explains their choices of $g(p)$, since the idea is that $A_p(x)\approx g(p)X$. – GH from MO Jan 14 '18 at 13:19