8
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ You would mean "in lowest terms", I suppose. $\endgroup$
    – Charles Matthews
    Commented May 17, 2011 at 11:55
  • $\begingroup$ see also mathoverflow.net/questions/22868/… $\endgroup$
    – Junkie
    Commented May 18, 2011 at 4:02
  • $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Commented May 18, 2011 at 6:09
  • $\begingroup$ @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. $\endgroup$
    – Sidney Raffer
    Commented May 18, 2011 at 9:27
  • $\begingroup$ Is it really the very best approximation you want to find, or would you be content with a non-trivially good one? (I'm not saying I have an answer even to that, but it feels quite a lot more feasible.) $\endgroup$
    – gowers
    Commented May 18, 2011 at 14:54

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$
    – Sidney Raffer
    Commented May 17, 2011 at 13:36
  • $\begingroup$ @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}$. $\endgroup$
    – Sidney Raffer
    Commented May 17, 2011 at 14:07
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @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. $\endgroup$
    – Sidney Raffer
    Commented Jun 8, 2011 at 13:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .