arminstraub.com

# Fast q-binomials in Mathematica

Recently, I have been doing experiments involving q-binomial coefficients in Mathematica. Starting with version 7, Mathematica is prepared for some q-business; in particular, there exists a function named QBinomial giving the q-analog of Binomial. However, this implementation turned out to not be fast enough for my needs. Here is an alternative approach which is not only way faster but provides a full factorization.

qn[n_, q_] :=
Product[If[Mod[n, d] == 0, Cyclotomic[d, q], 1], {d, 2, n}];
qfactorial[n_, q_] :=
Product[Cyclotomic[d, q]^Floor[n/d], {d, 2, n}];
qbinomial[n_, k_, q_] :=
If[k > n, 0,
Product[If[Floor[n/d] == Floor[k/d] + Floor[(n - k)/d], 1,
Cyclotomic[d, q]], {d, 2, n}]];


The above code is based on the following well-known observations. Let $$\Phi_n$$ be the $$n$$-th cyclotomic polynomial. Then $$\left( \begin{array}{c} n\\ k \end{array} \right)_q = \prod_d \Phi_d (q)$$ where the product is taken over those $$2 \leqslant d \leqslant n$$ for which $$\left\lfloor n / d \right\rfloor - \left\lfloor k / d \right\rfloor - \left\lfloor (n - k) / d \right\rfloor = 1$$. This follows from $$[n]_q = \prod_{d|n, d > 1} \Phi_d (q)$$, $$[n]_q ! = \prod_{m = 1}^n \prod_{d|m, d > 1} \Phi_d (q) = \prod_{d = 2}^n \Phi_d (q)^{\left\lfloor n / d \right\rfloor}$$ and $$\left( \begin{array}{c} n\\ k \end{array} \right)_q = \frac{[n]_q !}{[k]_q ! [n - k]_q !} = \prod_{d = 2}^n \Phi_d (q)^{\left\lfloor n / d \right\rfloor - \left\lfloor k / d \right\rfloor - \left\lfloor (n - k) / d \right\rfloor} .$$ Finally, note that $$\left\lfloor n / d \right\rfloor - \left\lfloor k / d \right\rfloor - \left\lfloor (n - k) / d \right\rfloor \in \{0, 1\}.$$