Short Course on Asymptotics
REU Number Theory Program, Summer 2002

Course Description

There are many situations in mathematics where one encounters expressions, such as complicated sums or integrals, that cannot be evaluated exactly, or where exact answers are too complex to yield useful information. In many of these instances it is possible to to obtain relatively simple approximate evaluations which in applications are often just as useful as an exact formula. Asymptotics (or, more precisely, asymptotic analyis) deals with methods to obtain such approximations. The terminology comes from the fact that the expressions usually involve a parameter (e.g., an integer n), and that the approximation gets better the larger this parameter is.

Asymptotic analysis has a wide range of applications, both to areas of pure mathematics such as number theory, combinatorics, probability theory, analysis, and to applied mathematics and computer science, for example in the analysis of the running time of computer algorithms. This course will be an elementary introduction to this theory at the undergraduate level. Here is a (tentative) outline:

Notation and terminology in asymptotics

To express approximate evaluations in a compact, yet precise and unambiguous form, requires using appropriate notation, such as the "Capital Oh" and "little oh" notations O(f(x)) and o(f(x)). These and related notations have precise meanings, and it is important to use these notations properly and be aware of potential pitfalls. This requires some practice.

Approximate evaluations of integrals

The logarithmic integral. Li(x) is the integral of 1/log y from 2 to x, called the logarithmic integral. It plays an important role in prime number theory (as the best known approximation to the number of primes below x), so having good information on its growth is important.
The error function integral This is the integral from x to infinity of the "bell curve function", exp(- x²). It is important in probability theory.
Oscillating integrals. Integrals involving sin x, cos x, or a complex exponential, such as the integral of (sin y)/y, from 0 to x.

Factorials and binomial coefficients

Stirling's formula. Perhaps the most famous asymptotic formula is Stirling's formula, giving an approximate evaluation of the factorial function, n!, when n is large.
The middle binomial coefficient. The largest of the binomial coefficients (n choose k) is the middle one, with k = [n/2]. When n is even, this coefficient represents 2^n times the probability of getting exactly n/2 heads in n tosses. As an application of Stirling's formula, one can derive an approximation to this coefficient (and hence to the probability mentioned).
Central binomial coefficients. The binomial coefficients decrease in size as one moves away from the middle coefficient. Because of the probabilistic interpretation it is of interest to determine more precisely the nature of this decay. It turns out that, when n is large, the decay follows very closely a properly scaled "bell curve". This is the famous De Moivre theorem in probability theory and a special case of what is called the "Central Limit Theorem."
Partial sums over binomial coefficients. The sum of the binomial coefficients (n choose k) over all k from 0 to n is 2^n, by the binomial theorem. By symmetry, it follows that if n is even, the partial sum over k<n/2 is exactly half of the complete sum. But what if the the sum is cut off at some intermediate point, say k< cn, with some real number c between 0 and 1/2? In this case, an exact answer is no longer possible, but with asymptotic techniques one can obtain good approximate answers.
Sums of powers of binomial coefficients. A well-known relation for binomial coefficients states that the sum over the squares of the coefficients (n choose k), from k=0 to k=n, is equal to the coefficient (2n choose n). However, there is no analogous formula if the second power is replaced by a more general power, say the cube, or a fractional power, such as 1/2. Here again asymptotic analysis provides some information.

Asymptotic analysis of sums

Euler's summation formula. This is an important formula that relates a sum over integers to the corresponding integral. Since integrals are usually easier to deal with than sums, this can be used to obtain approximations to sums.
Summation by parts. Also called partial summation, this is another important and useful general technique to deal with sums.
Harmonic numbers. The n-th partial sum of the harmonic series, the sum of 1/k from k=1 to k=n, is denoted by H_n and called the n-th harmonic number. There is no "closed" formula for these numbers, but one can use Euler's summation formula to obtain a remarkably accurate estimate.
Partial sums of the exponential series. The sum over x^n/n!, from n=0 to infinity, is, of course, given by the exponential function e^x. What if the sum is truncated at some index N? Again there is no closed formula, but with asymptotic methods one can obtain good estimates for such partial sums when x is large. Such estimates have a probabilistic interpretation.

Asymptotic analysis of inverse functions

The W-function. Trying to solve the equation w^w = x for w leads to the "W-function", for which there is no explicit formula. However, using asymptotic techniques such as "bootstrapping" and iteration, one can come up successively better approximations.
Roots of the equation cot x = x. This equation has infinitely many positive solutions x. One sees rather easily (by considering the graphs of the functions cot x and x) that there is one such solution in each interval [n pi, (n+1) pi], but to determine more precisely the location of these solutions requires asymptotic techniques.
Estimate for p_n, the n-th prime number. There is no (practical) known formula for the n-th prime number, so one has to resort to approximations. This leads to the problem of approximately solving equations such as Li(x) = n for x, or equivalently determining (approximately) the inverse function of Li(x). There is no explicit formula for the inverse function of Li(x), but one can use bootstrapping and iterative methods to obtain good approximations.

Short Course on Asymptotics REU Number Theory Program, Summer 2002