Research ContributionArnold Mathematical Journal

Received: 7 December 2015 / Revised: 28 July 2016 / Accepted: 2 August 2016

q-Polynomial Invariant of Rooted Trees

Józef H. PrzytyckiDepartment of Mathematics The George Washington University Washington, DC 20052 USA, University of Maryland College Park, College Park USA,
University of Gdańsk, Gdańsk Poland


We describe in this note a new invariant of rooted trees. We argue that the invariant is interesting on it own, and that it has connections to knot theory and homological algebra. However, the real reason that we propose this invariant to readers of Arnold Journal of Mathematics is that we deal here with an elementary, interesting, new mathematics, and after reading this essay readers can take part in developing the topic, inventing new results and connections to other disciplines of mathematics, and likely, statistical mechanics, and combinatorial biology.

Tree, Invariant, Quantum plane, UnimodalityKauffman bracket, Gaussian polynomial
$ \newcommand\Z{{\mathbb Z}}$

1 Introduction

1.1 Quantum Plane

We know well the Newton binomial formula:

$\displaystyle \begin{eqnarray*} (x+y)^n= \sum_{i=0}^n {n \choose i} x^iy^{n-i}. \end{eqnarray*}$

Of course we assume here that the variables commute, that is $ yx=xy$.

We can also visualize formulas for coefficients of $ (x+y)^n$ by considering the tree $ T_{b,a}$ of two long branches of length $ b$ and $ a$ respectively, coming from the root (Fig. 1). We can ask now how many different ways there are to “pluck” the tree $ T_{b,a}$ one leaf at a time. Of course we can tear (like in the child’s play “likes not like”) the left or right branch. In total: the left should be torn $ b$ times and the right $ a$ times so the answer about the number of different pluckings is clearly $ {a+b \choose a}$. Our notes present a dramatic generalization of this example.

Figure 1: The tree $ T_{b,a}$ with branches of length $ b$ and $ a$

We can ask now what happens with the binomial formula if we weaken commutativity by replacing it with $ yx=qxy$ ($ q$ commutes with $ x$ and $ y$). In applications in physics, $ q$ is often taken to be a complex number but it is better to work generally with the ring $ Z[q]$ and q-commutative11By $ q$-commutative we understand exactly $ yx=qxy$. polynomials of variables $ x$ and $ y$ over this ring (we call this ring of polynomials the quantum plane or noncommutative plane). The formula for $ (x+y)^n$ in the quantum plane was known already in the XIX century, but if we do not know the result it is good to first work out small examples: $$(x+y)^2= y^2+ xy +yx + x^2= y^2 + (1+q)xy +x^2,$$ \begin{multline*} (x+y)^3= y^3+ xy^2+ yxy +y^2x + x^2y+ xyx + yx^2 +x^3\\ = y^3 + (1+q+q^2)xy^2 + (1+q+q^2)x^2y+ y^3, \end{multline*} \begin{multline*} (x+y)^4= y^4 + xy^3+ yxy^2 +y^2xy + y^3x + x^2y^2 + xyxy\\ + xy^2x + yx^2y + yxyx + y^2x^2 + x^3y+ x^2yx + xyx^2 + yx^3 + x^4 \\= y^4 + (1+q+q^2+q^3)xy^3 + (1+ q + 2q^2+ q^3 + q^4)x^2y^2 + (1+q+q^2+q^3)x^3y +x^4 \\= y^4+(1+q+q^2+q^3)xy^3 + (1+q^2)(1+q+q^2)x^2y^2+ (1+q+q^2+q^3)x^3y +x^4 .\end{multline*} Observe that we can think of $ 1+q+\cdots+q^{n-1}$ as a $ q$-analogue of the number $ n$. We define formally $ [n]_q=1+q+\cdots+q^{n-1}$. In particular, for $ q=1$, $ [n]_q=n$. In the same vein we define $ q$ factorial of the $ q$-number $ [n]_q$ as: $ [n]_q!=[n]_q[n-1]_q\cdots [2]_q[1]_q$, and $ q$-analogue of the binomial coefficient22Called also the Gaussian polynomial, $ q$-polynomial of Gauss, Gaussian binomial coefficient, Gaussian coefficient, or $ q$-binomial coefficient. by $ \binom{n}{i}_q = \frac{[n]_q!}{[i]_q! [n-i]_q!}$. Sometimes to stress symmetry, $ i \leftrightarrow n-i$, of the Gaussian polynomial we write $ \binom{n}{i,n-i}_q$. We also observe that the coefficient of $ x^2y^2$ in $ (x+y)^4$ is $ (1+q^2)(1+q+q^2)= \frac{1+q+q^2+q^3}{1+q}(1+q+q^2)=\frac{[4]_q[3]_q}{[2]_q}= \binom{4}{2}_q$.

