English comparative and the sieve

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

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

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

|S|\leq N/D

where

N=\sum_{p\leq z}{\log p}-\log N

and

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

|\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.]

Published by

Kowalski

I am a professor of mathematics at ETH Zürich since 2008.

7 thoughts on “English comparative and the sieve”

  1. The largest sieve, if one pushes the analogy, would be when only one residue class is permitted modulo every prime. It turns out that the larger sieve gives a very good answer (see the Corollary in Gallagher’s paper just after he proves the inequality): provided the sum of log p for all primes involved in the sieve is > log N, there is at most _one_ integer <= N which remains. This is clearly best possible since one can start by fixing an integer and excluding all residue classes except its own! (I think the bound log N is also essentially best possible because of the Chinese Remainder Theorem).

  2. Dear Emmanuel,

    I had never given this construction a second thought before now. I spent the last few minutes trying to think of other examples, without too much success.

    However, it occurred to me that there is
    the following notion in English, that of being “the bigger man”. As you probably know, it is used in situations of the following type: two men are feuding, and each is too proud to forgive the other. A fried of one of the men may then encourage
    him to be “the bigger man” and be the first to break the silence between them.
    Thus,“the bigger man” makes a concession not out of weakness, but rather from a position of moral superiority.

    Is there an analogous notion in French? Presumably “the bigger man” suffers from the same difficulty of literal translation as your other examples.

    Regards,

    Matthew

  3. It sounds like the “bigger man” is another example of the construction, though maybe with an extra layer of conventional meaning.

    That extra layer can be picked up to give a translation in French, I think, most likely by using metaphorically an absolute comparative: “c’est le plus fort qui pardonne le premier” (“it’s the strongest who first forgives”). Here it’s pretty clear for a French speaker that “le plus fort” is not meant to say the person in question is the strongest in the world. But “le dictionnaire Oxford le plus court” (the shortest Oxford dictionary) just doesn’t work — it leads to a picture of one of those very small pocket dictionaries…

  4. I think the construction is rather common in English — i.e. Matthew and I both work in the industry of “higher education.” How is the mathematical phrase “higher cohomology operation” translated in French?

    Re #2, there is a very interesting family of questions surrounding what we might call “the second-largest sieve.” For some (potentially very sparse) set of primes P you look at the set of integers in [0..N] which lie in one of TWO residue classes (say, 1 and -1) mod every p in P. So one might for instance be asking how closely the solutions to x^2 = 1 (mod M) can cluster together in 0…M where M is some highly composite integer. This is related to Rudin’s conjecture on squares in arithmetic progressions, as I learned from Granville….

  5. Actually, “Higher education” translates directly to “Enseignement supérieur”, and (I guess) “Higher cohomology” to “cohomologie supérieure”, which sounds very much like the English construction since there is no direct reference to what it is “supérieur” to. So maybe “larger sieve” can be translated at least reasonably as “crible supérieur”…

    As for the “second largest” sieve, Gallagher’s corollary also says something in that case, though maybe not as much as one would want?

  6. Maybe the most natural translation, absent any relevant context, would be to use “participe passé”, wouldn’t it? “Shorter dictionary” is “Dictionnaire abrégé” so “larger sieve” would or should be “crible élargi”. But in the mathematical context, “supérieur” sounds very good, I guess.

Comments are closed.