Author 
Topic: Combinations of Pi and Sqrt(2) (Read 18278 times) 

Michael Dagg
Guest


Re: Combinations of Pi and Sqrt(2)
« Reply #25 on: Apr 14^{th}, 2005, 9:27pm » 
Quote Modify
Remove

Your group representation is a very good analogy. What if I asked if you could make the same analogy with a ring instead of a group and never mind whether it is finite or not, paying no attention to ideals or nilpotent elements?  just asking of course. It should be noted that when you stated that "The surprising answer is that you can't" certain holds with both finite and infinite problems and is applicable in such a wide variety of areas that we cannot possibly enumerate them all (enumerate is a bad word here but convenient). All we need to know is a good working model of one and the rest will follow. Does this make sense? Regards, MD


IP Logged 



Deedlit
Senior Riddler
Posts: 476


Re: Combinations of Pi and Sqrt(2)
« Reply #26 on: Apr 15^{th}, 2005, 3:38pm » 
Quote Modify

on Apr 14^{th}, 2005, 9:27pm, Michael Dagg wrote:Your group representation is a very good analogy. What if I asked if you could make the same analogy with a ring instead of a group and never mind whether it is finite or not, paying no attention to ideals or nilpotent elements?  just asking of course. 
 Well, there is the ideal membership problem for rings, which is unsolvable. As for the word problem, you can take any group G and form a Galgebra over something like Z_{2}, so rings inherit the unsolvability of the word problem for groups. If we look at the additive word problem instead, the abelian group word problem is solvable. Quote: It should be noted that when you stated that "The surprising answer is that you can't" certain holds with both finite and infinite problems and is applicable in such a wide variety of areas that we cannot possibly enumerate them all (enumerate is a bad word here but convenient). All we need to know is a good working model of one and the rest will follow. Does this make sense? 
 Brilliant grammar on my part  that of course should be "The surprising answer is that there isn't." I'm not following you on the "good working model." Can you elucidate?


IP Logged 



Michael Dagg
Guest


Re: Combinations of Pi and Sqrt(2)
« Reply #27 on: Apr 15^{th}, 2005, 8:08pm » 
Quote Modify
Remove

on Apr 15^{th}, 2005, 3:38pm, Deedlit wrote: Brilliant grammar on my part  that of course should be "The surprising answer is that there isn't." I'm not following you on the "good working model." Can you elucidate? 
 I like your previous statement over this one. My fault for not going further with the working model statement. I wasn't referring to some magic formula but was simply going on about analogies and as a collection they form a working model in every sense  that is, if they are used as such, and when so, they provide us with a powerful set reasoning abilities. What I just said did not tell anyone anything new but the importance of analogies is so profound such that we could never do without them in mathematics. The best working model you will ever have will be a collection of analogies and what is in that collection of analogies is entirely up to you. Regards, MD


IP Logged 



River Phoenix
Guest


Re: Combinations of Pi and Sqrt(2)
« Reply #28 on: May 22^{nd}, 2005, 1:42pm » 
Quote Modify
Remove

I'm not sure how much sense this problem makes: You are "given X" (by itself, and not as an explicit linear combination). But X is irrational: how can we be given X... precisely the problem is unsolvable, even with brute force. I think we would need some form of error bounds.


IP Logged 



River Phoenix
Guest


Re: Combinations of Pi and Sqrt(2)
« Reply #29 on: May 22^{nd}, 2005, 1:43pm » 
Quote Modify
Remove

I see that the uncountability of X's has already been mentioned, sorry


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Combinations of Pi and Sqrt(2)
« Reply #30 on: May 23^{rd}, 2005, 3:06pm » 
Quote Modify

You cannot be given the exact value for X, but you could be given the means to calculate X to any desired precision, which is equivalent. Note that we are restricting ourselves to X which are representable. However, we do run into this problem: Let S = {x : x = A*[sqrt]2 + B*[pi], for integers A, B}. Isolated points of S (if any exist) can be uniquely determined from X in a finite amount of time. But if X is an accumulation point of S, then infinite precision is necessary to distinguish the A and B for X from all others, and thus infinite calculation time. I have not examined the matter, but I believe S is dense in the real line, so every point of S is an accumulation point. If so, then no, the problem is not solvable.

« Last Edit: May 23^{rd}, 2005, 3:06pm by Icarus » 
IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



Deedlit
Senior Riddler
Posts: 476


