One of my favorite constructions in the English language is that bizarre form of comparative that makes it possible to speak of the “Shorter Oxford English Dictionary”, without any mention of what this estimable dictionary (two long and heavy volumes…) is actually compared to. Does this grammatical construction have a name? Does it exist in other languages? Certainly it is completely inexistent in French, and makes for rather thorny translation puzzles: how should a number theorist translate, in French, the name of Gallagher’s remarkably clever larger sieve? [The construction is actually particularly twisted here, since the implicit comparison point of Gallagher is, of course, already known as the large sieve…]
For those readers who have never heard of the larger sieve, here is the idea and the explanation for the name (which is very clearly explained in Gallagher’s paper): recall that a basic sieve problem (for integers) is to estimate the number of integers remaining from (say) an interval
$latex 1,2,\ldots, N$
after removing all those n which, reduced modulo some prime p in some set (for instance, all those up to z=Nδ for some δ>0) always stay away from a given subset Ωp of primes: in other words, one wishes to know the cardinality of the sifted set
$latex S=\{n\leq N\,\mid\, n\text{ mod p}\notin \Omega_p\text{ for all }p\leq z\}.$
Classically (and also not so classically), the first examples were those were one tries to get S to be essentially made of primes, or twin primes, etc. In that case, the size of Ωp is bounded as p grows. There situations are called small sieves.
Then Linnik introduced the large sieve which is efficient for situations where the size of Ωp is not bounded, and typically grows to infinity with p: basic examples are the set of quadratic residues (or non-residues), or the set of primitive roots modulo p.
And then came the larger sieve: Gallagher’s method works better than the large sieve when Ωp is extremely large, so that the integers in S have few possible reductions modulo primes (roughly speaking, the larger sieve is better when the number of excluded classes is larger than half of the residue classes modulo p; so quadratic non-residues are borderline, and indeed both the large and the larger sieve give the correct upper bound — up to a constant — for the number of squares up to N). More precisely, Gallagher shows that
$latex |S|\leq N/D$
where
$latex N=\sum_{p\leq z}{\log p}-\log N$
and
$latex D=\sum_{p\leq z}{\frac{\log p}{p-|\Omega_p|}}-\log N,$
provided the denominator D is positive.
As the number of classes excluded increases, the efficiency of this inequality becomes extremely impressive: if
$latex |\Omega_p|>p-p^{\theta}$
with θ>0, the number of elements of S becomes at most a power of log(N), whereas the large sieve gives a power of N. For an arithmetico-geometric application of a new variant of the larger sieve in number fields in a situation where the numerology is of this type, you can read a recent paper of J. Ellenberg, C. Elsholtz, C. Hall and myself.
[I should mention that it was C. Elsholtz who first mentioned the larger sieve to me a few years ago: the method is not as well known as it should, since it is extremely simple — Gallagher deals with it in nine lines, and our version is not much more complicated, though it is a bit more involved since it works with heights in the number field to sieve elements which are not necessarily integers. The basic argument and its applications can provide excellent exercises and problems for any introductory number-theory course.]
