UNIVERSAL GENERALIZATION OF THE CONTINUED FRACTION ALGORITHM
https://doi.org/10.22405/2226-8383-2015-16-2-35-65
Abstract
1. Simple generalization. Let three homogeneous real linear forms be given in a three-dimensional real space. Their moduli give a mapping of the space into another space. In the second space, we consider the convex hull of images of all integer points of the first space except its origin. This convex hull is called the modular polyhedron. The best integer approximations to the root subspaces of these forms are given by the integer points whose images lie on the boundary of the modular polyhedron. For the concret three linear forms, any part of the boundary of the modular polyhedron can be computed by means of any standard program for computation of a convex hull. The algorithm gives the best approximations, and it is periodic for cubic irrationalities with positive discriminant. It also allows to understand why matrix algorithms proposed by Euler, Jacobi, Dirichlet, Hermite, Poincare, Hurwitz, Brun, Guting and others are not universal: proper algorithm is composed from several different matrix algorithms. 2. Universal generalization. Let l linear forms and k quadratic forms (n = l + 2k) be given in the n-dimensional real space Rn. Absolute values of the forms define a map of the space Rn into the positive orthant S of the mdimensional real space Rm, where m = l + k. Here the integer lattice Zn in Rn is mapped into a set Z in S. The closure of the convex hull H of the set Z\0 is a polyhedral set. Integer points from Rn, which are mapped in the boundary ∂H of the polyhedron H, give the best Diophantine approximations to root subspaces of all given forms. In the algebraic case, when the given forms are connected with roots of a polynomial of degree n, we prove that the polyhedron H has m − 1 independent periods. It is a generalization of the Lagrange Theorem, that continued fractions of a square irrationality is periodic. For the certain set of the m forms, any part of the boundary ∂H of the polyhedron H can be computed by a program for computing convex hulls. 3. Main achievement. Best Diophantine approximations can be computed by a global algorithm using a standard program for computing convex hulls, instead of step-by-step computations as in the continued fraction algorithm. It gives a solution of the problem, that majority of main mathematicians of the XIX century tried to solve.
References
1. Venkov, BA 1937, Elementary theory of numbers, ONTI, Moscow–Leningrad.
2. Khinchin, AYa 1963, Continued fractions, Noordhoff, Groningen.
3. Wallis, JA 1655, Arithmetica infinitorum.
4. Euler, L. 1737, “De fractinibus continuis”, Comm. Acad. Sci. Imper. Petropol., vol. 9.
5. Lagrange, JL 1774, Complement chez Elements d’algebre etc. par M. L. Euler, T. III.
6. Euler, L. 1775, “De relatione inter ternas pluresve quantitates instituenda”, Petersburger Akademie Notiz. Exhib., Commentationes arithmeticae collectae. V. II. St. Petersburg. 1849. pp. 99–104.
7. Jacobi, C. G. J. 1868, “Allgemeine Theorie der Kettenbruch¨anlichen Algorithmen, in welchen jede Zahl aus drei vorhergehenden gebildet wird”, J. Reine Angew. Math., vol. 69, pp. 29–64. // Gesammelte Werke, Bd. IV. Berlin: Reimer, 1891. pp. 385–426.
8. Jacobi, C. G. J. 1868, “Ueber die Aufl¨osung der Gleichung a1x1+a2x2+. . .+anxn = fn”, J. Reine Angew. Math., vol. 69, pp. 21–28.
9. Poincare, H. 1889, “Sur une generalization des fraction´es continues”, C.R. Acad. Sci. Paris, Ser. 1, vol. 99, pp. 1014–1016.
10. Brun, V. 1920, “En generalisation av Kjedebroken”, Skrifter utgit av Videnskapsselskapeti Kristiania. I, Matematisk-Naturvidenskabelig Klasse 1919, no. 6.
11. Perron, O. 1907, “Grundlagen f¨ur eine Theorie des Jacobischen Ketten- bruchalgorithmus”, Math. Ann., vol. 64, pp. 1–76.
12. Bernstein, L 1971, The Jacobi-Perron algorithm — its theory and application, LNM 207, Springer Verlag, Berlin/Heidelberg/New York.
13. Pustylnikov, L.D. 2003, “Generalized continued fractions and the ergodic theory”, Russian Math.-Surveys, vol. 58, no. 1.
14. Schweiger, F 2000, Multidimensional Continued Fractions, Oxford Univ. Press, New York.
15. Hermite, Ch. 1905, Correspondance d’Hermite et de Stieltjes, T. II, lettres 232, 238, 408, Gauthier-Villars, Paris.
16. Bruno, A.D. & Parusnikov, V.I. 1994, “Klein polyhedrals for two cubic Davenport forms”, Math. Notes, vol. 56, no. 3–4, pp. 994–1007.
17. Bruno, A.D. & Parusnikov, V.I. 1997, “Comparison of various generalization of continued fractions”, Math. Notes, vol. 61, no. 3, pp. 278–286.
18. Parusnikov, V.I. 1998, “Klein polyhedra for complete decomposable forms”, Number theory. Dvophantine, Computational and Algebraic Aspects, Editors: K. Gy˝ory, A. Peth˝o and V. T. S´os, De Gruyter, Berlin, New York, pp. 453–463.
19. Parusnikov, V.I. 2000, “Klein polyhedra for the fourth extremal forms”, Math. Notes, vol. 67, no. 1, pp. 87–102.
20. Parusnikov, V.I. 1997, “Klein’s polyhedra with big faces”, Preprint no. 93 of the Keldysh Inst. of Applied Math., Moscow.
21. Parusnikov, V.I. 1998, “Klein’s polyhedra for the fifth extremal cubic form”, Preprint no. 69 of the Keldysh Inst. of Applied Math., Moscow.
22. Parusnikov, V.I. 1999, “Klein’s polyhedra for the sixth extremal cubic form”, Preprint no. 69 of the Keldysh Inst. of Applied Math., Moscow.
23. Parusnikov, V.I. 1999, “Klein’s polyhedra for the seventh extremal cubic form”, Preprint no. 79 of the Keldysh Inst. of Applied Math., Moscow.
24. Lejeune Dirichlet, G.P. 1842, “Verallgemeinerung eines Satzes aus der Lehre von den Kettenbr¨uchen nebst einigen Anwendungen auf die Theorie der Zahlen”, S.- В. Press. Akad. Wiss., S. 93–95 // Werke. Bd. I, Reimer, Berlin, 1889, pp. 635–638.
25. Hermite, Ch. 1850, “Lettres de M. Ch. Hermite ˆa M. Jacobi sur differents objets de la theorie des nombres”, J. Reine Angew. Math., Bd. 40, pp. 261–315 // Oeuvres, T. I, Gauther-Villares, Paris, 1905, pp. 100–163 // Opuscule Mathematica de Jacobi. V. II.
26. Klein, F. 1895, “ ¨ Uber eine geometrische Auffassung der gewohnlichen Kettenbru- ¨ chentwicklung”, Nadir. Ges. Wiss. G¨ottingen Math.-Phys. Kl., no. 3, pp. 357–359.
27. Minkowski, H. 1896, “Generalisation de le theorie des fractions continues”, Ann. Sci. Ec. Norm. Super, ser III, t. 13, pp. 41–60. Also in: Gesamm. Abh. I. P. 278–292.
28. Voronoi, GF 1896, On Generalization of the Algorithm of Continued Fraction, Warsawa University.
29. Skubenko, B.F. 1991, “Minimum of decomposable cubic form of three variables”, J. Sov. Math., vol. 53, no. 3, pp. 302–321.
30. Arnold, V.I. 1998, “Higher dimensional continued fraction”, Regular and Chaotic Dynamics, vol. 3, no. 3, pp. 10–17.
31. Lachaud, G. 1993, “Poly´edre d’Arnol’d et voile d’un cˆone simplicial: analogues du th´eor`eme de Lagrange”, C.R. Acad. Sei., Ser. 1, vol. 317, pp. 711–716.
32. Lachaud, G. 1993, “Poly´edre d’Arnol’d et voile d’un cˆone simplicial, analogues du th´eor`eme de Lagrange pour les irrationnels de degr´e quelconque”, Pr´etirage N 93–17, Laboratoire de Math´ematiques Discretes du C.N.R.S., Marseille.
33. Brentjes, A.J. 1981, “Multi-dimensional Continued Fraction Algorithms”, Mathematical Centre Tracts, 145, Amsterdam, Mathematisch Centrum.
34. Buchmann, J. 1987, “On the period length of the generalized Lagrange algorithm”, J. Number Theory, vol. 26, pp. 8–37.
35. Bykovsky, V.A. 1999, “The Valen’s theorem for two-dimensional convergent fraction”, Math. Notes, vol. 66, no. 1.
36. Hurwitz, A. 1984, “Ueber die angen¨aherte Darstellung der Zahlen durch rationale Br¨uche”, Math. Ann., Bd. 44, pp. 417–436.
37. Bruno, A.D. 1964, “Continued fraction expansion of algebraic numbers”, USSR Comput. Math. and Math. Phys., vol. 4, no. 2, pp. 1–15.
38. Lang, S. & Trotter, Н. 1972, “Continued fractions of some algebraic numbers”, J. Reine Angew. Math., Bd. 252, pp. 112–134.
39. Stark, H.M. 1971, “An explanation of some exotic continued fractions found by Brillhart”, Computers in Number Theory, Academic Press, London and New York, pp. 21–35.
40. Minkowski, Н. 1901, “Uber die Annelierung an eine reele Grosse durch rationale Zahlen”, Math. Annalen. B. 54, pp. 91–124. Also in: Gesamm. Abh. I. pp. 320–352.
41. Pipping, N. 1924, “Zur Theorie der Diagonalkettenbr¨uche”, Acta Acad. Aboens., B. 3, 22 S.
42. Nechaev, V.I. 1979, “Diagonal continued fraction”, Math. Encyclop., Kluwer Acad. Publ.
43. Bruno, A.D. 2003, “The correct generalization of the continued fraction”, Preprint no. 86 of the Keldysh Inst. of Applied Math., Moscow.
44. Bruno, A.D. & Parusnikov, V.I. 2003, “Polyhedra of absolute values for triple of linear forms”, Preprint no. 93 of the Keldysh Inst. of Applied Math., Moscow.
45. Bruno, A.D. 2004, “On generalization of the continued fraction”, Preprint no. 10 of the Keldysh Inst. of Applied Math., Moscow.
46. Bruno, A.D. 2004, “Algorithm of generalized continued fractions”, Preprint no. 45 of the Keldysh Inst. of Applied Math., Moscow.
47. Bruno, A.D. & Parusnikov, V.I. 2005, “Further generalization of the continued fraction”, Preprint no. 40 of the Keldysh Inst. of Applied Math., Moscow.
48. Bruno, A.D. & Parusnikov, V. I. “New generalizations of the continued fraction” Preprint no. 52 of the Keldysh Inst. of Applied Math., Moscow, 20 p.
49. Bruno, A.D. 2005, “Structure of the best Diophantine approximations”, Doklady Mathematics, vol. 71, no. 3, pp. 396–400.
50. Bruno, A.D. 2000, “Generalized continued fraction algorithm”, Doklady Mathematics, vol. 71, no. 3, pp. 446–450.
51. Parusnikov, V. I. 2005, “Comparison of several generalizations of the continued fraction”, Chebyshevsky Sbornik (Tula), vol. 5. no. 4, pp. 180–188.
52. Bruno, A.D. 2005, “Properties of the modular polyhedron”, Preprint no. 72 of the Keldysh Inst. of Applied Math., Moscow.
53. Klein, F. 1896, “Sur une representation geometrique du d´eveloppement, en fraction continue ordinare”, Nouv. Ann. Math. (3), Bd. 15, pp. 327–331.
54. Klein, F. 1896, “Ausgew¨ahlte Kapitel der Zahlentheorie”, Bd. I, Einleitung. G¨ottingen. pp. 16–50.
55. Koksma, JF 1936, Diophantische Approximationen, Julius Springer, Berlin.
56. Perron, O 1913, Die Lehre von den Kettenbr¨uchen, Teubner, Leipzig; Stuttgart, 1954, 1977.
57. Hurwitz, A. 1889, “Ueber eine besondere Art der Kettenbruch-Entwiklung relier Gr¨ossen”, Acta math, В. 12, pp. 367–405.
58. Korkina, E.I. 1995, “Two-dimensional convergent fractions. The simplest examples”, Proceedings of the Steklov Inst. of Math., vol. 209, pp. 124–144.
59. Kontsevich, M.L. & Suhov, Yu.M. 1999, “Statistics of Klein polyhedra and multidimensional continued fractions”, Amer. Math. Soc. Transi. (2), vol. 197, pp. 9–27.
60. Briggs, K. Klein polyhedra (2013), Available at: http://keithbriggs.info/klein-polyhedra.html.
61. Parusnikov, V.I. 2005, “Klein’s polyhedra for three extremal forms”, Math. Notes, vol. 77, no. 4, pp. 523–538.
62. Swinnerton-Dyer H.P.F. 1971, “On the product of three homogeneous linear forms”, Acta Arithmetica, vol. 18, pp. 371–385.
63. Delone, B.N. & Faddeev, D.K. 1964, “The theory of irrationalities of the third degree”, Am. Math. Soc. Transl. of Math. Monographs, vol. 10.
64. Delone, BN 1947, The Petersburg’s School of Mathematics, AN SSSR, Moscow– Leningrad.
65. Cassels, JWS 1959, An Introduction to the Geometry of Numbers, Springer-Verlag, Berlin.
66. Borevich, ZI & Shafarevich, IR 1966, Number Theory, Academic Press.
67. G¨uting, R. 1975, “Zur Verallgemeinerung des Kettenbruchalgorithmus. I”, J. Reine Angew. Math., 278/279.
68. Fukuda, K. “Exact algorithms and software in optimization and polyhedral computation”, Proceed. ISSAC’08 of XXI International Symposium on Symbolic and algebraic computations, ACM NY, USA, 2008, pp. 333–334.
69. Bruno, A.D. 2006, “Generalization of continued fraction”, Chebyshevsky sbornik, vol. 7, no. 3, pp. 4–71.
70. Bruno, A.D. 2010, “The structure of multidimensional Diophantine approximations”, Doklady Mathematics, vol. 82, no. 1.
71. Bruno, A.D. & Parusnikov, V.I. 2009, “Two–way generalization of the continued fraction”, Doklady Mathematics, vol. 80, no. 3, pp. 887–890.
72. Bruno, A.D. 2010, “Structure of the best Diophantine approximations and multidimensional generalizations of the continued fraction”, Chebyshevskii Sbornik (Tula), vol. 11, no. 1. pp. 68–73.
73. Maple 2015.0 (2015), Available at: http://www.maplesoft.com/products/Maple.
74. Bruno, A.D. 2014, “On geometric methods in works by V. I. Arnold and V. V. Kozlov”, Preprint of arXiv, No 1401.6320.
75. Bruno A. D. 2010 “New generalization of continued fraction, I”, Functiones et Approximatio, vol. 43, no. 1. pp. 55–104.
Review
For citations:
Bruno A.D. UNIVERSAL GENERALIZATION OF THE CONTINUED FRACTION ALGORITHM. Chebyshevskii Sbornik. 2015;16(2):35-65. (In Russ.) https://doi.org/10.22405/2226-8383-2015-16-2-35-65
Views:
530
Email this article 