3
$\begingroup$

Given $x\in]0,1[$, let the function $f:\mathbb{N}^+\times\mathbb{N}\to\mathbb{R}$ be defined by

$$ f(p,q) := x p - q $$

Is there an analytic formula for the minimum of $f$ under the constraint

$$ f(p,q) > 0 $$

(together with $p$ being a positive integer and $q$ a nonnegative integer)?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

For a rational $x$, there is a minimum. Suppose $x = \frac rs$ with $\gcd(r,s)=1$. Then $f(p,q) = \frac{rp - sq}{s}$, so it is a positive multiple of $\frac1s$; in particular, it must be at least $\frac1s$.

This is always achievable by the extended Euclidean algorithm: for integer $r,s$ it finds a solution $(m,n)$ to $rm + sn = \gcd(r,s)$, which is $1$ in this case. We'll get $f(m,-n)=\frac1s$. If $m>0$ and $n<0$, this is the solution we want. Otherwise, we also have $f(m+ks,kr-n)=\frac1s$ with $m-ks, kr-n>0$ for large enough $k$.

When $x$ is irrational, take the sequence $\frac{h_1}{k_1}, \frac{h_2}{k_2}, \dots$ of continued fraction approximations of $x$. In general, it is true that the even terms in this sequence give a close approximation to $x$ from below: $\frac{h_{2n}}{k_{2n}} < x < \frac{h_{2n}}{k_{2n}} + \frac{1}{k_{2n}^2}$. Rearranging, $$ 0 < k_{2n} x - h_{2n} < \frac1{k_{2n}} $$ so $f(k_{2n}, h_{2n})$ is positive but can be made as small as we want.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.