In the development of the large sieve, leading to its arithmetic applications, there is one step which — I must admit shamefully — I never completely understood as a natural argument instead of one with a somewhat mysterious clever trick. Or, at least, until now: just this week-end, one vaguely related thing leading to another, I’ve just stumbled on a very transparent proof of this result.<\/p>\n
I’ve written a short note with the details<\/a>, but here is the outline. For background, it may be useful to read my earlier post on the subject<\/a> on T. Tao’s blog, though I’ll use the classical setting of the sieve for integers below (as I did in the note, although it extends mutatis mutandis<\/em> to the general setting described in my recent book<\/a>).<\/p>\n The point is to provide the link between the analytic<\/em> and arithmetic<\/em> large sieve inequalities. The first one of these is the inequality<\/p>\n $latex (*)\\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\sum_{q\\leq Q}{\\sum_{(a,q)=1}{|\\sum_{n\\leq N}{a_n\\exp(2i\\pi na\/q)}|^2}}\\leq (N-1+Q^2)\\sum_{n\\leq N}{|a_n|^2}$<\/p>\n which is valid for all complex numbers (an<\/sub>)<\/em>; here the sum over a<\/em> is over all residue classes modulo q<\/em>, coprime with q<\/em>, and the resulting exponential is independent of the choice of representatives of those classes. This inequality is discussed in great detail in Montgomery’s survey article<\/a>; I’ll just say here that the constant N-1+Q2<\/sup><\/em>, which is not particularly easy to obtain, is of no importance for our purpose, and I will just write<\/p>\n $latex \\Delta=N-1+Q^2$<\/p>\n below to emphasize this.<\/p>\n The second inequality, the arithmetic large sieve inequality,<\/em> states that, for any choice of subsets \u256c\u00aep<\/sub><\/em> for primes p<\/em>, we have<\/p>\n $latex (**)\\ \\ \\ \\ \\ \\ \\ \\ \\ \\ |\\{n\\leq N\\ |\\ n\\ \\text{mod}\\ p\\ \\notin \\Omega_p\\ \\text{for}\\ p\\leq Q\\}|\\leq \\Delta H^{-1}$<\/p>\n where<\/p>\n $latex H=\\sum_{q\\leq Q}{\\mu(q)^2\\prod_{p\\mid q}{\\frac{|\\Omega_p|}{p-|\\Omega_p|}}}.$<\/p>\n This is thus, recognizably, a sieve estimate: we bound from above the number of integers remaining in a segment after removing all those which fail to satisfy some constraints on their reductions modulo primes, constraints which are imposed for all primes p<\/em> up to Q<\/em>. This Q<\/em> is a parameter which is adjusted for applications, depending on N<\/em>.<\/p>\n —————————————————————–<\/p>\n Example.<\/strong> If sieve is completely unfamiliar, here is one of the most traditional examples: let \u256c\u00aep<\/sub><\/em> be the residue classes 0 and -2 modulo p<\/em>. Among the integers surviving the sieve process are then all prime numbers r<\/em> larger than Q<\/em> such that r+2<\/em> is also prime. Hence the arithmetic large sieve inequality implies an upper bound<\/em> for the number of twin primes up to N<\/em>, namely<\/p>\n $latex \\pi_2(N)\\leq \\Delta H^{-1},\\ \\ \\ \\ \\ \\text{where}\\ \\ \\ \\ \\ H=\\sum_{q\\leq Q}{\\mu(q)^2\\prod_{p\\mid q}{\\frac{2}{p-2}}}$<\/p>\n (where in fact the coefficients 2 must be replaced by 1 when p=2<\/em>).<\/p>\n Using elementary techniques (see this treatment by Ben Green<\/a> for example), or general results on sums of multiplicative functions, it follows that<\/p>\n $latex H\\geq c(\\log Q)^2$<\/p>\n for Q> 2<\/em> and some constant c>0<\/em>. This leads to an estimate for the number of twin primes which is (conjecturally) of the right order of magnitude<\/p>\n $latex \\pi_2(N)\\ll \\frac{N}{(\\log N)^2}$<\/p>\n and by a partial summation, to the (weaker, but still spectacular) conclusion that the series of inverses of twin primes converges:<\/p>\n $latex \\sum_{p,p+2\\ \\text{primes}}{\\frac{1}{p}}<+\\infty,$<\/p>\n which was one of V. Brun’s first achievements in building the beginnings of the modern theory of sieve methods in the early 20th Century.<\/p>\n ————————————————————————–<\/p>\n So I will now describe how to derive (*) from (**). Or rather, I will derive (**) from the dual inequality<\/em><\/p>\n $latex (***)\\ \\ \\ \\ \\ \\ \\sum_{n\\leq N}{|\\sum_{q\\leq Q}{\\sum_{(a,q)=1}{\\beta(q,a)\\exp(\\frac{2i\\pi na}{q})}}|^2}\\leq \\Delta\\sum_{q\\leq Q}{\\sum_{(a,q)=1}{|\\beta(q,a)|^2}}$<\/p>\n where the complex coefficients \u256c\u2593(q,a)<\/em> are still arbitrary, and \u256c\u00f6<\/em> has the same value as before. The equivalence of (*) and (***) is a consequence of the elementary duality theory in finite-dimensional Hilbert spaces. But more importantly, (*) is often proved by means of (***) and this duality principle; in more general contexts, this is because (***) is usually easier to approach. So it is a natural starting point to argue towards the arithmetic inequality (**).<\/p>\n But before we begin, a notational convention: below, q<\/em> (and sums over q<\/em>) will always refer to squarefree (positive) integers.The idea is quite simple, in particular if you’ve ever seen the Chebychev inequality in probability: let S<\/em> denote the sifted set<\/p>\n $latex S=\\{n\\leq N\\ |\\ n\\ \\text{mod}\\ p\\ \\notin \\Omega_p\\ for\\ p\\leq Q\\}$.<\/p>\n Comparing with the structure of (***), we are going to describe an “amplifier” A(n)<\/em> which is of the form<\/p>\n $latex A(n)=\\sum_{q\\leq Q}{\\sum_{(a,q)=1}{\\beta(q,a)\\exp(\\frac{2i\\pi na}{q})}}$<\/p>\n and has the property that |A(n)|<\/em> is “large” whenever n<\/em> is in S<\/em>. If we have<\/p>\n $latex |A(n)|\\geq B,$<\/p>\n for n<\/em> in S<\/em>, then by positivity we deduce<\/p>\n $latex B^2|S|\\leq \\Delta \\sum_{q}{\\sum_{a}{|\\beta(q,a)|^2}}$<\/p>\n and if the last sum can be expressed conveniently and is not too large, we get an upper bound for |S|<\/em> in this manner.<\/p>\n To build the amplifier, consider first a single prime p<\/em> less than Q<\/em>: if n<\/em> is in S<\/em>, we know that the reduction of n<\/em> modulo p<\/em> is constrained to not be in \u256c\u00aep<\/sub><\/em>. We can express this analytically by saying that the characteristic function of this set, evaluated at n<\/em>, is zero. But now expand this characteristic function (say fp<\/sub><\/em>) in terms of the additive characters (the “discrete Fourier transform”): we have<\/p>\n $latex f_p(x)=\\sum_{a\\ mod\\ p}{\\alpha(p,a)\\exp(2i\\pi ax\/p)}$<\/p>\n with<\/p>\n $latex \\alpha(p,a)=\\frac{1}{p}\\sum_{x\\in\\Omega_p}{\\exp(-2i\\pi ax\/p)}.$<\/p>\n Thus for n<\/em> in S<\/em>, we have<\/p>\n $latex 0=f_p(n)=\\sum_{a\\ mod\\ p}{\\alpha(p,a)\\exp(2i\\pi an\/p)}$<\/p>\n and we rewrite this by isolating the contribution of the 0-th harmonic (which is the constant function 1, which encodes the probability that an integer modulo p<\/em> is in \u256c\u00aep<\/sub><\/em>):<\/p>\n $latex \\frac{|\\Omega_p|}{p}=\\alpha(p,0)=\\sum_{(a,p)=1}{(-\\alpha(p,a))\\exp(2i\\pi an\/p)}.$<\/p>\n This is the basis of our detector! First, this defines the coefficients<\/p>\n $latex \\beta(p,a)=-\\alpha(p,a)$<\/p>\n and then, to extend this to all squarefree integers q<\/em> up to Q<\/em>, we use the Chinese Remainder Theorem and multiply the detectors for primes dividing q<\/em>, getting coefficients \u256c\u2593(q,a)<\/em> for a<\/em> coprime with q<\/em>, such that<\/p>\n $latex \\prod_{p\\mid q}{\\frac{|\\Omega_p|}{p}}=\\sum_{(a,q)=1}{\\beta(q,a)\\exp(2i\\pi an\/q)}.$<\/p>\n For notational simplicity, we write<\/p>\n $latex c_p=\\frac{|\\Omega_p|}{p}.$<\/p>\n Thus the final detector for S<\/em> is<\/p>\n $latex A(n)=\\sum_{q\\leq Q}{\\sum_{(a,q)=1}{\\beta(q,a)\\exp(2i\\pi an\/q)}},$<\/p>\n and we have<\/p>\n $latex |A(n)|=\\sum_{q\\leq Q}{\\prod_{p\\mid q}{c_p}}.$<\/p>\n Calling this quantity B<\/em>, as previously, the resulting inequality after applying (***), from the sketch above, is<\/p>\n $latex B^2|S|\\leq \\Delta A$<\/p>\n with<\/p>\n $latex A=\\sum_{q\\leq Q}{\\sum_{(a,q)=1}{|\\beta(q,a)|^2}}.$<\/p>\n To compute this, we invoke the orthogonality of additive characters, and their compatibility with the Chinese Remainder Theorem: we have first<\/p>\n $latex A=\\sum_{q\\leq Q}{\\prod_{p\\mid q}{\\sum_{(a,p)=1}{|\\beta(p,a)|^2}}},$<\/p>\n and then, using the (discrete) Parseval formula<\/p>\n $latex \\sum_{a\\ mod\\ p}{|\\alpha(p,a)|^2}=\\frac{1}{p}\\sum_{x\\ mod\\ p}{|f_p(x)|^2}=c_p,$<\/p>\n we get by removing the contribution of a=0<\/em> that<\/p>\n $latex A=\\sum_{q\\leq Q}{\\prod_{p\\mid q}{c_p(1-c_p)}}.$<\/p>\n Now we have an inequality<\/p>\n $latex |S|\\leq \\Delta \\frac{A}{B^2},$<\/p>\n which is similar, but not quite identical, to (**). In general, it is somewhat weaker — though barely so for some problems like the twin-prime example above, where the sets \u256c\u00aep<\/sub><\/em> are quite small (i.e., what are called small sieves…)<\/p>\n To improve this inequality and get (**), we notice that we still can try other amplifiers. In particular, it is natural to notice that the inequality we got is not homogeneous if we replace the coefficients \u256c\u2593(q,a)<\/em> by multipliying by constants (depending only on q<\/em>, multiplicatively). Indeed, if we consider now<\/p>\n $latex \\gamma(q,a)=(\\prod_{p\\mid q}{\\lambda_p})\\beta(q,a)$<\/p>\n we replace B<\/em> with<\/p>\n $latex B_1=\\sum_{q\\leq Q}{\\prod_{p\\mid q}{\\lambda_pc_p}}$<\/p>\n while A<\/em> is replaced with<\/p>\n $latex A_1=\\sum_{q\\leq Q}{\\prod_{p\\mid q}{\\lambda_p^2c_p(1-c_p)}}$<\/p>\n and we can try to minimize the ratio A1<\/sub>\/B1<\/sub>2<\/sup><\/em> when the coefficients \u256c\u2557p<\/sub><\/em> are allowed to vary. This is the same classical problem that occurs in the Selberg sieve (see for instance the write-up by Ben Green<\/a> of the application of the Selberg sieve to the twin-prime problem, already mentioned, for an introduction): minimize a quadratic form with respect to a linear constraint (with a different quadratic form), and it is easily and elegantly solved: we casually Cauchy<\/p>\n $latex B_1^2\\leq (\\sum_{q\\leq Q}{\\prod_{p\\mid q}{\\lambda_p^2c_p(1-c_p)}})\\times (\\sum_{q\\leq Q}{\\prod_{p\\mid q}{c_p\/(1-c_p)}})=A_1H,$<\/p>\n so that, first of all, we can not do better (i.e., make the ratio smaller) than<\/p>\n $latex \\frac{A_1}{B_1^2}=\\frac{1}{H}$<\/p>\n and second, by the equality case in Cauchy’s inequality, we can<\/em> do something this good by taking<\/p>\n $latex \\lambda_q=\\prod_{p\\mid q}{1\/(1-c_p)}.$<\/p>\n This leads to the optimal value of the ratio and therefore proves the arithmetic large sieve inequality (**), as described previously.<\/p>\n A final remark: the simplicity of the argument suggests that it is probably not new. There are (in Montgomery’s survey article, for instance) a number of earlier derivations of the arithmetic large sieve inequality from the dual form of the analytic inequality. However, those I have seen (I must say I had not really looked at any of them until after writing the gist of my argument…) are based on, or inspired by, the connection with the Selberg sieve, and are therefore less elementary (and motivated). Still, the ingredients look always much the same, and I think this write-up is more a question of re-arranging them, instead of a really new proof.<\/p>\n","protected":false},"excerpt":{"rendered":" In the development of the large sieve, leading to its arithmetic applications, there is one step which — I must admit shamefully — I never completely understood as a natural argument instead of one with a somewhat mysterious clever trick. Or, at least, until now: just this week-end, one vaguely related thing leading to another, … Continue reading Demystifying (a bit) the arithmetic large sieve<\/span><\/a><\/p>\n","protected":false},"author":625,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-98","post","type-post","status-publish","format-standard","hentry","category-blogroll"],"_links":{"self":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/98","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/users\/625"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/comments?post=98"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/98\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/media?parent=98"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/categories?post=98"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/tags?post=98"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}