A multidimensional continued fraction based on a highorder recurrence relation
Authors:
Yves Tourigny and Nigel P. Smart
Journal:
Math. Comp. 76 (2007), 19952022
MSC (2000):
Primary 11J70
Published electronically:
May 11, 2007
MathSciNet review:
2336278
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
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 oneparameter 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 JacobiPerron algorithm. The second rounding procedure is Babai's nearestplane procedure. We compare the two rounding procedures numerically; our experiments suggest that the multidimensional continued fraction corresponding to nearestplane rounding converges at an optimal asymptotic rate.
 1.
L.
Babai, On Lovász’ lattice reduction and the nearest
lattice point problem, Combinatorica 6 (1986),
no. 1, 1–13. MR 856638
(88a:68049), http://dx.doi.org/10.1007/BF02579403
 2.
P.
R. Baldwin, A multidimensional continued fraction and some of its
statistical properties, J. Statist. Phys. 66 (1992),
no. 56, 1463–1505. MR 1156411
(93d:11082), http://dx.doi.org/10.1007/BF01054430
 3.
P.
R. Baldwin, A convergence exponent for multidimensional
continuedfraction algorithms, J. Statist. Phys. 66
(1992), no. 56, 1507–1526. MR 1156412
(93d:11083), http://dx.doi.org/10.1007/BF01054431
 4.
Patrick
Billingsley, Ergodic theory and information, John Wiley &
Sons, Inc., New YorkLondonSydney, 1965. MR 0192027
(33 #254)
 5.
D.
M. Hardcastle and K.
Khanin, Continued fractions and the 𝑑dimensional Gauss
transformation, Comm. Math. Phys. 215 (2001),
no. 3, 487–515. MR 1810942
(2002a:11090), http://dx.doi.org/10.1007/s002200000290
 6.
Bettina
Just, Generalizing the continued fraction algorithm to arbitrary
dimensions, SIAM J. Comput. 21 (1992), no. 5,
909–926. MR 1181407
(93k:11065), http://dx.doi.org/10.1137/0221054
 7.
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
(2008d:37005), http://dx.doi.org/10.1007/s002200060125y
 8.
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 (84a:12002), http://dx.doi.org/10.1007/BF01457454
 9.
J.
C. Lagarias, The quality of the Diophantine approximations found by
the JacobiPerron algorithm and related algorithms, Monatsh. Math.
115 (1993), no. 4, 299–328. MR 1230366
(94j:11074), http://dx.doi.org/10.1007/BF01667310
 10.
J.
C. Lagarias, Geodesic multidimensional continued fractions,
Proc. London Math. Soc. (3) 69 (1994), no. 3,
464–488. MR 1289860
(95j:11066), http://dx.doi.org/10.1112/plms/s369.3.464
 11.
G.
J. Rieger, Ein GaussKusminLevySatz für Kettenbrüche
nach nächsten Ganzen, Manuscripta Math. 24
(1978), no. 4, 437–448 (German). MR 0568143
(58 #27875)
 12.
C. Rössner & C. Schnorr, An optimal, stable continued fraction algorithm for arbitrary dimension, ECCC TR96020, (1996). http://www.eccc.unitrier.de/eccc
 13.
Fritz
Schweiger, Multidimensional continued fractions, Oxford
Science Publications, Oxford University Press, Oxford, 2000. MR 2121855
(2005i:11090)
 1.
 L. Babai, On Lovász' lattice reduction and the nearest lattice point problem, Combinatorica 6, 113 (1986). MR 856638 (88a:68049)
 2.
 P. Baldwin, A multidimensional continued fraction and its statistical properties, J. Stat. Phys. 66, 14631505 (1992). MR 1156411 (93d:11082)
 3.
 P. Baldwin, A convergence exponent for multidimensional continued fraction algorithms, J. Stat. Phys. 66, 15071526 (1992). MR 1156412 (93d:11083)
 4.
 P. Billingsley, Ergodic Theory and Information, Wiley, New York, 1965. MR 0192027 (33:254)
 5.
 D. M. Hardcastle and K. Khanin, Continued fractions and the dimensional Gauss transformation, Comm. Math. Phys. 215, 487515 (2001). MR 1810942 (2002a:11090)
 6.
 B. Just, Generalizing the continued fraction algorithm to arbitrary dimensions, SIAM J. Comput. 21, 909926 (1992). MR 1181407 (93k:11065)
 7.
 K. Khanin, J. L. Lopes and J. Marklof, Multidimensional continued fractions, dynamical renormalization and KAM theory, Comm. Math. Phys. 270 (2007), 197231. MR 2276445
 8.
 A. K. Lenstra, H. W. Lenstra & L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261, 515534 (1982). MR 682664 (84a:12002)
 9.
 J. C. Lagarias, The quality of the Diophantine approximations found by the JacobiPerron algorithm and related algorithms, Mh. Math. 115, 299328 (1993). MR 1230366 (94j:11074)
 10.
 J. C. Lagarias, Geodesic multidimensional continued fractions, Proc. London Math. Soc. 69, 464488 (1994). MR 1289860 (95j:11066)
 11.
 G. J. Rieger, Ein GaussKuzminLevySatz für Kettenbrüche nach nächsten Ganzen, Manuscripta Math. 24, 437438 (1978). MR 0568143 (58:27875)
 12.
 C. Rössner & C. Schnorr, An optimal, stable continued fraction algorithm for arbitrary dimension, ECCC TR96020, (1996). http://www.eccc.unitrier.de/eccc
 13.
 F. Schweiger, Multidimensional Continued Fractions, Oxford University Press, Oxford, 2000. MR 2121855 (2005i:11090)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2000):
11J70
Retrieve articles in all journals
with MSC (2000):
11J70
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
DOI:
http://dx.doi.org/10.1090/S0025571807020200
PII:
S 00255718(07)020200
Keywords:
Multidimensional continued fraction,
recurrence relation
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
Article copyright:
© Copyright 2007
American Mathematical Society
