Mathematics – Page 58 – E. Kowalski's blog

More mathematical terminology: friable

Today’s terminological post will be a contribution to the French-led insurgency that tries to replace the denomination “smooth number” (or “smooth integer“) with the much better “friable number” (in French, “nombre friable” instead of “nombre lisse“).

Of course, many readers may wonder “what is this anyway?”. And part of the point is that the better choice may lead such a reader to guess fairly accurately what is meant (possibly with a hint that this has to do with multiplicative properties of integers), whereas playing a game of “Define a smooth number” with a wide group of mathematicians may probably lead to wildly different interpretations.

So here is the definition: a positive integer n is called y-friable (or smooth, if you still insist) if all the prime divisors of n are at most y. The idea is that y should be much smaller than n, so that this means (intuitively) that n only has “small” prime factors. But the definition makes sense for all y, and for instance, any integer n is n-friable, a 2-friable integer is a power of 2, etc.

I do not wish to discuss the properties of those integers (only their name), so let me just refer to this survey by Granville for a discussion of their basic properties and of their applications to computational number theory.

The adjective “friable” (Capable of being easily crumbled or reduced to powder, OED) seems perfect to describe this type of integers: it is evocative and conveys not only something of the technical definition, but also a lot of the intuitive meaning and applicability. The other contender, “smooth”, has several problems (in fairness, it has at least one positive aspect: whatever we call them, the integers without large prime factors are extremely useful in many parts of analytic and algorithmic number theory, and the underlying current that smoothness is something desirable is not usurped): (1) it is much too overloaded (search for “smooth” without more precision in Math Reviews: 68635 hits as of tonight; for “friable”, only 19); (2) whichever meaning of smooth you want to carry from another field, it does not really mean anything here; (3) not to mention that, chronologically speaking, the terminology was already preempted by the smooth integers of Moerdijk and Reyes, which are the solutions of the equation sin π x=0 in the real line of suitable topoi (such as the smooth Zariski topos, apparently).

The chronology of the use of these words, as it appears from Math Reviews at least, seems quite interesting: the first mention it finds of “smooth numbers” in the number-theoretic meaning is in the title of a paper of Balog and Pomerance, published in 1992. However, the notion is of course quite a bit older: the standard paraphrase was “integers without large prime factors”, with many variants (as can be seen from the bibliography of Granville’s survey, e.g, A. A. Buchstab, “On those numbers in an arithmetic progression all prime factors of which are small in order of magnitude”, 1949; Balog and Sarkozy, “On sums of integers having small prime factors, I”, 1984; Harman, “Short intervals containing numbers without large prime factors”, 1991; etc : clearly, something needed to be done…).

As for “friable”, the first number-theoretic use (interestingly, the six oldest among the 19 occurences of “friable” in Math Reviews also refer to other contexts than number theory, namely some studies of models of friable materials, from 1956 to 1987) is in a review (by G. Martin in 2005) of a paper of Pomerance and Shparlinski from 2002, though “smooth” is used instead in the paper. The first occurence in a paper (and so, possibly, in print) is in one by G. Tenenbaum and J. Wu, published in 2003. It must be said that, for the moment, only French writers seem to use the right word (Tenenbaum, de la Bretèche, Wu, and their students)… G. Martin consistently uses it in his reviews, despite having to recall that this is the same as smooth numbers; however, he uses “smooth” in the title and body of his paper on friable values of polynomials (published in 2002, admittedly, and the abstract on his web page uses mostly “friable” instead…).

Beno Eckmann, 1917–2008

The Mathematical Department of ETH was saddened last week of learning of the death of Beno Eckmann, on Tuesday, Nov. 25, aged 91. He was one of the major historical figures in the department, linking us to the “classical” times of Polya, Weyl, Hopf and others by his long activity and involvement in the international mathematical community. In Zürich, part of his importance has been as the initiator and first director of the Forschungsinstitut für Mathematik in 1964.

He was a student of Heinz Hopf at ETH, obtaining his degree in 1942, and his genealogy lists 73 students and 1040 descendants (!), among whom can be recognized many well-known names from topology (e.g., M. Kervaire, 1956, or G. Mislin, 1968), analytic geometry (H. Grauert, 1956), algebra (e.g, M.A. Knus, 1967) and even probability theory (E. Bolthausen, 1973), and so on. (Part of the genealogy is presented in a more impressive way in this genealogical tree).

Although I didn’t meet him after my arrival in January, my colleagues have told me he was active until quite recently (and indeed, his last research paper on Math Reviews is dated 2004, though it is claimed to originate from a 2002 lecture..). His 90th birthday was celebrated last year at FIM.

Topologists in particular will probably enjoy some of the essays collected in these notes, in particular the reminiscences of the antesagittarian days of algebraic topology. (Apparently, the very first occurence of a “physical” arrow to indicate a map between spaces is to be found in a Research Announcement by W. Hurewicz from 1941).

The W(E_8) polynomial, graphically expressed

My colleague Richard Pink had the idea of illustrating the matrix I had found with F. Jouve and D. Zywina, whose characteristic polynomial has Galois group W(E₈), by plotting it on a grid with colors to indicate the size of the coefficients. This representation was then constructed by Leopold Talirz using Matlab, with the following result:

