1
$\begingroup$

Given two real numbers a and b and a threshold t>0, try to find the smallest positive integer n s.t. an and bn are both close enough to some integers with their difference less than t.

I think n does not always exist. But even if there does(in big t case), a fine algorithm for n is hard to develop.

  • 0
    I am not sure I fully understand the question. What do you mean by "$an$ and $bn$ are close enough to some integers"? Specifically, what is close enough? Whose difference is less than $t$, $an$ and $bn$, or the integers they are close enough to?2012-02-27

1 Answers 1

4

I think what you're asking about is this. Given real numbers $a$, $b$ and $t > 0$, does there exist some positive integer $n$ such that $\|an\| < t$ and $\|bn\| < t$, where $\|x\| = \min_{j \in {\mathbb Z}} |x - j|$? The answer is yes, and in fact you can do somewhat better. More generally, for $m$ real numbers $a_1, \ldots, a_m$ there exist infinitely many positive integers $n$ such that all $\|a_j n\| < n^{-1/m}$. The phrase to look up is "simultaneous Diophantine approximation".

  • 0
    As for an algorithm, just try each positive integer $n$ starting at $n=1$. Using the Pigeonhole Principle, it seems to me you're guaranteed to get a "hit" in at most $\lceil 1/t \rceil^2$ tries.2012-02-28