wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Combinations of Pi and Sqrt(2)
        
(Message started by: william wu on Oct 15^th, 2003, 9:06pm)

Title: Combinations of Pi and Sqrt(2)
Post by william wu on Oct 15^th, 2003, 9:06pm

Say I am given a number X = A*[sqrt]2 + B*[pi], where A and B are integers.

Given X, how can you find A and B, without using brute force?

Title: Re: Combinations of Pi and Sqrt(2)
Post by william wu on Oct 15^th, 2003, 9:19pm

Some of my initial ideas:
[hide]
My immediate intuition was dot products, because whenever I see a function which is a linear combination of basis functions, I know I can take the dot product of the function with each basis function to get the coefficients of the linear combination. However, these are integral coefficients, and it doesn't make sense to say [pi] and [sqrt]2 are orthogonal functions.

[pi] cannot be expressed as a rational multiple of [sqrt]2. So there is only one possible solution, if any.

Is it true that for any [epsilon] > 0, [exists] integers A and B such that [epsilon] = A[pi] + B[sqrt]2? How to prove/disprove this? If it is true, then perhaps we can argue that the problem is uncomputable, because finding a solution would require infinite precision computations, and thus infinite time/space.

If however we restrict A and B to be positive integers, then all I can think of is the knapsack algorithm, which runs in psuedopolynomial time. Perhaps there are some mathematical properties of sqrt(2) vs. [pi] that I can bank on to get a faster solution?
[/hide]

Title: Re: Combinations of Pi and Sqrt(2)
Post by Rezyk on Oct 15^th, 2003, 10:12pm

on 10/15/03 at 21:19:51, william wu wrote:

Is it true that [hide]for any [epsilon] > 0, [exists] integers A and B such that [epsilon] = A[pi] + B[sqrt]2?[/hide] How to prove/disprove this?

It [hide]fails for any rational epsilon;[/hide] proof by [hide]contradiction:
Let [epsilon] = p/q (p, q integers) = A[pi] + B[sqrt]2.
=> Aq[pi]+Bq[sqrt]2 - p = 0.
=> [pi] is a root of (Aqx+Bq[sqrt]2 - p)(Aqx-Bq[sqrt]2 - p) (a polynomial with integer coefficients)
=> [pi] is not transcendental
=> contradiction
[/hide]

Title: Re: Combinations of Pi and Sqrt(2)
Post by Rezyk on Oct 15^th, 2003, 10:38pm

My initial thought is to try and use [hide]the values of cos(2A[sqrt]2)=cos(2X) and cos(2[sqrt]2) to determine |A| somehow[/hide].

Title: Re: Combinations of Pi and Sqrt(2)
Post by Sir Col on Oct 16^th, 2003, 2:06am

on 10/15/03 at 21:19:51, william wu wrote:

Is it true that for any [epsilon] > 0, [exists] integers A and B such that [epsilon] = A[pi] + B[sqrt]2? How to prove/disprove this?

We can disprove this, and deduce something about [epsilon] in the process...
::[hide]
Suppose that [epsilon] is algebraic.
[epsilon]–B[sqrt]2=A[pi].
LHS is be algebraic, but RHS is transcendental.
Hence [epsilon] cannot be algebraic.
Futhermore, we can now assert that [epsilon] must be transcendental.
[/hide]::

I've not solved it yet, but this is a really interesting problem...
::[hide]
The result follows from solving, tan(X)=tan(A[sqrt]2) (or cosine).
Therefore, X=A[sqrt]2+B[pi].

We seem to be dealing with a type of periodic equivalence with transendentals over an infinite domain, but with a particular solution. I'm suspecting that we can do something with Euler's formula. By working with a complex domain we might be able to make more progress with this problem?
[/hide]::

Title: Re: Combinations of Pi and Sqrt(2)
Post by SWF on Oct 16^th, 2003, 5:18pm

My first thought was that any x that meets the conditions and can be well defined would have to be written in a form such that the values of A and B are immediately obvious. x is transcendental (unless B=0) so it is not easily described without giving away the integer coefficient of [pi].

