Author |
Topic: Combinations of Pi and Sqrt(2) (Read 21950 times) |
|
Michael Dagg
Guest
|
 |
Re: Combinations of Pi and Sqrt(2)
« Reply #25 on: Apr 14th, 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 15th, 2005, 3:38pm » |
Quote Modify
|
on Apr 14th, 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 G-algebra over something like Z2, 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 15th, 2005, 8:08pm » |
Quote Modify
Remove
|
on Apr 15th, 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 22nd, 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 22nd, 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 23rd, 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 23rd, 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 23rd, 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 < (a-b)pi < e mod sqrt(2), and so 0 < (a-b)pi + c sqrt(2) < e. Since e was arbitrary, the linear combinations of pi and sqrt(2) are dense.
|
| « Last Edit: May 23rd, 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 23rd, 2005, 4:33pm » |
Quote Modify
|
Thanks! I've got to stop being so lazy. Re-reading 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] [X-h, 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: 879
|
|
Re: Combinations of Pi and Sqrt(2)
« Reply #33 on: May 23rd, 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 23rd, 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[ai], where the ai 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 23rd, 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 24th, 2005, 3:04pm » |
Quote Modify
|
on May 23rd, 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 finite-time 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: 879
|
|
Re: Combinations of Pi and Sqrt(2)
« Reply #36 on: May 24th, 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 non-trivial 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 25th, 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 26th, 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 do-able 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: 13730
|
|
Re: Combinations of Pi and Sqrt(2)
« Reply #39 on: May 26th, 2005, 1:03pm » |
Quote Modify
|
on May 26th, 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 do-able 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 26th, 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 26th, 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: 13730
|
|
Re: Combinations of Pi and Sqrt(2)
« Reply #41 on: May 27th, 2005, 12:06am » |
Quote Modify
|
Ah, yes.. I overlooked that 
Sorry, you're quite right.
|
| « Last Edit: May 27th, 2005, 12:11am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Combinations of Pi and Sqrt(2)
« Reply #42 on: Jun 2nd, 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 Pi/Qi. Define ei= Qi*[pi] - Pi*sqrt(2). The following table shows the first 13:
| i ___ | Pi _________ | Qi ________ | ei | | 1 | 2 | 1 | 0.313 | | 2 | 9 | 4 | -0.161 | | 3 | 11 | 5 | 0.151 | | 4 | 20 | 9 | -9.93e-3 | | 5 | 311 | 140 | 2.55e-3 | | 6 | 953 | 429 | -2.27e-3 | | 7 | 1264 | 569 | 2.77e-4 | | 8 | 11065 | 4981 | -6.01e-5 | | 9 | 45524 | 20493 | 3.65e-5 | | 10 | 56589 | 25474 | -2.36e-5 | | 11 | 102113 | 45967 | 1.30e-5 | | 12 | 158702 | 71441 | -1.06e-5 | | 13 | 260815 | 117408 | 2.33e-6 |
Given an approximation to X, Xj = Aj*[pi] + Bj*sqrt(2), you can progressively improve the approximation by adding or subtracting an integral multiple of an ei from the table above. Start out with either A1=0 or B1=0. At each step use the largest abs(ei) 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 ei 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.59e-5.
Row 10 of the table with factor of 1 is subtracted leaving -45691*[pi]+101502*sqrt(2), with an error of -2.33e-6.
This is exactly the same magnitude as e13. 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: 500
|
|
Re: Combinations of Pi and Sqrt(2)
« Reply #43 on: Jun 2nd, 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 NP-complete has merit.
|
|
IP Logged |
Regards,
Michael Dagg
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Combinations of Pi and Sqrt(2)
« Reply #45 on: Feb 2nd, 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 (X-pi*B)^2=2*A^2
(P/Q-pi*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_1-sqrt(2)*A_2-pi*B_2=...
so
sqrt(2)*(A_1-A_2)=-pi*(B_1-B_2)
2*(A_1-A_2)^2=pi^2*(B_1-B_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 2nd, 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 3rd, 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 3rd, 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: 880
|
|
Re: Combinations of Pi and Sqrt(2)
« Reply #49 on: Feb 3rd, 2008, 10:10am » |
Quote Modify
|
on Feb 3rd, 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print