In the notation we introduced, our calculations can be concisely written as:

$\displaystyle \begin{eqnarray*} &\displaystyle (x+y)^2= y^2 +[2]_qxy +x^2,\\ &\displaystyle (x+y)^3= y^3 + [3]_qxy^2 + [3]_qx^2y+x^3,\\ &\displaystyle (x+y)^4= y^4+ [4]_qxy^3 + \binom{4}{2}_qx^2y^2 + [4]_qx^3y+ x^4. \end{eqnarray*}$

Now it is not difficult to guess the general formula for $ (x+y)^n$ in the quantum plane:

Proposition 1.1.

([MacMahon1916]; see e.g. [Kac and Cheung2002]; [Mansour and Schork2011]; [Mansour and Schork2016])  If $ yx=qxy$ then

$\displaystyle \begin{eqnarray*} (x+y)^n= \sum_{i=0}^n {n \choose i}_qx^iy^{n-i}. \end{eqnarray*}$

The simplest proof is by induction on $ n$ however one can also find proofs without words, interpreting combinatorially left and right sides of the equation.

Inductive proof  We already checked the formula for $ n\leq 4$, and we should add that we need the convention (as in the classical case). that $ [0]_q!=1$ and consequently $ {n \choose 0}_q=1 ={n \choose n}_q$. Now we perform the inductive step (from $ n-1$ to $ n$):

$\displaystyle \begin{eqnarray*} (x+y)^n=& (x+y)(x+y)^{n-1}=(x+y)\sum_{i=0}^{n-1} {n-1 \choose i,n-i-1}_qx^iy^{n-i-1}\\ =&\sum_{i=0}^{n-1} {n-1 \choose i,n-i-1}_qx^{i+1}y^{n-i-1} +\sum_{i=0}^{n-1}q^i{n-1 \choose i,n-i-1}_qx^iy^{n-i}\\ =&\sum_{i=0}^n\left({n-1 \choose i-1,n-i}_q +q^i{n-1 \choose i,n-i-1}_q\right)x^iy^{n-i}. \end{eqnarray*}$

We use here the convention that $ {n-1 \choose -1,n}_q=0$.

We are left now to check that

$\displaystyle \begin{eqnarray*} {n-1 \choose i-1,n-i}_q +q^i{n-1\choose i,n-i-1}_q)={n \choose i}_q. \end{eqnarray*}$

We encourage the reader to check it by themselves before looking at the following calculation.

  1. (i)

    \begin{multline*}[a+b]_q= 1+q+\cdots+q^{a+b-1}= (1+q+\cdots+q^{a-1}) + q^a(1+q+\cdots+q^{b-1})\\ = [a]_q+q^a[b]_q= [b]_q+q^b[a]_q\end{multline*}

  2. (ii)
    $\displaystyle \begin{eqnarray*} \binom{a+b}{a,b}_q=&\frac{[a+b]_q!}{[a]_q! [b]_q!}=[a+b]_q\frac{[a+b-1]_q!}{[a]_q! [b]_q!}\\ =&([a]_q+q^a[b]_q)\frac{[a+b-1]_q!}{[a]_q! [b]_q!}= \frac{[a+b-1]_q!}{[a-1]_q! [b]_q!} + q^a \frac{[a+b-1]_q!}{[a]_q! [b-1]_q!}\\ =&\binom{a+b-1}{a-1,b}_q + q^a\binom{a+b-1}{a,b-1}_q= \binom{a+b-1}{a,b-1}_q\\& +\, q^b\binom{a+b-1}{a-1,b}_q. \end{eqnarray*}$

$ \square$

We can now go back to the tree $ T_{b,a}$ and play the game in the $ q$-fashion that is the leaf taken from the right ($ a$) branch is counted as $ 1$ but the leaf taken from the left is counted with the weight $ q^a$. Thus we eventually get not the plucking number but the plucking polynomial $ Q(T_{b,a})$ which by definition satisfies the recursive relation $ Q(T_{b,a})= Q(T_{b,a-1}) + q^aQ(T_{b-1,a})$. We also notice that $ Q(T_{0,a})=Q(T_{b,0})=1$, thus we immediately recognize that the plucking polynomial is $ Q(T_{b,a})= \binom{a+b}{a,b}_q$. This is the starting point to our definition of the polynomial of plane rooted trees mentioned in the title of the note.

We can repeat our considerations with many variables, $ x_1,x_2,\ldots,x_k$. If variables commute we get the familiar multinomial formula (e.g. familiar to every student taking multivariable calculus):

$\displaystyle \begin{eqnarray*} (x_1+x_2+\cdots+x_k)^n= \sum_{a_1,\ldots,a_k; \sum a_i=n}^n {n \choose a_1,\ldots,a_k}x_1^{a_1} x_2^{a_2}\cdots x_k^{a_k}, \end{eqnarray*}$

where $ {n \choose a_1,\ldots,a_k} = \frac{[n]!}{[a_1]!\ldots[a_k]!}$. As before the pleasant interpretation of $ {n \choose a_1,\ldots,a_k}$ is the number of pluckings of a tree $ T_{a_k,\ldots,a_2,a_1}$ of $ k$ long branches of length $ a_k,\ldots,a_2,a_1$, respectively, as illustrated in Fig. 2.

Figure 2: The tree $ T_{a_k,\ldots,a_1}$ with branches of length $ a_k,\ldots,a_1$

We can now consider a noncommutative space with $ x_jx_i=qx_ix_j$, for $ i

$\displaystyle \begin{eqnarray*} (x_1+x_2+\cdots+x_k)^n= \sum_{a_1,\ldots,a_k; \sum a_i=n}^n {n \choose a_1,\ldots,a_k}_qx_1^{a_1} x_2^{a_2}\cdots x_k^{a_k}, \end{eqnarray*}$

where $ {n \choose a_1,\ldots,a_k}_q = \frac{[n]_q!}{[a_1]_q!\ldots[a_k]_q!}$. To prove the formula we can again use an induction on $ n$ and again the following two properties are of value:

  1. (i)

    $ [a_1+a_2+\cdots+a_k]_q= [a_1]_q + q^{a_1}[a_2]_q + q^{a_1+a_2}[a_2]_q+\cdots+q^{a_1+a_2+\cdots+a_{k-1}}[a_k]_q.$

  2. (ii)
    $\displaystyle \begin{eqnarray*} {a_1+a_2+\cdots+a_k \choose a_1,a_2,\ldots,a_k}_q =& {a_1+a_2+\cdots+a_k-1 \choose a_1-1,a_2,\ldots,a_k}_q\\ &+\, q^{a_1}{a_1+a_2+\cdots+a_k-1 \choose a_1,a_2-1,\ldots,a_k}_q\\ &+\cdots + q^{a_1+a_2+\cdots+a_{k-1}} {a_1+a_2+\cdots+a_k-1 \choose a_1,a_2,\ldots,a_k-1}_q. \end{eqnarray*}$

As in the $ q$-binomial case, we can interpret the $ q$-multinomial coefficients by $ q$-plucking the tree $ T_{a_k,\ldots,a_2,a_1}$, that is assuming the following plucking formula

$\displaystyle \begin{eqnarray*} Q(T_{a_k,\ldots,a_2,a_1}) =& Q(T_{a_k,\ldots,a_2,a_1-1}) + q^{a_1}Q(T_{a_k,\ldots,a_2-1,a_1})\\ &+\,q^{a_1+a_2}Q(T_{a_k,\ldots,a_3-1,a_2,a_1}) + \cdots + q^{a_1+a_2+\cdots+a_{k-1}}Q(T_{a_k-1,\ldots,a_2,a_1}). \end{eqnarray*}$

The recursion is the same as for the $ q$-multinomial coefficient so we conclude that

$\displaystyle \begin{eqnarray*} Q(T_{a_k,\ldots,a_2,a_1}) = {a_1+a_2+\cdots+a_k \choose a_1,a_2,\ldots,a_k}_q. \end{eqnarray*}$

