Kowalski – Page 77 – E. Kowalski's blog

Combinatorial cancellation

Here is the example of sums exhibiting a large amount of combinatorial cancellation that I mentioned in a comment on my previous post. First, some notation: p is a prime number, k is a positive integer, and G is the set of hyperplanes in the vector space F_p^k of dimension k over the finite field with p elements. Then consider

$\sum_{\emptyset\not=I\subset \mathbf{G}}{\frac{(-1)^{|I|+1} }{1-p^{j(I)-k}}}$

where, for any subset I of G, we let

$j(I)=\mathrm{dim} \bigcap_{H\in I}{H}$

(the dimension of the intersection of the hyperplanes in I).

The terms of this sum are of absolute value of size roughly 1, if p is large (since I is non-empty, the intersection is contained in any of the hyperplanes in I, so j(I)<k), but there are many of them, namely

$2^{|\mathbf{G}|}-1=2^{p^k+\cdots+p+1}-1,$

so one may suspect that the overall sum is quite large.

And yet, it turns out that, for fixed k and p going to infinity, the sum converges to k. My explanation for this is rather indirect, and I will explain it in another post soon, but maybe some readers can see a direct reason?

A charming little textbook

Like many others, the library of the mathematics department in Bordeaux used, every once in a while, to put in a bin somewhere duplicate copies of journals for anyone to take home; more rarely books also appeared there. This way, I found one some day which I find particularly fascinating.

It is not a research book, but an old French textbook for the program of the last year of high-school (the “Terminale”), published in 1971. It is part of a series probably encompassing the whole high-school curriculum. It is written by M. Debray, M. Queysanne, and D. Revuz (yes, the one of Revuz-Yor).

More properly, this is only Volume 1 of the Terminale textbook, since there exist two additional ones (which I do not have). The main topics of this first volume are “Nombres, probabilités” (numbers, probability theory), and one can see what the two others treated by looking at the official curriculum for the Terminale, which is reproduced at the beginning of the text: one was for analysis (basic calculus) and the other for geometry.

So the first striking impression is that of sheer size: if the other two volumes are of comparable length, this amounts to about 1000 pages for a single year of study, and this must have been combined with classes in French, Philosophy, Physics and Chemistry, History and Geography and Biology, and at least one foreign language, with Latin as a bougie sur le gâteau for quite a few students (probably; I can’t seem to find the general official program for 1971).

So what did French students know when finishing high-school in 1971? Before going into this, let’s look at what they were already supposed to know when entering the Terminale (as indicated by various Rappels de première in the text). The first chapter is entitled Entiers naturels (integers), which is reasonable enough; Section 1.1 is

Éléments réguliers pour une loi de composition interne. (“Regular elements for an internal operation”).

So an internal operation on a set is a concept taken for granted. Later, we learn that binary relations are just as old hat (hence also equivalence relations and quotient sets), and similarly for vector spaces (over the reals; not necessarily finite-dimensional). We learn that the study of the reals was, in Première, based on the Propriété des segments emboîtés (the fact that a countable decreasing intersection of non-empty compact intervals is non-empty), but it is taken anew now with the axiom that a non-empty set of reals which is bounded above as a least upper bound.

Then here are some highlights of the book:

In agreement with the official curriculum, the most important structures (groups, rings, vector spaces, and homomorphisms) are pointed out as frequently as possible whenever they occur;
The complex numbers are constructed as a subring of the 2×2 matrices over the reals (the product of such matrices being another remnant of the previous year);
The rationals and the integers are reconstructed as subrings of the reals, and shown to satisfy all the properties previously proved about them from the preliminary chapters where they were studied independently;
But the construction of Z from the integers, by a good old Grothendieck group construction, is relegated to an Appendix;
Is N really taken for granted? No, another Appendix sketches the construction of the (nonnegative) integers from set theory (!), through cardinals; this is for “interested readers”;
Limits are (of course) presented in clean and robust ε / δ fashion.

One may get from this the impression of Bourbakism running rampant among schoolchildren, but I confess to having selected these topics just to give such an impression. In fact, the text is not at all a distilled version of Nicolas’s great treatise for younger readers, but its influence is probably present in two respects: an emphasis on structures (and homomorphisms), and on rigor. Where things are not proved, this is stated clearly: nous avons admis les principales propriétés de… (“We have assumed valid the main properties of…”).

The style itself is much more readable for a textbook: most new definitions come after a short description of why they might be interesting or natural, often together with a preliminary example, which may then be the subject of a quick follow-up after the definition itself. In addition, there are many excellently chosen exercises, ranging from direct computational ones to more adventurous escapades (the arithmetic-geometric mean, for instance).

But more importantly perhaps, there is not only an emphasis on abstraction and definitions: the discussion of the reals contains a detailed investigation of approximations (decimal expansions, interval arithmetic, relative and absolute errors), and there is a really nice probability chapter. There, the definitions, as before, are rigorous and correspond to the general theory: although the theory is of course built on finite sets, there are tribus (“σ-algebras”), random variables, distribution laws and probability measures, and this chapter concludes with a version of the weak law of large numbers.

In the end, I get a mixed feeling from reading this book. It seems a fair guess that, in its time and for its intended audience, it must have been a complete disaster: the amount of the material to assimilate, and its abstract sophistication, must have made it a subject of hatred (or of jest…) for most students. But, as a “platonic” incarnation of the concept of a mathematical textbook, independently of its time and place, it is really not bad. If one or more of my children, one day, develop a taste for mathematics, and if they start looking eagerly, at a young and impressionable age, for almost any book to assuage their thirst for mathematics (as I did, and as most other mathematicians have done and still do), then at a reasonable time I will give them this textbook with pleasure.

(Note: I do not know at what rate the curriculum changed; I myself remember learning equivalence relations well before high-school, since vectors in the plane were introduced as equivalence classes of “bipoints équipollents”, but by the time I was finishing high-school, around 1986-87, they had been removed, though I remember that my mathematics teacher, in the first post-high-school year, started using them during the very first lesson without so much as a word of explanation… Nowadays, judging from what the students know when entering the first semester of university in Bordeaux, the program has probably been reduced by at least 90 percent, and all abstraction has vanished).

Another bad reference, and another exercise

My name turns out to be involved in another case of problematic bibliographic reference, but in contrast with the previous case, I am completely blameless. The book Mathematical Constants turns out to contain, as Added in Press, the statement that the “probability” that two integers belonging to the ring Z[j] (where j is a primiteve root of unity of order 3) are coprime is equal to

$\frac{6}{\pi^2 H}$

where

$H=\sum_{k\geq 0}{\Bigl(\frac{1}{(3k+1)^2}-\frac{1}{(3k+2)^2}\Bigr)}$

(probability is in the usual not-quite-strictly-correct sense of looking at the limit of the proportion in larger and larger balls or boxes centered at 0). For this, a reference is given to a putative unpublished note of mine entitled “Coprimality and squarefreeness within quadratic fields”.

However, this note does not exist, and never did! The only reason for this (somewhat casual) claim is that I had explained how to prove this (it is really an exercise, in line with this one) on the NMBRTHRY mailing list back in 2003.

Is there a combinatorial “square-root cancellation” philosophy?

As an analytic number theorist, I live among oscillating sums, from

$\sum_{n\leq x}{\mu(n)}$

where μ is the Möbius function, to

$\sum_{x\ mod\ p}{\exp(2i\pi (x+\bar{x})/p)}$

(the famed Kloosterman sum, one of the rare mathematical objects to have given his name to an infectious disease). In these finite sums, we add a finite number of complex numbers (say N), each of modulus at most 1, and we are in situations where the arguments of the complex numbers varies “quite a lot”.

For many such sums, a very reliable rule of thumb (at least as far as guessing what should be true) is that the sum should be of order of magnitude roughly given by the square root of the number of terms. This is easily justified on probabilistic grounds, and it is further confirmed by a remarkable array of rigorous results with sums of many different origins. It is also often incredibly deep: for the first sum above, a result of this type is equivalent to the Riemann Hypothesis, and for the second, a bound of the right shape was only proved by A. Weil in the 1940’s as a consequence of the Riemann Hypothesis for curves over finite fields. And it is quite easy, also, to write down oscillating sums where this type of cancellation would lead to a proof of the Twin Prime Conjecture, for instance.

In any case, if I am confronted with a sum as above, I don’t feel afraid, and I can often say something intelligent.

However, one can also find many oscillating, or at least alternating, sums coming from combinatorics where, however, the size of the terms in the sum are by no means bounded, but growing as the length of the sum increases… and yet the total sum remains controlled in magnitude. The most trivial example is

$\sum_{j=0}^n{(-1)^j({}^n_j)}$

which is 0 (for n at least 1) from the binomial theorem, whereas the size of the largest summand is exponential in terms of n.

Now, when I encounter such a sum, I do feel scared; if I suspect the sum is small, I am quite at a loss to know why that could be true, and even more so when it comes to trying to prove that this is the case.

But since I have reasons to suspect that some combinatorialists read this blog, maybe some enlightenment may come: is there a general rule that can lead to a serious guess that a “combinatorial looking” alternating sum is much smaller than the largest term (say, of polynomial size, compared with possibly exponential terms)? If yes, what are the most efficient and systematic means of trying to confirm such a guess? And, out of curiosity: what are the most remarkable yet-unproved statements of this type?

WBGO

If you are a graduate student busy and worried writing a thesis, and in need of spiritual encouragement on this long and forking path, I’d like to suggest to tune to WBGO, the 24-hour, public, commercial-free, Jazz Radio Station from Newark, New Jersey. If Jazz is not the food of clear and insightful writing, I don’t know what is.

Until a few years ago, this valuable advice was only useful under rather stringent boundary conditions: roughly speaking, you had to be a student in the Newark or New Brunswick campuses of Rutgers University, or in Manhattan (probably; I didn’t have the opportunity to try from Columbia, for instance). However, nowadays you can access the radio stream any time on the internet, by following the link above. (The boundary condition were indeed rather strict; a minor heartbreak when moving for a postdoc to Princeton University was that, from there, barely twenty mile from New Brunswick, the radio signal did not reach my apartment or office…)

The efficiency of this musical infusion is proved not only by my own case (I was in Rutgers in 1995-98), but in a conclusive second proof by my student Florent Jouve in his acknowledgements for his recently completed thesis.

Note: if you end up following this advice, consider also contributing to the radio station, which relies on its listeners to stay on the air.

Note bis: if you use Linux, following the links to listen to WBGO may lead to difficulties with media plugins; however, the VLC program works (at least for me on a recent Fedora), with the command line

vlc http://wbgo.org/listennow/wbgo.asx &