SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
GrenvilleCroll
Topic Author
Posts: 359
Joined: July 29th, 2004, 8:03 am

Prove that E0 is transcendental

March 14th, 2015, 10:55 pm

Consider the non-negative natural numbers: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19......encode primes as 1, the rest as 0E = 0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1....The number E0 is001.10101000101000101.... (ie the primes)E0 is irrational in every base due to a simple proof which shows that the binary pattern of the primes, E, is not periodic.Since the location of the (binary) point is arbitrary, if we locate the point one place to the right, we obtain E1 (=0011.0101....).So E1/E0 is the integer 2.Since E0 is irrational in every number base, we are led to the interesting aphorism:Every integer greater than one is the ratio of two irrational numbers. Each of these irrational numbers expresses the infinite pattern of the prime numbers.The Brainteaser is: Prove that E0 is transcendentalNote that C0 = 110.01010111010111010.... (ie the composites)and E0+C0 = 111.11111111111111111......All contributions acknowledged.Regards Grenville
 
User avatar
CommodityQuant
Posts: 215
Joined: July 5th, 2007, 6:16 am

Prove that E0 is transcendental

March 16th, 2015, 10:51 am

No, this is almost certainly not a legitimate brainteaser because it is much too difficult. Almost nothing that is not immediately obvious about the primes can be proved by elementary means. The problem may even be unsolved. It's a bit like saying "Here's a brainteaser. Prove or disprove the Riemann Hypothesis."It has happened before that job interviews contain problems that are much too difficult. Perhaps the interviewer would want you to talk about the density of the primes (1/log(n) ) and to mention that there are theorems in transcendental number theory which say that an infinite series can sometimes be proven to be transcendental if the terms diminish very rapidly in absolute value. For example, e is transcendental and so is the sum of 10^(-n!).To research the problem, simply google "transcendental number theory" and follow the links.To make a serious contribution to this "brainteaser" probably takes at least three years.CommodityQuant
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

Prove that E0 is transcendental

March 16th, 2015, 12:02 pm

Although most "brainteasers" are selected to be answerable after a few minutes of clever logic and pencil&paper computation, there are useful interview questions that call for the job candidate to discuss how they would solve a larger problem even if the final answer can't be produced quickly. And certainly one of the most important skills for a higher-level quant is the ability to recognize when a problem has shifted from the "we can solve this in 3 minutes" category to the "this might take 3 years" category. As an interviewer, it would be very useful to see how the candidate admits they cannot provide an answer in the scope of the interview time slot.This question certainly teases the brain even if it's much deeper and harder than the typical logic puzzle or turn-the-crank-in-your-head probability question.
 
User avatar
CommodityQuant
Posts: 215
Joined: July 5th, 2007, 6:16 am

Prove that E0 is transcendental

March 16th, 2015, 1:00 pm

QuoteOriginally posted by: outrunI know little about numbertheory, but if E0 wasn't transcendental then we would have a serious encryption problem (like in RSA) from what I can see. Even though non-periodic, the patterns of primes would then have structure, possibly predictabe, making factoring easier?Outrun,I don't think your claim can possibly be made by someone who knows "little about number theory." Either your claim doesn't really make much sense or you do know about transcendental number theory. Please can you justify your statement a bit? In particular note that, the sum of 10^(-n!) _is_ transcendental despite the total predictability of the pattern of 1s and 0s.CommodityQuant
 
User avatar
Cuchulainn
Posts: 61084
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Prove that E0 is transcendental

March 16th, 2015, 7:41 pm

A discussion between pure mathematician and CS guys?
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget
 
User avatar
GrenvilleCroll
Topic Author
Posts: 359
Joined: July 29th, 2004, 8:03 am

Prove that E0 is transcendental

March 16th, 2015, 9:33 pm

