Linear minimization over two integers

73 Views Asked by At

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)?

1

There are 1 best solutions below

0
On BEST ANSWER

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.