## Applications of pattern-free continued fractions

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

-
The only known equation? Really? That seems implausible, especially since the equation doesn't depend in a particularly simple way on m. There have to be plenty of difficult Diophantines you can write down this way. – Qiaochu Yuan Apr 30 2010 at 14:22
The only known in two unknowns. – Wadim Zudilin Apr 30 2010 at 14:28
The arxiv article seems to be arxiv.org/abs/0907.1356 – jc Apr 30 2010 at 14:35
"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.". As a consequence, you are saying you must know whether the equation 1^k+3^k+5^k+...+m^k=(m+2)^k+3879113 has finitely many solutions or not! – Kevin Buzzard Apr 30 2010 at 15:28
@Buzzard: That is false - he might be saying that your equation is not known. – Dror Speiser Apr 30 2010 at 19:42
show 2 more comments

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]

-
 Excellent! Thank you for this answer (with which I should be familiar). I keep your answer unaccepted, just vote, to have more (to choose). – Wadim Zudilin Apr 30 2010 at 22:30