The square grid represents the matrix graphically, and the scale for colors is indicated on the right. I think this is an intriguing picture. Can anyone suggest an explanation for its structure? In fact, since the matrix arises by a product

$m=x_1x_2\cdots x_{16}$

it would actually probably be even more interesting to show the evolution of the matrix from the identity as more terms are added in the product (and even to continue beyond this matrix in a random walk, as this the motivation for the construction…). If this leads to a nice result, I’ll post it later…

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

The harmonic series and surrounding folklore

Speaking of divergent series, I’d like to mention one of my favorites bits of informal folklore: this starts with a slogan

The only “truly” divergent series is the harmonic series
$H=1+\frac{1}{2}+\cdots +\frac{1}{n}+\cdots,$

which, of course, deserves plenty of quotes. But the idea is quite sound: it is that, given about any other series with real or complex terms (which does not involve this one in a hidden manner, of course, e.g., as an “irreducible summand”), such as

$\sum_{m\geq 1}{(-1)^{m+1}\frac{m^2}{4m^2-1}},$

it is quite often possible, by some kind of trick or feint, to assign a “value” (i.e., a real or complex number) to the series in a way which is reasonable and useful for certain purposes. [A famous example is the (apparently) ultra-divergent series

$\sum_{m\geq 0}{(-1)^m m!}=1-1+2-6+24-120+720-\cdots,$

which was considered by Wallis and Euler: its “value” is

$e\int_0^1{e^{-1/x}x^{-1}dx}=e\int_1^{+\infty}{y^{-1}e^{-y}dy}=0.5963473623231\ldots$

(see this article for an explanation of some of Euler’s ideas to do this “computation”).]

One setting in which the philosophy above has been refined to a precise (conjectural) statement is the theory of L-functions (over number fields). Indeed, observe that (formally) we have

$H=\zeta(1),$

where ζ(s) is the Riemann zeta function, which is only defined properly for the real part of s larger than one by the series

$\zeta(s)=\sum_{n\geq 1}{\frac{1}{n^s}}.$

Then, after translating the basic insight about the harmonic series from Dirichlet series to L-functions, one gets the following folklore conjecture:

If a reasonable (say, automorphic, or “motivic”) L-function L(s) over a number field k has a pole at s=1 (when normalized so that the functional equation relates values at s and 1-s), then L(s) is divisible by the Riemann zeta function, in the sense that
$L_1(s)=\frac{L(s)}{\zeta(s)}$
does not acquire poles at any of the complex zeros of the Riemann zeta function.

This is quite a rich problem: it contains a famous conjecture of Artin (the Dedekind zeta function of a number field should be divisible by the Riemann zeta function), and applied to the Rankin-Selberg convolution, it suggests the existence of the symmetric-square L-functions of modular forms — indeed, the first crucial result towards the “automorphic” existence of the latter (due to Gelbart and Jacquet), was the proof of this divisibility property by Shimura).

Now for the most amazing thing concerning this folklore property (at least to me): it seems that it also works modulo primes! Let me explain this (an explanation which I heard from Jean-Pierre Serre): another renowned formula of Euler for the values of the zeta function at even integers can be rephrased, after using the functional equation

$\pi^{-s/2}\Gamma(s/2)\zeta(s)=\pi^{-(1-s)/2}\Gamma((1-s)/2)\zeta(1-s),$

as the formula

$\zeta(1-2n)=1+2^{2n-1}+3^{2n-1}+\cdots + k^{2n-1}+\cdots =-\frac{1}{2n}B_{2n},$

where the Bernoulli numbers B_2n are rational numbers defined by the power series expansion

$1-\frac{1}{2}x+\sum_{n\geq 1}{B_{2n}\frac{x^n}{n!}}=\frac{x}{e^x-1}$

(and, of course, the middle expression for ζ(1-2n) is purely formal: it is one more example of a divergent series that can be given a convincing value).

The idea now is that the last expression (-1/2n B_2n) can be reduced modulo a prime p, provided p does not divide 2n and does not divide the denominator of the Bernoulli number. Now, lo and behold, the primes dividing the denominators of Bernoulli numbers are known: they are exactly the primes such that

$p-1\mid 2n$

or equivalently such that

$k^{2n-1}\equiv k^{-1}\text{ mod } p$

for all integers k coprime with p (those for which the inverse modulo p makes sense…). So the Bernoulli number can not be reduced modulo primes exactly when (either p divides 2n or) formally we have

$-\frac{1}{2n}B_{2n}\equiv 1+2^{2n-1}+3^{2n-1}+\cdots + k^{2n-1}+\cdots\equiv 1+2^{-1}+\cdots +k^{-1}+\cdots,$

the divergent harmonic series again! (One must omit the terms with k divisible by p of course, but since this is purely formal, why not?).

I have no idea if there is a good explanation for this coincidence, but it is remarkably beautiful, and it certainly gives a convincing argument for the fact that the numerators of Bernoulli numbers are much more mysterious: so are the zeros of the Riemann zeta function, in comparison with its pole…)