A multidimensional continued fraction based on a high-order recurrence relation
HTML articles powered by AMS MathViewer
- by Yves Tourigny and Nigel P. Smart PDF
- Math. Comp. 76 (2007), 1995-2022 Request permission
Abstract:
The paper describes and studies an iterative algorithm for finding small values of a set of linear forms over vectors of integers. The algorithm uses a linear recurrence relation to generate a vector sequence, the basic idea being to choose the integral coefficients in the recurrence relation in such a way that the linear forms take small values, subject to the requirement that the integers should not become too large. The problem of choosing good coefficients for the recurrence relation is thus related to the problem of finding a good approximation of a given vector by a vector in a certain one-parameter family of lattices; the novel feature of our approach is that practical formulae for the coefficients are obtained by considering the limit as the parameter tends to zero. The paper discusses two rounding procedures to solve the underlying inhomogeneous Diophantine approximation problem: the first, which we call “naive rounding” leads to a multidimensional continued fraction algorithm with suboptimal asymptotic convergence properties; in particular, when it is applied to the familiar problem of simultaneous rational approximation, the algorithm reduces to the classical Jacobi–Perron algorithm. The second rounding procedure is Babai’s nearest-plane procedure. We compare the two rounding procedures numerically; our experiments suggest that the multidimensional continued fraction corresponding to nearest-plane rounding converges at an optimal asymptotic rate.References
- L. Babai, On Lovász’ lattice reduction and the nearest lattice point problem, Combinatorica 6 (1986), no. 1, 1–13. MR 856638, DOI 10.1007/BF02579403
- P. R. Baldwin, A multidimensional continued fraction and some of its statistical properties, J. Statist. Phys. 66 (1992), no. 5-6, 1463–1505. MR 1156411, DOI 10.1007/BF01054430
- P. R. Baldwin, A convergence exponent for multidimensional continued-fraction algorithms, J. Statist. Phys. 66 (1992), no. 5-6, 1507–1526. MR 1156412, DOI 10.1007/BF01054431
- Patrick Billingsley, Ergodic theory and information, John Wiley & Sons, Inc., New York-London-Sydney, 1965. MR 0192027
- D. M. Hardcastle and K. Khanin, Continued fractions and the $d$-dimensional Gauss transformation, Comm. Math. Phys. 215 (2001), no. 3, 487–515. MR 1810942, DOI 10.1007/s002200000290
- Bettina Just, Generalizing the continued fraction algorithm to arbitrary dimensions, SIAM J. Comput. 21 (1992), no. 5, 909–926. MR 1181407, DOI 10.1137/0221054
- Kostya Khanin, João Lopes Dias, and Jens Marklof, Multidimensional continued fractions, dynamical renormalization and KAM theory, Comm. Math. Phys. 270 (2007), no. 1, 197–231. MR 2276445, DOI 10.1007/s00220-006-0125-y
- A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454
- J. C. Lagarias, The quality of the Diophantine approximations found by the Jacobi-Perron algorithm and related algorithms, Monatsh. Math. 115 (1993), no. 4, 299–328. MR 1230366, DOI 10.1007/BF01667310
- J. C. Lagarias, Geodesic multidimensional continued fractions, Proc. London Math. Soc. (3) 69 (1994), no. 3, 464–488. MR 1289860, DOI 10.1112/plms/s3-69.3.464
- G. J. Rieger, Ein Gauss-Kusmin-Levy-Satz für Kettenbrüche nach nächsten Ganzen, Manuscripta Math. 24 (1978), no. 4, 437–448 (German). MR 568143, DOI 10.1007/BF01168885
- C. Rössner & C. Schnorr, An optimal, stable continued fraction algorithm for arbitrary dimension, ECCC TR96-020, (1996). http://www.eccc.uni-trier.de/eccc
- Fritz Schweiger, Multidimensional continued fractions, Oxford Science Publications, Oxford University Press, Oxford, 2000. MR 2121855
Additional Information
- Yves Tourigny
- Affiliation: School of Mathematics, University of Bristol, Bristol BS8 1TW, United Kingdom
- Email: y.tourigny@bristol.ac.uk
- Nigel P. Smart
- Affiliation: Department of Computer Science, University of Bristol, Bristol, United Kingdom
- Email: n.p.smart@bristol.ac.uk
- Received by editor(s): August 22, 2006
- Published electronically: May 11, 2007
- Additional Notes: The first author acknowledges the support of the Engineering and Physical Sciences Research Council (United Kingdom) under a Discipline Hopping Award
- © Copyright 2007 American Mathematical Society
- Journal: Math. Comp. 76 (2007), 1995-2022
- MSC (2000): Primary 11J70
- DOI: https://doi.org/10.1090/S0025-5718-07-02020-0
- MathSciNet review: 2336278