Counting Restricted Integer Partitions

NEW

Problem: For $b\ge2$, let $p_b(n)$ count partitions of $n$ into powers of $b$, and

$$B_b(m,q)=\sum_{n\ge0}p_b(b^m n)q^n.$$

Blair defines $f_m(b,q)\in\mathbb Q[b,q]$ by

$$(1-q)^mB_b(m,q)=f_m(b,q)B_b(0,q).$$

Let

$$y(i)=\max\{r:\binom r2\le i\}=\left\lfloor\frac{1+\sqrt{8i+1}}2\right\rfloor .$$

Conjecture 1.6.2, as printed, asserts a decomposition of $f_m$ using polynomials $g_{m,i}(q)$, $h_i(q)$, where $q h_i(q)=g_{i+1,i}(q)$, and includes the sum $i=0,\dots,m-1$.

Result: The literal printed statement is false. From Conjecture 1.6.1’s notation,

$$f_1(b,q)=1,$$

so $g_{1,0}(q)=1$. Thus the definition $q h_0(q)=g_{1,0}(q)$ gives $q h_0(q)=1$, impossible for $h_0\in\mathbb Q[q]$. Even allowing $h_0=1/q$, the displayed formula would add an extra constant term.

There is also a boundary overlap at $m=2$: the $i=m-1$ term and the final leading term both involve $b^{\binom m2}=b$. Since

$$f_2(b,q)=1+(b-1)q,$$

the printed formula double-counts the $bq$ term.

The minimal natural repair is:

$$f_1(b,q)=1,\qquad f_2(b,q)=1+(b-1)q,$$

and for $m\ge3$,

$$\boxed{ \begin{aligned} f_m(b,q)=&(1-q)^{m-1}\\ &+q\sum_{i=1}^{m-1}(1-q)^{m-y(i)}h_i(q)b^i\\ &+\sum_{i=m}^{\binom m2-1}(1-q)^{m-y(i)}g_{m,i}(q)b^i\\ &+\frac{q b^{\binom m2}}{(m-1)!}\sum_{j=0}^{m-2}\left\langle {m-1\atop j}\right\rangle q^j . \end{aligned}}$$

Proof of the repaired statement. Define polynomials $C_m(b,t)\in\mathbb Q[b,t]$ by

$$C_1(b,t)=1,\qquad C_{m+1}(b,t)=\sum_{r=0}^{bt}C_m(b,r),$$

interpreted polynomially via Faulhaber summation. Then

$$f_m(b,q)=(1-q)^m\sum_{t\ge0}C_m(b,t)q^t.$$

Write

$$C_m(b,t)=\sum_i b^i P_{m,i}(t).$$

The summation operator sends a polynomial of degree $d$ to one whose $b^s$-part has $t$-degree at most $s$, and $s\le d+1$. Inductively this gives

$$\deg_t P_{m,i}\le y(i)-1.$$

Hence $[b^i]f_m$ is divisible by $(1-q)^{m-y(i)}$, defining $g_{m,i}(q)$.

Also $C_m(b,0)=1$, so $P_{m,i}(0)=0$ for $i>0$. Therefore $g_{i+1,i}(q)$ is divisible by $q$ for $i\ge1$, and $h_i(q)=g_{i+1,i}(q)/q$ is polynomial.

Moreover, for fixed $i\ge1$, the coefficient $P_{m,i}$ stabilizes once $m\ge i+1$: the zero-$b$-increase part is evaluation at $0$, which vanishes for $i>0$. Thus for $1\le i\le m-1$,

$$[b^i]f_m=(1-q)^{m-i-1}[b^i]f_{i+1} =q(1-q)^{m-y(i)}h_i(q).$$

Finally, the top $b$-degree term of $C_m$ is

$$[b^{\binom m2}]C_m(b,t)=\frac{t^{m-1}}{(m-1)!}.$$

Using

$$\sum_{t\ge0}t^{m-1}q^t =\frac{q}{(1-q)^m}\sum_{j=0}^{m-2}\left\langle {m-1\atop j}\right\rangle q^j,$$

we obtain the stated leading coefficient. This proves the repaired conjecture.

Citation: No prior resolution is used here. Source of the conjecture: David Dakota Blair, Counting Restricted Integer Partitions, PhD thesis, CUNY, 2015, Conjecture 1.6.2.