×

Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems. (English) Zbl 1458.05263

Summary: The coefficient sequences of multivariate rational functions appear in many areas of combinatorics. Their diagonal coefficient sequences enjoy nice arithmetic and asymptotic properties, and the field of analytic combinatorics in several variables (ACSV) makes it possible to compute asymptotic expansions. We consider these methods from the point of view of effectivity. In particular, given a rational function, ACSV requires one to determine a (generically) finite collection of points that are called critical and minimal. Criticality is an algebraic condition, meaning it is well treated by classical methods in computer algebra, while minimality is a semi-algebraic condition describing points on the boundary of the domain of convergence of a multivariate power series. We show how to obtain dominant asymptotics for the diagonal coefficient sequence of multivariate rational functions under some genericity assumptions using symbolic-numeric techniques. To our knowledge, this is the first completely automatic treatment and complexity analysis for the asymptotic enumeration of rational functions in an arbitrary number of variables.

MSC:

05E14 Combinatorial aspects of algebraic geometry
05A16 Asymptotic enumeration
14Q30 Computational real algebraic geometry
14Q65 Geometric aspects of numerical algebraic geometry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] André, Y., Séries Gevrey de type arithmétique. I. Théorèmes de pureté et de dualité, Ann. of Math. (2), 151, 2, 705-740 (2000) · Zbl 1037.11049
[2] Baryshnikov, Y., Melczer, S., Pemantle, R., 2020. Stratified points at infinity for analytic combinatorics. In preparation.
[3] Baryshnikov, Y.; Melczer, S.; Pemantle, R.; Straub, A., Diagonal asymptotics for symmetric rational functions via ACSV, (Fill, J. A.; Ward, M. D., 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 110 (2018), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik Dagstuhl, Germany), 12:1-12:15 · Zbl 1482.05011
[4] Baryshnikov, Y.; Pemantle, R., Asymptotics of multivariate sequences, part iii: quadratic points, Adv. Math., 228, 3127-3206 (2011) · Zbl 1252.05012
[5] Basu, S.; Pollack, R.; Roy, M.-F., Algorithms in Real Algebraic Geometry (2006), Springer-Verlag: Springer-Verlag Berlin · Zbl 1102.14041
[6] Bender, E. A., Central and local limit theorems applied to asymptotic enumeration, J. Comb. Theory, Ser. A, 15, 91-111 (1973) · Zbl 0242.05006
[7] Bender, E. A.; Richmond, L. B., Central and local limit theorems applied to asymptotic enumeration. ii. multivariate generating functions, J. Comb. Theory, Ser. A, 34, 255-265 (1983) · Zbl 0511.05003
[8] Bender, E. A.; Richmond, L. B., Multivariate asymptotics for products of large powers with applications to Lagrange inversion, Electron. J. Comb., 6 (1999), Research Paper 8, 21 · Zbl 0927.41017
[9] Bostan, A.; Lairez, P.; Salvy, B., Creative telescoping for rational functions using the Griffiths-Dwork method, (ISSAC ’13 (2013), ACM Press), 93-100 · Zbl 1360.68921
[10] Bostan, A.; Lairez, P.; Salvy, B., Multiple binomial sums, J. Symb. Comput., 80, part 3, 351-386 (2017) · Zbl 1351.05013
[11] Bouzidi, Y.; Lazard, S.; Pouget, M.; Rouillier, F., Separating linear forms and rational univariate representations of bivariate systems, J. Symb. Comput., 68, part 1, 84-119 (2015) · Zbl 1328.13041
[12] Brandwood, D. H., A complex gradient operator and its application in adaptive array theory, Proc. IEE-H, 130, 1, 11-16 (1983)
[13] Bugeaud, Y., Approximation by Algebraic Numbers, Cambridge Tracts in Mathematics, vol. 160 (2004), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1055.11002
[14] Bürgisser, P.; Clausen, M.; Shokrollahi, M. A., Algebraic Complexity Theory, Grundlehren der Mathematischen Wissenschaften, vol. 315 (1997), Springer-Verlag · Zbl 1087.68568
[15] Castro, D.; Pardo, L. M.; Hägele, K.; Morais, J. E., Kronecker’s and Newton’s approaches to solving: a first comparison, J. Complex., 17, 1, 212-303 (2001) · Zbl 1013.68296
[16] Christol, G., Diagonales de fractions rationnelles et equations différentielles, (Study group on ultrametric analysis, 10th year: 1982/83, No. 2 (1984), Inst. Henri Poincaré: Inst. Henri Poincaré Paris), pp. Exp. No. 18, 10 · Zbl 0534.12018
[17] Christol, G., Globally bounded solutions of differential equations, (Analytic Number Theory. Analytic Number Theory, Tokyo, 1988. Analytic Number Theory. Analytic Number Theory, Tokyo, 1988, Lecture Notes in Math., vol. 1434 (1990), Springer: Springer Berlin, Heidelberg), 45-64 · Zbl 0705.12006
[18] Chudnovsky, D. V.; Chudnovsky, G. V., Applications of Padé approximations to Diophantine inequalities in values of G-functions, (Number theory (New York, 1983-84). Number theory (New York, 1983-84), Lecture Notes in Math., vol. 1135 (1985), Springer: Springer Berlin), 9-51 · Zbl 0561.10016
[19] Cox, D. A.; Little, J.; O’Shea, D., Using Algebraic Geometry, Graduate Texts in Mathematics, vol. 185 (2005), Springer: Springer New York · Zbl 1079.13017
[20] D’Andrea, C.; Krick, T.; Sombra, M., Heights of varieties in multiprojective spaces and arithmetic Nullstellensätze, Ann. Sci. Éc. Norm. Supér. (4), 46, 4, 549-627 (2013) · Zbl 1354.14038
[21] De Bruijn, N. G., Asymptotic Methods in Analysis (1981), Dover, A reprint of the third North Holland edition, 1970 (first edition, 1958) · Zbl 0556.41021
[22] DeVries, T.; van der Hoeven, J.; Pemantle, R., Automatic asymptotics for coefficients of smooth, bivariate rational functions, Online J. Anal. Comb., 6 (2011), 24 pages · Zbl 1292.05037
[23] Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press · Zbl 1165.05001
[24] Furstenberg, H., Algebraic functions over finite fields, J. Algebra, 7, 271-277 (1967) · Zbl 0175.03903
[25] Gao, Z.; Richmond, L. B., Central and local limit theorems applied to asymptotic enumeration. IV. Multivariate generating functions, J. Comput. Appl. Math., 41, 1-2, 177-186 (1992), asymptotic methods in analysis and combinatorics · Zbl 0755.05004
[26] Gillis, J.; Reznick, B.; Zeilberger, D., On elementary methods in positivity theory, SIAM J. Math. Anal., 14, 2, 396-398 (1983) · Zbl 0599.42500
[27] Giusti, M.; Heintz, J.; Morais, J. E.; Morgenstern, J.; Pardo, L. M., Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra, 124, 1-3, 101-146 (1998) · Zbl 0944.12004
[28] Giusti, M.; Lecerf, G.; Salvy, B., A Gröbner free alternative for polynomial system solving, J. Complex., 17, 1, 154-211 (2001) · Zbl 1003.12005
[29] Gourdon, X.; Salvy, B., Effective asymptotics of linear recurrences with rational coefficients, Discrete Math., 153, 1-3, 145-163 (1996) · Zbl 0852.68075
[30] (Graham, R. L.; Grötschel, M.; Lovász, L., Handbook of combinatorics. Vol. 1, 2 (1995), Elsevier Science B.V., MIT Press: Elsevier Science B.V., MIT Press Amsterdam, Cambridge, MA) · Zbl 0833.05001
[31] Hadamard, J., History of science and psychology of invention, Mathematika, 1, 1-3 (1954) · Zbl 0056.00102
[32] Hirschhorn, M. D., A connection between π and ϕ, Fibonacci Q., 53, 1, 42-47 (2015) · Zbl 1396.11145
[33] Hörmander, L., An introduction to complex analysis in several variables, North-Holland Mathematical Library, vol. 7 (1990), North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam · Zbl 0685.32001
[34] Jouanolou, J.-P., Le formalisme du résultant, Adv. Math., 90, 2, 117-263 (1991) · Zbl 0747.13007
[35] Jungen, R., Sur les séries de Taylor n’ayant que des singularités algébrico-logarithmiques sur leur cercle de convergence, Comment. Math. Helv., 3, 266-306 (1931) · JFM 57.0373.03
[36] Katz, N. M., Nilpotent connections and the monodromy theorem: Applications of a result of Turrittin, Publ. Math. IHÉS, 39, 175-232 (1970) · Zbl 0221.14007
[37] Kedlaya, K. S.; Umans, C., Fast polynomial factorization and modular composition, SIAM J. Comput., 40, 6, 1767-1802 (2011) · Zbl 1333.11117
[38] Kobel, A.; Rouillier, F.; Sagraloff, M., Computing real roots of real polynomials .. and now for real!, (Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation. ISSAC ’16 (2016), ACM: ACM New York, NY, USA), 303-310 · Zbl 1365.65142
[39] Kobel, A.; Sagraloff, M., On the complexity of computing with planar algebraic curves, J. Complex., 31, 2, 206-236 (2015) · Zbl 1309.65025
[40] Krantz, S. G., Function Theory of Several Complex Variables, The Wadsworth & Brooks/Cole Mathematics Series (1992), Wadsworth & Brooks/Cole Advanced Books & Software: Wadsworth & Brooks/Cole Advanced Books & Software Pacific Grove, CA · Zbl 0776.32001
[41] Krick, T.; Pardo, L. M.; Sombra, M., Sharp estimates for the arithmetic Nullstellensatz, Duke Math. J., 109, 3, 521-598 (2001) · Zbl 1010.11035
[42] Kronecker, L., Grundzüge einer arithmetischen theorie der algebraischen grössen, J. Reine Angew. Math., 92, 1-122 (1882) · JFM 14.0038.02
[43] Lairez, P., Computing periods of rational integrals, Math. Comput., 85, 300, 1719-1752 (2016) · Zbl 1337.68301
[44] Macaulay, F. S., The algebraic theory of modular systems, Cambridge tracts in mathematics and mathematical physics, vol. 19 (1916), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, Cambridge · JFM 46.0167.01
[45] McIntosh, R. J., An asymptotic formula for binomial sums, J. Number Theory, 58, 1, 158-172 (1996) · Zbl 0858.05003
[46] Mehlhorn, K.; Sagraloff, M.; Wang, P., From approximate factorization to root isolation with application to cylindrical algebraic decomposition, J. Symb. Comput., 66, 34-69 (2015) · Zbl 1357.68305
[47] Melczer, S.; Salvy, B., Symbolic-numeric tools for analytic combinatorics in several variables, (ISSAC 2016—Proceedings of the 41st International Symposium on Symbolic and Algebraic Computation (2016)) · Zbl 1360.68945
[48] Mezzarobba, M., Numgfun: a package for numerical and analytic computation with D-finite functions, (Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation (ISSAC 2010) (2010), ACM), 139-145 · Zbl 1321.65202
[49] Mezzarobba, M., Rigorous multiple-precision evaluation of D-finite functions in SageMath (2016), extended abstract of a talk at the 5th International Congress on Mathematical Software
[50] Mignotte, M., Mathematics for Computer Algebra (1992), Springer: Springer New York · Zbl 0741.11002
[51] Odlyzko, A.M., 1995. Asymptotic enumeration methods. In: Graham et al. (1995), pp. 1063-1229. · Zbl 0845.05005
[52] Olver, F. W.J., Asymptotics and Special Functions (1974), Academic Press · Zbl 0303.41035
[53] Ouaknine, J.; Worrell, J., Decision problems for linear recurrence sequences, (Reachability Problems. Reachability Problems, Lecture Notes in Comput. Sci., vol. 7550 (2012), Springer: Springer Heidelberg), 21-28 · Zbl 1298.11015
[54] Ouaknine, J.; Worrell, J., Ultimate positivity is decidable for simple linear recurrence sequences, (Automata, Languages, and Programming. Part II. Automata, Languages, and Programming. Part II, Lecture Notes in Comput. Sci., vol. 8573 (2014), Springer: Springer Heidelberg), 330-341 · Zbl 1410.11135
[55] Pemantle, R.; Wilson, M. C., Asymptotics of multivariate sequences: I. Smooth points of the singular variety, J. Comb. Theory, Ser. A, 97, 1, 129-161 (2002) · Zbl 1005.05007
[56] Pemantle, R.; Wilson, M. C., Asymptotics of multivariate sequences. II. Multiple points of the singular variety, Comb. Probab. Comput., 13, 4-5, 735-761 (2004) · Zbl 1065.05010
[57] Pemantle, R.; Wilson, M. C., Twenty combinatorial examples of asymptotics derived from multivariate generating functions, SIAM Rev., 50, 199-272 (2008) · Zbl 1149.05003
[58] Pemantle, R.; Wilson, M. C., Analytic Combinatorics in Several Variables (2013), Cambridge University Press · Zbl 1297.05004
[59] Raichev, A., amgf documentation – release 0.8 (2012)
[60] Remmert, R., Theory of complex functions, Graduate Texts in Mathematics, vol. 122 (1991), Springer-Verlag: Springer-Verlag New York, Translated from the second German edition by Robert B. Burckel, Readings in Mathematics. https://doi.org/10.1007/978-1-4612-0939-3 · Zbl 0732.32002
[61] Rouillier, F., Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Eng. Commun. Comput., 9, 5, 433-461 (1999) · Zbl 0932.12008
[62] Safey El Din, M.; Schost, E., Bit complexity for multi-homogeneous polynomial system solving application to polynomial minimization, J. Symb. Comput., 87, 176-206 (2018) · Zbl 1391.13056
[63] Sagraloff, M.; Mehlhorn, K., Computing real roots of real polynomials, J. Symb. Comput., 73, 46-86 (2016) · Zbl 1330.65072
[64] Schost, É., Sur la résolution des systèmes polynomiaux à paramètres (2001), École polytechnique, Ph.D. thesis
[65] Schreier, P. J.; Scharf, L. L., Statistical Signal Processing of Complex-Valued Data, The Theory of Improper and Noncircular Signals (2010), Cambridge University Press: Cambridge University Press Cambridge
[66] Straub, A., Positivity of Szegö’s rational function, Adv. Appl. Math., 41, 2, 255-264 (2008) · Zbl 1147.42011
[67] van der Hoeven, J.; Lecerf, G., On the complexity exponent of polynomial system solving (2018), Preprint hal-01848572, HAL
[68] Vivanti, G., Sulle serie di potenze, Ann. Mat. Pura Appl. (1867-1897), 21, 1, 193-194 (1893) · JFM 25.0381.03
[69] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2003), Cambridge University Press · Zbl 1055.68168
[70] Wong, R., Asymptotic Approximations of Integrals (1989), Academic Press · Zbl 0679.41001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.