You are currently browsing the category archive for the 'Mathematics' category.
Todays IPG seminar had Fritz Eisenbrand (the Disctete Opt chair, Math department EPFL) talking about Diameter of Polyhedra:Limits of Abstraction. I don’t think I followed the topic too well, but this is a share of what I understood.
The topic is about a convex geometric problem on the diameter of a polyhedra. The question of whether the diameter of a polyhedron is polynomial or not seemed to be a longstanding open problem. The largest diameter of a
dimensional polyhedron with
facets has known upper and lower bounds.
.
The lower bound is due to Klee and Walkup and upper bound to Kalai and Kleitman. These bounds also hold good for combinatorial abstractions of the 1-skeleton of non-degenerate polyhedra (Polyhedron here is called non-degenrate). What Fritz and his colleagues have done is to look into the gap between these known lower and upper bounds. Apparently, the gap is wide and they have made some progress to get a super linear lower bound if
is allowed to grow with
.
The way they showed this bound is by establishing the bound for the largest diemeter of a graph in a base abstraction family. Let us say, the abstraction family of connected graphs be denoted by .The largest diameter of a graph in
is denoted by
. They find that,
and then using the fact that
, they conclude the bound
I have not had a chance to see their paper yet. I must say, the proof was not all that within my grab during the talk. However it appeared that it is based on some layering and combinatorics. He said some applications to covering problem, in particular disjoint covering design which I didn’t follow that well. Sometimes I get the feeling that I am a little dumb to grasp these ideas during a talk. I wonder whether others understand it very well on a first shot presentation. I have put it in my agenda (among the millions of other papers to read) to see through this problem and proof, one day! His presentation was very clear and legible though.
Today, during the evening chat, Emmanuel Abbe threw an interesting question: Whether the sum of square roots of consecutive binomial coefficients converge to some closed form! That is, . We tried a few known combinatorics tweak, but no meaningful solution arrived. We were also wondering whether this has some asymptotic limit, but that too did not yield anything. A quick check on Mathematica wasn’t helpful either. Now the question is: Does this sum yield some closed form expression.
While playing with this sum in Mathematica, I found that for the sum of squares of binomial coefficients, there is a nice simple closed form.
I was toying with a proof. It turns out that, the proof is extremely simple and is a one line tweak of the Vandermonde identity . Simply substitute
and we have the results on table. The natural question then would be: Is there a generalization for
for any
. Ofcourse now for
it is trivial.
Apparently, it turns out that, there is no closed form expression for a general (all) . There are some interesting divisibility properties of these sums. An interesting account of that is addressed by Neil Calkin (Factors of sums of powers of binomial coefficients).
At the moment, I get a feeling that sum of fractional powers of binomial coefficients is not trivial. May be there is no closed form. May be not!
I’ve finished reading the memoirs of Walter Rudin. It was a quick read for a few hours. His autobiography is titled The way I remember it, published by AMS in the history of mathematics series. It wasn’t particularly interesting, to say the least. From a mathematician who wrote excellent books on functional analysis and several others, I was expecting a much better story. Of course one cant write an imaginary story in an autobiography, but then the incidents in his life is pretty much the story of any European intellectual during the war days. The best I liked is the one from Karl Popper. However, I could connect many incidents from Rudin’s life, primarily because of the geography. There is a chapter on his days in Switzerland, which also touched upon Lausanne. That part for once enthused me! Was wondering how Lausanne would have been 70 years ago! If you are completely unaware of the life in Europe around the WW period, then this will give you a perspective. Like many scientific minds of that era, he had a long route to the United States. He discusses the path and family traits of that journey, in a somehat uncomplicated language.
In his autobiography, Rudin has discussed some of his contributions to mathematics as well. That part appeared a little informative, but technical read. If you know his work already, you would connect it nicely. I particularly liked the chapter on Function Theory in the Unit Ball of Cn.
In all, not a book I would recommend, unless you are a Walter Rudin fan and knows his contributions in much more detail. However, this may be a motivating read for a young school kid aspiring to be a mathematician. Why did I say that? I don’t know! Don’t ask me why either!
An interesting bound (problem from Rudi’s Modern coding theory book) regarding the chromatic number of a random graph. I first attempted it during the course. Here is the problem statement:
C.5 (Concentration of the Chromatic Number – Spencer and Shamir). Consider a graph on
vertices. The chromatic number of a graph
, denoted by
, is the smallest number of colors needed to color all vertices so that no two vertices which are joined by an edge have the same color. Consider the standard ensemble of random graphs on
vertices with parameter
: to sample from this ensemble, pick
vertices and connect each of the
ordered pairs of vertices independently from all other connections with probability
. Show that for this ensemble
.
My solution is as folllows: (PDF typeset as single file is available here. Look for problem 3)
Let is a random graph with
vertices. If
is the probability that a given edge is in
. The probability space be
. Let
be a filter on the set of all such random graphs. We can define a Martingale as follows:
where
and is the Chromatic number of
. Chromatic number changes at most by one , when the information about the new edge comes in. Clearly,
satisfies the conditions for Azuma’s inequality.
is a Martingale, with ). Let
. Clearly
Now we can use the Azuma’s inequality on to get,
.
Since , the result
follows.
Here is an interesting riddle on random matrices.
(Rank of Random Binary Matrix). Let denote the number of binary matrices of dimension
and rank
, so that by symmetry
. This is a repost of the solution that I have arrived at (certainly not the first!) and submitted as part of a homework (9) problem from the doctoral course Modern coding theory (by Rudiger Urbanke) at EPFL. The sumbitted solution in PDF is available here.
Rank of a matrix is essentially the number of nonzero rows when the matrix
is expressed in echelon form. So, we just need to compute the ways these matrices can be created with
non zero rows. Since the elements of the matrix are binary (from
), we can simply do a counting.
It is trivial to compute for
and
. For
, only all zero matrix possible, and only one such matrix exist. Hence
. For
, since
, no matrix exist, which means
.
Now we consider . How many ways? We have
non zero rows of the
matrix, which means all rows must be nonzero. Without loss of generality, for counting, we could assume that, the rows are ordered. The last row (
row can be be done in
, since there anything other than all
vector (of size
) is allowed. On
-th row, anything other than that of row
is allowed. There are
ways here.
-th row can have anything except any linear combination of the rows
and
. This is nothing but
. Row
then have
and so on. In all, Following the same procedure, we can have a total of
ways. For , we can construct a rank
matrix of size
in any of the following ways:
- Take a rank
matrix of size
and add an independent row.
- Take a rank
matrix of size
and add a dependent row.
For every matrix,
and hence,
ways. (Essentially avoid all possible linear combinations of existing rows). Using the second (item 2 above) method, we can have
and
different ways a rank matrix can be formed. Where,the first term (
) is when the all zero row is picked as the new row. In
ways we can pick any one of the exisiting row as a dependent (new row). In general for
we can have combination of
existing rows out of
in
different ways to make a dependent (new) row.
So using (1) and (2) we get,
Putting everything together,
I am caught with a little trouble to figure out an easier way to set up and solve a summation of a function of several variables. I just realized that Mathematica doesnt allow me to add a constraint in the summation operation. My problem is that, the summation should be performed over the ordered partition set of a number.
An example, will illustrate the problem definition a lot better. Suppose I want to compute the sum of a function of variables over all variables such that, the sum of the index variables always equal to a constant
.
Clearly, the indices here runs over all the ordered partitions of the number . Since
is not that big a number, we can simply write these partitions by hand and somehow get the job done. Let us say denote the ordered partitions and unordered partitions of the number
by
and
respectively.
. The ordered partition will have the permutations of each of these on the three positions! So
and
are different sets of
whereas, they are considered as one
in
. The summation needs to be carried over the ordered partition list
. Since both
and
grow pretty big with even modest
, the job of manual summation is not that appealing. I really hoped mathematica to aid me here. Unfortunately, I don’t see a way out here, other than the painful individual partition sum. Anyway, for the curious reader, the sum I attempt are of the following types:
typical values for is
and
is around
. If any enthused reader finds a way/trick, I will be happy to sponsor a coffee
(Sorry at this recession time, nothing more
sadly…).
In fact, the first one is easy (Interestingly, I just found a way, while typesetting the blog). I can do a differential with respect to and then scale it to get the requisite sum. It can be written as follows:
Second one is the trouble maker
Oh man! power of a coffee. As I am typing this on a moody Lausanne swiss weather, here comes the trick. I just made a coffee and that seemed to have worked. I guess I can apply a similar trick to the second one too. Basically, we can split them into two expressions and then write each as differential versions of a multinomial sum. Here it is:
Amazingly, we can simplify both to get a simple looking expression. I am glad! Here is what I finally got:
While searching for the book Information theory, Coding theorems for discrete memoryless systems by Imre Csiszar and Janos Korner, I came across several sites which echoes the fact that this book is one of the rarest specimen on earth. However in the process, I found a blog forum which lists a whole lot of out of print books. This book, as expected is in demand already. We can even vote to request to bring the out of print books to a possible reprint. I am not sure how effective this is, but there is no harm in trying! We can suggest any books you may want to have a reprint. To me, this is a whole new and welcome idea. For learning, we should have access to the good books. Already quite a few demands (See this blog for instance) for the Csiszar and Korner book. Man, the world sometimes think alike!
Last winter Etienne Perron, Suhas Diggavi and myself together, have developed a tool suit to prove inequalities in information theory. The tool is adapted from the previous work of Raymond Yeung and Ying-On Yan at Cornell. We have made it a complete C based software and removed the matlab dependency in the back end. There is also a pre-parser (using lex and yacc) built in to have flexibility on choosing random variable names. More importantly, a graphical front end is developed (using Gtk), which works well across the platform. Even though the beta version was ready in late 2007, for many reasons, including exhaustive testing (we always find scope for improvement) it was delayed. Last month, we finally made an official release. The original xitip project page in IPG has a short description and pointer to the exclusive Xitip page in EPFL (http://xitip.epfl.ch). A lot of things still need to be done, before we could say it is satisfactory. One of the main thing pending is the user guide and some kind of exemplified documentation. There is a technical report, I have prepared, but that is a bit too technical at the moment. Of course Raymond yeung’s amazing papers introducing the theoretical idea behind this prover and his book are valuable resources. I have tried to provide a little more easy understanding of the concept using some illustration and toy examples. I hope to put this report anyway in the EPFL repository sometime. The first version of the project discussing the background is available here in PDF form.

Xitip screenshot, the French version
The software is open source. If you are not bothered to compile and make an executable yourself, then please download the binary executable and just run. It is just a matter of double click in the latter case. We have Linux, Windows, Windows(Cygwin) and Mac versions available. There are two different linear programming software used. One is a Gnu open source GLPK and the other one is Qsopt (developed at Gatech). The Qsopt version is faster than the GLPK. Just in case you are obsessed with a perfect open source model, you could avail the GLPK [5] version.
Hopefully during this summer we will get to complete the pending work on this project. If any of you happen to find it interesting please don’t forget to update us, on what you though about the software (Comments can be good, bad and ugly!).
Aside, I better mention this: Xitip is a software useful for proving (verifying) Information theoretic inequalities [7] only. Such inequalities contain expressions involving measures such as entropy, mutual information etc. It is a pretty handy tool if you are trying to prove some limiting bounds in information theory. In reality, there is broad classification of Shannon type and non-Shannon type inequalities. Non-Shannon type inequalities are not many, but they exist. Xitip at the moment is equipped to solve only the Shannon type inequalities. You can expect more information on this at the Xitip home page [2]
[1]http://ipg.epfl.ch/doku.php?id=en:research:xitip
[2]http://xitip.epfl.ch
[3]http://www2.isye.gatech.edu/~wcook/qsopt/
[4]http://user-www.ie.cuhk.edu.hk/~ITIP/
[5]http://www.gnu.org/software/glpk/
[6]http://en.wikipedia.org/wiki/Information_theory
[7]http://en.wikipedia.org/wiki/Inequalities_in_information_theory
On the day before yesterday, while on travel I picked up two books from the Bangalore airport book shop. One was the Helen Keller autobiography “The Story of My Life”. This was perhaps the first full volume autobiography book I had read, when I was a child. I still remember, the used copy of this book being given to me, by a family friend and teacher, when I was in early school. The vivid recollection of Helen Keller learning the alphabets and notably, words like ‘rain’ sill echoes somewhere in the back of my mind. I decided to buy this book, with the plan to gift it to someone, who I come across, preferably young kid in school or so. Eventually, I gifted this to a friend of mine who, when I mentioned about the same, was all excited to grab it. In a way I felt happy because I could instigate interest in some one about Helen Keller. Keller’s life has been a message in itself to humanity. Her strives and constant efforts to learn to react to this world is touching to say the least.
The other book which I have picked along is on the story of “Nicolas Bourbaki”. It is titled “The artist, the mathematician: The story of Nicolas Bourbaki, The genius mathematician who never existed”. It was authored by Amir Aczel, the author of the book on ‘The Fermats Last theorem’. I never heard about this book before, either in reviews or from friends. Well, I must confess that I didnt really search for books or reviews on a topic of this kind, to really hear about such a book. Anyway, the book is a recent print and the news may be just coming out only.
This book turned out to be quite an interesting one. On the flight and while on wait, I could quickly finish reading the book. Being a math and mathematician related book, I didn’t feel sleepy over the book. That helped to complete the reading at a stretch. The book is about Nicolas Bourbaki. Out of my innocence, I never heard about this character before, either. As the title says, there was no specimen of this kind in human form lived upon earth. Yet, there was an identity to this Nicolas Bourbaki. The real truth about this name is revealed a little later in the book. Nicolas Bourbaki was not just one person, but an identity for a collection of mathematicians, mostly French. Together they have published a lot of work in mathematics, under the identity of one name “Nicolas Bourbaki”. How does that sound? Well, it sounds a little weird and a little interesting to me. Can we say, Nicolas Bourbaki was an institution itself? (Well there is a story about Nicolas Bourbaki being applied to get an AMS, American Mathematical Society and gets a reply to pay the institutional pay to get the same. Of course, the AMS president that time, had known the truth about the name Nicolas Bourbaki!)
So, Nicolas Bourbaki represented a group of Mathematicians, post 1935 (between first and second world war period), who formulated a systematic structure to the study of mathematics itself. They have worked predominantly on the Modern mathematics (modern algebraic concepts) including the concept of ’sets’. As you would expect (because of the time line and French connection), the star mathematician André Weil was one of the founding members of this group. Some of the other well known French (connected) mathematicians also figured in the celebrated group. They iuncluded names like Henri Cartan, Claude Chevalley, Jean Coulomb, Jean Delsarte, Jean Dieudonné, Charles Ehresmann, René de Possel, Szolem Mandelbrojt. Some later entrants to the Bourbaki group had the likes of Laurent Schwartz, Jean-Pierre Serre, Alexander Grothendieck, Samuel Eilenberg, Serge Lang and Roger Godement. The group would meet regularly to discuss and debate on modern mathematical topics and eventually publish under one name Nicolas Bourbaki!
Even though Bourbaki does not exist (at least actively) today, it is believed that this has brought some ’structure’ in not only mathematics, but in European culture in general. Besides, the stellar contributions on the field of algebra and number theory by this group is acknowledged very well.
Now, another reason, why this book took my interest is because of the presence of the mysterious Alexander Grothendieck. The book talks rather in detail about this mystery man. He was regarded as a genius and had contributed immensely to the world of mathematics. His fields medal in 1966 and related absence from the Moscow event on his own Fields medal confer perhaps tells more volumes about this man. I took by surprise to hear about the current life of this once world star of mathematics. Post 1991 he is believed to be living in a remote jungle/outskirts of Southern France, far from any worldly contacts. I quickly recollected the 2006 Fields medal winner Grigori Perelman, when he declined the medal and began to live away from mathematics crowd. Like Perelman, who (now accepted by everyone) proved the Poincaré Conjecture, Grothendieck as well, produced some monumental contributions. He was considered as a Genius and it was recognized too. But in close resemblance to what Perelman did in 2006, he as well decided to quit mathematics altogether and decided to live a mysterious and aloof life.
What makes, genius folks like Perelman and Grothendieck to abandon themselves from the world? It is surely not fear, simply because they have contributed so much to us and can only be proud of it. What else then? There may be arguments that Grothendieck was disappointed by the fact that, he couldn’t get the results he wanted from his political activities (He had strong political views on certain things against the establishment). Others say that, the childhood miseries and leading an abandoned life early on triggered him to do an isolated life, out of frustration and despair. In Perelman’s case, it is surely a hurt feeling and the one that of ignorance by the mathematical community, for questioning his credentials on the Poincaré conjuncture proof. But can the human mind, which is otherwise so highly brilliant all of a sudden taken aback by a feel of hurt? I feel sorry for these two fine mathematicians, who could have produced much more (They have already done so much, but….) to the world. The life and fate of these two tells the story of the society we all are in, where jealousy, politics, lack of respect to others can completely eradicate a gem, which we should have preserved at all cost.
Tears and anxiety glues through my mind on the current whereabouts of Grothendieck. I hope he lives a happy life around Montpelier! Human mind, man is a highly complex black box. What all it takes and what all it breaks?


Recent Comments