Mathematics desk
< May 23	<< Apr \| May \| Jun >>	May 25 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 24

Rational approximations of real ratios

Using continued fractions, it is easy to find rational approximations of the ratio between two real numbers, such as

e:\pi \approx 777:898.

What about the same for more than two numbers, such as

{\sqrt {2}}:e:\pi \approx 167:321:371.

Is there theory that gives a better approach than brute force? --Lambiam 11:44, 24 May 2021 (UTC)[reply]

The introduction of [1] says that "The method of Padé approximation has been widely used to obtain effective lower bounds for simultaneous rational approximations to algebraic numbers" and then goes on to elaborate. There is also apparently a simultaneous version of Dirichlet's approximation theorem. --JBL (talk) 19:06, 24 May 2021 (UTC)[reply]

Thanks. I'll have a look at the first, but apparently it cannot be used for transcendental numbers, or to numbers obtained by measurement, such as the atomic masses of the elements. I do not immediately see how the simultaneous version of Dirichlet's theorem can be used to improve on brute force. So the search goes on. --Lambiam 20:22, 24 May 2021 (UTC)[reply]

In the simple ratio case, let the ratio sought be (x:y). One way to look at continued fractions, is that they generate pairs of ratios, say (a₁:b₁), (a₂:b₂) so that a₁ b₂ - a₂ b₁ = 1 and (a₁:b₁)<(x:y)<(a₂:b₂). Given one such pair, you can find an improved pair by examining (a₁+a₂:b₁+b₂). (Please let + take precedence over : in this notation so I don't have to write a lot of parentheses.) Either (a₁+a₂:b₁+b₂)<(x:y)<(a₂:b₂) or (a₁:b₁)<(x:y)<(a₁+a₂:b₁+b₂), so choose (a₁+a₂:b₁+b₂), (a₂:b₂) or (a₁:b₁), (a₁+a₂:b₁+b₂) depending on which, as the next pair in a sequence. Given a suitable starting pair, every optimal pair will be in this sequence and every optimal approximate ratio will be in an optimal pair. This can be shown, for example, using well known properties of Farey sequences. Continued fractions just accelerate this process.

One can mimic this idea for complex ratios, but unfortunately the results are less satisfactory. Let the ratio sought be (x:y:z) and let (a₁:b₁:c₁), (a₂:b₂:c₂), (a₃:b₃:c₃) be a triple of ratios with |(a₁:b₁:c₁) (a₂:b₂:c₂) (a₃:b₃:c₃)| = 1 and (x:y:z) in the interior of the triangle formed by the three ratios considered as point in the projective plane. Here | * | denotes the determinate. The plan is similar; pick a point on one of the edges of the triangle, say (a₁+a₃:b₁+b₃:c₁+c₃), and use it to split the triangle into two subtriangles. The desired ratio (x:y:z) must be in exactly one of them, so replace one of the original vertices with this new point according to which, thus replacing the original triangle with one of the subtriangles. The problem is that there's no clear method of choosing which side the new point should be on. Some methods are better than others, for example you should always try a side which is "distant" from the desired ratio, where the exact definition of "distant" is flexible because we're dealing with projective space rather than Euclidean space. The result is that instead of getting a uniquely defined sequence, you get one somewhat arbitrary choice in a collection of such sequences.

One issue is that an exact idea of "closeness" hasn't been defined for complex ratios. The generalization to Dirichlet's theorem uses the uniform norm, max(|y/x - b/a|, |z/x - c/a|), but there's no reason to consider this better than the Euclidean norm √((y/x - b/a)² + (z/x - c/a)²). It doesn't seem to matter much though since it seems unlikely that an optimal approximation in either sense will appear as a vertex of any triangle in the sequence. For example, I tried the ratio (1:√2:√3). By brute force, the best approximation by either Euclidean or uniform norm for ratios with denominator (the first coordinate) less than 1000 is (828:1171:1434). According to one side selection scheme I got the triple

(280:396:485) (903:1277:1564) (944:1335:1635),

all of which are good approximations but not the optimal one. Using another selection scheme I got

(944:1335:1635) (519:734:899) (758:1072:1313)

again good approximations but not optimal and only one point in common between the two.

I think the problem is that there is no analog to the theory of Farey sequences in higher dimensions, at least not a simple one that I've heard of. This seems to be related to the fact that the submonoid of SL(2,Z) generated by

{\begin{pmatrix}1&1\\0&1\end{pmatrix}}

and

{\begin{pmatrix}1&0\\1&1\end{pmatrix}}

is free, but afaik there is no analogous fact for SL(3,Z). Another issue that seems to be related is that while a set of points in a line segment divide it into subsegments in a unique way, a set of points in a triangle does not divide the triangle into subtriangles in a unique way. So as I see it there are several options: 1) Use a reasonably good side selection scheme with the method above and be content with the fact that you get a good approximation instead of the best. 2) Try to find a selection scheme that's guaranteed to find an optimal solution. 3) Find a way to "sharpen" a good approximation from (1) to get an optimal approximation. 4) Just abandon this approach altogether. I don't think it's entirely impossible that this problem is NP-hard, at least in arbitrarily large dimension, even though it doesn't really have an NP-hard "feel" to it. But IMO you can say the the same thing about the Lattice reduction problem and that's known to be NP-hard. --RDBury (talk) 13:33, 25 May 2021 (UTC)[reply]

Did you try using the more symmetric

a_{1}+b_{1}+c_{1}:a_{2}+b_{2}+c_{2}:a_{3}+b_{3}+c_{3}

instead? --JBL (talk) 21:30, 25 May 2021 (UTC)[reply]

