Counterexamples to the Minimum Period Conjecture for Restricted Partition Functions

Technical Summary: Counterexamples to the Minimum Period Conjecture for Restricted Partition Functions

Problem Statement
The paper addresses the behavior of the restricted partition function $q_a(k)$, which counts the number of nonnegative integer solutions to the equation $a_1x_1 + \dots + a_nx_n = k$ for a fixed sequence of positive integers $a = (a_1, \dots, a_n)$. It is well-established that $q_a(k)$ is a quasi-polynomial of degree $n-1$, expressible as:
$$q_a(k) = \sum_{j=0}^{n-1} c_j(k) k^j$$
where the coefficients $c_j(k)$ are periodic functions.

In 2008, Beck, Sam, and Woods formulated a conjecture regarding the minimum period of these coefficient functions $c_j(k)$. Let $b_m$ denote the number of elements in $a$ divisible by $m$. The conjecture posits that the minimum period of $c_j(k)$ is exactly:
$$p_j = \text{lcm}\{m \in \mathbb{Z}_{>0} : b_m > j\}$$
The authors note that while this conjecture provides a clear divisibility upper bound, its validity as an exact equality had not been rigorously disproven or fully characterized in terms of vanishing coefficients.

Methodology
The authors employ a combination of complex analysis, specifically residue calculus, and discrete Fourier analysis to derive an exact formula for the coefficient functions $c_j(k)$.

1. Root-of-Unity Formula: By analyzing the generating function $R_a(x) = \prod_{i=1}^n (1-x^{a_i})^{-1}$, the authors derive an explicit expression for $c_j(k)$ as a sum over roots of unity. For a root of unity $\zeta$ with multiplicative order $m$, let $s_\zeta$ be the order of the pole of $R_a(x)$ at $\zeta$. The authors define an auxiliary holomorphic function $\Phi_\zeta(t) = t^{s_\zeta} R_a(\zeta e^{-t})$.
2. Coefficient Extraction: They prove that:
   $$c_j(k) = \sum_{\zeta \in \mu_N, s_\zeta > j} \gamma_{\zeta, j} \zeta^{-k}$$
   where $\gamma_{\zeta, j} = \frac{1}{j!} [t^{s_\zeta - 1 - j}] \Phi_\zeta(t)$.
3. Period Determination: Using the uniqueness of the Fourier expansion, they establish that the minimum period of $c_j(k)$ is the least common multiple of the orders of those roots of unity $\zeta$ for which the coefficient $\gamma_{\zeta, j}$ is non-zero.
4. Counterexample Construction: The authors identify that the Beck–Sam–Woods conjecture fails precisely when $\gamma_{\zeta, j} = 0$ for some $\zeta$ where $s_\zeta > j$. They construct a specific two-parameter family of generating functions $R_{u,M}(x) = (1-x^2)^{-4}(1-x)^{-u}(1-x^M)^{-1}$ (with $M$ odd) and derive a Diophantine condition on $u$ and $M$ such that the coefficient corresponding to the root $\zeta = -1$ vanishes.
5. Infinite Family Generation: The condition for vanishing coefficients is transformed into a negative Pell equation ($Y^2 - 3X^2 = -26$). By solving this equation using recurrence relations, they generate infinitely many pairs $(u, M)$ that satisfy the counterexample conditions.

Key Contributions and Results

• Exact Period Formula (Theorem 1.2): The paper provides the first exact formula for the minimum period of $c_j(k)$ in terms of the non-vanishing coefficients of the Taylor expansion of $\Phi_\zeta(t)$. This formula reveals that the period depends not just on the existence of poles ($s_\zeta > j$), but on whether specific Taylor coefficients vanish.
• Sharp Divisibility Bounds (Theorem 1.3): The authors prove that the minimum period $per(c_j)$ satisfies:
  $$\text{lcm}\{m : j+1 \le b_m \le j+2\} \mid per(c_j) \mid \text{lcm}\{m : b_m > j\}$$
  The right-hand side corresponds to the Beck–Sam–Woods conjectured value $p_j$. The paper demonstrates that both the upper and lower bounds are sharp, but the actual period can lie strictly between them.
• Disproof of the Conjecture (Theorem 1.4): The paper constructs an infinite family of counterexamples to the Beck–Sam–Woods conjecture. Specifically, for the sequence defined by $R_{u,M}(x)$, if $u$ and $M$ satisfy the derived Diophantine equation, the minimum period of $c_0(k)$ is $M$, whereas the conjecture predicts $2M$.
  • Specific Example: For $(u, M) = (2, 13)$, the sequence of parts consists of four 2's, two 1's, and one 13. The conjectured period is $p_0 = \text{lcm}(1, 2, 13) = 26$, but the actual minimum period is $13$.
• Variations: The authors provide additional counterexamples where all $a_i > 1$, where $a_i$ are pairwise distinct, and where $\gcd(a)=1$, demonstrating the robustness of the phenomenon across different constraints.

Significance and Claims
The paper claims to resolve the question of the minimum period for restricted partition functions by showing that the Beck–Sam–Woods conjecture, while providing a correct upper bound, is not universally true as an equality. The significance lies in:

1. Refining the Theory: Moving from a conjecture based solely on pole orders to an exact characterization involving the vanishing of specific Taylor coefficients.
2. Correcting the Record: Providing the first known counterexamples to a long-standing conjecture in the field of partition functions and quasi-polynomials.
3. Methodological Insight: Demonstrating that the "wave function" approach (related to Sylvester's work) and the residue calculus approach yield equivalent results, but the latter offers a more precise tool for determining periods by explicitly calculating the coefficients $\gamma_{\zeta, j}$.

The authors modestly conclude that their work replaces the proposed equality with a precise formula and establishes that the conjectured value $p_j$ remains a sharp universal upper bound, even though it is not always the exact period.