A back and forth Euclidean algorithm over the integers--does it have bounded length?

Question

cLet $a,b,c,d\in \mathbb{Z}$ and suppose we have the equation $ac+bd=1$. One way of thinking about this equation is it expresses the fact $\gcd(c,d)=1$. It is well-known that all other similar equations expressing that fact are of the form $(a+td)c+(b-tc)d=1$ for some $t\in\mathbb{Z}$.

Letting $a'=a+td,b'=b-tc$, one may ask if there is a "best" choice for $t$; or equivalently, if there is a best choice for $a',b'$. In some sense, the usual Euclidean algorithm (applied to $b,d$) gives a minimal linear combination--we'll call the resulting pair $(a',b')$ the Euclidean pair. But there are sometimes other situations where a different choice of $t$ is optimal. In any case, we can pass from $ac+bd=1$ to $a'c+b'd=1$.

Now, we can view this latter expression as a linear combination showing that $\gcd(a',b')=1$. So we can repeat the process to get a new $b',d'$ so that $a'c'+b'd'=1$. Continuing in this fashion by replacing either the $(a,c)$ pair or the $(b,d)$ pair with a new pair $(a',c')$ or $(b',d')$ respectively, then after a finite number of steps we can always reach the equation $1\cdot 1+ 0\cdot 0=1$. (One way to do this is just use the Euclidean pair for each replacement, except possibly at the end when one may need to pass from $0\cdot 0+1\cdot 1=1\mapsto 1\cdot 1+0\cdot 0=1$.)

My question is: Starting with any quadruple of integers $a,b,c,d\in\mathbb{Z}$ with $ac+bd=1$, is there an absolute bound $n\gg 0$ so that by performing some sequence of back-and-forth switching as described above we get to $1\cdot 1+0\cdot 0=1$ within at most $n$ steps?

The greedy algorithm of simply choosing the Euclidean pair will not give an absolute bound $n$, since we can easily construct a sequence which requires an arbitrarily large number of steps this way. But using the Euclidean pair is not always the best choice.

---

By the way, this number theory question originally arose in my study of perspective decompositions of the abelian group $\mathbb{Z}\oplus \mathbb{Z}$. The connection comes from associating nontrivial idempotents $E\in \mathbb{M}_2(\mathbb{Z})$ with 4-tuples $(a,b,c,d)$ satisfying $ac+bd=1$, by writing $E=\begin{pmatrix}ac & bc\\ ad & bd\end{pmatrix}$. [Here, $a$ is the gcd of the first column, etc...]

Further, I have a very ad hoc way of showing that the question above has a negative answer if we replace $\mathbb{Z}$ with the ring $\mathbb{F}_2[x]$. In that case, one can show that using Euclidean pairs is optimal.

Answer 1

We get an isomorphic problem by switching $c$ with $d$, and replacing $b$ with $-b$. Then we are considering matrices $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ in $SL_2(\mathbb{Z})$. Passage from $(a,b)$ to $(a',b')$ amounts to multiplication by a matrix $T^t = \begin{pmatrix} 1 & t \\ 0 & 1 \end{pmatrix}$ for some $t \in \mathbb{Z}$, and switching between $(a,b)$ and $(c,d)$ is (up to sign) given by multiplication by $S = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$. The question then amounts to whether there is a uniform bound on the length of words in $S$ and $T^t$ (as $t$ ranges over integers) describing elements of $SL_2(\mathbb{Z})$, and the answer is that such a bound does not exist.

One way to see this is by examining the geometry of Ford circles in the complex upper half-plane. $T$ translates the half-plane by integers (preserving the cusp at infinity), and $S$ more or less takes cusps to their reciprocals. Thus, a composite of $S$ with $T^t$ takes the circle at infinity to a circle tangent to it. A word describing an element $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ then necessarily has length at least as long as the chain of circles connecting the cusp at infinity with the cusp $a/c$, and such chains of circles have unbounded length (indeed, they have a sharp lower bound given by the length of signed continued fractions - the shortest word is the chain of circles touching the vertical line with real part $a/c$).

Answer 2

Consider the convergents $3/2, 7/5, 17/12, 41/29, 99/70, \cdots$ to $\sqrt{2}.$ For the pair $(70,99)$ the fastest descent is

$$29\cdot 99-41\cdot 70=$$ $$17\cdot 29-12\cdot 41=$$ $$5\cdot 17- 7\cdot 12=$$ $$3 \cdot 5 - 2\cdot 7=$$

Starting from the convergents to a number $1 \lt r \lt 2$ this will pretty much be the case. At the worst you would need to skip every other convergent. This happens where there is a $1$ in the continued fraction.

So the worst case is the convergents $2/3,3/5,5/8,8/13,13/21,21/34,34/55,55/89,144/89\cdots$ to the golden ratio which lead to

$$34\cdot 144-55\cdot 89=$$ $$13\cdot 55-21\cdot 34=$$ $$5\cdot 21- 8\cdot 13=$$

Later Here I am making the assumption that the fastest descent is the one which minimizes $|a|+|b|$ at each stage. That is true but I did not prove it. I will not prove it here but I'll give an illustration. That isn't a proof, but it may be convincing and might suggest what the precise things to prove would be.

For fixed coprime $c,d \gt 1$ there are two solutions $a',b'$ and $a'',b''$ to $ac+bd=1$ with $|a|+|b| \lt c+d.$ One has $-d \lt a' \lt 0 \lt b' \lt c$ and the other, $a'',b''=a+d,c-b'$ has $-c \lt b'' \lt 0 \lt a'' \lt d.$ Some inequalities will be weak when $\min(c,d) \le 1.$

There are special aspects of the lovely example $70,99$ which might be distracting so let me use instead $70,129$

I'll write $$[70, 129] ==> [-293, 159], [-164, 89], [-35, 19], [94, -51], [223, -121]$$ to indicate the first few possible pairs $[a,b].$

The continuations are

$$ [35, 19] ==> [-32, 59], [-13, 24], [6, -11], [25, -46], [44, -81]$$

$$ [51, 94] ==> [-223, 121], [-129, 70], [-35, 19], [59, -32], [153, -83]$$

$$ [89, 164] ==> [-363, 197], [-199, 108], [-35, 19], [129, -70], [293, -159]$$

$$ [121, 223] ==> [-352, 191], [-129, 70], [94, -51], [317, -172], 540, -293]$$

$$ [159, 293] ==> [-457, 248], [-164, 89], [129, -70], [422, -229], [715, -388]$$

So I suppose a conjecture would be that, if one rejects the solution which minimizes $|a|+|b|$, then at the next stage you can't get a solution which does better than the one you rejected.