Coefficients of Sylvester's denumerant

zbMATH Open1318.05004arXiv1312.7147MaRDI QIDQ5262025FDOQ5262025

Matthias Köppe, Jesús A. De Loera, Michèle Vergne, Nicole Berline, Velleda Baldoni, Brandon Dutra

Publication date: 9 July 2015

Abstract: For a given sequence

m a t h b f a l p h a = [a l p h a_{1}, a l p h a_{2}, d o t s, a l p h a_{N + 1}]

of

N + 1

positive integers, we consider the combinatorial function

E (m a t h b f a l p h a) (t)

that counts the nonnegative integer solutions of the equation

a l p h a_{1} x_{1} + a l p h a_{2} x_{2} + c d o t s + a l p h a_{N} x_{N} + a l p h a_{N + 1} x_{N + 1} = t

, where the right-hand side

t

is a varying nonnegative integer. It is well-known that

E (m a t h b f a l p h a) (t)

is a quasi-polynomial function in the variable

t

of degree

N

. In combinatorial number theory this function is known as Sylvester's denumerant. Our main result is a new algorithm that, for every fixed number

k

, computes in polynomial time the highest

k + 1

coefficients of the quasi-polynomial

E (m a t h b f a l p h a) (t)

as step polynomials of

t

(a simpler and more explicit representation). Our algorithm is a consequence of a nice poset structure on the poles of the associated rational generating function for

E (m a t h b f a l p h a) (t)

and the geometric reinterpretation of some rational generating functions in terms of lattice points in polyhedral cones. Our algorithm also uses Barvinok's fundamental fast decomposition of a polyhedral cone into unimodular cones. This paper also presents a simple algorithm to predict the first non-constant coefficient and concludes with a report of several computational experiments using an implementation of our algorithm in LattE integrale. We compare it with various Maple programs for partial or full computation of the denumerant.

Full work available at URL: https://arxiv.org/abs/1312.7147

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

zbMATH Keywords

polyhedral cones Barvinok's fast decomposition unimodular cones

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial aspects of partitions of integers (05A17)

Cited In (3)

Uses Software

This page was built for publication: Coefficients of Sylvester's denumerant

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5262025)