2010 in review

Happy New Year, everyone!

Sorry, there hasn’t been much activity on this blog over the past few months, but 2011 will be the year when you can expect a lot more stuff to be posted as I find more time to do so. Todd has been busy on other sites/blogs, especially MathOverflow and n-Category Cafe, but he is still an author/admin on this blog.

I got an email from WordPress, summarizing the level of activity on our blog for the year 2010. I thought it wouldn’t be so bad if I shared the information with you all.

2010 in review

The stats helper monkeys at WordPress.com mulled over how this blog did in 2010, and here’s a high level summary of its overall blog health:

The Blog-Health-o-Meter™ reads Wow.

Crunchy numbers

About 3 million people visit the Taj Mahal every year. This blog was viewed about 33,000 times in 2010. If it were the Taj Mahal, it would take about 4 days for that many people to see it.

In 2010, there were 2 new posts, growing the total archive of this blog to 122 posts.

The busiest day of the year was January 20th with 196 views. The most popular post that day was Continued fraction for e.

Where did they come from?

The top referring sites in 2010 were terrytao.wordpress.com, mathoverflow.net, en.wordpress.com, qchu.wordpress.com, and gilkalai.wordpress.com.

Some visitors came searching, mostly for imaginary numbers, platonic solids, euler’s formula, vertex, and challenging integrals.

Attractions in 2010

These are the posts and pages that got the most views in 2010.

1

Continued fraction for e August 2008
18 comments

2

Platonic Solids and Euler’s Formula for Polyhedra March 2008
10 comments

3

High IQ and Mathematics December 2007

4

Problem-Solving Hall of Fame! May 2008
5 comments

5

Integration Bee, Challenging Integrals January 2008
16 comments

Self-referential Paradoxes, Incompleteness and Fixed Points

Who doesn’t like self-referential paradoxes? There is something about them that appeals to all and sundry. And, there is also a certain air of mystery associated with them, but when people talk about such paradoxes in a non-technical fashion indiscriminately, especially when dealing with Gödel’s incompleteness theorem, then quite often it gets annoying!

Lawvere in ‘Diagonal Arguments and Cartesian Closed Categories‘ sought, among several things, to demystify the incompleteness theorem. To pique your interest, in a self-commentary on the above paper, he actually has quite a few harsh words, in a manner of speaking.

“The original aim of this article was to demystify the incompleteness theorem of Gödel and the truth-definition theory of Tarski by showing that both are consequences of some very simple algebra in the cartesian-closed setting. It was always hard for many to comprehend how Cantor’s mathematical theorem could be re-christened as a“paradox” by Russell and how Gödel’s theorem could be so often declared to be the most significant result of the 20th century. There was always the suspicion among scientists that such extra-mathematical publicity movements concealed an agenda for re-establishing belief as a substitute for science.”

In the aforesaid paper, Lawvere of course uses the language of category theory – the setting is that of cartesian closed categories – and therefore the technical presentation can easily get out of reach of most people’s heads – including myself. Thankfully, Noson S. Yanofsky has written a nice paper, ‘A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points’, that is a lot more accessible and fun to read as well.Yanofsky employs only the notions of sets and functions, thereby avoiding the language of category theory, to bring out and make accessible as much as possible the content of Lawvere’s paper. Cantor’s theorem, Russell’s Paradox, the non-definability of satisfiability, Tarski’s non-definability of truth and Gödel’s (first) incompleteness theorem are all shown to be paradoxical phenomena that merely result from the existence of a cartesian closed category satisfying certain conditions. The idea is to use a single formalism to describe all these diverse phenomena.

(Dang, I just found that John Baez had already blogged on this before, way back in 2006!)

‘Hooked for life’ on math

Sorry, there hasn’t been much activity on this blog lately – which is an understatement, I acknowledge! But, for now, here’s a small article by Terry Tao on CNNOpinion.

An Experiment in Cognitive Reasoning