However, try finding A and B when x is given by this rapidly converging series (remember brute force is discouraged):

http://tcw2.ppsw.rug.nl/~towr/PHP/FORMULA/formula.php?id=64

Title: Re: Combinations of Pi and Sqrt(2)
Post by James Fingas on Oct 17^th, 2003, 6:59am

Here are my thoughts about this problem.

First of all, it is quickly apparent that any real number can be approximated to arbitrary precision with a number of the form X = A[sqrt]2 + B[pi].

This presents the obvious problem that, without infinite-precision arithmetic, we cannot be sure that we have arrived at the actual solution, or have arrived at a very good approximation of a solution.

Infinite-precision arithmetic presents a difficult task. The only real alternative is to restrict our analysis to numbers such as the one that SWF gives in the preceding post. This is interesting, and I'm sure it's difficult, but does not bode well for this being a general sort of question.

So what can we do with finite precision arithmetic? Quite a lot, actually. Take an arithmetic with a precision of [epsilon] (the granularity of the numbers used). Assume that all calculations, including computing X = A[sqrt]2 + B[pi], can be done to an accuracy of [epsilon]. I know this is a bad simplification, and I'm sure we could come up with something better, but it would be markedly more complex.

Now we define p, the confidence we want to have in our answers. I'll use p=0.001 here. By choosing p in this way, we make sure that when we find candidate A and B that could make up X, we know with 99.9% confidence that X is actually a number formed by X = A[sqrt]2 + B[pi], rather than just a random number.

The model I define for the problem is that we are searching the grid of numbers (a,b) for pairs that are close to the line X = a[sqrt]2 + b[pi], or b = -a[sqrt]2/[pi] + X/[pi] (call this line 'T' for target). The constraint that we will put on these values of (a,b) is that they are also as close to (0,0) as reasonably possible. That means we will try to minimize the absolute value of a - b[sqrt]2/[pi] (which is the perpendicular to the line T that passes through the origin). Call the line a - b[sqrt]2/[pi] = 0 'C' for constraint. See the diagram below.

How do we do this for an arbitrary X (given to a precision of [epsilon])? I'll let you think about that one, but once we have picked a pair (a,b) that is as close to the line T as possible without being more than M away from the line C (M is found while solving this problem, and is roughly p/[epsilon]), we can check to see if the number we were given was based on a particular pair (c,d), or whether it was just a random number with no "reasonable" solution, with a probability of error of p=0.001.

Title: Re: Combinations of Pi and Sqrt(2)
Post by SWF on Oct 17^th, 2003, 5:09pm

Here is another x that can also be written as A[sqrt]2+B[pi]:

http://www.ai.rug.nl/~towr/PHP/FORMULA/formula.php?id=65

Title: Re: Combinations of Pi and Sqrt(2)
Post by rmsgrey on Oct 19^th, 2003, 7:25pm

A quick quibble about some of the arguments being thrown around ::[hide][epsilon] can be algebraic for a small (countably infinite) number of cases - those where the coefficient of [pi] is 0[/hide]::

Not that I have anything useful to contribute

Title: Re: Combinations of Pi and Sqrt(2)
Post by Icarus on Oct 19^th, 2003, 8:36pm

A different, simpler, proof that numbers of the form (A[sqrt]2 + B[pi]) do not consist of all positive reals is simply to note that the set of such numbers is countable, while the positive reals are not.

My thought is to find an integer B satisfying

x[sup2] - 2B[pi]x + B[sup2][pi][sup2] [equiv] 0 mod 1. I may be wrong, but I suspect that if such a B exists, it has to be unique.

Title: Re: Combinations of Pi and Sqrt(2)
Post by towr on Oct 20^th, 2003, 12:42am

on 10/19/03 at 20:36:30, Icarus wrote:

My thought is to find an integer B satisfying

x[sup2] - 2Bx + B[sup2][pi][sup2] [equiv] 0 mod 1. I may be wrong, but I suspect that if such a B exists, it has to be unique.

