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 thing..in 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: http://pauli.uni-muenster.de/~munsteg/arnold.html

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!