Universal generalization of the continued fraction algorithm

A. D. Bruno

Čebyševskij sbornik, Tome 16 (2015) no. 2, pp. 35-65.

Résumé

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 $\mathbb R^n$. Absolute values of the forms define a map of the space $\mathbb R^n$ into the positive orthant $\mathbf S$ of the $m$-dimensional real space $\mathbb R^m$, where $m = l + k$. Here the integer lattice $\mathbb Z^n$ in $\mathbb R^n$ is mapped into a set $\mathbf Z$ in $\mathbf S$. The closure of the convex hull $\mathbf H$ of the set $\mathbf Z \backslash 0$ is a polyhedral set. Integer points from $\mathbb R^n$, which are mapped in the boundary $\partial\mathbf H$ of the polyhedron $\mathbf 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 $\mathbf 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 $\partial\mathbf H$ of the polyhedron $\mathbf 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. Bibliography: 75 titles.

Détail

Keywords: continued fraction, modular polyhedron, program for computing convex hull.

Bibliographie

[1] Venkov B. A., Elementary theory of numbers, ONTI, M.–L., 1937

[2] Khinchin A. Ya., Continued fractions, Noordhoff, Groningen, 1963 | MR

[3] Wallis J. A., Arithmetica infinitorum, 1655

[4] Euler L., “De fractinibus continuis”, Comm. Acad. Sci. Imper. Petropol., 9 (1737)

[5] Lagrange J. L., Complement chez Elements d'algebre etc. par M. L. Euler, v. III, 1774

[6] Euler L., “De relatione inter ternas pluresve quantitates instituenda”, Petersburger Akademie Notiz. Exhib. (August 14, 1775); Commentationes arithmeticae collectae, v. II, St. Petersburg, 1849, 99–104

[7] Jacobi C. G. J., “Allgemeine Theorie der Kettenbruchänlichen Algorithmen, in welchen jede Zahl aus drei vorhergehenden gebildet wird”, J. Reine Angew. Math., 69 (1868), 29–64 ; Gesammelte Werke, v. IV, Reimer, Berlin, 1891, 385–426 | DOI | MR

[8] Jacobi C. G. J., “Ueber die Auflösung der Gleichung $a_1x_1+a_2x_2+\dotsc+a_nx_n = f_n$”, J. Reine Angew. Math., 69 (1868), 21–28

[9] Poincare H., “Sur une generalization des fractionés continues”, C.R. Acad. Sci. Paris. Ser. 1, 99 (1884), 1014–1016

[10] Brun V., “En generalisation av Kjedebroken”, Skrifter utgit av Videnskapsselskapeti Kristiania, v. I, Matematisk-Naturvidenskabelig Klasse, 6, 1919–1920 | Zbl

[11] Perron O., “Grundlagen für eine Theorie des Jacobischen Ketten-bruchalgorithmus”, Math. Ann., 64 (1907), 1–76 | DOI | MR | Zbl

[12] Bernstein L., The Jacobi–Perron algorithm — its theory and application, LNM, 207, Springer Verlag, Berlin–Heidelberg–New York, 1971 | MR | Zbl

[13] Pustylnikov L. D., “Generalized continued fractions and the ergodic theory”, Russian Math.-Surveys, 58:1 (2003) | DOI | MR | Zbl

[14] Schweiger F., Multidimensional Continued Fractions, Oxford Univ. Press, New York, 2000 | MR | Zbl

[15] Hermite Ch., Correspondance d'Hermite et de Stieltjes, lettres 232, 238, 408, v. II, Gauthier-Villars, Paris, 1905 | MR | Zbl

[16] Bruno A. D., Parusnikov V. I., “Klein polyhedrals for two cubic Davenport forms”, Math. Notes, 56:3–4 (1994), 994–1007 | DOI | MR | Zbl

[17] Bruno A. D., Parusnikov V. I., “Comparison of various generalization of continued fractions”, Math. Notes, 61:3 (1997), 278–286 | DOI | DOI | MR | MR | Zbl

[18] Parusnikov V. I., “Klein polyhedra for complete decomposable forms”, Number theory. Dvophantine, Computational and Algebraic Aspects, eds. K. Győry, A. Pethő, V. T. Sós, De Gruyter, Berlin–New York, 1998, 453–463 | MR | Zbl

[19] Parusnikov V. I., “Klein polyhedra for the fourth extremal forms”, Math. Notes, 67:1 (2000), 87–102 | DOI | DOI | MR | Zbl

[20] Parusnikov V. I., “Klein's polyhedra with big faces”, Preprinty IPM, 1997, 093 | Zbl