Isn't there a [pi] missing there? It seems to me it should be x[sup2] - 2B[pi]x + B[sup2][pi][sup2] [equiv] 0 mod 1

Title: Re: Combinations of Pi and Sqrt(2)
Post by Icarus on Oct 20^th, 2003, 9:46am

Look again - there is a second [pi] in there. And please ignore the edit announcement at the bottom. It has nothing to do with this. Honest - it doesn't! ::)

Title: Re: Combinations of Pi and Sqrt(2)
Post by towr on Oct 20^th, 2003, 11:10am

you forgot to edit my quote ;)

Title: Re: Combinations of Pi and Sqrt(2)
Post by Sir Col on Oct 21^st, 2003, 8:41am

Teehee, we could have great fun with this...

Suppose that I quote you after making a mistake:

on 10/20/03 at 11:10:32, towr wrote:

you forgot to edit my quote ;)

I then edit this post for no good reason.

You go back to correct your post, and hopefully post a follow up to acknowledge that you have changed it.

The trap has been sprung. I couldn't have misquoted a virgin post (one without the edit tell-tale sign below it), but now...

I can re-edit my post and change it to something like below (adding the [e] [/e] below to make it look like I've been back for a good reason):

on 10/20/03 at 11:10:32, towr wrote:

you forgot to edit my quote – by the way, I've finally decided to bow to Sir Col's mighty intellect and accept that the natural numbers are 1,2,3,... (not including zero). Sorry for doubting your magnificance!

[e]Ooh, I forgot to thank you before for your kind words[/e] ;)

Title: Re: Combinations of Pi and Sqrt(2)
Post by towr on Oct 21^st, 2003, 9:03am

on 10/21/03 at 08:41:21, Sir Col wrote:

Teehee, we could have great fun with this...

Espescially as moderators ;)

Quote:

I can re-edit my post and change it to something like below (adding the [e] [/e] below to make it look like I've been back for a good reason):

Well, of course any quotes in an edited post are somewhat suspect. Even when they aren't misquotes.. :P
Good thing we're all fairly honest around here..

Title: Re: Combinations of Pi and Sqrt(2)
Post by SWF on Oct 27^th, 2003, 6:51pm

I thought I should give the answers to the the two equations I gave above in case I lose my notes and the solution goes the way of Fermat's proof.

The first equation I gave equals: (-192)*[surd]2+(96)*[pi] and was found by using the series for sin([pi]/4) =[surd]2/2 and choosing coefficients to make the coefficient of [pi]¹ be zero.

The equation in my second post equals: (-4)*[surd]2+(2)*[pi] and was found by using the series for sin^-1([surd]2/2)=[pi]/4 and choosing coefficients that make the coefficient of [surd]2 be zero.

Title: Re: Combinations of Pi and Sqrt(2)
Post by Icarus on Oct 27^th, 2003, 7:06pm

My apologies for messing with your post, SWF, but I found the combination of hidden numbers that need to be highlighted to be seen and unhidden symbols that do not show at all when highlighted made the post extremely difficult to read.

Anyone who is reading this far down in the thread is not looking for hints, but rather has been highlighting and reading the previous posts anyway. In my opinion, late in the thread hiding text becomes more of a nuisance than it's worth.

Title: Re: Combinations of Pi and Sqrt(2)
Post by SWF on Oct 27^th, 2003, 7:44pm

No problem. I dislike trying to read hidden answers too, but when an answer is given without hiding there are often complaints. It would be my pleasure to cut back on inserting those tags in so much.

Title: Re: Combinations of Pi and Sqrt(2)
Post by Sir Col on Oct 28^th, 2003, 6:03am

on 10/27/03 at 19:06:23, Icarus wrote:

In my opinion, late in the thread hiding text becomes more of a nuisance than it's worth.

I'm glad someone else feels this way. It'd be good to have some clarity or other peoples thoughts on this issue. When to hide, when not to hide? Maybe you could start a poll, to canvas opinion, in more common location?

I appreciate that posting the 'answer' below the first post (containing the question), is not good. But once we get into discussing the solutions and presenting support and refutations, do we need to hide these posts? It is frustrating to have to continuously highlight the text and there is a definite issue with the symbols: they're visible when hidden, and often invisible when highlighted.

Title: Re: Combinations of Pi and Sqrt(2)
Post by towr on Oct 28^th, 2003, 6:21am

The symbols things is indeed annoying. I tend not to use them anymore when I intend to hide the text they're in, and just use sqrt() and whatever else we used before we had the symbols.

Perhaps it would help if we had a different kind of hiding system, one were you don't highlight the text, but just push a button or something. This is simple to do by just changing the style from visible to invisible with javascript. It has the added benefit that it works on images as well (just put it in a div-element, and hid the whole thing untill someone unhides it by pushing the 'unhide'-button)
The current system could be overlaid as consideration to those who don't like javascript and have it disabled (or have archaic browsers that can't read it)

Title: Re: Combinations of Pi and Sqrt(2)
Post by Brian on Nov 11^th, 2003, 9:12pm

Why not use integer relation algorithms (via standard lattice reduction methods)?

Title: Re: Combinations of Pi and Sqrt(2)
Post by Icarus on Nov 12^th, 2003, 6:08pm

Because jargon alone fails to impress the ladies. Care to elaborate?

Title: Re: Combinations of Pi and Sqrt(2)
Post by Brian on Nov 13^th, 2003, 8:17am

You are given a basis Pi and Sqrt[2]. You want to find A and B such that A Pi + B Sqrt[2] is closest to the given number X. This is an entirely standard problem in the theory of lattices. It is also NP-complete, in general. Luckily, we have very good approximation algorithms (LLL and BKZ, principally). There are some tricks to makes sure that the algorithm is numerically stable and convergent in a reasonable amount of time. Typically, 30 digits of precision will be able to pin down A and B if they are in the range of ~10^6 or less. Victor Shoup's NTL library has perhaps the nicest free implementation of LLL, combined with excellent arbitrary precision integer arithmetic support.

Title: Re: Combinations of Pi and Sqrt(2)
Post by Michael Dagg on Apr 13^th, 2005, 7:35pm

on 10/15/03 at 21:06:06, william wu wrote:

Say I am given a number X = A*[sqrt]2 + B*[pi], where A and B are integers.

Given X, how can you find A and B, without using brute force?

This is one of the more interesting discussions. But, unfortunately it cannot be done.

While it is clearly possible to find A and B such that A*sqrt(2) + B*pi is within some epsilon of X, this is a different problem all together than what Mr. Wu stated and is certainly not strongly NP-complete, since we can find A and B within some deterministic time by truncating X and achieving the same epsilon radius for the same A and B. Try it.

There is a Fresnel integral for sqrt(pi) that contains sqrt(2) as a factor and looks like

sqrt(pi) = 2*sqrt(2)*int[cos(z^2) dz, lower=0, upper=infinity]

that can be used to manipulate the original expression involving pi into an integral expression without pi. However, after a great deal of messy work you will eventually end up with an expression with some terms that are nonsense.

The fundamental reason it cannot be done is stated in Icarus's post: the set {A*sqrt(2)+B*pi: A,B in Z} is countable whereas the set {X: X in R} is uncountable.

Regards,
MD

Title: Re: Combinations of Pi and Sqrt(2)
Post by Deedlit on Apr 13^th, 2005, 10:12pm

I think William was talking just about X that is actually expressible in that form. But it does seem like you can't do much without any restriction on how X is presented. It reminds me a little of the word problem in group theory - given a finitely presented group, is there always an algorithm for determining when a word equals the identity? The surprising answer is that you can't.

Title: Re: Combinations of Pi and Sqrt(2)
Post by Michael Dagg on Apr 14^th, 2005, 9:27pm

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

Title: Re: Combinations of Pi and Sqrt(2)
Post by Deedlit on Apr 15^th, 2005, 3:38pm

on 04/14/05 at 21:27:04, Michael Dagg wrote:

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 Z₂, 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?

Title: Re: Combinations of Pi and Sqrt(2)
Post by Michael Dagg on Apr 15^th, 2005, 8:08pm

