# how to get the coefficient of a special term in the expansion of the graph polynomial?

What is the coefficient $c$ of the term $x_1^2x_2^2x_3^2\cdots x_{12}^2$ in the expansion of the following multivariable polynomial:

$(x_1-x_2)(x_1-x_3)(x_1-x_4)(x_1-x_{10})(x_2-x_3)(x_2-x_5)(x_2-x_{11})(x_3-x_6)(x_3-x_{12})(x_4-x_5)(x_4-x_6)(x_4-x_7)(x_5-x_6)(x_5-x_8)(x_6-x_9)(x_7-x_8)(x_7-x_9)(x_7-x_{10})(x_8-x_9)(x_8-x_{11})(x_9-x_{12})(x_{10}-x_{11})(x_{10}-x_{12})(x_{11}-x_{12})$

If we recognized each $x_i$ as a vertex and each factor as a edge, then we get a quadrilateral tessellation of the torus. The above polynomial is actually as the graph polynomial of the following quadrangulation of the torus:

I hope someone can give an algorithm to get the coefficient of the term $x_1^2x_2^2x_3^2\cdots x_{12}^2$ in the expansion of the above graph polynomial. Thank you very much!

• Would you mind editing your question so that it states the general question (written in the comments of Carlo Beenakker's answer) rather than just this special case?
– j.c.
Jun 4, 2018 at 15:39

With slightly different notations (and with the opposite sign), we look for the coefficient of $\prod a_i^2b_i^2c_i^2$ in the polynomial $F:=\prod_{i=1}^{2n} (a_{i+1}-a_i)(b_{i+1}-b_i)(c_{i+1}-c_i)\cdot \prod_{i=1}^{2n} (a_i-b_i)(b_i-c_i)(c_i-a_i)$, where indices are taken modulo $n$. We may apply this formula for all sets $A_i=\{0,1,2\}$. How does a non-zero value of $F$ occur? For each $i$, $[a_i,b_i,c_i]$ is a permutation $\pi_i$ of $0,1,2$, and $\pi_{i+1}$ is obtained from $\pi_i$ by a cyclic shift (there are two possible shifts). If we introduce $\varepsilon_i=\pm 1$ dependently on which shift is used, then $\sum \varepsilon_i$ must be divisible by 3 and the value of the polynomial is $4^{2n}\prod \varepsilon_i$. The denominator in the formula is always $4^{2n}$. So the coefficient equals $$6\sum_{3|\varepsilon_1+\dots+\varepsilon_{2n}}\varepsilon_1\cdot \ldots \cdot\varepsilon_{2n}=6\sum_{3 |m-n} (-1)^m\binom{2n} {m},$$ 6 corresponds to the choice of $\pi_1$, $m$ denotes the number of negative $\varepsilon$'s. The sum equals $\frac13((1-1)^{2n}+w^{-n}(1-w)^{2n}+w^{-2n}(1-w^2)^{2n})=\frac23 (-3)^n$, where $w=e^{2\pi i/3}$, thus the answer is $4(-3)^n$.

Here we use the fact (somebody here on MO told how is it called but I forgot) that for a Laurent polynomial $f(z)=\sum a_j z^j$ and a positive integer $n$ we have $$\sum_{k\equiv \alpha\pmod n} a_k=\frac1n\sum_{\omega:\omega^n=1} \omega^{-\alpha}f(\omega).$$

• Erm... The non-zero value may also come from the product of second and fourth powers. How do you account for those? Jun 4, 2018 at 15:02
• @fedja I am afraid that I do not understand you. Which second and fourth powers? Jun 4, 2018 at 15:37
• Ah, yes, sorry. I just misunderstood the argument entirely. No objection then. Jun 4, 2018 at 16:15
• @FedorPetrov Great works! Thanks a lot! I will check it . But where can I find the proof of this formula about the coefficient of $\prod_{i=1}^{n}x_i^{d_i}$ in the expansion of the polynomial $f(x_1, x_2,\cdots, x_{n})$? Jun 5, 2018 at 14:45
• We have 30, I guess, possible values for $[a_i,b_i,c_i,d_i,e_i]$ (proper 3-colorings of a 5-cycle.) Denote them $\{P_i\},1\leqslant i\leqslant 30$, further, if $P_k=[v_1,v_2,v_3,v_4,v_5]$ ($v_6:=v_1$), and $P_m=[u_1,u_2,u_3,u_4,u_5]$, we denote $h_k=(-1)^{\sum_{i=1}^5 v_i}\prod_{i=1}^5 \frac{v_{i+1}-v_i}{\binom{4}{v_i}}$; $A_{k,m}=h_k \prod_{i=1}^5 (u_i-v_i)$. The answer is the trace of the matrix $A^{2n}$. It remains to find the eigenvalues of $A$. Jun 7, 2018 at 6:34

Note that the problem asks essentially for the number of arrow arrangements on the edges such that at each vertex 2 arrows meet except these arrangements are counted with sign, which is $(-1)^N$ where $N$ is the number of "down" arrows plus the number of "right" arrows. For odd $m$ we immediately see from here that the answer is zero: the horizontal flip changes the parity of $N$, so each symmetric pair of arrangements cancels out.

Now take $m=2n$. We can immediately discard all arrangements that have vertical $3$-cycles because inverting such a cycle results in an admissible arrangement of the opposite parity. If we look at what is left, we see that in each column the numbers of vertical arrows converging at the 3 vertices in the column are 0,1,2 in some order and those numbers determine the arrows. The cyclic shifts of $\begin{bmatrix}0\\1\\2\end{bmatrix}$ have 2 downward arrows and, thereby, do not influence the parity, while the cyclic shifts of $\begin{bmatrix}2\\1\\0\end{bmatrix}$ have $1$ downward arrow. Now let's write those numbers and see what the horizontal arrows may be. If you see $2$ or $0$, it is clear, so the interesting part is $1$. Fix one column to start with and look at the direction of the horizontal arrows passing through $1$ in this column. Since the horizontal flip does not change the parity now, we can assume it is to the right and then just double the answer. Let's see what can be in the next column. You have two choices: either you keep $1$ in the same position and $0$ and $2$ flip (thus changing the column orientation), or you follow $1$ by $0$ (it cannot be $2$ because then you'll have too many arrows there), $2$ by $1$, and $0$ by $2$. Notice that the orientation of the horizontal arrows passing through the new $1$ is still to the right and if you choose the second option, then $1$ is shifted by a single position in the direction determined by the column orientation. Thus you have an oriented graph whose vertices are 6 rearrangements of $\begin{bmatrix}0\\1\\2\end{bmatrix}$ in which you want to count the cycles with signs. Note that the contribution to the parity of the horizontal arrows is just the sum of horizontal positions of $2$'s minus the sum of horizontal positions of $0$'s in each row, but if you sum over rows, you get $0$ because in each position (column) there is one $2$ and one $0$. Now you set up the $6$ by $6$ transition matrix for this problem (which looks something like $$\begin{bmatrix} 0 & -1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & -1 \\ 0 & -0 & 0 & -1 & 1 & 0 \\ 0 & -1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & -1 \\ 0 & -0 & 0 & -1 & 1 & 0 \end{bmatrix}$$ ("something like" because you may enumerate the positions differently from me; my original mistake was to put all $1$'s), note that it projects everything to a 3-dimensional subspace, on which it acts as $$\begin{bmatrix} 0 & -1 &1 \\ 1&0&-1 \\ -1&1&0 \end{bmatrix}$$ and compute the eigenvalues which are $0$, $\pm\sqrt 3i$. Thus the count (which is just the trace of the $2n$-th power of this transition matrix) is $2(-3)^n$ and we have to double it.

This is a bit sketchy, so feel free to ask questions. Alas, it does not help much with the $m\times n$ case.

Mathematica tells me the requested coefficient is $-36$.

In response to the comments, I evaluated the coefficient for larger arrays, of size $m\times n$. Denoting the absolute value of the coefficient by $C_{m,n}$ I find: $$C_{3,2}=12,\;\;C_{3,4}=36,\;\;C_{3,6}=108,\;\;C_{3,8}=324,\;\;C_{3,10}=972,$$ in agreement with the formula $C_{3,2p}=4\cdot 3^p$. Continuing to other values of $m$, I find

$$C_{2,2}=18,\;\;C_{2,4}=114,\;\;C_{2,6}=858,\;\;C_{2,8}=7074,$$ $$C_{4,2}=114,\;\;C_{4,4}=2970,\;\;C_{4,6}=98466,$$ $$C_{5,2}=180,\;\;C_{5,4}=4380,$$ $$C_{6,2}=858,\;\;C_{6,4}=98466.$$

Guess: the coefficients $C_{m,n}$ for $m$ and $n$ both even equal the number of Eulerian orientations of the torus grid graph $C_{m}\times C_n$, given by OEIS A29811:

This implies in particular that $C_{2p,2q}=C_{2q,2p}$. The value of $C_{2p,2q}$ follows from the even powers of the generating function $F_{2p}(x)$ given by $$F_2(x)=\frac{2 x \left(12 x^2-15 x+4\right)}{(1-x) (1-2 x) (1-3 x)},$$ $$F_4(x)=\frac{2 x \left(300 x^4-812 x^3+651 x^2-183 x+16\right)}{(1-x) (1-2 x) (1-5 x) \left(4 x^2-7 x+1\right)}.$$ I have not found a result for generating functions $F_{2p}(x)$ for $p>2$, is this an open problem?

• Indeed, $36$ it is (plus or minus depends on how you enumerate the vertices). Is Mathematica able to do the $3\times 40$ tesselation? (the human answer is plus or minus $2^{41}+4$ but humans are error-prone, you know...) Jun 3, 2018 at 21:42
• @Carlo Beenakker right answer. But I prefer to know how to calculate the answer out by hand. Is there any pattern in coefficient of the term in the expansion of the polynomial? Jun 3, 2018 at 22:33
• @fedja Yes, the case will be more complicated when there are more vertices and edges. Jun 3, 2018 at 22:38
• @CarloBeenakker "for m and n both even equal the number of Eulerian orientations" That was exectly my starting point and then I got confused with cancellations in the odd cases a bit. But how do you count those for big sizes? OEIS gives no hint whatsoever. Jun 4, 2018 at 14:58
• One reference for the connection between the coefficients of the graph polynomial and Eulerian orientations is Lemma 2.2 of "Colorings and orientations of graphs" by Alon and Tarsi cs.tau.ac.il/~nogaa/PDFS/chrom3.pdf . In particular, your guess holds true.
– j.c.
Jun 4, 2018 at 15:54