Counterexamples to the Minimum Period Conjecture for Restricted Partition Functions

Abstract

For a finite sequence of positive integers $\mathbf{a}=(a_1,\dots ,a_n)$, the restricted partition function $q_{\mathbf{a}}(k)$ denote the number of nonnegative integer solutions to the equation $a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n=k$. It is proved to be a quasi-polynomial of degree $n-1$. Write $q_{\mathbf{a}}(k)={\sum }_{j=0}^{n-1}{c}_j(k)k^j$ with periodic coefficient functions $c_j$, and set $b_m=\#\{i:m\mid a_i\}$. In 2008, Beck, Sam, and Woods conjectured that the minimum period of $c_j(k)$ is $\mathrm{lcm}\{m:b_m>j\}$. In this paper, we derive an exact root-of-unity formula for every coefficient function $c_j(k)$. The formula proves the conjectured divisibility upper bound, but it also reveals a lower bound for the period of $c_j(k)$. Both divisibility bounds are sharp. This leads us to construct a family of counterexamples to this conjecture.

19 pages