Bhargava's Factorials

Bhargava’s Factorials

Wow. Hard to believe we’re already a week into February. I began my new year with a trip to the 2010 Joint Mathematical Meetings, and I came back with a head and several notebooks full of ideas to contemplate and problems to solve. I’ve missed my little blog here while I’ve been lost in the unexplored corners of the mathemativerse. Sad truth that, until and unless I am tenured, I can’t afford to pass up any opportunities for research; I do have a family to think of. I haven’t been around here for a while, and I’m sorry for that. But today’s post should be a doozy.

Our topic for today comes from this year’s JMM, where the inimitable Manjul Bhargava gave an MAA invited address on factorial functions. (Coincidentally, I first learned about the topic of his talk when I read an article of his, reprinted in the charming book Biscuits of Number Theory, which I bought at the 2009 JMM.)

Wait a minute, factorial functions? That’s what gets talked about at the biggest math conference of the year, where people on the cutting edge of research mathematics get together, factorials? The ones you learned about in high school? Can there really be more to learn about $n!$ ?

Amazingly enough, yes. In a conference full of zonotopal algebra and cohomology and harmonic analysis, one of the invited addresses was about factorials. And it turns out that there is more to learn; factorials are really just the tip of an enormous iceberg.

The Factorial Function Revisited

By now you should all have heard of the traditional factorial function $n!$ , defined as the product of all the integers between 1 and $n$ inclusive.

Here is an alternative definition of the factorial function.

Pick a prime number $p$ .

Pick any integer whatsoever to be $a_0$ .
Now we want to choose an integer to be $a_1$ ; we choose it so that $(a_1-a_0)$ is divisible by as small a power of $p$ as possible. (There will probably be many equally good choices for $a_1$ , so make the choice arbitrarily.)
Now choose a third integer $a_2$ so that $(a_2-a_0)(a_2-a_1)$ is divisible by as small a power of $p$ as possible. (Again, if there are equally good choices, choose whichever you like.)
In general, choose $a_k$ so that $(a_k-a_0)(a_k-a_1)(a_k-a_2)\cdots(a_k-a_{k-1})$ is divisible by the smallest power of $p$ possible.

As we go along, we record the list of $a_i$ and also (more importantly) the list of powers of $p$ which divide the products.

As an example, consider the prime 2.

I choose $a_0=19$ . This is totally arbitrary. (By convention I’ll say that the power of 2 is always 1 at the first stage, when there is no product to speak of.)
If I take $a_1$ to be even, then $a_1-19$ won’t be divisible by two at all, so I take $a_1=42$ . (The power of 2 is 1 at this step.)
Now it is inevitable that $(a_2-19)(a_2-42)$ will be even, but we can prevent it from being divisible by 4. Take, say, $a_2=9$ . (The power of 2 is 2 now.)
Again, an even product is inevitable, but I can still keep $(a_3-19)(a_3-42)(a_3-9)$ from being divisible by 4 by taking $a_3=0$ , say. (Again, the power of 2 is 2 at this stage.)
In the product $(a_4-19)(a_4-42)(a_4-9)(a_4-2)$ , no matter what I do two of the terms will be even, and one of them will be divisible by 4. So the best I can hope for is to make the product divisible by 8 (but not 16), and that can be done by taking $a_4=15$ . (The power of 2 is 8 here.)

In this example, I began the sequence $19, 42, 9, 2, 15,\ldots$ , and obtained the sequence of powers $(1,)1,2,2,8,\ldots$ . What is amazing, given all the free choices involved in constructing the sequence, is that the sequence of $p$ -powers is well-defined! It does not depend on any of our choices! For the prime 2, we get the sequence $1,1,2,2,8,8,16,16,128,128,256,256,\ldots$ .

We repeat the process for all the other primes as well. For the prime 3 we get $1,1,1,3,3,3,9,9,9,81,81,81,243,243,243,\ldots$ ; for the prime 5 we get $1,1,1,1,1,5,5,5,5,5,25,25,25,25,25,\ldots$ ; etc. (You may begin to see some patterns; you might want to play around with building the sequences $a_i$ for other primes.)

Once you have all these sequences of $p$ -powers, we can multiply them all together. The whole big sequence starts $1,1,2,6,24,120,720,\ldots$ .

And we should recognize this sequence! It’s $0!, 1!, 2!, 3!, 4!, 5!, 6!,\ldots$ . This whole elaborate process serves as an alternative description of the classical factorial function!

I regret that I can’t give you any idea how a person would ever think of this construction for the factorials. I think you have to be Manjul Bhargava to do that.

And you will be forgiven for thinking that this is an absurdly elaborate way to define something that already had a perfectly simple and user-friendly definition. But read on.

Generalized Factorials

Now let $S$ be any infinite set of integers whatsoever. (Actually this definition is dramatically more general, and we can work with quite general rings instead of just the integers; but I don’t want to assume that you are familiar with such objects.) For example, you might take the set of square numbers, or the set of prime numbers, or the set of integers with no 7′s anywhere in their decimal expansion.

