Applications of pattern-free continued fractions

Question

Questions about continued fractions reminded me about a related diophantine problem. I am not quite sure that diophantine equations are still in fashion but $$ 1^k+2^k+\dots+(m-1)^k=m^k, $$ the Erdős--Moser equation, is quite special. This seems to be the only known equation in two unknowns ($k$ and $m$ are assumed to be positive integers) for which it is not proven whether there are finitely many solutions. Presumably there is only one solution, $1^1+2^1=3^1$. In a joint work with Yves Gallos and Pieter Moree (the preprint is available from arxiv.org), we show that, if a solution exists, then $m>10^{10^9}$ "by showing that $2k/(2m-3)$ is a convergent of $\log 2$ and making an extensive continued fraction digits calculation of $(\log 2)/N$, with $N$ an appropriate integer." Trying to build up some history on the use of continued fractions in diophantine equations, we could not find any other example besides the continued fractions of real quadratic irrationalities with their ultimate relation to Pell's equation (which in turn appears in studying some other equations). I am definitely interested if there are some, but also in other "serious" applications of "generic" (presumably pattern-free) continued fractions of mathematical constants (or functions) outside number theory. Please suggest "generic" cases where no rule for partial quotients is known.

Answer 1

Continued fractions are used in the effective solution of Thue equations. Given such an equation, say $x^4-3x^3y+7x^2y^2-y^4 = 1$ to be specific, we can brute force find all small $x,y$ solutions, and linear forms in logarithms results can be used to eliminate solutions with $x,y$ astronomically large. In the large intermediate range (which typically can mean $x,y$ with between 50 and $10^{50}$ digits, depending on the specifics of the equation) LLL is often helpful. The small intermediate range (say $x,y$ having between 3 and 50 digits) is where continued fractions make their appearance.

An example of this is the following. The equation given above is the same as $$r^4 - 3r^3 + 7 r^2 -1 = 1/y^4$$ where $r$ is the rational $x/y$. This factors (for some complex numbers $\alpha_i$) as $$(r-\alpha_1)(r-\alpha_2)(r-\alpha_3)(r-\alpha_4) = \frac{1}{y^4}.$$ Since the right hand side is small, one of the factors on the left must be small, say it's the first that is smallest. Letting $C=(\alpha_1-\alpha_2)(\alpha_1-\alpha_3)(\alpha_1-\alpha_4)/8$, our equation gives the inequality: $$\left| \alpha_1 - \frac xy \right| < \frac{2/(C y^2)}{2y^2}.$$ If $y$ is large enough (typically, say, 3 digits), then $2/(C y^2)<1$, and a theorem from a couple centuries ago states that if $$\left| \alpha - \frac xy \right| < \frac{1}{2y^2},$$ then $x/y$ is a convergent of the continued fraction of $\alpha$. This means that every solution to the original equation (except for the small ones) is a convergent to one of the roots of the equation, and numerators and denominators of convergents grow exponentially. So, as a practical matter, we can find all solutions of a Thue equation with between 3 and 50 digits essentially instantaneously.

Disclaimer: all statements here about how many digits constitutes large or small depend on the specific equation (among other things, on the embeddings into $\mathbb{C}$ of the group of fundamental units of the relevant extension of $\mathbb{Q}$), and the numbers I've given here derive from my personal experience. Some years ago, I worked at Wolfram Research to help bring diophantine equation solving to Mathematica, it will solve the above equation if you input:

Reduce[x^4 - 3 x^3 y + 7 x^2 y^2 - y^4 == 1, {x, y}, Integers]