Document Open Access Logo

Diagonal Asymptotics for Symmetric Rational Functions via ACSV

Authors Yuliy Baryshnikov, Stephen Melczer , Robin Pemantle, Armin Straub

PDF
Thumbnail PDF

File

LIPIcs.AofA.2018.12.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Yuliy Baryshnikov
  • University of Illinois, Department of Mathematics, 273 Altgeld Hall 1409 W. Green Street (MC-382), Urbana, IL 61801, USA
Stephen Melczer
  • University of Pennsylvania, Department of Mathematics, 209 South 33rd Street, Philadelphia, PA 19104, USA
Robin Pemantle
  • University of Pennsylvania, Department of Mathematics, 209 South 33rd Street, Philadelphia, PA 19104, USA
Armin Straub
  • University of South Alabama, Department of Mathematics and Statistics, 411 University Blvd N, MSPB 325, Mobile, AL 36688, USA

Funding

  • Baryshnikov, Yuliy: Partially supported by NSF grant DMS-1622370
  • Melczer, Stephen: Partially supported by an NSERC postdoctoral fellowship and NSF grant DMS-1612674
  • Pemantle, Robin: Partially supported by NSF grant DMS-1612674
  • Straub, Armin: Partially supported by a Simons Collaboration Grant

Cite AsGet BibTex

Yuliy Baryshnikov, Stephen Melczer, Robin Pemantle, and Armin Straub. Diagonal Asymptotics for Symmetric Rational Functions via ACSV. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.AofA.2018.12

Abstract

We consider asymptotics of power series coefficients of rational functions of the form 1/Q where Q is a symmetric multilinear polynomial. We review a number of such cases from the literature, chiefly concerned either with positivity of coefficients or diagonal asymptotics. We then analyze coefficient asymptotics using ACSV (Analytic Combinatorics in Several Variables) methods. While ACSV sometimes requires considerable overhead and geometric computation, in the case of symmetric multilinear rational functions there are some reductions that streamline the analysis. Our results include diagonal asymptotics across entire classes of functions, for example the general 3-variable case and the Gillis-Reznick-Zeilberger (GRZ) case, where the denominator in terms of elementary symmetric functions is 1 - e_1 + c e_d in any number d of variables. The ACSV analysis also explains a discontinuous drop in exponential growth rate for the GRZ class at the parameter value c = (d-1)^{d-1}, previously observed for d=4 only by separately computing diagonal recurrences for critical and noncritical values of c.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
Keywords
  • Analytic combinatorics
  • generating function
  • coefficient
  • lacuna
  • positivity
  • Morse theory
  • D-finite
  • smooth point

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. G. Almkvist, D. van Straten, and W. Zudilin. Generalizations of Clausen’s formula and algebraic transformations of Calabi-Yau differential equations. Proc. Edin. Math. Soc., 54:273-295, 2011. Google Scholar
  2. R. Askey and G. Gasper. Certain rational functions whose power series have positive coefficients. Amer. Math. Monthly, 79:327-341, 1972. Google Scholar
  3. R. Askey and G. Gasper. Convolution structures for Laguerre polynomials. J. D'Analyse Math., 31:48-68, 1977. Google Scholar
  4. Y. Baryshnikov, S. Melczer, and R. Pemantle. Asymptotics of multivariate sequences in the presence of a lacuna. In preparation, 2018. Google Scholar
  5. Y. Baryshnikov and R. Pemantle. Asymptotics of multivariate sequences, part III: quadratic points. Adv. Math., 228:3127-3206, 2011. Google Scholar
  6. J. P. Bell and S. Gerhold. On the positivity set of a linear recurrence sequence. Israel J. Math., 157:333-345, 2007. Google Scholar
  7. J. Borcea and P. Brändén. The Lee-Yang and Pólya-Schur programs, II: Theory of stable polynomials and applications. Comm. Pure Appl. Math., 62:1595-1631, 2009. Google Scholar
  8. G. Christol. Diagonales de fractions rationnelles et equations différentielles. In Study group on ultrametric analysis, 10th year: 1982/83, No. 2, pages Exp. No. 18, 10. Inst. Henri Poincaré, Paris, 1984. Google Scholar
  9. P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009. URL: http://algo.inria.fr/flajolet/Publications/books.html.
  10. H. Furstenberg. Algebraic functions over finite fields. J. Algebra, 7:271-277, 1967. Google Scholar
  11. J. Gillis, B. Reznick, and D. Zeilberger. On elementary methods in positivity theory. SIAM J. Math. Anal., 14:396-398, 1983. Google Scholar
  12. M. Hautus and D. Klarner. The diagonal of a double power series. Duke Math. J., 23:613-628, 1971. Google Scholar
  13. M. Kauers. Computer algebra and power series with positive coefficients. In Proc. FPSAC 2007, 2007. Google Scholar
  14. M. Kauers and D. Zeilberger. Experiments with a positivity-preserving operator. Exper. Math., 17:341-345, 2008. Google Scholar
  15. T. Koornwinder. Positivity proofs for linearization and connection coefficients of orthogonal polynomials satisfying an addition formula. J. London Math. Soc. (2), 18(1):101-114, 1978. Google Scholar
  16. C. Koutschan. HolonomicFunctions (User’s Guide). Technical report, no. 10-01 in RISC Report Series, University of Linz, Austria, January 2010. Google Scholar
  17. L. Lipshitz. The diagonal of a D-finite power series is D-finite. J. Algebra, 113(2):373-378, 1988. Google Scholar
  18. S. Melczer. Analytic combinatorics in several variables: effective asymptotics and lattice path enumeration. PhD thesis, University of Waterloo, 2017. URL: https://arxiv.org/abs/1709.05051.
  19. S. Melczer and B. Salvy. Symbolic-numeric tools for analytic combinatorics in several variables. In Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC '16, pages 333-340, New York, NY, USA, 2016. ACM. Google Scholar
  20. R. Pemantle and M. Wilson. Analytic Combinatorics in Several Variables, volume 340 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, New York, 2013. Google Scholar
  21. G. Pólya. Sur les séries entières, dont la somme est une fonction algébrique. L'Enseignement Mathématique, 22:38-47, 1921. Google Scholar
  22. A. Scott and A. Sokal. Complete monotonicity for inverse powers of some combinatorially defined poynomials. Acta Math., 213:323-392, 2013. Google Scholar
  23. A. Straub. Positivity of Szegö’s rational function. Adv. Appl. Math., 41(2):255-264, 2008. Google Scholar
  24. A. Straub. Multivariate Apéry numbers and supercongruences of rational functions. Algebra Number Theory, 8:1985-2008, 2014. Google Scholar
  25. A. Straub and W. Zudilin. Positivity of rational functions and their diagonals. J. Approx. Theory, 195:57-69, 2015. Google Scholar
  26. G. Szegö. Über gewisse Potenzreihen mit lauter positiven Koeffizienten. Math. Zeit., 37:674-688, 1933. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact