Today I Learned: the Strassen Algorithm

There's a reason why most of us are taught addition before multiplication - it's just so much easier (*). And so, it was pretty big deal when people invented Logarithms, because the fact that \begin{align}\log(xy)=\log(x)+\log(y)\end{align} meant that (provided that you could convert from a number \(x\) into its logarithm \(\log(x)\)) you were able to covert a multiplication problem into an addition one.

Now, I must admit that I was super-surprised to find out that the first (proper) logarithm ever developed was (more-or-less) done in base \(1-10^{-7}\). It...just seemed sooooooo arbitrary! Though, I think that there's probably a good astronomy-based explanation for why this base was chosen (**)... in fact, I might've even heard this explained on one of the recent episodes of the BBC In Our Time podcast? (hint: you should totes go check it out =P)

Analogously, matrix multiplication is also harder than matrix addition. And the fact that even for \(2\times2\) matrices, matrix multiplication \begin{align} \left[\begin{array}{c}{c} a_{11} & a_{12} \\ a_{21} & a_{22}\end{array}\right] \left[\begin{array}{c}{c} b_{11} & b_{12} \\ b_{21} & b_{22}\end{array}\right] = \left[\begin{array}{c}{c} a_{11}\times b_{11}+a_{12}\times b_{21} & a_{11}\times b_{12}+a_{12}\times b_{22} \\ a_{21}\times b_{11}+a_{22}\times b_{21} & a_{21}\times b_{12}+a_{22}\times b_{22}\end{array}\right] \end{align} actually requires 8 little multiplications just adds insult to injury...ammirite?

Weeeeell, fear no more! Because we can totally reduce \(2\times2\) matrix multiplication down to just 7 multiplications (***)! And here's how:

Start by computing these guys:

1. \(m_1:=(a_{11}+a_{22})\times (b_{11}+b_{22})\),
2. \(m_2:=(a_{21}+a_{22})\times b_{11}\),
3. \(m_3:=a_{11}\times (b_{12}- b_{22})\),
4. \(m_4:=a_{22}\times (b_{21}-b_{11})\),
5. \(m_5:=(a_{11}+a_{12})\times b_{22}\),
6. \(m_6:=(a_{21}-a_{11})\times (b_{11}+b_{12})\),
7. \(m_7:=(a_{12}-a_{22})\times (b_{21}+b_{22})\).

This takes up all 7 of the multiplications that we're allowing ourselves. To finish off the matrix multiplication, the four entries of our multiplied matrix are given by:

1. \(m_1+m_4-m_5+m7\),
2. \(m_3+m_5\),
3. \(m_2+m_4\),
4. \(m_1-m_2+m_3+m_6\).

Et voila! THIS is called the Strassen Algorithm.

Now, this might seem like kind of a stupid thing to do, but I think that it was supposedly kinda useful in the early days of computing, i.e.: when computers had trouble handling multiplication. Just...umm...goes to show, right? Multiplication...so much harder than addition. =P

 *: unless if you're dealing with \(0\)...in which case, it's pretty easy either way
**: coupled with the fact that \((1-10^{-7})^{10^7}\approx\frac{1}{e}\)
***: but with a few more additions, which is fine, because additions are totally easier than multiplications

Today I Learned: It's All Goodstein

I came back from China last Thursday and I've found it surprisingly difficult to restart this blog.

Maybe it's the thought that now that I've finished my semester with my Accelerated Maths tutorial class, I'll no longer have a real human audience for this writing? Or maybe it's just sloth. =P

So, I was away in China for a little over two weeks. It's summer there and suffocatingly hot and humid.

The first week or so I spent with my grandfathers: they live in the same apartment building, one floor away from each other. It was good to see that my (paternal) gramps was much healthier looking than the last time that I went back, although his attention span has grown somewhat evanescent. He would sit in his wicker chair, nude from the waist up, brows poised delicately on the fulcrum of furrowedom and unfurrowedness. The clacking of the rotating mechanical fan and his rhythmic laboured breathing lending his countenance an ethereal air. Except when we spoke, I was never sure if he was with me, or dreaming.

And the second week I spent in Shanghai. Yea, Shanghai's pretty chill, just not weatherwise. But let's start with the actual journey to China.

My flight was delayed by half an hour, so I sat in frustration (*) reading Harer and Penner's Combinatorics of Train Tracks. Nearing the original (undelayed) boarding time, I hear some commotion behind me and turn around to have a look: a Chinese girl had approached the metallic security door that you go through to get onto the plan. She was feeling...no...she was...groping every crevice of the door, until a few of the elderly aunties came up to her and told her that boarding had not yet commenced. She seemed content with that answer, strolled back to the waiting area, before swivelling about and running back to the gate, flailing at imaginary buttons that might magically open this door.

The buttons, they just weren't there.

And soon, the Chinese aunties came hobbling towards her once more, and so we saw the repetition of a few more cycles of this explanation/flailing-loop. Throughout this process, the airport staff are struggling to communicate with her, but to no avail. In between their attempts to talk to her, she makes a phone call to her dad (I found this out later), frantically crying out in fumbling, tumbling Chinese: "I'll listen to you", "The steel door is closed. It's closed" and "I want to go home; I want to go home; I JUST WANT TO GO HOME".

I just want to go home.

At this point the staff are asking for someone to help them translate, and I happily acquiesce, and we independently arrive at the (obvious) conclusion that she is probably a higher-functioning Asperger's syndrome-sufferer (**). Soon, security is called, and as they gently drag her from the security gate, I call out to her and begin explaining to her that I understand her desire to be on the plane since it's nearing 11. At this, she seemed relieved. I then ask if she received the firm instructions that she must be on the plane by 11 from a family member like her mother or her aunt (I didn't know that it was her father at this point) in the hopes that I could convince her to call them again and that I might then explain to them the actual situation (my guess is that she probably miscommunicated to the plane situation, and that perhaps they could give her new instructions). Maybe she was troubled at my line of questioning, maybe I just reminded her of her family and homesickness, but whatever the case she ran off.

Immediately, the security guards asked me to help talk to her, so I race around the crowd, get to her and by the time that I reach her she is in a state of hysteria. She is surrounded by a flock of chanting aunties, and has begun dry-sobbing. I offer her my hands (***), she takes them, and I begin anew my attempt to get her to call her father (by this time I've been informed by someone that it was her father).

She does (****) calm down.

But then I'm interrupted by a forceful middle-aged uncle who tells her that she must calm down and a middle-aged lady with an infant in her arm saying "look, my baby isn't afraid, so you shouldn't be scared either". And....and...I back away, entrusting them with the situation. And returning to my seat.

I..just walked away. =/

And then security took her away.

I mean, fair enough - security was probably always going to take her away; even if I'd managed to get her to contact her father, explain the situation, and have him relay to her new instructions regarding plane boarding, how might the airline staff trust her to behave sufficiently "normally" on the long flight back to China? A part of me keeps trying to find ways out - could her father have assigned me as a temporary "guardian" on this flight? Indeed, completely ridiculous "solutions" like these.

And after boarding, the empty seat next to mine on a mostly filled out plane did not help relieve me of these haunting thoughts: I kept wondering if this was her seat, the seat of that poor, crying, sobbing girl flailing herself against the hard, cold, metallic barrier: wanting to go home, but hindered by her own frets and incomprehension.

I guess, as a Christian, there's a parable here - there is, for me, a reminder that often we Christians, Jews and Muslims (worshippers of the same God) struggle and flail and cry and shout to "go home", but are stumbled by our own incomprehension. We do not see that Heaven/Paradise is to come to know, love and even befriend the God of the Jews, the Father of Abraham/Ibrahim, the Creator (*****) of the universe. And instead, miss the point.

So...erm...in remembrance of my inability to communicate with this girl...let's...let's try to communicate beyond the limitation of language. Let's try to do today's maths without words:

\(1=2^0.\)

1. \(\leadsto 3^0-1=0.\)

\(\Rightarrow G(1)=1.\)

 \(2=2^1.\)

1. \(\leadsto 3^1-1=2=2\cdot 3^0.\)
2. \(\leadsto 2\cdot 4^0-1=1=4^0.\)
3. \(\leadsto 5^0-1=0.\)

\(\Rightarrow G(2)=3.\)

\(3=2^1+2^0.\)

1. \(\leadsto 3^1+2^0-1=3^1.\)
2. \(\leadsto 4^1-1=3=3\cdot 4^0.\)
3. \(\leadsto 3\cdot 5^0-1=2=2\cdot 5^0.\)
4. \(\leadsto 2\cdot 6^0-1=1=6^0.\)
5. \(\leadsto 7^0-1=0.\)

\(\Rightarrow G(3)=5.\)

\(\Rightarrow G(4)=\ldots 7?\)

\(4=2^2.\)

1. \(\leadsto 3^3-1=28=2\cdot 3^2+2\cdot 3^1+2\cdot 3^0.\)
2. \(\leadsto 2\cdot 4^2+2\cdot 4^1+2\cdot 4^0-1=41=2\cdot 4^2+2\cdot 4^1+4^0.\)
3. \(\leadsto 2\cdot 5^2+2\cdot 5^1+5^0-1=60=2\cdot 5^2+2\cdot 5^1.\)
4. \(\leadsto 2\cdot 6^2+2\cdot 6^1-1=83=2\cdot 6^2+6^1+5\cdot 6^0.\)
5. \(\leadsto 2\cdot 7^2+7^1+5\cdot 7^0-1=109=2\cdot 7^2+7^1+4\cdot 7^0.\)
6. \(\leadsto 2\cdot 8^2+8^1+4\cdot 8^0-1=139=2\cdot 8^2+8^1+3\cdot 8^0.\)

\(\ldots\)

192. \(\leadsto 384^2+20\cdot 384-1=155136=384^2+19\cdot 384+383.\)

\(\ldots\)
\(\ldots\)
\(\vdots\)
\(\ldots\)

14. \(\leadsto 0.\)

\(\Rightarrow n=G(4)=3\cdot 2^{77}(2^{3\cdot 2^{77}}-1)+44>10^{100000}.\)

!!!

\(G(6)=???\Rightarrow\) $5. =)

Note that this is all made possible thanks to Goodstein's theorem, as in: it's not completely obvious that \(G(n)\) is finite for every positive integer \(n\). And I'm not the one paying out $5 for computing \(G(6)\), it's Ronald Graham.


*: My frustration did not stem from the delay of my flight, it was more because I was stuck on one of the steps in one of their proofs.
**: May be highly non-pc, but I will call it suffering, and I won't bother justifying myself in this footnote. =/
***: Let's not romanticise this in the most literal interpretation of "romanticise", she was no Rita Leeds.
****: At least...she does in my memories - which I don't completely trust, although I've written most of this down in a diary, so it should be fairly accurate.
*****: Whatever creation means.

Today I Learned: Generalised Pythagoras' Theorem

I had a hotpot dinner at church last Saturday. And speaking of hotpots - my friend broke her's (*). And no, that's neither a euphemism nor a metaphor. She was boiling water on the stove, forgot about it, only to come back to find a toasty dry pot roasting over blue flames. Quickly swiping the pot into the sink, she turned on the tap - only to find it shattered by the icy water.

This of course reminded me of my various childhood failures at drinking milk.

I used to drink about a litre of milk a day. I suppose that I should probably mention that China's experiments in pragmatic socialism had made this economically viable, but that's hardly the point. Instead, the point is that I was a champion of milk-drinking. So I was pretty shocked the first time that I tried milk here in Australia.

It was revolting.

It was all...creamy, and milky and not at all alike that watery malk produced by our proud proletariat Communist cows! Aussie milk: so gross.

So, to maintain my strong and healthy bones, I learned to take my milk with a big spoonful of sugar. Which again is slightly odd, because I was fine with taking medicine, in fact, I kind of liked it. But I'm getting distract when I should be distracting you with the story of that time that I mistook MSG for sugar - it certainly didn't help with my milk-loathing.

There was also one time when, home alone, I decided to microwave some milk during the commercial breaks (I can't remember the show, it was likely Sesame street or Play School), only to realise upon retrieving the glass that I'd forgotten to pour the actual milk into the glass (***). Shattered by my mindless folly, I took the glass to the sink and poured myself some water - only to find the glass shattered by this second act of mindless folly.

I've basically told you the same story twice: hot vessel + cold water = shattered pride. And this retelling of the same story but with minor details adjusted happens a lot in research mathematics. It is what we call generalising a result.

So let's talk about Pythagoras' theorem.

Oh wait, let's not - I've already done it here. Now there's an obvious generalisation to this result in higher dimensions. If we paraphrased/reinterpreted Pythagoras' theorem to say: the distance between two given points \((x_1,x_2)\) and \((y_1,y_2)\) on the plane \(\mathbb{R}^2\) is \begin{align}\sqrt{(y_1-x_1)^2+(y_2-x_2)^2},\end{align} then a fairly mundane generalisation would be that the distance between two points \((x_1,x_2,\ldots,x_n)\) and \((y_1,y_2,\ldots,y_n)\) on the plane \(\mathbb{R}^n\) is given by: \begin{align}\sqrt{(y_1-x_1)^2+(y_2-x_2)^2+\ldots+(y_n-x_n)^2}.\end{align}

But here's a more interesting generalisation that actually resembles the usual Pythagoras' theorem:

Take a square, slice off a small corner and you get a right-angled triangle. Take a cube, slice off a small corner and you get a right-angled tetrahedral. So take \(n\)-dimensional hypercube, slice off a small corner and you (should) get a right-angled \(n)-simplex (basically the generalisation of triangles and tetrahedrals)! Now, with a little imagination you should be able to see that this \(n\)-simplex has \(n+1\) "hyperfaces" - just like how a (\(2\)-dim) triangle has \(3\) sides or how a (\(3\)-dim) tetrahedral has \(4\) sides, You know how it is (****). And that one of these hyperfaces \(S_n\) is bigger than the rest \(S_0,\ldots,S_{n-1}\). Then we have following identity:\begin{align}vol(S_0)^2+\ldots+vol(S_{n-1})^2=vol(S_n)^2,\end{align} where \(vol(S_i)\) is the \((n-1)\)-dimensional volume of \(S_i\).

Awesome result, right? In particular, it says that the sum of the squares of the areas of the three smaller faces of a right-angled tetrahedral is equal to the square of the biggest face - i.e.: the sort of hypotenusoidal face.

To bad that the proof that I have for this isn't as cool as I want it to be. Although there are some nice ideas here, so very roughly outline it:

1. Show that a \(n\)-dimensional cone/pyramid with \((n-1)\)-dimensional base \(B\) has volume \(\frac{h}{n}vol(B)\), where \(h\) is the height of the apex (orthogonally) from the base. This can be done by considering about how the volume of \(B\) changes in the cross-sections of this cone parallel to the base, and then integrating these cross-sectional volumes along the height.
2. Conclude therefore that the volume of a right-angled simplex with vertices at \begin{align}(0,0,\ldots,0),(h_1,0,\ldots,0),(0,h_2,0,\ldots,0),\ldots,(0,\ldots,0,h_n)\end{align}is given by \(\frac{1}{n!}h_1\times h_2\times\ldots\times h_n\). And note that this may also be written as \(\frac{1}{n!}\) times the determinant of a matrix obtained by taking the non-origin vertex coordinates of our simplex as the rows of this matrix.
3. Combine this previous point with the fact that (high-dimensional versions of) shear mapping preserves volumes to get that the volume of a (general) \(n\)-simplex with one vertex at the origin, and the rest at \begin{align}(a_{1,1},a_{1,2},\ldots,a_{1,n}),(a_{2,1},a_{2,2},\ldots,a_{2,n}),\ldots,(a_{n,1},a_{n,2}\ldots,a_{n,n})\end{align} is given by \(\frac{1}{n!}\) times the determinant of the matrix \(A:=[a_{i,j}]\).
4. Now, embed this simplex in a one-dimension higher space, and in so doing + some shearing mappings, we get a formula for a \(n\)-simplex in \(\mathbb{R}^n\), which in term allows us to rearrage the vertex coordinate terms in this determinant into edge lengths. This is, to my current understanding, mainly (some impressive) algebraic manipulation, and may be found on page 124 and 125 of Sommerville's An Introduction to the Geometry of n Dimensions. It should be said that at this point, we're seeing that the square of the volume of our simplex is expressed completely in terms of the squares of the lengths of the edges of our simplex!
5. The proof of the last part that relates the volumes of all the hyperfaces of our simplex is also currently algebraic in nature, and may be found in the following paper.

Actually, in the process of writing this up, I've seen that Alvarez has an earlier proof of this result which seems much more elementary and uses induction. Maybe I should read it...

Maybe. =)

Update: yea, I read it, it's actually a much nicer proof. I mean, I don't get to make the cool observations about expressing volumes in terms of determinants and the shear mapping stuff, but it's a pretty chill induction proof.

*: I think that it was a hotpot pot, it might have been just a regular pot though. Who knows? She does, probably.

**: huh...it's curious now that I think about it...it's almost as if milk is actually an acquired taste, kinda like Vegemite?

***: on second thoughts, I could be lying here - I might have wanted water instead...huh, it was either water or milk...I'm leaning more towards water now.

****: this is an Arnold Schwarzenegger quote from Hercules in New York, but I just can't find footage of it on the interwebs. =(

Today I Learned: Descartes' Circle Theorem!

Guys, guys, guuuuys - my life, she-is-a-how-you-say-a-become-flippity-up-down: I just found out that forks may actually be a Chinese invention (*).

Yes, forks. And that they predate chopsticks. I mean, what the frigate?!!??

So, to distract myself from this distressing thought, here's a cute little fact: draw three circles \(C_a,C_b,C_c\) so that any two of them are tangent, then there exist precisely two circles \(C_d,C_{d'}\) tangent to all three circles.

Even cuter little fact: label the respective radii of \(C_a,C_b,C_c,C_d\) by the letters \(a,b,c,d\), then \begin{align}2(\frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2}+\frac{1}{d^2})=(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{d})^2.\end{align} A less cute fact: the above identity also holds if we replace \(d\) with \(d'\), i.e.: the radius of \(C_{d'}\); I was just too lazy to figure out how to say this nicely. Oh, and I also forgot to mention that if one of these circles encircles the other three, then we think of its radius as being a negative number.

For a much more eloquent description of this little gem, consider the following poem by the Nobel prize winner Frederick Soddy, published in Nature (one of the most respected journals out there), June 1936:

The Kiss Precise
 

For pairs of lips to kiss maybe
Involves no trigonometry.
'Tis not so when four circles kiss
Each one the other three.
To bring this off the four must be
As three in one or one in three.
If one in three, beyond a doubt
Each gets three kisses from without.
If three in one, then is that one
Thrice kissed internally.

Four circles to the kissing come.
The smaller are the benter.
The bend is just the inverse of
The distance from the center.
Though their intrigue left Euclid dumb
There's now no need for rule of thumb.
Since zero bend's a dead straight line
And concave bends have minus sign,
The sum of the squares of all four bends
Is half the square of their sum.

To spy out spherical affairs
An ocular surveyor
Might find the task laborious,
The sphere is much the gayer,
And now besides the pair of pairs
A fifth sphere in the kissing shares.
Yet, signs and zero as before,
For each to kiss the other four
The square of the sum of all five bends
Is thrice the sum of their squares.

So, peeps usually call this result Descartes' Circle Theorem, even though it's possible (I dun-actually-no) that this has been studied since the ancient Greeks. So, I've read somewhere that heaps of peeps have rediscovered this result over the years, and that there are a fair few proofs of it (including one by Newton!). I think that I know two, three ways to prove this result (but not its generalizations - which are, I think...also due to Soddy?).

• Mathod (**) 1: Coordinate bash - just write this up in \(\mathbb{R}^2\) and bash it out. But this is probably gonna be pretty nasty.
• Mathod 2: Inversions - Mobius transformations on the complex line \(\mathbb{C}\) take circles to circles, and so too do reflections (such as complex conjugation) on \(\mathbb{C}\), so the map\[\varphi:z\rightarrow\frac{r^2}{\bar{z}-\bar{w}}+w\] is a special kinda map that flips the inside of a circle of radius \(r\) based at \(w\) to the outside and the outside in so that circles are still preserved. And we can use maps of this form (called inversions) to get our circles in some standard form and then bash some stuff in this standard form. Still, nasty.
• Mathod 3: Heron's formula - I actually found a proof for this in a paper by Coxeter, who has a heap of stuff named after him in maths. He himself yoinked this proof from another paper by a Mr. Philip Beecroft in one of the most deliciously named journals ever: "The Lady's and Gentleman's Diary for the year of our Lord 1842, being the second after Bissextile, designed principally for the amusement and instruction of Students in Mathematics: comprising many useful and entertaining particulars, interesting to all persons engaged in that delightful pursuit".

Maaaaaan...that's such a good name for a journal.

Okay, so let's just try to briefly walk through how this proof works. I guess I should probably link the article that I pulled this from, for those who're interested. Coxeter's a very good writer, so it's actually pretty readable if you're willing to Google a few definitions. The first idea is to notice that given a configuration of four pairwise tangent circles \(C_a,C_b,C_c,C_d\), the three tangent points of any three such circles will lie on a unique circle. Therefore, we get four new circles \(C_\alpha,C_\beta,C_\gamma,C_\delta\) respectively meeting the tangents points of \[\{C_b,C_c,C_d\},\{C_a,C_c,C_d\},\{C_a,C_b,C_d\},\{C_a,C_b,C_c\}.\]

So, it's pretty cool that \(C_\alpha,C_\beta,C_\gamma,C_\delta\) will itself form a new configuration of four pairwise tangent circles, and that these eight circle come from a stereographic projection of the intersections of the eight face-planes of a regular octahedron contained in its circumsphere.

Psst: I was gonna draw a picture of this, but it got too messy. =(

Well, I'm not going to justify those facts, so let's just do some high school geometry instead and prove the darn result!

The first thing that we should notice is that, by construction, the circle \(C_{\delta}\) is circumscribed by the triangle with vertices placed at the centers of \(C_a,C_b\) and \(C_c\). Moreover, since the normal (line) to a tangent line of a circle goes through its center, we may split triangle \(\triangle ABC\) up into six little right-angled triangles each of height \(\delta\).

Invoking Heron's formula, we get that: \begin{align}\delta^2(a+b+c)^2=abc(a+b+c),\end{align}
which is a pretty sweet lookin' shabang. Now let's do something similar with the area of triangle \(\triangle BCD\) with its vertices centered at the circles \(C_b, C_c\) and \(C_d\). We see that this area - which we can compute by Heron's formula in terms of \(b,c\) and \(d\), may also be obtained by subtracting the area of the four smaller triangles from the two larger ones as per the following picture (you'll notice that my circles are pretty out of scale with respect to each other when compared with the first pic =P).

Therefore, we obtain in this case: \begin{align}\alpha^2(b+c+d)^2&=bcd(b+c+d).\end{align}
Which looks pretty similar to our previous formula. And at this point we just ply a few symmetry arguments, wlogs and a tiny bit of algebraic tweaking to obtain the following set of algebraic thingies: \begin{align} \alpha^{-2}&=b^{-1}c^{-1}+b^{-1}d^{-1}+c^{-1}d^{-1}\\ a^{-2}&=\beta^{-1}\gamma^{-1}+\beta^{-1}\delta^{-1}+\gamma^{-1}\delta^{-1}\\ \beta^{-2}&=a^{-1}c^{-1}+a^{-1}d^{-1}+c^{-1}d^{-1}\\ b^{-2}&=\alpha^{-1}\gamma^{-1}+\alpha^{-1}\delta^{-1}+\gamma^{-1}\delta^{-1}\\ \gamma^{-2}&=a^{-1}b^{-1}+a^{-1}d^{-1}+b^{-1}d^{-1}\\ c^{-2}&=\alpha^{-1}\beta^{-1}+\alpha^{-1}\delta^{-1}+\gamma^{-1}\delta^{-1}\\ \delta^{-2}&=a^{-1}b^{-1}+a^{-1}c^{-1}+b^{-1}c^{-1}\\ d^{-2}&=\alpha^{-1}\beta^{-1}+\alpha^{-1}\gamma^{-1}+\beta^{-1}\gamma^{-1}.\end{align} Well, we've got all of these cross-terms and stuff on the right hand side, so why not look at an algebraic expression which might generate such cross-terms (***): \begin{align}(a^{-1}+b^{-1}+c^{-1}+d^{-1})^2&=a^{-2}+b^{-2}+c^{-2}+d^{-2}+2\text{( all the cross terms! )}\\&=a^{-2}+b^{-2}+c^{-2}+d^{-2}+\alpha^{-2}+\beta^{-2}+\gamma^{-2}+\delta^{-2}\\&=(\alpha^{-1}+\beta^{-1}+\gamma^{-1}+\delta^{-1})^2.\end{align} So we see that: \begin{align}a^{-1}+b^{-1}+c^{-1}+d^{-1}=\alpha^{-1}+\beta^{-1}+\gamma^{-1}+\delta^{-1}.\end{align} Now playing the same game, but with fewer cross-terms, we obtain: \begin{align}-a^{-2}+b^{-2}+c^{-2}+d^{-2}&=2\alpha^{-1}(\alpha^{-1}+\beta^{-1}+\gamma^{-1}+\delta^{-1})\\&=2\alpha^{-1}(a^{-1}+b^{-1}+c^{-1}+d^{-1}).\end{align} Completing the square with the LHS and cancelling stuff, we find that:\begin{align}-a^{-1}+b^{-1}+c^{-1}+d^{-1}=2\alpha^{-1}.\end{align} At this point my brain's all like: come on maaaaaan, there's gots to be some monodromy goin' on in dis! Bah! I can't quite figure it out yet...(makes squinty eyes) one day, my friend, one day....

Anyhoo, so there are three other similar equations to this last guy, and if we just square both sides for each of these four equations, expand, add them together, then all the cross-terms cancel and we're left with: \begin{align}a^{-2}+b^{-2}+c^{-2}+d^{-2}=\alpha^{-2}+\beta^{-2}+\gamma^{-2}+\delta^{-2}.\end{align} So adorable.

Anyhooo, putting the fact that the reciprocal sums and the reciprocal square sums of \(\{a,b,c,d\}\) and \(\{\alpha,\beta,\gamma,\delta\}\) are equal, we finally get what we came for: \begin{align}2(a^{-2}+b^{-2}+c^{-2}+d^{-2})&=a^{-2}+b^{-2}+c^{-2}+d^{-2}+\alpha^{-2}+\beta^{-2}+\gamma^{-2}+\delta^{-2}\\&=(a^{-1}+b^{-1}+c^{-1}+d^{-1})^2.\end{align}

Claps chalk off hands and walks off.

*: according to something I saw on TV and Wikipedia, not the forks page, but the Chinese inventions page linked in the next line

**: I kept trying to type "method" but typed "mathod" instead. So I figured that I might as well stick to it, maths+method=mathod. =P

***: I'll admit that this is pretty weak motivation, even for me. =)

Today I Learned: the Thue-Morse sequence

I did the 15 km run for the kids last Sunday. It took me about 80 minutes to run the whole thing, and I beat my frenemy Han Liang Gan by 1 second. So, yea, pretty much the best run ever! =)

Orrite - it's maths time! Now, let's say that you're only allowed to write "A"s and "B"s, no spaces and no punctuation. What's the length of a longest square-free word that you can write? That is: what is a longest word that you can write before you have the same sequence of letters appearing twice consecutively, such as in AA or ABAB?

Okay, orrite, orrite - that was a pretty silly question. The answer is obviously 3 (either ABA or BAB).

But what if I'd asked for the longest cube-free word instead? That is: subsequences like ABAABAABA are forbidden since it's ABA repeated thrice.

Well, the answer is \(\infty\).

And in fact, it's actually surprisingly easy to construct an example of an infinitely long cube-free word:

The Thue-Morse sequence.

1. Start with an initial sequence just given by: A.
2. Stick a copy of the sequence that you've got at the end, but with "A"s and "B"s switched.
3. Go back to step 2.

Specifically, applying those instructions, we grow the following sequence:
A\(\rightarrow\)AB\(\rightarrow\)ABBA\(\rightarrow\)ABBABAAB\(\rightarrow\)ABBABAABBAABABBA\(\rightarrow\)\(\ldots\)

So how can we prove this? Well, I'm certainly not going to write up a proof right now - I'm off to Easter camp tomorrow and there's much packing and stuff to be done! =)
 

Today I Learned: The Rational Circle

I think that tonight is meant to be the Lantern Festival or whatever. But let's not get distracted - let's talk about:

The Rational Circle.

Huh...I like the sound of that.

It vaguely conjures up the image of a clandestine cult, perhaps akin to the Pythagorean Brotherhood (*), encircling an altar of smooth grey slate; each crimson robed member up-raising a dragon's fang of chalk in fearful exultation, only lowering these totems for the transcription of mystical symbols of power.

In short: a typical group of mathematicians sitting around a blackboard.

For the past year, a couple of friends and I have been going through Deligne's proof of the Weil conjectures - a finite fields version of the Riemann hypothesis. We've done Weil I, and we've gone through parts of Weil II and now (most of us) have Weil-fatigue (okay, sure, it should probably be Deligne-fatigue).

So we're currently looking at four potential new topics, one of which will be selected for this coming year: geometric Langlands, Cobordismy stuff (in particular, Madsen Weiss), (Homological) Mirror Symmetry and Topological Recursion (i.e.: Eynard-Orantin invariants and stuff). Oh, and I guess there was a fifth suggestion - we thought about sitting down and proving the Volume Conjecture, but decided that it wasn't exciting enough. =P

And in amidst all the discussion about the merits of each of these topics we started (as you do, assuming that your life is like American television) to reminisce all the good times that we had in the Weil conjecture series. Like that very first session when Norman Do, for whatever reason, gave us a pretty sweet description of the rational points of the unit circle in a passing remark. A description so sweet that we immediately distracted ourselves for a minute or so proving it.

Claim: the rational points on the unit circle \(\mathbb{S}^1\), i.e. the coordinates are fractions (of integers), may all be written in the form:\begin{align}(\frac{u^2-v^2}{u^2+v^2},\frac{2uv}{u^2+v^2}),\,u,v\in\mathbb{Z}.\end{align}
Huzzah.

In fact, we can easily see that any point of such a form is a rational circle point, unless if both \(u\) and \(v\) are zero. But I didn't really wanna type all that in the claim because MathJax makes words that you type in mathmode look funny.

Whatevs man, let's just prove this jazz.

To begin with, by the unit circle \(\mathbb{S}^1\), I mean the set:\begin{align}\mathbb{S}^1:=\{(x,y)\in\mathbb{R}^2\,:\,x^2+y^2=1\}.\end{align}
Now, consider the following map from \(\mathbb{S}^1\) to the real projective line \(\mathbb{R}\mathrm{P}^1\) given by:\begin{align}\psi:\mathbb{S}^1\rightarrow\mathbb{R}\mathrm{P}^1,\,(x,y)\mapsto[y:1-x].\end{align}
Heeeey, whaddya know - this is precisely the stereographic projection map of \(\mathbb{S}^1\) from \((1,0)\) onto the \(y\)-axis (plus an extra point at \(\infty\) for the projection of \((1,0)\) itself). So \(\psi\) is totally a bijection.

Now, it's clear that \(\psi(x,y)=[y:1-x]\) can be written in the form \([u:v]\in\mathbb{Z}\mathrm{P}^1\subset\mathbb{R}\mathrm{P}^1\) if \((x,y)\) is a rational circle point. In fact, for any \([u:v]\in\mathbb{Z}\mathrm{P}^1\), the inverse point \(\psi^{-1}[u:v]\) is a rational circle point!

Let's check this by bashing stuff.

So we're looking for some \(x,y)\) such that \([u:v]=[y:1-x]\). Therefore, we have that \(u(1-x)=vy\) and shoving this into \(x^2+y^2=1\) yields that:\begin{align}(u^2+v^2)x^2-2u^2x+u^2-v^2=0.\end{align}This quadratic yields the solutions that:\begin{align}x=\frac{u^2\pm v^2}{u^2+v^2}=1,\frac{u^2-v^2}{u^2+v^2}.\end{align} The case that \(x=1\) is covered by the latter (via \([u:v]=[1:0]\) ) and hence may be excluded.

Repeating the same calculations for \(y\), we get that\begin{align}y=0,\frac{2uv}{u^2+v^2}.\end{align}As before, the case that \(y=0\) is covered by the latter case (via \([u:v]=[\pm1:0]\) ) and may be excluded.

Oh look, not only did we show that the stereographic projection map \(\psi\) gives us a bijection between the rational circle points and \(\mathbb{Z}\mathrm{P}^1\), but we also proved our initial claim.

-*Insert obligatory proof-ending blank square*

Going back to my story: I think that the reason that Norm brought up this example was to demonstrate to us the following guiding principle: rational solutions to polynomials are all about number theory.

As an example: we've just characterised the rational solutions to the polynomial \(x^2+y^2=1\) as being of the form:\begin{align}(\frac{u^2-v^2}{u^2+v^2},\frac{2uv}{u^2+v^2}).\end{align}And anyone's who's played around with number theory will immediately recognise these as being related to the general form for any Pythagorean triad:\begin{align}(u^2-v^2,2uv,u^2+v^2).\end{align}Which, by the way, is hardly surprising once you think about rescaling Pythagorean triangles so that its hypotenuse is length \(1\).

What might be surprising, is that we started off with a rant about the Pythagorean Brotherhood, wandered about and wound up back at Pythagoras - effectively tracing out a big circle of thought, a rational circle, if you will. =P

Since it's pretty hard to finish on a circle, let's shoot off on a tangent. This characterisation of the rational points of the unit circle also comes as a consequence of Hilbert's Theorem 90 which is a pretty early example of how number theory may be phrased in terms of (and resolved via) cohomology theories.

Sometimes I worry about this.

Sometimes I worry one day we'll show that pretty much everything in maths may be phrased in terms of cohomologies...I mean, cohomology is one of the most straight forward ways that we can extract invariants from stuff...and to be honest, we usually can't do very much in maths apart from the most obvious things. So, who knows...may be my worries are...semi-quasi-pseudo-meta-justifiable?

Who knows, who cares: we thought in a big loop and went off on a perpendicular, thereby forming a Q - that is: Q for quitting.

Let's quit here.

I am become tired and (more) incoherent (than usual).

*: which, despite its name, did include women.

Today I Learned: the Infinite Nielsen Extension

I just saw something so cool that I had to write it down.

Grab a bordered Riemann surface \(R_0\).

Done it yet?

Goodo.

Now uniformize it with the unique (compatible) hyperbolic metric with geodesic boundaries; the universal cover of \(R_0\) will sit as some (strict) subset of the hyperbolic plane \(\mathbb{H}\). The fundamental group of \(R_0\) acts discontinuously on \(\mathbb{H}\), and the the quotient space under this action is a hyperbolic surface \(R_1\supset R_0\). Now forget about the hyperbolic metric on \(R_1\) and just remember its Riemann surface structure. And...

...uniformize it with a hyperbolic metric that has geodesic boundaries; ...etc.
(Just repeat what we did in the previous paragraph to get a \(R_2\) and so forth.)

By the end of this process, we wind up with whole bunch of Riemann surfaces\begin{align}R_0\subset R_1\subset R_2\subset R_3\subset\ldots \end{align}so that when each one is uniformized to have a hyperbolic metric with geodesic boundaries, the lengths of these boundaries are strictly decreasing! In fact, take the Riemann surface obtained as the "union" of all of these and you'll have something that uniformizes to a hyperbolic surface with cusps.

And that's the infinite Nielsen extension.

It's...it's actually kinda obvious when you think about it, but I still reckon it's pretty sweet. =P

In summary:

Maan...pictures are too efficient. Gotta nerf them.

Today I Learned: the Poincare Inequality

It's been a while since I've last written on this blog - and I've been learning some pretty cool stuff. Yes, I've had to concede that analysis is cool. Well, at least it's functional analysis.

Here's an awesome result that I saw yesterday:

Theorem of win (*): let \(\overline{M}\) be a connected compact Riemann surface with non-empty boundary, and \(K\) a smooth nonpositive function on \(\overline{M}\), then there exists a \(\mathbb{C}\)ompatible Riemannian metric \(g\) on \(\overline{M}\) which has \(K\) as its Gaussian curvature! Moreover, this metric \(g\) becomes unique (and still exists) if you designate a (smooth) metric on the boundary.

It's paraphrased slightly because I wanted to avoid asserting that every smooth Riemannian metric in a conformal class of metrics on a manifold can be written in the form: \[g=e^{2\varphi}g_0\] for some base metric \(g_0\) and any smooth function \(\varphi: \overline{M}\rightarrow\mathbb{R}\). In retrospect, maybe I should have just gone with that. Oh well, it's too late Liz Lemon, it's too late (Blast! Can't find a referencing Youtube clip for this 30 Rock quote).

On the plus side, I managed to introduce \(\mathbb{C}\)ompatible instead of saying compatible with its Riemann surface structure. Pretty Stokes'd with that...

Basically, this theorem tells us that as long as you don't deal with positive curvature, you can impose any kind of Gaussian curvature on your surface. This result isn't (to my understanding) all that hard to prove, although I still find some of the language a bit intimidating. But the fact that it's solving for a Dirichlet problem (i.e.: you specify the metric on the boundary) as opposed to something that let's you specify the geodesic curvature on the boundary, is unfortunate. Well, at least for me. Because I really want to prove stuff like, you can uniformize a bordered Riemann surface uniquely so that it's hyperbolic and has constant boundary geodesic curvature blah.

So I tried to prove this instead...and I think that I've done it. Almost all of the arguments are based on what Osgood, Phillips and Sarnak used in this little paper, all I did was that I:

1. Came up with a family of functionals that link together the two that they study for surfaces with negative Euler characteristic, and found appropriate constraints on the domain of these functionals.
2. Worked out a tweaked Poincare inequality that makes proves the boundedness of a sequence of functions tending to the infimum of one of our given functionals (step 3 of this).
3. Emailed Ben Andrews at the ANU to see if elliptic regularity would hold for one of the steps that I needed. He was really quick about responding to my emails and politely nudged me towards a pretty sweet reference when I asked for one (+we both know that I know waaaay too little analysis, and need to do a bit more ground-work before I can make use of his suggestions/hints/glaringly obvious solution to anyone who's moderately okay with analysis).

So let's try to prove this tweaked Poincare inequality, like, now.

Claim: given a Riemannian surface \((R,g)\), let \(W^{1,p}(R)\) denote its \((1,p)\)-th  Sobolev space. Then for a constant \(C\) dependent only upon \(R\) and \(p\), \begin{align}\|\varphi\|_p=\left(\int_R|\varphi|^pdA\right)^{\frac{1}{p}}\leq C\left(\int_R|\nabla\varphi|^pdA\right)^{\frac{1}{p}}=\|\nabla\varphi\|_p\end{align} is true for functions \(\varphi\) in any subspace \(W^{1,p}(R)^{\tau}\subset W^{1,p}(R)\) constrained by: \begin{align}(1-\tau)\int_R\varphi dA+\tau\int_{\partial R}\varphi|_{\partial R} ds=0,\,0\leq\tau\leq1,\end{align}where \(\varphi|_{\partial R}\) denotes the trace of \(\varphi\) - the notion agrees with what you think it means when \(\varphi\) is continuously defined over all of \(R\).

Sigh...such a mouthful. Here comes the proof (**):

Let's prove this by contradiction. Assume that there is sequence of functions \(\{\varphi_k\}\) in \(W^{1,p}(R)^{\tau}\) so that \begin{align}\int_R|\varphi_k|^pdA>k\int_R|\nabla\varphi_k|^pdA.\end{align} This means that \(\varphi_k\) can't be \(0\), hence the norms \(\|\varphi_k\|_p\) are nonzero and we may assume without loss of generality that the \(\varphi\) were normalized to begin with. Note that the normalization of a function still lies in \(W^{1,p}(R)^\tau\) because it's a vector subspace of the Sobolev space \(W^{1,p}(R)\).

The normalization means that \(\|\varphi_k\|_p=1\) and \(\|\nabla\varphi_k\|_p<\frac{1}{k}\). The former fact, combined with the Rellich-Kondrachov theorem tells us that a subsequence of the \(\{\varphi_k\}\) must converge strongly (and hence a subsequence of that subsequence converges pointwise) to some \(\varphi\in L^p(R)\). Relabel \(\{\varphi_k\}\) as this subsequence, coz we can.

Okay, I lied slightly. It doesn't follow from the most broad versions of Rellich-Kondrachov theorem straight off. The idea is that for bounded domains and \(p\geq n\), we know that \(W^{1,p}(\Omega)\subset W^{1,n-\epsilon}(\Omega)\) and so if you bring \(\epsilon\) close enough to \(0\), you can get that \(W^{1,n-\epsilon}(\Omega)\) is compactly embedded in \(L^p(\Omega)\). Hence, \(W^{1,p}(\Omega)\) is compactly embedded in \(L^p(\Omega)\) for all \(p\in[1,\infty]\). But to be honest, I'm a bit worried about this argument, because it's based on my understanding of the \(n=p\) case argument presented in a remark at the end of section 5.7 in Evans (**). And maybe I've misunderstood him, because he invokes Morrey's inequality and Arzela-Ascoli to handle when \(p>n\). Worrisome.

Anyhoo, back to the proof.

Let's show that the \(\varphi\) we found actually lies in \(W^{1,p}(R)^{\tau}\). We're gonna do this by constructing a weak derivative in \(L^p(R)\). Take an arbitrary compactly supported smooth function \(\phi\in C^{\infty}_c(R)\) (i.e.: a test function), then we have that: \begin{align}\int_R \varphi\,\partial_{x_i}\phi dA=\lim_{k\to\infty}\int_R\varphi_k\,\partial_{x_i}\phi dA=-\lim_{k\to\infty}\int_R\partial_{x_i}\varphi_k\,\phi=0,\end{align}
where the last limit is because \(\|\partial_{x_i} \varphi_k\|_p\leq\|\nabla \varphi_k\|_p<\frac{1}{k}\). Therefore, we may take the weak derivative \(\partial_{x_i}\varphi\) to be the zero function, and so we see that any first order weak derivatives of \(\varphi\) are zero, which means that \(\varphi\in W^{1,p}(R)\). Now invoking either problem 11 of Evans (**) or corollary 2.1.9 of (***), we know that \(\varphi\) has to be constant. At the same time, we know that \(\varphi\) has to also satisfy the constraint that we initially placed upon \(W^{1,p}(R)\). Therefore, \(\varphi=0\), which contradicts the fact that \(\|\varphi\|_p=1\).

Hooray! 

Or rather, maybe...hooray? I guess in the course of writing this up, I've realised that there are a few details here and there that I'm a tad worried about. For example, do I know that the constraint here in this last step extends to \(\varphi\)? I don't see why not, and it certainly does on the area integral, but I'm not so comfortable with what's happening on the boundary with the trace operator and jazz. (Update: yea, it works out because the trace operator is continuous.) Plus there's that whole business with showing that \(\varphi\) is in \(W^{1,p}(R)\). I'm not really sure why we had to play with those integrals. Is it because we cannot conclude from \(\|\nabla\varphi_k\|_p\) tending to \(0\) that \(\|\nabla\varphi\|_p\) is zero and we just had to go through that rigmarole? (Update: I now think that it's to show that zero is a valid candidate for the weak derivative.) I'm not comfortable enough with analysis to say for sure yet. But whatever the case, I've learned stuff man. I've learned stuff.

Oh and as per usual, I lament the fact that I still haven't finished writing up about Lie's line-sphere correspondence, and resolve to do it soon.

*: Prop 1.7 in Ch 14 of Taylor's "Partial Differential Equations Vol. 3". It's kind of a long chapter. In fact, chapter 14 is kind of the whole book minus some backgroundy stuff, I think?
**: the proof is adapted from Theorem 1 in section 5.7 of Evans's "Partial Differential Equations". It's a pretty thick book, but the writing is beautiful.
***: Ziemer's "Weakly Differentiable Functors".

Today I Learned: On De-Klein-ing Lie's - Part 2

Update: Part 0 Part 1.

Roughly a year ago, I waltzed through the streets of Munich.

Everything was wonderful - I'd recently befriended an American couple and a African+German couple (they all very kindly let me crash at their places for weeks) and life was a whimsical concoction of Japanese conversations with strangers (I'm not Japanese), Bible studies, scaling European architecture (in town and on the alps), office meetings with my supervisor at the Ludwig Maximilian University (he was technically holidaying) and asking God to provide for all of my accommodations (I'm currently fairly well-off, but I asked it for good reason, and He did provide for a whole month - including a free week at a hotel in Istanbul, so I'd better hold up my end of the bargain). Even the weather was wonderful: cold, lippy, but not so chilling as to be penetrating.

The only thing that really bothered me was...why did they love Bayesian Statistics so much? I mean, the signs were everywhere. Above libraries, on opera posters, on random landmarks were scribed these...these impenetrable and insufferable letters: "Bayerische Staats". They haunted me. Statistics had made her mark upon the capital of Bavaria.

Yes. Bavaria. I only realised (much to my humiliation) after I'd landed back in Melbourne that I'd mistranslated Bayerische Staats, that is: the Bavarian State.

It was a good trip, I even managed to miss my flight back to Australia because I was doing some maths with my supervisor and scored having my first Thanksgiving turkey - with the American couple I mentioned earlier. Life (*) is awesome.

Pity that I hadn't also visited the second largest city in Bavaria - neighbour to a little university/Siemens town called Erlangen.

A while back (to all AMSI peeps who're still reading this, after that meandering introduction, yes, I know that your summer school is nearly over and your exams are coming up - hey, I'm a slow writer), I decided to write up a few things that I've learned from reading one of Klein's lectures on Lie's line-sphere correspondence. This is part 2: the Erlangen program.

A slightly modern understanding of the Erlangen program is that it is the study of the invariants of a group \(G\) acting transitively on a homogeneous space \(X\). There are key words here: groups, transitive, spaces and invariants. Let's consider an example.

Example 1.

The group \(SO(n)\) made up of orthogonal matrices with determinant \(1\) may be thought of as matrices whose column (and rows) constitute an orthonormal basis for \(\mathbb{R}^n\). This means that:

• any vector gets mapped to a vector of the same length;
• angles between vectors are preserved.

The only transformations of \(\mathbb{R}^n\) which can do this are rotations and reflections - we discount the latter option in this case because the determinant of a matrix in \(SO(n)\) is \(1\) as, opposed to \(-1\).


Now, because orthogonal matrices must preserve vector lengths, they cannot act transitively on all of \(\mathbb{R}^n\), so our space needs to be something smaller - like the unit sphere (any radius will do):\[\mathbb{S}^{n-1}:=\{(x_1,\ldots,x_{n})\,:\,x_1^2+\ldots+x_{n}^2=1\}.\]

The transitivity of the action of \(SO(n)\) on \(\mathbb{S}^{n-1}\) means that for any two points \(x,y\in \mathbb{S}^{n-1}\) there are a whole bunch of matrices taking \(x\) to \(y\), and either by post- or pre-multiplication by a matrix, it's clear that this set of matrices is in bijection with the group of matrices fixing \(x\) (or fixing \(y\)). Take \[x=(0,0,\ldots,0,1)\] and we see that this group of point-fixing matrices needs to be \(x\) in the bottom row and \(x^{t}\) in the last column, so the group of point-fixing matrices is precisely \(SO(n-1)\). Which of course means that: \[\mathbb{S}^{n-1}=SO(n)/SO(n-1).\] And this is what we mean by a homogeneous space: a group quotiented by a sufficiently nice (possibly non-normal) subgroup.

So, we've got our group, we've got our space - what are these invariants?

Well, we know that \(SO(n)\) is distance preserving on \(\mathbb{R}^n\), and knowing this it's not too hard to show that orthogonal matrices also preserve distances on \(\mathbb{S}^{n-1}\). So there you go: distances are preserved. In addition, the angle between two intersecting curves on \(\mathbb{S}^{n-1}\) are also preserved - you can show this by thinking about the tangent lines of these two curves at the relevant point of intersection (an exercise!). So, distances are preserved, angles are preserved, surely this means that spherical polygons must be preserved (insert higher dimensional generalisations of polygons where appropriate).

In fact, we're seeing that these invariants are pretty much what we'd expect to care about as geometers: spherical lengths, angles, spherical shapes, spherical volumes...etc.

In fact, it's as if:

the Erlangen program is an attempt to unify geometry in a cohesive language.

Let's list a few more examples:

Example 2.

Group: \(O(n)\) - the orthonormal matrices.
Space: \(\mathbb{S}^{n-1}\)
Invariants: spherical lengths, angles, spherical shapes, spherical volumes...etc.

Wait, isn't this the same example? Well, almost. The only difference being that \(O(n)\) includes not just rotations but reflection matrices too. And so there is one invariant that is retained for \(SO(n)\) that isn't for \(O(n)\): orientation (mirror-image-ness). So in our first example, we were able to distinguish a triangle on \(\mathbb{S}^2\) and its mirror image, whereas the two would be regarded as being identical in this second example.

Example 3.

Group: the group of linear functions look-a-likes on \(\mathbb{R^n}\) of the form: \[x\mapsto Ax+b,\]
where \(A\in O(n)\) is an orthogonal matrix and  \(b\in\mathbb{R^n}\) is just another vector.
Space: \(\mathbb{R}^n\).
Invariants: lengths, angles, shapes, volumes...etc.

This might look unfamiliar, but it's really just Euclidean geometry in disguise. Our space is \(\mathbb{R}\) and our symmetries are any combination of translations and rotations and reflections - precisely the symmetries that we'd think of in primary school.

Example 4.

Group: the special linear group \(SL_2(\mathbb{R})\) of \(2\times2\) matrices of determinant \(1\).
Space: the hyperbolic upper half plane \(\mathbb{H}\) given by \[\mathbb{H}:=\{z=x+yi\in\mathbb{C}\,:\,\mathrm{Im}(z)=y>0\},\]
and the action of the group is given by:\begin{align}\left(\begin{array}{c c}a & b \\ c & d \end{array}\right)\cdot z:=\frac{az+b}{cz+d}.\end{align}
Invariants: angles, orientation, hyperbolic length, hyperbolic polygons, hyperbolic area...etc.


It's sometimes said that polygons in in spherical, Euclidean and hyperbolic geometry are respectively fat, boring and thin (okay, I sorta lied: I haven't heard anyone other than high school kids call Euclidean triangles "boring"). As in, the sides of spherical triangles are curved slightly outwards, the sides of a Euclidean triangle are straight and the sides of a hyperbolic triangle are curved slightly inwards. In fact, this simple phenomenon is a manifestation of a deeper invariant of these geometries called the Gaussian curvature. In particular, the curvature of a sphere is positive, for the plane it's zero and for the hyperbolic plane it's negative, and you can think of curvature either in terms of how triangles curve or how much "space" you squeeze in at each "point".

Also, it's worth pointing out that the fact that the hyperbolic plane is a homogeneous space does make it extremely rigid. I'm just mentioning that as an alternate handwavy explanation of the rigidity of hyperbolic spaces to any individuals who might have asked me about this in the past.

It's also worth pointing out that I've provided a presentation of the hyperbolic plane that does not generalise very well to general hyperbolic spaces (and instead generalises more nicely to the Siegel upper half space). Go check out the Wikipedia article for homogeneous spaces to see how to do it for hyperbolic spaces.

Recently, I stumbled across this discussion on MathOverflow about the Erlangen program and what precisely it states. And I think that one of take home message that I got was that Erlangen program is that curious combination of beautiful logic and deep intuition - in parallel with Klein's self-assessment as a mathematician (perhaps not so colourfully phrased). It's like Monet's impressionism: colour, fire, light, captured by masterful brush strokes. Its triumph is that of intuition - we see once and once again the her indelible fingerprints in geometry. In Riemannian geometry, she is present at the grand level by uniformization and local models and present at the microscopic level via the Levi-Civita connection. Which in turn leads us to Cartan geometries and Cartan connections. In symplectic geometry, Lie's contact-transformations seem also to be grounded in this philosophy. The details are somewhat foggy to me, perhaps like a Seurat, but the forms are there.

So...um...Felix Klein, more than just the guy who came up with the Klein bottle.

*: Secretly, I wanted to write that God is awesome, but I chickened out. =P
 

Today I learned: A Pain in the Anal-ysis

I'm currently watching the Aussie Open men's final between Djokovic and Murray, and it's shaping out to be a reasonably long match (I may have written this when they were still at 6-7,7-6). Speaking of long matches, I hear that the longest women's match is six and a half hours long and featured a half-hour 643 point rally! And they only played two sets.

So let's take our minds off such painful, laborious sports and do something relaxing, like analysis. Yes. Analysis.

I feel that most pure mathematicians that I know have very little tolerance or appreciation for analysis, and I am certainly no hipster-analysis-lover. But I've been looking at Osgood, Phillips and Sarnak's paper on finding the (unique) nicest metric compatible with the complex structure of a Riemann surface \(R\). To be bluntly honest, I haven't been exposed to very much functional analysis, and the idea here is sorta cool. Let's try to really crudely summarise the schematic of what I suspect is a generic strategy in this area:

1. Take a big vector space \(W\) of functions, like a Sobolev space, and define a functional \(F:W\rightarrow\mathbb{R}\) on it. Often, the functional is measuring some sort of energy these functions defined on a Riemannian manifold.
2. Show that \(F:W\rightarrow\mathbb{R}\) is strictly convex (concave), this means that the global minimum (maximum) of \(F\) is unique.
3. Plonk \(W\) in a bigger space \(H\) - often a \(L^p\) space, something like the Rellich-Kondrachov theorem is then used to show that a sequence of functions in \(W\) whose energies tend to the infimum of \(F\) has a convergent subsequence tending to some \(\varphi\in H\).
4. Use stuff like the elliptic regularity theorem to show that \(\varphi\) is a lot smoother than your average function in \(H\) and is in fact in \(W\) and hence unique by point 2.

Well, that's sorta my take on what appears to be important. I'll probably realise at some point that I'm pretty wrong.

During the process of going through and verifying each step of this proof there were two things that I couldn't get my head around. The first I'm still paranoid about, and I'll probably ask about it on MathOverflow in a day or two. It has to do with whether elliptic regularity holds for sufficiently nice nonlinear elliptic operators. The second had to do with why a strongly convergent sequence of measurable functions in \(L^p(\Omega\subset(\mathbb{R}^n,\mathrm{d}V))\) always has a subsequence that converges pointwise amost everywhere (a.e.) to a measurable function.

Let's prove this jazz.

So we've got a sequence of measurable real functions \[f_n:\Omega\rightarrow\mathbb{R}\] in \(L^p(\Omega)\) and we want to show that there's a subsequence that converges pointwise a.e.. Let's begin by figuring out what pointwise convergence actually means.

In order for the sequence \(\{f_n\}\) to converge to some function \(f\), it needs to get arbitrarily close to \(f\) as \(n\) blows up. That is: for any \(x\in\Omega\) and any \(\epsilon>0\), \begin{align}\limsup_{n\rightarrow\infty}|f_n(x)-f(x)|\ngtr\epsilon. \end{align} And since we're dealing with a.e. pointwise convergence, let's just turn this into a measure theoretic statement: for any \(\epsilon>0\), \begin{align}\mathrm{Vol}(\{x\in\Omega:\,\limsup_{n\rightarrow\infty}|f_n(x)-f(x)|>\epsilon\})=0.\end{align}
Okay, good, we've heuristically justified why this condition is equivalent to pointwise a.e. convergence.

Now, just by interpreting what \(\limsup\) is actually doing, we see that \begin{align}\mathrm{Vol}(\{x\in\Omega:\,\limsup_{n\rightarrow\infty}|f_n(x)-f(x)|>\epsilon\})\\=\lim_{n\rightarrow\infty}\mathrm{Vol}\left(\bigcup_{k=n}^{\infty}\{x:\,|f_k(x)-f(x)|>\epsilon\}\right). \end{align} So if we can show that \begin{align}\mathrm{Vol}\left(\bigcup_{k=n}^{\infty}\{x:\,|f_k(x)-f(x)|>\epsilon\}\right)\leq\sum_{k=n}^{\infty}\mathrm{Vol}(\{x:\,|f_k(x)-f(x)|>\epsilon\})\end{align} tends to \(0\) then we're done. But of course, one way of showing that the tail of a series converges to \(0\) is to show that the series converges.

Now, if we knew that \(\mathrm{Vol}(\{x:\,|f_k(x)-f(x)|>\epsilon\})\) tended to \(0\) we could easily take a subsequence \(\{f_{n_m}\}\) so that \begin{align}\mathrm{Vol}(\{x:\,|f_{n_m}(x)-f(x)|>\epsilon\})<2^{-m}\end{align} and this subsequence would have to converge pointwise a.e. to \(f\) - which is precisely the type of conclusion that we'd like. So everything boils down to using strong convergence to get that \begin{align}\mathrm{Vol}(\{x:\,|f_k(x)-f(x)|>\epsilon\})\rightarrow0\text{ as }n\rightarrow\infty.\end{align} This, however, can be shown as follows:\begin{align}&\mathrm{Vol}(\{x:\,|f_k(x)-f(x)|>\epsilon\})=\mathrm{Vol}(\{x:\,\epsilon^{-1}|f_k(x)-f(x)|>1\})\\=&\int_{\{x:\,\epsilon^{-1}|f_k(x)-f(x)|>1\}}\mathrm{d}V\\ <&\int_{\{x:\,\epsilon^{-1}|f_k(x)-f(x)|>1\}}\epsilon^{-p}|f_k(x)-f(x)|^p\mathrm{d}V\\\leq&\int_{\Omega}\epsilon^{-p}|f_k(x)-f(x)|^p\mathrm{d}V\\=&\epsilon^{-p}\|f_n-f\|_p^p.\end{align}Since strong convergence is defined to mean that \(\|f_n-f\|_p\) tends to \(0\) and \(\epsilon\) is just some fixed constant, this proves our claim. Oh, and I should probably point out that \(\|\cdot\|_p\) is notation for the norm on \(L^p(\Omega)\).

I really ought to have finished writing this post before the match ended. Oh well. =)
 

Today I Learned: On De-Klein-ing Lie's - Part 1

Update: Part 0 Part 2. Also, a crazy thought comes to mind - has anyone ever done linear modelling (of the statistical variety) with projective geometry and other geometries? It might be worthwhile doing this in situations with physical interpretations that admit conformal inversion-type maps on variables.

Okay okay okay, ugh...it's too early in the morning for anything other than maths: let's have another look at Lie's line-sphere correspondence.

Today's menus: projectivisation (again, I probably should say projective completion, but whatevs man!).

To begin, draw a circle. Now draw a bigger one. Now draw a much much much bigger circle. You'll notice that arcs on a circles become straighter as you increase the radius of the circle. So naturally, if you draw a really...perhaps...infinitely big circle, you should probably wind up with just a straight line. This idea that lines are pretty much circles (and planes are pretty much spheres and so forth) is formalised in projective geometry.

The basic idea is to extend spaces like \(\mathbb{R}^n\) and \(\mathbb{C}^n\) to these projective spaces called \(\mathrm{RP}^n\) and \(\mathbb{CP}^n\) which are a little bit bigger - but they're only larger in the sense that they have points "at infinity".

As an illustrative example, let's consider \(\mathbb{R}^1=\mathbb{R}\) - the real numbers.

Let's regard a real number, like \(2\in\mathbb{R}\), as a ratio \(a:b\), where \(b=2a\). This may seem rather silly, but when you think about it, there's something entirely natural and primitive about this - I mean, it's a tiny bit like how we build rational numbers, which is the foundation upon which we construct the real numbers.

In this way, any real number \(r\in\mathbb{R}\) may be written as \(1:r\), which we naturally expect to be equal to \(a:ar\). So we see the emergence of the following space:\begin{align*}\mathbb{RP}^1:=\{\text{pairs of the form }[a:b]\text{ where }[a:b]=[ax:bx]\text{ if }x\neq0\\\text{and }a,b\in\mathbb{R}\text{ aren't both }0\}.\end{align*}So we've got these funny square-bracketed pairs of numbers \([a:b]\), so notated as to resemble a ratio, and an embedding map\begin{align*}\iota:\mathbb{R}\rightarrow\mathbb{RP}^1,\, r\mapsto[1:r]\end{align*}that covers almost all of \(\mathbb{RP}^1\). In fact, the only point that isn't covered is the one point where the first coordinate is \(0\) - the point \([0:1]\). Now, it shouldn't be too hard to believe that this is \(\infty\) because if \([a:b]=\frac{b}{a}\), then we should expect that \([0:1]=\frac{1}{0}=\infty\).

Let's generalise to a general projective \(n\)-space:\begin{align*}\mathbb{RP}^n:=\{[x_0:x_1:\ldots:x_n]\,|\,[x_0:x_1:\ldots:x_n]=[rx_0:rx_1:\ldots:rx_n]\text{ if }r\neq0,\\\text{ and the }x_i\in\mathbb{R}\text{ aren't all }0,\}\end{align*}naturally, the complex projective \(n\)-space \(\mathbb{CP}^n\) is defined identically - just with \(\mathbb{R}\) replaced with \(\mathbb{C}\).

In these higher dimensional projective spaces, the points at infinity are given by points of the form \([0:x_1:x_2:\ldots:x_n]\). Which, if you think about it, is a projective space of \(1\) lower dimension. That is (as sets and also, I guess, as a CW-complex):\begin{align*}\mathbb{RP}^n=\mathbb{RP}^{n-1}\cup\mathbb{RP}^{n-2}\cup\ldots\cup\mathbb{RP}^{0},\end{align*}
and similarly with \(\mathbb{CP}^n\) of course. I should probably point out at this point that this decomposition is nice enough for calculating the homology of these spaces. And now, time for something completely different.

Notice that each point \([x_0:\ldots:x_n] \in\mathbb{RP}^n\) is secretly a whole line of points in \(\mathbb{R}^{n+1}\) given by\begin{align*}\{t(x_0,\ldots,x_1)\in\mathbb{R}^{n+1}\}. \end{align*} Therefore, we can think of \(\mathbb{RP}^n\) as the space of lines going through the origin in \(\mathbb{R}^{n+1}\). In fact, since each line is orthogonal to precisely one \(n\)-dimensional subspace (or hyperplane), we could actually think of \(\mathbb{RP}^n\) as the space of hyperplanes in \(\mathbb{R}^{n+1}\) if we so wished. And this duality between lines and hyperplanes is a powerful technique in projective geometry, and I won't say too much more about it because I really ought to have breakfast.

But one important thing that I ought to say is that since invertible \((n+1)\times(n+1)\)-linear transformations take lines to lines in \(\mathbb{R}^{n+1}\), this gives us a natural action of the matrices \(\mathrm{GL}_{n+1}(\mathbb{R})\) on \(\mathbb{RP}^n\). Maybe I'll write a bit more about that, after I've had something to eat.

Or maybe not? Who knows.

Today I Learned: On De-Klein-ing Lie's - Part 0

Update: Part 1 Part 2.

Note: for AMSI peeps who are bored and need some homework, here're the slides. =)

Last Thursday, a friend of mine - Nick Sheridan gave a seminar at my maths department on homological mirror symmetry. It was a pretty sweet talk - I really ought to go through his slides again at some point and write up the big picture. It was especially sweet because it's the first time that I've helped to organise one of these "proper" departmental seminars.

To secure the usual AGT (algebra-topology-geometry) seminar room for the talk, I had to obtain the booking from the AMSI 2013 Summer School organisers. So I wandered somewhat sheepishly into Jan de Gier's office and before I know it I'm walking out of his office with the requisite room booking in one hand, and an invitation to speak at a special seminar.

This post is an expanded summary (yes, it's oxymoronic, whatevs man!) of what I talked about.

Talk title: On De-Klein-ing Lie's

Talk title justification:

A small discourse between two mathematicians: Sophus Lie and Felix Klein.
L: Hey Felix, hey man, hey, tell me my beard's awesome.
K: I de-Klein.
L: Aww man, come on...just Lie a little.

Yep, puns and pictures are all I've got to go on.

The point of the talk was to walk through something that I'd picked up fairly recently on one of my daring excursions to the university library: a tiny volume entitled "Lectures on Mathematics ~ Klein". It's basically a collection of a whole bunch of lectures that Felix Klein gave at the Congress of Mathematics held in Chicago during August 1893. There's some pretty sweet stuff here, albeit written in slightly archaic language. My talk is motivated by/very very very loosely based on Lecture II: Sophus Lie.

Actually, this post is getting longer than I expected. Maybe I'll just give an overview of what I said.

Part 1: Projectivization

I'll be honest - I probably should have said projective completion instead of projectivization. But hey, I'm not an algebraic geometer, and projectivization sounds a bit better to me than "projective completion" or the "\(\mathrm{Proj}\)" construction.

The idea is to take \(\mathbb{R}^n\) or an algebraic variety (solution set to a polynomial) in \(\mathbb{R}^n\) and to "add stuff at infinity" so that we wind up with a compact space. I sort of emphasised the notion of "adding stuff at infinity" quite a bit during my talk, although "compactification" is probably slightly more accurate.

Part 2: The Erlangen Program.

This wasn't really necessary, but I thought it a cute introduction to the Erlangen program - which was at the time an attempt to unify all of these new non-Euclidean geometries that people were discovering. I basically just pointed out that \(\mathrm{GL}_{n+1}(\mathbb{R})\) acts on the projective space \(\mathbb{RP}^n\) transitively, and that Klein's Erlangen program is all about groups acting on spaces:
- the space tells you the "elements" of your geometry;
- the group tells you the "symmetries" of your geometry.

Part 3: Plucker's Line Geometry and Lie's Sphere Geometry.

This was the actual meat of the talk (it was a very fluffy and recreational talk). I gave the defining equations in \(\mathbb{RP}^5\) for the space of lines and the space of spheres in \(\mathbb{R}^3\) (*). As well as nice characterisations of when two points in the space of lines represented intersecting lines and when two points in the space of spheres represented tangentially meeting spheres. I concluded with a nice picture of how hyperboloids of 1-sheet and Dupin's cyclides are respectively corresponding objects in Plucker's line geometry and Lie's sphere geometry.

I then shamelessly advertised this blog and went home. =P

I'll try to flesh out part 3 a bit more next time, there's some pretty nice mathematics there - albeit a lot of it is just algebraic manipulation. Maybe I'll think about things more geometrically in the future.

(*) I lied a little here too, for expositional purposes, I should really be thinking about lines/spheres in \(\mathbb{RP}^3\). It's just a bit annoying/distracting having to clarify what that means.

Today I Learned: How to Plot a Doughnut

I lied.

I actually didn't learn this today, but a fair while back. Although I did kind of forget most of it, and had to figure it out today. So maybe I didn't lie in the title, but I lied in the first paragraph of this sentence. At least I didn't create a paradox.

The aim of this post is just to describe a way of deriving an implicit polynomial formula for high genus tori, much like how: \[x^2+y^2-1=0\] is an implicit formula for the unit circle. The main idea of the construction that we're going to use was taught to me by one of my ex-students: Andrew Elvey-Price. Drew, if you're reading this: do more geometry and less combinatorics. Music is also alright by me. =P

Let me just first show you what a genus \(3\) torus looks like:

Torus just means that it's sort of like the surface of a doughnut - a round thing with holes through it, and the genus just counts how many holes it's got. I've only really bothered to play around with genus \(3\) tori (plural of torus) today, but the ideas behind how I plotted this torus should work for any number of holes.

Let's start off with the scary part - let's see the actual formula used to describe the above surface: \begin{align*} (x^2+(y-2)^2-1)((x-\sqrt{3})^2+(y+1)^2-1)((x-\sqrt{3})^2+\\(y+1)^2-1)-0.001(x^2+y^2+7z^2)^5=0 \end{align*} Well, at least we can handle the right-hand side of this equation. Let's stare a bit harder at the left-hand side. The first thing that you should notice is that the big nasty first term on the top line is a product of three things that we should understand pretty well: \begin{align*} x^2+(y-2)^2-1,\; (x-\sqrt{3})^2+(y+1)^2-1 \text{ and }(x+\sqrt{3})^2+(y+1)^2-1 \end{align*} are just formulas for unit circles, respectively centered at \((0,2), (\sqrt{3},-1)\) and \((-\sqrt{3},-1)\). And here's the key idea that Andrew taught me: most of the time, when we we look at a formula like \[x^2+(y-2)^2-1=0,\] we pretty much just pay attention to the circle. But we really should think about the value that the LHS takes over the whole \(xy\)-plane: 

1. It's \(-\)ve inside the circle and \(+\) outside the circle. 
  
This means that the product of these three terms should be:

2.  \(-\)ve inside the three circles and \(+\) outside the three circles. Oh, and I should probably point out that it takes the value of \(0\) on the actual three circles.

Now let's think about adding something like... o, I dunno, \[-0.001(x^2+y^2)^5\] to the triple product. Well, we can see that this term is going to be negative, but it's only a little bit negative around the origin \((0,0)\), and gets really negative as we head outwards from the origin. So, basically, when you add it to the product of the three circles, near the origin it'll make the positive region from this product slightly smaller (but still positive). And as you head outwards, the value of this sum will get less and less positive, until it eventually hits \(0\).

3. So, the sum of the big triple product term and this \(-0.001(x^2+y^2)^5\) term is going to be \(0\) at three circular shaped regions close to the three unit circles that I keep (somewhat awkwardly) mentioning, as well as a big roundish region outside. here's a picture of what I'm talking about:

In the above diagram, the burgundy bits are positive, and the yellowy bits are negative, and that's what you get when you add two functions.

The reason that we added the \(-0.001(x^2+y^2)^5 \) term is because it's the \(z=0\) slice of the \[-0.001(x^2+y^2+7z^2)^5\] term in the defining (implicit) function of this surface. And the reason that we paid so much attention to it is because this is a part of how mathematicians actually draw a surface (or at least how we used to do it, before awesome computer programs like Mathematica and Matlab were around): we draw the curve for \(z=0\), and then change \(z\) to some other value nearby, like \(z=0.5\) and so forth, and slowly we build a cross section of our surface. Then we mesh all of those cross-sections together to form a pretty decent guess of what the surface actually looks like. Now, as we vary \(z\) away from \(0\), we see that

\[-0.001(x^2+y^2+7z^2)^5\] becomes much much more negative. What this does when you add it to the triple product term is that:


4. It  brings in the outside big circle, and makes the internal three circles larger, until these form regions merge up to form this Y-shaped boomerang thingy.

5. If you keep taking \(z\) farther away from \(0\), you'll find that this region keeps shrinking, until it eventually disappears.

So, with all that info, you should be able to build a picture like the one that I showed you at the start. Note that I had all of these random numbers like -0.001 and 7 hangin' around - that's just to tweak the formula so that the final shape looks nicer (well, actually, that's a bit of a lie - the 0.001 is sorta necessary, but I'll let you figure out why).

Now, having done all of this, I realised that I could, instead of using \[-0.001(x^2+y^2+7z^2)^5,\] maybe use a different function to draw a slightly differently shaped torus. My first idea is to use the three-leaf-clover curve given by something like: \[r=\cos(\frac{2\pi x}{3})+\sqrt{5},\] which is written in polar-coordinates, and to convert it back into \(x\) and \(y\). Doing so gave me this (after some playing around):

which kinda looks like a holey guitar pick. The formula for this one is a bit scarier than the last guy, it's: \begin{align*} (\frac{3}{2}x^2+(y-\frac{11}{5})^2-\frac{9}{5})\cdot (\frac{\sqrt{3}}{2}(x+\frac{11\sqrt{3}}{10})+\frac{1}{2}(y+\frac{11}{10}))^2\\+\frac{3}{2}(\frac{-1}{2}(x+\frac{11\sqrt{3}}{10})+\frac{\sqrt{3}}{2}(y+\frac{11}{10}))^2-\frac{9}{5})\cdot(\frac{\sqrt{3}}{2}(\frac{11\sqrt{3}}{10}-x)+\frac{1}{2}(y+\frac{11}{10}))^2\\+\frac{3}{2}(\frac{1}{2}(x-\frac{11\sqrt{3}}{10})+\frac{\sqrt{3}}{2}(y+\frac{11}{10})) ^2-\frac{9}{5})+5(x^2+y^2)^3\\-((y^3-x^2y)-(x^2+y^2)^2)^2-(4z^2+0.1(x^2+y^2))^6=0. \end{align*} And the last guy is a minor tweak of this formula, but there's no way I'm typing it all out. It's pretty similar to the above guy, but fluffier.

So ugh, there you go kids, go nuts drawing donuts.