BR Maths Corner-1

[Amber G.]

For the first problem, (just to be careful) the "correct" answer with proper nit-pick, IMO is actually "abs(det(A))" (otherwise, in some cases you will end-up with a negative volume) (Also, I will add "euclidean" in front of "n-dim" space )
For the second one, intuitively, the answer is:
squareroot(( det (A(transpose)*A))

[SK Mody]

Yes Abs(Det(A)). Sorry
Abs(det(Transpose(A).A)) is correct. With the sign it gives the oriented area.

I don't think you need to specify euclidian space, since volume can be defined using elementary cubes.

[Amber G.]

SKM - Not to nit-pick but "sqr(A)" (actually the "root" sign) (by accepted normal definition) means positive value onlee .. so "abs" in the second case need not be thre ... eg when one writes sqr(2) with either normal mathematical "root" sign or types it in google see here it means a (positive) number between 1.4 and 1.5 ..
Also, BTW (A(transose)*A) is always positive... so no need to put ABS there... (point is det(A) can be negative, but A(transpose)*A is always positive... (assuming of curse, as you said, you are dealing with real numbers)
(You may also see, say wiki: ..is the positive real number that, when multiplied by itself, gives the number 2.

Also - "volume(s)/areas" etc in non-Ecuadorian space(s) do have well defined meanings a little different .. (at least how normal mathematicians defines them) ... but I guess, it depends on the definition of "area" or "volume" so take it for FWIW..

[SK Mody]

SKM - Not to nit-pick but "sqr(A)" (actually the "root" sign) (by accepted normal definition) means positive value onlee .. so "abs" in the second case need not be thre ... eg when one writes sqr(2) with either normal mathematical "root" sign or types it in google see here it means a (positive) number between 1.4 and 1.5 ..
Also, BTW (A(transose)*A) is always positive... so no need to put ABS there... (point is det(A) can be negative, but A(transpose)*A is always positive... (assuming of curse, as you said, you are dealing with real numbers)

Of course. What was I thinking. The sign of det(A) gives the sign of the area.
Anyway can you prove part (b)?

Also - "volume(s)/areas" etc in non-Ecuadorian space(s) do have well defined meanings a little different .. (at least how normal mathematicians defines them) ... but I guess, it depends on the definition of "area" or "volume" so take it for FWIW..

I'm not really talking abt non-euclidean space. Just saying, no metric needs to be defined. You only need to define a measure. The normal volume measure can be obtained by taking a finite number (tending to infinity) of elementary cubes.

[Nandu]

Also, BTW (A(transose)*A) is always positive...

except when it is zero.

[SK Mody]

Also, I will add "euclidean" in front of "n-dim" space

to which sk mody casually replied:

Just saying, no metric needs to be defined. You only need to define a measure. The normal volume measure can be obtained by taking a finite number (tending to infinity) of elementary cubes.

I need to qualify the statements I made.
Yes, no metric needs to be defined if we are talking about finding the volume of a k-dimensional parallelopiped in n-dimensional space when k = n. However, when k < n, the question arises - how can we define the k-dimensional area of vectors a_1, a_2, ... a_k in n-dimensional space? The natural way to do it would be to take any k basis vectors (i, j, k etc .. ) in the original basis and rotate their span until the span of i, j, k ... coincides with the span of a_1, a_2, ... a_k. This implicitly assumes that rotation (using the usual matrix multiplication) preserves areas. But this assumption means we are implicitly giving the space an inner product sigma(xi.yi). Alternately we could find an orthonormal basis for a_1, a_2, ... a_k. But this too involves an inner product.

Hence you were more or less right Amber G. I should have been a little more careful.

It is no coincidence that Bhaskara's proof of Pythagoras theorem involves finding the difference in areas of a square and and another rotated square.

Comments appreciated.

[Amber G.]

Also, BTW (A(transose)*A) is always positive...
...except when it is zero. :

Should have used "non-negative"! (specially when I was busy last few days writing/editing "official solutions" to a regional math contest )

Speaking of Math contests, just curious, since it's the season, any BRFites (or their kids) are taking part in AMC/AIME and planning for Usamo etc.. (or their equivalent Indian RMO/InMO etc)

SKM- as you probably already know, your problem(s) are related to what is known in Physics (or math) as "cross product" (Like force on a moving charge is given by (proportional to) Vx B - which is equal to area spanned by these two vectors. (or generalized form of 'cross product' is know as 'wedge product' (or exterior product) and there are references in internet/books (see wikipedia article related to wedge product).
(The area/volume which you have asked is known as ( same as) wedged product of n vectors)

One can generalize classical meaning of "area" (or "volume") from 3 to n dimension ...It depends on how one defines/generalizes but for 2 (or 3) dimensional case, if we use formula's which we normally use for area/volume - they (or most formula's are valid) are valid for Euclidean space ... (hence, if you see wiki article, you may see qualifier 'Euclidean')

For example, one can define velocity (or position) on earth's surface by using two unit vectors (one north - other east) -- but going 100 Km north then 100 miles east thrn 100 miles south and then 100 miles west - you may not end up at the same place -- unless you are in a Euclidean space... (Or area of a triangle whose two sides are 'a' and 'b' (and are perpendicular to each other) need not be (1/2) a*b on surface of the earth )

I would end this post with a classic problem inspired by SKM's post. The problem is extremely well known so comments are welcome, but please do not put the answer for a few days. If you have not heard the problem before, try to get the answer before looking it up on internet.

Problem: A goat is tied up with a rope of unit length. How much goat can roam? (or if there is grass - how much grass the goat can eat). (Goat is also restricted to move in a space of given dimension(s))

In 1 dimension - (If the goat is restricted to move only in a line)
the answer is obviously 2 (can go one unit left or one unit right)
In 2 dimension - It is about 3.14 (area of unit circle - Pi)

In 3 dimension - It is about 3.82 (about (4*Pi/3 ) - a unit spehere)

How much grass the goat can eat if it is n dimension? What happens when n tends to infinity ... does the answer goes to infinity ... or limit tends to some given (large) number ... or something else?

(The Integral is not trivial but it is also not very hard)

Hint: (If you want to "check" your answer, for 4 dimension the answer is about 4.9)

[SK Mody]

One can generalize classical meaning of "area" (or "volume") from 3 to n dimension ...It depends on how one defines/generalizes but for 2 (or 3) dimensional case, if we use formula's which we normally use for area/volume - they (or most formula's are valid) are valid for Euclidean space ... (hence, if you see wiki article, you may see qualifier 'Euclidean')

The point I was trying to make in response to your comment about euclidean metric, is that you do not need to impose a euclidean metric in order to define volume. You need to define a measure and not a metric. I later qualified that and said that if you need to define areas of lower dimensional subspaces in n-dimensional space - only then do you implicitly end up defining a metric.

It goes without saying that in my first post it is to be assumed that the usual "volume measure" is to be used. While this is the same as the wedge product, my intention was to avoid technical vocabulary if not required for the problem at hand.

I hope you get my point.

[Amber G.]

Today is Pi Day. (3/14)! Happy Pi day to all!


A few centuries before Newton, Madhava of Kerala gave us (among other things) interesting relationship of pi ,
(see how pi appears with nothing but numbers like 1,3,5...)

pi/4 = 1-1/3+1/5-1/7+1/9 - .....

And in this thread, a problem
(1/2)*(3/4)*(5/6)*..... also had approximation related to pi

Finally, a beautiful and, of course, very old and famous relationship.. see if you can find the value (or prove it why it is so)


what is the value of: (or what value this infinite series converge to?)

1+ 1/4 + 1/9 + 1/16 + 1/25 + 1/36 + 1/7^2+1/8^2 ...

?

(BTW
I see no comments to the problem posted above:

Problem: A goat is tied up with a rope of unit length. How much goat can roam? (or if there is grass - how much grass the goat can eat). (Goat is also restricted to move in a space of given dimension(s))

[ArmenT]

what is the value of: (or what value this infinite series converge to?)

1+ 1/4 + 1/9 + 1/16 + 1/25 + 1/36 + 1/7^2+1/8^2 ...

(pi ^ 2) / 6. This is the solution to the Basel Problem, and first solved by Leonhard Euler. Solving this brought him a lot of fame, since no one could solve it for over 100+ years.

[shaardula]

delete.

[shaardula]

Problem: A goat is tied up with a rope of unit length. How much goat can roam? (or if there is grass - how much grass the goat can eat). (Goat is also restricted to move in a space of given dimension(s))

goat eat grass pi*(1+dx)^2, no?

[Mohan G]

Problem: A goat is tied up with a rope of unit length. How much goat can roam? (or if there is grass - how much grass the goat can eat). (Goat is also restricted to move in a space of given dimension(s))

If there are n dimensions the n-ball volume will be:



where R is the radius, Γ is the gamma function. (use R=1 above)

In the limit, as n->infinity, the n-ball volume shrinks to 0.

http://en.wikipedia.org/wiki/N-sphere
http://hyperphysics.phy-astr.gsu.edu/Hb ... rling.html

[Amber G.]

In the limit, as n->infinity, the n-ball volume shrinks to 0.

Yep! This some may find surprising ... the constant (C_n) increases in the beginning but after 5th dimension starts decreasing and becomes smaller and smaller as number of dimensions increase.

(BTW, one of the easiest way to get the above result is to note that r^2=x^2+y^2+.... and do the integral (r=0 to infinity) of exp(-r^2) and equate it to n products of exp(-x^2) - (each of which is equal to sqrt(pi/2)

[Amber G.]

what is the value of: (or what value this infinite series converge to?)

1+ 1/4 + 1/9 + 1/16 + 1/25 + 1/36 + 1/7^2+1/8^2 ...

(pi ^ 2) / 6. This is the solution to the Basel Problem, and first solved by Leonhard Euler. Solving this brought him a lot of fame, since no one could solve it for over 100+ years.

The answer is correct, of course. I find the result beautiful.
One of the fun way is to look at the old well-known expansion of sin (x)
sin(x) = x ( 1- (x/pi)^2)(1-(x/2pi)^2)(1-(x/3p)^2)...
putting x=(pi/2) gives the result of the old problem posted here ((1/2)(3/4)(5/6)....) and comparing the coff of x^3 gives the above result)

[Amber G.]

Just for fun

Here is high school/middle level problem, give it a try.
Was going to put in Vedic Math thread ... no you don't have to know Brhamgupta's methods but it sure will help.

What are the first 100 digits after decimal point in the value of
(7+5 sqrt(2))^100 ?

[ArmenT]

What are the first 100 digits after decimal point in the value of
(7+5 sqrt(2))^100 ?

I'm going to say 0.
Reason:
1. Forget all the integral numbers into the expression above because they don't play any part in the digits after the decimal point in the first place. The digits after the decimal point are really influenced by (sqrt(n))^X
2. If n is an integer and if X is even in step 1, then (sqrt(n))^X is an integer as well, since (sqrt(n))^X is the same as n^(X/2). Since X is even, X/2 is an integer. Since n is an integer, therefore it follows n^(X/2) is integer as well
3. Therefore first hundred digits after decimal point are 0.

[shaardula]

Problem: A goat is tied up with a rope of unit length. How much goat can roam? (or if there is grass - how much grass the goat can eat). (Goat is also restricted to move in a space of given dimension(s))

goat eat grass pi*(1+dx)^2, no?

ha! didn't read the full question.

[Amber G.]

I'm going to say 0.
Reason:
1. Forget all the integral numbers into the expression above because they don't play any part in the digits after the decimal point in the first place. The digits after the decimal point are really influenced by (sqrt(n))^X
2. If n is an integer and if X is even in step 1, then (sqrt(n))^X is an integer as well, since (sqrt(n))^X is the same as n^(X/2). Since X is even, X/2 is an integer. Since n is an integer, therefore it follows n^(X/2) is integer as well
3. Therefore first hundred digits after decimal point are 0.

How that argument stands out for a smaller even integer, say x=2, or 4?

[Amber G.]

In some strange way it would have been a little hard (or tricky) if I just asked "what is the first digit after the decimal" vs first hundred digits.. (by asking hundred digits one would "guess" that there is an easy way to do it - otherwise no one would ask the problem ...) (BTW, no use of calculator (or Maple/mathematica ) is assumed to be needed - and I guess calculator etc may not even help that much)

*************

Also, I don't know if some one noticed that
7+5 sqrt(2) = (1+sqrt(2))^3
So one could have used say (1+sqrt(2))^300..

*************
by the way Brhamgupta was first to notice that all the powers of (1+sqrt(2)) (eg (1+sqrt(2))^2 = 3+2sqrt(2)), (1+sqrt(2))^4 = 17+12 sqrt(2) etc...) have the property:
17^2-2*12^2 or 3^2-2*2^2 (or 7^2-2*5^2) each is plus or minus 1.... and these are the only such numbers which have this property (ie x^2-2*y^2 = + - 1, in integers) .. a method which European mathematicians did not know (to use it in similar problems) till many centuries later (and only after Brhamgupta's work was translated and became available in Europe )

[shaardula]

amber g and other folks,

against the spirit of this thread, can you kindly point me to some good sources on the connection between linear algebra and geometry - specifically conics? relation to ellipses and hyperbola i was able to figure out. i checked with some texts, to verify my work. but parabola and degenerate cases have me stumped.

what i am looking for is a unified parametrization for all the conics. does such a thing exist? agoston's book has a theorem without proof that the unit circle is projectively equivalent to all non-degenerate conics. i am not sure what he means by that. he has shown shown some examples with algebraic manipulation to illustrate. that much i understand. but how does this tie to linear algebra? or mebbe i am reading it all wrong.

[Amber G.]

You may already know but one of the best references (or at least starting point which will give further references) is wolfram..
try:
http://mathworld.wolfram.com/ConicSection.html

What you are looking for may be here:
http://www.geom.uiuc.edu/docs/reference ... ode28.html
or check its neighborhood :
eg:
http://www.geom.uiuc.edu/docs/reference ... ode26.html
or:
http://www.ipfw.edu/math/Coffman/pov/lsoc.html

Basically: All nondegenerate conics are projectively equivalent, so you might as well take (a unit) circle...

Hope this helps (at least a little

[shaardula]

amberg, thanks. i had not seen coffman. let me go through it.

Basically: All nondegenerate conics are projectively equivalent, so you might as well take (a unit) circle...

it hear it is so too. but i dunno.

have a nice weekend. i have 2 'projects' for the weekend. one coffman another armenT.

[ArmenT]

amberg, thanks. i had not seen coffman. let me go through it.

Basically: All nondegenerate conics are projectively equivalent, so you might as well take (a unit) circle...

it hear it is so too. but i dunno.

have a nice weekend. i have 2 'projects' for the weekend. one coffman another armenT.

Okay?? I'm happy to be included in some sort of 'project' but exactly what have I done to deserve this honor? Then again, SHQ is firmly convinced about my loony streak, so perhaps you're a psychiatrist studying the levels of lunacy among BRF posters.

[ArmenT]

AmberG: I should have mentioned that the "solution" came to me very early in the morning when I was trying to get some sleep and not succeeding at that very well. That's why I was surfing half-asleep and it sort of just occurred to me.

[vsunder]

Shaardula: There are two ways Linear Algebra enters conics and I am not sure what is your question. For computer vision purposes the projective characterization is most useful and people have written codes to implement all these algorithms which are 200 years old.

Let me explain this. First of all it seems you are confused what projectively equivalent means. I will show you now that
a parabola and a hyperbola are projectively equivalent and in the process the Linear Algebra will appear.

So here is a hyperbola

x^2-y^2=1. ------ (1)

And the parabola is y^2=x. ----- (2)

First these are the affine equations. To get the Projective eqn. of an affine curve you need to homogenize the eqn. so that
the polynomial becomes a homogeneous polynomial. So for (1) I would make a change of variable
x -----> X/Z and y-----> Y/Z. to get,

X^2-Y^2=Z^2 ----- (3)

This is the projective eqn. for the hyperbola. Why projective ? Because points in real projective space are represented by coordinates

P=( X,Y,Z) and if I multiply by a number m NON-ZERO I get Q= (mX,mY,mZ) and real projective space identifies
P and Q as the same. So as far as projective space goes P and Q are the SAME points. So for example in (3)
let X ----> mX, Y-----> mY, Z------> mZ you will see the equation remains UNCHANGED in total agreement that identified points also lie on the SAME curve.

Now projectivize the parabola. You will get,
Y^2=XZ -------- (4)

Now here comes the LINEAR ALGEBRA

DEFINITION: Two PROJECTIVE curves of any homogeneous degree ( but clearly have to be the same degree) are projectively equivalent IF AND ONLY IF there exists a 3X3 invertible MATRIX so that if (x,y.z) are points
on curve 1 then M(x,y,z) =(X,Y,Z) are the points on curve 2.

So you can FIX a standard curve and its coordinates like a reference curve and then your job is to find the 9 entries of the
3X3 matrix that will parametrize any other curve in your family. Lets see how this works in the example above.

So I will take the LINEAR TRANSFORMATION:

Y -----> Y, X------> U-V, Z ------> U+V. ----- (5)

Plug this into (4) you get,
Y^2= (U-V)(U+V)=U^2-V^2,

Y^2=U^2-V^2

That is a hyperbola or a projectivised ellipse.

You can also work out the matrix M from (5).

First column is (1, 0, -1), second column (0,1,0), third column ( 1,0,1) assuming the ordered basis are
(X, Y,Z) and ( U, Y,V). If you interchange the ordering of the basis off course the rows will interchange of M.
You can check M is invertible by seeing the determinant of M is NON-ZERO.

The algorithm for M in the general case to catch any conic is standard and people have written programs to do it.
The point I am making above is that even a "degenerate conic " like a parabola is PROJECTIVELY equivalent to
a NON-DEGENERATE conic by the totally trivial and elementary calculation above.

This is one way LINEAR ALGEBRA enters in parametrization problems for conics and other curves.

There is another way but heh I dont get paid but you ITvity types get paid huge amounts for finding matrices,
as I see, so .......

[Amber G.]

ArmenT- No harm, no foul. (Besides you answer was, although not exactly correct, was pretty close..

[vsunder]

Shaardula: Here is how what I wrote above is related to graphics and computer vision. Strange to explain all this to ITvity types. Since all of you are so gaga of conics being cut out of sections of cones lets start there. Well the most basic example of a projective transformation of the type I discussed above: the 3X3 matrix, is a perspective transformation.

So take the vertex of the cone as the perspective point. Now keep in mind the pencil of straight lines/rays that emanate from the vertex and run on the surface of the cone, these are the generators of the cone. Now cut the cone by planes.
Lets say I cut it two ways. In way 1; I cut it by plane 1 to get a circle. In way 2; I cut it by plane 2 to get a parabola say. Now the pencil of rays from the vertex pass through each point of the circle and hit a point of the parabola or pass through a point of the circle and do not hit the parabola except at infinity. My cone is considered an infinite cone.

Thus I have projectively transformed one may say DISTORTED in computer vision language the circle to the parabola.
What I did above is gave you a rigorous algebraic argument to what is trivially evident geometrically. Now the ITvity kids
are trying for example to take a distorted shape ( a parabola) and use the perspective and go back via a projective transformation and arrive at the circle the undistorted shape or vice versa depending on what you consider distorted. That is all you are trying to do.

For example, I take the sun and thats the perspective point. I look at the shadow of a house on the ground, and from that shadow I wish to reconstruct the image of the house facade. So you see projective transformations of the type I outlined at work. Its totally elementary no need to use wiki, diki or clicki, some thinking is all that is needed!!!

[sum]

Guys,
Does anyone know of a theorotical way of proving that the randomness of a LFSR with a base as a primitive polynomial of order,n=128 (with some random taps)?

Trying to simulate the LFSR results by running (2^128-1) results and checking if each output is highly random than the next is very time and memory consuming

[adityaS]

The optimal LFSR is a primitive polynomial of GF(2), are you looking for a proof of this, or a method to check whether a particular polynomial is primitive? If I remember right (please check!), you need to prove that the polynomial divides x^(2^128-1)-1 .

I assume you're been doing the autocorrelation? The "simpler" method if you already have all states is to see that all integers except 0 are covered.

[sum]

The optimal LFSR is a primitive polynomial of GF(2), are you looking for a proof of this, or a method to check whether a particular polynomial is primitive? If I remember right (please check!), you need to prove that the polynomial divides x^(2^128-1)-1 .

Im a noob in this area and so, am assuming that if we can prove that the polynomial chosen for the LFSR is primitive, any random seed will ensure that the pattern will repeat only after (2^128 -1) outputs and all the outputs are completely random. Please confirm.

Also, how can we check whether a Galois based LFSR or Fibonacci LFSR generates more random outputs(lesser correlation between successive outputs)?

[ArmenT]

Guys,
Does anyone know of a theorotical way of proving that the randomness of a LFSR with a base as a primitive polynomial of order,n=128 (with some random taps)?

One way would be to generate a large # of values and then apply a series of tests (chi-square, Kolmogorov-Smirnov, spectral test etc.) upon the set to see if they indicate any correlations. Donald Knuth ennumerates a series of tests in The Art of Computer Programming Vol II (sections 3.3.2 - 3.3.5 or so) that can be used to test randomness.

[adityaS]

sum: that's correct - depending on how you implement the LFSR, it should get "stuck" at either all 0's or all 1's - any other state means that the pattern generated has the longest period possible, which is because it basically transitions through all states in [1,2^n-1] . A different start seed only means a phase shifted output.

For the other, no idea, sorry. I would imagine that both LFSRs of length n will generate sequences of the same randomness, but I am likely wrong. (intuitively, both have different transition graphs, but their size is the same.)

[Raja Bose]

Going thru some of the last few pages of BR Maths kona, I was just wondering....despite having studied a lot of the stuff discussed here, the only things I remember are just basic fundamentals....rest all is as vague or non-existent as the ultimate Paki victory plan for getting Kashmir Whoever said that education is what remains after you forget what you learnt in school (and college), was right!

Great to see so many jingos indulge in maths/stats problems here with the deftness of a Dhruv helicopter of the Sarang team,....was wondering do you guys keep up-to-date with such stuff as part of your professions or is it a hobby onlee? In school and college I used to spend much time playing with olympiad problems (during my time Pitamber publications even came out with a book on olympiad problems) and later on some Putnam ones but now moi brain is rusted like PNS Ghazi onlee

[ArmenT]

^^^^
Bose Saar, can't speak for the others here, but I used to flunk math pretty regularly in school, especially during the latter half of 12th grade. In fact, I had the math teacher pretty concerned at one point when I only made 45/100 at the half-yearly exam and she actually held a special coaching class for me and the other class dunderheads. In my case, it was just pure boredom, because I was actually ahead of the class when 11th standard had started, but fell behind once the lessons got boring. Luckily for me, she succeeded in putting the fear of AoA in me, which made me start paying attention during her special class (at which point she realized I wasn't as dumb as I looked and kicked me out of there and told me to go home and study by myself). To this day, I owe Ms. TPS a big thank you for doing that.

Anyway, my interest in math was only rekindled a few years ago. I happened to read the book Fermat's Enigma by Simon Singh.

Actually, I'd read his other book first, which has a bit of mathematics as well (but not much):
The Code Book
and liked his writing style and so I bought Fermat's Enigma and got a bit hooked. While my math skills are pretty basic, in some cases I realize that I can actually solve the problem posed and that brings a new high. It's the logical part of it that makes it so appealing.

Other good books for leisurely reading:
1. History of Mathematics Vol I and II by D.E. Smith (found my copies in an old book store, you can get from Amazon too)
2. Vedic Mathematics by Jagadguru Swami Sri Bharati Krsna Tirthaji Maharaja (got my copy at some Hindu temple in LA a few years ago)

[adityaS]

probably OT, but does anyone else solve problems on Project Euler?

[Amber G.]

X-post from other thread ..
Its already beautiful Wednessday Morning in India and there is a measure news item developing ....

According to breaking news, three first year undergraduates from IIT Kanpur (Doshi, Joshi and Dandekar) with their Adviser Dr. Saxena has found a counter example of Fermat’s Last theorem.

Their main “tool” was neither a massive parallel nor a powerful super computer, but rather well known “google” applet known as “google calculator”

The Fermat’s last theorem speculates that, x^n+y^n=z^n has not solution in integers for any n>2. Though Fermat claimed that he had a “nice” proof of that but it was “too small to be put it in the margins”. For more details here is wikipedia link


Andrew Wiles was, believed to have proven the Theorem, but many mathematicians were skeptic that proof was defective. Now These four people have fond a counter example:

Counter example was found when they used google applet:

(If the link below does not work, simply:
1. go to www.google.com
2. type (in search) (1782^12+1841^12)^(1/12)
3. Hit enter:

link


As you can see from the link above:

((1 782^12) + (1 841^12))^(1 / 12) = 1 922
which results into:
1782^12 + 1841^12 = 1922^12
(or when n=12 gives a counter example)

Paper has been submitted to peer-reviewed journal, expect news to hit all the measure news outlet in about 24 ho

[Najunamar]

http://www.gamedev.net/community/forums ... _id=415662

I second that Amber G. Nice one - proof is here

[Raja Bose]

^^^

[Anujan]

Book Review - x-posting since I thought Rakshaks here might be interested.

A Sight digression from the usual politics, history type fare. Since BRF is a forum with much discussion, we always try to make logical arguments. But what exactly is logic ? What is "logical" ? Is it just a warm fuzzy vague feeling through which we decide what arguments are right and what are wrong, or is there a definite mathematical, rigorous definition along the lines of "addition" or "multiplication" ?

So I finished reading "Engines of Logic - Mathematicians and the origin of the computer" by Martin Davis. Martin davis is one of the greatest computer scientists alive and one of the greatest mathematicians of our time. This book however, does not delve deep into math, it is more of a very well researched history book, but with delightful reading. Many people do not know this, but the concept of a computer was conceptualized by mathematicians who dabbled in logic (logicians) and the most famous logicians in history were.... philosophers !! So the next time your friend gets drunk and thinks that he is a brilliant philosopher, point this out to him. The story starts with a famous mathematician, who dreamt of a machine to free "excellent men" from tedious calculations. He praised such a machine thus

And now that we may give final praise to the machine; we may say that it will be desirable to all who are engaged in computations which, it is well known, are the managers of financial affairs, the administrators of others' estates, merchants, surveyors, geographers, navigators, astronomers. . . For it is unworthy of excellent men to lose hours like slaves in the labor of calculations.

This scientist realized that to create such a machine english was not useful. Math at it existed then, was definitely not useful. In his own words

A script or language....that perfectly represents the relationship between our thoughts....how much better will it be to bring under mathematical laws, human reasoning, which is the most excellent and useful thing to have

Thus started a quest to define and discover (mathematical) logic. In case you wondered who this visionary mathematician was, it was Leibniz in circa 1680 !! Leibniz wanted a machine which could do calculation, based on a language that "perfectly captured the relationship between our thoughts" (a logical "program" as we call it today). Leibniz is regarded as the father of modern logic, he would write about 10,000 pages and not publish any. Because as he noted with sorrow, in one of the sheets

After so many logics, the logic I seek is yet to be discovered

This quest would last for centuries ! Tortuous progress would be made slowly. Martin Davis beautifully weaves history with funny and sad anecdotes, with individual triumph and loss, sadness and happiness with progress and setbacks in the field of mathematical logic. The reader gets to share the triumph of Boole, who realized if "true" is 1 and "false" is 0, if the "negation" of 1 were to be 0 and vice versa, if multiplication were regarded to be "AND", then the fact that a statement and its opposite cannot be true at the same time can be written as (negation of A) * A = 0. Which perfectly works out irrespective of whether A=0 or A=1. Thus Boolean logic was formed, which could capture, as algebra with purely symbolic operations some aspects of what we call as "logic". But Boole's logic was relegated as a curiosity in philosophy classes. Till Claude shannon noted that Boolean operators can be performed by electrical relays and voltage can be used to represent a 1 or a 0, thereby inventing the modern digital computer. But we are jumping ahead. Boole, regarded as a gentleman (in fact so courteous and well mannered that he intimidated women who felt "evil" and "inadequate" in front of such a saintly man), married a cranky lady. One day, while in his 40's Boole would catch a minor cold. His wife thought that his cold can be cured by wrapping him in freezing blankets. Boole died of pneumonia.

We get many such fascinating insights. Martin Davis tells us the story of Frege. The genius, much shunned by his collegues, poor, lacking a steady job, working away on an arcane branch of mathematics called "logic". Frege devotes decades of his life, towards the single minded pursuit of his magnum opus. However, recieves a letter from the young Bertrand Russell (of Russel's teapot fame), who points out a fatal flaw. Devastated, Frege adds a letter to the preface of his book

There is nothing worse that can happen to a scientist than to have his foundation collapse just as the work is finished. I have been placed in this position by Mr Bertrand Russell

This is integrity !! What russell unearthed, was a curious paradox - the Russell's paradox, which would defy explanation for decades. Martin Davis takes us to visit Cantor and talks about transfinite induction, proving that some infinities are bigger than others ! We visit Hilbert, who once, walked for weeks with torn trousers (his colleagues and students out of politeness, did not point it out, but asked his assistant to gently point it out to Hilbert). When Hilbert's assistant takes Hilbert for a walk near some thorny bushes and says "Probably one of the thorns has torn your trousers", Hilbert famously replied:

"Dont worry, I have been wearing this for weeks and nobody noticed"

We then read about Gödel - (of Gödel -'s incompleteness fame), who proved that no axiomatic system can be complete and consistent (the author explains in a easy way, what these concepts are). While traveling to the courthouse to gain american citizenship, Gödel - talked about numerous inconsistencies in the constitution of US and was furiously distracted by Einstein, who was afraid that the judge would deny him a citizenship. Alas, this would be of no use. When asked by the judge if US can ever become a dictatorship like Germany, Gödel went on to show, how constitutionally and in a manner consistent with the constitution a dictatorship may be established in the US ! We then visit Turing who was the first to how how a logic "program" may be mechanically implemented using a "turing machine" the precursor to a modern computer.

The book is a grand journey through history, personalities and anecdotes sprinkled with lucid and accessible explanations of concepts from logic and mathematics, all put together in a fascinating and way.

A Must read !!