8 posts tagged with "maths"

Coprime numbers, also known as relatively prime numbers, are integers that do not share any prime factors, or equivalently having a greatest common divisor (GCD) of 1. Although the definition of coprime integers are originally for a pair of integers, it can be extended to any number of integers due to its associativity.

When I first learnt about coprime integers in a number theory course, there was a question that was not covered during the course, nor did it occur to me until recently: what is the probability of choosing a pair of coprime integers at random¹?

Hi Again, Pi​

There turns out to be a definitive answer to this question with several well-established proofs, and it is quite an elegant one:

Surprisingly, $\pi$ seems to appear out of nowhere in the answer, which makes this a topic that could make into 3Blue1Brown's "Why pi?" video series. However, this should look familiar to those who are familiar with the Basel problem, or the sum of reciprocals of perfect squares. In fact, they are very closely related.

A Straightforward Proof​

There are several proofs of this result, including one by Dirichlet that has existed since all the way back to 1849, and one that involves a more advanced concept called lattice points (see Apostol's Introduction to Analytic Number Theory, Theorem 3.9), but there is actually a simpler, yet more insightful argument, presented by Simon Tiger, a budding prodigy mathematician.

He does not go for the usual brute-force, 'bottom-up' method of running through massive numbers of integer pair samples while checking for the coprimality of each pair and keeping track of the odds in order to see if the probability converges to a certain constant. Instead, he takes a 'top-down' approach by looking at the probability of a pair of integers having a greatest common divisor (GCD) of $2$ or above.

What does this mean? Suppose that we call the first number $x_1$ and the second number $x_2$. Let's start with $2$ as the target factor. For $x_1$ and $x_2$ to have an GCD of $2$, they must at least both be divisible by $2$. Since modular arithmetic tells us that we can group integers evenly based on their respective remainders after being divided by a certain factor, the probability of $x_1$ (resp. $x_2$) being divisible by $2$ (i.e. having remainder zero) is $\frac{1}{2}$.

Note that $2$ must be the highest common factor of $x_1$ and $x_2$, so if we divide both of them by $2$, they cannot share any other factor (except for $1$ of course). Note that this is exactly the definition of coprimality! In other words, we have obtained a pair of coprime integers (namely $\frac{x_1}{2}$ and $\frac{x_2}{2}$) through this procedure. What is the probability of finding such a pair? That's exactly what we're looking for; let's call that value $p$.

The key of the procedure just now is that it gives us an important characterisation of a pair of integers having a certain number as their GCD: they must both be divisible by said number, and after dividing them by that number, the new resulting pair must be coprime.

What is the probability of finding an integer pair like this? The argument above tells us that it is the product of the probabilities, which represent the criteria that must be fulfilled simultaneously, that we obtained through the procedure, i.e. $\frac{1}{2} \cdot \frac{1}{2} \cdot p = \frac{p}{4}$.

At this stage, you may have figured out that this procedure can be repeated for every other integer factors. For $3$, we obtain $\frac{1}{3} \cdot \frac{1}{3} \cdot p = \frac{p}{9}$; for $4$, we obtain $\frac{p}{16}$, and so on. We can even deduce the general pattern: for a factor $k$, the probability of an integer pair having $k$ as their GCD is $\frac{p}{k^2}$. This general pattern even works for the case when $k = 1$, because an integer pair having $1$ as their GCD essentially means that they are coprime, so the corresponding probability is indeed $p$.

Now, we see how everything comes together which helps us to obtain the value of $p$ that we want. Note that any integer pair has the GCD of any number. This means that the probability of obtaining any integer pair among the sea of all integer pairs, which is clearly $1$, is equal to the sum of all probabilities of an integer pair having the GCD of any number, ranged over all integers! Rewriting this description into an algebraic equation, we obtain

Rearranging the variables a bit yields

In other words, the probability $p$ of a randomly chosen integer pair being coprime is the reciprocal of the sum of reciprocal of squares! That's where the Basel problem, i.e. the reason why $\pi$ shows up in the solution, plays a role!

Extension to $n$ integers​

Another cool part of this argument is that it can be easily extended to an arbitrary number of randomly chosen integers, say, $n$ of them.

By investigating $n$ possible integers, say, $x_1,x_2,\ldots,x_n$ instead of just two like before, calculating the probability of these integers having a certain number $k$ as their GCD now involves multiplying $\frac{1}{k}$ for $n$ times in total, followed by multiplying $p$ at the end as before.

In a similar vein, we then obtain that

Does the denominator ring a bell? It is in fact the definition of the Riemann zeta function!

Rather, for the special case of positive integers, it is more commonly known as the $p$-series.

It may be tempting to ask what the probability will become as the number of integers chosen 'tends to infinity'. It may even be more tempting to deduce from the general formula we just obtained to conclude that the answer should be $1$. However, this question is meaningless because there can be contradicting outcomes depending on what kind of infinite collections of integers we are considering. For instance, the probability is $0$ for all even numbers, but is $1$ for all positive integers; notice that both cases involve an infinite number of integers.

What if we consider a finite range of numbers and a finite number of choices instead? According to this paper, this probability seems to decrease as the number of choices increases, which is frankly an interesting result.

Other sources, further reading​

• Zeta functions, statistical mechanics and Haar measure, by Qiaochu Yuan
• On the Probability That Two Random Integers Are Coprime, by Jing Lei and Joseph B. Kadane
• The Probability that Two Random Integers are Coprime, by Julien Bureaux and Nathanael Enriquez
• Probability of Coprimality section in the Wikipedia article on coprime integers
• What is the probability that $n$ integers chosen at random are coprime? on Mathematics StackExchange
• Probability that two random numbers are coprime is $6/\pi^2$ on Mathematics StackExchange
• The Probability that $k$ Positive Integers are Pairwise Relatively Prime, by László Tóth

Suppose that we select arbitrarily a number of, say, $n$ integers, denoted by $a_1, \ldots, a_n$. If we obtain their lowest common multiple (LCM), and label it as $M := \mathrm{lcm}(a_1,\ldots,a_n)$, then take for each of the initial $n$ integers the corresponding number $k_i$ ($i = 1, \ldots, n$) such that multiplying by that number gives us the LCM, i.e. $k_i a_i = M$ for each $i$, an intriguing pattern starts to emerge: all the numbers $k_i$ are coprime, i.e. $\gcd(k_1,\ldots,k_n)=1$.

The following is an example code snippet that illustrates this phenomenon. This snippet generates a list of $n$ random integers between $0$ and $K$, obtains their LCM, extract the factor $k_i$ for each of $a_i$, where $i = 1, \ldots, n$, from the LCM and calculate the greatest common divisor (GCD) of the $k_i$'s.

Repeatedly running this code generates a different group of $n$ integers, but notice that the GCD obtained in the end is always 1.

The definitions of lcm_euclidean_general and gcd_euclidean_general in the snippet can be found in this note.

from random import randint
n, K = 4, 2000 # feel free to change the parameters here
test = [randint(0, K) for i in range(n)]
lcm = lcm_euclidean_general(*test)
smallest_k = tuple(map(lambda x: lcm // x, test))
print(gcd_euclidean_general(*smallest_k)) # 1

Why though?​

To those who are familiar with the topic of coprime integers, this phenomenon should not come as a surprise. Nevertheless, a brief explanation of this fact will be presented here.

If we assume that the numbers $k_i$, where $i = 1,\ldots,n$ are not coprime, or equivalently $\gcd(k_1,\ldots,k_n) > 1$, and we call the GCD to be $G$, then we can write $k_i=Gb_i$ where $b_i$ is an integer and $G>1$. It follows that $M=Gb_ia_i$ for each $i$.

However, this also means that we can divide each of them throughout by $G$ and obtain $\frac{M}{G}=b_ia_i$ for each $i$. Note that $\frac{M}{G} < M$ because $M > 0$ and $G > 1$, and is a constant integer because $G$ is also a common factor of $M$. Note as well that since each $b_i$ is an integer, this means that $\frac{M}{G}$ is a common multiple of the $a_i$'s that is smaller than the lowest common multiple $M$? This does not make sense, right? This is where we reach a (logical) contradiction for which the only way to resolve this is to conclude that the GCD $G$ cannot be greater than 1 all along, thus the $k_i$'s from the start must be coprime!

We have thus demonstrated the technique of proof by contradiction to confirm the validity of this fact.

Introduction​

Invertible matrices are fundamental in linear algebra. They represent reversible linear transformations which are pleasant to work with, because:-

• Invertible matrices give us a unique solution to a system of linear equations.
• Invertible matrices represent linear transformations that are of full rank, i.e. those that do not 'squish' the space in a way that reduces its dimension, and injective (one-to-one).
• The columns of an ($n \times n$ real) invertible matrix, are linearly independent to each other, and thus spans the full $\mathbb{R}^n$ space.
• Invertible matrices have nonzero determinants.

– some of the logically equivalent statements in the Invertible Matrix Theorem (IMT)

As nice mathematical structures usually do not happen frequently, this makes one wonder: in the universe of square matrices of an arbitrarily fixed¹ size, say, $n \times n$, what is the probability of finding an invertible matrix?

Surprisingly (at least to me), it turns out to be a very technical problem that has very different answers depending on various factors with respect to the entries of the matrix, including their probability distribution, allowable types of numbers (discrete or continuous, etc.) and even the underlying measure. In other words, there isn't a blanket answer and certain conditions need to be specified in order to reach an answer.

It is way more often than you may expect​

Let's first consider the scenario that is considered 'default' or 'standard' by most people: the probability of finding an invertible matrix among the space of an $n \times n$ matrix of real numbers².

In this scenario, the answer turns out to be a surprising one (again, at least to me): it is almost surely to find an invertible matrix, i.e. the probability is 1 but this does not mean all real matrices are invertible (there are indeed singular, or non-invertible, matrices). This is a phenomenon that can happen when we are considering infinite sample spaces; even though there are an infinite number of singular matrices, invertible matrices still outnumber them so much that they are probabilistically negligible (literally zero probability). To quote the Wikipedia article about invertible matrices,

Singular matrices are rare in the sense that if a square matrix's entries are randomly selected from any bounded region on the number line or complex plane, the probability that the matrix is singular is 0, that is, it will "almost never" be singular.

There are two main approaches to prove this result, both of which make use of linear algebra and measure theory: one involves determinants, whereas the other involves subspaces and its dimension.

Determinant Argument​

The argument involving determinants, as found in this post and this post from Mathematics Stack Exchange, applies the fact that invertible matrices have nonzero determinant, or in other words, singular matrices have zero determinant. The determinant of a real $n \times n$ matrix (with $n^2$ entries) is also a polynomial function, as shown below ($\sigma$ represents a permutation function and $\operatorname{sgn}(\sigma)$ is either 1 or -1):

Therefore, since $\det(M) = 0$ if $M$ is singular, the collection of singular matrices is equivalent to the zero set of the determinant as a polynomial function from $\mathbb{R}^{n^2}$ to $\mathbb{R}$.

There is a mathematical result which states that the zero set of a polynomial function has measure zero (a proof of this can be found here or here). It's fine if you don't understand what 'measure zero' means: what matters here is that an event represented by a (sub)set of measure zero has zero probability.

Thus, there is zero probability that a random real square matrix is singular, so the probability to obtain an invertible matrix is 1 (in the almost surely sense).

Subspace Dimension Argument​

Another argument, as found in this Reddit comment, this blog post and this Mathematics Stack Exchange post, involves the fact that the collection of singular matrices form a subspace that is one dimension less than the space of all $n \times n$ matrices.

Why is that so? A less rigorous reasoning of this goes as follows: note that for an $n \times n$ matrix to be singular, it must have at least one column that is a linear combination of all the other $n-1$ columns.

Now, for a single nonzero vector $\vec{v}$ in $\mathbb{R}^n$, the collection of $\mathbb{R}^n$ vectors that are linearly dependent to that particular vector are its scalar multiples, i.e. $\{k\vec{v} : k \in \mathbb{R}\}$, and this is a one-dimensional subspace of $\mathbb{R}^n$. For two vectors $\vec{v_1}$ and $\vec{v_2}$, the collection of vectors that are linearly dependent to them is $\{ a\vec{v_1}+b\vec{v_2} : a,b \in \mathbb{R} \}$, which forms a 2-dimensional subspace. Following this pattern, if we have $n-1$ vectors in $\mathbb{R}^n$, the collection of vectors that are linearly dependent to them is exactly their linear span, which is an $n-1$-dimensional subspace.

This implies that the column space of a singular matrix is an at most $n-1$-dimensional subspace of $\mathbb{R}^n$, so the space of singular matrices form an $n - 1$-dimensional hypercube, compared to an $n$-dimensional hypercube formed by the space of all square matrices. Thus, the probability of finding a singular matrix is:

An alternative but very similar argument, as described here, states that due to the fact that singular matrices have zero determinant which gives us one constraint equation, the set of singular $n \times n$ matrices form an $n^2-1$-dimensional vector space, which similarly has measure zero, with respect to the $n^2$-dimensional space of all $n \times n$ matrices over the real numbers.

Either way, it follows that the probability of finding an invertible real matrix is, surprisingly, 1. In other words, for whatever real matrices that you come up with randomly, it is extremely likely to have an inverse!

Matrices with discrete entries​

Things start to get interesting when we restrict the entries of a square matrix to be discrete values, in particular binary (i.e. 0 or 1), finite field and integer values.

Binary matrices​

For binary matrices, the probability trend depends on the underlying ring (or in laymen's terms: number system) of the entries of the matrix. For binary matrices over the real numbers, it is a long-time research problem stemming from the 1960s that involves contributions by multiple mathematicians, and is settled by Tikhomirov in his 2018 paper: the probability that an $n \times n$ binary matrix $M_n$ is invertible is given by

where $o_n(1)$ denotes a quantity that tends to 0 as $n$ tends to infinity.

We can see that as $n$ gets larger, the probability gets closer to 1.

As for binary matrices over the finite field $\mathbb{F}_2$, it corresponds to the case when $q = 2$ in the next section of this article, where matrices over finite fields are discussed in more detail. One thing to note is that the change in probability as $n$ gets larger is different: it decreases and tends to a limiting number strictly between 0 and 1.

Matrices over finite fields​

There is a pretty neat argument, which can be found in several sources including Wikipedia, that gives us the probability of finding an invertible matrix in the space of square matrices over a finite field $\mathbb{F}_q$³.

In the lingo of abstract algebra, the number of invertible $n \times n$ matrices over the finite field $\mathbb{F}_q$ is the order of the general linear group of degree $n$ over $\mathbb{F}_q$, $\mathrm{GL}_n(\mathbb{F}_q)$. There is a pretty neat argument that gives us the probability of finding an invertible matrix in the space of square matrices over a finite field $\mathbb{F}_q$, which is described in several sources.

For a square matrices of size $n$ whose entries are taken from a finite field $\mathbb{F}_q$ of order $q$ (i.e. contains $q$ elements), which we denote here by $A$, there are $q$ possibilities in each entry. Since there are $n^2$ available slots, we have a total of $q^{n^2}$ such matrices. If we only consider one of its columns, then as there are $n$ entries in a column, there are $q^n$ possibilities.

Note that $A$ is invertible if and only if for $j = 1,\ldots,n$, the $j$-th column cannot be expressed as a linear combination of the preceding $j-1$ columns. For the first column $v_1$, there are $q^n-1$ possibilities, as only the zero vector is excluded. For the second column $v_2$, since we need to exclude the $q$ multiples of the first column, there are $q^n-q$ possibilities. For the third column $v_3$, we need to exclude the linear combinations of the first and second column, i.e. vectors in the form of $av_1+bv_2$ where $a,b=1,\ldots,q$, which contains $q \cdot q = q^2$ vectors, so in the end we have $q^n-q^2$ choices. Continuing this pattern, the last column will have $q^n-q^{n-1}$ choices. Thus, the number of invertible matrices over $\mathbb{F}_q$, or the order of $\mathrm{GL}_n(\mathbb{F}_q)$ is given by

It follows that the invertibility probability is

We then see that as the order $q$ increases, the probability tends to 1, whereas as the matrix size $n$ increases, the probability decreases and tends to a limiting number strictly between 0 and 1; for the case of binary matrices over $\mathbb{Z}_2$, the limit is approximately 0.288788.

Random integer matrices​

For the case of $n \times n$ matrices with entries over the integers, with an appropriate probability distribution and measure chosen², since there are infinitely many such random integer matrices, the result is analogous to the real matrices case as discussed above, i.e. the probability of finding an invertible matrix is 1, in the sense of being almost surely.

Sidenote: diagonalisable matrices​

There is another matrix-related property that is nice to work with and highly sought after for its usefulness in improving computational efficiency: being diagonalisable. Sadly, not all matrices are diagonalisable, even over complex numbers, but what is the probability of finding one, or more accurately speaking: the "density" of diagonalisable matrices?

There is a paper about this topic that quotes or features some important results, but they are mainly about integer matrices instead of real matrices. They are only presented briefly as a list here, but one can consult the paper for more details.

• The probability of an $n \times n$ matrix, where $n$ is arbitrary fixed, with real entries being diagonalisable over the complex numbers (i.e. the eigenvalues are allowed to be non-real), is 1.
• If the entries are only allowed to be integers, the probability of such $n \times n$ matrix being diagonalisable over the complex numbers is also 1.
• It turns out that for $n \times n$ matrices over the real or rational numbers, the question becomes remarkably difficult; even for $2 \times 2$ matrices the result is not straightforward: techinques in multivariable calculus and mathematical analysis are employed in the said paper to prove the results. Nonetheless, here are some key results concerning $2 \times 2$ matrices provided by the paper:
  • The probability of finding a $2 \times 2$ matrix with only integer entries that is diagonalisable over the real numbers (i.e. the eigenvalues can only be real numbers) among all $2 \times 2$ matrices with only integer entries is $\dfrac{49}{72}$. Not a particularly elegant number, but this seems to show that diagonalisable matrices might be denser than we expect.
  • The probability of obtaining a $2 \times 2$ matrix with only integer entries that is diagonalisable over the rational numbers (i.e. the eigenvalues can only be rational) among all $2 \times 2$ matrices with only integer entries is $0$, implying that diagonalisable integer matrices with only rational eigenvalues are so sparse that it is virtually negligible.

References, further reading​

• A Reddit post thread that discusses this topic

• Hetzel, A. J., Liew, J. S., & Morrison, K. E. (2007). The Probability that a Matrix of Integers Is Diagonalizable. The American Mathematical Monthly, 114(6), 491–499. https://doi.org/10.1080/00029890.2007.11920438

• Caron, R. & Traynor, T. (2005). The Zero Set of a Polynomial.

• Wicklin, R. (2011). What is the chance that a random matrix is singular?

• Sources that discuss binary matrices and matrices over a finite field:

  • Dai, A., Kim, C. & Kim, J. (2008). Invertibility Probability of Binary Matrices.
  • Morrison, K. E. (2006). Integer Sequences and Matrices Over Finite Fields. Journal of Integer Sequences.
  • Comment by Reddit user u/HotPocketRemix
  • Praveen Sriram (https://math.stackexchange.com/users/211932/praveen-sriram), Probability of building an Invertible Matrix, Mathematics Stack Exchange
  • Tikhomirov, K. (2020). Singularity of random Bernoulli matrices. Annals of Mathematics, 191(2), 593-634.

• Tao, T. & Vu, V. (2007). On the singularity probability of random Bernoulli matrices. Journal of the American Mathematical Society, 20(3), 603-628.

• Bourgain, V., Vu, V. H. & Wood, P. M. (2009). On the singularity probability of discrete random matrices. Journal of Functional Analysis, 258(2), 559-603.

• Some Mathematics Stack Exchange posts referenced:

  • kosmos (https://math.stackexchange.com/users/65781/kosmos), If I generate a random matrix what is the probability of it to be singular?
  • Gabriel Romon (https://math.stackexchange.com/users/66096/gabriel-romon), Are most matrices invertible?
  • Fred Daniel Kline (https://math.stackexchange.com/users/28555/fred-daniel-kline), Why is a singular matrix rare?

The Context​

In a mathematical proof to show the existence of the singular-value decomposition (SVD)¹ in real matrices which I have recently come across, there is a (small) statement that is applied in it without proof, which goes like this:-

Let $A \in \mathbb{R^{m \times n}}$ be a real matrix and $x \in \mathbb{R}^n$ a real vector, then the map $f : \mathbb{R}^n \to \mathbb{R}$, defined by $f(x)=\Vert Ax \Vert_2$, where $\Vert\cdot\Vert_2$ represents the 2-norm (Euclidean norm), is continuous.

This statement is used to show the existence of the largest singular value of a matrix $A \in \mathbb{R}^{m \times n}$, usually denoted as $\sigma_1$, when defining $\sigma_1 := \sup_{x \in S} \Vert Ax \Vert_2$, where $S$ represents the unit hypersphere centred at the origin.

This article describes a proof of the statement above, which makes use of the induced matrix norm (also known as the operator norm).

The Good Old Epsilon-Delta​

We employ the $\varepsilon-\delta$ definition of a continuous function for this proof, i.e.

Let $(X,d_X)$ and $(Y,d_Y)$ be metric spaces. A function $f : X \to Y$ is continuous in a set $A \subseteq X$ if for any point $a \in A$ and any $\varepsilon > 0$, there exists some $\delta>0$, which depends on $\varepsilon$ and/or $a$, such that whenever $d_X(x,a)<\delta$ where $x \in X$, we have $d_Y(f(x),f(a))<\varepsilon$.

This definition provides rigour to the notion that a continuous function leaves no 'gaps' to its graph, i.e. the distance between two points on the function graph is arbitrarily small as we 'zoom in' indefinitely so that the distance between two points on the domain becomes arbitrarily small.

In our case here, $X = \mathbb{R}^n$, $Y=\mathbb{R}$ and $d_X = d_Y = \Vert\cdot\Vert_2$.

The induced matrix 2-norm, whose definition is stated as follows, also comes into play here.

With these in place, let's start the proof:-

Let $x \in \mathbb{R}^n$, $A \in \mathbb{R^{m \times n}}$ and $\varepsilon > 0$ be arbitrary, and set $\delta=\dfrac{\varepsilon}{\Vert A \Vert_2}$.

If $A = 0$，i.e. $A$ is the zero matrix, then $f$ is essentially the function that maps everything to zero, which is clearly continuous².

Next, we consider nonzero $A$. We first note that from the definition of the induced matrix 2-norm, we can see that for any $x,y \in \mathbb{R}^n$ where $x \neq y$, we have that

Therefore, it follows that for $y \in \mathbb{R}^n$ such that $\Vert x-y \Vert_2<\delta$,²

Note that the first $\leqslant$ is due to the triangle inequality, and the second $\leqslant$ comes from (*).

This thus concludes the proof that the map $x \mapsto \Vert Ax \Vert_2$ is continuous.

The Nicer Things​

In fact, the statement above is a special case and combination of a number of nice results, which are stated as follows:-

• A linear map from a finite-dimensional space is always continuous. In fact, it is even nicer: if a linear map is continuous, it must be Lipschitz continuous³.

• The norm function in any normed space is continuous.

• The composition of continuous functions are continuous.

The proof of each of these statements is linked as above.

This article was submitted to the Summer of Math Exposition (SoME) 2024 and ranked 17 among all 44 valid non-video entries in the contest.

Level 0: Geometric Series​

A series that looks like the following:

is a convergent geometric series, which can be evaluated using the following infinite sum formula:

where $a$ is the first term of the series and $r$ is the common ratio. In the case of the series above, $a = \frac{1}{c}$ and $r = \frac{1}{c}$. Plugging them in, we obtain the sum, $S_0$, for the above series:

This series is useful in various applications, from distance calculation in physics, compound interests in finance, population growth in biology to even fascinating topics like fractal geometry. Indeed, this series is good and fun, but like most mathematicians may ask, "Can we generalise it even further, and how?"

This article demonstrates one way this series can be generalised, which is by allowing variables in the numerator of the summed over terms.

Level 1: Arithmetico-geometric Series​

Now, what if instead of the numerator being a constant number, it is the index of summation $k$?

It somewhat resembles the previous series but is no longer a geometric one. In fact, it is now an arithmetico-geometric series, with each term in the sum being the product of its respective term of an arithmetic sequence and that of a geometric sequence.

It seems like the infinite sum formula above is not really useful currently. How should we tackle this problem then?

Scaling and Shifting​

Since the variable $k$ in the numerator is of degree $1$, let's call the desired sum $S_1$, and list the first few terms of the series.

Next, let's multiply all of the terms by $\dfrac{1}{c}$. We then obtain $\dfrac{1}{c} S$, with the terms becoming the following.

Now, observe that with the exception of the $k=1$ term, there is a difference of $\dfrac{1}{c^k}$ between each term in the former and latter series. With this in mind, let's see what happens if we subtract the former sum by the latter.

We recover the geometric series at the beginning! The key here is that we have managed to reduce the problem down to what we've seen before, and we can now apply the geometric infinite sum formula!

How can we express this in terms of $S$ then? Recalling what we have previously done, we can in fact write it as $S-\frac{1}{c} S$. Doing some simplification and applying the infinite sum formula gives us the following equation:

Solving this equation finally gives us the desired answer, also known as the Gabriel's staircase:

Level 2: Quadratic-geometric Series​

At this point, one may ask, "Why stop here? Why not replace the numerator from $k$ to $k^2$ and find the general formula of the resulting new series? It will still be convergent (proof below) anyways."

Let's try to apply the same technique we used to obtain the general formula for the case when $p=1$. Here, we call the desired sum $S_2$.

Multiplying throughout by $\dfrac{1}{c}$ yields

Finally, subtracting the former by the latter, we obtain

Once again, we've managed to utilise the fact that the pairwise differences of consecutive perfect squares produce the sequence of odd numbers to reduce this series down to simpler results.

Applying the previous results obtained so far, we finally have

Level 3: Cubic-geometric Series​

Now, what can we get if the numerator is a cubic term?

We will call this sum $S_3$ and let's try the same method again.

Notice that in (#), the numerator terms are in the form of $k^3-(k-1)^3$, with $k = 1,2,3,\ldots$ This simplifies to $3k^2-3k+1$, which means that (#) can be rewritten as:

Finally, we then arrive at:

You may start to notice a pattern here, and this will be discussed in the next section.

Level p: Polynomial-geometric Series​

All of these naturally lead to the question: what happens if we generalise the power of $k$ on the numerator to be any positive integer, i.e. what is the infinite sum of the following series?

We know from previous sections that such series are in fact convergent, so we could try to find the respective general formulae for them.

Let's call this sum $S_p$. Inductively, one can see that if we obtain $\dfrac{c-1}{c}S_p$, its numerator terms are then in the form of $k^p-(k-1)^p$, where $k=1,2,3,\ldots$

Not only is this where the binomial theorem comes into play, you can observe that the highest-power term, $k^p$ gets cancelled out while the terms of lower powers remain intact. This means that this method enables us to obtain a recurrence relation of $S_p$ in terms of the lower-power sums, i.e. $S_{p-1}$, $S_{p-2}$ and so on, and this can help us to evaluate its general formula.

Since $k^p-(k-1)^p=k^p-\sum_{i=0}^{p}\binom{p}{i}k^{p-i}(-1)^i=\sum_{i=1}^{p}\binom{p}{i}k^{p-i}(-1)^{i+1}$, we then arrive at this recurrence relation:

In fact, this derivation is very similar to that in this short paper by Alan Gorfin.

A Segue into Combinatorics​

Interestingly, the closed form of this general formula has connections with combinatorics. According to a short paper by Tom Edgar, $S_p$ has the following formula, due to Carlitz:

where $A_p(c)=\sum_{k=0}^{p-1}A(p,k)c^k$ denotes the $p$-th order Eulerian polynomial (following the Wikipedia notation).

The coefficients of the Eulerian polynomial, denoted $A(p,k)$ as above, are called Eulerian numbers. We can construct a triangle similar to the Pascal's triangle using Eulerian numbers, with $p$ starting from $1$ and incrementing one step at a time when traversing down the column, whereas $k$ ranges from $0$ to $p-1$ as we go from the left to the right of each row. This triangle is then usually called the Euler's triangle.

Eulerian numbers have an application in combinatorics. To quote Wikipedia,

the Eulerian number is the number of permutations of the numbers $1$ to $n$ in which exactly $k$ elements are greater than the previous element (permutations with $k$ "ascents").

For example, $A(3,1) = 4$, gives us the number of permutations of $1,2,3$ with exactly one element being greater than the previous element, i.e. $132, 213, 231, 312$.

This means that this extension of the geometric series provides us a connection to a combinatorial pattern! Isn't that cool?

Level s: Complex-geometric Series​

As a sidenote, what if we generalise even further, so that the numerator variable could take on powers of any complex number?

This brings us beyond the realm (heh) of real numbers and opens ourselves up to the world of Dirichlet series and polylogarithm function, which are common research topics in analytic number theory.

A Dirichlet series is defined as a series of the form

where $s$ is a complex number and $a_k$ is a complex sequence.

The polylogarithm function is then a particular collection of Dirichlet series for which $a_k$ is a power series (the free variable in the terms of the series has successively increasing integer powers) in $z$, where $|z|<1$ and $z$ is allowed to be complex (hence the absolute value here is in fact the modulus). Here, $s$ is called the order or weight of the function.

One can then notice that $S_p$ discussed previously is in fact $\operatorname{Li}_{-p}\left(\frac{1}{c}\right)$, with $|c| > 1$.

Unfortunately, even allowing analytic continuation, obtaining a value or an explicit expression for $\operatorname{Li}_{-s}\left(\frac{1}{c}\right)$ for even just positive rational values of $s$, let alone a non-real number, is difficult. For example, even a closed-form expression for $\operatorname{Li}_{-\frac{3}{2}}\left(\frac{1}{c}\right)=\sum_{k=1}^{\infty}\frac{k\sqrt{k}}{c^k}$ is currently unknown.

That said, polylogarithm function is still a topic with various directions of research, including its integral representations, dilogarithms (i.e. when $s = 2$) and polylogarithm ladders.

To read more about the subject, as well as other topics covered here, feel free to search online using the keywords or navigate to the references/further reading section below.

References, further reading​

• Arithmetic-Geometric Progression - Brilliant Wiki
• Arithmetico-geometric series - Art of Problem Solving Online
• Edgar, T. (2018). Staircase Series. Mathematics Magazine, 91(2), 92–95.
• Gorfin, A. (1989). Evaluating the Sum of the Series $\sum_{k=1}^{\infty}{\frac{k^j}{M^k}}$. The College Mathematics Journal, 20(4), 329–331.
• Polylogarithms - Digital Library of Mathematical Functions
• Lewin, L. (1981). Polylogarithms and Associated Functions.
• Questions on Math Stack Exchange with Polylogarithm Tag

The Statement​

There is a prime number related result which is adapted from a tutorial question in a course about number theory, which is stated as follows.

For any prime $p$, $1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}$ is divisible by $p$.

The Proof​

A proof of this result is fairly straightforward, when observed correctly.

Indeed, when $p=2$, $1+\frac{1}{p-1}=1+1=2$ is divisible by $2$.

Now, we only consider the odd primes, then we should have an even number of terms for the sum above. Now here's the key part: note that the terms of the sum above can be rearranged such that the first and last term are next to each other, as well as the second and second last term, and so on. When we sum each of the pairs together, we then obtain

We can then see that we are able to factorise $p$ out of the sum, so it is indeed divisible by $p$.

In fact, using this result as well as the fact that there are an infinite number of prime numbers, which makes the set of prime numbers to be unbounded above due to the definition of prime numbers itself that necessitates them to be integers, it follows that the series $\sum_{n=1}^{\infty}\frac{1}{n}$ diverges to positive infinity. This provides an alternative proof to the ingenious method that produces an infinite sum of one halves.

How about the other way around?​

This gives rise to another interesting question: can we prove that there are infinitely many primes, assuming the divergence of the harmonic series?

In fact, this is true. If we break down the denominator of each term of the harmonic series into its respective prime factorisation, then apply the distributive law and the formula for the geometric infinite sum, we then obtain the following result due to Euler, where $\mathbb{P}$ denotes the set of prime numbers:

What Euler did next was taking logarithms on both sides and applying the Taylor series of logarithms gives the following:

Since this is equal to the divergent harmonic series and a finite sum containing finite terms must converge, it follows that there must be infinitely many primes. This result also implies that the sum of reciprocals of prime numbers diverges, which was more rigorously verfied by Franz Mertens.

Higher-order function (HOF) is a type of nested function that offers a higher level of abstraction than ordinary functions, where instead of taking primitives or variables as arguments (parameters) and outputting objects, functions are taken in and output by HOFs.

The subtleties between a function composition and HOF can be shown through the syntax of Python, which can result in different behaviours depending on how we close the parentheses.

A classic example is demonstrated as follows.

def thrice(f):
    return lambda x: f(f(f(x)))

add1 = lambda x: x + 1

x = thrice(thrice(add1))(0) # 9
y = thrice(thrice)(add1)(0) # 27

In the example above, x will output 9 because the defining line of code is interpreted ‘right-to-left’ (like function composition), first composing the add1 function thrice to produce a function equivalent to lambda x: x + 3, then composing the first output thrice to produce a function equivalent to lambda x: x + 9, thus 0 + 9 = 9.

As for y, it will output 27 because it is defined ‘left-to-right’, first composing the thrice function itself three times, resulting in an HOF that effectively composes an input function $3^3=27$ times, which then takes in the function add1 to produce a function equivalent to lambda x: x + 27, and finally we get 0 + 27 = 27.

Higher-order functions are closely related to mathematics, in the sense that they enable the implementation of operators in mathematics, as well as a family of functions, using code.

For example¹, in set theory, we can define a family of functions $F$, which itself is also considered a function from $\mathbb{N}^{\mathbb{N}} \to \mathbb{N}^{\mathbb{N}}$. This operator $F$ takes in a function $f : \mathbb{N} \to \mathbb{N}$ and outputs another function $F(f) : \mathbb{N} \to \mathbb{N}$ that takes in whatever $f$ takes in and outputs whatever $f$ outputs plus one.

Phrased in a set-theoretic language as ‘pure’ as possible, $F$ is defined as

An HOF implementation of $F$ in Python can then look like the following:

# The following type hints are to indicate that the functions are in N^N, and are unnecessary for practical purposes.
from typing import Annotated, Callable
from annotated_types import Ge # requires additional pip install: https://pypi.org/project/annotated-types/

def F(f: Callable[Annotated[int, Ge(0)], Annotated[int, Ge(0)]]) -> Callable[Annotated[int, Ge(0)], Annotated[int, Ge(0)]]:
    def output(n: Annotated[int, Ge(0)]) -> Annotated[int, Ge(0)]:
        return f(n) + 1
    return output

f = lambda x: x + 1
F(f)(0) # 2

This is supposed to be an article submitted as an entry of the third Summer of Math Exposition (SoME3) contest.

It was originally published on my main website but I have changed my place of posting blogs to this site. For reverse compatibility (so that the old link is still accessible), I am linking the article instead of reposting it, which can be found here.