That's actually equivalent to two steps with choosing an edge, with the second step constrained to pick the edge most recently added. I did try that though and several schemes that seemed attractive. I think the main problem with this kind of multistep approach is that not every possible point can be reached. For example with this a+b+c idea, if you start with a triangle where the all coordinate sums are odd, then all coordindate sum remain odd in the next step, so you might miss an optimal solution where the coordinate sum is even. Not that this might not be a problem with the original scheme; that the optimal point is a vertex of some possible triangle generated by the above process is questionable and the fact that it's true for simple ratios relies again on Farey sequences. It does seem to be true in the examples I've tried, for example the triangle (239:338:414), (198:280:343), (828:1171:1434) does contain the point (1:√2:√3) and has an optimal approximation (828:1171:1434) as a vertex, and this triangle is reachable in some sequence starting with (1:0:0), (0:1:0), (0;0:1), but finding this sequence seems to require that you already know the final triangle.

I realize the above scheme is sketchy and incomplete (not to mention over-long), but the short version is: yes, there are generalizations of continued fractions to higher dimensions, but they are more complicated than one might hope, not deterministic, and apparently not guaranteed to produce an optimal answer. Maybe the idea can be fixed up to create an actual working algorithm which finds an optimal approximation, but I didn't see how. --RDBury (talk) 01:04, 26 May 2021 (UTC)[reply]

As a measure of "goodness of fit" I used the inner product of the two normed rays (the cosine of the angle they form), which has the nice property of being insensitive to permutations of the n-tuples. --Lambiam 23:20, 25 May 2021 (UTC)[reply]

Yes, that does seem like a better measure. I suppose you could also use the sum of the coordinates instead of the the first one to bound the values. As a PS to the above, I re-did the brute force computation and found that (903:1277:1564) is actually the closest point to (1:√2:√3). I'm not sure what happened; do most of these calculations in a spreadsheet, so perhaps I sorted on the wrong column. --RDBury (talk) 02:14, 26 May 2021 (UTC)[reply]

I have actually been limiting the search to rational approximations

(p_{1}/q,p_{2}/q,...p_{n}/q)

of a given n-tuple

(x_{1},x_{2},...x_{n})

in the principal orthant, which seems a (subtly?) different problem. The last few best approximations of (1:√2:√3) before hitting the 5000 limit are:

(1183:1673:2049),

(1463:2069:2534),

(2646:3742:4583),

(4109:5811:7117).

The last two of these are each the (1,1)-weighted sum of their immediate two predecessors. This suggests considering the problem of finding out which weights with which predecessors will do the job. Starting with the n vertices (1:0:0:...:0:0), (0:1:0:...:0:0), ..., (0:0:0:...:0:1) of the hyperspherical n-simplex containing the point to be approximated, of course any integral ratio is a weighted sum of these starters, but perhaps there are smart ways of limiting the search. The approximation (903:1277:1564) is the (1,1)-weighted sum of its immediate predecessor (862:1219:1493) and a much earlier (41:58:71), and (862:1219:1493) is the (3,1)-weighted sum of its immediate predecessor (280:396:485) and an equally earlier (22:31:38). --Lambiam 12:29, 26 May 2021 (UTC)[reply]

Can you do this with the LLL algorithm? 2601:648:8200:970:0:0:0:752 (talk) 09:46, 26 May 2021 (UTC) 58[reply]

Yes, LLL works quite well. I just used it to find

{\sqrt {2}}:e:\pi \approx 5895895941388239:11332593058341037:13097387741575483

You then use the LL algorithm in a similar way as you would use it to find integer relations. If you want to find an integer relation between numbers x1,x2,x3 then you write down the matrix {1,0,0,Floor(A x1), {0,1,0,Floor(A x2)}, {0,0,1,Floor(A x3)}} where A is a large integer and then you apply the LLL algorithm on this matrix. This will then yield the set of short basis vectors which will yield a linear combination between x1, x2 and x3 with relatively small integer coefficients.

In this case we don't want to find an integer relation between the 3 numbers, instead we want to find a simple ratio between the 3 numbers. This can be considered as an integer relation problem where we want to find an integer relation between the vector (x2/x1,x3/x1) and the unit vectors (1,0) and (0,1). You then write down the matrix {{1,0,0,Floor( A x2/x1),Floor(A x3/x1)} , {0,1,0,A,0}, {0,0,1,0,A}} and then apply the LLL algorithm. This is basically the multi-component generalization of the integer relation problem. But because in this case the vector (x2/x1,x3/x1) only has two components, I think that the Euclidean algorithm would also work, as LLL is basically the generalization of the Euclidean algorithm to more than 3 numbers. Count Iblis (talk) 22:18, 26 May 2021 (UTC)[reply]

Actually, the Euclidean algorithm would not work as we have two entries for the two components for the residue, instead of just one. Count Iblis (talk) 22:23, 26 May 2021 (UTC)[reply]

1:{\sqrt {2}}:{\sqrt {3}}\approx 2358285571297:3335119438877:4084670428243

Count Iblis (talk) 06:15, 27 May 2021 (UTC)[reply]

1:{\sqrt {2}}:{\sqrt {3}}:{\sqrt {5}}\approx 288352158988805:407791533981531:499440589840789:644775028957795

Count Iblis (talk) 06:20, 27 May 2021 (UTC)[reply]

A more convenient measure than the cosine of the angle formed by the rays is the sine of that angle. For the last approximation I find it to be (less than) 5.808080838544285×10⁻²¹. --Lambiam 07:43, 27 May 2021 (UTC)[reply]