Among several things, these days, I have been doing some (serious) reading of literature on psychology, cognitive development, learning, linguistics, philosophy and a few other subjects. Well, the ones I just named happen to be parts of interdisciplinary areas, which are precisely the ones I am interested in. Of course, on many levels those parts also have a lot to do with mathematics, especially mathematical education. Ok, that was just a little background I wanted to provide for the content of today’s post.

I need to do a small (online) experiment in order to test a hypothesis, which will be the subject of my next post. Let me not reveal too much for now. The experiment is in the form of two puzzles that I ask readers (you!) to solve. They are both “multiple choice” puzzles with exactly two correct answers to each. Please bear in mind that this is NOT an IQ test. It is also not meant to test how good you are at solving puzzles individually. I am really interested in “aggregate” results. That is, for testing my hypothesis, I am only interested in what the majority thinks are the right answers. What is more, you won’t be graded, and no one (not even me) will ever know if you got the right answers. Please submit answers to both the puzzles.

Lastly, please don’t cheat or try to look for answers offline or online. As I said, this is NOT a test!

Let us now look at the puzzles.

Puzzle 1:

There are four cards, labelled either X or Y on one side and either 3 or 7 on the other. They are laid out in a row with their top (visible) sides shown like this: X Y 3 7. A rule states: “If X is on one side then there must be a 3 on the other.” Which two cards do you need to turn over to find out if this rule is true?

1) X

2) Y

3) 3

4) 7

Puzzle 2:

As you walk into a bar, you see a large sign that reads, “To drink alcohol here you must be over 18.” There are four people in the bar. You know the ages of two of them, and can see what the other two are drinking. The situation is: Alisa is drinking beer; Dymphna is drinking Coke; Maureen is 30 years old; Lauren is 16 years old. Which two people would you need to talk to in order to check that the “over 18 rule” for drinking alcohol is being followed?

1) Alisa

2) Dymphna

3) Maureen

4) Lauren

If you think you have the answers to those puzzles, then please click here Puzzles to submit your answers. (I couldn’t use PollDaddy to embed the above puzzles in this post because I am not allowed more than 160 characters in a single question. What a pain!) So, please go ahead and click the above link to submit yours answers.

Note: I will keep this “poll” open for a week to collect as much data as possible. Thanks!

Update: It seems many readers weren’t aware of the short duration of the “poll” and that they would have very much liked to participate. So, I am extending the poll till Jan 7, 2010 for them.  (Doing so would also help me in collecting more data.)

A Math student poses questions to Ayatollah Ali Khamenei

The following piece of news, in my humble opinion, deserves more mention in the math blogosphere than it has garnered so far. At the center of the story is an Iranian student of mathematics, Mahmoud Vahidnia, who was invited to a meeting between Iran’s Supreme Leader Ayatollah Ali Khamenei and the country’s scientific elite on Oct 28, 2009. An excerpt from a Guardian report on what transpired during a (perhaps, routine) question and answer session:

“I don’t know why in this country it’s not allowed to make any kind of criticism of you,” he told Iran’s most powerful cleric, who has the final say in all state matters. “In the past three to five years that I have been reading newspapers, I have seen no criticism of you, not even by the assembly of experts [a clerical body with the theoretical power to sack the leader]. I feel that if this doesn’t happen this situation will lead to discord and grudge.”

Vahidnia, who achieved nationwide recognition two years ago by winning Iran’s annual mathematics Olympiad, made his remarks at a meeting between Khamenei and the country’s scientific elite. They came after the supreme leader asked at the end of a question-and-answer session if anyone else wanted to speak. He chose Vahidnia after seeing him being pushed down by officials when he stood to ask a question.

Referring to the post-election crackdown sanctioned by Khamenei, he asked: “Wouldn’t our system have a better chance of preserving itself if we were using more satisfactory methods and limited the use of violence only to essential circumstances?”

I discovered the above piece of news “accidentally” via the Colbert Nation.  The Associated Press also did a report. I wonder if our Iranian readers (if there is any!) could furnish more information on this.

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.