One can find more properties of $ q$-binomial coefficients in [Kac and Cheung2002] and [Mansour and Schork2016]. The quantum plane relation $ yx=qxy$ can be generalized to the $ q$-deformed or quantized Weyl algebra where $ yx-qxy=h$; see Chapter 7 of [Mansour and Schork2016]. The generalization to rooted trees is not clear, or at least it is not unique. Our $ q$-polynomial is motivated by the Kauffman bracket relation in knot theory ([Dabkowski et al.2015]; [Dabkowski and Przytycki2016]). Possibly a connection of $ q$-deformed Weyl algebra to other quantum invariants of knots, developed by [Fenn and Turaev2007], can lead to other $ q$-polynomial invariants of trees. I would encourage readers to look in this direction. In [Asakly et al.2013] the relation of the Weyl algebra to labeled rooted trees is given but I do not see a clear relation with our work.

2 Recursive Definition of $ q$-Polynomial of Plane Rooted Tree

Our description of the quantum plane and noncommutative space is already over one hundred years old (e.g. MacMahon 1854–1929, [MacMahon1916]). It may, therefore, look surprising that a simple generalization to rooted trees, which we present here, is totally new. Maybe the explanation lies in the observation that, because there are so many $ q$-analogues, a new one is studied only if there is an outside reason to do so (like the Jones revolution in knot theory, in my case). Perhaps our $ q$-polynomial is buried somewhere in a work of MacMahon contemporaries?

We start our definition from the polynomial of a plane (that is embedded in the plane) rooted tree. In Corollary 2.3(iii) we show that the polynomial does not depend on the plane embedding and is therefore an invariant of rooted trees.

Figure 3: Plane rooted tree and an example of $ r(T,v)$

Figure 4: Tree expansion in the q-world

In our work we use the convention that trees are growing up (like in) (Fig. 3).

Definition 2.1.

Consider the plane rooted tree $ T$ (compare ) (Fig. 3). We associate to $ T$ the polynomial $ Q(T,q)$ (or succinctly $ Q(T)$) in the variable $ q$ as follows.

  1. (i)

    If $ T$ is the one vertex tree, then $ Q(T,q)=1$.

  2. (ii)

    If $ T$ has some edges (i.e. $ |E(T)|>0$) then

    $\displaystyle \begin{eqnarray*} Q(T,q)=\sum_{v \in \mbox{ leaves }}q^{r(T,v)}Q(T-v,q), \end{eqnarray*}$

    where the sum is taken over all leaves, that is vertices of degree $ 1$ (not a root), of $ T$ and $ r(T,v)$ is the number of edges of $ T$ to the right of the unique path connecting $ v$ with the root (an example is given in) (Fig. 3).

In Fig. 4 we give an example of the expansion by our formula and if we complete the calculation we get the polynomial $ Q(T)$:

$\displaystyle \begin{eqnarray*} &1+4q+9q^2+17q^3+28q^4+41q^5+56q^6+ 71q^7+83q^8+91q^9+94q^{10}\\ &\quad+\,91q^{11}+ 83q^{12}+ 71q^{13}+ 56q^{14}+ 41q^{15}+ 28q^{16}+ 17q^{17}+9q^{18}\\&\quad+\,4q^{19}+q^{20}. \end{eqnarray*}$
33We show later that it is in fact equal to $ [2]_q^2[4]_q{8\choose 3,5}_q;$ Corollary 2.3 (ii).

As an example we can check that for $ T_{1,1,\ldots,1}$ a star with $ n$ rays we get $ Q(T_{1,1,\ldots,1}) = [n]_q!$. In particular, $ Q(\bigvee)= (1+q)=[2]_q$. One can look at a proof of the formula by direct induction on $ n$, but of course it is a very special case of the last formula of Sect. 1. The first important result in our theory of $ Q(T)$ polynomials is the product formula for trees glued along their roots (wedge or pointed product).

Theorem 2.2.

Let $ T_1 \vee T_2$ be a wedge product of trees $ T_1$ and $ T_2$ . Then:

$\displaystyle \begin{eqnarray*} Q(T_1 \vee T_2)= \binom{|E(T_1)|+|E(T_2)|}{|E(T_1)|}_qQ(T_1)Q(T_2). \end{eqnarray*}$

We proceed by induction on the number of edges of $ T$, $ |E(T)|$, with the obvious initial case of no edges in one of the trees, that is $ |E(T_1)|=0$ or $ |E(T_2)|=0$. For simplicity we write $ E_i$ for $ |E(T_i)|$. Let $ T$ be a rooted plane tree with $ E_1E_2\neq 0$, then we have:

$\displaystyle \begin{eqnarray*} &Q(T)= \sum_{v\in L(T)} q^{r(T,v)}Q(T-v)\\ &\quad=\sum_{v\in L(T_1)} q^{r(T_1,v)+E_2 }Q(T_1-v)\vee T_2)+ \sum_{v\in L(T_2)} q^{r(T_2,v)}Q(T_1\vee (T_2-v))\\ &\quad\stackrel{inductive\ assumption}{=} \sum_{v\in L(T_1)} q^{r(T_1,v)+E_2 }{E_1+E_2-1 \choose E_1-1,E_2}_q Q(T_1-v)Q(T_2)\\ &\qquad+ \sum_{v\in L(T_2)} q^{r(T_2,v)}{E_1+E_2-1 \choose E_1,E_2-1}_qQ(T_1)Q(T_2-v)\\ &\quad= Q(T_2)q^{E_2}{E_1+E_2-1\choose E_1-1,E_2}_q\sum_{v\in L(T_1)} q^{r(T_1,v)}Q(T_1-v)\\ &\qquad+ Q(T_1){E_1+E_2-1 \choose E_1,E_2-1}_q\sum_{v\in L(T_2)} q^{r(T_2,v)}Q(T_2-v)\\ &\quad\stackrel{definition}{=} Q(T_1) Q(T_2)\left(q^{E_2}{E_1+E_2-1 \choose E_1-1,E_2}_q +{E_1+E_2-1\choose E_1,E_2-1}_q\right)\\ &\quad= Q(T_1) Q(T_2){E_1+E_2\choose E_1,E_2}_q \mbox{ as needed}. \end{eqnarray*}$
46One can modify the polynomial $ Q(T)$ so that the formula of Theorem 2.2 can be interpreted as a homomorphism. For this we take $ Q'(T)=\frac{Q(T)}{[|E(T)|]_q!}$. With this definition we have $ Q'(T_1\vee T_2)= Q'(T_1)Q'(T_2)$. A disadvantage of such an approach is that $ Q'(T)$ is not ncessarily a polynomial but only a rational function.

$ \square$

Directly from Theorem 2.2 we conclude several properties of the $ q$-polynomial, $ Q(T)$, which by the nature of its definition, as pointed up before, we propose to be called the plucking polynomial. We should stress, in particular, part (iii) which establishes the independence of the polynomial of its plane embedding.

Corollary 2.3.
  1. (i)

    Let a plane tree be a wedge product of $ k$ trees that is

    $\displaystyle \begin{eqnarray*} T=T_{k} \vee \cdots \vee T_2 \vee T_1, \; \mbox{ then } \end{eqnarray*}$
    $\displaystyle \begin{eqnarray*} Q(T)= \binom{E_k+E_{k-1}+\cdots+E_1}{E_k,E_{k-1},\ldots,E_1}_qQ(T_k)Q(T_{k-1})\cdots Q(T_1). \end{eqnarray*}$

    where $ E_i=|E(T_i)|$ is the number of edges in $ T_i$ .

  2. (ii)

    (State product formula)

    $\displaystyle \begin{eqnarray*} Q(T) = \prod_{v\in V(T)}W(v), \end{eqnarray*}$

    where $ W(v)$ is a weight of a vertex (we can call it a Boltzmann weight) defined by:

    $\displaystyle \begin{eqnarray*} W(v)= \binom{|E(T^v)|}{|E(T^v_{k_v})|,\ldots,|E(T^v_{1})|}_q, \end{eqnarray*}$

    where $ T^v$ is a subtree of $ T$ with root $ v$ (part of $ T$ above $ v$, in other words $ T^v$ grows from $ v$) and $ T^v$ may be decomposed into wedge of trees as follows: $ T^v= T^v_{k_v} \vee \cdots \vee T^v_2 \vee T^v_{1}.$

  3. (iii)

    (Independence from a plane embedding) Plucking polynomial, $ Q(T)$ does not depend on a plane embedding, it is therefore an invariant of rooted trees.

  4. (iv)

    (Change of root). Let $ e$ be be an edge of a tree $ T$ with the endpoin ts $ v_1$ and $ v_2$. Denote by $ E_1$ the number of edges of the tree $ T_1$ with the root $ v_1$ and $ E_2$ the number of edges of the tree $ T_2$ with the root $ v_2$, where


(i)  The formula (i) follows by using $ (k-1)$-times the product formula of Theorem 2.2 and the fact that the $ q$-multinomial coefficient is a product of binomial coefficients:

$\displaystyle \begin{eqnarray*} &\binom{a_k+a_{k-1}+\cdots+a_2+a_1}{a_k,a_{k-1},\ldots,a_2,a_1}_q\\ &\quad\stackrel{def.}{=} \frac{[a_k+a_{k-1}+\cdots+a_2+a_1]_q!}{[a_k]_q![a_{k-1}]_q!\ldots[a_2]_q![a_1]_q!}\\ &\quad=\frac{[a_2+a_1]_q!}{[a_2]_q! [a_1]_q!}\cdot\frac{[a_3+a_2+a_1]_q!}{[a_3]_q! [a_2+a_1]_q!}\cdot\, \cdots \,\cdot \frac{[a_k+a_{k-1}+\cdots+a_2+a_1]_q!}{[a_k]_q! [a_{k-1}+\cdots+a_2+a_1]_q!}\\ &\quad= \binom{a_2+a_1}{a_2,a_1}_q\binom{a_3+a_2 + a_1}{a_3,a_2+a_1}_q\binom{a_4+a_3+a_2 + a_1}{a_4,a_3+a_2+a_1}_q\\ &\qquad\cdots \binom{a_k+a_{k-1}+\cdots+a_2+a_1}{a_k,a_{k-1}+\cdots+a_2+a_1}_q \end{eqnarray*}$

(ii)  The formula (ii) follows by using (i) several times.

(iii)  Independence of embedding follows from the fact that the state product formula (ii) does not depend on the embedding.

(iv)  We compare product formulas of Theorem 2.2 for $ v_1$ and $ v_2$ and we get:

$\displaystyle \begin{eqnarray*} Q(T,v_1)=&{E_1+E_2+1 \choose E_1, E_2+1}_q Q(T_1)Q(T_2)\quad \mbox{ and }\\ Q(T,v_2)=& {E_1+E_2+1 \choose E_1+1, E_2}_q Q(T_1)Q(T_2), \end{eqnarray*}$

from which the formula of (iv) follows directly. $ \square$

There are other nice properties of $ Q(T)$ (e.g. the observation that it has polynomial time complexity) and I am sure readers will discover more. Here we give a few properties which have some importance in knot theory.

