# Rational Points Near Curves and Small Nonzero |x3-y2| via Lattice Reduction

@inproceedings{Elkies2000RationalPN, title={Rational Points Near Curves and Small Nonzero |x3-y2| via Lattice Reduction}, author={Noam D. Elkies}, booktitle={ANTS}, year={2000} }

We give a new algorithm using linear approximation and lattice reduction to efficiently calculate all rational points of small height near a given plane curve C. For instance, when C is the Fermat cubic, we find all integer solutions of | x 3 + y 3 −z 3| < M with 0 < x ≤y < z < N in heuristic time ≪ (log O(1) N ) M provided M ≫N, using only O(log N) space. Since the number of solutions should be asymptotically proportional to M log N (as long as M < N 3), the computational costs are essentially… Expand

#### Topics from this paper

#### Paper Mentions

#### 73 Citations

Bounding the sum of square roots via lattice reduction

- Computer Science, Mathematics
- Math. Comput.
- 2010

It is shown that this problem is closely related to the shortest vector problem in certain integral lattices and an algorithm to find lower bounds based on lattice reduction algorithms is presented, whose validation implies that the algorithm runs in polynomial time and the problem of comparing two sums of square roots of small integers can be solved in poynomial time. Expand

Worst cases and lattice reduction

- Mathematics, Computer Science
- Proceedings 2003 16th IEEE Symposium on Computer Arithmetic
- 2003

A new algorithm to find worst cases for correct rounding of an analytic function, and exhibits some new worst cases found using this algorithm, for double-extended and quadruple precision. Expand

Marshall Hall's Conjecture and Gaps Between Integer Points on Mordell Elliptic Curves

- Mathematics
- 2014

For a non-square positive integer x, let k_x denote the distance between x^3 and the perfect square closest to x^3. A conjecture of Marshall Hall states that the ratios r_x = (x^(1/2))/k_x, are… Expand

Sums and differences of three kth powers

- Mathematics
- 2008

Abstract Let k > 2 be a fixed integer exponent and let θ > 9 / 10 . We show that a positive integer N can be represented as a non-trivial sum or difference of 3kth powers, using integers of size at… Expand

Searching worst cases of a one-variable function using lattice reduction

- Computer Science, Mathematics
- IEEE Transactions on Computers
- 2005

A new algorithm to find worst cases for the correct rounding of a mathematical function of one variable by extending Coppersmith's work on the integer small value problem - for polynomials with integer coefficients - using lattice reduction is proposed. Expand

Correction to “Gaps in n mod 1 and ergodic Theory”

- Mathematics
- 2005

Cut the unit circle S = R/Z at the points { √ 1}, { √ 2}, . . . , { √ N }, where {x} = x mod 1, and let J1, . . . , JN denote the complementary intervals, or gaps, that remain. We show that, in… Expand

Rational points near manifolds and metric Diophantine approximation

- Mathematics
- 2009

This work is motivated by problems on simultaneous Diophantine approximation on manifolds, namely, establishing Khintchine and Jarnik type theorems for submanifolds of R^n. These problems have… Expand

Gaps in √n mod 1 and ergodic theory

- Mathematics
- 2004

Cut the unit circle S = R/Z at the points { √ 1}, { √ 2}, . . . , { √ N }, where {x} = x mod 1, and let J1, . . . , JN denote the complementary intervals, or gaps, that remain. We show that, in… Expand

Deciding Existence of Rational Points on Curves: An Experiment

- Mathematics, Computer Science
- Exp. Math.
- 2008

This paper considers all genus-2 curves over ℚ given by an equation y 2 = f(x) with f a square-free polynomial of degree 5 or 6, and decides whether there is a rational point on the curve by a combination of techniques that are applicable to hyperelliptic curves in general. Expand

Computing elliptic curves over ℚ via Thue-Mahler equations and related problems

- Mathematics
- 2019

We present a practical and efficient algorithm for solving an arbitrary Thue-Mahler equation. This algorithm uses explicit height bounds with refined sieves, combining Diophantine approximation… Expand

#### References

SHOWING 1-10 OF 28 REFERENCES

On searching for solutions of the Diophantine equation x3 + y3 + z3 = n

- Computer Science, Mathematics
- Math. Comput.
- 1997

A new search algorithm to solve the equation x 3 + y 3 + z 3 = n for a fixed value of n > 0.5 is proposed, using several efficient number-theoretic sieves and much faster on average than previous straightforward algorithms. Expand

Geometric postulation of a smooth function and the number of rational points

- Mathematics
- 1991

This paper is devoted to giving refinements and extensions of some of the results of Bombieri and the author [1] obtaining upper bounds for the number of integral lattice points on the graphs of… Expand

On Mordell's Equation

- Mathematics
- 1998

In an earlier paper we developed an algorithm for computing all integral points on elliptic curves over the rationals Q. Here we illustrate our method by applying it to Mordell's Equation y2=x3+k for… Expand

The number of integral points on arcs and ovals

- Mathematics
- 1989

integral lattice points, and that the exponent and constant are best possible. However, Swinnerton–Dyer [10] showed that the preceding result can be substantially improved if we start with a fixed,… Expand

Heegner point computations

- Mathematics, Computer Science
- ANTS
- 1994

We discuss the computational application of Heegner points to the study of elliptic curves over Q, concentrating on the curves E d : Dy2 = x3 − x arising in the “congruent number” problem. We begin… Expand

The density of zeros of forms for which weak approximation fails

- Mathematics
- 1992

The weak approximation principal fails for the forms x + y + z = kw, when k = 2 or 3. The question therefore arises as to what asymptotic density one should predict for the rational zeros of these… Expand

Algorithms for Modular Elliptic Curves

- Mathematics
- 1992

This book presents a thorough treatment of many algorithms concerning the arithmetic of elliptic curves with remarks on computer implementation. It is in three parts. First, the author describes in… Expand

Shimura Curve Computations

- Mathematics, Computer Science
- ANTS
- 1998

Some methods for computing equations for certain Shimura curves, natural maps between them, and special points on them are given, and a list of open questions that may point the way to further computational investigation of these curves are illustrated. Expand

Elliptic and modular curves over finite fields and related computational issues

- Mathematics
- 1997

The problem of calculating the trace of an elliptic curve over a finite field has attracted considerable interest in recent years. There are many good reasons for this. The question is intrinsically… Expand

Old and new conjectured diophantine inequalities

- Mathematics
- 1990

The original meaning of diophantine problems is to find all solutions of equations in integers or rational numbers, and to give a bound for these solutions. One may expand the domain of coefficients… Expand