Ferdinand Georg Frobenius, new giant of the 'week'.

I cannot have enough of Grigory Perelman's picture, but people have been complaining: the meaning of 'week' is being undeservedly stretched.

The new giant, with the mandatory beard, is Ferdinand Georg Frobenius.

I stumbled upon him during week 16, more specifically, while reading about the amazing history of the Grandi series, where you will find Frobenius at the last paragraph of: http://en.wikipedia.org/wiki/History_of_Grandi's_series

Going deeper underground.

Mathematical analysis draws me in like a black hole sucking light, but everybody argues: "why the hell do you need this", help!!!

I have written about sqrt(2) more than once, and how it provided many motivations in the past.

It turns out, you can also use it to motivate interest in 'mathematical analysis'.

Take a right triangle with 2 sides of length 1, and place it on a 2D coordinate system as show in the figure. Now let us try to estimate the length of the hypotenuse using limits.

We will cut the hypotenuse into tiny segments, which is a standard practice of estimating lengths of curves, and compute the total length of the segments. If we do this we end up with the answer of 2 and not sqrt(2)! What is wrong with this?

But Jad! you say, what you just calculated is the Manhattan distance and not the length of the hypotenuse. And you would be right. But, can't we make the same claim about this not working for our summation of small rectangles for definite integrals? what exactly is the difference? and how can it be formalized? Mathematical analysis can tell you.

For more fun examples, I recommend page 3,4,5 from: http://www.math.ucla.edu/~tao/resource/general/131ah.1.03w/week1.pdf

Another topic for this post is 'telescoping series'.

For discrete integrals, our current topic in the math project, sums of series becomes very important, it is also a brain enlarging topic and a lot of fun.

One technique for summing infinite series is called 'telescoping series'.

It works on sums of series where terms cancel each other out, and what is left is a finite and easy to calculate number.

The nice thing about this for me was that it ties to the discrete math toy problem of finding the sum of i's where i goes from 1 to n.

I have given a geometric proof of this I came up with in a previous post.

One can also do it by induction.

It turns out, it is also possible using telescoping as shown in the figure.

The interesting thing is that both induction and telescoping are very indirect, in that, if you wanted to find the answer to this problem, you would need intuition first, you would get the answer and THEN try to prove it.

The more we dig into math the more we see that this is how most of the important theories get discovered. This is one of the reasons why learning about this is great for one's brain.

Usually, one tries to proceed sequentially and directly from problem to solution, and that only works for the simpler problems. After a certain level, laziness is simply not an option anymore!

Richard Bellman had the following remark once:

"Each individual problem was an exercise in ingenuity, much like plane geometry. Change one small feature, and the structure of the solution was strongly altered. There was no stability!"

Angular to linear speed

It is quite intuitive that the linear speed for a point rotating around the origin at distance R is wR if w is the angular speed.

Since we are very much concerned about proofs in our math project, here is a proof.

I found it interesting how such an intuitive equation actually passes through quite some transformations, most relevantly, it is the chain rule and the trigonometric derivatives that play a crucial role, a little bit less intuitive than one might think!

"the long and short of steering in computer games" simon l. tomlinson

http://ducati.doc.ntu.ac.uk/uksim/uksim'04/Papers/Simon%20Tomlinson-%2004-20/paper04-20%20CR.pdf

I found this very nice blog ...

the content of which I only barely understand, but that is exactly what we are working on ...

http://stochastix.wordpress.com/

I also found this nice article:

http://www.centreforthemind.com/publications/integerarithmetic.cfm

"So in conclusion, we believe that the mental apparatus to perform "lightning fast" integer arithmetic calculations such as multiplication and division resides in us all, even though it is not normally accessible. The brain appears to perform something tantamount to arithmetic calculations (or analogously equipartitioning) for some unknown aspect of mental processing. The challenge now is to unravel which aspect."

Who said that?

"Human reason, in one sphere of its cognition, is called upon to consider questions, which it cannot decline, as

they are presented by its own nature, but which it cannot answer, as they transcend every faculty of the mind.

It falls into this difficulty without any fault of its own. It begins with principles, which cannot be dispensed