on 04/15/05 at 15:38:08, 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

Title: Re: Combinations of Pi and Sqrt(2)
Post by River Phoenix on May 22^nd, 2005, 1:42pm

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.

Title: Re: Combinations of Pi and Sqrt(2)
Post by River Phoenix on May 22^nd, 2005, 1:43pm

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

Title: Re: Combinations of Pi and Sqrt(2)
Post by Icarus on May 23^rd, 2005, 3:06pm

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.

Title: Re: Combinations of Pi and Sqrt(2)
Post by Deedlit on May 23^rd, 2005, 3:20pm

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.

Title: Re: Combinations of Pi and Sqrt(2)
Post by Icarus on May 23^rd, 2005, 4:33pm

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.

Title: Re: Combinations of Pi and Sqrt(2)
Post by SWF on May 23^rd, 2005, 9:58pm

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

Title: Re: Combinations of Pi and Sqrt(2)
Post by Deedlit on May 23^rd, 2005, 10:27pm

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.

Title: Re: Combinations of Pi and Sqrt(2)
Post by Icarus on May 24^th, 2005, 3:04pm

on 05/23/05 at 21:58:03, 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)".

Title: Re: Combinations of Pi and Sqrt(2)
Post by SWF on May 24^th, 2005, 8:46pm

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.

Title: Re: Combinations of Pi and Sqrt(2)
Post by Icarus on May 25^th, 2005, 4:45pm

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

Title: Re: Combinations of Pi and Sqrt(2)
Post by River_Phoenix on May 26^th, 2005, 11:17am

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?

Title: Re: Combinations of Pi and Sqrt(2)
Post by towr on May 26^th, 2005, 1:03pm

on 05/26/05 at 11:17:23, River_Phoenix wrote:

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)

Title: Re: Combinations of Pi and Sqrt(2)
Post by River_Phoenix on May 26^th, 2005, 3:02pm

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).

Title: Re: Combinations of Pi and Sqrt(2)
Post by towr on May 27^th, 2005, 12:06am

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

Title: Re: Combinations of Pi and Sqrt(2)
Post by SWF on Jun 2^nd, 2005, 10:10pm

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.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, 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₁=0 or B₁=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.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 e₁₃. 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.

Title: Re: Combinations of Pi and Sqrt(2)
Post by Michael_Dagg on Jun 2^nd, 2005, 10:56pm

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.

Title: Re: Combinations of Pi and Sqrt(2)
Post by towr on Jun 3^rd, 2005, 12:00am

Wow.. that's terribly clever..

Title: Re: Combinations of Pi and Sqrt(2)
Post by BenVitale on Feb 2^nd, 2008, 10:36am

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.

Title: Re: Combinations of Pi and Sqrt(2)
Post by Icarus on Feb 2^nd, 2008, 11:04am

Yes, and even slightly stronger, X is transcendental, since http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif[http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2, 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.

Title: Re: Combinations of Pi and Sqrt(2)
Post by BenVitale on Feb 3^rd, 2008, 1:33am

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.

Title: Re: Combinations of Pi and Sqrt(2)
Post by temporary on Feb 3^rd, 2008, 9:46am

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.

Title: Re: Combinations of Pi and Sqrt(2)
Post by pex on Feb 3^rd, 2008, 10:10am

on 02/03/08 at 09:46:47, temporary wrote:

How about first reading the thread?

Title: Re: Combinations of Pi and Sqrt(2)
Post by Icarus on Feb 3^rd, 2008, 12:13pm

Yes, please do. SWF has given two examples of numbers that can be expressed as Ahttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2 + Bhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif, even though it is not at all clear that this is so, much less what the values of A and B would be.

He has also given what is a very good algorithm for finding A and B, though it does fall in the "Brute Force" category, and for reasons also discussed in this thread, is not guaranteed to give you a definitive result in any finite amount of time.

Title: Re: Combinations of Pi and Sqrt(2)
Post by Hippo on Feb 3^rd, 2008, 3:46pm

BTW: It seems to me X=A+B pi decomposition would be of the same complexity as X=A sqrt(2) + B pi decomposition. Am I wrong?

Title: Re: Combinations of Pi and Sqrt(2)
Post by Icarus on Feb 3^rd, 2008, 5:08pm

Well, certainly X = A + B(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2) is of the same complexity. I don't see why http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif itself would be any simpler.

Title: Re: Combinations of Pi and Sqrt(2)
Post by Mickey1 on Nov 14^th, 2010, 6:25am

If you allow a newbie (as well as a mathematical amateur):

If, as I assume, a transcendental number t added to an integer will also be transcendeltal, and the same is true for algebraic numbers, there will be no well-defined algebraic and transcendental part of the sum. That would take away any approach based on these fundamental principles leading me to assume that other approaches might have some component of what you might call brute force.

Title: Re: Combinations of Pi and Sqrt(2)
Post by SWF on Apr 19^th, 2011, 9:17pm

The equations I posted on the first page have disappeared, so I recreated them here and added a new one. I like the new one best because the right hand side contains only rational numbers, while the others have either pi or sqrt(2) on the right hand side.

Remember, the intent here is to fully define expressions for which the correct values of A and B are not immediately obvious.

Title: Re: Combinations of Pi and Sqrt(2)
Post by Mickey1 on Feb 18^th, 2012, 3:21am

1 How can X be given at all, being transcendental?
The only way seems to be if X is known in an indirect way such as for the natural logarithm base e (or simply given by a certain combination of A and B which would make the problem very easy to solve).

2 How about the “other than by brute force” statement, indicating that such a method would be available?

The right hand side part is countable, =RHS(N), and the solution is unique since
(A1-A2)pi+ (B1-B2)sqrt(2) =0 implies the contradiction that sqrt(2) would be a transcendental number.
But how are we to identify that the X=RHS(N) in a finite number of steps, assuming we were given X in a similar way as e above (and that X was indeed =RHS)?

It would lead to a Goedel type statement that X must be =RHS(N) for some N but we cannot prove it (i.e. verify the solution).

Title: Re: Combinations of Pi and Sqrt(2)
Post by Mickey1 on Feb 29^th, 2012, 12:30am

Let me have another go at a ”solution”, in three steps:
1)
X = 5*sqrt(2) + 3*Pi. It seems that A=5, B=3 is a (unique) solution.
2)
We assume that the number is given in by an infinite decimal representation. I now attack the problem in a way similar to, or rather inspired by, Cantor’s diagonal argument:

First, the digital part of X is considered (assuming it exists). It is clear to the calculation experts of the forum that infinitely many combinations exist, e.g. combining a large positive A with a large negative B, which would have the same digital part. I now multiply both side of the equation with 10 and repeat the argument, to show that the digital plus the first decimal have the same property (allowing infinitely many combinations which all have an identical digital and the first decimal part). The process can continue to infinity since, if it stopped, (I suggest without proof that) it would imply that there was a “tail” of decimals from A*pi (TApi) and B*sqrt(2) (TBs) and rational numbers r1 and r2, so that TApi=r1*TBs, implying in turn the same relation between the two original right hand side terms: A*pi = r2* B*sqrt(2), a contradiction since pi would have to be algebraic and sqrt(2) simultaneously must be transcendental.
3)
The contradiction between 1 and 2 underlines the problem of the formulation of the question. According to 2), there can be no solution at all, not even for the obvious case, 1).

Title: Re: Combinations of Pi and Sqrt(2)
Post by SWF on Mar 6^th, 2012, 7:23pm

on 02/18/12 at 03:21:32, Mickey1 wrote:

Have you read this thread? There are 3 examples given immediately before your post. Obviously, listing all the digits is not the way to do it, but it can be defined mathematically, for example as an infinite series, an integral, or as the solution to transcendental equations.

Quote:

2 How about the “other than by brute force” statement, indicating that such a method would be available?

