Pretending In Number Theory
A definition is often more important than a theorem
Andrew Granville is a British mathematician and a world expert in analytic number theory. He came to Canada for his PhD, and after a postdoc in Toronto and time at IAS in Princeton, joined the faculty of another Georgia university, Tech’s arch-rival in football, the “Bulldogs” of the University of Georgia. After serving as Chair of Mathematics there he went back to Canada in 2002 to join the Université de Montréal, where he is today. Interestingly his university also has a football team, where “football” does not mean soccer like in Britain, but does not quite mean football. It plays Canadian football, which uses a wider and longer field for teams of 12 not 11 but allows only 3 downs to advance 10 yards. Is that football? It depends on how you define “football.” Anyway, his new team is not a rival of ours.
Today I wish to discuss the role of the right definition in advancing mathematics and theory in general, and Granville’s relatively new brilliant definition in particular.
Granville is both a solver of hard open problems, and the writer of beautiful papers. He takes time to write insightful expository articles and has won several prizes for them. Five years ago he won the coveted Chauvenet Prize from the Mathematical Association of America for his paper “It is easy to determine whether a given integer is prime” surveying developments ushered in by the polynomial congruence method of Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, which yielded the first deterministic polynomial-time algorithm for primality.
He has a short survey on his website with the provocative title
“Don’t be seduced by the zeros!”
—about alternatives to the zeta function as tools for analysis. He is also the keeper of a indispensable web resource—a summary of many of the properties of binomial coefficients—if you need to know about them, check out this page.
A definition, as used in mathematics, cannot be wrong. Every definition is legal, is allowed, none can be wrong. A definition can, however, be useless, unproductive, or just plain uninteresting.
A definition really is just a shorthand for some concept, and the definition itself can always be eliminated. Yet a definition can be amazingly powerful. The right definition suggests the right conjectures, the right arguments, and the right definition can make understanding a proof much easier. A definition can be of immense power.
Consider a simple example from number theory:
We know that this concept is of great importance, and is used in basic results and in advanced results throughout math. The classic proof that the square root of is not a rational number is based on an argument that uses this concept. We could prove this result without this definition; we could, but it would be much harder to follow. That is the beauty of the right definition.
Consider another example: the notion of a graph. Leonhard Euler in 1736 invented graph theory, with the publication of his famous paper on the Seven Bridges of Königsberg—here it is in Latin. Below is a diagram from the original paper:
And here is how we view it today:
One could also argue that he invented topology, but he certainly invented graph theory. He essentially defined the notion of a graph, and opened a new chapter in mathematics. Euler did a mountain of great work, solved hard open problems, but this definition was one of his greatest results.
Before going on to discuss a relatively new definition due to Granville, I note that mathematical logicians care about the elimination of definitions. They know that they can always be removed, although sometimes the removal can lead to an increase in the length of a proof. See for example the paper by Jeremy Avigad on the cost of elimination of definitions in proofs in first order logic. Spoiler alert: the cost in first order theory is at most a polynomial increase in length.
Andrew Granville and Kannan Soundararajan have created a beautiful definition that has already made important changes to number theory. They have defined the notion of when one function pretends to be another one. It allows them, for example, to give a new proof of the prime number theorem: which they call
“A pretentious proof of the prime number theorem”.
The definition is wonderful; the name is clever; and the notion suggests lots of new directions.
A meta-comment before I give their main definition. The idea that one math object can “pretend” to be another is really related to the notion of distance. Instead of number-theoretic functions consider a simple pair of vectors, say and , that lie in some Eucliden space. We could say that “pretends” to be if the distance between and is small. Certainly this notion of pretending makes good sense: if is near , then often statements about also hold for —especially if the statements are stable under small perturbations. Many general statements about football also apply to Canadian football, such as the importance of having a good field-goal kicker, the nature of various passing plays, the need to gain 10 yards. Other differences matter more, such as the end zones being twice as deep as in the US, which compensates somewhat for having only 3 downs when the offense is close to the end zone.
Granville with his colleague Soundararajan have noted that , well let me quote the abstract to one of their short papers on the notion of pretending:
We note how several central results in multiplicative number theory may be rephrased naturally in terms of multiplicative functions that pretend to be another multiplicative function . We formalize a `distance’ which gives a measure of such pretentiousness, and as one consequence obtain a curious inequality for the zeta-function.
The inequalities they get are indeed curious:
See their paper for full details. Also look at this page, which is the main page of a course that Granville gave in 2011. The title of the course is: Pretentious Introduction to Analytic Number Theory.
One version of the problem is this: Suppose that takes on values and is multiplicative. Erdös asked years ago, and placed a $500 prize on its answer, whether is it possible (for any such function) that the partial sums of are bounded.
The development, shown last year in a paper by Joseph Vandehey, is that if we use the notion of pretender then the resulting analogue of this still-open problem has a positive answer.
Here is what he proved. For a function to be multiplicative it suffices to stipulate that
for every prime . The key insight is to weaken this definition. Call a function a multiplicative pretender if the above holds only for primes in some finite set . Then Vandehey can prove that there do exist such functions so that
for all . The proof is a clever case analysis that constructs the actual function.
I like the idea of viewing one function as pretending to be another. That it already has been very powerful in number theory suggests we might use the notion in complexity theory. Can we define the right definition about pretenders for objects that we study? How would the pretender notion be used in the study of boolean functions, or the study of complexity classes? Indeed, what are the right definitions?