Fundamentals of Asymptotic Analysis

When establishing the size of certain problems and the time complexity of certain algorithms, especially for those closely related to number theory, a skirmish with number theoretic functions and their prefix sums may be inevitable. They are in staircase shape, some of them are hard to visualize or calculate directly, while precise calculation is unnecessary when we just want to estimate the size or complexity.

And this is how the natural idea of asymptotic analysis comes into being. With the exotic work of numerous mathematicians, we have finally established a theory to provide smooth or even analytic alternatives to their staircase counterparts, with reasonable error terms. The theory comes with basic asymptotic result as building blocks, along with validated principles to compose them, to apply them in complexer scenarios.

In this text, we are going to introduce some fundamental principles and techniques of asymptotic analysis. They are the foundation of deeper content in analytic number theory.

Asymptotic notations

We may be familiar with analysis of complexity of algorithms, and uses small-Oh and big-Oh notations there. Such notations are also commonly used in asymptotic analysis in analytic number theory, but with a little bit variation, in order to adapt to the definition of number theoretic functions:

Definition (Small-Oh and Big-Oh Notations)

Let there be functions and such that , the modulus of complex number, we have:

Proof. Here's just some comments on the translation to the limits.

In the case of , one can simply find it can be translated to language with in the place of and in the place of , defining the limit , which will converge to as .

In the case of , such a weak constrain cannot guarantee to converge, just take and we will see. However, it guarantees the limit superior of to exists as there has already been . Conversely, if we know , which indicates , then just choose and let , and then we are done with the existence of and .

For convenience, we ellide certain terms with asymptotic notations in appropriate circumstances: for functions and such that , we may write:

In order to be useful, we may always require that in either cases.

Meantime, is said to be asymtotically equal to when , and denote it as . Actually, we have:

Lemma

Proof.

Euler's summation formula

Euler's summation formula provides us a handy way to do asymptotic analysis for ranged summation in the form of , which is:

Theorem (Euler's Summation formula)

For integers and continuously differentiable function where is the derivative of , we have:

Proof. First, for any integer , we have:

Which can be fixed into .

Then, we know there's , sum the left side and we will have:

Now we are done with the proof.

With a little modification, we can get a more general form extended to those ranged from real numbers:

Corollary

For real numbers and continuously differentiable function where is the derivative of , we have:

Proof. Let and . Noted that there's , but , so we must only sum from to :

We would like to pad the integral range from to , and we know:

With them, we can pad the integral and finally we have:

Which can be fixed into the formula we would like to prove.

Here's a direct application of the Euler's summation formula:

Theorem (Asymptotic Expansion of Sum of -th Power)

Proof.

We all know the harmonic series diverges, but few know it can also be replaced asymptotically:

Theorem (Asymptotic Expansion of Harmonic Series)

Where is the Euler–Mascheroni constant.

Proof. By Euler's summation formula we have:

The integral in the middle can be splitted by . And they can be furtherly fixed into:

Where the replacement of into is due to the following rationale at each positive integer :

All it remains is to show the limit converges to a constant.

Let , first we can see there's , let while with little analysis we can see , which indicates and is monotonically increasing as .

On the other hand, we can see is below whenever there's , in the range of , the area between and the -axis is , while the area between and the -axis is , so we have , and is bounded above.

Since is monotonically increasing and bounded by , it must only converge to a constant. More precisely, noted that , must converge to a constant in . Commonly we will let , so we eventually have:

And we are done with the proof.

The harmonic series occurs very often in analytic number theory, recall that , which is in harmonic series form, we would like to show:

Corollary (Dirichlet's Formula)

Proof.

Please notice that will not annihilate to unless they can be shown to be equal after some algebraic transformations. Actually need not to be positive, it just represents how much error there will be deviated from its actual value, or how fast will the error diminish as increses in its magnitude.

Here's another example where Euler's summation formula is applicable:

Theorem

Proof. By Euler's summation formula we have:

Again, with analogous rationale of how we deal with the intermediate integral of asymptotic expansion of , we will deal with the integral , in the way shown as below:

Where the replacement of into is due to the following rationale at each positive integer :

Let to study its convergence, with constrained to as we are inspecting its behavior at infinity. We can see there's . We can see is decreasing monotonically since . Noted that corresponds to the area of between and while corresponds to the area of between and , which is below . Therefore, and decreases monotinically whenever there's .

On the other hand, the graph of is below when there's . Between and , the area of the former is , while the latter is , which means , which means is bounded below. In this way, we know converges to a constant, and we can let .

Replace the result relative to the intermediate integral , and we get , and we are done with the proof.

Riemann zeta function

Besides harmonic series, we may also encounter its variation in the form of . First we would like to show:

Lemma

When , the series converges to a constant.

Proof. First, all of them are monotonically increasing as , so all it remains is to show it's capped above. Noted that:

Which means when , series must converge to a constant in .

When , the series diverges as they are greater than the harmonic series which diverges. But we can still show:

Lemma

When , converges to a constant.

Proof. Just like what we've done before, let . One should find no difficulty in confirming:

Noted that the diagram of is above whenever , which means there's always whenever , and thus there's always .

Then, consider , with and , so it must be , and is decreasing monotonically as .

So in order for to converge as , it must be bounded below. It's time to consider the ordinary , in which the diagram of is always below , so we have:

Which means must converge to a constant in as .

As they converge, mathematicians has defined a function to yield their convergence values, which is the Riemann zeta function:

Definition (Riemann Zeta Function)

With Riemann zeta function, we can write down the asymptotic expansion of as:

Theorem (Asymptotic Expansion of Harmonic-Like Series)

Proof. First, inspired by the form of Euler's summation formula, for each positive integer , it won't be hard to show:

For the interval of integral , we have:

And we also have , since .

Then, it must be mentioned that whenever it's or , since:

When , we have and ;
When , although and , but we have already defined and proved .

Finally, the asymptotic expansion can be obtained in the way as below:

And we are done with the proof.

With Riemann zeta function and the asymptotic expansion of , we are able to expand asymptotically, which is:

Corollary (Asymptotic Expansion of Prefix Sum of Divisor Sum Function)

Proof.

Abel's identity

The Abel's identity, also known as the Abel's summation formula, is a common summation technique that appears in both fundamental real analysis and asymptotic analysis, comes in formally and analytically:

Lemma (Abel's Identity, Formal Transformation)

For real numbers , number theoretic functions where , and continuous functions , we have:

Proof.

Theorem (Abel's Identity, Analytic Transformation)

For real numbers , number theoretic functions where , and continuously differentiable functions where is the derivative of , we have:

Proof. Utilize the feature of and we have:

Substitute them back and we have:

Which is in the form of what we are to prove.

Sometimes it's also considered to be more general than the Euler's summation formula, as Euler's summation formula can be seen as letting , which results immediately in:

However, as we can see, the Euler's summation formula does provide us with a common way to accomodate each terms in simple asymptotic expansion.

We will reveal more common usage in the following texts, and let's leave it for now.

Faulhaber's formula and Bernoulli numbers

We have shown the asymptotic complexity of the sum of -th power to be , using the Euler's summation formula. However, such a coarse approximation with remainder term up to can be shown to be insufficient under many cases, and when is integer, we can even derive a closed form for such summation, the Faulhaber's formula.

For convenience, we may let where , for any appropriate input. First, by applying the Abel's identity, we would like to show the following recurrence relationship exists:

Lemma

Proof. First, we apply the Abel's identity by seeing the summation as , and then we have:

Then, move the term of to the left, and the left hand side becomes . Noted that , so we will move the term to the right. So we have:

Replace by via offseting and we are done.

Corollary

Proof. Just expand the term furtherly:

Although the expansion in such a way above requires , but it won't be hard to find it's still true for and .

The theorem and collary enable us to write the code to compute the sum of -th power:

from typing import *

# compute A_0 up to A_m in Faulhaber's formula
def faulhaber(N: Any, m: int, idiv=False) -> List[Any]:
	A = list([None] * (m+1))
	A[0] = N # A_0 = N
	binom = list([0] * (m+1)) # space up to m
	binom[0] = 1
	Np = list(N**k for k in range(0, m+2)) # N^0 to N^(m+1)
	for k in range(1, m+1): # 1 to m
		# update binom for subscript k first
		prev = 1
		for i in range(1, k):
			prev, binom[i] = binom[i], prev + binom[i]
		binom[k] = 1
		# evaluate A_k now
		kp1Ak = (Np[k+1]) + k*(Np[k]) + sum(
			binom[l-1] * (Np[l]-A[l]) for l in range(1, k))
		A[k] = kp1Ak // (k+1) if idiv else kp1Ak / (k+1)
	return A

# normal usage with python integer
#print(faulhaber(10**7, 100, idiv=True))

# use sympy to export the result
import sympy
N = sympy.var('N')
A = faulhaber(N, 17) # A_0 up to A_17
for i, expr in enumerate(A):
	print(f'A_{i} = {expr.expand()}')

Which generates the following result:

With a little bit of mathematical induction, one can easily see the closed form of must be a polynomial with leading term , which matches our previous result of asymptotic expansion. On the other hand, there's zero constant term for every , also due to the mathematical induction.

The coefficient of in each must always be . Since it's true for , and when , it's calculated from:

Where is from the leading coefficient of .

Other terms in besides seem to be rather random, but they can be shown to be in order and and goverened by a single closed form formula, due to Bernoulli.

To show, we first need to get aquainted with a technique called binomal inversion:

Theorem (Binomial Inversion)

Proof. Let's denote:

Clearly there's , where is non-degenerated and thus the inverse exists. If the equivalence to prove would like to be true, we need to show its inverse is exactly in the form of:

Such that .

While one can directly check whether , but actually we can deduce each row in from . Clearly by letting , we have . And by Gaussian elimination clearly on first rows of and then the last row, we have:

Alongside with:

It's easy to check is indeed in the form we expected, by mathematical induction, we assume is in the form we expect it to be, and all we need to show is . However, for the -th item inside, we have:

Which completes the proof.

The transformation applied in our proof is just like the binomial inversion, and can be proof with the analogous rationale:

Lemma

Proof. Just like what we've done in the theorem of binomial inversion:

(Be wary of the matrix size, this time there're rows in , rather than rows in the previous case of binomial inversion).

And we need to prove:

In this case, the recursion of becomes , and there's:

And thus we have:

Consider the first item of , if it were true for where , then we have:

Please notice the expression above is not compatible with the case of , in which . And we may not apply binomial inversion on , since it does not depend merely on , meantime it's impossible to cleanse the term to involve merely .

Now consider the -th term () of , we can see:

And now we are done with the proof.

Corollary

Proof. When it's easy to verify the first case is true. And when , we have:

Be wary of the range of : since when , but it's not true for , since . So we expand it directly, by we know , and thus , which does not fit in with the case of .

Corollary

Proof. It won't be hard to verify the right hand side is true when . And when , we have:

Which completes the proof.

The constants and are called the Bernoulli numbers.

By now, we are eventually able to prove the closed form of the Faulhaber's formula:

Theorem (Faulhaber's Formula)

Proof. First, for each , we can partiton the summands in such way:

By seeing we have:

And thus we have:

Where the swap of the summation is based on that the summands of are lattices situated inside triangle on plane, and can be swapped into .

And when we replace via offseting we will get:

Which is exactly what we are to prove.

February 10, 2024

number-theory analytic-number-theory