A method is given on page 2 of this thread. Knowing that X is expressible in the desired form, another way of dealing with X is to have the digits revealed a few at a time. For each step of the algorithm, a best estimate based on the given digits is obtained. If that isn't the correct answer, the most significant digit of the error between between X and the estimate could be provided so another estimate can be made accounting for the additional information. Eventually that error would be zero.

Title: Re: Combinations of Pi and Sqrt(2)
Post by Mickey1 on Mar 14^th, 2012, 12:15pm

I now have read the threads more carefully which doesn’t mean that I understood them all.
I was first confused by the “Given X” passage since X cannot be given in a finite form (except indirectly). I then, later, interpreted the question to refer to a situation like: if X= 5*sqrt(2) + 3*Pi then 2X= 10*sqrt(2) + 6*Pi. Also, we accept squaring both the left- and right hand side etc. for the same reason ( even we if still do not accept X given in infinite terms). The reason we would accept this, is not based on accepting infinitely long numbers, but based on the Peano axioms (assuming they can transported without too many contradictions through the Dedekind cut and apply to real numbers).

Now, take these following statements as questions from an interested amateur:

1 As I interpret your stepwise process, it can identify one (perhaps the lowest?) possible A and B within a bounded environment of X. Since the right hand side gives a countable set, you could disregard the first answer coming up if you detected a difference at all between the given X and the right hand side of the equation.
This process might take you through all possible values and sooner or later to the right one. (A more cumbersome approach would be to test all A and B values).

2. The verification process would still require infinite steps. Even if X was given in a finite form, the suggested solution would be infinite.

3. If one doesn’t accept the infinite verification process, the alternative is that X is given “as an infinite series, an integral, or as the solution to transcendental equations”, i.e. in a finite form.

4. In this case the solution would depend on (mathematical) pattern recognition, and we might not need a algorithm or any other approach managing the equation’s right hand side.

5 (This I believe has not been mentioned by the other thread authors, perhaps to their credit?): The possible forms of finite forms of infinite series etc are not only infinite, but I believe them to be similar to “all subsets of the natural numbers” i.e. uncountable. To any series can be added 1-1 or 1 – (1/2 + 1/4…) etc. I therefore launch the conjecture that no systematic approach of formula recognition can be sufficient to supply the solution.

Title: Re: Combinations of Pi and Sqrt(2)
Post by SWF on Mar 14^th, 2012, 7:56pm

Mickey1, I think many of the arguments you are making involve common characteristics of transcendental numbers or even irrationals, not just A*pi+B*sqrt(2). You can't specify such a number by writing out all of its decimal digits.

on 03/14/12 at 12:15:21, Mickey1 wrote:

2. The verification process would still require infinite steps. Even if X was given in a finite form, the suggested solution would be infinite.

The way I think of this problem is that the person who provided X knows what A and B are, and challenges you to find A and B given X (or an approximation to X). The verification process involves checking the values of A and B, not the decimal expansion of X.

Quote:

3. If one doesn’t accept the infinite verification process, the alternative is that X is given “as an infinite series, an integral, or as the solution to transcendental equations”, i.e. in a finite form.

Do you mean "infinite form"?

Quote:

5.... I therefore launch the conjecture that no systematic approach of formula recognition can be sufficient to supply the solution.

This is true of expressions for integers too. Part of the discussion here has been how to fully express an X whose A and B are not immediately obvious. So trying to disguise expressions is part of the game. How about this one (does it count as a finite form?):

X = 2*Tan^-1( cot( exp(sinh^-1( sqrt(17) )) - sqrt(17) ) )

Title: Re: Combinations of Pi and Sqrt(2)
Post by Mickey1 on Mar 15^th, 2012, 2:26pm

3. "finite form"?
No, I mean finite form i.e. using a finite number of words in a fixed language, hence the need - and possibility - to use recognition techniques. And you are right in that I am mainly looking at the general problem rather than the given one. I did note that the equation would be (or at least look) simpler if both sides were taken as exp(iX)=exp(i(A*pi +B*sqrt(2)), but I think that point was made early on. Perhaps new ideas can emerge about the actual problem but I actually doubt it. In any case it would probably not come from me.