Approximating sums by integrals only: multiple sums and sums over lattice polytopes

Year 2022, , 72 - 92, 15.06.2022

Iosif Pinelis

https://doi.org/10.33205/cma.1102689

Abstract

The Euler--Maclaurin (EM) summation formula is used in many theoretical studies and numerical calculations. It approximates the sum
$\sum_{k=0}^{n-1} f(k)$ of values of a function $f$ by a linear combination of a corresponding integral of $f$ and values of its higher-order derivatives $f^{(j)}$. An alternative (Alt) summation formula was presented by the author, which approximates the sum by a linear combination of integrals only, without using derivatives of $f$. It was shown that the Alt formula will in most cases outperform the EM formula. In the present paper, a multiple-sum/multi-index-sum extension of the Alt formula is given, with applications to summing possibly divergent multi-index series and to sums over the integral points of integral lattice polytopes.

Keywords

Euler-Maclaurin summation formula, alternative summation formula, multiple sums, multi-index series, approximation, lattice polytopes

References

• A. Abdesselam, V. Rivasseau: An explicit large versus small field multiscale cluster expansion, Rev. Math. Phys., 9 (2) (1997), 123–199.
• A. Abdesselam, V. Rivasseau: Trees, forests and jungles: a botanical garden for cluster expansions, Constructive physics (Palaiseau, 1994), Lecture Notes in Phys., vol. 446, Springer, Berlin, 1995, pp. 7–36.
• J. Agapito, L. Godinho: New polytope decompositions and Euler-Maclaurin formulas for simple integral polytopes, Adv. Math., 214 (1) (2007), 379–416.
• J. Agapito, L. Godinho: Cone decompositions of non-simple polytopes, J. Symplectic Geom., 14 (3) (2016), 737–766.
• A. I. Barvinok: A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res., 19 (4) (1994), 769–779.
• N. Berline, M. Vergne: Local Euler-Maclaurin formula for polytopes, Mosc. Math. J., 7 (3) (2007), 355– 386, 573.
• M. Brion, M. Vergne: Lattice points in simple polytopes, J. Amer. Math. Soc., 10 (2) (1997), 371–392.
• S. E. Cappell, Julius L. Shaneson: Euler-Maclaurin expansions for lattices above dimension one, C. R. Acad. Sci. Paris Sér. I Math., 321 (7) (1995), 885–890.
• A. Carbery, M. Christ and James Wright: Multidimensional van der Corput and sublevel set estimates, J. Amer. Math. Soc., 12 (4) (1999), 981–1015.
• V. Guillemin, S. Sternberg: Riemann sums over polytopes, vol. 57, 2007, Festival Yves Colin de Verdière, pp. 2183–2195.
• C. Haase: Polar decomposition and Brion’s theorem, Integer points in polyhedra—geometry, number theory, algebra, optimization, Contemp. Math., vol. 374, Amer. Math. Soc., Providence, RI, 2005, pp. 91–99.
• L. Hörmander: Lectures on nonlinear hyperbolic differential equations, Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 26, Springer-Verlag, Berlin, (1997).
• Y. Karshon, S. Sternberg and J.Weitsman: The Euler-Maclaurin formula for simple integral polytopes, Proc. Natl. Acad. Sci. USA, 100 (2) (2003), 426–433.
• Y. Karshon, S. Sternberg and J. Weitsman: Euler-Maclaurin with remainder for a simple integral polytope, Duke Math. J., 130 (3) (2005), 401–434.
• N. H. Katz, E. Krop and M. Maggioni: Remarks on the box problem, Math. Res. Lett., 9 (4) (2002), 515–519.
• K. Knopp: Theory and application of infinite series, Blackie, London, (1951).
• J. Lawrence: Polytope volume computation, Math. Comp., 57 (195) (1991), 259–271.
• Y. L. Floch, Á. Pelayo: Euler-MacLaurin formulas via differential operators, Adv. in Appl. Math., 73 (2016), 99–124.
• I. Pinelis: An alternative to the Euler–Maclaurin summation formula: approximating sums by integrals only, Numerische Mathematik, 140 (3) (2018), 755–790.
• A. V. Pukhlikov, A. G. Khovanski: The Riemann-Roch theorem for integrals and sums of quasipolynomials on virtual polytopes, Algebra i Analiz, 4 (4) (1992), 188–216.
• A. Szenes, M. Vergne: Residue formulae for vector partitions and Euler-MacLaurin sums, Advances in Applied Mathematics, 30 (1–2) (2003), 295–342.
• T. Tate: Asymptotic Euler-Maclaurin formula over lattice polytopes, J. Funct. Anal., 260 (2) (2011), 501–540.
• G. N. Watson: A note on Gamma functions, Edinburgh Math. Notes, 42 (1959), 7–9.
• H. Whitney: Analytic extensions of differentiable functions defined in closed sets, Trans. Amer. Math. Soc., 36 (1) (1934), 63–89.