Efficient computing of n-dimensional simultaneous Diophantine approximation problems

Attila Kovács; Norbert Tihanyi

doi:10.2478/ausi-2014-0002

Abstract

In this paper we consider two algorithmic problems of simultaneous Diophantine approximations. The first algorithm produces a full solution set for approximating an irrational number with rationals with common denominators from a given interval. The second one aims at finding as many simultaneous solutions as possible in a given time unit. All the presented algorithms are implemented, tested and the PariGP version made publicly available.

References

[1] F. Armknecht, C. Elsner, M. Schmidt, Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design. AFRICACRYPT, 2011, pp. 242-259. →1810.1007/978-3-642-21969-6_15
Search in Google Scholar
[2] A. Frank, É. Tardos, An application of simultaneous Diophantine approximation in combinatorial optimization, Combinatorica, 7, 1 (1987) 49-66. →1810.1007/BF02579200
Search in Google Scholar
[3] A. Y. Khinchin, Continued Fractions, Translated from the third (1961) Russian edition, Reprint of the 1964 translation, Dover, Mineola, NY, 1997. →20
Search in Google Scholar
[4] Sh. Kim, S. Östlund, Simultaneous rational approximations in the study of dynamical systems, Phys. Rev. A, 34, 4 (1986) 3426-3434. →1810.1103/PhysRevA.34.3426
Search in Google Scholar
[5] C. Kimberling, Best lower and upper approximates to irrational numbers, Elem. Math., 52, 3 (1997) 122-126. →2010.1007/s000170050020
Search in Google Scholar
[6] T. Kotnik, Computational Estimation of the order of ζ(1/2+it), Math. Comp., 73, 246 (2004) 949-956. →3310.1090/S0025-5718-03-01568-0
Search in Google Scholar
[7] J. C. Lagarias, Best simultaneous Diophantine approximations I., Growth rates of best approximation denominators, Trans. Am. Math. Soc., 272, 2 (1982) 545-554. →1810.1090/S0002-9947-1982-0662052-7
Search in Google Scholar
[8] J. C. Lagarias, Best simultaneous Diophantine approximations II., Behavior of consecutive best approximations, Pacific J. Math., 102, 1 (1982) 61-88. →1810.2140/pjm.1982.102.61
Search in Google Scholar
[9] J. C. Lagarias, The computational complexity of simultaneous Diophantine approximation problems, SIAM J. Computing 14, 1 (1985) 196-209. →1810.1137/0214016
Search in Google Scholar
[10] A. K. Lenstra, H. W. Lenstra Jr., L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261, 4 (1982) 515-534. →18, 2110.1007/BF01457454
Search in Google Scholar
[11] A. M. Odlyzko, The 1020-th zero of the Riemann zeta function and 175 million of its neighbors, 1992 (unpublished) →33
Search in Google Scholar
[12] V. T. Sós, G. Szekeres, Rational approximation vectors, Acta Arithm., 49, 3 (1988) 255-261. →18 10.4064/aa-49-3-255-261
Search in Google Scholar

Efficient computing of n-dimensional simultaneous Diophantine approximation problems

Abstract

Paradigm

My account