The Character of Physical Law

There is quite a buzz on the physics (and also math) blogospheres over the release of seven videotaped lectures, which were delivered by Richard P. Feynman as part of Cornell University’s Messenger Lecture Series of November 1964. The videos have been released by Microsoft Research with quite a few enhancements, though, I believe, they have been around on YouTube for quite some time.

I watched the first two video lectures, titled ‘Lecture 1: The Law of Gravitation – An Example of Physical Law‘ and ‘Lecture 2: The Relation of Mathematics and Physics‘. It goes without saying that they are spell-binding and brilliant! Of course, the textbook ‘The Feymnan Lectures on Physics‘ (which was followed later by a problem-solving supplement that I highly recommend) is such a joy to read, but if you wish to learn physics “face to face” from the master, then I exhort, nay implore, you to watch those video lectures.

(I came to know about the existence of the videos released by the Microsoft Research group from Terence Tao.)

A relation is an equivalence iff it is reflexive and euclidean

High-school students and undergraduates are (almost) always taught the following definition of an equivalence relation.

A binary relation on a set is an equivalence iff it satisfies

• the reflexive property: for all  in , ,
• the symmetric property: for all in , if , then , and
• the transitive property: for all in , if and , then .

However, there is another formulation of an equivalence relation that one usually doesn’t hear about, as far as I know. And, it is the following one.

A binary relation on a set is an equivalence iff it satisfies

• the reflexive property: for all  in , , and
• the euclidean property: for all in , if and , then .

Exercise:  Show that a binary relation on a set is reflexive, symmetric and transitive iff it is reflexive and euclidean.

The 54th Carnival of Mathematics

Welcome to the 54th Carnival of Mathematics, and Happy Fourth of July to our American readers! Indeed, the carnival should have been hosted yesterday, and I apologize for being a day late.

Trivia: Today, we have the 234th Independence Day celebrations in the  US, and ours is the 54th carnival. 2+3+4 = 5+4, see? Boy, do I feel so clever!

Ok, let’s begin, now!

We start off with a post, submitted by Shai Deshe, that presents a collection of YouTube videos explaining different kinds of infinities in set theory, causality vs conditionality in probability and some topology. The videos are the kind of ones that “math people” could use to explain a few mathematical concepts to their friends, family members and colleagues who may not be enamored of math very much but may still possess a lingering interest in it.

Experimental philosophy, according to the Experimental Philosophy Society, “involves the collection of empirical data to shed light on philosophical issues“. As such, a careful quantitative analyses of results of experiments are used to shed light on many philosophical issues/debates. Anthony Chemero wrote a post titled, ‘What Situationist Experiments Show‘, that links to a paper with the same title that he coauthored with John Campbell and Sarah Meerschaert. In the paper, the authors, through quantitative analyses of actual experimental data, argue that virtue ethics has not lost to the siuationist side, whose critiques of virtue theory are far from convincing.

Next, I would like to bring the readers’ attention to two math blogs that came into existence somewhat recently and which I think have a lot of really good mathematical content. They are Annoying Precision and A Portion of the Book. In my opinion, their blog posts contain a wealth of mathematical knowledge, especially for undergraduates (and graduate students too!), who, if inclined toward problem-solving, will enjoy the posts even more. Go ahead and dive into them!

At Annoying Precision, a project aimed at the “Generally Interested Lay Audience” that Qiaochu Yuan started aims “to build up to a discussion of the Polya enumeration theorem without assuming any prerequisites other than a passing familiarity with group theory.” It begins with GILA I: Group Actions and Equivalence Relations, the last post of the series being GILA VI: The cycle index polynomials of the symmetric groups.

Usually, undergrads hardly think integrals have much to do with combinatorics. At A Portion of the Book, Masoud Zargar has a very nice post that deals with the intersection of Integrals, Combinatorics and Geometry.

Tom Escent submitted a link to an article titled, “Introduction to Nerds on Wall Street“, which actually provides a very small snapshot of the book named, Nerds on Wall Street: Math, Machines and Wired Markets whose author is David J. Leinweber. I haven’t read the book yet, but based on generally good reviews, it seems like it chronicles the contribution of Quant guys to Wall Street over the past several decades. Should be interesting to Math and CS majors, I think.

Let’s have a post on philosophy and logic, shall we? At Skeptic’s Play, there is a discussion on Gödel’s modal ontological argument regarding the possibility of existence of God. As someone who has just begun a self-study of modal logic, I will recommend Brian K. Chellas’ excellent introduction to the subject, titled Modal Logic: An Introduction.

