Rational points near curves and small nonzero |x^3-y^2| via lattice reduction
Noam D. Elkies (Harvard University)
我们给出了一个新的算法,使用线性近似和晶格减小,以有效地计算给定平面曲线C附近的小高度的所有合理点。 例如,当 C 是 Fermat 立方时,我们找到具有 0<x<=y<z<N 时位值 0<x<=y<z<N 的所有整数解决方案,其中 L(X):= (log X)^O(1)] 提供 M>>N,仅使用 O(log N) 空间。 由于解决方案的数量应与M log N(只要M<N^3)成正比,计算成本基本上尽可能低。 此外,该算法易于并行化。 它不仅产生了新的数字例子,而且导致了理论结果,困难的开放问题,以及自然概括。 我们还调整我们的算法来研究霍尔的猜想:我们发现所有具有 x<<X 时间的 0<|x^3-y^2|<<x^(1/2) 的整数解决方案,以及时间 O(X^(1/2) L(X))。 通过用 X=10^18 实现这个算法,我们打破了 x^(1/2)/|x^3-y^2| 的先前记录。 O(X^1/2 L(X) 绑定是严格的;它的证明也产生了任何正理性 c 的 sqrt(cx^3) 分布 mod 1 的新估计。
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 << L(N) M [where L(X):= (log X)^O(1)] 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 essent...
