BR Maths Corner-1

The Technology & Economic Forum is a venue to discuss issues pertaining to Technological and Economic developments in India. We request members to kindly stay within the mandate of this forum and keep their exchanges of views, on a civilised level, however vehemently any disagreement may be felt. All feedback regarding forum usage may be sent to the moderators using the Feedback Form or by clicking the Report Post Icon in any objectionable post for proper action. Please note that the views expressed by the Members and Moderators on these discussion boards are that of the individuals only and do not reflect the official policy or view of the Bharat-Rakshak.com Website. Copyright Violation is strictly prohibited and may result in revocation of your posting rights - please read the FAQ for full details. Users must also abide by the Forum Guidelines at all times.
Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 27 Dec 2012 08:04

Amber G. wrote:22!+1 is divisible by 23 ... (Why ? ..


Very interesting..
Those who are familiar with Number theory will recognize the above right away as Wilson's theorem.

What I did not know that Wilson did not prove it...and some say that it was first mentioned by Bhaskara almost a 1000 years ago!

Lagrange was the first one who published the proof in western journals in 18th century.
http://mathworld.wolfram.com/WilsonsTheorem.html
http://www-history.mcs.st-andrews.ac.uk/Biographies/Al-Haytham.html gives the proof Al-Haytham used to prove it in 1000AD..

See: http://www.bookdepository.co.uk/Wilsons-Theorem-Lambert-Surhone/9786130333003

There is some discussion here .. if Bhaskara really proved it ..(Can some check original sources..)
http://mathoverflow.net/questions/106848/at-what-times-were-people-interested-in-prime-numbers/106858#106858

ArmenT
BR Mainsite Crew
Posts: 4239
Joined: 10 Sep 2007 05:57
Location: Loud, Proud, Ugly American

Re: BR Maths Corner-1

Postby ArmenT » 27 Dec 2012 11:46

Amber G. wrote:what is the value of (this infinite sequence..

sqrt(1+sqrt(1+2*sqrt(1+3*sqrt(1+4*sqrt( ................................

Answer = 3. That was one of the first articles he posted to Journal of Indian Mathematical Society.

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 27 Dec 2012 20:11

^^Thanks. Also this also appeared here with some solutions given by Najunamarji ...:)
<link>
(BTW the answer, if I am not mistaken is 2)
Last edited by Amber G. on 28 Dec 2012 05:40, edited 1 time in total.

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 28 Dec 2012 05:37

Another personal favorite of mine from Ramanujan's work ...
(There is a long story attached to this, many may know it... it caused lot of excitement in 1970's..and the whole story became very famous)

Check it out, if you have a good calculator ... Ramanujan did it by hand.. and how did he know that result will come out to be an "integer"...:)

exp(pi*sqrt(1+2*3^4))=640320^3+744

See here

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 28 Dec 2012 11:00

Amber G. wrote:
Amber G. wrote:BTW:
Can you prove (it is not really very hard) that apart from 4, there is no other even value of n.


If you like to peek, here is a very simple proof of that...

If n is even, say n=2m then we want to find ..
2^n - 7 = y^2
or 4^m-7 = y^2
Let 2^m = x then
x^2 - 7 = y^2 or x^2 = Y^2 +7
Obviously we must have x>y,
also if y>3, then (y+1)^2 = y^2+2y+1 > y^2+7
so y+1>x>y which is not possible if both x and y are integers :)

Another simpler, much simpler proof given recently by a very young middle school student...

Write one of the steps in above as x^2-y^2 = 7 = (x+y)(x-y) => x+y=7, and x-y=1, rest is simple
(7 has only two factors , 7 and 1).

ArmenT
BR Mainsite Crew
Posts: 4239
Joined: 10 Sep 2007 05:57
Location: Loud, Proud, Ugly American

Re: BR Maths Corner-1

Postby ArmenT » 29 Dec 2012 10:24

Amber G. wrote:(BTW the answer, if I am not mistaken is 2)

Wiki says it is 3.
http://en.wikipedia.org/wiki/Ramanujan#Attention_from_mathematicians
Using this equation, the answer to the question posed in the Journal was simply 3.

Take that general equation in that section, let a = 0, n = 1 and x = 2 and we get the answer.

[edit]Actually you are right. The answer is 2. I didn't notice that the equation from the wiki page is slightly different from the one you posted. The equation on the wiki page evaluates to 3. However it forms part of the equation that you posted.
Your equation was: sqrt(1+sqrt(1+2*sqrt(1+3*sqrt(1+4*sqrt(...
Per the wiki article, we know that sqrt(1+2*sqrt(1+3*sqrt(1+4*sqrt(... evaluates to 3 if we take a = 0, n = 1 and x = 2.
So we can use that value in your equation, which now evaluates to:
sqrt(1 + 3)
which evaluates to 2.

Errare humanum est. :oops:
[/edit]

Vayutuvan
BRF Oldie
Posts: 10330
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 29 Dec 2012 11:02

Interestingly the above I read as sqrt(1+sqrt(2+sqrt(3+sqrt(4+...)))) and this too converges to

3.09...

vsunder
BRFite
Posts: 848
Joined: 06 Sep 1999 11:31
Location: Ulan Bator, Mongolia

Re: BR Maths Corner-1

Postby vsunder » 29 Dec 2012 20:54

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
ANNOUNCEMENT

This is to announce a Summer School in Analysis and Geometry to be held at
the Tata Institute of Fundamental Research (TIFR)-Bangalore Center, July 8-29th 2013.

http://math.tifrbng.res.in


The focus for the summer school is on Analysis and Geometry. The Summer school will be held under the aegis of TIFR, NBHM( National Board of Higher Mathematics) and NCM( National Center of Mathematics) and the DAE ( Department of Atomic Energy) from July 8-29th, 2013. Here is a link to the NCM web pages:

http://www.atmschools.org/

The webpages for this specific summer school on Analysis and Geometry are here:

http://atmschools.org/2013/ais/ang


The summer school has 4 parts, and the syllabi for all 4 parts were written by me.

The 4 parts are:

1. Harmonic and Fourier Analysis ( 15 lectures all delivered by me,
with tutorial help by Prof. Swagato Ray, Indian Statistical Institute-Kolkata),

2. Differential Topology ( 8+7 lectures
by Profs. A.R. Shastri ( IIT Bombay) and A. Adimurthi (TIFR-Bangalore)),

3. Differential Geometry (8+7 Lecture split, by Profs. R. Kulkarni ( IIT Bombay) + Debraj Chakrabarti
( TIFR)),

4. Variational Calculus and Non-Linear Functional Analysis ( 8+7 lectures split,
by Profs. Srikanth and Sandeep both from TIFR-Bangalore center).

You may find the detailed syllabus here:

http://atmschools.org/2013/ais/ang/spea ... d-syllabus

The detailed syllabus without the numerous typos on the webpage above
can also be downloaded from my homepage in PDF format.

http://www.math.rutgers.edu/~chanillo/s ... school.pdf

The last date for the application material to reach Prof. Srikanth ( TIFR-Bangalore)who is handling the applications is 3rd MARCH 2013. The application forms are to be found here:

http://atmschools.org/2013/ais/ang/application-form

Selected candidates will get train fare to Bangalore, and living allowance in Bangalore
and access to course notes etc.

I have already prepared 120 pages of typed notes as supplementary material
to my lectures( I will not lecture on the typed part) and 200 pages of handwritten notes
from where I will lecture. There are many, many novelties in my notes. Here is one part
of my typed notes on Caustics that supplement the course lecture on the Principle
of Stationary Phase and which I am showing as a sample:

http://www.math.rutgers.edu/~chanillo/caustics.pdf

The list of ALL programs offered by NCM for the calendar year 2013 are here:

http://atmschools.org/2013

There is going to be a Workshop Jan 4-9th 2014 FOLLOWING the summer school.
The workshop will feature three experts in Conformal and CR Geometry giving 3 lectures each.
The workshop has been listed on the NCM pages for 2013, though technically it will be in 2014,
but official sanction of the budget has not been received.

I shall be happy to answer any questions you have about the summer school
or the workshop ( names of speakers for the workshop etc) if you send your queries to

chanillo[atzzzxxxxyyy]math[dawt]rutgers[dawtxxxx]edu

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

Sincerely,
sc

svenkat
BRF Oldie
Posts: 4725
Joined: 19 May 2009 17:23

Re: BR Maths Corner-1

Postby svenkat » 29 Dec 2012 22:02

Sir,
If you do not mind,are you sagun channillo or v.s.sunder?

Are these two the same person.

vsunder
BRFite
Posts: 848
Joined: 06 Sep 1999 11:31
Location: Ulan Bator, Mongolia

Re: BR Maths Corner-1

Postby vsunder » 29 Dec 2012 22:20

First of all you need to spell my name correctly. Secondly I am the same person.
But what has that got to do with the summer school
announcement? If you have questions you should
have asked me by e-mail in private.

V.S. Sunder is a functional analyst working in Institute of Mathematical Sciences
in Chennai

http://www.imsc.res.in

He is a friend of mine and we spent a quarter together, Spring 1987 at UCLA, Los
Angeles, our offices were 3 doors apart, and he drove a convertible which he liked to drive very fast.
In fact he gave me a ride to the airport when I left for the long flight to India from LA for my
wedding.
I havent seen him in a long time,
the last time I saw him was in Bangalore when I visited Indian Statistical Institute
for a lecture and before he moved to IMSc, maybe 1998. Unfortunately and sadly he is not keeping
well these days though I am happy IMSc celebrated his 60th birthday. He writes a column
occassionally for the Hindu on MS and how he is negotiating the world with this ailment.

I hope that answers your question. I am still puzzled what this inane question
has to do with the summer school ?

SaiK
BRF Oldie
Posts: 36402
Joined: 29 Oct 2003 12:31
Location: NowHere

Re: BR Maths Corner-1

Postby SaiK » 30 Dec 2012 01:58

Can someone explain this more in layman's terms:
http://www.thehindu.com/news/american-m ... 253593.ece He said the so-called “deathbed puzzle” which, according to Ramanujan, was revealed to him by the goddess Namagiri, may unlock secrets about black holes. “We proved that Ramanujan was right. We found the formula explaining one of the visions that he believed came from his goddess. No one was talking about black holes back in the 1920s when Ramanujan first came up with mock modular forms, and yet, his work may unlock secrets about them,” said Professor Ono.

The Mail said that Ramanujan’s letter described several new functions that behaved differently from known theta functions, or modular forms, and yet closely mimicked them.

“Functions are equations that can be drawn as graphs on an axis, like a sine wave, and produce an output when computed for any chosen input or value. Ramanujan conjectured that his mock modular forms corresponded to the ordinary modular forms earlier identified by Carl Jacobi, and that both would wind up with similar outputs for roots of 1,” it said. Nobody at the time understood what the Indian mathematical genius was talking about.

“It wasn’t until 2002, through the work of Sander Zwegers, that we had a description of the functions that Ramanujan was writing about in 1920,” Prof. Ono said.

His team, which used modern mathematical tools to solve the puzzle, was “stunned” to find the function could be used even today.www.thehindu.com/news/american-mathematicians-solve-ramanujans-deathbed-puzzle/article4253593.ece

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 30 Dec 2012 11:55

[edit]Actually you are right. The answer is 2. I didn't notice that the equation from the wiki page is slightly different from the one you posted. The equation on the wiki page evaluates to 3. However it forms part of the equation that you posted.
Your equation was: sqrt(1+sqrt(1+2*sqrt(1+3*sqrt(1+4*sqrt(...
Per the wiki article, we know that sqrt(1+2*sqrt(1+3*sqrt(1+4*sqrt(... evaluates to 3 if we take a = 0, n = 1 and x = 2.
So we can use that value in your equation, which now evaluates to:
sqrt(1 + 3)
which evaluates to 2.


Thanks..

Some time ago, I saw this problem,... (Also from the Ramanujan's book)
S=sqrt(6+2*sqrt(7+3*sqrt(8+4*sqrt(9+ .....

Of course, if some one knew Ramanujan method, the answer will be clear.. without that it is very hard.. (The answer is 4)

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 30 Dec 2012 23:44

^^^ For those who want to see the beauty of the above, may like to see, how simple it becomes once
we get the idea Ramanujan used..(It even baffled Hardy and Littlewood , when the series was presented without any hint)..

Here is an easy method, for everyone ...

Let f(n) = n+2
then f(n) = sqrt(n^2+4n+4)
= sqrt (1+ n^2+4n+3)
= sqrt (1+ (n+1)(n+3))
or
f(n) = sqrt (1+(n+1)*f (n+1))

(And one goes f(n+1) = sqrt(1+(n+2)* f (n+2)) etc... so essentially you get the RHS of the series...
put n=0, and we get the answer f(n) = n+2 = 0+2 = 2

(Essentially f(0) = sqrt (1+f(1))
= sqrt (1+sqrt(1+2f(2)))
= sqrt (1+sqrt(1+ 2*sqrt(1+3 f(3))))
= sqrt (1+sqrt(1+ 2*sqrt(1+3*sqrt(1+4 f(4))))
and so on...)
Last edited by Amber G. on 31 Dec 2012 11:16, edited 1 time in total.

Vayutuvan
BRF Oldie
Posts: 10330
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 30 Dec 2012 23:58

That is beautiful.

Yayavar
BRF Oldie
Posts: 4774
Joined: 06 Jun 2008 10:55

Re: BR Maths Corner-1

Postby Yayavar » 02 Jan 2013 03:49

^^amazing.

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 28 Jan 2013 08:35

Meanwhile it may have been posted before .. for people in NY
Math in the Middle of Manhattan: NYC’s MoMath

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 28 Jan 2013 20:12

Okay, here is another problem from Ramanujan's ....

Most of Ramanujan's popular problem deal with number theory, analysis, infinite series and such, this is old fashioned geometry which any high-schooler can test using compass and ruler...

Try to prove it, (or at least construct it) ..(I did get the solution, so it is solvable)... At least enjoy it.
Let AB be a diameter and BC be a chord of a circle ABC. Bisect the minor arc BC at M; and draw a chord BN equal to half the length of the chord BC. Join AM. Describe two circles with A and B as centers and AM and BN as radii cutting each other at S and S′ and cutting the given circle again at the points M′ and N′ respectively. Join AN and BM intersecting at R and also join AN′ and BM′ intersecting at R′. Through B, draw a tangent to the given circle meeting AM and AM′ produced at Q and Q′ respectively. Produce AN and M′B to meet at P and also produce AN′ and MB to meet at P′. Show that the eight points PQRSS′R′Q′P′ are cyclic and that the circle passing through these points is orthogonal to the given circle ABC.

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 28 Jan 2013 20:56

ArmenT wrote:^^^^
Very funny :). I tried hacking some code together, but it seemed to run for ever. Then I recalled something weird I'd read a while ago (no, I'm not a math major, but I tend to remember odd stuff for some reason).
Brocard's Problem

On the other hand, I did get some practice in hacking lua code before shifting to the ol' standby once the values started getting really large.


ArmenT, you may like this recent article on Brocard/Ramanujan problem:
http://www.math.uiuc.edu/~berndt/articles/galway.pdf

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 28 Jan 2013 21:35

matrimc wrote:That is beautiful.

Okay, here is another one, similar and extremely simpler looking problem, also from Ramanujan ..

x = sqrt (8 - sqrt (8 + sqrt (8 - sqrt (8 + ......

Write x in some simpler form :)
(Okay use computer/calculator, if you have not seen the problem before..
(Hint: It is comparability not that hard, using math books and google, one should be able to find the solution .. and solution is fairly easy and elegant)

Vayutuvan
BRF Oldie
Posts: 10330
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 29 Jan 2013 00:56

I got the bounds -8 <= x <= 56. Is the above a Diophantine equation, i.e. does x have to be an integer? Then after a quick calculation in the head I think there is no solution. Can x be real or complex? Then using the bounds in a Newton-Raphson.

Vayutuvan
BRF Oldie
Posts: 10330
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 29 Jan 2013 01:00

x == 2.192582403567252

Here is some sage code

x = var('x')
find_root(x==sqrt(8-sqrt(8+x)),-8,56)

One can go to Sage Cell Server and paste the above code and evaluate for a solution.

vishvak
BR Mainsite Crew
Posts: 5660
Joined: 12 Aug 2011 21:19

Re: BR Maths Corner-1

Postby vishvak » 29 Jan 2013 01:17

Say x=sqrt(y -sqrt(y + sqrt(y ..
x^2 = y - sqrt(y -sqrt(y + sqrt(y ..
or x^2 = y - (x) .........[notice - (x)=> -sqrt(y +sqrt(y - sqrt(y .. i.e. inverse of +/- signs]
=> x^2 + x - y = 0
y=8=>
x^2 + x - 8 = 0 which is standard quadratic equation.

Using Image
where a=1, b=1, c=-8

x= (-1 +/- square-root(33) ) /2.

Gives two values as per original equation - taking one root as positive and the other as negative.

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 29 Jan 2013 02:00

vishvak wrote:Say x=sqrt(y -sqrt(y + sqrt(y ..
x^2 = y - sqrt(y -sqrt(y + sqrt(y ..
or x^2 = y - (x) .........[notice - (x)=> -sqrt(y +sqrt(y - sqrt(y .. i.e. inverse of +/- signs]
=> x^2 + x - y = 0
y=8=>
x^2 + x - 8 = 0 which is standard quadratic equation.


Vishvak - Yes, right approach but there seem to be a typo..
Shouldn't you get something like x^2 = y - sqrt(y+x) instead of x^2 + x - y = 0?
Last edited by Amber G. on 29 Jan 2013 02:11, edited 1 time in total.

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 29 Jan 2013 02:08

matrimc wrote:x == 2.192582403567252

I think the answer is a bit larger ...Should be around ...2.1848... (Now can one write this in some familiar form? :) )

Vayutuvan
BRF Oldie
Posts: 10330
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 29 Jan 2013 02:38

I was thinking something like the following.

Let x = sqrt(8-sqrt(8+sqrt(8-sqrt(8+...))))

The part in red is also x, so we have got

x = sqrt(8-sqrt(8+x))
x^2 = 8 - sqrt(8+x)

It looks like Sage's Newton-Raphson doesn't use enough precision.

ramana
Forum Moderator
Posts: 53936
Joined: 01 Jan 1970 05:30

Re: BR Maths Corner-1

Postby ramana » 29 Jan 2013 03:22

AmberG, Can you decode the article linked by SaiK please?

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 29 Jan 2013 04:20

^^^ Much has been written about this.. a few good links for aam admi ..
From sciencedaily
http://www.sciencedaily.com/releases/2012/12/121217091604.htm
From Newscientist
http://www.newscientist.com/article/mg21628904.200-mathematical-proof-reveals-magic-of-ramanujans-genius.html

Or wiki
http://en.wikipedia.org/wiki/Mock_modular_form#History

The math used here finds application in calculating entropy of a black hole so is interesting to Physicists...
""He had some sort of magic tricks that we don't understand," says Freeman Dyson regarding this.. As I said before, Dyson is one physicist who is one expert on Ramanujan math.

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 30 Jan 2013 19:50

Amber G. wrote:
matrimc wrote:That is beautiful.

Okay, here is another one, similar and extremely simpler looking problem, also from Ramanujan ..

x = sqrt (8 - sqrt (8 + sqrt (8 - sqrt (8 + ......

Write x in some simpler form :)
(Okay use computer/calculator, if you have not seen the problem before..
(Hint: It is comparability not that hard, using math books and google, one should be able to find the solution .. and solution is fairly easy and elegant)


Sorry but a correction and clarification for the above, please read carefully.
For the problem mentioned above the answer given by Matrimc is numerically correct, so let me give an explanation for the below...

Amber G. wrote:
matrimc wrote:x == 2.192582403567252

I think the answer is a bit larger ...Should be around ...2.1848... (Now can one write this in some familiar form? :) )



The exact answer for above is, with a little algebra, of course: (sqrt(29)-1)/2)

(For those who will like to see the method, you have to solve
x^2 = 8 - sqrt(x+8)
which becomes
(x^2-8)^2 = x+8
or x^4-16x^2 - x + 56 = 0
or (x^2-x-8)(x^+x-7) = 0

Since the answer is positive and less than sqrt(8), only answer is (sqrt(29)-1)/2 which is approx = 2.19258 ...

For the rest of the comments, and the reason I mentioned "2.1848" ...please see the next post.
Last edited by Amber G. on 30 Jan 2013 21:14, edited 1 time in total.

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 30 Jan 2013 20:49

What is important to note the problem give above differs slightly from the one given by Ramanujan.
The original problem (given by R) was/is:

x = sqrt (8 - sqrt (8 + sqrt (8 - sqrt (8 - ......

That is, the cycle of sign(s) is THREE and not two, IOW signs go: - + - ; - + -; - + -

The answer 2.1848 for this original problem (given above) ... and the solution is

1 + 2*sqrt(3)*sin(20 degrees)
(which is approx 2.1848 as said before)

Now how do you get this?

(BTW, the equation originated with R's problem of solving a set of three equation,
x^2 = y+a, y^2 = z+a, and z^2= x+a )

(Again, the problem is not very hard, but the way it lands itself into elegant answer is nice)

Hope this is interesting to all ...

shaardula
BRF Oldie
Posts: 2591
Joined: 17 Apr 2006 20:02

Re: BR Maths Corner-1

Postby shaardula » 31 Jan 2013 21:03

after all these years, could we finally state that probability has emerged as the undisputed language for modeling complexity and uncertainty? isn't use of probability as a measure of uncertainty one of the most fundamental success stories of our times?

Vayutuvan
BRF Oldie
Posts: 10330
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 01 Feb 2013 02:14

I don't agree with such a blanket statement.

Complexity traditionally was used in two different senses. One is computational complexity which originally did not involve any probability theory and the other is complex systems which is related to chaos.

In 1961 Alan Cobham and Jack Edmonds introduced the concept of deriving the number of steps an algorithm would take as a function of input size. This was the start of computational complexity. Algorithm design and analysis (including worst case analysis) arises out of these concepts.

The other seminal development started at around the same time (1960 by Solomonoff) was the area of Kolmogrorv Complexity (which should be properly called as Solomonoff-Kolmogorov-Chaitin Complexity) which is the basis for the area called Algorithmic Information Theory which deals with descriptional complexity. This is a combination of Shannon's information theory and Computational Complexity where the former is based on probability theory.

Turing Machine is the model of computation.

From my limited reading about complex systems, I say the theory was developed from nonlinear physical processes.

Cellular Automata of von Neumann is the model of computation.

Recursive function theory and Turing Machines are proved to be equivalent , i.e. Turing Machines are capable of computing all the functions that Recursive Function Theory can compute and vice versa. Stephen Wolfram - a physicist - proved that cellular automata are equivalent to Turing Machines.

In other words, any language that is Turing Complete (roughly speaking same power as a Turing Machine) can model complexity however you define complexity. Please consider that any imperative language that has "branch on zero", and is able to maintain arbitrary number of variables is Turing Complete with obe caveat. Physical realizations of a Turing Machine have only limited memory and thus they are really Linear Bounded Automata - or an LBA - which are strictly less powerful than Turing Machines. But, since LBAs can recognize Context Sensitive Languages (all natural languages are CSLs), these can be considered Turing Machines for all practical purposes. The argument is as follows: we can only express ideas in natural languages and these problems can be recognized by the physical realizations of the LBA subset of the Turing Machines. Since we do not even have the means to pose problems that only a Turing Machine can solve, the LBA subset of the Turing Machines is good for our purposes.

Vayutuvan
BRF Oldie
Posts: 10330
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 01 Feb 2013 04:33

Shardula ji

Also look at the wiki page on Digital Physics (a controversial theory) and criticism along with papers/book by Konrad Zuse and David Deutch (physicist who gave the mathmatical construction of a Quantum Computer which is freely available on the net).

shaardula
BRF Oldie
Posts: 2591
Joined: 17 Apr 2006 20:02

Re: BR Maths Corner-1

Postby shaardula » 01 Feb 2013 09:19

thanks matrimc-ji. mistake about complexity was reading something about model complexity and in the euphoria overstated. mainly uncertainty. i'm just amazed at the pervasiveness of probability for modeling on uncertainty in so many applications.

kasthuri
BRFite
Posts: 411
Joined: 02 Jan 2009 08:17
Location: Mount Doom in Mordor

Re: BR Maths Corner-1

Postby kasthuri » 01 Feb 2013 10:30

shaardula wrote:thanks matrimc-ji. mistake about complexity was reading something about model complexity and in the euphoria overstated. mainly uncertainty. i'm just amazed at the pervasiveness of probability for modeling on uncertainty in so many applications.

A rigorous theoretical framework is critical for any field to flourish. The greatest triumph of modern mathematics is the axiomatization of the probability theory by Kolmogorov. This along with Lesbegue's thesis on measure and integration laid a firm foundation (actually, on the notion of integrabilty and hence expectation) to probability and put several debates to rest. Lesbegue's theory is a cornerstone of modern day probability theory which could not have seen the light with just Riemann integral alone (as you may know Riemann integral has lots of problems, especially when it comes to convergence of integrable functions which Lesbesgue integral handles beautifully). If Kolmogorov can be called the father of probability theory, then Lesbesgue can rightfully be called the grandfather.

Isn't it amazing that the notion of probability which attempts to capture indeterminism has a deterministic axiomatic basis? It is like generating random numbers through a fixed seed - usually results in pseudorandom numbers. So are the theories that are explained through probability are really pseudo-real theories? I will let you ponder about this question.

shaardula
BRF Oldie
Posts: 2591
Joined: 17 Apr 2006 20:02

Re: BR Maths Corner-1

Postby shaardula » 01 Feb 2013 19:37

A rigorous theoretical framework is critical for any field to flourish. The greatest triumph of modern mathematics is the axiomatization of the probability theory by Kolmogorov. This along with Lesbegue's thesis on measure and integration laid a firm foundation (actually, on the notion of integrabilty and hence expectation) to probability and put several debates to rest. Lesbegue's theory is a cornerstone of modern day probability theory which could not have seen the light with just Riemann integral alone (as you may know Riemann integral has lots of problems, especially when it comes to convergence of integrable functions which Lesbesgue integral handles beautifully). If Kolmogorov can be called the father of probability theory, then Lesbesgue can rightfully be called the grandfather.


agree. i would also add fields and sets to the above. i have a very basic understanding of measure theory though, just enough to damage something or hurt myself. for someone only exposed to dealing with physical measures, it was stunning to see probability holding up its properties under all the operations and transformations. For something that is really arbitrarily assigned, it is really amazing that it has a consistent behavior, as if it were a latent physical quantity.

talking of arbitrary, i wonder if 'value' as used in economics/finance is a measure? :)

Isn't it amazing that the notion of probability which attempts to capture indeterminism has a deterministic axiomatic basis? It is like generating random numbers through a fixed seed - usually results in pseudorandom numbers. So are the theories that are explained through probability are really pseudo-real theories? I will let you ponder about this question.


This i didnot understand, why you say so. Its not a generative process, is it? There is nothing that is sitting there and spitting probabilities. Its just a measure of uncertainty, no? further more, uncertainty itself is the difference between model and "reality"? sort of a language to describe a condition. as a grammer for that language, the theory itself is true in that it is consistent and complete. no?

kasthuri
BRFite
Posts: 411
Joined: 02 Jan 2009 08:17
Location: Mount Doom in Mordor

Re: BR Maths Corner-1

Postby kasthuri » 02 Feb 2013 02:31

shaardula wrote: i would also add fields and sets to the above.


You are right, the contributions of Russell and Whitehead cannot be forgotten. And especially Borel sets and measures.

for someone only exposed to dealing with physical measures, it was stunning to see probability holding up its properties under all the operations and transformations. For something that is really arbitrarily assigned, it is really amazing that it has a consistent behavior, as if it were a latent physical quantity. For something that is really arbitrarily assigned, it is really amazing that it has a consistent behavior, as if it were a latent physical quantity.


I don't quite get it. If you are talking about operations such as the additivity of expectations, it follows from the additivity of measures. If you are talking about convolutions, it follows from the additivity of underlying random variables. What do you mean by "properties under all operations and transformations"?

kasthuri wrote:Isn't it amazing that the notion of probability which attempts to capture indeterminism has a deterministic axiomatic basis? It is like generating random numbers through a fixed seed - usually results in pseudorandom numbers. So are the theories that are explained through probability are really pseudo-real theories? I will let you ponder about this question.


This i didnot understand, why you say so. Its not a generative process, is it? There is nothing that is sitting there and spitting probabilities. Its just a measure of uncertainty, no? further more, uncertainty itself is the difference between model and "reality"? sort of a language to describe a condition. as a grammer for that language, the theory itself is true in that it is consistent and complete. no?


This is just a metaphor and should be construed only as a metaphor. In my humble opinion, probability does not measure uncertainty if uncertainty is thought as a gap between model and reality. The gap between model and reality is like the gap between rational numbers and irrational numbers. Irrational numbers have a cardinality of continuum whereas rationals are countable. The gap cannot be closed. Probabilistic models provide a good approximation to the reality and can remain only as an approximation, just as how the rationals can approximate the irrationals. Can we build better probabilistic models, sure yeah, why not? But they don't measure the gap (or "uncertainty" in your terms). They provide better approximation and nothing more. In my world, grammar are the axioms of probability, languages are the probabilistic models and realities are physical realities which the languages try to explain. You are right, a theory is true when it is consistent and complete. However, probability theory even as a first/second order logic cannot be complete and so to imagine that it can describe "reality" is a far-fetching thought, imho!

Amber G.
BRF Oldie
Posts: 6809
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 02 Feb 2013 23:09


Let x = sqrt(8-sqrt(8+sqrt(8-sqrt(8+...))))

The part in red is also x, so we have got

x = sqrt(8-sqrt(8+x))
x^2 = 8 - sqrt(8+x)

It looks like Sage's Newton-Raphson doesn't use enough precision.


Here is one method, which requires simple high school math ...

First let us write the first eq as:
x = sqrt (8-y)
where y = sqrt(8+x)
So
x^2 = 8 - y (*)
y^2 = 8 + x (**)
(obviously 0<x < sqrt(8), while y > sqrt(8) etc and y>x etc..)
Subtraction (*) from (**) we get
y^2 - x^2 = x+y
or (y+x)(y-x) = x+y
(since x+y is not zero, - both x and y >0 - we can divide it on both side and get
y-x = 1

Rest is simple, substitute this in (*) to get x^2 = 8 - 1 -x = 7 - x
and only positive root is x = (sqrt(29) - 1) /2
(And Sage's Newton-Raphson's method actually gives very good result)

Nandu
BRF Oldie
Posts: 2195
Joined: 08 Jan 2002 12:31

Re: BR Maths Corner-1

Postby Nandu » 02 Feb 2013 23:55

I came across this recently. It is a programming problem with a mathematical solution.

Given two finite sequences of numbers a[i], and b[i], which are of the same length n, we need to determine if they are the same, up to permutations.

The usual programmer's way is to sort both arrays and then sequentially compare for equality, but for small values of n, (say n <= 5). This might be faster.

If, for j=1 to n, (n >= 0), sum(a[i]^j) = sum(b[i]^j), then b is a permutation of a.

Question: Can you prove this?

Vayutuvan
BRF Oldie
Posts: 10330
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 03 Feb 2013 05:58

I haven't tried to prove what you asked, but as for time, for small n, the method you proposed will take $\Omega(n^2)$ (because you have a double loop and in the inner loop you need to compute the power also). A simple O(n^2) algorithm by simply comparing each number from one list with all the numbers in the other list and striking off from the second list if found and one final pass to check that all the numbers in the second list are marked off will do it. If the second list is immutable, then an extra mark vector (of char type) of size n will do the job in O(n^2). The constants are very low which is the reason why one would use this for small n.

kasthuri
BRFite
Posts: 411
Joined: 02 Jan 2009 08:17
Location: Mount Doom in Mordor

Re: BR Maths Corner-1

Postby kasthuri » 03 Feb 2013 08:22

^^^ As it is known that any comparison based algorithm would take O(n^2) (at the worst case) and an average case of O(nlogn), if the range of the numbers are known, can we do some kind of counting sort/bucket sort? The reason is, while we are binning it, we may see from which list the numbers came from and thus matching the pairs. This would give us a complexity to O(n) on the average case. How about concatenating the list with a pointer to which list the number came from, and then sorting the '2n' numbers?

Added later: The lowest bound for any comparison based sorting would be O(nlogn) but since counting/bucket/radix sort does not make any comparison, we can achieve even smaller bounds, at least for sorting.


Return to “Technology & Economic Forum”

Who is online

Users browsing this forum: Google [Bot] and 13 guests