A polynomial time algorithm for Sylvester waves when entries are bounded

2024/06/27 by Guoce Xin, Chen Zhang, Xin, Guoce +1 · 1 citation
Engineering · #Advanced Surface Polishing Techniques

paper · pdf · doi:10.48550/arxiv.2406.18975

Abstract

The Sylvester's denumerant \( d(t; \boldsymbola) \) is a quantity that counts the number of nonnegative integer solutions to the equation \( ∑_i=1^N a_i x_i = t \), where \( \boldsymbola = (a₁, …, a_N) \) is a sequence of distinct positive integers with \( gcd(\boldsymbola) = 1 \). We present a polynomial time algorithm in N for computing \( d(t; \boldsymbola) \) when \( \boldsymbola \) is bounded and \( t \) is a parameter. The proposed algorithm is rooted in the use of cyclotomic polynomials and builds upon recent results by Xin-Zhang-Zhang on the efficient computation of generalized Todd polynomials. The algorithm has been implemented in Maple under the name Cyc-Denum and demonstrates superior performance when \( a_i ≤ 500 \) compared to Sills-Zeilberger's Maple package PARTITIONS.

Cited by

• Counterexamples to the Minimum Period Conjecture for Restricted Partition Functions

Related

• An algebraic combinatorial approach to Sylvester's denumerant
• On the Sylvester waves in partition function
• An Algebraic Approach to q-Partial Fractions and Sylvester Denumerants
• Partitions and Sylvester waves
• Distributed Computation for Solving the Sylvester Equation Based on Optimization