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

  • $\begingroup$ Calling vectors $v$ and $x$ as in your question 'orthogonal' seems like an abuse of terminology …. $\endgroup$
    – LSpice
    Dec 25, 2017 at 20:30
  • $\begingroup$ @LSpice Thanks, I just edited that. $\endgroup$ Dec 25, 2017 at 20:40

1 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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