Then apply the definition as before! For every prime $p$ , form a sequence of $a_i$ in order to generate the sequence of powers of $p$ in the product. The only new rule is that all your $a_i$ must come from $S$. Just as before (and just as miraculously), the resulting sequence of powers will always be the same no matter what choices you make. Then multiply the prime powers together to obtain the values $0!_S, 1!_S, 2!_S, 3!_S,\ldots$ .

I’m a number theorist, so the example I’ll play around with is the set of prime numbers. Let $P$ be the set of primes. I spent a little bit of time on the bus this morning playing with numbers to work out this sequence; I encourage you to engage in a little number-play of your own.

For $p=2$ , one possible sequence that minimizes the powers is $2, 3, 5, 7, 17, 11, 13,\ldots$ , giving the sequence of powers $1, 1, 2, 8, 16, 128, 256,\ldots$ . Notice this sequences is growing faster than the one for the classical factorial. This is because we have fewer choices for the $a_i$ , so we get forced into higher powers of $2$ sooner.
For $p=3$ , one possible sequence that minimizes the powers is $2, 3, 7, 5, 13, 17, 19, \ldots$ , giving the sequence of powers $1, 1, 1, 3, 3, 9, 9,\ldots$
For $p=5$ , one possible sequence that minimizes the powers is $2, 3, 5, 19, 11, 7, 13, \ldots$ , giving the sequence of powers $1, 1, 1, 1, 1, 5, 5,\ldots$
For $p\geq 7$ , we have enough freedom that the sequence begins $1, 1, 1, 1, 1, 1, 1,\ldots$

Assembling these sequences gives us $1, 1, 2, 24, 48, 5760, 11520,\ldots$ . This gives us the first few values of the “prime factorial function”. $0!_P=1, 1!_P=2, 2!_P=2, 3!_P=24, 4!_P=48, 5!_P=5760, 6!_P=11520.$

This is the upshot: when restated as above, the definition of factorial applies to any infinite set of integers whatsoever! With one definition, we get a factorial function based on the primes, a factorial function based on the squares, etc. For centuries mathematicians have worked with the classical factorial function, little suspecting that it was just the most basic member of an enormous family of related functions.

Key Idea: Ubiquity

Okay, you have every right not to be impressed yet. I mean, just because you can make up a function doesn’t mean that it’s interesting.

The classical factorial function is well-known to all mathematicians, and it’s not just because exclamation points are fun to write. It’s because the factorial function enjoys lots of interesting properties and shows up in the answer to lots of questions from all corners of mathematicians.

$\frac{(m+n)!}{m!n!}$ is always an integer, for any $m,n\geq 0$ . (Moreover, this integer is the binomial coefficient, and is the answer to a whole raft of counting problems.)
If you pick any integers $a_0, a_1, \ldots, a_n$, then the product of all the possible differences among them $\prod (a_i-a_j)$ is \emph{always} divisible by $0!1!2!3!\cdots n!$ , and that’s not true for any larger number.
Consider the polynomial $f(x)=3x^2+5x+2$ , to be evaluated at integers. Even though the coefficients (3 and 5 and 2) have no factors in common, all the values of $f(x)$ are even. (Why is that?) You might think of 2 as a “hidden” factor of $f$ (hidden because 2 doesn’t divide all the coefficients). In general, if we form an $n$ -th degree polynomial with integer coefficients, how large can the hidden factors be? The answer is $n!$ .

(And I could go on with this list almost endlessly, all across the spectrum of mathematical sophistication.)

In a word, the factorial function is ubiquitous. One of the reasons that mathematics is so powerful, so beautiful, so borderline-magical, is that there are some big ideas that manifest themselves in totally unrelated-seeming areas. Think of $\pi$ and $e$ , for example.

And this is what’s so amazing, almost belief-defying. You can adapt the questions in my above list (and lots of others) from $\mathbb{Z}$ to arbitrary sets $S$ , and the answers always come by just replacing the classical factorial function by the generalized one.

$\frac{(m+n)!_S}{m!_Sn!_S}$ is always an integer, for any $m,n\geq 0$ .
If you pick any integers $a_0, a_1, \ldots, a_n$in $S$ , then the product of all the possible differences among them $\prod (a_i-a_j)$ is \emph{always} divisible by $0!1!2!3!\cdots n!$ , and that’s not true for any larger number.
In general, if we form an $n$ -th degree polynomial $f(x)$ with integer coefficients and evaluate $f$ at numbers in $S$ , how large can the common factors of all the $f(x)$ be? The answer is $n!_S$ .

I close on a note of wonder and mystery. Mathematical innovation is happening all the time, at the hands of mathematicians, both university professors and home enthusiasts, and admittedly most of it is happening in distant corners of the mathiverse, in places that would take years or decades of study even to understand the questions. This might lead you to think that mathematical research has nothing to do with anything that nonmathematicians understand. But Bhargava’s factorials tell us a different story.

The next big mathematical innovation could be about anything. Any idea, even an idea that’s been thoroughly studied for hundreds of years, might conceal a big secret, just waiting to be looked at in the right way.

About these ads

This entry was posted on Monday, February 8th, 2010 at 14:11 and is filed under Articles. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to Bhargava’s Factorials

NAA: Bhargava’s Factorials « Cap Khoury's Miscellanea says:

8 February 2010 at 14:19

[...] Permalink: Bhargava’s Factorials. [...]

Reply

Not About Apples