# Efficient computation of the least fraction with square denominator greater than the square root of 2.

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.

-
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
–  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

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.
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
@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