Sunday, March 22, 2009

Curiosities in Computer Science. Can one go beyond finite and discrete data ?

My knowledge of Computer Science is near 0.
My knowledge of Mathematics is epsilon.
Officially I am supposed to know some finite amount of Physics.

My only slight non-trivial brush with CS was with the exciting course that I took with Prof.Madhavan Mukund at my Alma-mater Chennai Mathematical Institute (CMI). Prof.Madhavan Mukund is definitely one of the best 5 professors I have ever seen in IEMS (Rourkela), St.Xavier's Collegiate School (Kolkata), CMI, IMSc, TIFR and SINP. (4 institutes of India where I have spent non-trivial amounts of time).

{Of course St.Xaviers is a special case in this list from where I can hardly recall a single good science teacher. I definitely got some great English and Hindi teachers. And IEMS (Ispat English Medium School), Rourkela is the school in Orissa in which I studied till class 6. I was in Rourkela for 11 years. IEMS had an intensive mathematics and science environment and that instilled in me a love for these subjects right since my childhood. That school has produced many awesome students and its a pity that today that school is crumbling because of government's apathy towards it and lack of funding. I would urge people to collect together to do something for that school which has given Indian some of the finest students in science in the 1990s and the late 80's.}

Prof. Madhavan's course was awesome to say the least. (those unforgettable days when I used to stay awake for days at a stretch trying to do his innovative assignments...I could atleast get a working code ready for all of the questions, though almost always my algorithm was nowhere close to the slick solutions of some of my awesome batchmates like Hrushikesh, Arnold or Preyas.} For me whose only exposure to programming in school was ISC exam level programming with C++, this was an introduction to the completely new world of CS. I always wished that I could take up more courses in TCS but given my professional commitment to Physics I never could get the time to study TCS more seriously, but I keep hoping that someday I shall study more of it. At least I hope to understand someday Automata and Complexity Theory. Little that I see of it from talking to my various friends who work in these fields, I feel they are exciting things to know.

I later sat through another course of Prof.Madhavan Mukund..just listened to the lectures. But anyway thanks to his lectures in the 2 courses, it sparked in me an interest for CS. It drilled in me a basic fact that CS is NOT programming as is commonly and erroneously conceived.

Anyway here I want to talk of some naive thoughts about mine about CS. These are mostly some questions about CS which I have been curious to understand and know but never got the time to do serious reading about them. I am sure most of what I will be talking here will be naive to professional CS people but then I have been filled with childish curiosity to know about a million things since I was a kid. I have no fears to ask questions no matter how naive they are.

I would be glad if some CS or Maths person reading this blog decided to explain these things to me. I have been thinking of these questions for quite some-time but as usual given my primary commitment to Physics I have never been able to do serious reading along these lines and hence have made no substantial progress. All I have is some questions to ask. Let me at least ask them publicly!

So let me begin.

We know that given a linear map between 2 finite dimensional vector spaces one can represent it by a matrix by a choice of basis in the two spaces. A lot of interesting things begin to happen if the linear transformation is an automorphism and then I have interesting structures to play with like the eigenvalue, eigenvector, trace and determinant etc. Now we know that even if the matrix representation is dependent on the basis one can write the characteristic polynomial of this linear transformation and then the coefficients of this are basis invariants. The coefficient of the highest and the first power are most familiar to us by names of "determinants" and the "trace". And the determinant of of a matrix written without the signum function in its defintion is the well-known "Pfaffian". {There are some very exotic definitions of Pfaffnians through graph theory and through differential geometry but I shall avoid all that stuff here}( I shall avoid getting into the complication of differentiating between the minimal polynomial and the characteristic polynomial and whether the field is algebraically closed or not and what its characteristic is. I shall brazenly sweep these subtleties under the carpet so that I can get my essential questions across to the reader. Reader is requested to assume the best case scenario whenever required :P )

