Month: August 2019

Riemann’s Rearrangement Theorem

Themistoklis Haris

This post will be devoted to a very special and surprising result given by the great Bernhard Riemann on the topic of the convergence of infinite series.

The theorem states:

Let \{a_n\}_{n=1}^{\infty} be a sequence of real numbers so that \sum\limits_{n=1}^{\infty} a_n is conditionally convergent (it converges but not absolutely). Then if we let M\in\mathbb{R}\cup\{\infty,-\infty\}, there exists a permutation \sigma of \{a_n\} such that \sum\limits_{n=1}^{\infty} a_{\sigma(n)} = M

Let’s let that result sink in first through a classic example. Consider the series 1 - \frac{1}{2} + \frac{1}{3} - \cdots = \sum\limits_{n=1}^{\infty}\frac{(-1)^{n+1}}{n}. We know this series converges to ln(2), through Taylor’s series but the series \sum\limits_{n=1}^{\infty}\frac{1}{n} is the harmonic series and diverges. So our series is conditionally convergent. But observe that we can rearrange the terms of the infinite sum so that the series converges to the half of itself:

\left(1-\frac{1}{2}-\frac{1}{4}\right) + \left(\frac{1}{3}-\frac{1}{6} - \frac{1}{8}\right) + \left(\frac{1}{5} - \frac{1}{10} - \frac{1}{12}\right) + \cdots = \sum\limits_{n=1}^{\infty}\left(\frac{1}{2n-1}-\frac{1}{4n-2} - \frac{1}{4n}\right) = \sum\limits_{n=1}^{\infty}\frac{1}{4k(2k-1)} = \frac{1}{2}ln(2)

 

This is very weird. The same numbers added up in different order up to infinity, lead to a different sum. So addition works in strange ways when we take limits to infinity. We already sort of knew that but this theorem showcases it to an extent I couldn’t imagine before. And not only can we get half our sum by rearranging the terms, but we can get all possible numbers, by rearranging the terms in some way. We can even get \pm \infty.

We should prove this important theorem. In fact we shall prove a stronger statement: that if -\infty \leq a \leq b \leq \infty, there exists a rearrangement \sigma of \{a\}_{n=1}^{\infty} such that

\liminf_{n\rightarrow\infty}s_n'= a and \limsup_{n\rightarrow \infty}s_n' = b,

where s_n' is the sequence of partial sums of the rearranged sequence.

We get our result immediately if a=b. In case there is confusion about the \limsup and \liminf notation, recall that these signify the limit superior and limit inferior of a sequence, which are limiting bounds on a sequence (more info here).

First, define the following sequences: p_n = \frac{|a_n| + a_n}{2} and q_n = \frac{|a_n|-a_n}{2}. So p consists of all the positive terms in a and of 0s in the place of the negative terms and q is the opposite.

FACT: p and q diverge.

This isn’t very hard to see. If they both converged then \sum|a_n| would have to converge and if one converged and one diverged then \sum a_n would converge (check this!)

Now consider the sequences P_n, Q_n of positive terms and of the absolute values of the negative terms in order in \sum a_n. P and Q differ from p and q only in the placement of 0s in between of the latters’ terms, so both P and Q diverge.

IDEA / GOAL: Construct sequences \{m_n\}, \{k_n\} such that the series

P_1 + \cdots P_{m_1} - Q_1 -\cdots - Q_{k_1} + \\[1mm] P_{m_1+1} + \cdots + P_{m_2} - Q_{k_1+1} - \cdots - Q_{k_2} + \cdots

,which is obviously a rearrangement of \sum a_n satisfy our theorem’s target.

How to do this? First choose sequences \alpha_n \rightarrow a, \beta_n \rightarrow b so that \beta_1 > 0 and \alpha_n < \beta_n. Then let m_n and k_n be the smallest integers such that

x_n = \sum\limits_{i=0}^{m_n}P_i - \sum\limits_{i=0}^{k_{n-1}} Q_i > \beta_n and y_n = \sum\limits_{i=0}^{m_n}P_i - \sum\limits_{i=0}^{k_n} Q_i < \alpha_n (let k_0 = -1)

We can always find such integers because P, Q diverge.

Since m_n and k_n are the smallest integers with this property, we have that |x_n - \beta_n| \leq P_{m_n} and |y_n - \alpha_n| \leq Q_{k_n} so that x_n \rightarrow a and y_n \rightarrow b.

Finally, it is clear that no subsequential limit of our rearranged series can converge to something larger than b or smaller than a and so our proof is complete.

Proof adapted from the book “Principles of Mathematical Analysis”, by Walter Rudin.

2D Max Sum of Subarray – Kadane’s algorithm

Themistoklis Haris

Consider a matrix M m\times n with integer values. We seek to find a rectangular subarray of M whose sum of elements is maximized.

\begin{matrix} 5 & -4 & -3 & 4 \\ -3 & -4 & 4 & 5 \\ 5 & 1 & 5 & -4 \end{matrix}

First, let’s examine the 1D version of the problem. The brute force approach would be O(n^2) as we would have to examine all subarrays of M and build up the sums incrementally. A cleverer way is by using Dynamic Programming in Kadane’s algorithm.

Let P(i) denote the maximum sum subarray of M ending at index i. We can easily see how the following recursive formula holds:

P(i) = \left\{ \begin{array}{ll} M[i], &\text{if } i=0 \\ \max\{M[i], M[i]+P(i-1)\}, & \text{otherwise} \end{array} \right.

 

After finding P(i) for all i, we can loop through those values to get the maximum one. The time complexity is O(n).

For the 2D version of the problem, we employ a small trick. We examine the space between all possible pairs of columns. Let c_1 and c_2 \geq c_1 be two columns of M. Then we want to constructively construct an array T such that T[i] holds the sum of all values of row i of M between the two columns. On T we run Kadane’s algorithm for 1D to get our solution. This algorithm runs in O(n^3) over the O(n^4) brute force approach.

Animation, 3D Rigging, Mixed Reality and more Unity

Themistoklis Haris

In recent weeks, I have been working a lot to augment my MR project for my research through modifying the animation tracks present in it. I will record many of my conclusions, progress and understanding in this page.

Firstly, I was briefly exposed to the vast field of Computer Animation. I was in possession of a Humanoid Avatar, which was rigged and animated according to some motion capture data. I first had to understand some of the mechanics of Unity’s animation system, which was recently changed relative to the past. In Unity, to animate a GameObject, one must first attach an Animator component to it. The Animator component contains an Animator Controller. This Controller is a whole different beast altogether and can be wired up using the special Animator window. In short, it contains multiple Layers, which one can animate and each layer contains a State Machine which ties into how something is animated. Each state contains an Animation Clip, which can either be composed in Unity’s animation window or be some external thing.

Animation Clips can be produced through the animation window through pose rigging. One simply rigs a couple of poses in succession to one another and then Unity interpolates through them to produce the clip. Of course, there are a lot to see and do at this stage. One can control the interpolation curves to make the animation smoother or more cartoonish. And of course one can control the speed of the animation, make it loop etc… All those elements of animation in Unity are accessible through code in C#, where I found that pausing / continuing an animation is possible simply by tweeking its speed. This is also required in other cases too, like when most animation clips are too fast.

As a final part to experiencing Unity’s animation environment, I also played around with the Timeline, a tool that allows the user to play animations and activate / deactivate objects in succession. This allowed me to build quite a cool little application in MR and would have made things extremely easy if I was aware of its existence early on, because in the beginning I would devote hours to synchronizing different Animators manually, while this tool does it better and automatically.

In terms of MR, I practiced a lot linking the controllers to code and giving the user control over their Mixed Reality experience. I implemented an application in which the user can rotate, shrink and transport humanoid avatars with their controllers while they are performing some animation clip. The user could also pause / continue that animation.

For the humanoid avatars, I spent quite a bit of time thinking and experimenting with different models. I first chose a very rudimentary model from the Unity Asset Store and then upgraded it to the “Man In A Suit” model. Lastly, I started using UMA 2 (Unity Multipurpose Avatar), which is very customizable and well-rigged but was kind of buggy and gave me trouble more than once. I realized that using the Bone Builder tool is the way to go to achieve integration of UMA in the Timeline. Important fact: UMA AVATARS NEED A FLOOR underneath them or they will fall to infinity because they are by default rigidBody objects (I just realized this).

And speaking of floors, I also spent a lot of time thinking about how to make this floor invisible, because I certainly didn’t want it to show up in my MR application. The solution I used in the end was something called a stencil shader. A stencil shader is a type of shader that is used to hide parts of a mesh for being shown in the screen. I will compile my efforts to understand more about shaders in another post.

Lastly, I also had to synthesize one my own animation clips of a rigged hands model. Producing this kind of animation is something that may be doable through Unity but I used Blender to do it. Again, I had to rig each pose individually and it was quite time consuming, but I got to see how Blender works and a bit of its mechanics.