*(Continuation of part I)*

So, we’ve made rationals, and before we get to the favorite object, we are going to do another construction.

So far, we have only *numbers*. We don’t have anything which can “process” numbers in a sense. Much in the same way we extended the naturals with $\nu$ to make $\mathbb{N}[\nu]$, we can do the same, but this time, we will extend with an abstract object called $x$ which can serve as a placeholder for a number. So, we will extend the rationals with $x$ to give $\mathbb{Q}[x]$.

We can do our basic arithmetic operations (addition, subtraction, and multiplication; not division though, we need $Q(\mathbb{Q}[x])$ for that). So for example, we have $2+x$ or $8xxx-7$ or $x(x+2)(5x-6)$. Instead of $xxx$, we just write $x^3$. We can expand anything we construct out into a simple form: \[a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots,\] where $a_1, a_2, \ldots$ are rational numbers. If you don’t believe this, take $x(x+2)(5x-6)$ for example. After expanding, we get $(x^2+2x)(5x-6)$. Expand again, we get $5x^3+4x^2-12x$. Here, $a_0=0$, $a_1=-12$, $a_2=4$, and $a_3=5$.

These objects are called *polynomials*. More specifically, they’re polynomials with rational coefficients. If we substitute the indeterminate $x$ in a polynomial with a value, we can get a rational. So, we can view polynomials as *functions* when we can replace $x$ by a value.

Formally, we write a polynomial $p$ of *degree* $n$ (the highest power of $x$ is $n$) with coefficients $p_0,p_1,\ldots,p_n$ as a sum of *terms*: \[p = \sum_{k=0}^n p_k x^k.\]

Polynomials are themselves objects of course, and so we can, in an abstract sense, do to them the same as we did to the integers: form quotients. This we write as $Q(\mathbb{Q}[x])$, but more simply, we can just write $\mathbb{Q}(x)$. These are called the *rational polynomials*. A rational polynomial $q=(a,b)$ (remember that a quotient is represented by a pair? $1/2=(1,2)$, etc.) with coefficients $a_1, \ldots, a_n$ for $a$ and $b_1,\ldots, b_m$ for $b$. We write this mathematically as \[q = \frac{\displaystyle\sum_{k=0}^n a_k x^k}{\displaystyle\sum_{k=0}^m b_k x^k}.\]

Now, let’s step back and take a breath, and just review.

- We started off with the natural numbers.
- We added to the naturals a concept of “negative” by introducing an abstract quantity $\nu$, making the integers.
- We defined the concept of “part” and “whole” by making pairs of integers, where the first number is the part, the second is the whole. This made the rational numbers by forming quotients of integers.
- We introduced the “indeterminate”, $x$, which can be replaced with a rational number, and this allows us to have polynomials and polynomial functions.
- We took these polynomials, and made rational polynomials, which are just quotients of polynomials in the same sense as #3.

There are lots of ways to continue generalizing. For example, we can add more indeterminates, $y$ and $z$, to produce *multivariate polynomials* (which turn out to actually just be polynomials whose coefficients are polynomials!). We can do lots. But there is one peculiar generalization which really strums my strings of adoration.

Recall the geometric sum. A *geometric sum* is a polynomial whose coefficient ratios are constant. That is, given the polynomial \[p = \sum_{k=0}^n p_k x^k,\] we say it is geometric if for all $0\le k< n$, we have that $p_{k+1}/p_k = R$ for some rational number $R$ called the *common ratio*. For example, consider the sum \[\sum_{k=0}^n 2^k x^k.\] We see that $2^{k+1}/2^k = 2$. The ratio of successive coefficients is $2$, the common ratio.

This already has a good deal of “practical applications” (I add the scare quotes because, I don’t know, who cares). Archimedes used an infinite geometric sum (a *geometric series*) to compute the area under a parabola. In fact, he used \[\sum_{k=0}^n 2^k x^k\] substituting $x$ with $1/8$ to give \[\sum_{k=0}^n 2^k \left(\frac{1}{8}\right)^k = \sum_{k=0}^n 4^{-k}.\] However, he let $n$ tend toward infinity, even through the resulting area is finite, $4/3$ to be exact. (To go off on a tangent, is it possible to add an infinite number of things to get a finite result? Yes, an easy example: consider a candy bar. Pretend we could divide it infinitely. We could cut it in half, then in fourths, then in eighth, then in sixteenths, and so on infinitely. But if we never get rid of any pieces, then the whole candy bar, a finite amount of candy, is now divided into an infinite number of slices.)