{Most common difficulties will arise when the algebraic dimension and the geometric dimension of an eigen value doesn't match but then if one restricts oneself to algebraically closed fields like the complex plane this problem is gone. So kindly do it if you run into problems :D }

Q1. We needed a choice of basis to define these n-basis-invariants (let the vector space be of dimension "n"). Can we define these basis invariants without a choice of basis?

Q2. So isn't it possible to the give a linear transformation as an "input" to a computer program by giving it these n invariants along with their multiplicities? Can't everything that can be known or said about the linear transformation become deducible to the computer as soon at it knows these n-invariants?

I can see this much that one can solve the characteristic polynomial to uniquely determine the linear transformation (upto permutation of the basis) if there are no degeneracies in the eigen-value.

Q3. The most naive way to specify an automorphism of a finite dimensional vector space to a computer would be to give it a matrix representation of it. But can't there be situations when it is advantageous to the computer to get the linear transformation as a set of its invariants ? {it saves memory for one the first way it has to store n^2 data and in the next it has to store n data}

On the same strain if I have a finite group then everything about the group is known if I know its group multiplication table.

Q4. Hence isn't it possible to give a finite group as an input to the computer by specifying its multiplication table?

Q5. We know that in some cases the group is generated by a generator set using some relations. In those cases can't memory be saved by giving the computer an group not as a multiplication table but instead as a generating set and the relations?

Q6. Isn't it possible to input to the computer in this way a free abelian group on a set? Or to get very fanciful, is it possible to make the computer understand the "free abelian group" on a set as a solution to an universal mapping problem?

Q7. Conversely given a table which "looks like" a group multiplication table isn't it possible to write a program to take this as an input and test whether this represents a group? This definitely can be checked in a finite number of steps but I suppose one should be able to come up with a slick algorithm which does this checking in less than that.

Q8. If the above can be done then isn't it possible for the computer to check whether two finite groups are isomorphic given their multiplication table? This again seems to be a finite process but can someone give a slick way to do that?

Obviously the non-trivial question is when the cardinality of the 2 groups are equal. Since we know that there can be non-isomorphic groups of the same cardinality.

Q9. Thanks to Lagrange's theorem we know the possible values of the cardinality of the subgroups of a finite group. Hence given the multiplication table we know the subsets of it that we need to search to detect subgroups of a group. Given any subset of the matrix checking whether it forms a subgroup isn't very difficult.

Hence can't one write a computer program which will take the group multiplication table as an input and then generate all possible subgroups of it?

In the all the above cases the saving grace is that there is a sense of finiteness about the data being taken by the computer whether in form of a vector space dimension or cardinality of a group. But this is where I want to let my fantasy take a bit of flight.

Can't we get computers to get to operate with things which are not finite and discrete?

Apparently Topological Spaces seem to be such a non-finite and non-discrete data unless the underlying set is a finite set.

So we can think of the following possibilities:

Q10. If the underlying set is finite then it should be possible to give as input to the computer the set and the open sets and then ask it to find out, say, whether this Topology is Hausdorff. This seems possible since it is more or less a search algorithm.

Q12. Even if the underlying set is not finite, but say the Topological Space is second countable and further the basis is finite. Then can't this be given to the computer as input?

Q13. Similarly other immediate notions of "finiteness" in topology that might be a good area to try computability would be:
a. If every point has a countable basis of neighbourhoods.
b. If the space is compact.
c. If the space is paracompact.

Q14. Further if the space is not only compact but also can be embedded in some euclidean space and can be gotten as the 0-set of some equation. Then too probably one can try a method of doing topology on it with a program

Q15. We see that the essential trouble with programming topologies is that we don't know of any way to make the computer understand logic which involve ideas like:

a. "For any 2 points..."
b. "Given any point one can find...."
c. "Given a curve.."
d. "Given an open set containing.."

It is not clear how a program can be made to understand ideas of "any" when the number of possibilities is uncountably infinite.

I would be delighted if some computer programmer or mathematician reading this blog can think about these questions and try to come up with ways of bypassing these limitations.

Q16. Can one do some kind of lattice approximation to topological space.
Like try to convert topological properties into lattice calculation?

I know it is a very fanciful thinking. But still can you do it?

Q17. On a probably simpler note I think it would be great if people can collaborate to create a database for Homotopy, Homology and Cohomology groups of known spaces and write programs which can take input like "X union Y" ("X x Y" would be trivial ) and compute these groups for these spaces by searching the database for the groups for spaces X and Y.

The issue of computability has always seemed an interesting question to me. Those questions which can be "programmed" always seem to belong to a different kind of understanding than those which can't be programmed.

Like one can write a program which will take a matrix as an input and will decide whether the corresponding linear transformation is invertible and can also decide if not then how large is the null-space.

Q18. But it doesn't seem to be possible to write a program which will take a function as an input and will decide whether it is continuous or differentiable at a point. It isn't clear how to program the idea of "taking the limits".
And as far as my intuition goes I don't think a lattice idea will ever work here since things can go wrong on a measure 0 space which a lattice can never get to.

One can also try making this following idea computable:

Q19. Given a Lie Group find its Lie Algebra.
Even mathematically it is a hard question unless quite a lot is known about the group in terms of its topology or it being understood as a zero-set of some polynomial ring.

Or a more difficult and basic question would be to understand how to give a Lie Group as an "input" to the computer?
The issue here becomes circular since in most cases a natural way to give this data to the computer at least for finite dimensional Lie Groups would be to input a chosen basis in the Lie Algebra as matrices! And that means to solve what I wanted to solve I need to know the solution!

Obviously I am thinking very naively and I would urge CS people to give some serious thought about this question.

And making the above question programmable shall be of great utility to Physics.

Q20. I would encourage computer scientists to look into these questions about general manifolds as well where there is a hint of finiteness to help compute things about apparently continuous and infinite data:

1. Triangulable manifolds (all differential manifolds are triangulable)
2. More hopes lie with manifolds which are homotopic to some polytope.

This was a brief glimpse into my world of scientific imagination about which very few people know.

I hope this glimpse would motivate some Computer Science or Maths person to think along these lines.

PS: I would recommend people to read:

PS: If any of you readers have any ideas about how to go about these questions then kindly put the idea in the comment. Let there be an online discussion of the ideas. If something non-trivial can be developed through these blogs!

Monday, March 16, 2009

Some thoughts about elections.

{ This has also been put up at this blog. }

Recently got my legs pulled and jibed at by a senior of mine, Vipul (from my alma-mater CMI and currently at UChicago doing a PhD in Mathematics,) about the stagnant situation of this blog and whether democracy can really be reformed by people who blog about it only once in 2 months.

{ Actually one can look at in this way: I have not been able to put up updates on this blog since I was too busy with my Physics whose professional requirements have been mounting off-late. Hence I was spending more time with Physics. Now is this a bad logic that I have actually been contributing more to the nation by trying to do my Physics well rather than blogging here? }

Anyway thanks to Vipul's comments and pokes, it accelerated the process of me finally writing down some things which I have been thinking of recently. The election round the corner seems to provocate enough number of dinner and coffee table discussions to keep one's mind thinking and hence thought of sharing some of the thoughts which I discussed during these discussions.

1. One thing has always worried me as to whether election makes any sense in a country where most voters are illiterate and are probably have little or no information about the political scenario and the plans of the parties and the larger questions that the country needs to face. Can't really blame the people because if one has to struggle day in and day out to make one's both ends meet one simply can't afford to keep track of the larger questions! The larger issues are simply a luxury when you are not assured of your next meal.

In this situation what is the difference between large number of uneducated/mis/non informed or non-thinking voters voting and voting by a random number generator?

It seems to me that a random number generator will be better since it will be unbiased and might help a better party win in comparison to a corrupt politician being able to "buy" these non-thinking voters by dubious means.

Here one also sees why issues like "caste" and "religion" and "telengana" issue based voting makes such an impact in India. When the population is so huge with no net coherence of thought then if some local issue can cause a local correlation it has large contribution to the net scenario since the rest of the system is anyway randomized! Thats what politicians use, cause local polarization (especially with a non-thinking mass) based in local issues hoping that there is no large scale coherence.

This actually shows why "blogs" are potentially powerful. They can become centers to cause these correlations among a certain section of the population and that can become non-trivial.

2. The point about becoming an effective voter is whether as a voter I am a "thinker" who takes a well-thought decision or a "believer" who goes by the hype and votes for the party which best hypnotizes me into believing in them.

As Vipul put it in a catchy question to me

"Do you think you are believer or you believe that you are a thinker?"

Let us first realize that the essential reflection of whether one is a thinker or a believer is in the way the person makes "choices". Its the process of decision making that amounts to making a choice is what differentiates between "thinkers" and the rest. It can start from simple things like working on a maths question where at every step one needs to think to decide the optimal next step and also in bigger questions like choosing one's life-partner.

Let me try to list out here as to what all a person needs to be a "thinker" apart from the basic minimum intelligence which unfortunately a person cannot change :

1. Freedom of choice.

Unless one has choices there is no use of the ability to think. If one gets excessively constrained that one's choices then there is nothing that the person can do even if he/she can think. Now choices can get constrained by internal as well as external reasons. Internal as in, I fail to see the choices that exist or may be for external reasons where some external force closes choices for me. like as a dalit landless farmer facing the guns of the rich upper-caste landlords, my choices in life are too constrained.

A large section of the Indian electorate is deprived of this fundamental thing as in freedom to choice.

And pretty paradoxically this section of the people who are artificially deprived of choices are the one's for whom a good government might make the biggest difference. Rich businessmen and people in research are probably more immune to political perturbations.

2. Relevant and correct information.

This is the next step. I have enough intelligence to think and say I have choices but still I need some substance to start thinking on. An Economics Nobel Laureate simply can't think about a question in Quantum Theory unless she/he knows enough Physics. <>

Thats the basic kind of problem a large section of the Indian electorate faces. Many simply can't afford to get time to get themselves informed about the parties and the larger issues since they have their first priority to arrange for food! Who cares about what happens to the nation when I am hungry and have no food to eat? And another considerable section of the population simply doesn't care to find out though they have lots of resources since either they are too busy with their profession or busy hanging out at the malls. Somehow given the kinds of lives we live cocooned inside research institutes worrying day and night about courses, assignments, exams and science, politics and larger questions of India seems pretty distant.

Given that large sections of the population don't cast a well-thought vote..I don't know what sense democracy makes in a country like this.

Now there are 3 sides to see in this:

1. If everybody is busy with his/her life striving for professional excellence isn't that by economic ideas an optimal state for the country? How does it then matter whether each person is thinking about the future of governance and larger national questions since anyway every person is trying for professional excellence?

May be the above idea can be put in analogy with the idea of economics that "we get our bread because the baker wants to make profit". The idea is that such a set of people is creating "positive externalities" for each other and the system is thus progressive and then why would anyone need a government? Somehow isn't it possible for such a system of "self-optimizing systems" to show some kind of spontaneous large scale collaboration like what in statistical physics is called "self-organized criticality"?

The associated idea is that a single man's vote is irrelevant to the election since one vote cannot make difference to the future and the energy and time needed to spend to inform oneself and vote knowledgeably is huge. And at the end of all this research the party for whom this party voted might not win. Hence the "net payoff" in this process tends to 0 and hence this makes no economic sense for a person to drop commitment to one's profession and educate oneself about the larger national issues.

So why should anyone vote?

2. When every person is trying to achieve personal professional excellence then everyone is tending to get into a tunnel vision where one is slowly missing the larger picture and anyway people are only going to create positive externalities only locally and not cause large scale collaborations to happen.

This is where the government chips in with an external view of the larger picture to cause macroscopic reallocation of resources to optimize its utilization by the entire population as opposed to the only local optimization that you and I can cause.

Hence one needs a good government.

3. Education and ability to think brings in with it a sense of individualism and independence of thought. How likely is it that a set of such people will show cohesion and coherent thinking? Why hasn't it happened that all the good students across the various world class institutes in India like CMI, ISI, IIT, TIFR get together to form a party which will surely have an average IQ and education billion times any other existing party?

The question is where does the market equilibrate between these 3 competing factors? Can a government have this global ability to cause large scale optimization by macroscopic rearrangement of resources? Can a government be expected to have enough insight and information to cause this?

If the answers to the above question is "no" and if anyway most voters are "non-thinkers" (and hence 1 thinker's vote counts for nought) and even economically it makes no sense to try to be a "thinker" w.r.t voting, why should I vote or worry about casting a good vote instead of doing Physics and Maths properly?

Wednesday, March 11, 2009

Holi at TIFR

Coming from a relatively highly sophisticated and silent and gentleman/womanly atmosphere of my Chennai Mathematical Institute holi at TIFR was a culture shock.

Back in CMI Holi used to be a very formal affair where some of the guys used to dab a pinch of gulal on each other's face. Mostly it was arranged by my batchmate Jigar. Only last year Holi at CMI took a slightly more vibrant tone. But still it was quite an organized thing except for the last minute efforts by my great friend Atul to throw mud on each other and add some new "colours" to the event.

But then last year in CMI, I believe the defining moment was when one of my batchmates went to put colours on another girl in CMI and she sharply replied back "You dare do that and I shall slap you hard". And she went back to her academics shutting off the colorful frenzy outside.

Hence Holi in CMI for the sake of self-respect remained mostly a guy's affair.

Hence I had a completely new kind of Holi here at TIFR. They dug up the ground to create a huge mud pit and then people were thrown into it irrespective of age,sex and position in TIFR. { After CMI I was actually pretty surprised to see such enthusiastic and uinhibited participation of the female sex in the Holi chaos. In TIFR they were quite instrumental in initiating the funny mayhem! }

The students went and caught each of the profs and held them up by feet and hands and threw them into the mud pit. And then everyone kept splashing mud on each other. Some of the profs said "no" and their decision was respected and some who said "I don't want to" got held by legs and hands and dumped into the mud pit. :P

Obviously I too got thrown in and it was quite fun to get drenched in mud by so many people. And the I also joined in the process of throwing mud on others! :)

I have been shedding many inhibitions over the last 2 years and I shed this one today. I am a highly freed person and I don't restrain myself from trying out something unless the action runs the risk of destabilizing my thinking or damaging my health or others. Hence I don't drink alcohol or smoke but have danced at parties and balls.

As soon as the people were coming out of the pit there was a water shower arranged for them to clean up and thats where the consistent pranks started. People were too drenched in mud to see whether the other guy was pouring mud or water. So as soon as someone got out of the shower cleaned he/she was welcomed with a bucket of mud water on him/her.

The argument was simple "You are not allowed to be so clean"

There were a few visiting French scientists in the Physics department and they too got thrown in. One of our physics profs went to them and explained to them:

"You have to do nothing at all. Just go and sit in the pool and close your eyes and ears. The rest will be taken care by us. This is annual ayurvedic treatment festival in India"

They happily enjoyed the "ayurvedic treatment"

One of the profs had boiled a lot of beat-root to create pink colours and that was given to the children in the campus to play with. Nutritious and non-toxic colours for children.

And there were obviously colours but they took an obvious back-seat and there were liters of "Bhang" and sweets for everyone. The girl who was distributing the Bhang found a nice excuse to be not thrown into the mud saying "I am busy" :P

I steered clear from such suspicious liquids. :)