with in the field of experience, and the truth and sufficiency of which are, at the same time, insured by

experience. With these principles it rises, in obedience to the laws of its own nature, to ever higher and more

remote conditions. But it quickly discovers that, in this way, its labours must remain ever incomplete,

because new questions never cease to present themselves; and thus it finds itself compelled to have recourse

to principles which transcend the region of experience, while they are regarded by common sense without

distrust. It thus falls into confusion and contradictions, from which it conjectures the presence of latent errors,

which, however, it is unable to discover, because the principles it employs, transcending the limits of

experience, cannot be tested by that criterion. The arena of these endless contests is called Metaphysic."

Bigfoot gets physical

Very busy with Killzone3, I had very little time to do some animation work,

but I still managed to add a couple of things to 'Bigfoot' in preparation for some motion retargeting experiments.

It now can analyze skeletons loaded from mocap files and split them into branches.

It can automatically assign masses to joints using a heuristic based on skeleton connectivity.

It also now contains a physics analyzer that can compute the position of the center of mass (C.O.M in video) it's velocity and acceleration for each frame, and the same for all other joints.

The results are actually pretty fun to watch, but the video came out with bad quality,

I have to adjust the resolution to fit youtube next time...

The blue trails and velocities correspond the center of mass.

The lost animation variable...

Uniqueness of inverses for Groups, by contradiction.

In mathematical groups, the uniqueness of inverses is almost a direct consequence of the definition of a Group. Yet I could not prove it in 10 minutes, was too lazy and looked it up here: http://planetmath.org/encyclopedia/UniquenessOfInverseForGroups.html.

It bothered me that I could not come up with this proof, I tried to discover why. One of the attempts I tried was proving it by contradiction which also failed, but looking at the proof, I can see I gave up too early.

After peeking, I wanted to at least try to still prove it by contradiction (unlike the proposed proof) which intuitively seemed like the way to go for me, because the proposed proof 'constructs statements from nothing', starting with an expression, expanding it for no very obvious reason at that point (but of course obvious later), then collapsing it.

It is interesting how doing it by contradiction shows a slightly clearer path through the infinite 'ocean of statements' and the infinite number of 'valid paths' between each 2 statements, because you always have the 2 sides of the inequality to visually look at.

Here is my proof by contradiction:

Given other proofs me and Tom have attempted in the last months, I am sure I would have solved it if I gave it a bit more time, but I knew it had to be short so I wanted to solve it fast, but I failed. All in all this was a good insight into my problem solving technique.

This one falls into the category 'so obvious that it blocks you'.

Differentiable is 'stronger' than continuous...

As a reference for the calculus part of our course, we are using the excellent book 'Calculus Lifesaver' from Adrian Banner. This book is accompanied by extremely useful free downloadable video lectures with very clear explanations. Sometimes, it is not as deep as we would like it to be, but there is plenty of sources to remedy that when it happens.

In section 5.2.11, one proof of 'Differentiability implies continuity' is laid down, There is a step (step 4) in the proof that involves using a not so obvious trick.

I wanted to try to prove it myself in a more straightforward manner.

Here is what I came up with: http://jadnohra.net/release/math/diff_implies_cont.pdf.

I will let Tom review it and tell me what he thinks, hopefully it convinces him :)

What is natural

At project-perelman, We have inevitably started delving into Cauchy sequences and real analysis because if you really want to believe calculus proofs and have enough genuine interest and analytical mind, you will discover very fast that there are missing foundations and hand-waving proofs all over the place if you do not go deeper. This is best expressed by Karl Hahn in his excellent website.

As the first thing in introducing calculus he says:

"

Calculus deals with properties of the real numbers. In order to understand calculus you must first understand what it is about the real numbers that separates them from other kinds of numbers we use from day to day."

As an example, my (failed) proof (http://jadnohra.net/release/math/evt.pdf) of the Extreme Value Theorem does not perfectly work because I could not prove that my induction would cover the whole space of inputs. This can only be done by digging deeper than calculus.

Discussing with Tom we agreed that this is not explained in the majority of cases because there is no real interest in Calculus, and we have many times discussed how it ends up being used as a way to mechanically solve meaningless (to the student) exercises, and that does not stop at school. In any case, for the interested, it is inevitable.

That page led me to yet another page by Eric Schechter, where I found a quote I really like:

"

There is a natural way to "add" or "multiply" two points in the Euclidean plane. By "natural" I mean that the definitions have turned out to be useful for many applications, and that the definitions are fairly simple"

It puts in words what we many times feel but cannot express, when something mathematical feels 'natural'. Worth memorizing!

To all of this, I will add this unrelated and brilliant quote that my lovely wife just sent me:

"...höre nie auf zu zweifeln. Wenn Du keine Zweifel mehr hast, dann nur , weil du auf deinem Weg stehen geblieben bist. .... Aber achte auf eines: Lass nie zu, dass Zweifel dein Handeln lähmen. Treffe auch dann immer die notwendigen Entscheidungen, wenn du nicht sicher bist, ob deine Entscheidung richtig ist. .... Paolo Coelho, Brida"

Geometric proof of sum(1 to n)

Ah, geometric proofs, so graphic, so intuitive and clear, so fitting to the way our brain works. I remember that last year I spent some time doubting Pythagoras' proof of c2 = a2 x b2, it sent me on a survey for all existing proofs, many of the more graphical ones did not 'really' convince me, specially when they involved rotating or moving shapes and then made claims about them fitting somehow, Euclid's proof on wikipedia did a better job, one of it's 'less convincing' points being the triangle area lemma. When I look at it I am pretty sure it came out of intuition (like most good proofs) and then the 'formal' proof got put into pieces after having 'devised a plan for the solution' as George Polya would put it in his classic book: HOW to solve it.

Still, it made me like geometric proofs more than I used to -- and the reason I liked algebraic ones more, in retrospect is because of the history of my Math teachers -- and so I started scribbling... I came up with a couple of tiny nice geometric proofs.

The first one is proving that and that . The key idea is (like the start of Pythagoras' theorem) is to use area when multiplying numbers by each other, and then figuring out a relationship between the resulting shapes (in this case all rectangles) and writing it down:


Another, nicer proof is the one for the sum of 1 to n being equal to n(n+1)/2 :

There are many ways to proove this one, by induction per example, or geometrically as demonstrated in one of the discrete math video lectures I am using. However, the geometric proof used there involves having to rotate shapes and comparing them, I did not really like that, so I tried to come up with a clearer proof and I found out that it is possible, I have not seen a proof that did it exactly this way, so here it is:

The idea is that we know that the square in the figure has n x n 'dots' in it, we therefore know that cutting in half by the diagonal, we have dots. This 'almost' covers the total number of dots (the answer we are looking for) and might not even be an integer.

We can see that all the last dots are cut by the diagonal in half, and those halves are all what is missing to account for the missing rest, therefore, we add them.

We have n halves since we have n rows, so adding to , we get the final answer: . We did it without having to move shapes, rotate them or compare their lengths. And that is nice!

So I tried 'Star Wars, the force unleashed II, Demo' on PS3 for half an hour.

Of course I was not being nice, did not play along and built all sorts of contraptions. But hey ... I was simply using 'the force' the way Vader taught me.

Follow the discussion here: http://forums.aigamedev.com/showthread.php?t=4516
.

Know your induction, deduction and logical implication.

Induction:

Induction in colloquial English means 'educated guess', Mathematical induction however, is a kind of deductive reasoning, unlike plain 'induction'.

Deduction:

An argument is valid if it is impossible both for its premises to be true and its conclusion to be false. An argument can be valid even though the premises are false.

Deductive arguments are generally evaluated in terms of their validity and soundness, For a deductive argument to be considered sound the argument must not only be valid, but the premises must be true as well.

Logical implication:

Many writers draw a technical distinction between the form ``p implies q " and the form ``if p then q ". In this view, writing ``p implies q " asserts the existence of a certain relation between the logical value of p and the logical value of q while writing ``if p then q " simply forms a compound sentence whose logical value is a function of the logical values of p and q . Notice that a relation is a mathematical object while a sentence, whether open or closed, is a syntactic form that exists in the domain of signs.


How young students understand this: Students' understandings of logical implication

.

sqrt(prime) is irrational proof as an excuse for latex training

Proving that the square root of a prime number is a basic discrete math exercise, here is my proof (using my first latex document ever).
Final pdf:
http://jadnohra.net/release/sqrt_prime_irrational.pdf
Source tex file:
http://jadnohra.net/release/sqrt_prime_irrational.tex

.

Integer remainder repetition

I was just trying to solve a discrete math problem, when I bumped into the following:

take 2 prime numbers A and B, when you starting taking multiples of A, the remainders of those multiples after division by B will change at every multiple, and within B repetitions, they would have produced all possible remainders, this is quite 'intuitive' if we take an example.

Let us take 11 and 7.

11 x 1 = 7 x 1 + 4

11 x 2 = 7 x 3 + 1

11 x 3 = 7 x 4 + 5

11 x 4 = 7 x 6 + 2

11 x 5 = 7 x 7 + 6

11 x 6 = 7 x 7 + 3

11 x 7 = 7 x 11 + 0

The sequence of remainder is quite interesting: 4,1,5,2,6,3,0.

I guess it is possible to derive an equation for it depending on the 2 numbers but for now let us try to prove that within 7 multiples of 11, all possible remainders are generated.

It is not very hard:

http://mathbin.net/53727

Project Perelman is 12 weeks old

Check out our latest exponential related proofs at:

https://sites.google.com/site/77neuronsprojectperelman/weeks/week-10-the-exponential-function

Spot a 'Vulgar Mechanick', how many of them do you know?

"A Vulgar Mechanick can practice what he has been taught or seen done, but if he is in error, he knows not how to find it out and correct it; . . . Whereas he that is able to reason nimbly and judiciously about figure, force, and motion, is never at rest till he gets over every rub"

Isaac Newton wrote to Nathaniel Hawes on 25 May 1694.

Free BVH viewer released.

I just released a small viewer for the Biovision BVH mocap file format.

It can be downloaded from this page: http://jadnohra.net/?page_id=58

I did not plan to write this viewer, but I suddenly found myself having all the code I need for it while writing code for my animation research projects.

The 'Bigeye' UI library

I already had developed the 'Bigeye' UI library. This was I think the 4th UI library I had ever written. For this one, I had a couple of goals in mind: Small, OpenGL based but without state management headaches, easy integration of 3D scenes using render to texture, good looking with shadows, mouse-over, gradients, ttf and svg, no complex auto-layout/resizing support, no need for editor or text definition (at least not for the first versions). It took a number of weeks for this to happen, but I am very pleased with the results.

ImageMagick

A key idea was to use the ImageMagick library which is basically, photoshop/gimp in your code.

It allowed me to create nice and detailed widgets without having to prerender them in an image editor.

Compiling and linking ImageMagick can be quite a headache, but after that is done, using it is a lot of fun. I spent quite some time reading 'how to make a nice button' tutorials and trying things out in gimp before deciding on a look, one of the main inspirations was the Zbrush user interface. Colorpic was also a useful ally in debugging the looks and colors of various widget screenshots that I wanted to reproduce.

RenderState Management

For the UI I wanted to keep things simple, but still self managing, I went for a render tree approach, with automatic dependency management which was important for the 3D scenes rendered to textures. That way, RenderToTexture widgets could simply declare their dependency on a different (3D) RenderTree than their current tree (the main UI tree), and the Renderer would automatically take care of ordering the trees. Inside a tree, parents would render before their children.

The rendering would happen in three stages, building the render tree, figuring out dependencies, and then rendering in the right order.

For render states, again a simple design with one hashed state containing all the options needed for all the UI widgets (e.g: enabling transparency, texture, etc...). Each UI element would set it's desired render state instance, and the rest would happen automatically. Of course this is not the most flexible or performant design as code needs to be added to the render state structure and it can grow big, and for options that are not in the render state (e.g: line width) care must be taken to set them every time they are needed, but for a tiny UI like this, it does the job perfectly.

Biovision .BVH file format

Of all mocap formats, .BVH is the simplest, but many free mocap resources in bvh format exist on the internet, specially the .BVH conversion of the CMU mocap database is great. I will probably add .c3d support when I feel need it.

The format is relatively well documented on the internet. The fact that it uses Euler angles is usually the biggest source of headaches as I gathered from forums. I also had to try a couple of things out before finding out what the right way is. This included looking a the blender importer source code and even having fun writing a feature-incomplete bvh exporter for blender. A precise answer to the question of how to create a rotation matrix from the angles is nowhere to be found, because of that even some bvh viewers (bioviewer) got it wrong.

BVH euler rotation order

According to this very helpful resource: http://www.cs.wisc.edu/graphics/Courses/cs-838-1999/Jeff/BVH.html

one way to build the rotation matrix is to concatenate the matrices built from each angle in the order Y,X,Z. This is not entirely correct. The order should follow the one delcared in the bvh file itself, this means that if in the bvh file you see: "CHANNELS 3 Zrotation Xrotation Yrotation"

you concatenate with the order Y,X,Z but "CHANNELS 3 Xrotation Zrotation Yrotation" would require the order: Y,Z,X.

Since most files use the Y,X,Z order this bug can easily slip by.

Some of the CMU mocap files have a different order and look wrong in the viewers that got it wrong.

Of course, as usual, care must be taken about the coordinate systems and the order of matrix multiplications. Depending on you code, this might be different.

In a previous project of mine, I had a very elaborate runtime coordinate system conversion system, but this time I kept it simple and convert everything to an OpenGL compatible system when loading.

Code Dependencies

Everybody hates dependencies, but if you want to be productive, and pick the right ones, it is not so bad. In the past I avoided them like the plague, which was very educational, but this time around I am using the glm library (basically glsl on your pc) for math, strtk for strings (a great library which makes file parsing a ride in the park), glew for OpenGl extensions (which I need for rendering to texures using FBO), OpenGLUT and finally ImageMagick. I link all of them statically except for glew for now.

Viewer 'features'

The viewer loads bvh files using drag and drop and has the usual playback controls.

It analyzes the scale of the skeleton and the bounding box of the animation space, from that it decides on the best grid size, depth planes, camera position and camera movement speeds.

I implemented a simple 'turn table' camera controller (as inspired by Blender).

I also copied the way Blender renders Skeletons, without lighting for now.

If you download it and like it, let me know.

If you have any feature requests, let me know as well...

Stanford bunny released.

I was cleaning up my hard disk at home and I found the 'packet ray tracing project that was supposed to become the base of a photon mapper' I posted about in the past:

1. http://jadnohra-tech.blogspot.com/2008_09_01_archive.html#1603298383616017587
2. http://jadnohra-tech.blogspot.com/2008_10_01_archive.html#7537941235422943422
3. http://jadnohra-tech.blogspot.com/2008_10_01_archive.html#1222221128104057181
4. http://jadnohra-tech.blogspot.com/2008_10_01_archive.html#8986353999879708385
5. http://jadnohra-tech.blogspot.com/2008_10_01_archive.html#8721967187970184236
6. http://jadnohra-tech.blogspot.com/2008_10_01_archive.html#472543603436067225
7. http://jadnohra-tech.blogspot.com/2008_10_01_archive.html#1172483216700342377

Since I will have no time to take this anywhere anytime soon, I thought it might be a good idea to simply release the source code instead of backing it up into the dark corners of the web and a backup DVD.

The last version I am releasing dropped support for all primitives (e.g: spheres, quadrics) except for triangles and concentrated on triangles with SSE Packet tracing, BVH, and multi-core using OpenMP.

OpenMP is disabled in the delivered executable because my Visual Studio at home is the Express Edition and it does not include OpenMP.

SSE Packet tracing is also disabled because it does not support Lambert shading (I do not remember why though ... it's been a long time).

This means you will not see the 1 millions rays per sec I claim in one of the posts.

There is a number of build configurations and preprocessor options to play around with to enable / disable these options and other features.

In the executable, you can use numeric pad keys to rotate the camera and arrow keys to move the camera, when you do this, the program enters a low detail rendering mode until you release the keys. It is not great, but at least some kind of camera control is there.

The code depends on the 'WitchEngine' library (namespace 'WE' in code) which is the engine I had written for 'World of Football', but that is a LOT of code, so I spent 10 minutes only copying the code needed. It should therefore build with no problems, all you need is to point it to a DX9 SDK.

The download URL is: http://jadnohra.net/release/JadNohra_DistribPacketRaytracer.7z

AIGameDev Paris 2010, for the record.

Animation and math, starting 3000 BC.

http://sites.google.com/site/77neuronsprojectperelman/jad/animation-math

.

Homegrown math study group.

Tom Lahore and me, and I am sure many others, find that there are not enough practical problems forcing us non-PhD / non-academic to delve into math as much as we like. It is a chicken and egg problem and we have strongly felt during the last years that we should do something about it and never had the discipline to do it consistently and therefore usefully. We will give this another shot at http://sites.google.com/site/77neuronsprojectperelman/

We will start by using the Khan academy videos (1 to 2 videos per week) and discuss them during sundays possibly using some online conference tool and use the wiki to share our thoughts. The Site is public so feel free to do it with us. Will we fail and stop in a month? I don't know ... we hope the fact that we do it in a group and that we use very low commitment (1 to 2 videos per week) will help.

That's what happens when you are researching human locomotion.

You find sentences like:

"Modern humans exhibit a much higher body fat content and reduced relative muscle mass than their ancestral counterparts, trends that are seen in domesticated animals generally (Allen and Mackey, 1982; O’Dea, 1991; Clutton-Brock, 1999)." (http://jeb.biologists.org/cgi/content/full/204/18/3235)

.

More time = shorter letter

Yet another extremely valuable addition to my neuronal network. (Thanks to R.M)

http://dangerousintersection.org/2006/04/12/more-time-shorter-letter/

How true!

Anything must be something, except for nothing ...

We all have encountered and enjoyed seemingly mind convoluting statements like:
"This statement is false" or "I am a liar", such statements are basically 'unprovable'.

I have been reading about this while investigating logic and it's roots, mathematics, number theory, Goedel .... Some older posts are related to this.

Recently I decided to write down one such sentence that comes pretty naturally whenever you start thinking about what 'something' is.

Here is the complete sentence:
"Anything (any 'thing') must be 'something', except for nothing, which is of course also 'something', but on a different level of thingness, which goes up and down into itself to infinity."

The sentence flows pretty naturally when you are making it up, you start with:
"Anything must be something"
But then your mind remembers that there is an exception to that so you add:
"Except for nothing"
Again your mind jumps in, it cannot accept the void, this 'nothing' also fits the mind's intuitive notion of 'something', in the end, we just mentioned it, so it must be something, and this is where the fun starts, so you add:
"Nothing is also some kind of 'something'"
But then you fell uncomfortable, now nothing is nothing and something at the same time, but let's simply go on trying to explain how we feel about that:
"But on a different level of thingness"
The mind is trying to say that this nothing on one level (of 'thingness') is 'something', yes, but not on that same level), but now we have two levels, we needed those to resolve the paradox of nothing, but that's a problem, because on that new level we can probably do the same, and we can also think that the lower level is an upper level for some other level which has a 'nothing'. So we add:
"which goes up and down into itself to infinity."

So here we have it, nothing, something, a paradox and infinity all at the same time, plus the inability to make logical sense out of even the simplest everyday construct.

If you have been reading some Set theory, Number theory, Russel, Hilbert, Whitehead, Turing and friends all this would seem all too familiar: nothing could be the more formal 'Empty Set {}' ... and it's a long ride after that. So this is my layman's version of what all these geniuses and many others spent years thinking about, if that makes you interested, I suggest you read the most excellent book: "Godel, Escher, Bach: An Eternal Golden Braid"

I also found it interesting that this multi-level hierarchy of rules that we make up to reflect on a lower system from a higher system (escaping to the meta level as some colleagues would say) is inherent in the way we think, it is even mentioned in a seemingly unrelated game design book "Theory of Fun" and also a recurrent topic in our AI related discussions.

Next I will be investigating in more detailed the 'Completeness' part of this whole topic coming from Goedel's famous "Incompleteness theorem" that seems to be touching the physical limits of our brain and melting them in the core. More specifically completeness relative to what? Logic itself? probably, but, but ....

.