3
$\begingroup$

Let $S = \{(x,y,z)\ : \ x,y,z \in \mathbb Z, \gcd(x,y,z) = 1\}$, I would like to investigate the connectedness of $S$, considered as an (infinite) graph, where two vertices $(x,y,z)$ and $(a,b,c)$ are connected by an edge iff $ax+by+cz = 1$.

After some experiment I conjectured that $S$ is connected. My thoughts: let's start from $(1,0,0)$, and we can reach $(1,a,b)$ for all $a,b\in\mathbb Z$. From there we can proceed to $(x, y, z)$ for all $\gcd(y,z)=1$, by a simple application of Bézout's theorem on $(y, z)$. This is already quite close to our goal. But it gets much more complicated to proceed from here, since there is this strange constraint on $y$ and $z$. And even if we successfully characterize $\{(a,b,c)\ : \ \exists x,y,z, \gcd(y,z)=1 \wedge ax+by+cz=1\}$, there are still more work to do because it does not seem to cover the whole $S$.

On the other hand, maybe we could somehow start from an arbitrary element in $S$ and work our way back to $(1,0,0)$, by defining some strictly decreasing measure, but I can't think of a good way to proceed yet.

By the way, another subject of interest is the minimum number of steps it takes to get from $(x,y,z)$ to $(1,0,0),(0,1,0)$ or $(0,0,1)$ (i.e. the graph-theoretic distance). But it is not relevant here.

Any help is appreciated!

$\endgroup$
1
  • $\begingroup$ Nice question! The interesting invariant to track of a triple $(a, b, c)$ seems to be $(\gcd(b, c), \gcd(a, c), \gcd(a, b))$, and the interesting case is when all of these are greater than $1$ (your argument shows that if any of them is equal to $1$ then we can connect to $(1, 0, 0), (0, 1, 0)$, or $(0, 0, 1)$ in two steps). $\endgroup$ Aug 29, 2020 at 23:26

1 Answer 1

2
$\begingroup$

Aha! In fact the interesting number to track turns out to be

$$m(a, b, c) = \text{min}(\gcd(b, c), \gcd(a, c), \gcd(a, b));$$

we can arrange for this to be strictly decreasing (in fact exponentially strictly decreasing), so it eventually hits $1$, and then your observation shows we hit $(1, 0, 0), (0, 1, 0)$, or $(0, 0, 1)$ (each of which is connected to, say, $(1, 1, 1)$) in two more steps. That is, every triple $(a, b, c)$ connects to $(1, 1, 1)$ in at most

$$\lfloor \log_2 m(a, b, c) \rfloor + 3$$

steps. As an easy upper bound note that we have $m(a, b, c) \le \text{min}(a, b, c)$, and with a little more effort we can show that $m(a, b, c) \le \text{min}(\sqrt{a}, \sqrt{b}, \sqrt{c})$, although this improves the bound by $1$ so it doesn't matter much.

We can see this as follows. Let's start with any triple $(a, b, c)$ whatsoever. WLOG let $d = \gcd(b, c) = m(a, b, c)$ be minimal. Then any triple $(x, y, z)$ this triple is connected to satisfies $ax + by + cz = 1$ by definition, hence $d | ax - 1$, or equivalently $x \equiv a^{-1} \bmod d$. This is actually the only constraint on $x$; given such an $x$ we can always find suitable $y, z$ by Bezout. Hence we can arrange for $x$ to be an integer congruent to $a^{-1} \bmod d$ between $-\frac{d}{2}$ and $\frac{d}{2}$ (which is unique if $d$ is odd and almost unique if $d$ is even); if we do so, then we've connected $(a, b, c)$ to a triple $(x, y, z)$ such that $\gcd(x, y) \le |x| \le \frac{d}{2}$, so $m(x, y, z) \le \frac{d}{2}$. Now we can repeat the same construction but in the third variable, etc. After logarithmically many steps we hit a triple with $m(-, -, -) = 1$.

Example. Consider the triple $(15, 21, 35)$, so that $m(15, 21, 35) = \text{min}(7, 5, 3) = 3$. The smallest gcd is $\gcd(15, 21) = 3$, so we expect to be able to connect this to a triple $(x, y, z)$ such that $z \equiv 35^{-1} \equiv 2 \bmod 3$; the unique such $z$ between $-\frac{3}{2}$ and $\frac{3}{2}$ is $-1$, so we can take $z = -1$ and now we need to find $x, y$ such that

$$15x + 21y - 35 = 1$$

or $15x + 21y = 36$ or $5x + 7y = 12$. Happily we can take $x = y = 1$ so this is clear. So $(15, 21, 35) \to (1, 1, -1)$ in one step.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .