One-upmanship

A quip of S. Lang states that “analysis is number theory at the place infinity”.  (Which implies, correctly, that analytic number theory is some particularly exalted form of number theory).

The equally quipful E. Witten goes rather further in reducing mathematics to its essentials: during the conference organized by the Mathematics Department of Princeton University in honor of the 250th anniversary of Princeton University, he said something like: “Most of 20th century mathematics is the study of the harmonic oscillator”. (This can be seen, in a slightly different and weakened form, on page 120 of the Google Book preview linked above; my memory is that he did state, during his lecture, something closer to what I wrote; but that was a while ago, so I may be over-reacting in hindsight…)

P.S. For the obligatory etymological epilogue: the word “one-upmanship” is quite recent (1952), but “quip” goes back to the early 16th century. I didn’t know about the charming derivative “quipful” before looking in the OED.

An exercise

Here is a striking example of the unfortunate (but probably unavoidable) dispersion of mathematics: at the end of the abstract of V. Arnold’s talk at the recent conference in honor of A. Douady, one can read:

The Cesaro mean values K̂ of the numbers K(n) tend, as n tends to ∞, to a finite limit K̂(∞)=lim 1/n ∑m=1n K(m) = 15/π2. This theorem, deduced from the empirical observation of the coincidence of 20 first digits, is now proved, using the formula K̂(∞)=ζ(2)/ζ(4)

Here, K(n) is defined before in the abstract as the expression

K(n)=\prod_{p\mid n}{(1+1/p)}

Arnold’s achievements as mathematician are about as impressive as it can get. But the statement here is a completely elementary exercise in analytic number theory, and has been for at least one century (i.e., Dirichlet, or Chebychev, could do it in a few minutes, if not Euler).  Here’s the proof in Chebychev style:

K(n)=\sum_{d\mid n}{\mu(d)^2/d}

hence, exchaning the sum over n and the sum over d, we get

\sum_{n<X}{K(n)}=\sum_{d<X}{\mu(d)^2d^{-1} [X/d]}

and replacing the integral part by X/d+O(1), this is clearly asymptotic to CX with

C=\sum_{d\geq 1}{\mu(d)^2d^{-2}}

which is an absolutely convergent series. As an Euler product it is

\prod_{p}{(1+p^{-2})}=\prod_{p}{\frac{1-p^{-4}}{1-p^{-2}}}=\frac{\zeta(2)}{\zeta(4)}

as desired.

A combinatorial dichotomy

I have just read about the following very nice dichotomy: suppose we have an infinite set X, and a collection of subsets C in X; suppose further we look at all subsets F of X of finite size n, and at the subsets of F which can be defined by intersection of F with an element of C. How rich can this collection of subsets of F be, as F varies over all subsets of fixed (but growing) size?

For example, X could be the real line, and C the collection of half-lines ]-∞,a]. Then if we enumerate the finite subset F in increasing order

x_1\lt x_2 \lt \ldots \lt x_n

the subsets we obtain by intersecting with C are rather special: apart from the emptyset, we have only the n subsets of elements in increasing order up to some a:

x_1\lt x_2 \lt \ldots \lt x_r \le a

with r≤n. In particular, there are only n+1 subsets of F which can be obtained in this manner, much less than the 2n subsets of F.

As a second example, if C is the collection of all open subsets of the real line, we can clearly obtain all subsets of F as intersection of an element of C and F.

The dichotomy in question is that, in fact, those two examples are typical in the following sense: either one can, for all n, find an n element set F and recover all its subsets as intersection with C (as in the second example); or for any n and any F in X of size n, the number of subsets obtained from F by intersecting with C is bounded by a polynomial function of n. So it is not possible to have intermediate behavior (subexponential growth which is not polynomial), and this is certainly surprising at first (at least for me).

This very nice fact is due to Vapnik-Chernovenkis and Shelah, independently (published in 1969 and 1971, respectively). What is quite remarkable is that the first authors were interested in basic probability theory (they found conditions for the “empirical” probability of an event in the standard Bernoulli model to converge uniformly to the mathematical probability over a collection of events, generalizing the weak law of large numbers), while Shelah was dealing with model-theoretic properties of various first-order theories (in particular, stability).