[21] Parusnikov V. I., “Klein's polyhedra for the fifth extremal cubic form”, Preprinty IPM, 1998, 069

[22] Parusnikov V. I., “Klein's polyhedra for the sixth extremal cubic form”, Preprinty IPM, 1999, 069

[23] Parusnikov V. I., “Klein's polyhedra for the seventh extremal cubic form”, Preprinty IPM, 1999, 079 | Zbl

[24] Lejeune Dirichlet G. P., “Verallgemeinerung eines Satzes aus der Lehre von den Kettenbrüchen nebst einigen Anwendungen auf die Theorie der Zahlen”, S.-V. Press. Akad. Wiss., 1842, 93–95; Werke, v. I, Reimer, Berlin, 1889, 635–638

[25] Hermite Ch., “Lettres de M. Ch. Hermite â M. Jacobi sur differents objets de la theorie des nombres”, J. Reine Angew. Math., 40 (1850), 261–315 ; Oeuvres, I, Gauther-Villares, Paris, 1905, 100–163; Opuscule Mathematica de Jacobi, v. II | DOI | MR

[26] Klein F., “Über eine geometrische Auffassung der gewöhnlichen Kettenbruchentwicklung”, Nadir. Ges. Wiss. Göttingen Math.-Phys. Kl., 1895, no. 3, 357–359 | Zbl

[27] Minkowski H., “Generalisation de le theorie des fractions continues”, Ann. Sci. Ec. Norm. Super, ser. III, 13 (1896), 41–60 ; Gesamm. Abh., v. I, 278–292; Собр. соч. в 3-х томах, т. 1, Из-во АН УССР, Киев, 1952, 197–391 | MR | Zbl

[28] Voronoi G. F., On Generalization of the Algorithm of Continued Fraction, Warsawa University, 1896

[29] Skubenko B. F., “Minimum of decomposable cubic form of three variables”, J. Sov. Math., 53:3 (1991), 302–321 | DOI | MR | Zbl | Zbl

[30] Arnold V. I., “Higher dimensional continued fraction”, Regular and Chaotic Dynamics, 3:3 (1998), 10–17 | DOI | MR | Zbl

[31] Lachaud G., “Polyédre d'Arnol'd et voile d'un cône simplicial: analogues du théorème de Lagrange”, C. R. Acad. Sei. Ser. 1, 317 (1993), 711–716 | MR | Zbl

[32] Lachaud G., Polyédre d'Arnol'd et voile d'un cône simplicial, analogues du théorème de Lagrange pour les irrationnels de degré quelconque, Prétirage No 93-17, Laboratoire de Mathématiques Discretes du C.N.R.S., Marseille, 1993

[33] Brentjes A. J., Multi-dimensional Continued Fraction Algorithms, Mathematical Centre Tracts, 145, Mathematisch Centrum, Amsterdam, 1981 | MR | Zbl

[34] Buchmann J., “On the period length of the generalized Lagrange algorithm”, J. Number Theory, 26 (1987), 8–37 | DOI | MR

[35] Bykovsky V. A., “The Valen's theorem for two-dimensional convergent fraction”, Math. Notes, 66:1 (1999) | DOI | MR | Zbl

[36] Hurwitz A., “Ueber die angenäherte Darstellung der Zahlen durch rationale Brüche”, Math. Ann., 44 (1894), 417–436 | DOI | MR

[37] Bruno A. D., “Continued fraction expansion of algebraic numbers”, USSR Comput. Math. and Math. Phys., 4:2 (1964), 1–15 | DOI | MR | Zbl

[38] Lang S., Trotter N., “Continued fractions of some algebraic numbers”, J. Reine Angew. Math., 252 (1972), 112–134 | MR

[39] Stark H. M., “An explanation of some exotic continued fractions found by Brillhart”, Computers in Number Theory, Academic Press, London–New York, 1971, 21–35 | MR

[40] Minkowski N., “Uber die Annelierung an eine reele Grosse durch rationale Zahlen”, Math. Annalen, 54 (1901), 91–124 ; Gesamm. Abh., v. I, 320–352 | DOI | MR | Zbl

[41] Pipping N., “Zur Theorie der Diagonalkettenbrüche”, Acta Acad. Aboens., 3 (1924), 22 | Zbl

[42] Nechaev V. I., Diagonal continued fraction, Math. Encyclop., Kluwer Acad. Publ., 1979 | MR

[43] Bruno A. D., “The correct generalization of the continued fraction”, Preprinty IPM, 2003, 086

[44] Bruno A. D., Parusnikov V. I., “Polyhedra of absolute values for triple of linear forms”, Preprinty IPM, 2003, 093

