5 posts tagged with "maths"

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.

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.