2
$\begingroup$

If I have a ratio of two positive real numbers $x:y,$ then I can find the "best" rational approximations to it by writing it as a continued fraction (e.g. by repeatedly removing the integer part and taking the reciprocal of the remainder) $$\frac xy=a_0+\frac1{a_1+\frac1{a_2+\ddots}},\rlap{\qquad\text{$a_i$ integer}}$$ and then I can cut it off after any of the $a_i$ to form a rational approximation like $$\frac xy\approx a_0+\frac1{a_1}=\frac pq,\rlap{\qquad\text{$p,q$ integer}}$$

and this is a "best small" approximation in the sense that any closer rational approximation $\frac{p'}{q'}$ with $\left|\frac{p'}{q'}-\frac xy\right|<\left|\frac pq-\frac xy\right|$ has $p'\ge p$ and $q'\ge q$. (At least one of those will be strict for a distinct ratio.) This process doesn't produce all the best small approximations, but a modification does.

Recently, I wanted to approximate a ratio of three numbers like $13780:8992:3364$, instead of just two. I realized I didn't know how, hence this question.

We should define what a "best small" approximation is in this 3D context. To tell how well $p:q$ approximates $x:y$, we just computed $|\frac pq-\frac xy|$. To generalize this to $p:q:r$ and $x:y:z$, I think we should follow this answer. We treat them as vectors in 3D space and normalize them onto the unit sphere. Then we can find the distance between these projections. (For the 2D case I don't think this definition gives the same numbers, but I think it gives the same ordering.) Then $p:q:r$ is a best small approximation to $x:y:z$ if any closer approximation $p':q':r'$ has $p'\ge p,q'\ge q,r'\ge r$. (Comments welcome on the suitability of this definition.)

In my one-off case I did it somewhat ad hoc by dividing out the smallest part of the ratio to get $4+\frac1{10+\ddots}:2+\frac1{2+\frac1{4+\ddots}}:1$, truncating at the first and second positions respectively to get $4:2+\frac12:1,$ and then multiplying by the common denominator to $8:5:2.$ By enumerating all smaller ratios I find this is a best small approximation, but my process doesn't appear general. E.g. if I instead truncate to $4.1:2.5:1$ and then multiply to $41:25:10$, I find it is actually worse than the smaller (best small) approximation $37:24:9$. Is there/what is a general process for finding best small approximations to a ratio of three (or more) numbers? (Other than just enumerating all small ratios and taking the best ones.)

$\endgroup$
5
  • 1
    $\begingroup$ Any thoughts about my answer? $\endgroup$ Commented Sep 12, 2021 at 12:58
  • 2
    $\begingroup$ @GerryMyerson Oh, sorry, I've been a bit busy. But I really am looking for an explicit, effective procedure to do this, even if it is annoyingly complicated. So I didn't really consider your answer complete and was waiting for someone to write something out (or for me to have time to research what you were referencing and write an answer myself). $\endgroup$
    – HTNW
    Commented Sep 12, 2021 at 14:58
  • 1
    $\begingroup$ math.tamu.edu/~doug.hensley/SimultaneousDiophantine.pdf $\endgroup$
    – O. S. Dawg
    Commented Sep 23, 2021 at 22:15
  • 1
    $\begingroup$ How is your research coming along, HTNW? $\endgroup$ Commented Oct 4, 2021 at 4:39
  • 1
    $\begingroup$ See Chapter 5 of "Brentjes, Arne Johan. "Multi-dimensional continued fraction algorithms." MC Tracts 145 (1981): 1-183." Available free of charge at NTIS.gov $\endgroup$
    – O. S. Dawg
    Commented Oct 14, 2021 at 21:08

1 Answer 1

4
$\begingroup$

I think what you are looking for comes under the heading simultaneous diophantine approximation. The basic theorem under this heading is the simultaneous version of the Dirichlet's approximation theorem, which says, given real numbers $\alpha_1,\dots,\alpha_d$ and a natural number $N$ there are integers $p_1,\dots,p_d$ and $q$, $1\le q\le N$ such that $$\left|\alpha_i-{p_i\over q}\right|\le{1\over qN^{1/d}}$$ In your case, the real numbers are $x/z$ and $y/z$, and the approximating fractions are $p/r$ and $q/r$.

The theorem tells you these good approximations exist, but doesn't tell you how to find them. The proof given at the Wikipedia page can, in principle, be used to find them, but in practice, it's miserable. There are better methods, but they are more complicated than the continued fractions that work for approximating a single real or rational. But the search term "simultaneous diophantine approximation" should get you started.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .