ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2022. Vol 40

Generating Function of the Solution of a Difference Equation and the Newton Polyhedron of the Characteristic Polynomial

Evgenij K. Leinartas1, Tat’jana I. Yakovleva1

1Siberian Federal University, Krasnoyarsk, Russian Federation


Generating functions and difference equations are a powerful tool for studying problems of enumerative combinatorial analysis. In the one-dimensional case, the space of solutions of the difference equation is finite-dimensional. In the transition to a multidimensional situation, problems arise related both to the possibility of various options for specifying additional conditions on the solution of a difference equation (the Cauchy problem) and to describing the corresponding space of generating functions.

For difference equations in rational cones of an integer lattice, sufficient conditions are known on the Newton polyhedron of the characteristic polynomial that ensure the preservation of the Stanley hierarchy for the generating functions of its solutions. Namely, a generating function is rational (algebraic, D-finite) if such are the generating functions of the initial data and the right side of the equation.

In this paper, we propose an approach for finding the generating function of a solution to a difference equation based on the possibility of extending the rational cone in which solutions of the equation are sought to a cone in which sufficient conditions for the conservation of the Stanley hierarchy are satisfied. In addition, an integral formula is given that relates the generating functions of the solution in the original and extended cones.

About the Authors

Evgenij K. Leinartas, Dr. Sci. (Phys.–Math.), Assoc. Prof., Siberian Federal University, Krasnoyarsk, 660041, Russian Federation, lein@mail.ru.

Tat’jana I. Yakovleva, Cand. Sci. (Phys.Math.), Siberian Federal University, Krasnoyarsk, 660041, Russian Federation, t.neckrasova@gmail.com

For citation
Leinartas E. K., Yakovleva T. I. Generating function of the solution of a difference equation and the Newton polyhedron of the characteristic polynomial. The Bulletin of Irkutsk State University. Series Mathematics, 2022, vol. 40, pp. 3–14. (in Russian) https://doi.org/10.26516/1997-7670.2022.40.3
multidimensional difference equations, Cauchy problem, generating function, Newton polyhedron of the characteristic polynomial, rational cone

1.Leinartas E.K. Multidimensional Hadamard composition and sums with linear constraints on the summation indices. Sib. Math. J., 1989, vol. 30, pp. 250–255. https://doi.org/10.1007/BF00971380

2. Leinartas E.K. Multiple Laurent series and fundamental solutions of linear difference equations. Sib. Math. J., 2007, vol. 48, pp. 268–272. https://doi.org/10.1007/s11202-007-0026-0

3. Leinartas E.K., Nekrasova T.I. Constant coefficient linear difference equations on the rational cones of the integer lattice. Sib. Math. J., 2016, vol. 57, pp. 74–85. https://doi.org/10.1134/S0037446616010080

4. Nekrasova T.I. Dostatochnye uslovija algebraichnosti proizvodjashhih funkcij reshenij mnogomernyh raznostnyh uravnenij [Sufficient conditions of algebraicity of generating functions of the solutions of multidimensional difference equations]. The Bulletin of Irkutsk State University. Series Mathematics, 2013, vol. 6, no. 3, pp. 88–96. (in Russian)

5. Pochekutov D.Y. Diagonals of the laurent series of rational functions.Sib. Math. J., 2009, vol. 50, no. 6, pp. 1081–1091. https://doi.org/10.1007/s11202-009-0119-z

6. Stanley R. Perechislitel’naja kombinatorika. Derev’ja, proizvodjashhie funkcii i simmetricheskie funkcii [Enumerative combinatorics. Trees, generating functions and symmetric functions.] Moscow, Mir Publ., 2009, 767 p. (in Russian)

7. Yakovleva T.I. Well-posedness of the Cauchy problem for multidimensional difference equations in rational cones. Siberian Mathematical Journal, 2017, vol. 58, no. 2, pp. 363–372.https://doi.org/10.1134/S0037446617020185

8. Apanovich M.S., Leinartas E.K. On correctness of Cauchy problem for a polynomial difference operator with constant coefficients. The Bulletin of Irkutsk State University. Series Mathematics, 2018, vol. 26, pp. 3–15. https://doi.org/10.26516/1997-7670.2018.26.3

9. Bousquet-M´elou M., Petkovˇsek M. Linear recurrences with constant coefficients: the multivariate case. Discrete Mathematics, 2000, vol. 225, pp. 51–75.

10. Djokoviˆc D.ˆZ. A properties of the Taylor expantion of rational function in several variables. J. of Math. Anal. and Appl., 1978, vol. 66, pp. 679–685.

11. Haustus M.L.T., Klarner D.A. The diagonal of a double power series. Duke Math. J., 1971, vol. 38, no. 2, pp. 229–235.

12. Leinartas E.K., Yakovleva T.I. The Cauchy problem for multidimensional difference equations and the preservation of the hierarchy of generating functions of its solutions. Journal of Siberian Federal University. Mathematics and Physics, 2018, vol. 11, no. 6, pp. 712–722. https://doi.org/10.17516/1997-1397-2018-11-6-712-722

13. Lipshitz L. D-Finite power series. Journal of Algebra, 1989, vol. 122, pp. 353–373.

14. Lyapin A.P., Chandragiri S. Generating functions for vector partition functions and a basic recurrence relation. Journal of Difference Equations and Applications, 2019, vol. 25, no. 7, pp. 1052–1061. https://doi.org/10.1080/10236198.2019.1649396

Full text (russian)