Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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 '10 at 14:22
1  
The only known in two unknowns. –  Wadim Zudilin Apr 30 '10 at 14:28
    
The arxiv article seems to be arxiv.org/abs/0907.1356 –  j.c. Apr 30 '10 at 14:35
1  
"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 '10 at 15:28
1  
@Buzzard: That is false - he might be saying that your equation is not known. –  Dror Speiser Apr 30 '10 at 19:42

1 Answer 1

up vote 11 down vote accepted

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]

share|improve this answer
    
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 '10 at 22:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.