Then, there is the Daily Integral, a blog dealing with solving elementary integrals and which I think may be particularly useful for high-school students.

Let me close this carnival by asking the reader, “What do you think is the world’s oldest mathematical artifact?” There are several candidates, and according to The Number Warrior, candidate #1 is The Lebombo Bone, found in the Lebombo Mountains of South Africa and Swaziland, that dates back to 35,000 BC!

That’s all for now! Thanks to everyone who made submissons.

Number of idempotent endofunctions

Last summer, Todd and I discussed a problem and its solution, and I had wondered if it was fit enough to be in the POW-series (on this blog) when he mentioned that the problem might be somewhat too easy for that purpose. Of course, I immediately saw that he was right. But, a few days back, I thought it wouldn’t be bad if we shared this cute problem and its solution over here, the motivation being that some of our readers may perhaps gain something out of it. What is more, an analysis of an egf solution to the problem lends itself naturally to a discussion of combinatorial species. Todd will talk more about it in the second half of this post. Anyway, let’s begin.

PROBLEM: Suppose , where is a positive natural number. Find the number of endofunctions satisfying the idempotent property, i.e. .

It turns out that finding a solution to the above problem is equivalent to counting the number of forests with nodes and height at most , which I found here (click only if you wish to see the answer!) at the Online Encyclopedia of Integer Sequences. If you haven’t clicked on that link yet and wish to solve the problem on your own, then please stop reading beyond this point.

SOLUTION: There are two small (and related) observations that need to be made. And, both are easy ones.

Lemma 1: has at least one fixed point.

Proof: Pick any and let , where . Then, using the idempotent property, we have , which implies . Therefore, is a fixed point, and this proves our lemma.

Lemma 2: The elements in that are not fixed points are mapped to fixed points of .

Proof: Suppose is not a fixed point such that .  Then, using the idempotent property again, we immediately have , which implies , thereby establishing the fact that itself is a fixed point. Hence, (which is not a fixed point) is mapped to some fixed point of .

In both the lemmas above, the idempotent property “forces” everything.

Now, the solution is right before our eyes! Suppose has fixed points. Then there are ways of choosing them. And, each of the remaining elements of  that are not fixed points are to be mapped to any one of the fixed points. And, there are a total of ways of doing that. So, summing over all , our final answer is .

Exponential Generating Function and Introduction to Species

Hi; Todd here. Vishal asked whether I would discuss this problem from the point of view of exponential generating functions (or egf’s), and also from a categorical point of view, using the concept of species of structure, which gives the basis for a categorical or structural approach to generatingfunctionology.

I’ll probably need to write a new post of my own to do any sort of justice to these topics, but maybe I can whet the reader’s appetite by talking a little about the underlying philosophy, followed by a quick but possibly cryptic wrap-up which I could come back to later for illustrative purposes.

Enumerative combinatorics studies the problem of counting the number of combinatorial structures of some type on an -element set, such as the number of idempotent functions on that set, or the number of equivalence relations, and so on. A powerful idea in enumerative combinatorics is the idea of a generating function, where we study the series by rolling them into a single analytic function, such as

(this the so-called “exponential” generating function of ). In many cases of interest, the function will be recognizable in terms of operations familiar from calculus (addition, multiplication, differentiation, composition, etc.), and this can then be used to extract information about the series , such as explicit formulas, asymptotics, and so on. If you’ve never seen this idea in action, you should definitely take a look at Wilf’s book generatingfunctionology, or at the book Concrete Mathematics by Graham, Knuth and Patashnik.

Each of the basic operations one performs on analytic functions (addition, multiplication, composition, etc.) will, it turns out, correspond to some set-theoretic operation directly at the level of combinatorial structures, and one of the trade secrets of generating function technology is to have very clear pictures of the combinatorial structures being counted, and how these pictures are built up using these basic structural operations.

In fact, why don’t we start right now, and figure out what some of these structural operations would be? In other words, let’s ask ourselves: if and are generating functions for counting combinatorial structures of type (or species) and , then what types of structures would the function “count”?  How about ? Composition ?

The case of is easy: writing

and thinking of as counting structures of type on an -element set, and as counting structures of type , the quantity counts elements in the disjoint union of the sets of -structures and -structures.

In the categorical approach we will discuss later, we actually think of structure types (or species of structure) as functors, which take an -element set to the set of structures of type on . Here, we have to be a little bit careful about what categories we’re talking about, but the general idea is that if we have a bijection from one -element set to another, then it should always be possible to “transport” -structures on to -structures on , simply by relabeling points along the bijection . So, let us define a species to be a functor

where is the category of finite sets and bijections (not all functions, just bijections!), and is the category of sets. In enumerative combinatorics, the set is normally assumed to be finite, but in other applications of the notion of species, we actually allow a lot more latitude, and allow the functor to map into other categories , not just (“-valued species”). But if we stick for now just to set-valued species , , then we define the species by the functorial formula

where denotes disjoint union. So addition of generating functions will correspond to the concrete operation of taking disjoint unions of sets of combinatorial species.

More interesting is the case of multiplication. Let’s calculate the product of two egf’s:

The question is: what type of structure does the expression “count”? Look at the individual terms: the binomial coefficient describes the number of ways of decomposing an -element set into two disjoint subsets, one with elements and the other with , where and add to . Then, is the number of ways of putting an -structure on the -element part, and is the number of -structures on the -element part.

This suggests a new operation on structure types: given structure types or species , we define a new species according to the formula

(that is, a structure of type on a set is an ordered pair, consisting of an -structure on a subset of and a -structure on its complement). This functorial operation is usually called the “convolution product” of the combinatorial species : it is the concrete set-theoretic operation which corresponds to multiplication of generating functions.

Finally, let’s look at composition . Here we make the technical assumption that (no -structures on the empty set!), so that we won’t have divergence issues blowing up in our faces: we want to remain safely within the realm of finitary structures. Okay, then, what type of combinatorial structure does this egf count?

Perhaps not surprisingly, this is rather more challenging than the previous two examples. In analytic function language, we are trying here to give a meaning to the Taylor coefficients of a composite function in terms of the Taylor coefficients of the original functions — for this, there is a famous formula attributed to Faà di Bruno, which we then want to interpret combinatorially. If you don’t already know this but want to think about this on your own, then stop reading! But I’ll just give away the answer, and say no more for now about where it comes from, although there’s a good chance you can figure it out just by staring at it for a while, possibly with paper and pen in hand.

Definition: Let be species (functors from finite sets and bijections to finite sets), and assume . The substitution product is defined by the formula

This clearly requires some explanation. The sum here denotes disjoint union, and denotes the set of equivalence relations on the finite set . So here is an equivalence relation, which partitions into nonempty sets (-equivalence classes). And the quotient denotes the set of such equivalence classes (so we think of each class as a point of ). What this formula says is that a structure of type on consists of a partition of into a bunch of non-empty blobs, a -structure on each blob, and then an -structure on the set of blobs.

It’s high time for an example! So let’s look at Vishal’s problem, and see if we can picture it in terms of these operations. We’re going to need some basic functions (or functors!) to apply these operations to, and out of thin air I’ll pluck the two basic ones we’ll need:

The first is the generating function for the series . So for the species , there’s just one structure of type for each set (in categorical language, the functor is the terminal functor). We can just think of that structure as the set itself, if we like, with no other structure appended thereon.

For , we have unless , where . So is the species for the one-element set structure (meaning that unless has cardinality 1, in which case ).

Okay, on to Vishal’s example. He was counting the number of idempotent functions , and now, as promised, I want to determine the corresponding egf. You might be able to find it by looking at his formula, but obviously I want to use the ideas I’ve developed thus far, which focuses much more on the pictures. So, let’s picture , first as Vishal did, by thinking of the elements of as ‘nodes’, and then drawing a directed edge from node to node if . (Then, by idempotence of , will be a fixed point of . Let’s agree not to bother drawing an edge from to itself, if is already a fixed point.)

In this picture, we get a directed graph which consists of a disjoint union of “sprouts”: little bushes, each rooted at a fixed point of , whose only other nodes are “leaves” joined to the root by an edge. We can simplify the picture a little: if you put a circle around each sprout, you don’t need the edges at all: just mark one of the points inside as the root, and you know what to do.

So we arrive at a picture of an idempotent function on : a partition of into a collection of (nonempty) blobs, and inside each blob, one of the points is marked “root”. In terms of our operations, what does it mean to mark a point in a blob? It just means: break the blob into two pieces, where one piece is given the structure of “one-element set”, and the other piece is just itself. In terms of the ideas developed above, this means each blob carries a structure; we’ll suggestively write this structure type as .

In this picture of idempotent , there is no extra combinatorial structure imposed on the set of blobs, beyond the set itself. In other words, in this picture, the set of blobs carries merely an “-structure”, nothing more.

So, putting all this together, we picture an idempotent function on as a partition or equivalence relation on , together with an assignment of a marked point in each equivalence class. In the language of species operations, we may therefore identify the structure type of idempotent functions with

or more suggestively, . The exponential generating function is, of course, !

In summary, the theory of species is a functorial calculus which projects onto its better-known “shadow”, the functional calculus of generating functions. That is to say, we lift operations on enumeration sequences , as embodied in their generating functions, directly up to the level of the sets we’re counting, where the functorial operations become both richer and more concrete. The functorial analogue of the generating function itself is called the “analytic functor” attached to the species (the species itself being the concrete embodiment of the enumeration).

Much more could be said, of course. Instead, here’s a little exercise which can be solved by working through the ideas presented here: write down the egf for the number of ways a group of people can be split into pairs, and give an explicit formula for this number. Those of you who have studied quantum field theory may recognize this already (and certainly the egf is very suggestive!) ; in that case, you might find interesting the paper by Baez and Dolan, From Finite Sets to Feynman Diagrams, where the functorial point of view is used to shed light on, e.g., creation and annihilation operators in terms of simple combinatorial operations.

The literature on species (in all its guises) is enormous, but I’d strongly recommend reading the original paper on the subject:

• André Joyal, Une théorie combinatoire des séries formelles, Adv. Math. 42 (1981), 1-82.

which I’ve actually referred to before, in connection with a POW whose solution involves counting tree structures. Joyal could be considered to be a founding father of what I would call the “Montreal school of combinatorics”, of which a fine representative text would be

• F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-like Structures, Encyclopedia of Mathematics and its Applications 67, 1998.

More to come, I hope!

A Mathematical Chess (Dissection) Paradox

I thought I would share with our chess-loving readers the following interesting (and somewhat well-known) mathematical chess paradox , apparently proving that , and the accompanying explanation offered by Prof. Christian Hesse, University of Stuttgart (Germany).  It shows a curious connection between the well-known Cassini’s identity (related to Fibonacci numbers) and the chessboard ( being a Fibonacci number!). The connection can be exploited further to come up with similar paradoxes wherein any -square can always be “rerranged” to form a -rectangle such that the difference between their areas is either or . Of course, for the curious reader there are plenty of such dissection problems listed in Prof David Eppstein’s Dissection page.

Happy Co-Valentine’s Day!

Love is like PI – natural, irrational and very important!
- Lisa Hoffman

Happy Co-Valentine's Day

Valentine’s Day is usually associated with romantic love, but I think such an idea although wonderful is somewhat restrictive. This time of the year, I believe, is also about letting people close and dear to you know how much you love and care about them! Keeping that in mind, I wish my parents a Happy Valentine’s Day and hope that my younger brother, Vishant, has a great Valentine’s Day too!

I also sincerely hope that Todd gets to spend a great Valentine weekend with his wife and family! And, here’s hoping that all our readers and my friends (including Aditya, Pawan and Kenji!) will today not hesitate in expressing their love to their near and dear ones.

And very importantly, here’s wishing Carolyn an unforgettable Valentine’s Day! Thanks for being my Valentine even though you are thousands of miles away!!

[I do hope Todd will forgive me for posting something completely non-mathematical. In my defense, this post has at least a reference to PI and category theory! ]

Using Mathematical Induction to “disprove” the foundation of Calculus!

Or, at least, that’s what this blog post at Science and Math Defeated aims to do. Normally, I avoid writing on such a topic but I think the following example could be instructive to a few people, at least, in learning how not to infer from mathematical induction. The author of that blog post sets to “disprove” the foundation of Calculus by showing that the “assumption” leads to a contradiction (which I am sure most of you have seen before.) And this is supposed to be achieved  through the use of Mathematical Induction.

Let be the statement for all  and .

Claim:  is true for all .

Proof: , and so,  is true. This takes care of the base case. Now assume  is true for some , where . Now, it is easy to show that  is true as well (I just skipped some details!). Hence,  holds. This takes care of the induction step. (Note that is shown to be true independent of !) And, this proves our claim.

(Erroneous) Conclusion: Hence, .

Notwithstanding the inductive proof (which is correct) above, why is the above conclusion wrong?

Ans. Because “infinity” is not a member of .

(Watch out for Todd’s next post in the ETCS series!)

Link to 43rd Carnival of Mathematics

I would like to quickly point out to our readers that Jason Dyer is currently hosting the 43rd Carnival of Mathematics and that the Carnival lists Todd’s POW-11 (Preserving Sums of Squares) post as one of its entries!

A note on a simple polynomial-logarithmic algebraic identity

The following “polynomial-logarithmic” algebraic identity that one encounters on many occasions turns out to have a rather useful set of applications! 

POLYNOMIAL-LOGARITHMIC IDENTITY: If is a polynomial of degree  with roots , then .

PROOF: This one is left as a simple exercise. (Hint: Logarithms!)

A nice application of the above identity is found in one of the exercises from the chapter titled Analysis (p120) in Proofs from the Book by Aigner, Ziegler and Hofmann. 

EXERCISE: Let be a non-constant polynomial with only real zeros. Show that for all .

SOLUTION: If is a zero of , then the right hand side of the above inequality equals zero, and we are done. So, suppose  is not a root of . Then, differentiating the above identity w.r.t. , we obtain , and we are done.

It turns out that the above identity can also used to prove the well-known Gauss-Lucas theorem.

GAUSS-LUCAS: If is a non-constant polynomial, then the zeros of lie in the convex hull of the roots of .

PROOF: See this. 

HISTORY: The well-known Russian author V.V. Prasolov in his book Polynomials offers a brief and interesting historical background of the theorem, in which he points out that Gauss’ original proof (in 1836) of a variant of the theorem was motivated by physical concepts, and it was only in 1874 that F. Lucas, a French Engineer, formulated and proved the above theorem. (Note that the Gauss-Lucas theorem can also be thought of as some sort of a generalization (at least, in spirit!) of Rolle’s theorem.)

Even though I knew the aforesaid identity before, it was once again brought to my attention through a nice (and elementary) article, titled On an Algebraic Identity by Roberto Bosch Cabrera, available at Mathematical Reflections. In particular, Cabrera offers a simple solution, based on an application of the given identity, to the following problem (posed in the 2006 4th issue of Mathematical Reflections), the solution to which had either escaped regular problem solvers or required knowledge of some tedious (albeit elementary) technique. 

PROBLEM: Evaluate the sum . (proposed by Dorin Andrica and Mihai Piticari.)

SOLUTION: (Read Cabrera’s article.)

There is yet another problem which has a nice solution based again on our beloved identity!

PROBLEM: (Putnam A3/2005) Let be a polynomial of degree , all of whose zeros have absolute value 1 in the complex plane. Put . Show that all zeros of  have absolute value 1.

SOLUTION: (Again, read Cabrera’s article.)

World Chess Championship 2008!

Perhaps most people are preoccupied with the global financial crisis right now, especially with people in the US much more focused on the upcoming US presidential election in November. So, for those who haven’t been following the news in chess closely I would like to bring their kind attention to the current World Chess Championship (2008) match (Bonn, Germany) between two supreme chess grandmasters, Vishwanathan Anand (India) and Vladimir Kramnik (Russia). Technically, Anand (pronounced Aa-nand and not A-naand; well, actually it is more like Aa-nundh) is the current world chess champion, but personally I think that his winning the World Chess Championship Mexico (2007) last year was a somewhat “unsatisfactory” accomplishment, if you will, given that he won the crown by winning a tournament and not a “classical” chess match. I fervently believe that a person should be crowned world chess champion (like Fischer, Kasparov, Capablanca, Kramnik, to name a few) only after he or she has won a “proper” world championship match played under “classical time controls” (remember the  Fischer-Spassky match in 1972 and the Kasparov-Kramnik match in 2000?)  Without that, the gravitas of the chess crown is somewhat diminished. 

So, here is Anand’s chance now to silence his critics, of which there are very few really, once and for all that he is indeed the undisputed world chess champion! And judging by the result of the third game, which he just won in a dramatic fashion (woohoo!), as well as the tremendous amount of home preparation it clearly seems he has done, there is no doubt that he is on a steady path to the crown. In all the first three games, Anand has demonstrated thus far that he is the superior player. Of course, there are nine more games left and the bets are not off by any means. After all, it was Kramnik who beat Kasparov convincingly in 2000 to win the crown. 

For analyses of the first two games, click here and here. 

Ok, so here is a poll that I invite our readers to participate in. (Obviously, if you choose the “wrong” answer, all your future comments on this blog will be deleted! So, think hard before you vote.)