Smallest size of integral vector with certain inner product

Question

Let $v =(r,s,t) \in \mathbb{N}^3$ be a vector such that $\gcd(r,s,t)=1$. We know that there are vectors $x= (x_1,x_2,x_3) \in \mathbb{Z}^3 $ such that $v.x =1$. For each $v$, let $O(v)$ be the smallest size ($L^1$ or $L^\infty$ norm) of such $x$. Now for a natural number $n$ define $f(n)$ to be the maximum of $O(v)$, where $v$ ranges over vectors with $L^1$ norm at most n (i.e. , $r+s+t \leq n$). What is the asymptotic of $f(n)$?

Also similar question when the vector has a fixed number of entries (at least 3).

Answer 1

$f(n)$ grows linearly in $n$. It grows at least linearly as seen from the triples $(2,2,2m+1)$. But we always may achieve that all coefficients are $O(n)$. For seeing this, we search a linear representation not of $r,s,t$, but of $r,r+s,r+t$, where we assume $r=\max(r,s,t)$. These numbers, I denote them $A,B,C$, lie between $r$ and $2r$. Look at a combination $xA+yB+zC=\pm 1$ with minimal value of $|xA|+|yB|+|zC|$ and assume that it is at least $100r^2$. Without loss of generality, $x\geqslant 0$, $y\geqslant 0$ and $z\leqslant 0$. Then $|zC|=|xA|+|yB|\pm 1\geqslant 50 r$ and $-z\geqslant 25 r$. Either $xA$ or $yB$ is then at least $25 r$, thus either $x$ or $y$ is greater than $2r$ for sure. If it is $x$, we may replace $(x,y,z)$ to $(x-C,y,z+A)$ and get smaller values of $x$ and $-z$.