This question extends my earlier MO post for which I'm grateful for answers and useful comments.

The Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$ satisfy: $\text{$C_{1,n}$ is odd iff $n=2^j-1$ for some $j$}$.

The $2$-adic valuation of $x\in\mathbb{N}$ is the highest power $2$ dividing $x$, denoted by $\nu(x)$. Let $s(x)$ stand for the sum of the binary digits of $x$. Then, we have the fact that $$\nu(C_{1,n})=s(n+1)-1. \tag1$$ Let $n+1=n_r2^r+n_{r-1}2^{r-1}+\cdots+n_12+n_0$ be the binary expansion of $n+1\in\mathbb{N}$, for some $n_j\in\{0,1\}$. Further, denote by $(n+1)^*=\{n_{j_1},n_{j_2},\dots,n_{j_t}\}$ the non-zero digits ordered as $j_1>j_2>\cdots>j_t$. Note: $\#(n+1)^*=s(n)$.

One version of the $q$-Catalan polynomials $C_n(q)$ is given in the manner $$C_n(q)=\frac1{[n+1]_q}\binom{2n}n_q;$$ where $[0]_q:=1, [n]_q=\frac{1-q^n}{1-q}$ and $\binom{n}k_q=\frac{[n]_q!}{[k]_q![n-k]_q!}$. Here $[n]_q!=[1]_q[2]_q\cdots[n]_q$.

Working in the spirit of (1), I was curious to find a possible $q$-analogue.

QUESTION 1. Is this true? If so, how does the proof go? $$\prod_{k=1}^{t-1} (1+q^{2^{j_k}}) \qquad \text{divides} \qquad C_n(q), \tag2$$ and no other such factors divide it!

REMARK. In view of the fact that the term $1+q^{2^{j_t}}$ is absent from the LHS of (2) ensures that (2) indeed emulates (1), naturally.


For a positive integer $m$, an $m$-th primitive root $\alpha_m$ of $-1$ [which is the root of the polynomial $1+q^m$, and when $m$ is a power of two the converse also holds: any root of $q^m+1$ is an $m$-th primitive root of $-1$] is a root of $[k]_q$ exactly when $2m$ divides $k$. So, $\alpha_m$ is a root of $[N!]_q$ of multiplicity $[\frac{N}{2m}]$. Therefore, $\alpha_m$ is a root of $C_n(q)$ of multiplicity $$\left[\frac{2n}{2m}\right]-\left[\frac{n}{2m}\right]-\left[\frac{n+1}{2m}\right].$$ When is this positive? For $m=1$ never, so assume that $m>1$. Denote $n+1=2mk+r$, $0\leqslant r<2m$. Then we have $$ \left[\frac{2n}{2m}\right]-\left[\frac{n}{2m}\right]-\left[\frac{n+1}{2m}\right]=
2k-\chi_{r=0}+\chi_{r>m}-\left(2k-\chi_{r=0}\right)-2k=\chi_{r>m}. $$ Now if $m=2^a$, and $n+1=2^{j_1}+2^{j_2}+\dots+2^{j_t}$, $j_1>j_2>\dots>j_t$, the remainder of $n+1$ modulo $2^{a+1}$ is greater than $2^a$ exactly when $a\in \{j_1,j_2,\dots,j_{t-1}\}$. This implies your claim.

Note also that $C_n(q)$ is a product of cyclotomic polynomials in certain powers (since so is each $[k]_q$). All cyclotomic polynomials other than $\Phi_{2^{a+1}}=1+q^{2^a}$, $a=0,1,\dots$, take value 1 at point 1. Therefore substituting $q=1$ to the $q$-version we get the usual $q=1$ oddity statement.


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.