Corollary 2.4.
  1. 1.

    $ Q(T)$ is of the form $ c_0+c_1q+\cdots+c_Nq^N$ where: (i) $ c_0=1=c_N$ , $ c_i>0$ for every $ i\leq N$ , (ii) $ c_i=c_{N-i}$ , that is $ Q(T)$ is a palindromic polynomial (often, less precisely we say symmetric polynomial), (iii) the sequence $ c_0,c_1,\ldots,c_N$ is unimodal, that is for some $ j$ :

    $\displaystyle \begin{eqnarray*} c_0\leq c_1 \leq \cdots \leq c_j \geq c_{j+1} \geq \cdots \geq c_N \end{eqnarray*}$

    (in our case $ j= \lfloor\frac{N}{2}\rfloor$ or $ \lceil\frac{N}{2}\rceil$). (iv) For a nontrivial tree $ T$, that is a tree with at least one edge, we have:

    $\displaystyle \begin{eqnarray*} c_1 = \sum_{v\in V(T)} (k_v-1), \end{eqnarray*}$

    where $ k_v= deg_{T^v}(v)$ is the number of edges growing up from $ v$ , that is the degree of $ v$ in the tree $ T^v$ growing from $ v$ (as in Corollary 2.3 (ii)). In particular, if $ T$ is a binary tree, $ c_1(T)$ is the number of vertices of $ T$ which are not leaves.

  2. 2.
    1. (i)

      $ Q(T)$ is a product of $ q$-binomial coefficients (of type $ {a+b\choose a}_q$).

    2. (ii)

      $ Q(T)$ is a product of cyclotomic polynomials. 77 Recall that $ n$ th cyclotomic polynomial is a minimal polynomial which has as a root $ e^{2\pi i/n}$ . We can write this polynomial as: $ \Psi_n(q)=\prod_{\omega^n=1,\omega^k\neq 1, k. For example $ \Psi_4(q)=1+q^2$ , $ \Psi_6(q)=1-q+q^2$ .

  3. 3.

    The degree of the polynomial $ N=deg Q(T)$ can be described by the formula:

    $\displaystyle \begin{eqnarray*} N=deg Q(T)=\sum_{v\in V(T)}\left(\sum_{1\leq i < j \leq k_v}E_i^vE_j^v\right), \end{eqnarray*}$

    where, as in Corollary 2.3(ii) $ T^v$ is a subtree of $ T$ with the root $ v$ (part of $ T$ above $ v$, in other words $ T^v$ is growing from $ v$) and $ T^v$ can be presented as a bouquet of trees: $ T^v= T^v_{k_v} \vee \cdots \vee T^v_2 \vee T^v_{1}.$


1(i) follows easily from the definition of the plucking polynomial. Namely we see that the constant term is obtained in a unique way by always plucking the most rightmost leaf from the tree (repeating this each time in the calculation). Thus $ c_0=1$. Similarly, the highest power of $ q$ is obtained uniquely by always plucking the leftmost leaf of the tree. The condition that $ c_i>0$ for any $ i\leq N$ requires a more careful look at the recursive computation of $ Q(T)$ and the proof is absolutely elementary; we leave it to the reader because in (iii) we provide much a stronger condition (but using a nontrivial fact proven by [Sylvester1878]). (1)(ii) We start from observing the symmetry of $ q$-binomial coefficients; namely we have:

$\displaystyle \begin{eqnarray*} {a+b \choose a,b}_{q^{-1}} = q^{-ab} {a+b \choose a,b}_q. \end{eqnarray*}$

Then we use an easy observation that a product of symmetric polynomials is symmetric, and the fact we proved already and formulated in (2) that the polynomial $ Q(T)$ is always a product of binomial coefficients. (1) (iii) Follows from the nontrivial fact, originally proved by Sylvester that $ q$-binomial coefficients are unimodal and from a simple observation that a product of symmetric (i.e. palindromic) positive unimodal polynomials is symmetric unimodal (see [Stanley1989]; [Wintner1938]). (1) (iv) The formula for $ c_1$ follows from the observation that $ {a+b \choose a, b}_q= 1+q+\cdots$ for $ a,b >0$ and more generally, $ {a_1+a_2+\cdots+a_k \choose a_1,a_2,\ldots,a_k}_q = 1+ (k-1)q + \cdots $ for $ a_1,a_2,\ldots,a_k >0$. Then the conclusion follows from the product formula of Corollary 2.3. (2) and (3): These conditions follow directly from the product formula of Corollary 2.3(ii). $ \square$

With regard to Corollary 2.4(iii) we can ask: for which trees, is $ Q(T)$ strictly unimodal, that is

$\displaystyle \begin{eqnarray*} c_0 < c_1 < \cdots < c_j > c_{j+1} > \cdots > c_N \end{eqnarray*}$

for some $ j$; compare the computation for the tree of Fig. 3 (see also [Pak and Panova2013]).

3 Comments and Connections

As I was stressing from the beginning, and by now many readers may agree, the $ q$-polynomial (plucking polynomial) is interesting on its own. However, I would have never constructed or discovered it if I had not observed its shadow in my knot theory research. Concretely it was my work with M.Dabkowski and his student C.Li concerning skein modules of generalized (lattice) crossings (Fig. 5), which gave some initial motivation ([Dabkowski et al.2015]). In that paper we do not use $ Q(T)$, as it was observed after the paper was completed. We will use it, however, in future research ([Dabkowski and Przytycki2016]). Knot theory also motivates specific generalizations of the plucking polynomial by enhancing it with a delay function, $ f: L(V) \to {\mathcal N}=\{n\in \Z\ | \ n \geq 1\}$. This function regulates which leaves are used in the recursive formula (Definition 2.1) and which are “delayed”. In fact we have much flexibility in the definition so we challenge a reader to play with possibilities.

The relation of the plucking polynomial to the Kauffman bracket skein modules is precise but difficult to describe succinctly. To have a concrete idea we can say that it concerns the study of the generalized (lattice) crossing (Fig. 5), under the assumption that we resolve every crossing using the Kauffman bracket skein relation , and replace every trivial component by the Laurent polynomial $ -A^2 - A^{-2}$.

Figure 5: $ T_{m\times n}$: $ m\times n$ lattice crossing

One can generalize the plucking polynomial to any graph. If a graph $ G$ has a base-point $ b$ then the invariant $ Q(G,b)$ is a collection (multiset) of plucking polynomials of spanning trees $ G$ with the root $ b$ ([Przytycki2016]). I challenge the reader to study connections of this invariant with known invariants of graphs.

Our polynomial also has relations to homological algebra: let $ \mathcal C$ be a chain complex, that is a sequence of abelian groups, $ C_n$, and homomorphisms $ \partial_n:C_n \to C_{n-1}$, so that $ \partial_{n-1} \partial_n = 0$. On the basis of a chain complex we build homology groups by defining $ H_n(\mathcal C)= \ker \partial_n/im(\partial_{n+1})$. Very often in topology and homological algebra the boundary operation $ \partial_n$ is an alternating sum of homomorphisms, called face maps: $ \partial_n= \sum_{i=0}^n (-1)^id_i$. M. Kapranov asked about what happens if $ (-1)^i$ is replaced by $ q^n$, that is we define

$\displaystyle \begin{eqnarray*} \partial^q_n= \sum_{i=0}^n q^id_i. \end{eqnarray*}$

He noticed that if $ q$ is a $ k$th root of unity different from $ 1$ (i.e. $ q^k=1, q\neq 1$) then the $ k$th iteration of $ \partial^q$ is the zero map ($ \partial^q_{n-k+1}\ldots\partial^q_{n-1} \partial^q_n = 0$) ([Kapranov2016]). The fact that Kapranov’s idea is related to our $ q$-polynomial is clear, however deep connections require careful study: possibly you—the reader—could make a breakthrough.

J. H. Przytycki was partially supported by the GWU REF Grant, and Simons Collaboration Grant-316446. The author would like to thank a referee for directing his attention to [Asakly et al.2013] and [Mansour and Schork2011]; [Mansour and Schork2016].


  • [Asakly et al.2013] Asakly, W., Mansour, T., Schork, M.: Representing elements of the Weyl algebra by labeled trees. J. Math. Phys. 54(2), 023514 (2013)
  • [Dabkowski et al.2015] Dabkowski, M.K., Li, C., Przytycki, J.H.: Catalan states of lattice crossing. Topol. Appl. 182, 1–15 (2015). [math.GT]
  • [Dabkowski and Przytycki2016] Dabkowski, M.K., Przytycki, J.H.: Catalan states of lattice crossing II (2016) (in preparation)
  • [Fenn and Turaev2007] Fenn, R., Turaev, V.: Weyl algebras and knots. J. Geom. Phys. 57, 1313–1324 (2007)
  • [Kac and Cheung2002] Kac, V., Cheung, P.: Quantum calculus. Universitext, Springer (2002)
  • [Kapranov2016] Kapranov, M.M.: On the q-analog of homological algebra. J. Knot Theory Ramif. (2016). (to appear)
  • [Loday1998] Loday, J.L.: Cyclic homology. Grund. Math. Wissen. Band, vol. 301. Springer, Berlin (1992) (2nd edn, 1998)
  • [MacMahon1916] MacMahon, P.A.: Combinatory analysis, vol. 2. Cambridge University Press, Cambridge (1916) (vol. 1, 1915)
  • [Mansour and Schork2011] Mansour, T., Schork, M.: The commutation relation $ xy=qyx +hf(y)$ and Newton’s binomial formula. Ramanujan J. 25, 405–445 (2011)
  • [Mansour and Schork2016] Mansour, T., Schork, M.: Commutation relations, normal ordering, and Stirling numbers. CRC Press, Taylor & Francis Group, USA (2016)
  • [Pak and Panova2013] Pak, I., Panova, G.: Strict Unimodality of $ q$-Binomial Coefficients. C. R. Acad. Sci. Paris, Ser. I 351(11–12), 415–418 (2013). [math.CO]
  • [Przytycki2016] Przytycki, J.H.: Knots and graphs: two centuries of interaction. In: Proceedings of Knots-2013, Mohali, India. To appear in Contemporary Mathematics, vol. 670 (2016)
  • [Stanley1989] Stanley, R.P.: Log-concave and unimodal sequences in algebra, combinatorics, and geometry, vol. 576, pp. 500–535. Annals of the New York Academy of Sciences, New York (1989)
  • [Sylvester1878] Sylvester, J.J.: Proof of the hithero undemonstrated Fundamental Theorem of Invariants. Philos. Mag. 5, 178–188 (1878) [reprinted in Coll. Math. Papers, vol 3. Chelsea, New York 1973, 117–126 (1973)]
  • [Wintner1938] Wintner, A.: Asymptotic distributions and infinite convolutions. Edwards Brothers, Ann Arbor (1938)