It seems obvious that E0 must be transcendental, else there exists a polynomial which has as one of its roots a number which expresses exactly the infinite pattern of the primes. I am hoping I have missed something blindingly obvious, or have failed to make a few simple connections between a few useful truths.For instance there is a solid proof that no polynomial can produce only primes (Google "No polynomial can produce only primes") for the book chapter by H.Riesel. It would seem easy to leap from this classic result (due to Legendre I believe) to the proof of E0's transcendence. But I can't see which way to jump. I have taken a look at Sturmian Sequences and Liouville numbers to no avail.Also, I struggle with E0 + C0. This is clearly 111.1111111.... But is E0 + C0 actually 1000? E.G. In decimal, 1/3 + 2/3 = 1. In Binary 1/11 = 0.010101010101... and 10/11 = 0.1010101010101.... So 1/11 + 10/11 = 0.11111111111... but 1/11 + 10/11 = 1. Somehow the inifinite "last" bit flips and ripples up the binary digit sequence such that in binary one third plus two thirds equals 1 (as it must!). So does the same apply to the infinite, irrational and complementary sequences of E0 and C0?. If it does then there is a trivial conseqence of taking exponents:e^(E0+C0) = e^8 (e^8 is transcendental) soe^E0 * e^C0 = e^8in which case either or both of e^E0 and e^C0 are transcendental.And how far does that get us!
 
User avatar
Cuchulainn
Posts: 61084
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Prove that E0 is transcendental

March 17th, 2015, 5:39 am

QuoteIt seems obvious that E0 must be transcendental,You cannot say that; it must be proved or disproved, mathematically.
Last edited by Cuchulainn on March 16th, 2015, 11:00 pm, edited 1 time in total.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget
 
User avatar
wileysw
Posts: 593
Joined: December 9th, 2006, 6:13 pm

Prove that E0 is transcendental

March 17th, 2015, 6:07 am

Grenville,i think your question is still open. here are few things that might be helpful for you to search around:(1) the base 2 case of your number E0 is known as the "Prime constant";(2) since it's apparently not normal, which is indeed a strong indication that it is transcendental, as all irrational algebraic numbers are conjectured to be normal (note on the contrary, normal numbers can be transcendental, e.g., Champernowne constant). one related number is Copeland-Erdos number. it's normal in all base but is also conjectured to be transcendental. your number in this sense actually falls in an "easier" category. if you wish to pursue this route, not too sure what the state of the art is, but try the papers by Boris Adamczewski. he has established that expansion with low complexity cannot be algebraic irrational (and try also searching "7/3-powers" which is a pattern of 'XXx', where 'X' is a string and 'x' is the first 1/3 substring of 'X'). but this approach might not be effective, as prime numbers do exhibit patterns (e.g., twin prime conjecture indicates that '101' occurs infinitely often) and seems established results/patterns are just not strong enough----- ----- ----- ----- -----btw, don't quite get some of what you commented. e.g., the product of any integer and any irrational number (with whatever interesting patterns one finds) is by definition an irrational number; also 0.111... in base 2 is 1, as it's just the infinite sum of 2^(-n) from n=1 to infinity
Last edited by wileysw on March 16th, 2015, 11:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 61084
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Prove that E0 is transcendental

March 17th, 2015, 2:21 pm

The equality of 0.9999 and 1, for all bases..More precisely, Dedekind introduced his cuts. For example, the number 1 is the set of all rational numbers less than 1. Dedekind cut The example of sqrt(2) is useful.This is real analysis 1st year maths. Rudin.
Last edited by Cuchulainn on March 16th, 2015, 11:00 pm, edited 1 time in total.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget
 
User avatar
GrenvilleCroll
Topic Author
Posts: 359
Joined: July 29th, 2004, 8:03 am

Prove that E0 is transcendental

March 17th, 2015, 10:59 pm

Hmm,So I just rediscovered the prime constant, which is already proven irrational - in, er 1938 - Hardy and Wright, page 112, - thanks wileysw. How the f*ck did I miss that? And I demonstrated that I didn't do a first year analysis course - thanks cuch & outrun - but I can forgive myself as I did straight CS all those years ago.The question of E0's transcendence is still open as wileysw suggests, however its been open since about 1938. So commodityquant is rightly miffed that its an outrageous brainteaser. Its a wicked interview question for traden4alpha.The outcomes of this little brainteaser are:1) The overwhelming benefits of peer review2) Peer review in Wilmott is exceptionaland3) Prove that E0 is transcendentalHave fun!RegardsGrenville
Last edited by GrenvilleCroll on March 17th, 2015, 11:00 pm, edited 1 time in total.
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On