Although we have quite some power with the tools we have, we still can’t express a lot of things. For example, can we express the $\sin$ function from mathematics with these concepts? Not exactly. It is true we can write a series for $\sin x$, but we wish to build the framework first, then express $\sin$ in it, not the other way around.

So, take the geometric sum, but instead of requiring the common ratio to be a rational *number*, require it to be a *rational polynomial* in terms of the index of summation. In other words, let \[p = \sum_{k=0}^n p_k x^k,\] and require that $p_{k+1}/p_k = R(k)$ where $R(k)$ is an element of $\mathbb{Q}(k)$. An example might be \[p = \sum_{k=0}^n \frac{1}{k!}x^k,\] where $k!$ is the factorial function ($5! = 5\times 4\times 3\times 2\times 1$ and $0!=1$ by definition). Here, $p_k = 1/k!$, and \[p_{k+1}/p_k = (k+1)!/k! = (k+1)k!/k! = k+1.\] And this indeed is a rational polynomial ($k+1 = (k+1)/1$). All geometric sums fit this category, since numbers are themselves a subset of rational polynomials. What is this category? Behold… these are the great, endeared favorite of mine… they are called…

**Hypergeometric Sums**

To put it bluntly, hypergeometric sums kick ass. To beat around the bush, hypergeometric sums represent a huge collection of mathematical functions (trigonometric functions, exponential functions, logarithmic functions, and tons more). And the best part is that hypergeometric sums are very clearly built up from the most basic objects, the naturals. Here are some hypergeometric sums: \[%

\begin{align*}

\exp x &= \sum_{k=0}^\infty \frac{1}{k!}x^k\\

\sin x &= \sum_{k=0}^\infty \frac{(-1)^k}{(2k+1)!}x^{2k+1}\\

\cos x &= \sum_{k=0}^\infty \frac{(-1)^k}{(2k)!}x^{2k}\\

\log (1-x) &= x\sum_{k=0}^\infty \frac{1}{k} x^k

\end{align*}\] Bessel functions, Legendre polynomials, Chebyshev, Laguerre, $\pi$, $e$, harmonic numbers, … I could go on forever naming what can be represented as hypergeometric functions. And all of these are made computable and constructive.

I will note that most of these are represented by hypergeometric *series*, infinite sums. Despite the fact that we are representing an infinite, never-completely-computable quantity, we have found a representation which allows us to compute as much precision as we want, while representing it in a way that only has fundamental objects and operations involved. Most of the finite hypergeometric sums come up in combinatorics and combinatorial identities, especially in counting and enumeration problems. ‘Tis why Doron Zeilberger, the great finitist and combinatorialist of Rutgers (and formerly Temple) University, has a deserved claim to fame for his algorithm, *Zeilberger’s algorithm*. What does it do? It computes hypergeometric sums in *closed form* (a form where the result is void of any summation or indexes, much like $4/3$ is a closed form of $\sum_k 4^{-k}$). Not only does it *compute* the closed form, it provides a* completely rigorous proof* that the closed form is valid. And if the algorithm says it doesn’t have a closed form, *then it is a proof that the sum has no closed form* (this is actually a little imprecise; it actually finds something called a *holonomic recurrence*, a recurrence relation whose terms are polynomials and whose solution is the sum. From there one can use techniques to solve recurrences to find the actual sum, if possible in closed form).

