Markov unchained

Ashleigh Wilcox

20 May 2024

• Click to share on X (Opens in new window)
• Click to share on Facebook (Opens in new window)
• Click to share on Reddit (Opens in new window)
• Click to share on LinkedIn (Opens in new window)
• Click to share on Threads (Opens in new window)
• Click to share on Mastodon (Opens in new window)

Diophantine equations are polynomial equations with integer coefficients for which we are interested in finding integer solutions. These equations are named after Diophantus of Alexandria, a third century Greek mathematician, who was interested in finding out whether these equations were soluble in integers.

These equations have held mathematicians’ interest ever since. In 1900, David Hilbert outlined 23 problems to shape the future of mathematics. The tenth of these was to provide an algorithm, to decide whether a Diophantine equation is solvable in integers.

In 1970, Matiyasevich proved that a general algorithm was not possible, and now researchers try to solve specific classes of equations. There are also a number of questions researchers like to ask in this area, many of which are shown in the flowchart below.

The question you are trying to answer can dramatically affect the difficulty of the problem. For example, you may easily check that the equation
$$
xy-zt=1
$$
has an integer solution $(x,y,z,t)=(2,5,3,3)$. The eagle-eyed among you may spot that this equation has infinitely many integer solutions. For example, for any integer $u$,
\[(u+1)\times 1- u \times 1 = 1,\]
hence we have an infinite family, namely $(x,y,z,t)=(u+1,1,u,1)$. However, describing all integer solutions to this equation in parametrised form is a much more difficult task. In fact, the solution to this equation requires 46 parameters, as proved by Vaserstein in 2010, but due to the complex nature of these polynomials, the solution has never been written explicitly; but it is possible, in theory.

Let us now look at a well-known example, the Pythagoras equation
$$
a^2+b^2=c^2.
$$
In school, you may have been tasked with finding three positive integers that ‘work’ in the above equation. You may instantly think $3^2+4^2=5^2.$ This quickly answers ‘yes’ to the question: does the Pythagoras equation have an integer solution?

It is easy to see that if we enlarge the triangle by any scale, we obtain a similar triangle. We can apply this same idea to the solution $(a,b,c)=(3,4,5)$: if we multiply this solution by any integer $u$, we obtain another integer solution to the Pythagoras equation, ie $(a,b,c)=(3u,4u,5u)$. We can confirm that this really is a solution:
\begin{align*}
a^2+b^2&=(3u)^2+(4u)^2=9u^2+16u^2 \\ &=25u^2=(5u)^2=c^2.
\end{align*}
By finding the infinite family $(a,b,c)=(3u,4u,5u)$ for all integers $u$, we have now also positively answered the question: ‘Does the equation have infinitely many integer solutions?’ However, describing every Pythagorean triple is not as easy a task. Thankfully it is doable. In fact, we can write all integer solutions to the Pythagoras equation as either
$$
(a,b,c)=(2uvw,u(w^2-v^2),u(w^2+v^2)),
$$
for integers $u,v,w$, or in the same way but with the expressions for $a$ and $b$ swapped.

Challenge: Prove that all integer solutions to the Pythagoras equation are covered by the above description.

The cuboid equation

Diophantine equations are not all about Pythagoras though. We could also consider problems involving products and squares. We’ve already considered triangles, so now let’s look at cuboids. For example, we could ask: For what integer dimensions of a cuboid is its volume equal to the square of its diagonal? Mathematically we can write this as:

Find all positive integers solutions $(x,y,z)$ to
$$
x^2+y^2+z^2=xyz.
$$

We will refer to this equation as the cuboid equation.

As we are considering the problem geometrically, $x,y,z$ must all be positive. In fact, if we find all positive integer solutions to the cuboid equation, we can use this to describe all integer solutions to the equation, by taking all combinations of signs that make the right hand side positive. That is, if $(x,y,z)$ is a solution, then $(x,-y,-z)$, $(-x,y,-z)$, and $(-x,-y,z)$ are also solutions.

Where are the solutions?

So, how can we find all positive integer solutions to the cuboid equation?

One strategy could be to try values of $n\geq 0$ in increasing order, set $n=xyz$, and see if any of its finitely many divisors are solutions to the equation. We can do these searches on a computer, such as by using the Reduce function in Mathematica. If we try all values of $n \leq 50$, we obtain the integer solutions $(0,0,0)$ and $(3,3,3)$. This strategy seems inefficient as we have looked at the factors of $50$ numbers and only found two integer solutions.