In fact, these references are given by L. van den Dries (Notes to Chapter 5 of “Tame topology and O-minimal structures”, which is where I’ve read about this, and which is available in the Google preview), but whereas it’s easy to find the result in the paper of Vapnik-Chernovenkis, I would be hard put to give a precise location in Shelah’s paper where he actually states this dichotomy! This is a striking illustratation both of the unity and divergence of mathematics…

The proof of the dichotomy, as one can maybe expect (given the information that it is true), is clever but fairly simple, and gives rather more precise information than what I stated. Let’s say that C is a rich uncle of a finite set F if any subset of F is the intersection of F with a subset in C. We must show that either C is a rich uncle for at least one finite subset of every order, or else C only represents relatively few subsets of any finite subset.

First, a lemma states that:

Given a finite set of size n and a collection D of subsets of F, which contains (strictly) more subsets than there are subsets of F of size up to (but strictly less than) some d, one can always find in F a subset E of size d such that D is a rich uncle of E.

Note that this is best possible, because if we take D to be those substes F of size up to (and excluding) d, it certainly can not be a rich uncle of a set of size d.

If we grant this lemma, the proof of the dichotomy proceeds as follows: assume we are not in the first case, so for some d, C is a rich uncle for no subset of order d. Let n>d be given (to get polynomial behavior, we can restrict to this case), and let F be a subset of order n. The lemma (applied with D the intersections of C with F), and the definition of d, imply by contraposition that the number of subsets of F which are obtained by intersection from C is less than the number of subsets of a set of order n which are of order d at most. But this is a polynomial function of n, of degre d.

As for the lemma, I leave the proof as an exercise (see page 80 in the book of van den Dries, which is also in the preview), with a hint: proceed by induction on n. (One is tempted, in view of the statement, to use the pigeon-hole principle to say that D must contain one subset at least of order d, but the proof by induction doesn’t use that).

Now I am going to try and think if I can find some other application of this fact…

An exotic preprint server

In number theory, there is (as far as I know) no currently active preprint server, besides arXiv, and there hasn’t been one since quite a few years (there was an algebraic number theory preprint archive which was incorporated into arXiv around 1998, if I remember right). So I was intrigued to hear a colleague mention a very active preprint server for Linear Algebraic Groups and Related Structures, which contains a fair number of works of great interest which are not available on arXiv (some may be on individual web pages, but not all; for instance, among the more recent ones, neither preprint 292 nor 291 is on arXiv, but they are both quite interesting).

As befits the subject, there are of course plenty of papers there on exceptional groups and other exotic structures.

A local-global question (and how my mathematical grand-father solved a problem 28 years before it was raised)

I did a post a while ago on some “bad” mathematical terminology. I will here modestly continue with an example from my own work. Already a few years ago, I wrote a paper on some local-global questions where, among other things, I introduced something called a “fairly well-spread point” on a commuative algberaic group (defined over a number field). Some recent work of A. Perucca shows that this condition, for a point P in a simple abelian variety A/K is equivalent with asking that the Zariski closure of the subgroup generated by P is equal to A, a condition so natural that it deserves a better name (though she mentioned that some other people call this “independent”, which is also quite bad in its way).

To defend myself, the context of the definition for me was that I was trying to prove a certain theorem as cleanly as possible for as many algebraic groups as possible, and I had found that an even stronger condition (being “well-spread”) gave a nice proof, without undue tricks. But that condition is almost certainly true only in the case of (infinite order) points on elliptic curves or the multiplicative group (though I’m not sure if counter-examples are actually known), and I observed that only three consequences of the well-spread condition were used, leading to “fairly well-spread”. Since the three conditions were pretty ugly looking, I didn’t want to emphasize them. But the results of Perucca show I didn’t dig far enough to understand the true mechanisms involved…

But now I would like to point out something which, I think, my paper did right, compared with a number of other related works around the same time (2000-2003), which were interested in the so-called support problem.

The original version of this problem, apparently due to Erdös, concerns two non-zero integers x and y, and asks whether

for all prime numbers p not dividing x or y, the (multiplicative) order of x modulo p is equal the order of y modulo p,

implies that x=y.

This was first solved explicitly around 1995 by Corrales Rodrigáñez and Schoof, with an affirmative answer, and in a more general case (as described below).

What I think was useful in my contribution in this problem was to find a more intrinsic-looking variant, that makes sense in greater generality, and (probably) has a “cleaner” answer.

The first natural generalization that comes to the mind (I guess) of most algebraically inclined arithmeticians would be: for a commutative algebraic group G/K defined over a number field, and two rational points P and Q of G(K), what does the condition

for almost all prime numbers p of the ring of integers of K, the order of Q modulo p divides the order of P modulo p,

imply for P and Q? Then the question before amounts to looking at the multiplicative group over Q and integral points on it. Note that the original condition is stronger in asking for information modulo all primes where it makes sense, whereas for a general group, it certainly is easier to try to avoid, if possible, having to introduce the “best” integral model to reduce at. It is also stronger in the assumption of equality of the orders, but one quickly comes to see that the one-sided divisibility assumption is more natural. It also means the answer has to be more complicated than P=Q, because it is clear that Q=f(P) works, for any endomorphism f of G (defined over K).

This question is the version in the work of Corrales Rodrigáñez and Schoof, who proved that indeed the example above is the only possibility (if the points are of infinite order) for the multiplicative group or for an elliptic curve.

My own version was the following: given an algebraic group G/K (arbitrary, though of finite type of course), and a single point P on G, let <<P>> be the set of all Q such that

for almost all prime numbers p of the ring of integers of K, Q modulo p is in the subgroup generated by P modulo p.

Then the question is to compute this set <<P>>, indeed this subgroup (it is clearly a subgroup).

This question is not the same question as before, a priori, except in the simple case of the multiplicative group: indeed, then Q is in <<P>> if and only if it satisfies the assumption of the support problem, because in a finite cyclic group (such as the group of invertible elements in a finite field), the subgroup generated by an element x is uniquely determined as the set of elements having order dividing that of x. So the result of Corrales Rodrigáñez and Schoof, and the fact that the only endomorphisms of the multiplicative group are “raising to some integral power”, imply that <<P>>=<P> for any such group. But the converse is also true! Because Schinzel had proved the desired conclusion for the second problem as far back as 1960 (at least over Q), it follows that the question of Erdös was solved 28 years before he raised it (there is a very cute proof by Gallagher, based on his highly ingenious larger sieve, about which I will probably post one day).

My own paper (among other not-too-closely related problems) proved that the same conclusion holds for elliptic curves, and some other abelian varieties (those with trivial endomorphism ring with dimension 2,6, or odd). The case of CM curves illustrates a different with the support problem, where the existence of CM endomorphisms really does affect the answer.

Now, why do I think that my version is a better question than the support problem or its variants? (A position which, it should be said, has not been adopted by the other people working around this type of problems, though there are some works which call this the “linear dependence problem”).

There are two reasons.

(1) I do not ask for a “Yes or No” answer, but I want to compute some subgroup, which clearly contains <P>; if it is bigger, then it’s an interesting phenomenon that should be noted and investigated (just as, even if the ring of integers in a number field is not principal, its ideal class group, which encodes “how far” it is from being principal, is of capital importance). For example, in the case of the additive group, <<P>> is the set of Q-multiples of P (so, it is strictly bigger than the set of integral multiples).

(2) The setting seems more intrinsic, somehow. To emphasize this, the following properties are easy to prove: <<P>> is a subgroup with some “functoriality” property, which doesn’t depend on the choice of either the group G or the field K, provided P is in G(K). (In particular, e.g., one can compute it for tori if the answer is known in the split case). In an Appendix to my paper, I found easy examples that illustrate that the set of points Q satisfying the assumptions of the support problem can fail any of these three properties (for instance, for the additive group, the set in question is all of K, for any non-zero P, so it depends on K).

The best general result concerning the problem of determining the “subgroup locally generated by P” is really due to T. Weston (working independently of me, and without the general terminology): he proved that the subgroup locally generated by n elements (defined by generalizing in the obvious way the case of n=1 above) in an abelian variety with trivial endomorphism ring is contained in the subgroup generated by those elements and by the torsion subgroup of A(K). Note that this conclusion is not quite satisfactory in view of the properties above: it is not invariant under field extensions (or replacing A but a bigger variety).

It is open, but conceivable that for any abelian variety A/K, and any rational point P on A, we have <<P>>=<P>. On the other hand, for the general support problem, Larsen showed first that Q must satisfy f(P)=cQ for some endomorphism f and non-zero constant c, and then found examples where c can not be taken to be 1. This depends non-trivially on the structure of A and of its subgroup of rational torsion points. So finding a “general formula” for the set of Q solving the support problem for a given P seems difficult.