Recall that $\binom{n}{k}=n!/[k!(n-k)!]$ is the *binomial coefficient*. As an example, his algorithm can show \[f(n,k) = \binom{n}{k}x^k,\] satisfies the recurrence \[-(x+1)f(n,k)+1\cdot f(n+1,k) = \Delta_k C(n,k)f(n,k)\] where $\Delta_k$ is called the *difference operator* defined by $\Delta_k g(k) = g(k+1)-g(k)$ for some function in $k$, and $C(n,k)$ is called the *certificate* and in this case is, given by Zeilberger’s algorithm, \[C(n,k)=-\frac{k}{n+k-1}.\]Â What good is this? Well, $\Delta_k C(n,k)f(n,k)$ has a very special property, namely that \[\sum_{k=0}^n \Delta_k C(n,k)f(n,k) = 0.\] So, if we sum both sides of the recurrence, we have \[%

\begin{align*}

\sum_{k=0}^n \big[-(x+1)f(n,k)+1\cdot f(n+1,k)\big] &= \sum_{k=0}^n\big[\Delta_k C(n,k)f(n,k)\big]\\

-(x+1)\sum_{k=0}^n f(n,k) + \sum_{k=0}^n f(n+1,k) &= 0.

\end{align*}

\] Write \[S(x) = \sum_{k=0}^n f(x,k)\] giving \[ -(x+1) S(n) + S(n+1) = 0. \] This is a first-order linear recurrence and can easily be solved: \[S(n) = (x+1)^n,\] which of course is the binomial theorem.

As a much more complicated example, consider \[f(n,k) = \binom{2k}{k}\binom{n}{k},\] which, as his algorithm shows, satisfies \[\small\begin{aligned}&9(n+1)^2 f(n,k)\\ &\quad - (10n^2 + 30n + 23)f(n+1,k) + (n+2)^2 f(n+2,k) = \Delta_k [ C(n,k) f(n,k) ],\end{aligned}\label{eq:z2}\] where \[C(n,k) = -\frac{k^3(n+1)^2(4n-3k+8)}{(n-k+1)^2(n-k+2)^2}.\] Sum both sides of the recurrence, and get \[%

\begin{align*}

\sum_k \left[9(n+1)^2 f(n,k) - (10n^2 + 30n + 23)f(n+1,k) + (n+2)^2 f(n+2,k)\right] &= \sum_k \Delta_k [ C(n,k) f(n,k) ]\\

9(n+1)^2 \sum_k f(n,k) – (10n^2 + 30n + 23)\sum_k f(n+1,k) + (n+2)^2 \sum_k f(n+2,k) &= 0.

\end{align*}

\] If we write $S(n) = \sum_k f(n,k)$ as we did previously, then we have \[ 9(n+1)^2 S(n) - (10n^2 + 30n + 23)S(n+1) + (n+2)^2 S(n+2) = 0,\] which is a holonomic recurrence in $n$. In this case, we cannot solve the recurrence in a closed form, but we *can* solve it in terms of *indefinite hypergeometric series *(hypergeometric functions which do *not* depend on the upper bound of summation). For the curious reader, the solution is \[\frac{1}{(-n-1)!\,\sqrt{\pi}}\sum_{k=0}^{\infty} \frac{(k+1/2)!\,(k-n-1)!}{k!^2}(-4)^k,\] a hypergeometric sum.

So, while the particular uses of hypergeometric sums may not appeal to the reader — or while their use still isn’t clear to the reader — I hope that the construction can be appreciated; that very rich mathematics can be *simply* derived from the most basic elements.

By the way, as I mentioned in my earlier post, I am making a computer algebra system called *Doron*, and the name was derived from *Doron Zeilberger*, precisely to celebrate his algorithm (which is very important in computer algebra), but also because of his promotion of so-called experimental mathematics (which I will write about some other time), which the system is dedicated to doing.

Take care.

*Fun Fact! The fastest way (in the practical, non-theoretical sense) to compute $\pi$ on a 32-bit computer is Chudnovsky’s formula for $1/\pi$, which is *\[\frac{\sqrt{640320^3}}{12\pi} = \sum^\infty_{k=0} \frac{(6k)!\, (545140134k+13591409)}{(3k)!\,k!^3}\left(-\frac{1}{640320^3}\right)^k,\]* a hypergeometric series. Notice how all integers fit into 32-bits of memory, allowing for fast CPU arithmetic.
*

## Response

Robert Smith:Turning on TCO by default mucks around with things like dynamic variables. One has to be careful about that. Some peopl...Gabriel Laddel:Is there any reason one wouldn't want TCO? I'm unaware of any downsides of adding it to the CL standard.Manuel Reyes:Hi there, your post feels so familiar! I've been working at Google as Vendor for the past year and a half, and I've bee...Guillaume Dosser:I think it is possible to use only one call of the random function as there is a limited number of shuffled arrays. (n! ...Lee:wow. from the interview questions you answered well, i'm shocked you didn't get hired quickly. anyways, this makes me fe...