Instead of searching for factors of $n=xyz$, another method could be to try to find integer solutions to the cubic equation satisfying $\max(x,y,z)\leq m$. In this case, if we let $m=6$, we obtain the solutions found previously, as well as $(3,3,6),$ $(3,6,3)$ and $(6,3,3)$. This seems like a more efficient way of finding integer solutions to the cuboid equation, as we obtain five solutions when $m=6$, as opposed to the two solutions we found when $n=50$.

An observant reader may notice that the three extra solutions we have obtained are equivalent up to the permutation of $x,y,z$, so you could argue that we have only found one extra solution, which is still better, but it seems less impressive. These permutations are possible because the cuboid equation is symmetric: if we permute the variables in the equation, we obtain the same equation. Therefore to reduce the necessary computation power and increase the efficiency of finding all positive integer solutions up to a bound, we may only consider the solutions with $x \geq y \geq z \geq 0$, and then take all permutations.

We can then try using Mathematica to find all the solutions satisfying $x \geq y \geq z \geq 0$ with $\max(|x|,|y|,|z|)\leq m$. Taking $m=100$ gives $6$ solutions. Increasing $m$ to 1000, we obtain $11$ solutions. Interestingly, increasing $m$ to 10,000 only finds $17$ integer solutions.

This experimentation suggests that the equation may have infinitely many integer solutions, but the distance between them significantly increases. It is clear that using a ‘brute force’ style method is inefficient and impossible.
So, we need another strategy.

Looking at the solutions found earlier, we could conjecture that all integer solutions are divisible by $3$. In fact, if $x$ is divisible by $3$, then $y^2+z^2$ must also be divisible by $3$. Perfect squares modulo $3$ are either equal to $0$ or $1$, so for the sum of two squares to be equal to $0$ modulo $3$, they must both be equal to $0$ modulo $3$. This proves that if one of $x,y$ and $z$ is divisible by $3$, then they must all be divisible by $3$. Further analysis modulo $3$ proves that $x,y$ and $z$ all being multiples of $3$ is, in fact, the only possibility when seeking a solution.

If we make the substitutions $x=3X$, $y=3Y$ and $z=3Z$ for integers $X,Y,Z$, and cancel $9$, we obtain the equation
$$
X^2+Y^2+Z^2=3XYZ.
$$
This is a famous equation, known as the Markov equation, first studied by Andrey Markov in around 1880. We can prove that for every integer solution to the Markov equation, the solutions obtained by the transformations
\begin{equation}\label{markov:these_three}\left.\begin{split}
(X,Y,Z) &\to (3YZ-X,Y,Z), \\
(X,Y,Z) &\to (X,3XZ-Y,Z), \\
(X,Y,Z) &\to (X,Y,3XY-Z),
\end{split}\hspace{6mm} \right\} \hspace{-10mm} \tag{1}
\end{equation}
are also integer solutions. We will see where these transformations come from later. For now, we can show that this is true by substituting these transformed solutions into the Markov equation. For example, for $(3YZ-X,Y,Z)$, we see that
\begin{align*}
\text{LHS}
&=(3YZ-X)^2+Y^2+Z^2 \\
&=9Y^2Z^2-6XYZ + X^2+Y^2+Z^2\\
&=9Y^2Z^2-6XYZ + 3XYZ\\
&=3(3YZ-X)YZ\\
&=\text{RHS}.
\end{align*}
Hence, if we find one non-trivial integer solution—ie a solution $(X,Y,Z)\neq (0,0,0)$—then we can make the three transformations and obtain new integer solutions. Similar analysis can be applied to the new $Y$ and $Z$ values, and we can show that these are genuinely new solutions, not ones we have found before.

You may have noticed that $(X,Y,Z)=(1,1,1)$ is a non-trivial integer solution to the Markov equation. In fact, excluding $(0,0,0)$, we can obtain all integer solutions to this equation from $(X,Y,Z)=(1,1,1)$ by applying the transformation $(X,Y,Z) \to (3YZ-X,Y,Z)$, permuting the variables, and swapping between positive and negative numbers. Therefore, the equation has infinitely many integer solutions, which implies that the cuboid equation also has infinitely many integer solutions.

Now, we just need to figure out how to describe them all.

Happy descriptions

Describing all integer solutions to equations can be done in many different ways. My personal preference is to describe the integer solutions by listing a solution and the necessary transformations to obtain all other solutions to the equation. Some people may not like this method of describing solutions, and may instead prefer to present them differently, such as by using a recursive description. It is a matter of taste for how solutions are presented and whether you think a description is ‘acceptable’. If you aren’t keen on the descriptions to solutions presented in this article, you are more than welcome to describe them in an alternative manner.

Let’s now return to the Markov equation. First, we will determine the necessary transformations to find every ‘similar’ solution: we can change the signs of a solution as long as the right hand side is positive, just like we did for the cuboid equation, and we can permute the variables. We can summarise these transformations more concisely as
\begin{equation}\label{markov:this_one}\left.\begin{split}
(X,Y,Z) &\to (-X,-Y,Z), \\
(X,Y,Z) &\to (Y,X,Z), \\
(X,Y,Z) &\to (X,Z,Y).
\end{split}\hspace{6mm} \right\} \hspace{-10mm} \tag{2}
\end{equation}
Note that applying any of these transformations twice returns us to the solution we started with. However, by applying these transformations in different orders, we can obtain all the ‘similar’ solutions to $(X,Y,Z)$.

It can be proven that all non-trivial integer solutions to the Markov equation can be obtained by a sequence of the three transformations in \eqref{markov:this_one} and
$$
(X,Y,Z) \to (3YZ-X,Y,Z)
$$
to the solution $(X,Y,Z)=(1,1,1)$.

If we want to solve the cuboid equation, then we can either take every integer solution to the Markov equation and multiply it by $3$; or we can describe all integer solutions to the cuboid equation from the solution $(x,y,z)=(3,3,3)$ and apply a sequence of the transformations in \eqref{markov:this_one} and $$(x,y,z) \to (yz-x,y,z).$$

This method of finding solutions can be drawn as a tree, as shown at the top of the next page. The tree diagram shows the rapid growth of integer solutions. Here, we only show integer solutions satisfying $x \geq 0$, $y \geq 0$ and $ z \geq 0$ to the cuboid equation: if we wanted to show all the ‘similar’ solutions too, we would need much more space!

The positive integer solutions to the cuboid equation

The method we have used to describe all integer solutions to the Markov equation
is called Vieta jumping and it is very powerful.

Vieta jumping

If we start with a one-variable quadratic equation $a x^2 + b x + c = 0$ with two solutions, say $x_1$ and $x_2$, then $x_1 + x_2 = -b/a$. So, for any given equation, if we find one solution, we can obtain another.

Let’s see this on a two-variable equation,
\[x^2 + x y + y^2 = 1.\]
We can easily see that $(x,y)=(1,0)$ is a solution. If we substitute $x=1$ into the equation, we obtain $1+y+y^2=1$, which is a quadratic equation in $y$ and it has a solution $y=0$. Applying Vieta jumping to it, we find that it also has solution $y=-1/1-0 = -1$, and we obtain $(x,y)=(1,-1)$ which is a solution to the original two-variable equation. If we do the same trick with the variables $x$ and $y$ swapped, we find another solution $(x,y)=(0,-1)$ to our two-variable equation.

So, taking any integer solution $(x,y)=(x_0,y_0)$, we can substitute $y=y_0$ into the equation and obtain an equation that is quadratic in $x$, which has a solution $x=x_0$. Then, by Vieta jumping, it must also have a solution $x=-y_0-x_0$.
Similarly, by substituting $x=x_0$ in the equation and doing Vieta jumping in $x$, we can conclude that $(x,y)=(x_0,-x_0-y_0)$ is also a solution. By starting with any integer solution to the equation, we can obtain an infinite chain of solutions.

The Markov equation can be considered as a quadratic in any of the variables. If we apply this trick to the equation separately for each of the variables, we have three jumps, and these are the transformations in \eqref{markov:these_three}.

While in this article we have used the Vieta jumping method to describe all infinitely many integer solutions to equations, for some equations, we can also use this method to show that the equation has finitely many or no integer solutions!

Ashleigh Wilcox

Ashleigh is a PhD student and graduate teaching assistant at the University of Leicester. Her main mathematical interests are in number theory. She is passionate about outreach and inclusion in mathematics, volunteers as a STEM ambassador and is a representative for the Piscopia Initiative.

All articles by Ashleigh