Re: Combinations of Pi and Sqrt(2)
« Reply #31 on: May 23^{rd}, 2005, 3:20pm » 
Quote Modify

S is in fact dense. Proof: Divide R/(sqrt(2) Z) into disjoint intervals of length less than some postive number e. If there are n intervals, among the first n+1 multiples of pi, there will be two in the same interval. Since pi and sqrt(2) are incommensurate, 0 < (ab)pi < e mod sqrt(2), and so 0 < (ab)pi + c sqrt(2) < e. Since e was arbitrary, the linear combinations of pi and sqrt(2) are dense.

« Last Edit: May 23^{rd}, 2005, 3:26pm by Deedlit » 
IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Combinations of Pi and Sqrt(2)
« Reply #32 on: May 23^{rd}, 2005, 4:33pm » 
Quote Modify

Thanks! I've got to stop being so lazy. Rereading my post, I don't think it is as clear as I intended. So I thought I would try to expand a bit: If we only know X to a certain precision, say h, then we can at best restrict the possible values of A, B to those for which A[sqrt]2 + B[pi] [in] [Xh, X+h]. Since S is dense, there are an infinite number of pairs (A, B) satisfying this condition. This holds for any value of h>0. Therefore, in order to uniquely identify A, B, we need h = 0. I.e. we must know the exact value of X. Since X is irrational, no general (i.e. applicable to all irrational numbers) means of expressing X exactly with finite resources is available. Therefore the problem is unsolvable.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



SWF
Uberpuzzler
Posts: 871


Re: Combinations of Pi and Sqrt(2)
« Reply #33 on: May 23^{rd}, 2005, 9:58pm » 
Quote Modify

The first page of this thread gives a couple of different x that may both be rewritten as A*pi + B*sqrt(2).


IP Logged 



Deedlit
Senior Riddler
Posts: 476


Re: Combinations of Pi and Sqrt(2)
« Reply #34 on: May 23^{rd}, 2005, 10:27pm » 
Quote Modify

Indeed. So far, we have made the following observations: 1. If we pick a real number at random by some natural continuous distribution, the probability that it is a linear combination of pi and sqrt(2) is zero. 2. If we are restricted to finite approximations only, there are infinitely many possibilities in any neighborhood of any real number. 3. There seems to be no hope of finding a linear combination without restricting the means of description. In terms of restricting the description, here are two fairly strict classes of expressions: A: Sum[a_{i}], where the a_{i} are rational numbers. B: The integers closed under +, , *, /, square root, and the trigonometric functions. Even with these restrictions, an algorithm looks unfeasible.

« Last Edit: May 23^{rd}, 2005, 10:28pm by Deedlit » 
IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Combinations of Pi and Sqrt(2)
« Reply #35 on: May 24^{th}, 2005, 3:04pm » 
Quote Modify

on May 23^{rd}, 2005, 9:58pm, SWF wrote:The first page of this thread gives a couple of different x that may both be rewritten as A*pi + B*sqrt(2). 
 This is why I said determining A, B from some general means of expressing X is impossible. There are plenty of ways to be given an X so that finding A and B is easy. For example if you are told that X = 4*sin(pi/4) + 8*tan^{1}(1), figuring out A and B is trivial. The point I am making is: if you are given an expression for X in a form that can be applied to any irrational number, then even if you are guaranteed that integers A, B exist, there will be no way to calculate them in a finite amount of time. Particularly, this is true if you are given nothing more than some means to calculate X's decimal expansion to any desired accuracy. It is only for special cases that finitetime calculation is possible. Note also that every possible X has at least one expression for which determining A and B is easy: the trivial case where X is given to you as "A*pi + B*sqrt(2)".


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



SWF
Uberpuzzler
Posts: 871


Re: Combinations of Pi and Sqrt(2)
« Reply #36 on: May 24^{th}, 2005, 8:46pm » 
Quote Modify

I was responding to River Phoenix's remarks wondering how such an X could possibly be written down (presumably meaning nontrivial forms), not questioning any other point.


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Combinations of Pi and Sqrt(2)
« Reply #37 on: May 25^{th}, 2005, 4:45pm » 
Quote Modify

Oh. My apologies for misinterpreting the intent of your comment.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



River Phoenix
Junior Member
Gender:
Posts: 125


Re: Combinations of Pi and Sqrt(2)
« Reply #38 on: May 26^{th}, 2005, 11:17am » 
Quote Modify

So basically it doesn't even make sense that we could find A and B, with using brute force. So what if we restrict A and B to the natural numbers. Then it's clearly doable with a computer; is there a better way to find them?


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13259


Re: Combinations of Pi and Sqrt(2)
« Reply #39 on: May 26^{th}, 2005, 1:03pm » 
Quote Modify

on May 26^{th}, 2005, 11:17am, River_Phoenix wrote:So basically it doesn't even make sense that we could find A and B, with using brute force. So what if we restrict A and B to the natural numbers. Then it's clearly doable with a computer; is there a better way to find them? 
 If you can do natural numbers brute force, than you can do integer brute force (there's a one to one mapping between them) The problem is any A and B, no matter how large, might be the ones you need. And I don't think you can use something like binary search (and even if you could it wouldn't help much in theory, except that in practice the number you're looking for is represented in the computer as well). I'd be hardpressed to suggest a criteria for telling how close your A and B are to the value you're looking for (relatively to other choices for A,B)

« Last Edit: May 26^{th}, 2005, 1:04pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



River Phoenix
Junior Member
Gender:
Posts: 125


Re: Combinations of Pi and Sqrt(2)
« Reply #40 on: May 26^{th}, 2005, 3:02pm » 
Quote Modify

If you limit A and B to the natural numbers, I don't see how they can be dense in R, since in that case there are only finitely many Asqrt(2) + Bpi less than any N>0 (you can't just make any number you want out of Asqrt(2)+Bpi unless A and B can be any integer, including negative ones).


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13259


Re: Combinations of Pi and Sqrt(2)
« Reply #41 on: May 27^{th}, 2005, 12:06am » 
Quote Modify

Ah, yes.. I overlooked that Sorry, you're quite right.

« Last Edit: May 27^{th}, 2005, 12:11am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



SWF
Uberpuzzler
Posts: 871


Re: Combinations of Pi and Sqrt(2)
« Reply #42 on: Jun 2^{nd}, 2005, 10:10pm » 
Quote Modify

I tried to see how difficult it would be to actually come up with A and B given a numerical value for X, and came up with a method that seems work quite well. This is intended for practical use, and of course would be limited by using finite precision in the calculations. Express the value of [pi]/sqrt(2) as a continued fraction, and generate a sequence of ever improving best rational approximations. The i'th approximaion to [pi]/sqrt(2) is P_{i}/Q_{i}. Define e_{i}= Q_{i}*[pi]  P_{i}*sqrt(2). The following table shows the first 13: i ___  P_{i} _________  Q_{i} ________  e_{i}  1  2  1  0.313  2  9  4  0.161  3  11  5  0.151  4  20  9  9.93e3  5  311  140  2.55e3  6  953  429  2.27e3  7  1264  569  2.77e4  8  11065  4981  6.01e5  9  45524  20493  3.65e5  10  56589  25474  2.36e5  11  102113  45967  1.30e5  12  158702  71441  1.06e5  13  260815  117408  2.33e6  Given an approximation to X, X_{j} = A_{j}*[pi] + B_{j}*sqrt(2), you can progressively improve the approximation by adding or subtracting an integral multiple of an e_{i} from the table above. Start out with either A_{1}=0 or B_{1}=0. At each step use the largest abs(e_{i}) that is less than the error in the approximation to X. In every case I have tried, this method has resulted in the correct solution. An example: Given X=2.9950753101730819597986... (I got this by picking two fairly large A and B, and want to see if the method results in the same ones), the best approximation with A or B zero is 1*[pi] + 0*sqrt(2) which gives an approximation to X with an error of 0.1465. The largest e_{i} in the table whose absolute value is less than this is for i=4, and a factor of 15 is the closest integer multiple. Add 15 times the values for i=4: 1*[pi]+0*sqrt(2) + 15* ( 9*[pi]  20*sqrt(2) ) = 136*[pi]  300*sqrt(2) This differs from X by 0.002543. The row of the table for i=6 is the max value less than this, but only by a factor of 1. Subtract 1 times the values in row 6 giving 293*[pi]+653*sqrt(2), which differs from X by .000266 Row 8 with a factor of 4 is then subtracted giving 20217*[pi]+44913*sqrt(2), which differs from X by 2.59e5. Row 10 of the table with factor of 1 is subtracted leaving 45691*[pi]+101502*sqrt(2), with an error of 2.33e6. This is exactly the same magnitude as e_{13}. Add row 13 giving 71717*[pi]  159313*sqrt(2), which to the precision I am using, equals X. Those A and B are the ones I started with. That may sound complex, but it is fairly straight forward. Given the table of approximations to [pi]/sqrt(2), it was only 6 steps to come up with the solution for some fairly large A and B.


