A certain conjectured criterion for restricted partitions

267 Views Asked by At

Given the number of partitions of $n$ into distinct parts $q(n)$, with the following generating function

$\displaystyle\prod_{m=1}^\infty (1+x^m) = \sum_{n=0}^\infty q(n)\,x^n\tag{1a}$

Which may be conveniently generalized into

$\displaystyle q_{k}(x)= \sum_{n=0}^\infty q((2k-1)n)\,x^n\tag{1b}$

for positive integers $k$

After some brute-force experimentation with wolfram mathematica, I discovered the following conjecture analogous to the one discussed in this post

The nth coefficient $q((2k-1)n)$ is odd if and only if

the power of the last term included in the partial sum of the generating function $(1b)$ is $n\stackrel{\mathrm{def}}{=}\frac{c}{2}$ where $c$ is the solution to this diophantine equation $d^2-12(2k-1)c=1$ which has two unknowns $d$ and $c$ for every positive integer $k\gt0$

Integer solutions to the diophantine equation above:

Given $e \in \mathbb{Z}$

$k=1: c=3e^2+e, c=3e^2+5e+2$

$k=2: c=9e^2+e, c=9e^2+17e+8$

$k=3: c=15e^2+e, c=15e^2+11e+2, c=15e^2+19e+6, c=15e^2+29e+14$

$k=4:\dots$

$\vdots$

For example let $k=3$, then we have the following generating function $q_3(x)=x^{\color{red}{0}}+3x^{\color{red}{1}}+10x^2+27x^{\color{red}{3}}+64x^4+142x^5+296x^6+585x^{\color{red}{7}}+1113x^{\color{red}{8}}+2048x^9+3658x^{10}+6378x^{11}+\dots$

And as per our conjecture we have the corresponding diophantine equation

$d^2-(12×5)c=1$

Then the coefficient $q(5n)$ from the generating function (1b) is odd iff the powers of x are

$\frac{15e^2+e}{2}: \color{red}{8}, \color{red}{31}, \color{red}{69}, \color{red}{122}, \color{red}{190},\dots$

$\frac{15e^2-e}{2}: \color{red}{7}, \color{red}{29}, \color{red}{66}, \color{red}{118}, \color{red}{185},\dots$

$\frac{15e^2+11e+2}{2}: \color{red}{14}, \color{red}{42}, \color{red}{85}, \color{red}{143}, \color{red}{216},\dots$

$\frac{15e^2-11e+2}{2}: \color{red}{3}, \color{red}{20}, \color{red}{52}, \color{red}{99}, \color{red}{161},\dots$

$\frac{15e^2+19e+6}{2}: \color{red}{20}, \color{red}{52}, \color{red}{99}, \color{red}{161},\dots$

$\frac{15e^2-19e+6}{2}: \color{red}{1}, \color{red}{14}, \color{red}{42}, \color{red}{85}, \color{red}{143},\dots$

$\frac{15e^2+29e+14}{2}: \color{red}{29}, \color{red}{66}, \color{red}{118}, \color{red}{185},\dots$

$\frac{15e^2-29e+14}{2}: \color{red}{0}, \color{red}{8}, \color{red}{31}, \color{red}{69}, \color{red}{122},\dots$

for integers $e\in \mathbb{N_0}$

Thus in general it is clear that the powers at which the coefficient $q((2k-1)n)$ is odd occur when $n\stackrel{\mathrm{def}}{=}\frac{c}{2}$ where $c$ is the solution of the general diophantine equation $d^2-12(2k-1)c=1$

Question: How do we prove the conjecture?

1

There are 1 best solutions below

8
On

The pentagonal number theorem states

$$ \prod_{m=1}^\infty 1-x^m = \sum_{k=-\infty}^\infty (-1)^k x^{k(3k-1)/2} = 1 + \sum_{k=1}^\infty (-1)^k \Big(x^{k(3k+1)/2} + x^{k(3k-1)/2}\Big). $$ In other words, $$ (1-x)(1-x^2)(1-x^3)\cdots = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - \cdots. $$ The exponents $1, 2, 5, 7, 12, \dots$ on the right side are given by the formula $g_k = k(3k-1)/2$ for $k=1,-1,2,-2,3,\dots$ and are called (generalized) pentagonal numbers (sequence A001318 in the OEIS).

Note that

$$ ((6m-1)^2-1)/24 = m(3m-1)/2 = g_m. \tag1 $$

Equivalently, the Diophantine equation

$$ d^2 - 24n = 1 \tag2 $$

has only solutions $\,d = 6m-1\,$ with $\,n = g_m\,$ for some integer $m$. In other words,

$$ n = g_m \quad\text{iff}\quad m = \frac{1\pm\sqrt{1+24n}}6. \tag3 $$

Define the infinite product power series

$$ \prod_{j=1}^\infty (1 - x^j) = \sum_{n=0}^\infty a(n)x^n. \tag4 $$

The pentagonal number theorem is equivalent to the statement that $\, a(n) = 0\,$ iff $\,n \ne g_m\,$ otherwise, $\,a(n) = (-1)^m.\,$ This implies that $\,a(n) \equiv 1 \pmod 2\,$ iff $\, n = g_m\,$ for some $m$.

Define a related infinite product power series

$$ \prod_{j=1}^\infty (1 + x^j) = \sum_{n=0}^\infty q(n)x^n. \tag5 $$

Note that $\,a(n) \equiv q(n) \pmod 2 \,$ because $\, 1 \equiv -1 \pmod 2.$ This implies that $\,q(n)\,$ is odd iff $\,a(n)\,$ is odd and, as previously noted in equation $(2)$, iff $\,n = g_m\,$ for some $m$.

Thus, the conjecture regarding the parity of $\,q(n)\,$ is true.

For example, if $\,n = 15\,$ in equation $(2),\,$ then $\,d=19.\,$ Now $\,a(n) = -1\,$ is odd and also $\, q(n) = 27.\,$ Now $\,q(n) = q(1\cdot 15) = q(3 \cdot 5) = q(5\cdot 3) = q(15\cdot 1)\,$ which applies to the conjecture

The nth coefficient $q((2k-1)n)$ is odd if and only if ...