[45] Bruno A. D., “On generalization of the continued fraction”, Preprinty IPM, 2004, 010

[46] Bruno A. D., “Algorithm of generalized continued fractions”, Preprinty IPM, 2004, 045 | Zbl

[47] Bruno A. D., Parusnikov V. I., “Further generalization of the continued fraction”, Preprinty IPM, 2005, 040

[48] Bruno A. D., Parusnikov V. I., “New generalizations of the continued fraction”, Preprinty IPM, 2005, 052, 20 pp.

[49] Bruno A. D., “Structure of the best Diophantine approximations”, Doklady Mathematics, 71:3 (2005), 396–400 | MR | Zbl

[50] Bruno A. D., “Generalized continued fraction algorithm”, Doklady Mathematics, 71:3 (2000), 446–450

[51] Parusnikov V. I., “Comparison of several generalizations of the continued fraction”, Chebyshevsky Sbornik, 5:4 (2005), 180–188 | MR

[52] Bruno A. D., “Properties of the modular polyhedron”, Preprinty IPM, 2005, 072

[53] Klein F., “Sur une representation geometrique du développement, en fraction continue ordinare”, Nouv. Ann. Math. (3), 15 (1896), 327–331 | Zbl

[54] Klein F., Ausgewählte Kapitel der Zahlentheorie, Einleitung I, Göttingen, 1896, 16–50

[55] Koksma J. F., Diophantische Approximationen, Julius Springer, Berlin, 1936 | MR | Zbl

[56] Perron O., Die Lehre von den Kettenbrüchen, Teubner, Leipzig, 1913 ; Stuttgart, 1954; 1977 | Zbl

[57] Hurwitz A., “Ueber eine besondere Art der Kettenbruch-Entwiklung relier Grössen”, Acta math., 12 (1889), 367–405 | DOI | MR | Zbl

[58] Korkina E. I., “Two-dimensional convergent fractions. The simplest examples”, Proceedings of the Steklov Inst. of Math., 209 (1995), 124–144 | MR | Zbl

[59] Kontsevich M. L., Suhov Yu. M., “Statistics of Klein polyhedra and multidimensional continued fractions”, Amer. Math. Soc. Transl. (2), 197 (1999), 9–27 | MR | Zbl

[60] Briggs K., Klein polyhedra, , 2013 http://keithbriggs.info/klein-polyhedra.html

[61] Parusnikov V. I., “Klein's polyhedra for three extremal forms”, Math. Notes, 77:4 (2005), 523–538 | DOI | DOI | MR | Zbl

[62] Swinnerton-Dyer H. P. F., “On the product of three homogeneous linear forms”, Acta Arithmetica, 18 (1971), 371–385 | MR | Zbl

[63] Delone B. N., Faddeev D. K., The theory of irrationalities of the third degree, Am. Math. Soc. Transl. of Math. Monographs, 10, 1964 | MR | Zbl

[64] Delone B. N., The Petersburg's School of Mathematics, AN SSSR, M.–L., 1947

[65] Cassels J. W. S., An Introduction to the Geometry of Numbers, Springer-Verlag, Berlin, 1959 | MR | Zbl

[66] Borevich Z. I., Shafarevich I. R., Number Theory, Academic Press, 1966 | MR | MR | Zbl

[67] Güting R., “Zur Verallgemeinerung des Kettenbruchalgorithmus, I”, J. Reine Angew. Math., 278/279 (1975) | MR | Zbl

[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, 333–334 | MR

[69] Bruno A. D., “Generalization of continued fraction”, Chebyshevsky sbornik, 7:3 (2006), 4–71 | MR

[70] Bruno A. D., “The structure of multidimensional Diophantine approximations”, Doklady Mathematics, 82:1 (2010) | DOI | MR | Zbl

[71] Bruno A. D., Parusnikov V. I., “Two–way generalization of the continued fraction”, Doklady Mathematics, 80:3 (2009), 887–890 | DOI | MR | Zbl

[72] Bruno A. D., “Structure of the best Diophantine approximations and multidimensional generalizations of the continued fraction”, Chebyshevsky Sbornik, 11:1 (2010), 68–73 | MR | Zbl

[73] Maple 2015.0, http://www.maplesoft.com/products/Maple

[74] Bruno A. D., On geometric methods in works by V. I. Arnold and V. V. Kozlov, arXiv: 1401.6320

[75] Bruno A. D., “New generalization of continued fraction, I”, Functiones et Approximatio, 43:1 (2010), 55–104 | DOI | MR | Zbl