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

The least rational number greater than $\sqrt{2}$ that can be written as a ratio of integers $x/y$ with $y\le10^{100}$ can be found in a moment using a little Python program. Can anyone write a program that finds, in hours rather than centuries, the least rational greater than $\sqrt{2}$ of the form $x/y^2$ with $y^2\le 10^{100}$?

More generally, my question is whether the following computation is known to be feasible or not feasible:

Given $N$, find the least rational greater than $\sqrt{2}$ of the form $x/y^2$, with $x$ and $y$ integers and $y^2\le N$. For definiteness, let's say that the output should be the required rational written in lowest form.

By a feasible computation I mean one that can be done in $O((\log N)^k)$ bit operations for some constant $k$.

Of course the square root of 2 is not essential here. Any irrational would do, as long as comparisons with rationals are feasible. I don't know of any such irrational for which I can answer the question I've posed.

share|improve this question
    
You would mean "in lowest terms", I suppose. –  Charles Matthews May 17 '11 at 11:55
    
@Charles: Thanks. I've edited. –  SJR May 17 '11 at 12:07
    
see also mathoverflow.net/questions/22868/… –  Junkie May 18 '11 at 4:02
    
In essence, you're trying to find $x,y$ with $x^2-2y^4$ small. For any fixed integer $c$, $x^2-2y^4=c$ has only finitely many solutions, but it may not be easy to find them. This makes me think it's hard to solve your problem (although it's very far from a convincing argument). Maybe it suggests at least that the literature on diophantine equations like $x^2-2y^4=c$ is a good place to start. –  Gerry Myerson May 18 '11 at 6:09
    
@Gerry: It may be that I'm really trying to make $x^2-2y^4$ small, but this puzzles me, because I don't have any idea whatsoever how lopsided is asymmetric (i.e. from above) approximation of $\sqrt{2}$ by fractions with square denominator. Maybe the numbers $x/y^2$ I'm looking for are often not very good approximations, which would make singling them out via values of $x^2-2y^4$ rather delicate. –  SJR May 18 '11 at 9:27

2 Answers 2

The following "aglorithm" gives not necessarily the best solution but yields fairly "good" solutions.

Start with a $n$ "bad" rational approximations $x_1/y_1,\dots,x_n/y_n$ of $2^{1/4}$ (obtained eg. by considering a few convergents of $2^{1/4}$) such that $y_1 \dots y_n < N$ and consider a linear combination $\sum_{i=1}^n a_i(x_i/y_i)^2=x/(y_1\cdots y_n)^2$ with $a_i\in \mathbb Z,\sum_{i=1}^na_i=1$ which is slightly larger than $\sqrt 2$. One way to get coefficients $a_1,\dots,a_n\in \mathbb Z$ with $\sum a_i(x_i/y_i)^2$ close to $\sqrt{2}$ is by using the LLL-algorithm: Consider the $(n+1)-$dimensional sublattice $\Lambda$ of $\mathbb R^{n+2}$ spanned by $f_1=(1,0,0,\dots,0,A(x_1/y_1)^2)$, $f_2=(0,1,0,\dots,0,A(x_2/y)^2),\dots$, $f_n=(0,0,\dots,1,0,A(x_n/y_n)^2)$, $f_{n+1}=(0,\dots,0,1,A\sqrt 2)$ where $A$ is some huge real number (one can also work with an integral lattice by rounding off the last coordinate to the nearest integer for a fixed large real number $A$). A short vector of the form $(a_1,\dots,a_n,1)$ in $\Lambda$ yields a good rational approximation $\sum_{i=1}^n a_i(x_i/y_i)^2$ of $\sqrt 2$ . About half of the time, such an approximation should have the correct sign. A few LLL runs for various large constant values of $A$ (which should be larger than $\max (y_i^2)$, perhaps $A\sim \sqrt{N}$ is interesting) and various finite sets $x_1,\dots,x_n$ (with $n$ also varying) should give interesting approximations.

share|improve this answer
    
Thanks Roland. I am interested in efficient ways to get "good" approximations. Do you know anything about the exponents $e$ such that the method you describe gives approximations $x/y^2$ with $|x/y^2-\sqrt{2}|<y^e$? –  SJR May 17 '11 at 13:36
    
@Roland: By the way, I am not sure that the rational $x/y^2$ to be computed in my question is always "good" approximation to $\sqrt{2}$. It might even be (for all I know) that for all but finitely many $N$ the best approximations $x/y^2$ with $y^2\le N$ are LESS than $\sqrt{2}$. –  SJR May 17 '11 at 14:07

You should try the algorithms in Elkies' paper (from 2000) "Rational points near curves ..." http://arxiv.org/abs/math/0005139 . His idea is to cover the curve with a bunch of small rectangles, and use lattice basis reduction within each such region. He proves a result which either says that there are small number of solutions or all the solutions lie on a line.

share|improve this answer
    
@Victor: Elkies paper looks interesting. I suppose you have in mind finding small values of $x^2−2y^4$, and Elkies ideas certainly seem relevant to this. On the hand, it seems that his approach, no matter how practical, is nonfeasible. What I'm really hoping for is a proof that the type of problem I stated is nonfeasible, or at least ways to reduce the general problem to other problems whose complexity has been studied. –  SJR Jun 8 '11 at 13:55

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.