Category: Mathematics

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 &

Quadratic reciprocity, exercised

Here is an amusing elementary property:

Let n and m be odd integers, and d such that n+m=d2, and d is congruent to 2 modulo 4; then
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(\frac{d}{n}\right)=-\left(\frac{d}{m}\right)
where the left and right-hand sides are Jacobi symbols.

If n and m happen to be odd primes, then we have Legendre symbols, and then this property means that one, and only one, of the equations

y^2=d\ \mbox{mod}\ n

and

y^2=d\ \mbox{mod}\ m

has a solution. (For general n and m, we can only deduce that one of those equations has no solution).

Here is a hint for the proof: compute

\left(\frac{d}{d^2-n}\right)

using the reciprocity law for Jacobi symbols to check that it is  –(d/n). This requires to use all cases of the reciprocity law (namely, the “generic” law for odd moduli, and the supplementary laws for (2/d) and (-1/d) if d is odd). There might be another proof than this, of course, but it doesn’t seem easy to use, for instance, the concrete interpretation above, in the case where n and m are primes.

I don’t know if this is a well-known factlet about quadratic reciprocity. I only noticed it using computer experiments (then, of course, it wasn’t very long before I found the easy proof using the reciprocity law), as I wanted to check that, roughly, among the expressions d2=n+m, with d even and n and m odd primes, roughly half of the values of n were such that d is not a quadratic residue modulo n. When d was congruent to 2 modulo 4, the computer indicated that this was true of exactly half of the values, which only seemed plausible if the property above was true…

Incidentally, it is known by work of Perelli that, for any monic integral polynomial P of positive degree, which does not always take odd values, then for “most” positive integers n, P(n) is a Goldbach number if it is even, i.e., it is a sum of two primes, so for most d congruent to 2 modulo 4, we can indeed write d2=n+m with n and m both primes. This result refines, in a sense, the well-known fact – which goes back to van der Corput, Tchudakov and Estermann at least – that most even integers are sums of two primes; one proof of this, which is more or less a consequence of a suitably strong version of Vinogradov’s theorem on representations of odd integers as sums of three primes, is given in Chapter 19 of my book with Henryk Iwaniec.

(As to why I looked at this bizarre question, it is because of a question of Nguyen Ngoc Dong Quan, involving slightly more complicated conditions).

New category

I’ve not been particularly efficient in using tags, categories, and the rest, to organize this blog, but I’d like to point out that I just added one category Exercises which can be used to retrieve all posts which contain rather elementary mathematical facts which may be suitable as exercises for rainy days or when one has to write an exam.

Version control in action

A while back I mentioned the usefulness of version control software in my work (see also the current discussion at the Secret Blogging Seminar). Now here is a True Life example of what it can do: Vijay Patankar wrote to me today, pointing out that in my paper Weil numbers generated by other Weil numbers and torsion fields of abelian varieties, I claim (misquoting slightly for typographical reasons):

Remark 3.9. In [K1], the question of the “splitting behaviour” of a simple abelian variety A/Q at all primes is also raised: is it true that the reduction modulo p of A remains simple for almost all p? In fact, the “horizontal” statements of Chavdarov can already deal with this. For instance, this property holds if A/Q has the property that the Galois group of the field Q(A[n]) generated by the points of n-torsion of A is equal to Sp(2g,Z/nZ) for any sufficiently large prime n.

Here, the citation [K1] refers to my earlier paper Some Local-Global Applications of Kummer Theory, but as he pointed out, the question is not mentioned anywhere there… So where did it go?

I have no memory at all of what happened, but thanks to SVN’s history facility, I have been able to reconstitute the outline of this nanoscopic academic drama: first, in late 2001, I added a remark about this problem in the final section, among other questions suggested by the paper:


r416 | emmanuel | 2001-09-13 08:52:44 +0200 (Thu, 13 Sep 2001) | 3 lines
416 emmanuel \item Given an abelian variety $A/k$ over un number field, how does
416 emmanuel its decomposition in simple factors relate to that of its reductions
416 emmanuel in general? In particular, assuming $A$ to be $k$-simple, is the set
416 emmanuel of primes $\ideal{p}$ with $A_{\ideal{p}}$ reducible finite, or of
416 emmanuel density $0$?

Here, the first line is an excerpt from the log file which records the history of every file under version control (it is produced by the svn log command); the number 416 is the “revision number” which identifies at what point in time the changes corresponding to this “commit” were made.

The next lines (which, in fact, come chronologically first in the unraveling of the mystery, as they tell which revision number to look at to find the exact date) are obtained by the svn blame command: for each line of a file, this indicates (1) at which revision the line was added (or last changed); (2) who did the change.

Then, in late 2002, just before sending the corrected version to the publisher, I commented out this question:

r1831 | emmanuel | 2002-11-14 21:16:41 +0100 (Thu, 14 Nov 2002) | 2 lines
1831 emmanuel %\item Given an abelian variety $A/k$ over un number field, how does
1831 emmanuel % its decomposition in simple factors relate to that of its reductions
1831 emmanuel % in general? In particular, assuming $A$ to be $k$-simple, is the set
1831 emmanuel % of primes $\ideal{p}$ with $A_{\ideal{p}}$ reducible finite, or of
1831 emmanuel % density $0$?

I still don’t know why I ended up doing this; indeed, two years later, I was convinced I had not done so, when I wrote the excerpt above from my other paper (the date can again be determined using SVN). In passing, this confirms the principle (which I try to adhere to usually) that one should always give a complete detailed reference to any outside work – even if it’s your own.  If I had taken the trouble of trying to locate the page or section number for this question, I would have realized it was missing…

Finally, if the question seems of interest, this paper of Murty and Patankar develops it further.