IP Logged 



Michael Dagg
Senior Riddler
Gender:
Posts: 485


Re: Combinations of Pi and Sqrt(2)
« Reply #43 on: Jun 2^{nd}, 2005, 10:56pm » 
Quote Modify

SWF your demonstration is quite excellent. It appears that my previous mark that computing A and B it is not strongly NPcomplete has merit.


IP Logged 
Regards, Michael Dagg



Benny
Uberpuzzler
Gender:
Posts: 1024


Re: Combinations of Pi and Sqrt(2)
« Reply #45 on: Feb 2^{nd}, 2008, 10:36am » 
Quote Modify

By the transcendental character of pi, this equation can have no solution unless X is irrational. For suppose for a contradiction that X=P/Q and X=sqrt(2)*A+pi*B for some integers P,Q,A and B. Then (Xpi*B)^2=2*A^2 (P/Qpi*B)^2=2*A^2 and thus pi would be algebraic, for a contradiction. Next, any solution for a given irrational X is unique. For suppose X=sqrt(2)*A_1+pi*B_1=sqrt(2)*A_2+pi*B_2 Then sqrt(2)*A_1+pi*B_1sqrt(2)*A_2pi*B_2=... so sqrt(2)*(A_1A_2)=pi*(B_1B_2) 2*(A_1A_2)^2=pi^2*(B_1B_2)^2 So if B_1 is not equal to B_2, we would conclude pi is algebraic, which is false, hence B_1=B_2, which immediately implies A_1=A_2.


IP Logged 
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Combinations of Pi and Sqrt(2)
« Reply #46 on: Feb 2^{nd}, 2008, 11:04am » 
Quote Modify

Yes, and even slightly stronger, X is transcendental, since [2, X], and if X were algebraic, the entire field would be. However, the problem was to figure out how to actually determine A and B from X, assuming as given that X is expressible in this form.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



Benny
Uberpuzzler
Gender:
Posts: 1024


Re: Combinations of Pi and Sqrt(2)
« Reply #47 on: Feb 3^{rd}, 2008, 1:33am » 
Quote Modify

Icarus stated: "the problem was to figure out how to actually determine A and B from X ..." I missed that. How about First of all, for any A and B integers, X is unique, in that for that X, there is no other pair of A and B that would satisfy this equation. Otherwise, one could compute pi in terms of Sqrt(2). Now, let's rearrange the equation: e^(2X  2B Sqrt(2)) = e^2B(pi) = 1 Expand the left , subtract 1 from it, so that you have an infinite series in powers of B, with X as coefficients, which equals 0. There is a way of finding the inverse series so that we can compute the value of B in terms of X so that the first series equals 0. But there is such a thing as an inverse infinite series. You can then go ahead and add up the powers of X until you end up with a number that is nearly an integer, with a shrinking decimal value. That is the value for B that you seek, and A follows. Of course, then it becomes a matter of finding "more efficient series" to determine B from X.


IP Logged 
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.



temporary
Full Member
Posts: 255


Re: Combinations of Pi and Sqrt(2)
« Reply #48 on: Feb 3^{rd}, 2008, 9:46am » 
Quote Modify

This reminds me of complex numbers. Anyway, the decimal would be infinite for any number given(I doubt there are any asqrt(2)+bpi=x where x is rational). So the number they give you would have to already be in the form of asqrt(2)+bpi or you could never be sure it is asqrt(2)+bpi since it could be off by one decimal that you wouldn't see since they can't show them all.


IP Logged 
My goal is to find what my goal is, once I find what my goal is, my goal will be complete.



pex
Uberpuzzler
Gender:
Posts: 838


Re: Combinations of Pi and Sqrt(2)
« Reply #49 on: Feb 3^{rd}, 2008, 10:10am » 
Quote Modify

on Feb 3^{rd}, 2008, 9:46am, temporary wrote:This reminds me of complex numbers. Anyway, the decimal would be infinite for any number given(I doubt there are any asqrt(2)+bpi=x where x is rational). So the number they give you would have to already be in the form of asqrt(2)+bpi or you could never be sure it is asqrt(2)+bpi since it could be off by one decimal that you wouldn't see since they can't show them all. 
 How about first reading the thread?


IP Logged 



