Scaling a set of reals to be nearly integers

Question

I have a set $P$ of $n$ positive real numbers, for example: $$ P = \{ \pi, e, \sqrt{2} \} \approx \{3.14159, 2.71828, 1.41421\} \;. $$ Given some $\epsilon > 0$, I would like to find the smallest scale factor $s \ge 1$ so that, for each $x \in P$, $s x$ is within $\epsilon$ of an integer. More precisely, if $[z]$ is $z$ rounded to the nearest integer, then $| sx - [sx] | < \epsilon$. For example, if $\epsilon = 0.08$, then $s=7.018$ works for the above $P$:

$$ 7.018 \, P \approx \{22.0477, 19.0769, 9.92495\} \;, $$ and the gaps to the nearest integers are $$ \{0.0477, 0.0769, 0.0750\} \;. $$ But I don't know that $7.018$ is the minimum.

Q. What is a general procedure to compute the smallest $s$, given $P$ and $\epsilon$?

Answer 1

There's a simple approach: search through all possible integer values for them to round to.

It may be 'inelegant', but it is simple, easy to implement, and may already meet your needs.

To elaborate on how this might work, we could proceed as follows:

• The interval of $s$ satisfying $|s \pi - 1| < \epsilon$ is too small
• The interval of $s$ satisfying $|s \pi - 2| < \epsilon$ is too small
• The interval of $s$ satisfying $|s \pi - 3| < \epsilon$ is too small
• The interval of $s$ satisfying $|s \pi - 4| < \epsilon$ is $s \in \left( \frac{4-\epsilon}{\pi}, \frac{4+\epsilon}{\pi} \right) $
  • There are no integers in the interval $\left( \frac{4-\epsilon}{\pi} \cdot e, \frac{4+\epsilon}{\pi} \cdot e \right) $
• The interval of $s$ satisfying $|s \pi - 5| < \epsilon$ is $s \in \left( \frac{5-\epsilon}{\pi}, \frac{5+\epsilon}{\pi} \right) $
  • There are no integers in the interval $\left( \frac{5-\epsilon}{\pi} \cdot e, \frac{5+\epsilon}{\pi} \cdot e \right) $
• The interval of $s$ satisfying $|s \pi - 6| < \epsilon$ is $s \in \left( \frac{6-\epsilon}{\pi}, \frac{6+\epsilon}{\pi} \right) $
  • There are no integers in the interval $\left( \frac{6-\epsilon}{\pi} \cdot e, \frac{6+\epsilon}{\pi} \cdot e \right) $
• The interval of $s$ satisfying $|s \pi - 7| < \epsilon$ is $s \in \left( \frac{7-\epsilon}{\pi}, \frac{7+\epsilon}{\pi} \right) $
  • The interval $\left( \frac{7-\epsilon}{\pi} \cdot e, \frac{7+\epsilon}{\pi} \cdot e \right) $ contains the integer $6$
  • The interval of $s$ satisfying $|s \pi - 7| < \epsilon$ and $|s e - 6| < \epsilon$ is $(2.2027, 2.23671)$
    • There are no integers in the interval $(2.2027 \cdot 1.4142, 2.23671 \cdot 1.4142)$
• The interval of $s$ satisfying $|s \pi - 8| < \epsilon$ is $s \in \left( \frac{8-\epsilon}{\pi}, \frac{8+\epsilon}{\pi} \right) $

and so forth.

Answer 2

Such $s$ leads to good rational approximations for the quotients of the components (here, $\frac \pi e\approx\frac{22}{19}$, $\frac\pi{\sqrt 2}\approx\frac{22}{10}$, and $\frac e{\sqrt 2}\approx\frac{19}{10}$). Generalizing, we look for rational approximatons $\alpha\approx \frac nm$ where more precisely $\frac{n-\epsilon}{m+\epsilon}<\alpha<\frac{n+\epsilon}{m-\epsilon}$. In other words, $\alpha=\frac{n+t\epsilon}{m-t\epsilon}$ with $-1<t<1$. Soloving for $t$, we get $$\tag1t=t(n.m)=\frac{\alpha m-n}{(1+\alpha)\epsilon} $$ and thus are looking for a rational approximation $\frac nm$ with $$\left|\alpha-\frac nm\right|<\frac{(1+\alpha)\epsilon}{m}$$ We see that we really want to rationally approximate our number $\alpha$ (in fact several numbers simultaneously) with a relative error $\sim\epsilon$. The trial method described in Hurkyl's answer is certainly simple and good enough for many applications - as long as $\epsilon$ is not too small and the quotients are not "too irrational".

In more complex cases one may save time by going more systematically through the good enough rational approximations. Playing around with Farey fractions may be of good help there.

Example computation: $\frac{\pi}{\sqrt 2}$ is between $\frac 21$ and $\frac 31$. Using $(1)$, we find $t(2,1)\approx 0.86$, which is good enough (whereas the multiple $t(4,2)\approx 1.7$ is not); but $t(3,1)\approx -3$ is bad. Next we try the Farey sum $\frac{2+3}{1+1}=\frac 52$: $t(5,2)\approx -2.2$ is bad. We try the next Farey sum (noting that $\frac 52$ replaces $\frac 31$ because their $t$-values are both negative) $\frac{2+5}{1+2}=\frac 73$. As $t(7,3)\approx -1.3$, we continue with $\frac{2+7}{1+3}=\frac 94$. As $t(9,4)\approx -0.44$ have found another candidate (in fact two candidates as $t(18,8)\approx -0.88$ is good as well). Now we have to test both $\frac{2+9}{1+4}=\frac {11}5$ and $\frac{9+7}{4+3}=\frac{16}{7}$. We find that $t(11,5)\approx 0.42$ and $t(22,10)\approx 0.83$, whereas $t(16,7)\approx -1.7$. So far we have found the first few terms of a sequence of candidate fractions or perhaps rather proportions (because we want to distinguish forms that are not in shortest terms) (not necessarily in shortest terms), roughly in ascending order of either part $$2:1, 9:4, 18:8, 11:5, 22:10, \ldots $$ We can concurrently generate the corresponding sequences for $\frac\pi e$ and $\frac e{\sqrt 2}$ and readily find the smallest "match", leading to $\pi:e:\sqrt 2\approx 22:19:10$. From here, it is straightforward to find the smallest $s$.