10
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks! Technically, I have another account on here, but I don't have the log-in information anymore. (It would be great if an administrator could merge the two accounts.) $\endgroup$ Nov 10, 2014 at 19:28
  • $\begingroup$ Do you mean instead to express the fact that gcd(c,d) is 1? $\endgroup$ Nov 10, 2014 at 19:42
  • 1
    $\begingroup$ See mathoverflow.net/help/merging-accounts . $\endgroup$ Nov 10, 2014 at 20:08
  • $\begingroup$ Pace, you may also wish to look here regarding your account: meta.mathoverflow.net/q/15/778 $\endgroup$ Nov 11, 2014 at 16:55

2 Answers 2

9
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Oops, the lower bound in terms of the vertical line is slightly off, but it is within a factor of 2. $\endgroup$
    – S. Carnahan
    Nov 11, 2014 at 8:30
  • $\begingroup$ Scott, here is an alternate solution, which avoids the special nature of $\mathbb{Z}$. Still pass to $SL_2(\mathbb{Z})$ (or $PSL_2(\mathbb{Z})$). The question becomes whether the group has "bounded generation"--which is classical. The standard proof that the answer is "no" follows by finding a finite index subgroup which is free. Quite interestingly, $SL_3(\mathbb{Z})$ does have bounded generation! $\endgroup$ Nov 13, 2014 at 17:55
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "For the pair (70,99) the fastest descent is..." This might be silly to ask, but why is this the fastest descent? What is the proof? $\endgroup$ Nov 10, 2014 at 18:57
  • 1
    $\begingroup$ It may be that the most convincing proof is to work backwards: find all pairs that reach the target in one step, then find all that reach the target in two steps, and so on. $\endgroup$ Nov 10, 2014 at 19:48

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.